時間：2023-06-02 15:28:06
引言：易發表網憑借豐富的文秘實踐，為您精心挑選了九篇路徑規劃典型算法范例。如需獲取更多原創內容，可隨時聯系我們的客服老師。
作者簡介： 朱新平（1983-），男，博士，研究方向為先進機場場面運行控制，電話：13419037831，E-mail：
通訊作者： 韓松臣（1963-），男，教授，博士，研究方向為空中交通安全、空域規劃管理，E-mail：
文章編號： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027
摘要：
為支持先進機場場面活動引導與控制系統（A-SMGCS，advanced surface movement guidance and control system）實施航空器滑行的精確引導，將場面分為滑行道交叉口和直線段等典型運行單元，利用改進的擴展賦時庫所Petri網，建立了場面運行模塊化模型；采用該模型進行染色體編碼，并考慮場面運行管制規則，提出了染色體合法性檢測與修復算法，以及染色體交叉和變異算法.基于首都國際機場01號跑道實際運行數據，用本文模型和算法進行了多個航班滑行初始路徑規劃，研究結果表明：與節點-路段類模型相比，本文模型能更充分地描述場面管制規則約束，可避免生成違反管制規則的路徑；本文算法的每個航班初始路徑規劃耗時小于10 s，符合A-SMGCS的要求；由于考慮了航空器滑行速度調整特征，更符合場面運行的實際情況.
關鍵詞：
空中交通；A-SMGCS；滑行路由規劃； Petri網；遺傳算法
中圖分類號： V351.11文獻標志碼： A
航空器滑行自動路由規劃可以協調進離港航班安全有序地滑行，從而減少場面擁堵并提升場面容量.在國際民航組織（International Civil Aviation Organization， ICAO）提出的先進機場場面引導與控制系統（advanced surface movement guidance and control system， A-SMGCS）中，路由規劃功能是實現航空器場面滑行精確引導的前提[1].航空器場面滑行具有并發、資源共享特性，并受多種管制規則約束. A-SMGCS路由規劃不同于傳統道路網絡中的車輛路徑規劃，文獻[2]提出了A-SMGCS三階段路由規劃策略：
（1） 初始路徑規劃，為進離港航班確定最優滑行路徑和s-1個次優滑行路徑（s值由管制員動態交互確定）；
（2） 滑行前路由指派，依據航空器開始滑行前的場面態勢，為其確定合理路由；
（3） 路由實時更新，在航空器滑行過程中實時調整路由，以避免沖突發生.
本文僅考慮第（1）階段，即初始路徑規劃問題.
Petri網廣泛用于A-SMGCS場面運行過程的建模與沖突監控[3-4]，但較少用于航空器滑行路由規劃.文獻[5]將無向交通網絡轉換為Petri網表示的有向圖，并通過Petri網仿真器求解最短有向路徑.文獻[6]將機場滑行路徑描述為有向圖，并轉換為Petri網圖求解最佳滑行路徑.文獻[2]建立了基于Petri網的場面活動模型，并通過時間窗調度來進行路由規劃.上述研究建立的Petri網模型對場面管制規則約束考慮不全面，在算法設計上未充分利用Petri網的數學特征，且通常針對某一特定機場進行分析，實用性和通用性均顯不足.另一方面，將航空器場面滑行速度假設為恒定值[7-9]，忽略了航空器在場面不同區域滑行速度的調整變化，導致所得路由結果不能支持航空器滑行的精確引導.
在文獻[2]的基礎上，本文從以下方面展開研究：
（1） 給出一種擴展賦時庫所Petri網（extended timed place Petri net， ETPPN），以準確描述場面運行管制規則約束，并提出一種模塊化、面向路由規劃的場面運行ETPPN模型建模方法；
（2） 采用遺傳算法規劃航空器初始滑行路徑，其染色體編碼采用場面ETPPN模型的變遷激發序列，且交叉和變異均僅針對模型中的變遷進行，避免了以滑行道系統拓撲結構中的交叉口或直線段為基因組成染色體，在此基礎上展開的遺傳操作保證了方法的通用性；
（3） 與文獻[7-9]中關于航空器場面滑行速度恒定的假設不同，細化了航空器加減速特性對路段占用時間的影響，使路由規劃結果的精確度更高，實用性更強.
1
航空器場面運行過程建模
1.1
面向資源的場面運行過程建模
可見，采用ETPPN模型對場面運行進行建模，可描述航空器對場面各單元的動態占用與釋放，以及航空器在各單元滑行應遵循的管制規則.場面其它典型單元運行過程的Petri網建模也可采用本節的方法.不同機場的場面交通系統具有不同構型，但基本組成單元類似且有準確的數量和明確的運行規則.因此，利用各單元對應的ETPPN模型，并采用Petri網同步合成技術[10]可實現場面運行過程建模.
1.2
航空器滑行特征分析
航空器場面滑行速度具有以下特征：
（1） 當航空器先后通過的兩路段均為直線或彎道時，無須加減速；
（2） 當航空器從彎道滑入直線段時，須啟動加速過程；
（3） 當航空器從直線段滑入彎道時，減速過程通常在進入彎道前完成.
2
基于GA的初始路徑規劃算法
2.1
面向初始路徑規劃的GA設計
遺傳算法（genetic algorithm， GA）在工程優化領域已得到廣泛應用[11]，并越來越多地應用于航空器路由優化[12-15].本文提出基于場面ETPPN模型和GA的初始路徑規劃方法，基本思路為：
（1）
采用第1節方法，建立場面活動區中各典型運行單元對應的ETPPN模型，同時將場面管制規則約束集成到Petri網元素中，最終得到場面ETPPN模型；
（2）
以場面ETPPN模型為基礎，采用合適的編碼方式對模型中所含相關元素進行染色體編碼，并設計相關遺傳操作，求解初始滑行路徑集合（包括1個最優和s-1個次優滑行路徑）.
上述思路的優勢在于，對任何一個機場的航空器初始路徑規劃，所要解決的問題只需采用第1節的模塊化建模方法，將場面交通系統映射為對應的ETPPN模型并輸入管制規則約束即可，因而保證了所給算法的實用性和通用性.
2.2
染色體編碼
染色體應滿足以下約束：
（1） 物理約束.指與航空器自身占用物理空間大小或與滑行性能相關的約束，如翼展對通過某些區域的限制等.
（2） 管制規則約束.指管制規則確定的航空器在某些路段的滑行約束，如滑行速度約束、進出某機坪必經的交叉口等.
算法2中，步驟1保證了染色體不會出現重復基因，即所規劃滑行路徑不會出現環路；步驟2保證了航空器在單元內部的滑行過程滿足航空器性能要求，例如航空器在同一交叉口滑行時不能多次轉彎；步驟3～5保證了航班按照所規劃路徑滑行時能滿足相關約束.
2.3
選擇算子與遺傳算子
2.3.1選擇算子
2.3.2
交叉算子
2.3.3
變異算子
由于采用變遷激發序列進行染色體編碼，若采取隨機改變某一基因位變遷進行變異，則極有可能產生不滿足可激發約束的解.以往采取兩種方法解決該問題：第1種方法是隨機改變染色體，當生成了不滿足約束的解時再進行改正；第2種方法是在進行變異時保證不產生不可行解[16].
3
仿真試驗
3.1
仿真試驗設計
以首都國際機場為研究對象，采集T3航站樓東側飛行區某日實際運行數據，為所有進離港航班規劃初始滑行路徑集.該部分飛行區的場面交通系統結構如圖6所示，采用北向運行模式（使用01號跑道），且假設所有離港航班均使用全跑道起飛，即從跑道等待區Q0處（圖中方框所示區域）進入跑道起飛，進港航班從快速脫離道Q5、Q6、Q7脫離的比例為0.1∶0.6∶0.3.作為對比，采用文獻[12]的方法為圖6所示飛行區建立對應的節點-路段類有向圖模型，并采用基于遺傳算法的路徑規劃方法為航班規劃滑行路徑.
文獻[12]采取的優化目標是所有航班滑行的總里程最短，將其修改為與本文算法相同的優化目標，即滑行時間較短的s條滑行路徑（設s=3）.對比的目的是：
（1） 檢驗用本文所建場面模型進行路徑規劃是否比節點-路段類模型能更好地遵循管制規則；
（2） 檢驗本文初始路徑規劃算法的效率和有效性.
計算環境CPU為Interl（R） Pentium Dual 2.2 GHz，內存為4 GB.
具體實施過程為：在基于Anylogic的場面運行仿真平臺上建立對應的場面ETPPN模型，然后解析得到該模型對應的關聯矩陣并導入MATLAB2008a中，采用Sheffield大學的遺傳算法工具箱GATBX求解滑行路徑.在求解過程中，MATLAB可直接調用Anylogic存儲的相關庫所屬性數據庫，并采用遺傳算法工具箱GATBX進行求解.文獻[12]中算法的實現直接用MATLAB的遺傳算法工具箱GATBX完成.
3.2
仿真試驗結果及分析
為了給每個航班的進離港滑行規劃s
個滑行時間較短的初始滑行路徑，需要設置合理的遺傳算法參數.但目前在遺傳算法參數設定方面缺乏通用理論，一般根據問題難易程度和染色體編碼形式，由經驗和反復試湊來設定參數值.
用上述參數為離港航班SK996（所在機位511）規劃初始滑行路徑集（包含3條路徑）.由于遺傳算法具有一定的隨機性，可進行多次試驗，每次試驗得到的最短滑行時間均為246 s，因此認為對應的滑行路徑為最短滑行路徑.
圖8為在1次隨機試驗中不同遺傳代數所得路徑集的最短滑行時間和平均滑行時間變化曲線.由圖8可以看出，每次優化均能獲得最短滑行路徑，且隨著進化代數的增加，平均滑行時間越來越接近最短滑行時間，表明算法收斂性良好.
最終為該航班確定的初始滑行路徑集如表3所示.對每條路徑進行分析可知，在優化場面資源使用的同時，滿足了各類場面運行管制規則約束.
采用文獻[12]的遺傳算法為該航班規劃初始滑行路徑集，將求出的前3條較短滑行路徑參照圖6轉化為對應的節點形式，如表4所示.
由表4可見，路徑1和路徑2分別在滑行道K5和K4上未遵循該路段的運行方向約束，這與該算法設計僅考慮避免航空器之間的滑行沖突約束但未充分考慮其它約束有關.可見，在節點-路段類模型中，模型本身對管制規則約束的描述能力有限，僅在算法實現過程中考慮各類約束，可能影響路徑規劃結果的有效性.
此外，文獻[12]中設定的航空器具有單一固定滑行速度5 m/s，路徑3的滑行時間為467 s（表4），用本文方法路徑3的滑行時間為260 s（表3），二者相差較大.可見，考慮航空器滑行速度的調整特性，可更精確地計算航空器的滑行時間.
4
結束語
提出了一種面向A-SMGCS的航空器場面滑行初始路徑規劃方法，該方法具有以下特點：
（1） 定義一種擴展賦時庫所Petri網（ETPPN），可對航空器場面滑行過程進行建模，該模型充分體現了管制規則約束；
（2） 考慮航空器場面滑行速度調整特性，使規劃結果更接近實際運行需要；
（3） 采用場面運行ETPPN模型中的變遷激發序列進行GA染色體編碼，結合場面滑行特征給出交叉與變異設計，改變以往研究中對問題空間（場面拓撲結構）的直接處理，算法的通用性更好.
在求解初始滑行路徑時僅以滑行時間最短作為優化目標，今后需要考慮更多的優化目標，例如航空器加減速次數、轉彎次數等，并與其它路徑規劃方法進行比較.
參考文獻：
[1]International Civil Aviation Organization （ICAO）. Doc.9830-AN/452， Advanced surface movement guidance and control systems （A-SMGCS） manual[S]. 2004.
[2]湯新民，王玉婷，韓松臣. 基于DEDS的A-SMGCS航空器動態滑行路徑規劃研究[J]. 系統工程與電子技術，2010，32（12）： 2669-2675.
TANG Xinmin， WANG Yuting， HAN Songchen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics， 2010， 32（12）： 2669-2675.
[3]朱新平，湯新民，韓松臣. 基于EHPN的A-SMGCS機場滑行道運行控制建模[J]. 交通運輸工程學報，2010，10（4）： 103-108.
ZHU Xinping， TANG Xinmin， HAN Songchen. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering， 2010， 10（4）： 103-108.
[4]朱新平，湯新民，韓松臣. 基于DES監控理論的滑行道對頭沖突控制策略[J]. 西南交通大學學報，2011，46（4）： 664-670.
ZHU Xinping， TANG Xinmin， HAN Songchen. Avoidance strategy for head-on conflict on taxiway based on supervisory control theory of DES[J]. Journal of Southwest Jiaotong University， 2011， 46（4）： 664-670.
[5]黃圣國，孫同江，呂兵. 運輸網絡的最短有向路Petri網仿真算法[J]. 南京航空航天大學學報，2002，34（2）： 121-125.
HUANG Shengguo， SUN Tongjiang， LU Bing. Petri net simulation arithmetic of the shortest directional path in transportation net[J]. Journal of Nanjing University of Aeronautics and Astronautics， 2002， 34（2）： 121-125.
[6]張威，謝曉妤，劉曄. 基于Petri網的機場場面路徑規劃探討[J]. 現代電子工程，2007，4（1）： 59-61.
ZHANG Wei， XIE Xiaoyu， LIU Ye. Petri-net based airport surface routes planning[J]. Modern Electronic Engineering， 2007， 4（1）： 59-61.
[7]GARCIA J， BERLANGAA A. Optimization of airport ground operations integrating genetic and dynamic flow management algorithms[J]. AI Communications， 2005， 18（2）： 143-164.
[8]KEITH G， RICHARDS A， SHARMA S. Optimization of taxiway routing and runway scheduling[C]∥Proc. of AIAA Guidance， Navigation， and Control Conference and Exhibit. Honolulu： [s. n.]， 2008： 1-11.
[9]MARN G. Airport management： taxi planning[J]. Annals of Operations Research， 2006， 143（1）： 191-202.
[10]王化冰. 一種基于同步合成Petri網的FMS建模方法[J]. 系統工程理論與實踐，2001，21（2）： 35-42.
WANG Huabing. A Petri net synchronous synthesis method for modeling flexible manufacturing systems[J]. System Engineering： Theory and Practice， 2001， 21（2）： 35-42.
[11]GEN M， CHENG R W. Genetic algorithms and engineering optimization[M]. New York： John Wiley and Sons， 2000： 297-340.
[12]劉長有，叢曉東. 基于遺傳算法的飛機滑行路徑優化[J]. 交通信息與安全，2009，27（3）： 6-8.
LIU Changyou， CONG Xiaodong. Taxing optimization for aircraft based on genetic algorithm[J]. Transportation Information and Safety， 2009， 27（3）： 6-8.
[13]劉兆明，葛宏偉，錢鋒. 基于遺傳算法的機場調度優化算法[J]. 華東理工大學學報：自然科學版，2008，34（3）： 392-398.
LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm[J]. Journal of East China University of Science and Technology： Nature Science Edition， 2008， 34（3）： 392-398.
[14]GOTTELAND J， DURAND N， ALLIOT J M， et al. Aircraft ground traffic optimization[C]∥Proc. of the Genetic and Evolutionary Computation Conference. San Francisco： IEEE Press， 2001： 1-9.
[15]GOTTELAND J， DURAND N. Genetic algorithms applied to airport ground traffic optimization[C]∥Proc. of the 2003 Congress on Evolutionary Computation. Canberra： IEEE Press， 2003： 544-551.
關鍵詞：路徑規劃；搜索區域；A*算法
中圖分類號：TP306文獻標識碼：A文章編號：1009-3044(2008)21-30523-02
An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach
XU Zhan-peng, LIN Kai
(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)
Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time
Key words: Path planning; Search region; A* algorithm
1 引言
路徑規劃是在車輛行駛前或行駛過程中尋找車輛從起始點到達目的地的最佳行車路線的過程[1], 它屬于智能交通
系統中的最短路徑問題的一個具體應用。
最短路徑規劃產生的路徑分為兩種：距離最短的路徑和時間最短路徑,其中前者相對比較易于實現，但是它容易忽略路徑的具體情況和行車實際環境以及人為因素。因為在實際車輛行駛中要求不但在此路徑上行車距離盡可能短，而且路徑的行車環境盡可能好，即盡量走道路較寬、路面質量較好、紅綠燈較少、紅綠燈設置間隔較大、車流量較小的路徑，避免走行車環境太差的路徑。作者針對最短路徑規劃存在的不足之處 ,根據已有A*算法，給出了一種改進的最優路徑規劃算法，此算法在根據道路的實際情況對路網進行分層的同時，根據實際路網的拓撲特性對搜索區域進行合理的限制。
2 A*算法
A*算法是人工智能中一種典型的啟發式搜索算法．也是路徑規劃算法中的常用算法，它通過選擇合適的估計函數，指導搜索朝著最有希望的方向前進．以期求得最優解限制搜索區域的多層最優路徑規劃算法，A*算法評價函數的定義為[2]：
f(n)=g(n)+h(n) （1）
f(n)是從初始點通過節點n 到達目標點的估價函數；
g(n)是在狀態空間中從初始節點到n節點的實際代價；
h(n)是從節點n到目標節點最佳路徑的估計代價。它決定了搜索的效率和可采納性。對于幾何路網來說，可以取兩點間歐氏距離（直線距離）作為估價值，即
其中，(xd,yd)、(xn,yn)分別為節點n 和目標節點在數字地圖中的坐標。由于估價值h(n)≤n 到目標節點的距離實際值，算法具有可采納性，能得到最優解。[3]
3 改進的A*算法球最短路徑
本文在三個方面對傳統的A*算法進行了更改：1)A*算法提到的權值會根據用戶的不同查詢條件來調用相對應的計算權值的公式；2) 添加了一個判斷過程。當查詢下一個臨近邊的時候首先查詢交通控制策略，判斷是否有管制信息并將相映的點從v中刪除；3) 減少路徑搜索的范圍，以出發點與目的地點連線的中間點為圓心，以兩點之間直線距離的二分之一再加上幾公里為半徑畫圓，在圓范圍內的路徑參加搜索，在圓范圍之外的路徑不參加搜索。
具體實現如下：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點，設各個點的權值（也稱為費用值）為g。遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,計算X的估價值[4]。
1)初始的OPEN表僅包含原節點．其費用值g為0，令CLOSED為空表，設其他節點的費用為∞ 。
2)若OPEN表為空．則宣告失?。悍駝t，選取OPEN表中所有的節點移至CLOSED表，將此CLOSED表作為新的OPEN表。重復第二步，直到深度達到4。
3)對第二步在深度4時形成的OPEN表進行操作，若OPEN表為空．則宣告失敗：否則，選取OPEN表中具有最小權值的節點，并叫做最佳節點NEXT．把NEXT從OPEN表移至CLOSED表．判斷此NEXT是否是一目標節點。若NEXT為目標節點．轉步驟3，若NEXT不是目標節點。則根據地圖數據庫包含的聯接路段屬性擴展并生成NEXT的后繼節點。對于每一個后繼節點n，進行下列過程：
①計算節點n的費用：g(n)= NEXT費用+從NEXT到n的費用
②如果n與OPEN表上的任一節點相同．判斷n是否具有最小的g值。若是最低的g值，用n的費用代替OPEN表中相同的節點費用。且建立匹配節點的后向指針指向NEXT
③如果n在CLOSED表中與一節點相匹配。檢查節點n是否具有最小的g值，如果n具有最小的g值，則用節點n的費用代替匹配節點的費用。并把匹配節點的后向指針指向NEXT。并把該匹配節點移到OPEN表
④如果n不在OPEN表。也不在CLOSED表上，則把n的后向指針指向NEXT。井把n放入OPEN表中。計算節點n的估價函數：f(n)=g(n)+h(n)
例如圖1，為帶權的有向圖。
根據步驟三，針對圖1，算法的具體實現如圖2。
4)重復第三步：
若在深度為7的搜索中找到目標結點且僅有一條路徑，則該路徑為最終路徑，返回；
若在若在深度為7的搜索中找到目標結點并且有多條路徑則回朔，比較找到的路徑費用，取權值最小的作為最終路徑；
若在在深度為7的搜索中未找到任何目標點則跳轉到第五步。
5)從深度為7的搜索中的所有的NEXT節點回朔，即從NEXT的后向指針一直到原節點遍歷節點，最后報告若干條路徑，比較個路徑費用，取費用最小的前100條路徑繼續重復第三步、第四步。由于h函數在滿足h下限得條件下，愈趨近于h效率愈高，因此實際應用中，我們取的是節點到目的點的直線距離保證滿足下限的情況下，盡可能的趨近h。
4 結語
實踐表明基于改進A*算法的限制搜索區域的路徑規劃方法不僅在進行路徑規劃時節省了時間，而且規劃后的路徑大部分道路位于高層路網上，路徑長度與最短路徑長度之比小于1.1,可以被人接受，是行車意義上的最優路徑。
參考文獻：
[1] 付夢印.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報,2004(10).
[2] 趙亦林.車輛定位與導航系統[M].北京:電子工業出版社,1999:1-7.
[3] 王亞文.智能交通系統中路徑規劃算法研究與系統設計[D].陜西師范大學,2007.
【關鍵詞】神經動態規劃 最優路徑 子問題 Matlab仿真
為了減輕交通壓力，人們越來越關心交通系統的智能化進程。智能交通系統主要的研究方向之一就是動態路徑誘導系統，它可根據外出的人們的需求，為駕駛員提供最新的路況信息和最佳路徑選擇，以此避免交通擁堵現象的發生，從而優化交通狀況，最終使交通時時地保持一個合理的動態分配。目前，最優路徑選擇的方法有很多，但是真正需要解決大型問題時，計算機需要搜索的選擇范圍太大，傳統的動態算法基本上無法處理。1995年，神經動態規劃算法被提出，該算法把復雜的問題分成若干子問題，這些子問題被拆分后更容易解決，使計算過程大幅簡化，且更容易被計算機處理。采用這種方法，可準確、快速、實時、穩定地選擇出最優路徑，值得推廣。
1 神經動態規劃概述與核心思想
在解決多階段決策問題時，動態規劃大致思想為：將非常繁瑣的原始問題分解為若干個階段，這些階段看似不相關，卻是相互聯系的子階段，在找到上一階段的解決方法以后才能處理下一個階段，依次求出每個階段的解，最后得到全局最佳的解。多階段決策問題具備很強的順序性，同時每個階段所使用的解決方法也是隨著階段的變化而變化，所以“動態”意義就得以體現。其中交通網中最佳路徑的求解就是典型的多階段決策問題。
在路徑優化中，動態規劃是一種非常經典的計算方法，但在處理實際問題的時，我們肯定會遇到缺少一個完整信息或者維數災等一系列問題，所以，引進神經網絡對動態規劃具有較大的解決實際問題的意義。神經動態規劃如圖1所示。
2 基于神經動態規劃算法的最優路徑實現
（1）將原來的問題分解成很多個小問題，即子階段，并且找到每個子階段的最優解決辦法。求解多級問題的步驟為：根據每個問題的特點，劃分子階段。在劃分子階段時，必須按照一定的規則，比如根據執行決策的時間、空間的順序等。本文用x來表示子階段變量。
（2）求解狀態和狀態變量。每個子階段具體的起始位置可以依靠自然狀態來指導，其中客觀條件階段性數目的狀態是自然狀態中的一種，它傳達每個子階段的關鍵信息，此外，一組或者無后效性的變量同樣可以用來表示狀態變量。本文用Hx來表示第x級的狀態變量。
（3）求解原問題決策變量和集合。從目前階段到下一個階段狀態選擇時，決策者需要做出恰當的決策，決策變量的范圍稱為集合。本文用Dx表示決策集合，用Ux表示決策變量。
（4）研究狀態轉移的方程。假設狀態轉移方程是：Hx+1=Tx（Hx，Ux）。次方程式中Tx不定，根據具體問題才能確定，如果Hx確定，一旦變量Ux確定，那么第x+1階段狀態變量（Hx+1）也將確定。
（5）研究指標函數。因為n和vi的遞進性和可分離性，所以很容易找到指標函數n和vi之間的關系，顯然，指標函數的求解也相對簡單化。
（6）動態規劃函數的基本方程。邊界條件為；
，第x-m階的最優動態規劃函數是。
3 仿真結果
將上述模型，在Matlab仿真軟件上進行模擬仿真，分解原始問題并確定各個子階段的最佳方案，將這個問題用網格的形式如圖2進行表示：A為起始地點，E為目標地點，從起始地點到目標終點有很多路徑，假設經過每個節點需要一定的運輸成本，在Matlab仿真軟件上進行仿真后依據動態規則算法的要求，設定好相應的算法模型以及相應的計算公式，這樣便可以找到最優路徑。
由圖2可以非常清楚的看出，成本最低的路線為：或者或者，成本都是110。仿真結果可以看出神經動態規劃算法具有較多優點：得到清晰運算結果；很容易找到全局的最優路徑；可以找到一組完善的解，有利進一步的分析。
4 結語
我們在使用神經動態規劃算法來探索最優路徑的時候，具有很多優勢，首先其具有穩定、可靠的步驟，過程并不復雜，但是給予我們的結果十分清晰明確，且適用于現實生活。使用這種動態規劃算法解決復雜的問題時，可以非常容易找到解決方案，而且效率很高。當然，該算法也有一定的局限，但只要我們不斷地改進完善，日后繼續研究神經動態規劃算法，相信一定可以攻克更多的局限，能夠使其更好地被應用。
參考文獻
[1]謬慧芬，邵小兵.動態規劃算法的原理及應用[J].中國科技信息，2006（23）：32.
[2]楊琰，廖偉志，李文敬，楊文，李杰.基于Petri網的顧及轉向延誤的最優路徑算法[J].計算機工程與設計，2013（10）.
作者簡介
楊超（1994-），男，廣東省吳川市人?，F在就讀于長沙理工大學計算機科學與技術系。
關鍵詞：最短路徑；動態規劃；C 語言編程
中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）09-2191-03
1 概述
數學源于生活，又服務于生活.它是一門研究現實世界中的數量關系與空間形式的學科.當今社會，隨著物質水平的不斷提高，生活需求的不斷擴大，自然資源的不斷開發利用.像天然氣管道鋪設問題，廠區布局問題，旅行費用最小問題等都已成為我們平時經濟生活中的普遍問題.它們其實都可以化歸為最短路線問題，而最短路問題實質上是一個組合優化問題[1]。
動態規劃方法主要是研究與解決多階段決策過程的最優化問題，它將求解分成多階段進行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實際問題時，更顯其優越性。為了快速、簡單的計算最短路徑，節約運輸時間與成本，該文利用動態規劃的思想編寫了C語言程序，解決物流運輸過程中多地點的最短路徑的選擇問題。
2 最短路徑問題
2.1 最短路徑問題算法的基本思想
在求解網絡圖上節點間最短路徑的方法中，目前國內外一致公認的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網絡被抽象為一個圖論中定義的有向或無向圖，并利用圖的節點鄰接矩陣記錄點間的關聯信息。在進行圖的遍歷以搜索最短路徑時，以該矩陣為基礎不斷進行目標值的最小性判別，直到獲得最后的優化路徑[2]。
Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎。為了求出賦權圖中任意兩結點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結點為源點，重復執行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復雜度為[On3]，雖然與重復執行Dijkstra算法n次的時間復雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。
2.2 最短路徑問題算法的基本步驟[3]
這樣經過有限次迭代則可以求出[v1]到[vn]的最短路線。
（2）Floyd算法的基本步驟
（3）動態規劃算法基本步驟
我們將具有明顯的階段劃分和狀態轉移方程的規劃稱為動態規劃[1]。在解決多個階段決策問題時采用動態規劃法是一個很有效的措施，同時易于實現。
根據動態規劃的基本概念，可以得到動態規劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態變量。4）根據狀態變量確定費用函數和目標函數。5）建立各階段狀態變量的轉移過程，確定狀態轉移方程。
根據動態規劃的基本模型，確定用動態規劃方法解題的基本思路，是將一個[n]階段決策問題轉化為一次求解[n]個具有遞推關系的單階段的決策問題，以此來簡化計算過程.其一般步驟如下：
用于衡量所選決策優劣的函數稱為指標函數.指標函數有有階段的指標函數和過程的指標函數之分.階段的指標函數是對應某一階段狀態和從該狀態出發的一個階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標函數是指從狀態[xn（k=1，2，...，n）]出發至過程最終，當采取某種子策略時，按預定的標準得到的效益值。這個值既與[xk]本身的狀態值有關，又與[xk]以后所選取的策略有關，它是兩者的函數值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標函數又是它所包含的各階段指標函數的函數。本文研究的過程的的指標函數是其各階段指標函數的和的形式.當[xk]的值確定后，指標函數的值就只同k階段起的子策略有關。對應于從狀態[xk]出發的最優子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態規劃求解最短路徑程序流程圖如圖2所示。
3 最短路徑態規劃實際應用舉例
設某物流配送網絡圖由12個配送點組成，點1為配送中心起點，12為終點，試求自終點到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離[4]。
首先用動態規劃法來討論圖3的最短路徑，由圖可知：
1）集合[ξ4]中有點9、10、11，它們在一步之內可到達點12；
2）集合[ξ3]中有點6，7，8，它們不超過兩步就可達到點12；
3）集合[ξ2]中包括點 2、3、4、5，不超過三步就可到達點12；
4）集合[ξ1]中包括點1，不超過四步可到達點12；
按照動態規劃法類推，得到最優路徑長為16，徑路通過點為1，2，7，10，12和1，3，6，10，12。
根據動態規劃算法編寫C語言計算程序[5] [6]，計算得到實驗結果如下圖4所示：
由圖4可以看出程序得到的結果與本文推出的結果一樣。證明了本文編寫的C語言程序是正確的。
4 結束語
綜上所述，用動態規劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實現.我們可以看到，動態規劃方法的應用很廣泛，已成功解決了許多實際問題，具有一定的實用性。此種算法我們用動態規劃思想來編程，并解決相應的問題，其在 VC 環境下實現，能方便快速的計算出到達目的地的最短距離及路徑，節省更多的運輸時間與成本。不過，該文只考慮了動態規劃算法在生活中的簡單運用，在實際生活中可能存在多個目的地或者更復雜的情況.因此我們可以考慮將其進行改進或者結合啟發式算法，使之更好的運用在實際生活中，這有待于以后的繼續研究。
參考文獻：
[1] 杜彥娟.利用動態規劃數學模型求解最短路徑[J].煤炭技術，2005（1）：94-95.
關鍵詞:移動多智能體;全局規劃;局部規劃
中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)16-4487-03
Research on Path Planning for Mobile Multi-Agent
CHEN Cui-li, GAO Zhen-wei
(Henan Normal University, Xinxiang 453007,China)
Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.
Key words: mobile Multi-Agent; global path; local path
在移動智能體相關技術研究中,路徑規劃技術是一個重要研究領域。移動智能體路徑規劃問題是指在有障礙的環境中,尋找一條智能體從起始點到目標點的運動路徑,使智能體在運動過程中安全、無碰撞地繞過所有的障礙物。這不同于用動態規劃等方法求得最短路徑,而是指移動智能體能對靜態及動態環境下做出綜合性判斷,進行智能決策。在以往的研究中,移動智能體路徑規劃方法大體上可以分為三種類型:其一是基于環境模型的路徑規劃,它能處理完全已知的環境下的路路徑規劃。而當環境變化時(出現移動障礙物)時,此方法效果較差,具體方法有:A*方法、可視圖法、柵格化和拓撲圖法等;其二是基于傳感器信息的局部路徑規劃方法,其具體的方法有:人工勢場法、模糊邏輯法和遺傳算法等;其三是基于行為的導航行為單元,如跟蹤和避碰等,這些單元彼此協調工作,完成總體導航任務。隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。
一個好的路徑規劃方法需要滿足如下性能[1]:合理性、完備性、最優性、適時、環境變化適應性和滿足約束。有些方法沒有高深的理論,但計算簡單,實時性、安全性好,就有存在的空間。如何使性能指標更好是各種算法研究的一個重要方向。
在未知的(或部分已知的),動態的非結構的環境下,多智能體利用傳統的路徑規劃方法很難滿足前面的性能要求,本文提出了一種將全局路徑規劃方法和局部規劃方法相結合,將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。
1 路徑規劃方法
1.1 相關研究
1) A*算法
在最佳優先搜索的研究中,最廣范圍應有的方法為A*搜索,其基本思想[2]是:它把到達節點的代價g(n)和從該節點到目標節點的代價h(n)結合起來對節點進行評價:f(n) = g(n) + h(n)(1)。A*算法用于移動多智能體的路徑規劃時,多智能體分別按照已知的地圖規劃出一條路徑,然后沿著這條生成路徑運動,但智能體傳感探測到的環境信息和原來的環境信息不一致時,智能體重新規劃從當前位置到目標點的路徑。如此循環直至智能體到達目標點或者發現目標點不可達[3]。重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且由于采用A*方法規劃出的最優路徑并沒有考慮到機器人的運動學約束,即使機器人可以采用A*方法規劃出一條最優路徑,機器人也未必可以沿著這條路徑運動。
2) 人工勢能法
人工勢能法由 Khatib 提出的一種虛擬力法[4]。人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但根據人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只能局部的,當智能體和障礙物超過障礙物影響范圍的時候,智能體就不受來自障礙物引起的排斥勢場的影響。所以,勢場法只能解決局部空間的避障問題,他缺乏所在的全局信息,,這樣就造成產生局部最優解不能進行整體規劃,智能于局部最小點的時候,智能體容易產生振蕩和停滯不前。
1.2 路徑規劃方法描述
鑒于A*算法全局路徑搜索的全局性與改進人工勢場算法局部路徑搜索的靈活性,通過一定的方法把兩者結合起來,其思路如下:多智能體分別采用A*算法進行全局路徑規劃,各自生成到達目標點的子目錄節點序列,同時采用改進的人工勢能對子目錄節點序列中相鄰節點進行路徑的平滑和優化處理,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數增加。采用改進人工勢場的局部路徑規劃方法對A*方法進行優化,可以有效增大A*方法的柵格粒度,達到降低A*方法運算量的目的。
2 環境構造
目前主要有三種比較典型的環境建模方法:構型空間法、自由空間法和柵格法,本文仿真實驗采用的環境建模方法是柵格法,柵格法將機器人路徑規劃的環境劃分成二維網格,每格為一個單元,并假設障礙的位置和大小已知,且在機器人運動過程中不會發生變化。柵格法中的網格單元共有三種類型,即障礙網格、自由網格和機器人所在網格。目前常用的柵格表示方法有兩種,即直角坐標法和序號法。這兩種表示方法本質上是一樣的,每個單元格都與(x, y)一一對應。本文采用序號法表示柵格,設柵格的中心點坐標為柵格的直角坐標,則每個柵格編號都與其直角坐標一一對應,地圖中任意一點(x,y)與柵格編號N的映射關系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數表示取整,而柵格中心點的坐標為(xG,yG),它與柵格編號N之間的關系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號%表示取余操作。本文中根據機器人的尺寸來確定柵格的粒度,假設一個柵格能容納一個智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環境為800cm×800cm,柵格號N=0~399,機器人的初始位置的柵格號為N=42,目標位置的柵格號為N=314。在Visual Studio 2005中進行仿真,仿真結果如圖1所示,長方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機器人的起始柵格和目標柵格,剩下的是自由柵格。在路徑規劃中機器人可以選擇自由柵格作為它的路徑點。
建立柵格后,對柵格進行初始化。設置變量G_Obstacle為0表示自由柵格,G_Obstacle為1表示障礙網格包括機器人柵格。若障礙物或智能體占當前位置柵格面積大于1/3則設置變量G_Obstacle為1.
3 數據的采集
對于簡單地形,我們將實際地形就行考察并進行測量、量化,轉化為平面坐標數據最后轉換相應的柵格編號。對于復雜地形在沒有航攝資料的情況下,本實驗以地圖為數據源的DTM數據獲取方法在,可利用已有的地形圖采集地形數據,用手扶跟蹤式數字化儀將平面圖形轉化為平面坐標數據,最后轉換相應的柵格編號。
4 實現過程
第1步:對環境信息進行數據采集并轉化成相應的平面坐標數據。
第2步:確定各個智能體的初始位置和目標位置。
第3步:建立柵格,對柵格進行初始化。
第4步:智能體S(i)首先根據已知信息規劃出各自的一條目標序列S(i)n。
第5步:智能體S(i)利用測試傳感器探測到臨界危險區L范圍內的信息與原有信息是否一致,當智能體利用傳感器探測到臨界危險區L范圍內的信息與原有信息一致時,利用改進后的人工勢能算法搜索相鄰目標點之間的軌跡,否則智能體搜索從當前序列點S(i)n到S(i)n+4路徑。定義臨界危險區L、目標序列點S(i)n(n>=1)。
第6步:智能體一旦移動到達目標柵格,則程序終止;否則返回第5步。系統的工作流程如圖2所示。
5 仿真結果及結論
在Visual Studio 2005平臺上進行了仿真,,首先根據已知環境信息,進行數據采集量化并進行柵格化處理,設置障礙和智能體的大小及位置(為了簡單化,本實驗所有障礙都設置為圓形),再進行初始化操作,采用0、1二元信息數組存儲柵格化的地形。
智能體運用A*算法進行全局路徑規劃,圖3顯示兩個智能體的運動過程,顯然兩個智能體的路徑相交可能會發生碰撞,智能體為了避免碰撞應重新規劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且顯然只用A*算法規劃出二維路徑點序列,相鄰兩點之間的夾角一定是π/4的整倍數,機器人很難按照所生成的序列點運動。智能體采用改進后的人工勢場進行目標序列點之間的局部路徑規劃,圖4顯示智能體的運動過程。顯然智能體的整條運動軌跡顯得比較平滑同時又實現實時避障的目的。
6 總結
本文對多智能體在動態環境下路徑規劃技術進行了研究探索,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。
參考文獻:
[1] 劉華軍,楊靜宇,陸建峰,等.移動機器人運動規劃研究綜述[J].中國工程科學,2006,8(1):85-94.
[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.
關鍵詞：快速搜索隨機樹；汽車局部路徑規劃；高斯分布；路徑跟隨
中圖分類號：TP242 文獻標志碼：A
An Improved RRT Algorithm of Local Path Planning for Vehicle Collision Avoidance
SONG Xiaolin，ZHOU Nan，HUANG Zhengyu，CAO Haotian
（Stake Key Laboratory of Advanced Design and Manufacturing for Vehicle Body， Hunan University，Changsha 410082，China）
Abstract：The original Rapidly-exploring Random Trees（RRT） algorithm has a rapid exploring-speed and short required time in path planning though it has large randomness and lacks of constraints. Thus， an improved RRT was proposed where the expected paths were built in both straight and curved roads. The random points were accorded with normal distribution around the expected paths. Heuristic search method that led the random points to the goal with a certain probability was also used for improvement. Compared with the original RRT algorithm， it performs quite well in both time-efficient and path quality in the simulation. Meanwhile， the effectiveness of the improved RRT algorithm was verified in Prescan. The path can be followed well and the secure lateral acceleration was satisfied. In conclusion， the improved RRT is effective in the path planning for vehicle collision avoidance.
Key words： rapidly-exploring random trees； vehicle path planning； Gauss distribution； path following
近年來隨著汽車向智能化的不斷發展，無人駕駛汽車技術引得越來越多人開始關注.路徑規劃作為其中一項關鍵技術，許多學者開展了有益的探索，并取得了一些研究成果.比如A*算法[1]、D*算法[2]等啟發式搜索算法，在復雜環境下有著很好的規劃速度，但是路徑并不理想；人工勢場法[3]是一種虛擬力算法，其優點是規劃的路徑平滑，但是容易陷入局部最優解；人工勢場法與彈性繩模型結合[4-6]在車輛局部路徑規劃時有理想的路徑，但由于模型比較復雜，搜索效率低；此外蟻群算法、遺傳算法、神經網絡算法、水滴算法等智能仿生算法[7-10]，在理復雜動態環境信息時有較好表現，但由于需迭代計算，時效性不夠好.
快速搜索隨機樹算法（RRT）[11]由Lavalle于1998年提出，是一種基于樹結構的典型算法，在移動機器人路徑規劃中有著較早應用.由于算法在進行路徑規劃時是隨機采樣，不需要預處理，因此有著很快的搜索速度.路徑點之間可以經過運動學、動力學仿真生成可執行曲線，因此該方法可用于解決含有運動學約束的路徑規劃問題.但RRT算法存在一些不足：1）重現性差，對同一環境進行多次路徑規劃結果不同；2）尋找最優或者次優路徑能力較差；3）隨機采樣點在整個可行域內隨機尋點的搜索方式，存在很多不必要的運算，影響算法速度.
隨著RRT算法的應用和改進，一些學者也提出了不同的方法.偏向RRT[12]以及雙向RRT[13]的提出使得算法的搜索效率得到了提高；DRRT[14]與MP-RRT[15]原算法在搜索路徑的穩定性上做出了改進.但上述改進之后的結果并不適用于汽車行駛路徑.針對以上不足，本文將建立道路模型，考慮路徑約束，改進RRT算法，使其規劃出的路徑能夠適用于汽車運動.
1 道路環境建模
在環境已知的情況下，建立道路環境模型.直道環境模型根據道路長度以及車道寬即可得到，彎道環境模型如圖1所示，位于道路上的慣性坐標系的原點選取在道路中心線上，道路寬度為W，規劃起始點即主車位置A，目標點C，障礙車位置為B.高速路直線之間的緩和曲線通常采用回旋線來實現平滑過渡，回旋線的特征是其曲率變化為常數.假定長度為l的回旋線線段起始曲率為C1，終止曲率為Cf，變化常數為C2，則有C（l）=C1+C2×l成立，C2=（Cf-C1）/l.回旋線常采用多項式逼近的形式表示：
式中：R0為道路中心線初始橫向偏移；C0為初始的方向角.根據圖1，結合邊界條件R（0）=0，R′（0）=0可以將R0和C0消除掉.
為了保持車道寬度一致，彎道的左右邊界是通過中心線上點向著其法線方向上下平移單個車道寬度來得到.在道路坐標系下中心線上的點可由式（2）表示.
中心線上一點的切向量和法向量則可以表示成：
因此道路左右界則可以由（4）來表示
2 RRT算法原理
基本的RRT算法如圖2所示，RRT算法以給定的起始點為隨機樹根節點，根據當前環境快速有效地搜索可行域空間，通過隨機采樣點，將搜索導向空白區域并增加隨機樹的葉節點直至目標點區域，從而生成從起始點到目標點的路徑.
算法的一般步驟如下：
1）首先通過environment（）函數建立環境數據模型，初始化各項參數；
2） 通過while循環來判斷樹節點是否達到目標點goal范圍內，若沒有，則開始擴展點.先生成隨機采樣點Prand，在樹節點上通過函數Nearest（）選擇距離Prand最近的樹節點作為擴展節點Pnear，通過擴展函數New得到新的樹節點Tnew，并將其添加到隨機樹上，直到循環終止.
3）通過getpath（）函數來得到生成的路徑path.
原算法主體程序如下：
如圖3所示，傳統的RRT算法應用到車輛路徑規劃中存在以下問題：
1）由于隨機采樣點隨機性大，導致搜索空間中有過多的冗余搜索，表現為搜索樹布滿了道路環境空間；
2）搜索出來的路徑曲率變化過大，甚至出現小范圍內直角變化，這樣的路徑并不能滿足汽車行駛的正常狀態；
3）路徑在靠近障礙時才開始避障，對于運動中的汽車會造成失穩或者與障礙物發生碰撞.
道路長度/m
3 RRT算法的改進
3.1 期望路徑模型
針對原RRT算法表現出來的問題，提出了一種隨機采樣點高斯分布的改進RRT算法.根據汽車行駛環境不同，設計了兩種期望路徑模型.
3.1.1 直道模型
駕駛經驗豐富的駕駛員期望的避障路徑模型如圖4（a）所示.期望路徑以函數Epz表示，其中各段均為直線段，start為起始點，goal為目標點.
提前避障在車輛避障路徑規劃中是必要的，故在模型中需要添加提前避障距離S，并根據車速調整大小.設V為當前車速，tc為換道時間，通常完成換道時間tc為1～2 s，ΔS為自定義安全提前量.
對于車速為V的汽車其剎車距離
則提前避障距離
圖4（a）中fz2表示提前避障區域，區間長度為S，fz4區間長度也為S.
期望路徑只是粗略的路徑模型，在此基礎上進行平滑得出的路徑并不能滿足汽車安全穩定行駛的要求.因此采用RRT算法進行路徑尋優搜索.為了使隨機采樣點分布在期望路徑周圍，利用高斯分布函數生成的點集中在其均值周圍的特點，結合期望路徑函數則可以實現這一目的.在道路坐標系下隨機采樣點的高斯分布概率函數為：
令μ=Epz（x），則可以得到如圖4（b）所示的隨機采樣點分布趨勢圖.
道路長度/m（a）期望路徑模型
道路長度/m（b）隨機采樣點高斯分布
σ的大小決定了隨機點在Epz（x）周圍的集中程度，σ越小越靠近Epz（x）.特別地，對于fz2與fz4周圍的隨機采樣點，如圖4（a）以fz2為例，通過相應水平范圍的隨機點高斯分布旋轉處理得到，即對
旋轉角度：
3.1.2 彎道模型
將彎道分為多段，采用直線代替彎道曲線的形式來完成期望路徑模型的建立.如圖5（a）彎道的期望路徑以函數Epw來表示.
隨機采樣點在fw各段函數區間的分布同直道的處理相同，從而可以得到如圖5（b）所示的分布趨勢圖.
3.2 約束條件
要使一條規劃出來的路徑有效地應用于汽車運動，即路徑可跟蹤，則規劃路徑時必須滿足道路環境約束.首先，隨機樹節點的生成要滿足道路環境約束，設Bleft，Bright分別為道路的左右邊界，則樹節點位置坐標要滿足：
考慮到汽車是具有幾何形體的，設其車寬為D，則上述y方向的約束變為：
假定汽車質心沿著規劃的路徑運動，為了保證行駛過程中的穩定性，規劃出的路徑的曲率變化不能過大.若在實際情況下前輪最大轉角為θmax，則路徑中子節點與其父節點的連線和父節點與其父節點的連線之間的夾角β必須滿足β
其中：K1為直線TaTb的斜率；K2為TcTb的斜率.βT為夾角限制值.
為了保證所擴展的點不與障礙車有交集，即樹節點不與障礙車碰撞的要求，采用安全橢圓包絡障礙車，并適當放大安全橢圓以保證避障要求.若新節點與其父節點的連線不與安全橢圓相交，則所擴展的新點滿足避障要求.取連線上的五等分點Pi（x，y），則約束方程表現為：
其中（xob，yob）為障礙車的位置，半車長a=2 m；半車寬b=1 m；s為安全橢圓放大系數，當s=2時，安全橢圓正好包絡矩形的障礙車，因此從安全避障考慮，s≥2.
3.3 啟發式搜索
原算法在擴展隨機樹時，由于缺乏導向機制，算法的收斂速度在一定程度上受到了影響，為了提高算法計算速度，引入啟發式機制來對隨機采樣點以及隨機樹節點的選擇進行處理.采樣點Prand在隨機生成過程中會以一定概率ρ0選擇目標點，從而將隨機樹節點向目標點引導，通常ρ0=0.1.
其中，GaussRand（）為隨機采樣點生成函數.
另外，在選擇Pnear時不再單獨以距離Prand最近作為選擇標準，而是以隨機樹節點的擇優系數Ch來決定，Pnear確定為Ch值最小所對應的樹節點.
其中ωi，ωj為權重系數，且ωi+ωj=1；Dpr為樹節點到Prand的距離，Dg為樹節點到目標點goal的距離.當ωj>ωi時，選擇出的Pnear具有向目說憧拷的趨勢.通過以上啟發式的處理，使得算法更快地收斂，減少計算時間.
3.4 平滑處理
RRT算法規劃出來的路徑通常會存在小范圍內的曲折現象，路徑并不連續.為了使得路徑能夠滿足汽車在運動時的穩定性和安全性要求，需要對規劃出來的路徑進行光滑處理.B樣條在處理路徑光滑時能夠不改變整個路徑形狀而進行局部調整[16]，利用B樣條這一特性，來對算法所規劃出來的路徑進行插值擬合，從而達到光滑路徑的目的，通常所采用的為3次B樣條曲線.
當有m+1個控制頂點Pi（i=0，1，…，m）時，3次B樣條曲線表示為：
3.5 算法流程
隨機樹節點的擴展受到隨機采樣點的影響，通過以上方式的處理，隨機采樣點不再是在可行域內隨機分布，而是具有一定的趨向性.這樣使得隨機樹節點的分布也具有趨向性，算法的隨機性得到了改善，所規劃出來的路徑質量得到提高.主體程序如下：
算法的實現過程如下：
1）初始化階段，首先通過environment（）函數建立道路環境模型，根據現有的環境模型，以expect（）函數建立期望路徑模型.
2） 路徑求解階段，進入while循環來判斷樹節點是否達到目標點goal范圍內，若沒有，則開始擴展點.隨機采樣點Prand通過Pick（）函數在goal和GaussRand（）函數所生成的點之間進行概率選擇；根據當前Prand計算樹節點的擇優系數Ch，并由Fitbest（）函數得出Pnear；通過函數New在Pnear的基礎上擴展出新節點Tnew，當新節點滿足約束函數constraint（）時，新節點則添加到整個隨機樹Tree上，否則，返回循環重新尋點直到其終止.
3）路徑處理階段，getPath（）函數從所得的Tree中獲取最短路徑，最后通過函數smoothing（）對所得路徑path進行光滑處理，得到一條平緩的路徑.
4 仿真實驗驗證
改進的RRT在應用于信息多變的不確定環境時會存在建模困難的缺陷，本文主要對確定車道環境下的改進RRT開展研究.由于條件有限，不能在實際車輛中進行試驗驗證.而Prescan軟件能夠對實際場景進行建模，并且有根據實車建立的車輛模型數據庫，能夠模擬實際車輛行駛過程.因此，為驗證改進RRT算法的有效性，在Prescan軟件平臺中搭建直道和彎道場景如圖6所示，仿真實驗硬件平臺Win10+Core-i7@3.6Hz+ARM@8G.仿真參數如表1～表3所示.
4.1 規劃時間的影響參數分析
影響算法計算效率的重要參數主要包括搜索步長ΔL、約束夾角βT.步長越小，為了搜索到目標點所需要的節點數目也就越多，計算時間越長；約束夾角βT越小，規劃路徑也越平緩，但計算時間也越長.改變步長以及約束夾角并進行大量仿真實驗，統計表明：在ΔL=3，βT=15°時，改進RRT算法在規劃時間以及路徑效果上的綜合表現較好.圖7為ΔL=3時，不同角度下計算時間的統計，以20次計算時間平均值做一次統計.
4.2 規劃路徑對比
為說明改進RRT算法的效果，在直道場景中，采用了其余2種規劃算法來進行對比.一種是蟻群算法[7]，另一種是彈性繩算法[5].直道仿真對比結果如圖8所示，改進前后的算法規劃效果在彎道中的對比如圖9所示，路徑效果參數對比如表4所示.由圖和表的結果對比可知：
1）相對于蟻群算法和原RRT算法，改進RRT算法與彈性繩算法規劃的路徑都更為平滑，不存在頻繁的大曲率變化，且路徑較短.
2）從直道的規劃時間上看，傳統的蟻群算法用時最長，而彈性繩算法平均計算時間為1.42 s.改進后的RRT算法平均計算時間0.25 s，相對于原RRT計算時間略有增加，這是由于增加了模型處理過程以及各約束條件所導致的.但與其余2種算法相比，改進RRT算法依然保持其在計算時間上的優勢.
3） 原RRT算法在靠近障礙時才開始避障，改進RRT算法能夠實現提前避障，并且根據車速不同自動調節避障提前量，這對安全行駛很重要.
4.3 路徑跟隨驗證
對一條規劃出來的路徑，需要驗證其有效性，即路徑的跟隨性，本文采用路徑跟隨時主車的側向加速度曲線監測路徑的穩定性，跟隨速度20 m/s.直道和彎道仿真結果分別如圖10、圖11所示.
由圖10（a）（b）可知，直道跟隨路徑基本和目標路徑一致，跟隨誤差在0.2 m以內，誤差較小；車輛保持穩定行駛時的最大側向加速度由地面附著力決定，通常為0.8g.由圖10（c）可知，跟隨時的側向加速度在0.4g以內，說明整個過程中都能夠保證主車按照路徑行駛時的穩定性.彎道仿真結果如圖11所示，跟隨誤差都在0.1 m以內，跟隨效果好；側向加速度都在0.5g范圍內，滿足穩定性要求.
5 結 論
本文在將RRT算法應用到汽車避障局部路徑規劃時，針對原算法在隨機性以及路徑曲率變化上的不足，建立了直道和彎道的期望路徑模型，使隨機采樣點在期望路徑模型周圍近似呈高斯分布，采用啟發式搜索方式使采樣點和隨機樹節點向目標點靠近，從而降低算法的隨機性；并且在路徑規劃時加入約束，使得所規劃出的路徑更為合理.仿真實驗結果表明：改進RRT算法不僅規劃出的路徑質量高、實時好、跟隨性強，而且車輛的穩定性也滿足要求.因此，改進RRT算法可以應用于實時汽車路徑規劃.
參考文獻
[1] YAO J， LIN C， XIE X， et al. Path planning for virtual human motion using improved A* algorithm[C]//Proceedings of the Conference on Information Technology： New Generations （ITNG）.Washington， DC： IEEE Computer Society， 2010： 1154-1158.
[2] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik， 1959， 1（1）： 269-271.
[3] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research， 1986， 5（1）： 90-98.
[4] SONG X， CAO H， HUANG J. Vehicle path planning in various driving situations based on the elastic band theory for highway collision avoidance[J]. Proceedings of the Institution of Mechanical Engineers， Part D： Journal of Automobile Engineering， 2013， 227（12）： 1706-1722.
[5] SONG X， CAO H， HUANG J. Influencing factors research on vehicle path planning based on elastic bands for collision avoidance[J]. SAE International Journal of Passenger Cars-Electronic and Electrical Systems， 2012， 5（2）：625-637.
[6] 肖浩， 宋曉琳， 曹昊天. 基于危險斥力場的自動駕駛汽車主動避撞局部路徑規劃[J]. 工程設計學報， 2012，19（5）： 379-384.
XIAO Hao， SONG Xiaolin， CAO Haotian.Local path planning for autonomous vehicle collison avoidance based on dangerous repellant fields[J]. Chinese Journal of Engineering Design，2012， 19（5）： 379-384.（In Chinese）
[7] 康冰， 王曦輝， 劉富. 基于改進蟻群算法的搜索機器人路徑規劃[J]. 吉林大學學報：工學版， 2014， 44（4）：1062-1068.
KANG Bing， WANG Xihui， LIU Fu. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University：Engineering and Technology Edition， 2014， 44（4）： 1062-1068.（In Chinese）
[8] HU Y， YANG S X. A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of the Conference on Robotics and Automation. Washington，DC： IEEE Computer Society， 2004： 4350-4355.
[9] 吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J].湖南大學學報：自然科學，2013，40（1）：33-37.
WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University： Natural Sciences， 2013，40（1）：33-37.（In Chinese）
[10]SHAH-HOSSEINI H. Problem solving by intelligent water drops[C]// Proceedings of the Conference on Evolutionary Computation.Washington，DC： IEEE Computer Society， 2007： 3226-3231.
[11]LAVALLE S M.Rapidly-exploring random trees： A new tool for path planning[J]. Algorithmic & Computational Robotics New Directions， 1998：293-308.
[12]LAVALLE S M， KUFFNER J J. Rapidly-exploring random trees： progress and prospects[J]. Algorithmic & Computational Robotics New Directions， 2000：293-308.
[13]KUFFNER J J， LAVALLE S M. RRT-connect： An efficient approach to single-query path planning[C]// Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2003：995-1001.
[14]FERGUSON D， KALRA N， STENTZ A. Replanning with rrts [C]//Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2006： 1243-1248.
[15]ZUCKER M， KUFFNER J， BRANICKY M. Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2007： 1603-1609.
關鍵字：最優路徑選擇；A-Star算法；貪婪算法；模擬仿真
中圖分類號：TP301.6 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2013.06.012
0 前言
物流與國民經濟及生活的諸多領域密切相關，越來越多得到重視，甚至被看作是企業“第三利潤的源泉”，而在物流成本方面，運輸費用占大約50% ，比重最大[1]。因此，物流配送中最優路徑選擇的研究具有巨大的經濟意義。物流配送中的最優路徑選擇問題的研究和應用都相當廣泛，近幾十年，國內外均有大量企業機構、學者對該問題進行了大量而深入的研究，取得豐碩的學術成果。如1953年，Bodin，Golden 等人便撰文綜述了該問題的有關研究進展情況，列舉了幾百余篇相關文獻，這些文獻成為了早期車輛路徑問題研究資料，隨后隨著該問題不斷研究深入，約束模型及條件不斷變化，車輛路徑問題研究的最新進展可見Alt- inkerner 和 Oavish，Laporte，Salhi 等人的綜述性文章[2]。圍繞該問題的解決也極大推動了計算機學科的發展，不斷有新的模型和算法推出。針對物流配送車輛路徑優化問題的求解方法很多，根據算法原理的不同大致可分為兩大類：精確算法和智能式啟發算法。精確算法是指可以車輛路徑問題的數學模型可求出其最優解算法，但由于算法存在諸多缺陷，所以在實際中應用并不廣泛。目前，啟發式算法是解決物流配送中最優路徑選擇的主要方法和主向[3]。近年來，隨著科學的發展，一些新的啟發式方法被用在求解物流路徑選擇及優化問題上，可以通過使用啟發式方法獲得較快的收斂速度和較高質量的全局解，常用的算法有模擬退火算法、GA 算法等[4]。A*算法是人工智能中一種典型的啟發式搜索算法，被廣泛應用于最優路徑求解和一些策略設計的問題中[5、6]。本文結合貪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平臺上，采用Visual C++編程對物流配送問題進行模擬仿真，同時考慮最短時間和最短路徑兩個方面，以此來解決物流配送中最優路徑選擇的問題，達到物流配送最優線路規劃的目的。
1 需求分析
1.1 總體框架
在物流配送時，物流車裝載當日需要配送的貨品從倉庫出發，按照事先規劃好的最優配送路徑為每一個客戶進行配送，最后返回倉庫。這就涉及在配送時配送路線的選擇問題，而在配送之前，IT系統需要根據客戶的配送地址間線路間距和經驗路況分析計算出一條最優配送路徑。并且在配送過程中，如果某路段發生堵車狀況，需要動態調整配送路線，以達到最優配送的目的。為此，在QT Creator平臺上，以面向對象的設計方式來開發最優物流配送的功能軟件。通過再現交通運輸環境，模擬物流運輸中的突發事件，優化物流配送的路線，分別根據需求，設計出最短路徑和最少時間兩種配送方式，并通過二維動畫的效果顯示出來。通過此軟件呆模擬解決物流配送中各種情況，從而降低運輸成本。設計本軟件的總體思路如圖1所示。
1.2 功能設計
設計的軟件從功能上來說，主要包括以下幾點：
（1）載入一張已有地圖（*.map的文件）或生成一張空白地圖。用戶可以在這張空白地圖上操作，通過障礙物的增刪來設置城市的道路。
（2）道路突發事件設置。
a.用戶可以根據實際情況或主觀意愿對地圖進行規劃。在地圖中添加障礙物，設置道路前方的暫時封閉或者道路施工等未知路況。
b.也可以模擬城市人流量大的地方，通過在地圖上，設置易堵車而導致前行速度下降的未知路況。
（3）設置倉庫及客戶點。
a.隨機生成倉庫及客戶點。在地圖中，用戶可隨機生成若干個客戶點和倉庫點。
b.指定生成倉庫及客戶點。在已生成或者模擬的地圖上，根據用戶的不同需求，可在地圖上任意位置生成客戶點和倉庫點。
c.可以對倉庫及客戶點進行增刪。
（4）計算路徑及優化。
a.根據用戶之前模擬的各種情況，計算其最短路徑。根據用戶載入或者自己規劃的地圖，模擬計算出最短路徑，在界面的左上角顯示其時間，并在地圖上顯示其路徑。
b.根據用戶之前模擬的各種情況，計算其最短時間。根據用戶載入或者自己規劃的地圖，模擬計算出最短時間，在界面的左上角顯示其時間，并在地圖上顯示其對應路徑。
軟件的大致功能如下圖2所示。
圖2 功能模塊圖
2 算法描述
2.1 貪婪算法
貪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到達山頂，即逐步獲得最優解，是解決最優化問題時的一種簡單但適用范圍有限的策略[7]。
貪婪算法是基于鄰域的搜索技術，它在計算過程中逐步構造最優解[8]。在構造解的過程中，每一步常以當前情況為基礎根據某個優化測度（greedy criterion，貪婪準則，也稱貪婪因子）作最優選擇，而不考慮各種可能的整體情況，選擇一旦做出就不再更改，這省去了為找最優解要窮盡所有可能而必須耗費的大量時間。它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，一般情況下只是近似最優解[9]。雖然貪婪法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的求最優解問題來說，它是一種最直接的算法設計技術，通過一系列局部最優的選擇，即貪婪選擇可以產生整體最優解[10]。
對于一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解并不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。一般情況下，要選出最優量度標準并不是一件容易的事，但對某問題能選擇出最優量度標準后，用貪婪算法求解則特別有效。最優解可以通過一系列局部最優的選擇（貪婪選擇）來達到。根據當前狀態做出在當前看來是最好的選擇，即局部最優解選擇，然后再去解出這個選擇后產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題，最終可得到問題的一個整體最優解。它是一種改進了的分級處理方法。
2.2 A-Star算法
A*算法是人工智能中一種典型的啟發式搜索算法，它是一種靜態路網中求解最短路最優算法，其公式可表示為：
（1）
其中，是從初始點經由節點到目標點的估價函數；是在狀態空間中從初始節點到節點的實際代價；是從到目標節點最佳路徑的估計代價[11、12]。
在A*算法中，找到最短路徑（最優解的）的關鍵在于估價函數的選取。當估價值到目標節點的距離實際值時，搜索的點數多，搜索范圍大，效率低，但能得到最優解；當估價值到目標節點的距離實際值時，搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解[13、14]。
A*算法的難點在于建立一個合適的估價函數，估價函數構造得越準確，則A*算法搜索的時間就越短[15]。A*算法的估價函數可表示為：
（2）
這里，是估價函數，是起點到節點的最短路徑值，是到目標的最短路徑的啟發值。由于這個其實是無法預先知道的，所以我們用前面的估價函數做近似。當時，可以代替（大多數情況下都是滿足的，可以不用考慮），但只有在時，才能代替。可以證明，應用這樣的估價函數能有效地找到最短路徑。
本文綜合貪婪算法和A*算法的思想來求解決物流配送中最優路徑選擇的問題。圖3為綜合算法的流程圖。
3 實驗仿真設計
3.1 軟件概述
開發的軟件要具有實用性，這就是說，能給企業帶來效益，這就包了兩方面的內容：企業能獲得的利潤和客戶的滿意程度。也就是說采用所建立的模型要設計出合理的物流配送路線，保證在較短的路程或時間內遍歷所有的節點，從而保證貨物按時送到。
從算法角度來看，為了保證算法的有效性和高效性，結合軟件的功能，則該軟件的設計目標[16]為：①路徑最短或時間最短， ②滿足實際中遍歷節點的要求， ③算法高效性， ④軟件的普度適用性。
軟件操作流程具體步驟如下：
第一步.用戶載入一張已有地圖或生成一張空白地圖。
第二步.設置相關參數及約束條件。
第三步.顯示計算結果和最優路徑。
該軟件可運行于Windows 7操作系統，主要包括3個部分：地圖文件的讀取部分、算法部分和用戶界面部分。
3.2 軟件模擬實現
1.初始化
根據軟件的需求分析，本軟件初始產生一個空白的二維平面圖，在該模塊用戶可以根據實際情況模擬出實際路況，提供兩種方式來實現該功能：
（1）通過點擊工具欄上面的初始化按鈕自動初始化。
（2）通過鼠標右鍵選擇初始化選項。
圖4 系統初始化界面
2.道路的參數設置
在視圖界面中，用戶可以點擊鼠標右鍵，選擇生成障礙物或刪除障礙物來模擬現實生活中城市道路可能發生的各種情況，如：
（1）用戶可以根據實際情況，點擊鼠標右鍵，在出現的下拉菜單中，選中添加障礙物，設置道路前方的暫時封閉或者道路施工等未知路況。
（2）也可以在地圖上，點擊鼠標右鍵來設置易堵車而導致前行速度下降的未知路況。
在地圖中淺黃色的區域是模擬人流量大的鬧市區。深褐色方塊模擬障礙物。
圖5 道路模擬圖
3.倉庫點及客戶點的生成
客戶點和倉庫點的生成包括兩種情況：
（1）隨機生成客戶點和倉庫點。在視圖界面中，通過頂端的輸入框，輸入生成客戶點或倉庫點的個數，點擊生成客戶點或倉庫點按鈕來隨機生成客戶點或倉庫點。
（2）在指定位置生成客戶點和倉庫點。在已生成或者模擬的地圖上，根據用戶不同的需求，在地圖指定位置生成客戶點和倉庫點。
在如圖5的道路設計下，在地圖上隨機添加了10個客戶點和1個倉庫點，如圖6所示。
圖6 場景界面圖
4.路徑最短和時間最短的配送路徑
根據圖6所設計的場景，通過貪婪算法和A*算法，分別計算出路徑最短和時間最短的配送路徑，并在地圖上顯示其路徑。圖7依據最短路徑實現物流配送的最優方案，主要從距離這個方面進行考慮；圖8根據最短時間實現物流配送的最優方案，主要考慮的是在道路有突發狀況發生時物流配送的時間最少。
圖7 路徑最短的配送路徑
圖8 時間最短的配送路徑
4 認識與結論
通過對物流配送中的實際問題進行模擬研究，在QT Creator平臺上采用Visual C++編程開發出針對物流配送中最優路徑選擇問題的軟件，從最短時間和最短路程兩方面考慮，為物流配送公司提供可靠有效的參考信息，使配送方案符合實際情況。同時，深入研究了貪婪算法和A*算法，從算法的角度對物流配送中的時間和路程進行分析，設計實現了物流配送中最優數學模型，以期達到最優路徑的目的。通過本研究的結果來看，開發的模擬軟件能解決物流運送過程中的時間、路徑等實際問題，同時實現了二維圖形的可視化，更加直觀地體現了物流配送中存在的問題和解決方式，對物流配送企業提高運營效率、降低運營成本等具有重要意義。
參考文獻
[1]黃中鼎. 現代物流管理學[M]. 上海： 上海財經大學出版社， 2004， 1-37.
[2]謝秉磊， 郭耀煌， 郭強. 動態車輛路徑問題：現狀與展望[J]. 系統工程理論方法應用， 2002， 11（2）： 116-120.
[3]鄒挺. 基于蟻群和人工魚群混合群智能算法在物流配送路徑優化問題中的應用研究[D]. 蘇州： 蘇州大學， 2011， 3-7.
[4]吳云志， 樂毅， 王超， 等. 蟻群算法在物流路徑優化中的應用及仿真[J]. 合肥工業大學學報（ 自然科學版）， 2009， 32（2）：211-214.
[5]王海梅， 周獻中. 直線優化A*算法在最短路徑問題中的高效實現[A]. 全國第計算機技術與應用（CACIS）學術會議論文集（下冊）[C]， 2008， 932-936.
[6]陳和平， 張前哨. A*算法在游戲地圖尋徑中的應用與實現[J]. 計算機應用與軟件， 2005， 22（12）：94-96.
[7]晏杰. Matlab 中貪婪算法求解背包問題的研究與應用[J]. 赤峰學院學報（自然科學版）， 2012， 28（9）：23-24.
[8]劉紀岸， 周康渠， 寧李俊， 等. 基于貪婪算法的摩托車生產物流配送規則優化[J]. 制造業自動化， 2010， 32（5）：97-99.
[9]蔣建國， 李勇， 夏娜. 一種求解單任務Agent聯盟生成的貪婪算法[J]. 系統仿真學報， 2008， 20（8）：1961-1964.
[10]江朝勇， 陳子慶， 謝贊福. 基于優先級貪婪算法的排課系統排研究與實現[J]. 信息技術， 2008， 24（7）：173-176.
[11]徐偉， 孫士兵. 基于A-Star算法警用地圖查詢系統的設計與實現[J]. 信息安全與技術， 2011. 5-2：52-56.
[12]王敬東， 李佳. A*算法在地圖尋徑中的實用性優化[J]. 電腦開發與應用， 2007， 20（7）：24-25.
[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一種現代方法[M]. 姜哲，譯. 北京：人民郵電出版社， 2004， 76-83.
[14]王文杰， 葉世偉. 人工智能原理與應用[M]. 北京：人民郵電出版社， 2004， 115-121.
關鍵詞： B樣條曲線； 無人車； 路徑規劃； 碰撞檢測； 最大曲率約束； 最優路徑
中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2016）26-0235-03
B-spline Curve based Trajectory Planning for Autonomous Vehicles
QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong
（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）
Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.
Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature
1 引言
近年來，無人駕駛技術備受關注，各大研究機構和企業爭相推出各自的無人駕駛平臺。無人車作為未來智能交通的主要主體也逐漸融入到我們的日常生活中，比如自主巡航[1]和自動泊車等等。然而，為了使其更好地服務于我們，需要進一步提高其智能化水平，而路徑規劃作為連接環境感知和運動規劃的橋梁，是無人車智能化水平的重要體現[2]。
由于受到自身動力學和運動學模型的約束，車輛的路徑規劃問題除過要嚴格滿足端點狀態約束之外，還要求其中間狀態滿足運動系統的微分約束。由于實現簡單，并且高階多項式曲線能夠很好地滿足運動系統的微分約束，生成高階平滑的路徑，所以很多路徑規劃系統選擇使用基于多項式曲線的方法生成路徑。B樣條曲線是一種典型的多項式曲線，且因為其所有的中間狀態均是由控制點加權生成，所以其能夠完全滿足端點狀態約束。綜合考慮無人車路徑規劃的要求和實現復雜度，在僅已知初始位姿和目標位姿的情況下，本文選擇B樣條曲線生成路徑，重點講述分步規劃模型，即路徑簇生成、最大曲率約束、碰撞檢測以及最優評價四個過程，并通過Matlab仿真對本文方法進行了驗證。
2 問題描述
本節分別描述了無人車路徑規劃問題和B樣條曲線。
2.1 路徑規劃問題描述
路徑規劃得到的是一條從初始位置到目標位置的路徑，即二維平面內一條從初始位置點到目標位置點的曲線，曲線上的每一個點表示車在行駛過程中的一個狀態?？紤]到實現方便，本文將路徑描述成離散點序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點[Si（xi，yi，θi）]表示車的一個狀態，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態和目標狀態。圖1中的圓[（xobs1，yobs1，robs1）]表示環境中的障礙物，[（xobs1，yobs1）]表示障礙物的位置信息，[robs1]表示障礙物的半徑。
2.2 B樣條曲線
如果給定[m+n+1]個控制點[Pi（i=0，1，???，m+n）]，就可以構造[m+1]段[n]次B樣條曲線，其可以表示為公式1：
[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）
其中，[Pi，n（t）]表示第[i]個[n]次B樣條曲線片段，[n]表示B樣條曲線的次數，[t]為控制參數，其取值范圍為[[0，1]]，[Pi+k]為控制點，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。
3 本文算法
本節重點講述基于B樣條曲線的路徑規劃方法和基于該方法生成路徑的過程。
3.1 基于B樣條曲線的路徑規劃方法
選擇三階B樣條曲線生成幾何路徑，即每四個控制點生成一個路徑片段，然后通過片段的拼接就可以實現從初始狀態到目標狀態的路徑規劃，下面著重講述基于六控制點的三階B樣條曲線生成滿足車輛端點位姿約束路徑的方法，如圖2所示。
l 依據初始狀態選擇控制點[P0，P1，P2]。當[P0，P1，P2]三個控制點共線，并且[P1]為線段[P0P2]的中點時，生成的B樣條曲線與線段[P0P2]相切于點[P1]。所以選擇無人車的初始位置為控制點[P1]，將控制點[P0]和[P2]選在初始航向角[θstart]所在直線上，并關于控制點[P1]對稱。如是，即能滿足車輛的初始位姿約束；
l 依據目標狀態選擇控制點[P3，P4，P5]。當[P3，P4，P5]三個控制點共線，并且[P4]為線段[P3P5]的中點時，生成的B樣條曲線與線段[P3P5]相切與點[P4]。所以選擇無人車的目標位置為控制點[P3]，將控制點[P3]和[P5]選在目標航向角[θgoal]所在的直線上，并關于控制點[P3]對稱。如是，即能滿足車輛的目標位姿約束。
（a） 路徑簇
（b） 最大曲率約束
（c） 碰撞檢測
3.2 分步路徑規劃
本小節將以圖3所給定的場景為例，講述最優路徑生成的過程。
3.2.1 路徑簇生成
在選定控制點[P1]和[P4]之后，通過選擇不同的控制點[P2]和[P3]，從而得到多組控制點，進而得到多條路徑。將控制點選擇的極限定為線段[P1P2]、[P3P4]與[P1P4]相等，但是[P1P2]和[P3P4]不能出現交叉。將這個范圍等間隔量化，各取四個點，共組成16組控制點，得到16條路徑，如圖3（a）中的藍色曲線所示。
3.2.3 最大曲率約束
理論上，車輛的最小轉彎半徑[Rmin=Lsin（θmax）]是其本身屬性[3]，只取決于車輛的軸距[L]和最大前輪轉角[θmax]。那么，車輛可行駛路徑的最大曲率[κmax=1Rmin]也是固定的，假設無人車可行駛路徑的最大曲率[κmax=16]，以此為約束條件，在路徑簇中選擇滿足最大曲率約束的路徑，如圖3（b）所示，圖中綠色曲線表示不滿足最大曲率約束的路徑。
3.2.4 碰撞檢測
碰撞檢測的目的是保證車輛在規劃路徑上行駛而不與障礙物發生碰撞。采取的碰撞檢測的方法很簡單，因為環境中的障礙物采用圓來描述，所以只要判斷路徑上每一點到圓心的距離與障礙物半徑的關系，就能確定其是否發生碰撞。由兩點間距離公式：
[d=（x1-x2）2+（y1-y2）2] （2）
如果[d]大于障礙物半徑，則不發生碰撞；如果[d]小于障礙物半徑，則發生碰撞。圖3（c）中的藍色曲線表示既滿足最大曲率約束，又不與障礙物碰撞的路徑。
3.2.2 最優路徑
路徑要求的側重點不同，優化的目標函數也可以有多種選擇，常用的目標函數有最短和最平滑等。其中，路徑最短可以抽象成優化問題：
[traoptimal=arg mintraids] （3）
路徑最平滑可以抽象成優化問題：
[traoptimal=arg mintraiκ2] （4）
式中，[traoptimal]為最優路徑，[traids]為第[i]條路徑的長度，[traiκ2]為第[i]條路徑上所有點處的曲率平方之和。圖3（d）中的紅色曲線即為得到的最短可行駛路徑。
如是，就能得到滿足車輛運動學約束，并且無碰撞的最優路徑。
4 結論
本文選擇使用B樣條曲線解決無人車路徑規劃問題，并建立了基于B樣條曲線的分步規劃模型。仿真結果表明，使用基于B樣條曲線的路徑規劃方法能夠很好地解決簡單障礙物場景中無人車的路徑規劃問題，并且因為路徑生成過程簡單，所以該方法常常表現得十分高效，能夠完全滿足無人車路徑規劃系統對算法實時性的要求。
參考文獻：
[1] Vahidi A， Eskandarian A. Research advances in intelligent collision avoidance and adaptive cruise control [J]. IEEE Transactions on Intelligent Transportation Systems， 2003， 4（3）：143-153.
關鍵詞： 最短路徑； A*算法； Dijkstra算法； 路徑優化
中圖分類號： TN911.1?34； TP312 文獻標識碼： A 文章編號： 1004?373X（2017）13?0181?03
Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.
Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization
最短路轎侍[1]是圖論中網絡分析的經典問題，近年來，隨著路徑搜索技術的不斷發展，已經涌現出很多成熟的路徑規劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關于人工智能領域的啟發式搜索算法和動態規劃算法等。A*啟發式搜索算法作為人工智能領域的重要組成部分，其針對網格數據有著更高的運算效率，而且利用啟發信息大幅度提高了搜索速度。這種全新的啟發式搜索算法[4]將會極大地改變現有的交通管理與服務模式。
1 A*算法原理
傳統的BFS算法的評估函數只考慮當前點與終點的距離，其策略是選擇與終點最近的點進行搜索。而Dijkstra算法則只關注當前點與起點的距離，選擇與起點最近的點開始搜索。A*算法[5]則是將二者結合起來，其啟發函數采用如下的計算公式：
式中：就是A*算法[5]對每個節點的評估函數[2]，其包含兩部分信息：是從起點到當前節點的實際代價，也就是從起點到當前節點的移動距離；相鄰的兩個點的移動距離是1，當前點距離起點越遠，這個值就越大。是從當前節點到終點的距離評估值，這是一個從當前節點到終點的移動距離的估計值。
A*算法的搜索過程需要兩個表：一個是OPEN表，存放當前已經被發現但是還沒有搜索過的節點；另一個是CLOSE表，存放已經搜索過的節點，具體的算法流程圖如圖1所示。
1.1 常用的距離評估函數
是A*算法的距離估計值[6]，A*算法需要一個距離評估函數來計算這個值。常用的距離評估函數有曼哈頓距離、歐式幾何平面距離和切比雪夫距離。在沒有障礙物的地圖上，這三種距離評估函數得到的效果是一樣的，但是在有障礙物的情況下，這三種距離評估函數的效果略有差異。當距離評估函數總是0時，A*算法就退化為Dijkstra算法[6]的效果。
1.1.1 曼哈頓距離
從數學上描述，曼哈頓距離是兩個點在各個坐標軸上的距離差值的總和，維幾何空間中曼哈頓距離的數學描述為：
對于二維平面上的兩個點和，其曼哈頓距離為：
即歐式幾何平面距離為在直角坐標系中兩個坐標軸上的投影距離和。
1.1.2 歐式幾何平面距離
歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數學定義是維空間中兩個點之間的真實距離（幾何距離），其數學符號可以描述為：
對于二維平面上的兩個點和其歐式幾何平面距離為：
即平面幾何中兩點之間的幾何距離。
1.1.3 切比雪夫距離
切比雪夫距離（Chebyshev Distance）是由一致范數（或稱上確界范數）衍生的度量，從數學角度上理解，對于兩個向量和其切比雪夫距離就是向量中各個分量的差的絕對值中最大的那一個，用數學符號可以描述為：
特別情況下，對于平面上的兩個點和，其切比雪夫距離為：
距離評估函數與A*算法的結果之間存在很微妙的關系，如果令始終為0，相當于一點啟發信息都沒有，則A*算法[5]退化為Dijkstra算法，這種情況即為最差的A*算法。的值越小，啟發信息越少，搜索范圍越大，速度越慢，但是越有希望得到最短路徑；的值越大，啟發信息越多，搜索的范圍越大，但是其有可能得不到真正的最短路徑。當大到一定程度時，公式中的就可以忽略不計，則A*算法演化成為BFS（廣度優先搜索算法），速度最快，但是不一定能夠得到最短路徑。所以通過調整和函數，可以使得A*算法[6]在速度與準確性之間獲得一個折中的效果。
1.2 A*算法的實現
A*算法實現的關鍵在于維護OPEN表和CLOSE表，其中對于OPEN表的主要操作就是查詢最小的節點以及刪除節點，因此考慮在算法實現時將OPEN表[7]設計為有序表。這樣在OPEN列表存儲數據時就可以自動將數據按照距離進行排序，這樣算法的執行效率比較高。A*算法的參數設置見表1，參數的迭代次數見圖2。
通過仿真實驗分析可以得出，A*算法[5]在有障礙物的情況下中和了BFS算法和Dijkstra算法的優點，能夠更有效地找到最終的最短路徑。
2 A*算法與Dijkstra算法效率的比較
Dijkstra算法是典型的單源最短路徑算法，其適用于求解沒有負權邊的帶權有向圖的單源最短路徑問題。由于Dijkstra算法[2?3]使用了廣度優先搜索的策略，它可以一次得到所有點的最短路徑。但是，它只是簡單地做廣度優先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗費很多時間和空間。考慮到實際地圖上面兩點之間存在位置和距離等信息，A*算法既能夠像Dijkstra算法那樣搜索到最短路徑，又能像BFS（廣度優先搜索算法）一樣使用啟發式函數進行啟發式搜索，是目前各種尋徑算法中最受歡迎的選擇。
將A*算法同Dijkstra算法[6]進行仿真比較，用于比較性能的主要指標有：時間復雜度分析；搜索到最短路徑的成功率分析。利用C++語言編制了三種算法的最短路徑搜索程序，運行在本地計算機上，并得出仿真模擬圖。
搜索效率的對比結果如表2所示。
由表2可以看出：當地圖節點的個數和弧的條數比較多時，A*算法[5]的搜索效率比Dijkstra算法快很多，當節點數不斷增多時，其搜索最短路徑的效率更高。在相同路網和位置信息的條件下進行仿真實驗的結果如圖3所示。
由圖3可以看出，兩種算法在相同障礙物條件下進行模擬仿真時，A*算法的搜索效率和時間復雜度要明顯優于Dijkstra算法，并對不同實驗場景下的效率進行對比，結果如圖4所示。
3 結 語
從Dijkstra算法和A*算法[2]的實現可知，Dijkstra算法的時間復雜度是其中是有向圖中頂點的個數。對于不含負權邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優先搜索算法的特點，在速度和準確性之間有很大的靈活性。除了調整和可以獲得不同的效果外，A*算法還有很多可以提高效率的改進方法。比如，在地圖比較大的情況下使用二叉堆來維護OPEN表以獲得更好的運算效率。
參考文獻
[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.
[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. /data.
[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.
[4] 周郭許，唐西林.基于柵格模型的機器人路徑規劃快速算法[J].計算機工程與應用，2006，42（21）：197?199.
[5] 李大生，劉欣，吳明華，等.基于動力學約束的機器人無碰運動規劃[J].機器人，1990（5）：14?19.
[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.
[7] 李得偉，韓寶明，韓宇.一種逆向改進型A*路徑搜索算法[J].系統仿真學報，2007，19（22）：5175?5177.
[8] 林丹.一種室內清潔機器人返回路徑規劃算法[J].重慶科技學院學報（自然科學版），2009，12（1）：110?113.
[9] 趙真明，孟正大.基于加權A～*算法的服務型機器人路徑規劃[J].華中科技大學學報（自然科學版），2008（z1）：196?198.
