引言：易發(fā)表網(wǎng)憑借豐富的文秘實踐，為您精心挑選了九篇路徑規(guī)劃典型算法范例。如需獲取更多原創(chuàng)內(nèi)容，可隨時聯(lián)系我們的客服老師。

第1篇

作者簡介： 朱新平（1983-），男，博士，研究方向為先進機場場面運行控制，電話：13419037831，E-mail：

通訊作者： 韓松臣（1963-），男，教授，博士，研究方向為空中交通安全、空域規(guī)劃管理，E-mail：

文章編號： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027

摘要：

為支持先進機場場面活動引導與控制系統(tǒng)（A-SMGCS，advanced surface movement guidance and control system）實施航空器滑行的精確引導，將場面分為滑行道交叉口和直線段等典型運行單元，利用改進的擴展賦時庫所Petri網(wǎng)，建立了場面運行模塊化模型；采用該模型進行染色體編碼，并考慮場面運行管制規(guī)則，提出了染色體合法性檢測與修復算法，以及染色體交叉和變異算法.基于首都國際機場01號跑道實際運行數(shù)據(jù)，用本文模型和算法進行了多個航班滑行初始路徑規(guī)劃，研究結果表明：與節(jié)點-路段類模型相比，本文模型能更充分地描述場面管制規(guī)則約束，可避免生成違反管制規(guī)則的路徑；本文算法的每個航班初始路徑規(guī)劃耗時小于10 s，符合A-SMGCS的要求；由于考慮了航空器滑行速度調(diào)整特征，更符合場面運行的實際情況.

關鍵詞：

空中交通；A-SMGCS；滑行路由規(guī)劃； Petri網(wǎng)；遺傳算法

中圖分類號： V351.11文獻標志碼： A

航空器滑行自動路由規(guī)劃可以協(xié)調(diào)進離港航班安全有序地滑行，從而減少場面擁堵并提升場面容量.在國際民航組織（International Civil Aviation Organization， ICAO）提出的先進機場場面引導與控制系統(tǒng)（advanced surface movement guidance and control system， A-SMGCS）中，路由規(guī)劃功能是實現(xiàn)航空器場面滑行精確引導的前提[1].航空器場面滑行具有并發(fā)、資源共享特性，并受多種管制規(guī)則約束. A-SMGCS路由規(guī)劃不同于傳統(tǒng)道路網(wǎng)絡中的車輛路徑規(guī)劃，文獻[2]提出了A-SMGCS三階段路由規(guī)劃策略：

（1） 初始路徑規(guī)劃，為進離港航班確定最優(yōu)滑行路徑和s-1個次優(yōu)滑行路徑（s值由管制員動態(tài)交互確定）；

（2） 滑行前路由指派，依據(jù)航空器開始滑行前的場面態(tài)勢，為其確定合理路由；

（3） 路由實時更新，在航空器滑行過程中實時調(diào)整路由，以避免沖突發(fā)生.

本文僅考慮第（1）階段，即初始路徑規(guī)劃問題.

Petri網(wǎng)廣泛用于A-SMGCS場面運行過程的建模與沖突監(jiān)控[3-4]，但較少用于航空器滑行路由規(guī)劃.文獻[5]將無向交通網(wǎng)絡轉(zhuǎn)換為Petri網(wǎng)表示的有向圖，并通過Petri網(wǎng)仿真器求解最短有向路徑.文獻[6]將機場滑行路徑描述為有向圖，并轉(zhuǎn)換為Petri網(wǎng)圖求解最佳滑行路徑.文獻[2]建立了基于Petri網(wǎng)的場面活動模型，并通過時間窗調(diào)度來進行路由規(guī)劃.上述研究建立的Petri網(wǎng)模型對場面管制規(guī)則約束考慮不全面，在算法設計上未充分利用Petri網(wǎng)的數(shù)學特征，且通常針對某一特定機場進行分析，實用性和通用性均顯不足.另一方面，將航空器場面滑行速度假設為恒定值[7-9]，忽略了航空器在場面不同區(qū)域滑行速度的調(diào)整變化，導致所得路由結果不能支持航空器滑行的精確引導.

在文獻[2]的基礎上，本文從以下方面展開研究：

（1） 給出一種擴展賦時庫所Petri網(wǎng)（extended timed place Petri net， ETPPN），以準確描述場面運行管制規(guī)則約束，并提出一種模塊化、面向路由規(guī)劃的場面運行ETPPN模型建模方法；

（2） 采用遺傳算法規(guī)劃航空器初始滑行路徑，其染色體編碼采用場面ETPPN模型的變遷激發(fā)序列，且交叉和變異均僅針對模型中的變遷進行，避免了以滑行道系統(tǒng)拓撲結構中的交叉口或直線段為基因組成染色體，在此基礎上展開的遺傳操作保證了方法的通用性；

（3） 與文獻[7-9]中關于航空器場面滑行速度恒定的假設不同，細化了航空器加減速特性對路段占用時間的影響，使路由規(guī)劃結果的精確度更高，實用性更強.

1

航空器場面運行過程建模

1.1

面向資源的場面運行過程建模

可見，采用ETPPN模型對場面運行進行建模，可描述航空器對場面各單元的動態(tài)占用與釋放，以及航空器在各單元滑行應遵循的管制規(guī)則.場面其它典型單元運行過程的Petri網(wǎng)建模也可采用本節(jié)的方法.不同機場的場面交通系統(tǒng)具有不同構型，但基本組成單元類似且有準確的數(shù)量和明確的運行規(guī)則.因此，利用各單元對應的ETPPN模型，并采用Petri網(wǎng)同步合成技術[10]可實現(xiàn)場面運行過程建模.

1.2

航空器滑行特征分析

航空器場面滑行速度具有以下特征：

（1） 當航空器先后通過的兩路段均為直線或彎道時，無須加減速；

（2） 當航空器從彎道滑入直線段時，須啟動加速過程；

（3） 當航空器從直線段滑入彎道時，減速過程通常在進入彎道前完成.

2

基于GA的初始路徑規(guī)劃算法

2.1

面向初始路徑規(guī)劃的GA設計

遺傳算法（genetic algorithm， GA）在工程優(yōu)化領域已得到廣泛應用[11]，并越來越多地應用于航空器路由優(yōu)化[12-15].本文提出基于場面ETPPN模型和GA的初始路徑規(guī)劃方法，基本思路為：

（1）

采用第1節(jié)方法，建立場面活動區(qū)中各典型運行單元對應的ETPPN模型，同時將場面管制規(guī)則約束集成到Petri網(wǎng)元素中，最終得到場面ETPPN模型；

（2）

以場面ETPPN模型為基礎，采用合適的編碼方式對模型中所含相關元素進行染色體編碼，并設計相關遺傳操作，求解初始滑行路徑集合（包括1個最優(yōu)和s-1個次優(yōu)滑行路徑）.

上述思路的優(yōu)勢在于，對任何一個機場的航空器初始路徑規(guī)劃，所要解決的問題只需采用第1節(jié)的模塊化建模方法，將場面交通系統(tǒng)映射為對應的ETPPN模型并輸入管制規(guī)則約束即可，因而保證了所給算法的實用性和通用性.

2.2

染色體編碼

染色體應滿足以下約束：

（1） 物理約束.指與航空器自身占用物理空間大小或與滑行性能相關的約束，如翼展對通過某些區(qū)域的限制等.

（2） 管制規(guī)則約束.指管制規(guī)則確定的航空器在某些路段的滑行約束，如滑行速度約束、進出某機坪必經(jīng)的交叉口等.

算法2中，步驟1保證了染色體不會出現(xiàn)重復基因，即所規(guī)劃滑行路徑不會出現(xiàn)環(huán)路；步驟2保證了航空器在單元內(nèi)部的滑行過程滿足航空器性能要求，例如航空器在同一交叉口滑行時不能多次轉(zhuǎn)彎；步驟3～5保證了航班按照所規(guī)劃路徑滑行時能滿足相關約束.

2.3

選擇算子與遺傳算子

2.3.1選擇算子

2.3.2

交叉算子

2.3.3

變異算子

由于采用變遷激發(fā)序列進行染色體編碼，若采取隨機改變某一基因位變遷進行變異，則極有可能產(chǎn)生不滿足可激發(fā)約束的解.以往采取兩種方法解決該問題：第1種方法是隨機改變?nèi)旧w，當生成了不滿足約束的解時再進行改正；第2種方法是在進行變異時保證不產(chǎn)生不可行解[16].

3

仿真試驗

3.1

仿真試驗設計

以首都國際機場為研究對象，采集T3航站樓東側飛行區(qū)某日實際運行數(shù)據(jù)，為所有進離港航班規(guī)劃初始滑行路徑集.該部分飛行區(qū)的場面交通系統(tǒng)結構如圖6所示，采用北向運行模式（使用01號跑道），且假設所有離港航班均使用全跑道起飛，即從跑道等待區(qū)Q0處（圖中方框所示區(qū)域）進入跑道起飛，進港航班從快速脫離道Q5、Q6、Q7脫離的比例為0.1∶0.6∶0.3.作為對比，采用文獻[12]的方法為圖6所示飛行區(qū)建立對應的節(jié)點-路段類有向圖模型，并采用基于遺傳算法的路徑規(guī)劃方法為航班規(guī)劃滑行路徑.

文獻[12]采取的優(yōu)化目標是所有航班滑行的總里程最短，將其修改為與本文算法相同的優(yōu)化目標，即滑行時間較短的s條滑行路徑（設s=3）.對比的目的是：

（1） 檢驗用本文所建場面模型進行路徑規(guī)劃是否比節(jié)點-路段類模型能更好地遵循管制規(guī)則；

（2） 檢驗本文初始路徑規(guī)劃算法的效率和有效性.

計算環(huán)境CPU為Interl（R） Pentium Dual 2.2 GHz，內(nèi)存為4 GB.

具體實施過程為：在基于Anylogic的場面運行仿真平臺上建立對應的場面ETPPN模型，然后解析得到該模型對應的關聯(lián)矩陣并導入MATLAB2008a中，采用Sheffield大學的遺傳算法工具箱GATBX求解滑行路徑.在求解過程中，MATLAB可直接調(diào)用Anylogic存儲的相關庫所屬性數(shù)據(jù)庫，并采用遺傳算法工具箱GATBX進行求解.文獻[12]中算法的實現(xiàn)直接用MATLAB的遺傳算法工具箱GATBX完成.

3.2

仿真試驗結果及分析

為了給每個航班的進離港滑行規(guī)劃s

個滑行時間較短的初始滑行路徑，需要設置合理的遺傳算法參數(shù).但目前在遺傳算法參數(shù)設定方面缺乏通用理論，一般根據(jù)問題難易程度和染色體編碼形式，由經(jīng)驗和反復試湊來設定參數(shù)值.

用上述參數(shù)為離港航班SK996（所在機位511）規(guī)劃初始滑行路徑集（包含3條路徑）.由于遺傳算法具有一定的隨機性，可進行多次試驗，每次試驗得到的最短滑行時間均為246 s，因此認為對應的滑行路徑為最短滑行路徑.

圖8為在1次隨機試驗中不同遺傳代數(shù)所得路徑集的最短滑行時間和平均滑行時間變化曲線.由圖8可以看出，每次優(yōu)化均能獲得最短滑行路徑，且隨著進化代數(shù)的增加，平均滑行時間越來越接近最短滑行時間，表明算法收斂性良好.

最終為該航班確定的初始滑行路徑集如表3所示.對每條路徑進行分析可知，在優(yōu)化場面資源使用的同時，滿足了各類場面運行管制規(guī)則約束.

采用文獻[12]的遺傳算法為該航班規(guī)劃初始滑行路徑集，將求出的前3條較短滑行路徑參照圖6轉(zhuǎn)化為對應的節(jié)點形式，如表4所示.

由表4可見，路徑1和路徑2分別在滑行道K5和K4上未遵循該路段的運行方向約束，這與該算法設計僅考慮避免航空器之間的滑行沖突約束但未充分考慮其它約束有關.可見，在節(jié)點-路段類模型中，模型本身對管制規(guī)則約束的描述能力有限，僅在算法實現(xiàn)過程中考慮各類約束，可能影響路徑規(guī)劃結果的有效性.

此外，文獻[12]中設定的航空器具有單一固定滑行速度5 m/s，路徑3的滑行時間為467 s（表4），用本文方法路徑3的滑行時間為260 s（表3），二者相差較大.可見，考慮航空器滑行速度的調(diào)整特性，可更精確地計算航空器的滑行時間.

4

結束語

提出了一種面向A-SMGCS的航空器場面滑行初始路徑規(guī)劃方法，該方法具有以下特點：

（1） 定義一種擴展賦時庫所Petri網(wǎng)（ETPPN），可對航空器場面滑行過程進行建模，該模型充分體現(xiàn)了管制規(guī)則約束；

（2） 考慮航空器場面滑行速度調(diào)整特性，使規(guī)劃結果更接近實際運行需要；

（3） 采用場面運行ETPPN模型中的變遷激發(fā)序列進行GA染色體編碼，結合場面滑行特征給出交叉與變異設計，改變以往研究中對問題空間（場面拓撲結構）的直接處理，算法的通用性更好.

在求解初始滑行路徑時僅以滑行時間最短作為優(yōu)化目標，今后需要考慮更多的優(yōu)化目標，例如航空器加減速次數(shù)、轉(zhuǎn)彎次數(shù)等，并與其它路徑規(guī)劃方法進行比較.

參考文獻：

[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航空器動態(tài)滑行路徑規(guī)劃研究[J]. 系統(tǒng)工程與電子技術，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監(jiān)控理論的滑行道對頭沖突控制策略[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]黃圣國，孫同江，呂兵. 運輸網(wǎng)絡的最短有向路Petri網(wǎng)仿真算法[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網(wǎng)的機場場面路徑規(guī)劃探討[J]. 現(xiàn)代電子工程，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網(wǎng)的FMS建模方法[J]. 系統(tǒng)工程理論與實踐，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]劉長有，叢曉東. 基于遺傳算法的飛機滑行路徑優(yōu)化[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]劉兆明，葛宏偉，錢鋒. 基于遺傳算法的機場調(diào)度優(yōu)化算法[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.

第2篇

關鍵詞：路徑規(guī)劃；搜索區(qū)域；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 引言

路徑規(guī)劃是在車輛行駛前或行駛過程中尋找車輛從起始點到達目的地的最佳行車路線的過程[1], 它屬于智能交通

系統(tǒng)中的最短路徑問題的一個具體應用。

最短路徑規(guī)劃產(chǎn)生的路徑分為兩種：距離最短的路徑和時間最短路徑,其中前者相對比較易于實現(xiàn)，但是它容易忽略路徑的具體情況和行車實際環(huán)境以及人為因素。因為在實際車輛行駛中要求不但在此路徑上行車距離盡可能短，而且路徑的行車環(huán)境盡可能好，即盡量走道路較寬、路面質(zhì)量較好、紅綠燈較少、紅綠燈設置間隔較大、車流量較小的路徑，避免走行車環(huán)境太差的路徑。作者針對最短路徑規(guī)劃存在的不足之處 ,根據(jù)已有A*算法，給出了一種改進的最優(yōu)路徑規(guī)劃算法，此算法在根據(jù)道路的實際情況對路網(wǎng)進行分層的同時，根據(jù)實際路網(wǎng)的拓撲特性對搜索區(qū)域進行合理的限制。

2 A*算法

A*算法是人工智能中一種典型的啟發(fā)式搜索算法．也是路徑規(guī)劃算法中的常用算法，它通過選擇合適的估計函數(shù)，指導搜索朝著最有希望的方向前進．以期求得最優(yōu)解限制搜索區(qū)域的多層最優(yōu)路徑規(guī)劃算法，A*算法評價函數(shù)的定義為[2]：

f(n)=g(n)+h(n) （1）

f(n)是從初始點通過節(jié)點n 到達目標點的估價函數(shù)；

g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價；

h(n)是從節(jié)點n到目標節(jié)點最佳路徑的估計代價。它決定了搜索的效率和可采納性。對于幾何路網(wǎng)來說，可以取兩點間歐氏距離（直線距離）作為估價值，即

其中，(xd,yd)、(xn,yn)分別為節(jié)點n 和目標節(jié)點在數(shù)字地圖中的坐標。由于估價值h(n)≤n 到目標節(jié)點的距離實際值，算法具有可采納性，能得到最優(yōu)解。[3]

3 改進的A*算法球最短路徑

本文在三個方面對傳統(tǒng)的A*算法進行了更改：1)A*算法提到的權值會根據(jù)用戶的不同查詢條件來調(diào)用相對應的計算權值的公式；2) 添加了一個判斷過程。當查詢下一個臨近邊的時候首先查詢交通控制策略，判斷是否有管制信息并將相映的點從v中刪除；3) 減少路徑搜索的范圍，以出發(fā)點與目的地點連線的中間點為圓心，以兩點之間直線距離的二分之一再加上幾公里為半徑畫圓，在圓范圍內(nèi)的路徑參加搜索，在圓范圍之外的路徑不參加搜索。

具體實現(xiàn)如下：

創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點，設各個點的權值（也稱為費用值）為g。遍歷當前節(jié)點的各個節(jié)點，將n節(jié)點放入CLOSE中，取n節(jié)點的子節(jié)點X,計算X的估價值[4]。

1)初始的OPEN表僅包含原節(jié)點．其費用值g為0，令CLOSED為空表，設其他節(jié)點的費用為∞ 。

2)若OPEN表為空．則宣告失敗：否則，選取OPEN表中所有的節(jié)點移至CLOSED表，將此CLOSED表作為新的OPEN表。重復第二步，直到深度達到4。

3)對第二步在深度4時形成的OPEN表進行操作，若OPEN表為空．則宣告失敗：否則，選取OPEN表中具有最小權值的節(jié)點，并叫做最佳節(jié)點NEXT．把NEXT從OPEN表移至CLOSED表．判斷此NEXT是否是一目標節(jié)點。若NEXT為目標節(jié)點．轉(zhuǎn)步驟3，若NEXT不是目標節(jié)點。則根據(jù)地圖數(shù)據(jù)庫包含的聯(lián)接路段屬性擴展并生成NEXT的后繼節(jié)點。對于每一個后繼節(jié)點n，進行下列過程：

①計算節(jié)點n的費用：g(n)= NEXT費用+從NEXT到n的費用

②如果n與OPEN表上的任一節(jié)點相同．判斷n是否具有最小的g值。若是最低的g值，用n的費用代替OPEN表中相同的節(jié)點費用。且建立匹配節(jié)點的后向指針指向NEXT

③如果n在CLOSED表中與一節(jié)點相匹配。檢查節(jié)點n是否具有最小的g值，如果n具有最小的g值，則用節(jié)點n的費用代替匹配節(jié)點的費用。并把匹配節(jié)點的后向指針指向NEXT。并把該匹配節(jié)點移到OPEN表

④如果n不在OPEN表。也不在CLOSED表上，則把n的后向指針指向NEXT。井把n放入OPEN表中。計算節(jié)點n的估價函數(shù)：f(n)=g(n)+h(n)

例如圖1，為帶權的有向圖。

根據(jù)步驟三，針對圖1，算法的具體實現(xiàn)如圖2。

4)重復第三步：

若在深度為7的搜索中找到目標結點且僅有一條路徑，則該路徑為最終路徑，返回；

若在若在深度為7的搜索中找到目標結點并且有多條路徑則回朔，比較找到的路徑費用，取權值最小的作為最終路徑；

若在在深度為7的搜索中未找到任何目標點則跳轉(zhuǎn)到第五步。

5)從深度為7的搜索中的所有的NEXT節(jié)點回朔，即從NEXT的后向指針一直到原節(jié)點遍歷節(jié)點，最后報告若干條路徑，比較個路徑費用，取費用最小的前100條路徑繼續(xù)重復第三步、第四步。由于h函數(shù)在滿足h下限得條件下，愈趨近于h效率愈高，因此實際應用中，我們?nèi)〉氖枪?jié)點到目的點的直線距離保證滿足下限的情況下，盡可能的趨近h。

4 結語

實踐表明基于改進A*算法的限制搜索區(qū)域的路徑規(guī)劃方法不僅在進行路徑規(guī)劃時節(jié)省了時間，而且規(guī)劃后的路徑大部分道路位于高層路網(wǎng)上，路徑長度與最短路徑長度之比小于1.1,可以被人接受，是行車意義上的最優(yōu)路徑。

參考文獻：

[1] 付夢印.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學學報,2004(10).

[2] 趙亦林.車輛定位與導航系統(tǒng)[M].北京:電子工業(yè)出版社,1999:1-7.

[3] 王亞文.智能交通系統(tǒng)中路徑規(guī)劃算法研究與系統(tǒng)設計[D].陜西師范大學,2007.

第3篇

【關鍵詞】神經(jīng)動態(tài)規(guī)劃 最優(yōu)路徑 子問題 Matlab仿真

為了減輕交通壓力，人們越來越關心交通系統(tǒng)的智能化進程。智能交通系統(tǒng)主要的研究方向之一就是動態(tài)路徑誘導系統(tǒng)，它可根據(jù)外出的人們的需求，為駕駛員提供最新的路況信息和最佳路徑選擇，以此避免交通擁堵現(xiàn)象的發(fā)生，從而優(yōu)化交通狀況，最終使交通時時地保持一個合理的動態(tài)分配。目前，最優(yōu)路徑選擇的方法有很多，但是真正需要解決大型問題時，計算機需要搜索的選擇范圍太大，傳統(tǒng)的動態(tài)算法基本上無法處理。1995年，神經(jīng)動態(tài)規(guī)劃算法被提出，該算法把復雜的問題分成若干子問題，這些子問題被拆分后更容易解決，使計算過程大幅簡化，且更容易被計算機處理。采用這種方法，可準確、快速、實時、穩(wěn)定地選擇出最優(yōu)路徑，值得推廣。

1 神經(jīng)動態(tài)規(guī)劃概述與核心思想

在解決多階段決策問題時，動態(tài)規(guī)劃大致思想為：將非常繁瑣的原始問題分解為若干個階段，這些階段看似不相關，卻是相互聯(lián)系的子階段，在找到上一階段的解決方法以后才能處理下一個階段，依次求出每個階段的解，最后得到全局最佳的解。多階段決策問題具備很強的順序性，同時每個階段所使用的解決方法也是隨著階段的變化而變化，所以“動態(tài)”意義就得以體現(xiàn)。其中交通網(wǎng)中最佳路徑的求解就是典型的多階段決策問題。

在路徑優(yōu)化中，動態(tài)規(guī)劃是一種非常經(jīng)典的計算方法，但在處理實際問題的時，我們肯定會遇到缺少一個完整信息或者維數(shù)災等一系列問題，所以，引進神經(jīng)網(wǎng)絡對動態(tài)規(guī)劃具有較大的解決實際問題的意義。神經(jīng)動態(tài)規(guī)劃如圖1所示。

2 基于神經(jīng)動態(tài)規(guī)劃算法的最優(yōu)路徑實現(xiàn)

（1）將原來的問題分解成很多個小問題，即子階段，并且找到每個子階段的最優(yōu)解決辦法。求解多級問題的步驟為：根據(jù)每個問題的特點，劃分子階段。在劃分子階段時，必須按照一定的規(guī)則，比如根據(jù)執(zhí)行決策的時間、空間的順序等。本文用x來表示子階段變量。

（2）求解狀態(tài)和狀態(tài)變量。每個子階段具體的起始位置可以依靠自然狀態(tài)來指導，其中客觀條件階段性數(shù)目的狀態(tài)是自然狀態(tài)中的一種，它傳達每個子階段的關鍵信息，此外，一組或者無后效性的變量同樣可以用來表示狀態(tài)變量。本文用Hx來表示第x級的狀態(tài)變量。

（3）求解原問題決策變量和集合。從目前階段到下一個階段狀態(tài)選擇時，決策者需要做出恰當?shù)臎Q策，決策變量的范圍稱為集合。本文用Dx表示決策集合，用Ux表示決策變量。

（4）研究狀態(tài)轉(zhuǎn)移的方程。假設狀態(tài)轉(zhuǎn)移方程是：Hx+1=Tx（Hx，Ux）。次方程式中Tx不定，根據(jù)具體問題才能確定，如果Hx確定，一旦變量Ux確定，那么第x+1階段狀態(tài)變量（Hx+1）也將確定。

（5）研究指標函數(shù)。因為n和vi的遞進性和可分離性，所以很容易找到指標函數(shù)n和vi之間的關系，顯然，指標函數(shù)的求解也相對簡單化。

（6）動態(tài)規(guī)劃函數(shù)的基本方程。邊界條件為；

，第x-m階的最優(yōu)動態(tài)規(guī)劃函數(shù)是。

3 仿真結果

將上述模型，在Matlab仿真軟件上進行模擬仿真，分解原始問題并確定各個子階段的最佳方案，將這個問題用網(wǎng)格的形式如圖2進行表示：A為起始地點，E為目標地點，從起始地點到目標終點有很多路徑，假設經(jīng)過每個節(jié)點需要一定的運輸成本，在Matlab仿真軟件上進行仿真后依據(jù)動態(tài)規(guī)則算法的要求，設定好相應的算法模型以及相應的計算公式，這樣便可以找到最優(yōu)路徑。

由圖2可以非常清楚的看出，成本最低的路線為：或者或者，成本都是110。仿真結果可以看出神經(jīng)動態(tài)規(guī)劃算法具有較多優(yōu)點：得到清晰運算結果；很容易找到全局的最優(yōu)路徑；可以找到一組完善的解，有利進一步的分析。

4 結語

我們在使用神經(jīng)動態(tài)規(guī)劃算法來探索最優(yōu)路徑的時候，具有很多優(yōu)勢，首先其具有穩(wěn)定、可靠的步驟，過程并不復雜，但是給予我們的結果十分清晰明確，且適用于現(xiàn)實生活。使用這種動態(tài)規(guī)劃算法解決復雜的問題時，可以非常容易找到解決方案，而且效率很高。當然，該算法也有一定的局限，但只要我們不斷地改進完善，日后繼續(xù)研究神經(jīng)動態(tài)規(guī)劃算法，相信一定可以攻克更多的局限，能夠使其更好地被應用。

參考文獻

[1]謬慧芬，邵小兵.動態(tài)規(guī)劃算法的原理及應用[J].中國科技信息，2006（23）：32.

[2]楊琰，廖偉志，李文敬，楊文，李杰.基于Petri網(wǎng)的顧及轉(zhuǎn)向延誤的最優(yōu)路徑算法[J].計算機工程與設計，2013（10）.

作者簡介

楊超（1994-），男，廣東省吳川市人。現(xiàn)在就讀于長沙理工大學計算機科學與技術系。

第4篇

關鍵詞：最短路徑；動態(tài)規(guī)劃；C 語言編程

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

數(shù)學源于生活，又服務于生活.它是一門研究現(xiàn)實世界中的數(shù)量關系與空間形式的學科.當今社會，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴大，自然資源的不斷開發(fā)利用.像天然氣管道鋪設問題，廠區(qū)布局問題，旅行費用最小問題等都已成為我們平時經(jīng)濟生活中的普遍問題.它們其實都可以化歸為最短路線問題，而最短路問題實質(zhì)上是一個組合優(yōu)化問題[1]。

動態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，它將求解分成多階段進行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實際問題時，更顯其優(yōu)越性。為了快速、簡單的計算最短路徑，節(jié)約運輸時間與成本，該文利用動態(tài)規(guī)劃的思想編寫了C語言程序，解決物流運輸過程中多地點的最短路徑的選擇問題。

2 最短路徑問題

2.1 最短路徑問題算法的基本思想

在求解網(wǎng)絡圖上節(jié)點間最短路徑的方法中，目前國內(nèi)外一致公認的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網(wǎng)絡被抽象為一個圖論中定義的有向或無向圖，并利用圖的節(jié)點鄰接矩陣記錄點間的關聯(lián)信息。在進行圖的遍歷以搜索最短路徑時，以該矩陣為基礎不斷進行目標值的最小性判別，直到獲得最后的優(yōu)化路徑[2]。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎。為了求出賦權圖中任意兩結點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結點為源點，重復執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復雜度為[On3]，雖然與重復執(zhí)行Dijkstra算法n次的時間復雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。

2.2 最短路徑問題算法的基本步驟[3]

這樣經(jīng)過有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動態(tài)規(guī)劃算法基本步驟

我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃[1]。在解決多個階段決策問題時采用動態(tài)規(guī)劃法是一個很有效的措施，同時易于實現(xiàn)。

根據(jù)動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態(tài)變量。4）根據(jù)狀態(tài)變量確定費用函數(shù)和目標函數(shù)。5）建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。

根據(jù)動態(tài)規(guī)劃的基本模型，確定用動態(tài)規(guī)劃方法解題的基本思路，是將一個[n]階段決策問題轉(zhuǎn)化為一次求解[n]個具有遞推關系的單階段的決策問題，以此來簡化計算過程.其一般步驟如下：

用于衡量所選決策優(yōu)劣的函數(shù)稱為指標函數(shù).指標函數(shù)有有階段的指標函數(shù)和過程的指標函數(shù)之分.階段的指標函數(shù)是對應某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標函數(shù)是指從狀態(tài)[xn（k=1，2，...，n）]出發(fā)至過程最終，當采取某種子策略時，按預定的標準得到的效益值。這個值既與[xk]本身的狀態(tài)值有關，又與[xk]以后所選取的策略有關，它是兩者的函數(shù)值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標函數(shù)又是它所包含的各階段指標函數(shù)的函數(shù)。本文研究的過程的的指標函數(shù)是其各階段指標函數(shù)的和的形式.當[xk]的值確定后，指標函數(shù)的值就只同k階段起的子策略有關。對應于從狀態(tài)[xk]出發(fā)的最優(yōu)子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態(tài)規(guī)劃求解最短路徑程序流程圖如圖2所示。

3 最短路徑態(tài)規(guī)劃實際應用舉例

設某物流配送網(wǎng)絡圖由12個配送點組成，點1為配送中心起點，12為終點，試求自終點到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離[4]。

首先用動態(tài)規(guī)劃法來討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點9、10、11，它們在一步之內(nèi)可到達點12；

2）集合[ξ3]中有點6，7，8，它們不超過兩步就可達到點12；

3）集合[ξ2]中包括點 2、3、4、5，不超過三步就可到達點12；

4）集合[ξ1]中包括點1，不超過四步可到達點12；

按照動態(tài)規(guī)劃法類推，得到最優(yōu)路徑長為16，徑路通過點為1，2，7，10，12和1，3，6，10，12。

根據(jù)動態(tài)規(guī)劃算法編寫C語言計算程序[5] [6]，計算得到實驗結果如下圖4所示：

由圖4可以看出程序得到的結果與本文推出的結果一樣。證明了本文編寫的C語言程序是正確的。

4 結束語

綜上所述，用動態(tài)規(guī)劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實現(xiàn).我們可以看到，動態(tài)規(guī)劃方法的應用很廣泛，已成功解決了許多實際問題，具有一定的實用性。此種算法我們用動態(tài)規(guī)劃思想來編程，并解決相應的問題，其在 VC 環(huán)境下實現(xiàn)，能方便快速的計算出到達目的地的最短距離及路徑，節(jié)省更多的運輸時間與成本。不過，該文只考慮了動態(tài)規(guī)劃算法在生活中的簡單運用，在實際生活中可能存在多個目的地或者更復雜的情況.因此我們可以考慮將其進行改進或者結合啟發(fā)式算法，使之更好的運用在實際生活中，這有待于以后的繼續(xù)研究。

參考文獻：

[1] 杜彥娟.利用動態(tài)規(guī)劃數(shù)學模型求解最短路徑[J].煤炭技術，2005（1）：94-95.

第5篇

關鍵詞:移動多智能體;全局規(guī)劃;局部規(guī)劃

中圖分類號: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

在移動智能體相關技術研究中,路徑規(guī)劃技術是一個重要研究領域。移動智能體路徑規(guī)劃問題是指在有障礙的環(huán)境中,尋找一條智能體從起始點到目標點的運動路徑,使智能體在運動過程中安全、無碰撞地繞過所有的障礙物。這不同于用動態(tài)規(guī)劃等方法求得最短路徑,而是指移動智能體能對靜態(tài)及動態(tài)環(huán)境下做出綜合性判斷,進行智能決策。在以往的研究中,移動智能體路徑規(guī)劃方法大體上可以分為三種類型:其一是基于環(huán)境模型的路徑規(guī)劃,它能處理完全已知的環(huán)境下的路路徑規(guī)劃。而當環(huán)境變化時(出現(xiàn)移動障礙物)時,此方法效果較差,具體方法有:A*方法、可視圖法、柵格化和拓撲圖法等;其二是基于傳感器信息的局部路徑規(guī)劃方法,其具體的方法有:人工勢場法、模糊邏輯法和遺傳算法等;其三是基于行為的導航行為單元,如跟蹤和避碰等,這些單元彼此協(xié)調(diào)工作,完成總體導航任務。隨著計算機、傳感器及控制技術的發(fā)展,特別是各種新算法不斷涌現(xiàn),移動機器人路徑規(guī)劃技術已經(jīng)取得了豐碩研究成果。

一個好的路徑規(guī)劃方法需要滿足如下性能[1]:合理性、完備性、最優(yōu)性、適時、環(huán)境變化適應性和滿足約束。有些方法沒有高深的理論,但計算簡單,實時性、安全性好,就有存在的空間。如何使性能指標更好是各種算法研究的一個重要方向。

在未知的(或部分已知的),動態(tài)的非結構的環(huán)境下,多智能體利用傳統(tǒng)的路徑規(guī)劃方法很難滿足前面的性能要求,本文提出了一種將全局路徑規(guī)劃方法和局部規(guī)劃方法相結合,將基于反應的行為規(guī)劃和基于慎思的行為規(guī)劃相結合的路徑規(guī)劃方法,其思路如下:多智能體分別采用A*算法進行全局路徑規(guī)劃,各自生成到達目標點的子目錄節(jié)點序列,同時采用改進的人工勢能對子目錄節(jié)點序列中相鄰節(jié)點進行路徑的平滑和優(yōu)化處理,該方法不但能夠充分利用已知環(huán)境信息生成全局最優(yōu)路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規(guī)劃的性能。

1 路徑規(guī)劃方法

1.1 相關研究

1) A*算法

在最佳優(yōu)先搜索的研究中,最廣范圍應有的方法為A*搜索,其基本思想[2]是:它把到達節(jié)點的代價g(n)和從該節(jié)點到目標節(jié)點的代價h(n)結合起來對節(jié)點進行評價:f(n) = g(n) + h(n)(1)。A*算法用于移動多智能體的路徑規(guī)劃時,多智能體分別按照已知的地圖規(guī)劃出一條路徑,然后沿著這條生成路徑運動,但智能體傳感探測到的環(huán)境信息和原來的環(huán)境信息不一致時,智能體重新規(guī)劃從當前位置到目標點的路徑。如此循環(huán)直至智能體到達目標點或者發(fā)現(xiàn)目標點不可達[3]。重新規(guī)劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且由于采用A*方法規(guī)劃出的最優(yōu)路徑并沒有考慮到機器人的運動學約束,即使機器人可以采用A*方法規(guī)劃出一條最優(yōu)路徑,機器人也未必可以沿著這條路徑運動。

2) 人工勢能法

人工勢能法由 Khatib 提出的一種虛擬力法[4]。人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但根據(jù)人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只能局部的,當智能體和障礙物超過障礙物影響范圍的時候,智能體就不受來自障礙物引起的排斥勢場的影響。所以,勢場法只能解決局部空間的避障問題,他缺乏所在的全局信息,,這樣就造成產(chǎn)生局部最優(yōu)解不能進行整體規(guī)劃,智能于局部最小點的時候,智能體容易產(chǎn)生振蕩和停滯不前。

1.2 路徑規(guī)劃方法描述

鑒于A*算法全局路徑搜索的全局性與改進人工勢場算法局部路徑搜索的靈活性,通過一定的方法把兩者結合起來,其思路如下:多智能體分別采用A*算法進行全局路徑規(guī)劃,各自生成到達目標點的子目錄節(jié)點序列,同時采用改進的人工勢能對子目錄節(jié)點序列中相鄰節(jié)點進行路徑的平滑和優(yōu)化處理,該方法不但能夠充分利用已知環(huán)境信息生成全局最優(yōu)路徑,而且還能及時處理所遇到的隨機障礙(其它智能體)信息,從而提高了多智能體整體的路徑規(guī)劃的性能。由于A*方法采用柵格表示地圖,柵格粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數(shù)增加。采用改進人工勢場的局部路徑規(guī)劃方法對A*方法進行優(yōu)化,可以有效增大A*方法的柵格粒度,達到降低A*方法運算量的目的。

2 環(huán)境構造

目前主要有三種比較典型的環(huán)境建模方法:構型空間法、自由空間法和柵格法,本文仿真實驗采用的環(huán)境建模方法是柵格法,柵格法將機器人路徑規(guī)劃的環(huán)境劃分成二維網(wǎng)格,每格為一個單元,并假設障礙的位置和大小已知,且在機器人運動過程中不會發(fā)生變化。柵格法中的網(wǎng)格單元共有三種類型,即障礙網(wǎng)格、自由網(wǎng)格和機器人所在網(wǎng)格。目前常用的柵格表示方法有兩種,即直角坐標法和序號法。這兩種表示方法本質(zhì)上是一樣的,每個單元格都與(x, y)一一對應。本文采用序號法表示柵格,設柵格的中心點坐標為柵格的直角坐標,則每個柵格編號都與其直角坐標一一對應,地圖中任意一點(x,y)與柵格編號N的映射關系為:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x軸的取值范圍,Gs表示柵格尺寸的大小,INT函數(shù)表示取整,而柵格中心點的坐標為(xG,yG),它與柵格編號N之間的關系為:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符號%表示取余操作。本文中根據(jù)機器人的尺寸來確定柵格的粒度,假設一個柵格能容納一個智能體,這里選擇柵格的大小為40cm×40cm[5]。本文的仿真環(huán)境為800cm×800cm,柵格號N=0~399,機器人的初始位置的柵格號為N=42,目標位置的柵格號為N=314。在Visual Studio 2005中進行仿真,仿真結果如圖1所示,長方形和橢圓圖形代表障礙物柵格,小圓圈所代表的柵格為機器人的起始柵格和目標柵格,剩下的是自由柵格。在路徑規(guī)劃中機器人可以選擇自由柵格作為它的路徑點。

建立柵格后,對柵格進行初始化。設置變量G_Obstacle為0表示自由柵格,G_Obstacle為1表示障礙網(wǎng)格包括機器人柵格。若障礙物或智能體占當前位置柵格面積大于1/3則設置變量G_Obstacle為1.

3 數(shù)據(jù)的采集

對于簡單地形,我們將實際地形就行考察并進行測量、量化,轉(zhuǎn)化為平面坐標數(shù)據(jù)最后轉(zhuǎn)換相應的柵格編號。對于復雜地形在沒有航攝資料的情況下,本實驗以地圖為數(shù)據(jù)源的DTM數(shù)據(jù)獲取方法在,可利用已有的地形圖采集地形數(shù)據(jù),用手扶跟蹤式數(shù)字化儀將平面圖形轉(zhuǎn)化為平面坐標數(shù)據(jù),最后轉(zhuǎn)換相應的柵格編號。

4 實現(xiàn)過程

第1步:對環(huán)境信息進行數(shù)據(jù)采集并轉(zhuǎn)化成相應的平面坐標數(shù)據(jù)。

第2步:確定各個智能體的初始位置和目標位置。

第3步:建立柵格,對柵格進行初始化。

第4步:智能體S(i)首先根據(jù)已知信息規(guī)劃出各自的一條目標序列S(i)n。

第5步:智能體S(i)利用測試傳感器探測到臨界危險區(qū)L范圍內(nèi)的信息與原有信息是否一致,當智能體利用傳感器探測到臨界危險區(qū)L范圍內(nèi)的信息與原有信息一致時,利用改進后的人工勢能算法搜索相鄰目標點之間的軌跡,否則智能體搜索從當前序列點S(i)n到S(i)n+4路徑。定義臨界危險區(qū)L、目標序列點S(i)n(n>=1)。

第6步:智能體一旦移動到達目標柵格,則程序終止;否則返回第5步。系統(tǒng)的工作流程如圖2所示。

5 仿真結果及結論

在Visual Studio 2005平臺上進行了仿真,,首先根據(jù)已知環(huán)境信息,進行數(shù)據(jù)采集量化并進行柵格化處理,設置障礙和智能體的大小及位置(為了簡單化,本實驗所有障礙都設置為圓形),再進行初始化操作,采用0、1二元信息數(shù)組存儲柵格化的地形。

智能體運用A*算法進行全局路徑規(guī)劃,圖3顯示兩個智能體的運動過程,顯然兩個智能體的路徑相交可能會發(fā)生碰撞,智能體為了避免碰撞應重新規(guī)劃算法依舊是從當前位置到目標點的全局搜索的過程,運算量較大。而且顯然只用A*算法規(guī)劃出二維路徑點序列,相鄰兩點之間的夾角一定是π/4的整倍數(shù),機器人很難按照所生成的序列點運動。智能體采用改進后的人工勢場進行目標序列點之間的局部路徑規(guī)劃,圖4顯示智能體的運動過程。顯然智能體的整條運動軌跡顯得比較平滑同時又實現(xiàn)實時避障的目的。

6 總結

本文對多智能體在動態(tài)環(huán)境下路徑規(guī)劃技術進行了研究探索,提出了一種能夠?qū)⑷致窂揭?guī)劃方法和局部路徑規(guī)劃方法相結合,通過仿真取得了很好的結果,證明A*和人工勢場算法的結合可行。

參考文獻:

[1] 劉華軍,楊靜宇,陸建峰,等.移動機器人運動規(guī)劃研究綜述[J].中國工程科學,2006,8(1):85-94.

[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.

第6篇

關鍵詞：快速搜索隨機樹；汽車局部路徑規(guī)劃；高斯分布；路徑跟隨

中圖分類號：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

近年來隨著汽車向智能化的不斷發(fā)展，無人駕駛汽車技術引得越來越多人開始關注.路徑規(guī)劃作為其中一項關鍵技術，許多學者開展了有益的探索，并取得了一些研究成果.比如A*算法[1]、D*算法[2]等啟發(fā)式搜索算法，在復雜環(huán)境下有著很好的規(guī)劃速度，但是路徑并不理想；人工勢場法[3]是一種虛擬力算法，其優(yōu)點是規(guī)劃的路徑平滑，但是容易陷入局部最優(yōu)解；人工勢場法與彈性繩模型結合[4-6]在車輛局部路徑規(guī)劃時有理想的路徑，但由于模型比較復雜，搜索效率低；此外蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡算法、水滴算法等智能仿生算法[7-10]，在理復雜動態(tài)環(huán)境信息時有較好表現(xiàn)，但由于需迭代計算，時效性不夠好.

快速搜索隨機樹算法（RRT）[11]由Lavalle于1998年提出，是一種基于樹結構的典型算法，在移動機器人路徑規(guī)劃中有著較早應用.由于算法在進行路徑規(guī)劃時是隨機采樣，不需要預處理，因此有著很快的搜索速度.路徑點之間可以經(jīng)過運動學、動力學仿真生成可執(zhí)行曲線，因此該方法可用于解決含有運動學約束的路徑規(guī)劃問題.但RRT算法存在一些不足：1）重現(xiàn)性差，對同一環(huán)境進行多次路徑規(guī)劃結果不同；2）尋找最優(yōu)或者次優(yōu)路徑能力較差；3）隨機采樣點在整個可行域內(nèi)隨機尋點的搜索方式，存在很多不必要的運算，影響算法速度.

隨著RRT算法的應用和改進，一些學者也提出了不同的方法.偏向RRT[12]以及雙向RRT[13]的提出使得算法的搜索效率得到了提高；DRRT[14]與MP-RRT[15]原算法在搜索路徑的穩(wěn)定性上做出了改進.但上述改進之后的結果并不適用于汽車行駛路徑.針對以上不足，本文將建立道路模型，考慮路徑約束，改進RRT算法，使其規(guī)劃出的路徑能夠適用于汽車運動.

1 道路環(huán)境建模

在環(huán)境已知的情況下，建立道路環(huán)境模型.直道環(huán)境模型根據(jù)道路長度以及車道寬即可得到，彎道環(huán)境模型如圖1所示，位于道路上的慣性坐標系的原點選取在道路中心線上，道路寬度為W，規(guī)劃起始點即主車位置A，目標點C，障礙車位置為B.高速路直線之間的緩和曲線通常采用回旋線來實現(xiàn)平滑過渡，回旋線的特征是其曲率變化為常數(shù).假定長度為l的回旋線線段起始曲率為C1，終止曲率為Cf，變化常數(shù)為C2，則有C（l）=C1+C2×l成立，C2=（Cf-C1）/l.回旋線常采用多項式逼近的形式表示：

式中：R0為道路中心線初始橫向偏移；C0為初始的方向角.根據(jù)圖1，結合邊界條件R（0）=0，R′（0）=0可以將R0和C0消除掉.

為了保持車道寬度一致，彎道的左右邊界是通過中心線上點向著其法線方向上下平移單個車道寬度來得到.在道路坐標系下中心線上的點可由式（2）表示.

中心線上一點的切向量和法向量則可以表示成：

因此道路左右界則可以由（4）來表示

2 RRT算法原理

基本的RRT算法如圖2所示，RRT算法以給定的起始點為隨機樹根節(jié)點，根據(jù)當前環(huán)境快速有效地搜索可行域空間，通過隨機采樣點，將搜索導向空白區(qū)域并增加隨機樹的葉節(jié)點直至目標點區(qū)域，從而生成從起始點到目標點的路徑.

算法的一般步驟如下：

1）首先通過environment（）函數(shù)建立環(huán)境數(shù)據(jù)模型，初始化各項參數(shù)；

2） 通過while循環(huán)來判斷樹節(jié)點是否達到目標點goal范圍內(nèi)，若沒有，則開始擴展點.先生成隨機采樣點Prand，在樹節(jié)點上通過函數(shù)Nearest（）選擇距離Prand最近的樹節(jié)點作為擴展節(jié)點Pnear，通過擴展函數(shù)New得到新的樹節(jié)點Tnew，并將其添加到隨機樹上，直到循環(huán)終止.

3）通過getpath（）函數(shù)來得到生成的路徑path.

原算法主體程序如下：

如圖3所示，傳統(tǒng)的RRT算法應用到車輛路徑規(guī)劃中存在以下問題：

1）由于隨機采樣點隨機性大，導致搜索空間中有過多的冗余搜索，表現(xiàn)為搜索樹布滿了道路環(huán)境空間；

2）搜索出來的路徑曲率變化過大，甚至出現(xiàn)小范圍內(nèi)直角變化，這樣的路徑并不能滿足汽車行駛的正常狀態(tài)；

3）路徑在靠近障礙時才開始避障，對于運動中的汽車會造成失穩(wěn)或者與障礙物發(fā)生碰撞.

道路長度/m

3 RRT算法的改進

3.1 期望路徑模型

針對原RRT算法表現(xiàn)出來的問題，提出了一種隨機采樣點高斯分布的改進RRT算法.根據(jù)汽車行駛環(huán)境不同，設計了兩種期望路徑模型.

3.1.1 直道模型

駕駛經(jīng)驗豐富的駕駛員期望的避障路徑模型如圖4（a）所示.期望路徑以函數(shù)Epz表示，其中各段均為直線段，start為起始點，goal為目標點.

提前避障在車輛避障路徑規(guī)劃中是必要的，故在模型中需要添加提前避障距離S，并根據(jù)車速調(diào)整大小.設V為當前車速，tc為換道時間，通常完成換道時間tc為1～2 s，ΔS為自定義安全提前量.

對于車速為V的汽車其剎車距離

則提前避障距離

圖4（a）中fz2表示提前避障區(qū)域，區(qū)間長度為S，fz4區(qū)間長度也為S.

期望路徑只是粗略的路徑模型，在此基礎上進行平滑得出的路徑并不能滿足汽車安全穩(wěn)定行駛的要求.因此采用RRT算法進行路徑尋優(yōu)搜索.為了使隨機采樣點分布在期望路徑周圍，利用高斯分布函數(shù)生成的點集中在其均值周圍的特點，結合期望路徑函數(shù)則可以實現(xiàn)這一目的.在道路坐標系下隨機采樣點的高斯分布概率函數(shù)為：

令μ=Epz（x），則可以得到如圖4（b）所示的隨機采樣點分布趨勢圖.

道路長度/m（a）期望路徑模型

道路長度/m（b）隨機采樣點高斯分布

σ的大小決定了隨機點在Epz（x）周圍的集中程度，σ越小越靠近Epz（x）.特別地，對于fz2與fz4周圍的隨機采樣點，如圖4（a）以fz2為例，通過相應水平范圍的隨機點高斯分布旋轉(zhuǎn)處理得到，即對

旋轉(zhuǎn)角度：

3.1.2 彎道模型

將彎道分為多段，采用直線代替彎道曲線的形式來完成期望路徑模型的建立.如圖5（a）彎道的期望路徑以函數(shù)Epw來表示.

隨機采樣點在fw各段函數(shù)區(qū)間的分布同直道的處理相同，從而可以得到如圖5（b）所示的分布趨勢圖.

3.2 約束條件

要使一條規(guī)劃出來的路徑有效地應用于汽車運動，即路徑可跟蹤，則規(guī)劃路徑時必須滿足道路環(huán)境約束.首先，隨機樹節(jié)點的生成要滿足道路環(huán)境約束，設Bleft，Bright分別為道路的左右邊界，則樹節(jié)點位置坐標要滿足：

考慮到汽車是具有幾何形體的，設其車寬為D，則上述y方向的約束變?yōu)椋?/p>

假定汽車質(zhì)心沿著規(guī)劃的路徑運動，為了保證行駛過程中的穩(wěn)定性，規(guī)劃出的路徑的曲率變化不能過大.若在實際情況下前輪最大轉(zhuǎn)角為θmax，則路徑中子節(jié)點與其父節(jié)點的連線和父節(jié)點與其父節(jié)點的連線之間的夾角β必須滿足β

其中：K1為直線TaTb的斜率；K2為TcTb的斜率.βT為夾角限制值.

為了保證所擴展的點不與障礙車有交集，即樹節(jié)點不與障礙車碰撞的要求，采用安全橢圓包絡障礙車，并適當放大安全橢圓以保證避障要求.若新節(jié)點與其父節(jié)點的連線不與安全橢圓相交，則所擴展的新點滿足避障要求.取連線上的五等分點Pi（x，y），則約束方程表現(xiàn)為：

其中（xob，yob）為障礙車的位置，半車長a=2 m；半車寬b=1 m；s為安全橢圓放大系數(shù)，當s=2時，安全橢圓正好包絡矩形的障礙車，因此從安全避障考慮，s≥2.

3.3 啟發(fā)式搜索

原算法在擴展隨機樹時，由于缺乏導向機制，算法的收斂速度在一定程度上受到了影響，為了提高算法計算速度，引入啟發(fā)式機制來對隨機采樣點以及隨機樹節(jié)點的選擇進行處理.采樣點Prand在隨機生成過程中會以一定概率ρ0選擇目標點，從而將隨機樹節(jié)點向目標點引導，通常ρ0=0.1.

其中，GaussRand（）為隨機采樣點生成函數(shù).

另外，在選擇Pnear時不再單獨以距離Prand最近作為選擇標準，而是以隨機樹節(jié)點的擇優(yōu)系數(shù)Ch來決定，Pnear確定為Ch值最小所對應的樹節(jié)點.

其中ωi，ωj為權重系數(shù)，且ωi+ωj=1；Dpr為樹節(jié)點到Prand的距離，Dg為樹節(jié)點到目標點goal的距離.當ωj>ωi時，選擇出的Pnear具有向目說憧拷的趨勢.通過以上啟發(fā)式的處理，使得算法更快地收斂，減少計算時間.

3.4 平滑處理

RRT算法規(guī)劃出來的路徑通常會存在小范圍內(nèi)的曲折現(xiàn)象，路徑并不連續(xù).為了使得路徑能夠滿足汽車在運動時的穩(wěn)定性和安全性要求，需要對規(guī)劃出來的路徑進行光滑處理.B樣條在處理路徑光滑時能夠不改變整個路徑形狀而進行局部調(diào)整[16]，利用B樣條這一特性，來對算法所規(guī)劃出來的路徑進行插值擬合，從而達到光滑路徑的目的，通常所采用的為3次B樣條曲線.

當有m+1個控制頂點Pi（i=0，1，…，m）時，3次B樣條曲線表示為：

3.5 算法流程

隨機樹節(jié)點的擴展受到隨機采樣點的影響，通過以上方式的處理，隨機采樣點不再是在可行域內(nèi)隨機分布，而是具有一定的趨向性.這樣使得隨機樹節(jié)點的分布也具有趨向性，算法的隨機性得到了改善，所規(guī)劃出來的路徑質(zhì)量得到提高.主體程序如下：

算法的實現(xiàn)過程如下：

1）初始化階段，首先通過environment（）函數(shù)建立道路環(huán)境模型，根據(jù)現(xiàn)有的環(huán)境模型，以expect（）函數(shù)建立期望路徑模型.

2） 路徑求解階段，進入while循環(huán)來判斷樹節(jié)點是否達到目標點goal范圍內(nèi)，若沒有，則開始擴展點.隨機采樣點Prand通過Pick（）函數(shù)在goal和GaussRand（）函數(shù)所生成的點之間進行概率選擇；根據(jù)當前Prand計算樹節(jié)點的擇優(yōu)系數(shù)Ch，并由Fitbest（）函數(shù)得出Pnear；通過函數(shù)New在Pnear的基礎上擴展出新節(jié)點Tnew，當新節(jié)點滿足約束函數(shù)constraint（）時，新節(jié)點則添加到整個隨機樹Tree上，否則，返回循環(huán)重新尋點直到其終止.

3）路徑處理階段，getPath（）函數(shù)從所得的Tree中獲取最短路徑，最后通過函數(shù)smoothing（）對所得路徑path進行光滑處理，得到一條平緩的路徑.

4 仿真實驗驗證

改進的RRT在應用于信息多變的不確定環(huán)境時會存在建模困難的缺陷，本文主要對確定車道環(huán)境下的改進RRT開展研究.由于條件有限，不能在實際車輛中進行試驗驗證.而Prescan軟件能夠?qū)嶋H場景進行建模，并且有根據(jù)實車建立的車輛模型數(shù)據(jù)庫，能夠模擬實際車輛行駛過程.因此，為驗證改進RRT算法的有效性，在Prescan軟件平臺中搭建直道和彎道場景如圖6所示，仿真實驗硬件平臺Win10+Core-i7@3.6Hz+ARM@8G.仿真參數(shù)如表1～表3所示.

4.1 規(guī)劃時間的影響參數(shù)分析

影響算法計算效率的重要參數(shù)主要包括搜索步長ΔL、約束夾角βT.步長越小，為了搜索到目標點所需要的節(jié)點數(shù)目也就越多，計算時間越長；約束夾角βT越小，規(guī)劃路徑也越平緩，但計算時間也越長.改變步長以及約束夾角并進行大量仿真實驗，統(tǒng)計表明：在ΔL=3，βT=15°時，改進RRT算法在規(guī)劃時間以及路徑效果上的綜合表現(xiàn)較好.圖7為ΔL=3時，不同角度下計算時間的統(tǒng)計，以20次計算時間平均值做一次統(tǒng)計.

4.2 規(guī)劃路徑對比

為說明改進RRT算法的效果，在直道場景中，采用了其余2種規(guī)劃算法來進行對比.一種是蟻群算法[7]，另一種是彈性繩算法[5].直道仿真對比結果如圖8所示，改進前后的算法規(guī)劃效果在彎道中的對比如圖9所示，路徑效果參數(shù)對比如表4所示.由圖和表的結果對比可知：

1）相對于蟻群算法和原RRT算法，改進RRT算法與彈性繩算法規(guī)劃的路徑都更為平滑，不存在頻繁的大曲率變化，且路徑較短.

2）從直道的規(guī)劃時間上看，傳統(tǒng)的蟻群算法用時最長，而彈性繩算法平均計算時間為1.42 s.改進后的RRT算法平均計算時間0.25 s，相對于原RRT計算時間略有增加，這是由于增加了模型處理過程以及各約束條件所導致的.但與其余2種算法相比，改進RRT算法依然保持其在計算時間上的優(yōu)勢.

3） 原RRT算法在靠近障礙時才開始避障，改進RRT算法能夠?qū)崿F(xiàn)提前避障，并且根據(jù)車速不同自動調(diào)節(jié)避障提前量，這對安全行駛很重要.

4.3 路徑跟隨驗證

對一條規(guī)劃出來的路徑，需要驗證其有效性，即路徑的跟隨性，本文采用路徑跟隨時主車的側向加速度曲線監(jiān)測路徑的穩(wěn)定性，跟隨速度20 m/s.直道和彎道仿真結果分別如圖10、圖11所示.

由圖10（a）（b）可知，直道跟隨路徑基本和目標路徑一致，跟隨誤差在0.2 m以內(nèi)，誤差較小；車輛保持穩(wěn)定行駛時的最大側向加速度由地面附著力決定，通常為0.8g.由圖10（c）可知，跟隨時的側向加速度在0.4g以內(nèi)，說明整個過程中都能夠保證主車按照路徑行駛時的穩(wěn)定性.彎道仿真結果如圖11所示，跟隨誤差都在0.1 m以內(nèi)，跟隨效果好；側向加速度都在0.5g范圍內(nèi)，滿足穩(wěn)定性要求.

5 結 論

本文在將RRT算法應用到汽車避障局部路徑規(guī)劃時，針對原算法在隨機性以及路徑曲率變化上的不足，建立了直道和彎道的期望路徑模型，使隨機采樣點在期望路徑模型周圍近似呈高斯分布，采用啟發(fā)式搜索方式使采樣點和隨機樹節(jié)點向目標點靠近，從而降低算法的隨機性；并且在路徑規(guī)劃時加入約束，使得所規(guī)劃出的路徑更為合理.仿真實驗結果表明：改進RRT算法不僅規(guī)劃出的路徑質(zhì)量高、實時好、跟隨性強，而且車輛的穩(wěn)定性也滿足要求.因此，改進RRT算法可以應用于實時汽車路徑規(guī)劃.

參考文獻

[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] 肖浩， 宋曉琳， 曹昊天. 基于危險斥力場的自動駕駛汽車主動避撞局部路徑規(guī)劃[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] 康冰， 王曦輝， 劉富. 基于改進蟻群算法的搜索機器人路徑規(guī)劃[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] 吳乙萬，黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[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.

第7篇

關鍵字：最優(yōu)路徑選擇；A-Star算法；貪婪算法；模擬仿真

中圖分類號：TP301.6 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2013.06.012

0 前言

物流與國民經(jīng)濟及生活的諸多領域密切相關，越來越多得到重視，甚至被看作是企業(yè)“第三利潤的源泉”，而在物流成本方面，運輸費用占大約50% ，比重最大[1]。因此，物流配送中最優(yōu)路徑選擇的研究具有巨大的經(jīng)濟意義。物流配送中的最優(yōu)路徑選擇問題的研究和應用都相當廣泛，近幾十年，國內(nèi)外均有大量企業(yè)機構、學者對該問題進行了大量而深入的研究，取得豐碩的學術成果。如1953年，Bodin，Golden 等人便撰文綜述了該問題的有關研究進展情況，列舉了幾百余篇相關文獻，這些文獻成為了早期車輛路徑問題研究資料，隨后隨著該問題不斷研究深入，約束模型及條件不斷變化，車輛路徑問題研究的最新進展可見Alt- inkerner 和 Oavish，Laporte，Salhi 等人的綜述性文章[2]。圍繞該問題的解決也極大推動了計算機學科的發(fā)展，不斷有新的模型和算法推出。針對物流配送車輛路徑優(yōu)化問題的求解方法很多，根據(jù)算法原理的不同大致可分為兩大類：精確算法和智能式啟發(fā)算法。精確算法是指可以車輛路徑問題的數(shù)學模型可求出其最優(yōu)解算法，但由于算法存在諸多缺陷，所以在實際中應用并不廣泛。目前，啟發(fā)式算法是解決物流配送中最優(yōu)路徑選擇的主要方法和主向[3]。近年來，隨著科學的發(fā)展，一些新的啟發(fā)式方法被用在求解物流路徑選擇及優(yōu)化問題上，可以通過使用啟發(fā)式方法獲得較快的收斂速度和較高質(zhì)量的全局解，常用的算法有模擬退火算法、GA 算法等[4]。A*算法是人工智能中一種典型的啟發(fā)式搜索算法，被廣泛應用于最優(yōu)路徑求解和一些策略設計的問題中[5、6]。本文結合貪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平臺上，采用Visual C++編程對物流配送問題進行模擬仿真，同時考慮最短時間和最短路徑兩個方面，以此來解決物流配送中最優(yōu)路徑選擇的問題，達到物流配送最優(yōu)線路規(guī)劃的目的。

1 需求分析

1.1 總體框架

在物流配送時，物流車裝載當日需要配送的貨品從倉庫出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個客戶進行配送，最后返回倉庫。這就涉及在配送時配送路線的選擇問題，而在配送之前，IT系統(tǒng)需要根據(jù)客戶的配送地址間線路間距和經(jīng)驗路況分析計算出一條最優(yōu)配送路徑。并且在配送過程中，如果某路段發(fā)生堵車狀況，需要動態(tài)調(diào)整配送路線，以達到最優(yōu)配送的目的。為此，在QT Creator平臺上，以面向?qū)ο蟮脑O計方式來開發(fā)最優(yōu)物流配送的功能軟件。通過再現(xiàn)交通運輸環(huán)境，模擬物流運輸中的突發(fā)事件，優(yōu)化物流配送的路線，分別根據(jù)需求，設計出最短路徑和最少時間兩種配送方式，并通過二維動畫的效果顯示出來。通過此軟件呆模擬解決物流配送中各種情況，從而降低運輸成本。設計本軟件的總體思路如圖1所示。

1.2 功能設計

設計的軟件從功能上來說，主要包括以下幾點：

（1）載入一張已有地圖（*.map的文件）或生成一張空白地圖。用戶可以在這張空白地圖上操作，通過障礙物的增刪來設置城市的道路。

（2）道路突發(fā)事件設置。

a.用戶可以根據(jù)實際情況或主觀意愿對地圖進行規(guī)劃。在地圖中添加障礙物，設置道路前方的暫時封閉或者道路施工等未知路況。

b.也可以模擬城市人流量大的地方，通過在地圖上，設置易堵車而導致前行速度下降的未知路況。

（3）設置倉庫及客戶點。

a.隨機生成倉庫及客戶點。在地圖中，用戶可隨機生成若干個客戶點和倉庫點。

b.指定生成倉庫及客戶點。在已生成或者模擬的地圖上，根據(jù)用戶的不同需求，可在地圖上任意位置生成客戶點和倉庫點。

c.可以對倉庫及客戶點進行增刪。

（4）計算路徑及優(yōu)化。

a.根據(jù)用戶之前模擬的各種情況，計算其最短路徑。根據(jù)用戶載入或者自己規(guī)劃的地圖，模擬計算出最短路徑，在界面的左上角顯示其時間，并在地圖上顯示其路徑。

b.根據(jù)用戶之前模擬的各種情況，計算其最短時間。根據(jù)用戶載入或者自己規(guī)劃的地圖，模擬計算出最短時間，在界面的左上角顯示其時間，并在地圖上顯示其對應路徑。

軟件的大致功能如下圖2所示。

圖2 功能模塊圖

2 算法描述

2.1 貪婪算法

貪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到達山頂，即逐步獲得最優(yōu)解，是解決最優(yōu)化問題時的一種簡單但適用范圍有限的策略[7]。

貪婪算法是基于鄰域的搜索技術，它在計算過程中逐步構造最優(yōu)解[8]。在構造解的過程中，每一步常以當前情況為基礎根據(jù)某個優(yōu)化測度（greedy criterion，貪婪準則，也稱貪婪因子）作最優(yōu)選擇，而不考慮各種可能的整體情況，選擇一旦做出就不再更改，這省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，一般情況下只是近似最優(yōu)解[9]。雖然貪婪法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的求最優(yōu)解問題來說，它是一種最直接的算法設計技術，通過一系列局部最優(yōu)的選擇，即貪婪選擇可以產(chǎn)生整體最優(yōu)解[10]。

對于一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數(shù)量度標準作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標準是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標準并不是一件容易的事，但對某問題能選擇出最優(yōu)量度標準后，用貪婪算法求解則特別有效。最優(yōu)解可以通過一系列局部最優(yōu)的選擇（貪婪選擇）來達到。根據(jù)當前狀態(tài)做出在當前看來是最好的選擇，即局部最優(yōu)解選擇，然后再去解出這個選擇后產(chǎn)生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規(guī)模更小的子問題，最終可得到問題的一個整體最優(yōu)解。它是一種改進了的分級處理方法。

2.2 A-Star算法

A*算法是人工智能中一種典型的啟發(fā)式搜索算法，它是一種靜態(tài)路網(wǎng)中求解最短路最優(yōu)算法，其公式可表示為：

（1）

其中，是從初始點經(jīng)由節(jié)點到目標點的估價函數(shù)；是在狀態(tài)空間中從初始節(jié)點到節(jié)點的實際代價；是從到目標節(jié)點最佳路徑的估計代價[11、12]。

在A*算法中，找到最短路徑（最優(yōu)解的）的關鍵在于估價函數(shù)的選取。當估價值到目標節(jié)點的距離實際值時，搜索的點數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解；當估價值到目標節(jié)點的距離實際值時，搜索的點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解[13、14]。

A*算法的難點在于建立一個合適的估價函數(shù)，估價函數(shù)構造得越準確，則A*算法搜索的時間就越短[15]。A*算法的估價函數(shù)可表示為：

（2）

這里，是估價函數(shù)，是起點到節(jié)點的最短路徑值，是到目標的最短路徑的啟發(fā)值。由于這個其實是無法預先知道的，所以我們用前面的估價函數(shù)做近似。當時，可以代替（大多數(shù)情況下都是滿足的，可以不用考慮），但只有在時，才能代替。可以證明，應用這樣的估價函數(shù)能有效地找到最短路徑。

本文綜合貪婪算法和A*算法的思想來求解決物流配送中最優(yōu)路徑選擇的問題。圖3為綜合算法的流程圖。

3 實驗仿真設計

3.1 軟件概述

開發(fā)的軟件要具有實用性，這就是說，能給企業(yè)帶來效益，這就包了兩方面的內(nèi)容：企業(yè)能獲得的利潤和客戶的滿意程度。也就是說采用所建立的模型要設計出合理的物流配送路線，保證在較短的路程或時間內(nèi)遍歷所有的節(jié)點，從而保證貨物按時送到。

從算法角度來看，為了保證算法的有效性和高效性，結合軟件的功能，則該軟件的設計目標[16]為：①路徑最短或時間最短， ②滿足實際中遍歷節(jié)點的要求， ③算法高效性， ④軟件的普度適用性。

軟件操作流程具體步驟如下：

第一步.用戶載入一張已有地圖或生成一張空白地圖。

第二步.設置相關參數(shù)及約束條件。

第三步.顯示計算結果和最優(yōu)路徑。

該軟件可運行于Windows 7操作系統(tǒng)，主要包括3個部分：地圖文件的讀取部分、算法部分和用戶界面部分。

3.2 軟件模擬實現(xiàn)

1.初始化

根據(jù)軟件的需求分析，本軟件初始產(chǎn)生一個空白的二維平面圖，在該模塊用戶可以根據(jù)實際情況模擬出實際路況，提供兩種方式來實現(xiàn)該功能：

（1）通過點擊工具欄上面的初始化按鈕自動初始化。

（2）通過鼠標右鍵選擇初始化選項。

圖4 系統(tǒng)初始化界面

2.道路的參數(shù)設置

在視圖界面中，用戶可以點擊鼠標右鍵，選擇生成障礙物或刪除障礙物來模擬現(xiàn)實生活中城市道路可能發(fā)生的各種情況，如：

（1）用戶可以根據(jù)實際情況，點擊鼠標右鍵，在出現(xiàn)的下拉菜單中，選中添加障礙物，設置道路前方的暫時封閉或者道路施工等未知路況。

（2）也可以在地圖上，點擊鼠標右鍵來設置易堵車而導致前行速度下降的未知路況。

在地圖中淺黃色的區(qū)域是模擬人流量大的鬧市區(qū)。深褐色方塊模擬障礙物。

圖5 道路模擬圖

3.倉庫點及客戶點的生成

客戶點和倉庫點的生成包括兩種情況：

（1）隨機生成客戶點和倉庫點。在視圖界面中，通過頂端的輸入框，輸入生成客戶點或倉庫點的個數(shù)，點擊生成客戶點或倉庫點按鈕來隨機生成客戶點或倉庫點。

（2）在指定位置生成客戶點和倉庫點。在已生成或者模擬的地圖上，根據(jù)用戶不同的需求，在地圖指定位置生成客戶點和倉庫點。

在如圖5的道路設計下，在地圖上隨機添加了10個客戶點和1個倉庫點，如圖6所示。

圖6 場景界面圖

4.路徑最短和時間最短的配送路徑

根據(jù)圖6所設計的場景，通過貪婪算法和A*算法，分別計算出路徑最短和時間最短的配送路徑，并在地圖上顯示其路徑。圖7依據(jù)最短路徑實現(xiàn)物流配送的最優(yōu)方案，主要從距離這個方面進行考慮；圖8根據(jù)最短時間實現(xiàn)物流配送的最優(yōu)方案，主要考慮的是在道路有突發(fā)狀況發(fā)生時物流配送的時間最少。

圖7 路徑最短的配送路徑

圖8 時間最短的配送路徑

4 認識與結論

通過對物流配送中的實際問題進行模擬研究，在QT Creator平臺上采用Visual C++編程開發(fā)出針對物流配送中最優(yōu)路徑選擇問題的軟件，從最短時間和最短路程兩方面考慮，為物流配送公司提供可靠有效的參考信息，使配送方案符合實際情況。同時，深入研究了貪婪算法和A*算法，從算法的角度對物流配送中的時間和路程進行分析，設計實現(xiàn)了物流配送中最優(yōu)數(shù)學模型，以期達到最優(yōu)路徑的目的。通過本研究的結果來看，開發(fā)的模擬軟件能解決物流運送過程中的時間、路徑等實際問題，同時實現(xiàn)了二維圖形的可視化，更加直觀地體現(xiàn)了物流配送中存在的問題和解決方式，對物流配送企業(yè)提高運營效率、降低運營成本等具有重要意義。

參考文獻

[1]黃中鼎. 現(xiàn)代物流管理學[M]. 上海： 上海財經(jīng)大學出版社， 2004， 1-37.

[2]謝秉磊， 郭耀煌， 郭強. 動態(tài)車輛路徑問題：現(xiàn)狀與展望[J]. 系統(tǒng)工程理論方法應用， 2002， 11（2）： 116-120.

[3]鄒挺. 基于蟻群和人工魚群混合群智能算法在物流配送路徑優(yōu)化問題中的應用研究[D]. 蘇州： 蘇州大學， 2011， 3-7.

[4]吳云志， 樂毅， 王超， 等. 蟻群算法在物流路徑優(yōu)化中的應用及仿真[J]. 合肥工業(yè)大學學報（ 自然科學版）， 2009， 32（2）：211-214.

[5]王海梅， 周獻中. 直線優(yōu)化A*算法在最短路徑問題中的高效實現(xiàn)[A]. 全國第計算機技術與應用（CACIS）學術會議論文集（下冊）[C]， 2008， 932-936.

[6]陳和平， 張前哨. A*算法在游戲地圖尋徑中的應用與實現(xiàn)[J]. 計算機應用與軟件， 2005， 22（12）：94-96.

[7]晏杰. Matlab 中貪婪算法求解背包問題的研究與應用[J]. 赤峰學院學報（自然科學版）， 2012， 28（9）：23-24.

[8]劉紀岸， 周康渠， 寧李俊， 等. 基于貪婪算法的摩托車生產(chǎn)物流配送規(guī)則優(yōu)化[J]. 制造業(yè)自動化， 2010， 32（5）：97-99.

[9]蔣建國， 李勇， 夏娜. 一種求解單任務Agent聯(lián)盟生成的貪婪算法[J]. 系統(tǒng)仿真學報， 2008， 20（8）：1961-1964.

[10]江朝勇， 陳子慶， 謝贊福. 基于優(yōu)先級貪婪算法的排課系統(tǒng)排研究與實現(xiàn)[J]. 信息技術， 2008， 24（7）：173-176.

[11]徐偉， 孫士兵. 基于A-Star算法警用地圖查詢系統(tǒng)的設計與實現(xiàn)[J]. 信息安全與技術， 2011. 5-2：52-56.

[12]王敬東， 李佳. A*算法在地圖尋徑中的實用性優(yōu)化[J]. 電腦開發(fā)與應用， 2007， 20（7）：24-25.

[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一種現(xiàn)代方法[M]. 姜哲，譯. 北京：人民郵電出版社， 2004， 76-83.

[14]王文杰， 葉世偉. 人工智能原理與應用[M]. 北京：人民郵電出版社， 2004， 115-121.

第8篇

關鍵詞： B樣條曲線； 無人車； 路徑規(guī)劃； 碰撞檢測； 最大曲率約束； 最優(yōu)路徑

中圖分類號：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 引言

近年來，無人駕駛技術備受關注，各大研究機構和企業(yè)爭相推出各自的無人駕駛平臺。無人車作為未來智能交通的主要主體也逐漸融入到我們的日常生活中，比如自主巡航[1]和自動泊車等等。然而，為了使其更好地服務于我們，需要進一步提高其智能化水平，而路徑規(guī)劃作為連接環(huán)境感知和運動規(guī)劃的橋梁，是無人車智能化水平的重要體現(xiàn)[2]。

由于受到自身動力學和運動學模型的約束，車輛的路徑規(guī)劃問題除過要嚴格滿足端點狀態(tài)約束之外，還要求其中間狀態(tài)滿足運動系統(tǒng)的微分約束。由于實現(xiàn)簡單，并且高階多項式曲線能夠很好地滿足運動系統(tǒng)的微分約束，生成高階平滑的路徑，所以很多路徑規(guī)劃系統(tǒng)選擇使用基于多項式曲線的方法生成路徑。B樣條曲線是一種典型的多項式曲線，且因為其所有的中間狀態(tài)均是由控制點加權生成，所以其能夠完全滿足端點狀態(tài)約束。綜合考慮無人車路徑規(guī)劃的要求和實現(xiàn)復雜度，在僅已知初始位姿和目標位姿的情況下，本文選擇B樣條曲線生成路徑，重點講述分步規(guī)劃模型，即路徑簇生成、最大曲率約束、碰撞檢測以及最優(yōu)評價四個過程，并通過Matlab仿真對本文方法進行了驗證。

2 問題描述

本節(jié)分別描述了無人車路徑規(guī)劃問題和B樣條曲線。

2.1 路徑規(guī)劃問題描述

路徑規(guī)劃得到的是一條從初始位置到目標位置的路徑，即二維平面內(nèi)一條從初始位置點到目標位置點的曲線，曲線上的每一個點表示車在行駛過程中的一個狀態(tài)。考慮到實現(xiàn)方便，本文將路徑描述成離散點序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點[Si（xi，yi，θi）]表示車的一個狀態(tài)，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態(tài)和目標狀態(tài)。圖1中的圓[（xobs1，yobs1，robs1）]表示環(huán)境中的障礙物，[（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樣條曲線的次數(shù)，[t]為控制參數(shù)，其取值范圍為[[0，1]]，[Pi+k]為控制點，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。

3 本文算法

本節(jié)重點講述基于B樣條曲線的路徑規(guī)劃方法和基于該方法生成路徑的過程。

3.1 基于B樣條曲線的路徑規(guī)劃方法

選擇三階B樣條曲線生成幾何路徑，即每四個控制點生成一個路徑片段，然后通過片段的拼接就可以實現(xiàn)從初始狀態(tài)到目標狀態(tài)的路徑規(guī)劃，下面著重講述基于六控制點的三階B樣條曲線生成滿足車輛端點位姿約束路徑的方法，如圖2所示。

l 依據(jù)初始狀態(tài)選擇控制點[P0，P1，P2]。當[P0，P1，P2]三個控制點共線，并且[P1]為線段[P0P2]的中點時，生成的B樣條曲線與線段[P0P2]相切于點[P1]。所以選擇無人車的初始位置為控制點[P1]，將控制點[P0]和[P2]選在初始航向角[θstart]所在直線上，并關于控制點[P1]對稱。如是，即能滿足車輛的初始位姿約束；

l 依據(jù)目標狀態(tài)選擇控制點[P3，P4，P5]。當[P3，P4，P5]三個控制點共線，并且[P4]為線段[P3P5]的中點時，生成的B樣條曲線與線段[P3P5]相切與點[P4]。所以選擇無人車的目標位置為控制點[P3]，將控制點[P3]和[P5]選在目標航向角[θgoal]所在的直線上，并關于控制點[P3]對稱。如是，即能滿足車輛的目標位姿約束。

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測

3.2 分步路徑規(guī)劃

本小節(jié)將以圖3所給定的場景為例，講述最優(yōu)路徑生成的過程。

3.2.1 路徑簇生成

在選定控制點[P1]和[P4]之后，通過選擇不同的控制點[P2]和[P3]，從而得到多組控制點，進而得到多條路徑。將控制點選擇的極限定為線段[P1P2]、[P3P4]與[P1P4]相等，但是[P1P2]和[P3P4]不能出現(xiàn)交叉。將這個范圍等間隔量化，各取四個點，共組成16組控制點，得到16條路徑，如圖3（a）中的藍色曲線所示。

3.2.3 最大曲率約束

理論上，車輛的最小轉(zhuǎn)彎半徑[Rmin=Lsin（θmax）]是其本身屬性[3]，只取決于車輛的軸距[L]和最大前輪轉(zhuǎn)角[θmax]。那么，車輛可行駛路徑的最大曲率[κmax=1Rmin]也是固定的，假設無人車可行駛路徑的最大曲率[κmax=16]，以此為約束條件，在路徑簇中選擇滿足最大曲率約束的路徑，如圖3（b）所示，圖中綠色曲線表示不滿足最大曲率約束的路徑。

3.2.4 碰撞檢測

碰撞檢測的目的是保證車輛在規(guī)劃路徑上行駛而不與障礙物發(fā)生碰撞。采取的碰撞檢測的方法很簡單，因為環(huán)境中的障礙物采用圓來描述，所以只要判斷路徑上每一點到圓心的距離與障礙物半徑的關系，就能確定其是否發(fā)生碰撞。由兩點間距離公式：

[d=（x1-x2）2+（y1-y2）2] （2）

如果[d]大于障礙物半徑，則不發(fā)生碰撞；如果[d]小于障礙物半徑，則發(fā)生碰撞。圖3（c）中的藍色曲線表示既滿足最大曲率約束，又不與障礙物碰撞的路徑。

3.2.2 最優(yōu)路徑

路徑要求的側重點不同，優(yōu)化的目標函數(shù)也可以有多種選擇，常用的目標函數(shù)有最短和最平滑等。其中，路徑最短可以抽象成優(yōu)化問題：

[traoptimal=arg mintraids] （3）

路徑最平滑可以抽象成優(yōu)化問題：

[traoptimal=arg mintraiκ2] （4）

式中，[traoptimal]為最優(yōu)路徑，[traids]為第[i]條路徑的長度，[traiκ2]為第[i]條路徑上所有點處的曲率平方之和。圖3（d）中的紅色曲線即為得到的最短可行駛路徑。

如是，就能得到滿足車輛運動學約束，并且無碰撞的最優(yōu)路徑。

4 結論

本文選擇使用B樣條曲線解決無人車路徑規(guī)劃問題，并建立了基于B樣條曲線的分步規(guī)劃模型。仿真結果表明，使用基于B樣條曲線的路徑規(guī)劃方法能夠很好地解決簡單障礙物場景中無人車的路徑規(guī)劃問題，并且因為路徑生成過程簡單，所以該方法常常表現(xiàn)得十分高效，能夠完全滿足無人車路徑規(guī)劃系統(tǒng)對算法實時性的要求。

參考文獻：

[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.

第9篇

關鍵詞： 最短路徑； A*算法； Dijkstra算法； 路徑優(yōu)化

中圖分類號： 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]是圖論中網(wǎng)絡分析的經(jīng)典問題，近年來，隨著路徑搜索技術的不斷發(fā)展，已經(jīng)涌現(xiàn)出很多成熟的路徑規(guī)劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關于人工智能領域的啟發(fā)式搜索算法和動態(tài)規(guī)劃算法等。A*啟發(fā)式搜索算法作為人工智能領域的重要組成部分，其針對網(wǎng)格數(shù)據(jù)有著更高的運算效率，而且利用啟發(fā)信息大幅度提高了搜索速度。這種全新的啟發(fā)式搜索算法[4]將會極大地改變現(xiàn)有的交通管理與服務模式。

1 A*算法原理

傳統(tǒng)的BFS算法的評估函數(shù)只考慮當前點與終點的距離，其策略是選擇與終點最近的點進行搜索。而Dijkstra算法則只關注當前點與起點的距離，選擇與起點最近的點開始搜索。A*算法[5]則是將二者結合起來，其啟發(fā)函數(shù)采用如下的計算公式：

式中：就是A*算法[5]對每個節(jié)點的評估函數(shù)[2]，其包含兩部分信息：是從起點到當前節(jié)點的實際代價，也就是從起點到當前節(jié)點的移動距離；相鄰的兩個點的移動距離是1，當前點距離起點越遠，這個值就越大。是從當前節(jié)點到終點的距離評估值，這是一個從當前節(jié)點到終點的移動距離的估計值。

A*算法的搜索過程需要兩個表：一個是OPEN表，存放當前已經(jīng)被發(fā)現(xiàn)但是還沒有搜索過的節(jié)點；另一個是CLOSE表，存放已經(jīng)搜索過的節(jié)點，具體的算法流程圖如圖1所示。

1.1 常用的距離評估函數(shù)

是A*算法的距離估計值[6]，A*算法需要一個距離評估函數(shù)來計算這個值。常用的距離評估函數(shù)有曼哈頓距離、歐式幾何平面距離和切比雪夫距離。在沒有障礙物的地圖上，這三種距離評估函數(shù)得到的效果是一樣的，但是在有障礙物的情況下，這三種距離評估函數(shù)的效果略有差異。當距離評估函數(shù)總是0時，A*算法就退化為Dijkstra算法[6]的效果。

1.1.1 曼哈頓距離

從數(shù)學上描述，曼哈頓距離是兩個點在各個坐標軸上的距離差值的總和，維幾何空間中曼哈頓距離的數(shù)學描述為：

對于二維平面上的兩個點和，其曼哈頓距離為：

即歐式幾何平面距離為在直角坐標系中兩個坐標軸上的投影距離和。

1.1.2 歐式幾何平面距離

歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數(shù)學定義是維空間中兩個點之間的真實距離（幾何距離），其數(shù)學符號可以描述為：

對于二維平面上的兩個點和其歐式幾何平面距離為：

即平面幾何中兩點之間的幾何距離。

1.1.3 切比雪夫距離

切比雪夫距離（Chebyshev Distance）是由一致范數(shù)（或稱上確界范數(shù)）衍生的度量，從數(shù)學角度上理解，對于兩個向量和其切比雪夫距離就是向量中各個分量的差的絕對值中最大的那一個，用數(shù)學符號可以描述為：

特別情況下，對于平面上的兩個點和，其切比雪夫距離為：

距離評估函數(shù)與A*算法的結果之間存在很微妙的關系，如果令始終為0，相當于一點啟發(fā)信息都沒有，則A*算法[5]退化為Dijkstra算法，這種情況即為最差的A*算法。的值越小，啟發(fā)信息越少，搜索范圍越大，速度越慢，但是越有希望得到最短路徑；的值越大，啟發(fā)信息越多，搜索的范圍越大，但是其有可能得不到真正的最短路徑。當大到一定程度時，公式中的就可以忽略不計，則A*算法演化成為BFS（廣度優(yōu)先搜索算法），速度最快，但是不一定能夠得到最短路徑。所以通過調(diào)整和函數(shù)，可以使得A*算法[6]在速度與準確性之間獲得一個折中的效果。

1.2 A*算法的實現(xiàn)

A*算法實現(xiàn)的關鍵在于維護OPEN表和CLOSE表，其中對于OPEN表的主要操作就是查詢最小的節(jié)點以及刪除節(jié)點，因此考慮在算法實現(xiàn)時將OPEN表[7]設計為有序表。這樣在OPEN列表存儲數(shù)據(jù)時就可以自動將數(shù)據(jù)按照距離進行排序，這樣算法的執(zhí)行效率比較高。A*算法的參數(shù)設置見表1，參數(shù)的迭代次數(shù)見圖2。

通過仿真實驗分析可以得出，A*算法[5]在有障礙物的情況下中和了BFS算法和Dijkstra算法的優(yōu)點，能夠更有效地找到最終的最短路徑。

2 A*算法與Dijkstra算法效率的比較

Dijkstra算法是典型的單源最短路徑算法，其適用于求解沒有負權邊的帶權有向圖的單源最短路徑問題。由于Dijkstra算法[2?3]使用了廣度優(yōu)先搜索的策略，它可以一次得到所有點的最短路徑。但是，它只是簡單地做廣度優(yōu)先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗費很多時間和空間。考慮到實際地圖上面兩點之間存在位置和距離等信息，A*算法既能夠像Dijkstra算法那樣搜索到最短路徑，又能像BFS（廣度優(yōu)先搜索算法）一樣使用啟發(fā)式函數(shù)進行啟發(fā)式搜索，是目前各種尋徑算法中最受歡迎的選擇。

將A*算法同Dijkstra算法[6]進行仿真比較，用于比較性能的主要指標有：時間復雜度分析；搜索到最短路徑的成功率分析。利用C++語言編制了三種算法的最短路徑搜索程序，運行在本地計算機上，并得出仿真模擬圖。

搜索效率的對比結果如表2所示。

由表2可以看出：當?shù)貓D節(jié)點的個數(shù)和弧的條數(shù)比較多時，A*算法[5]的搜索效率比Dijkstra算法快很多，當節(jié)點數(shù)不斷增多時，其搜索最短路徑的效率更高。在相同路網(wǎng)和位置信息的條件下進行仿真實驗的結果如圖3所示。

由圖3可以看出，兩種算法在相同障礙物條件下進行模擬仿真時，A*算法的搜索效率和時間復雜度要明顯優(yōu)于Dijkstra算法，并對不同實驗場景下的效率進行對比，結果如圖4所示。

3 結 語

從Dijkstra算法和A*算法[2]的實現(xiàn)可知，Dijkstra算法的時間復雜度是其中是有向圖中頂點的個數(shù)。對于不含負權邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優(yōu)先搜索算法的特點，在速度和準確性之間有很大的靈活性。除了調(diào)整和可以獲得不同的效果外，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] 周郭許，唐西林.基于柵格模型的機器人路徑規(guī)劃快速算法[J].計算機工程與應用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學約束的機器人無碰運動規(guī)劃[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].系統(tǒng)仿真學報，2007，19（22）：5175?5177.

[8] 林丹.一種室內(nèi)清潔機器人返回路徑規(guī)劃算法[J].重慶科技學院學報（自然科學版），2009，12（1）：110?113.

[9] 趙真明，孟正大.基于加權A～*算法的服務型機器人路徑規(guī)劃[J].華中科技大學學報（自然科學版），2008（z1）：196?198.