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

第1篇

作者簡介： 朱新平（1983-），男，博士，研究方向?yàn)橄冗M(jìn)機(jī)場場面運(yùn)行控制，電話：13419037831，E-mail：

通訊作者： 韓松臣（1963-），男，教授，博士，研究方向?yàn)榭罩薪煌ò踩⒖沼蛞?guī)劃管理，E-mail：

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

摘要：

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

關(guān)鍵詞：

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

中圖分類號： V351.11文獻(xiàn)標(biāo)志碼： A

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

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

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

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

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

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

在文獻(xiàn)[2]的基礎(chǔ)上，本文從以下方面展開研究：

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

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

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

1

航空器場面運(yùn)行過程建模

1.1

面向資源的場面運(yùn)行過程建模

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

1.2

航空器滑行特征分析

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

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

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

（3） 當(dāng)航空器從直線段滑入彎道時，減速過程通常在進(jìn)入彎道前完成.

2

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

2.1

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

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

（1）

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

（2）

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

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

2.2

染色體編碼

染色體應(yīng)滿足以下約束：

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

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

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

2.3

選擇算子與遺傳算子

2.3.1選擇算子

2.3.2

交叉算子

2.3.3

變異算子

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

3

仿真試驗(yàn)

3.1

仿真試驗(yàn)設(shè)計

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

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

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

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

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

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

3.2

仿真試驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

4

結(jié)束語

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

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

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

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

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

參考文獻(xiàn)：

[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)工程與電子技術(shù)，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ī)場滑行道運(yùn)行控制建模[J]. 交通運(yùn)輸工程學(xué)報，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]. 西南交通大學(xué)學(xué)報，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]黃圣國，孫同江，呂兵. 運(yùn)輸網(wǎng)絡(luò)的最短有向路Petri網(wǎng)仿真算法[J]. 南京航空航天大學(xué)學(xué)報，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)的機(jī)場場面路徑規(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)工程理論與實(shí)踐，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ī)滑行路徑優(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]劉兆明，葛宏偉，錢鋒. 基于遺傳算法的機(jī)場調(diào)度優(yōu)化算法[J]. 華東理工大學(xué)學(xué)報：自然科學(xué)版，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ān)鍵詞：路徑規(guī)劃；搜索區(qū)域；A*算法

中圖分類號：TP306文獻(xiàn)標(biāo)識碼：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ī)劃是在車輛行駛前或行駛過程中尋找車輛從起始點(diǎn)到達(dá)目的地的最佳行車路線的過程[1], 它屬于智能交通

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

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

2 A*算法

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

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

f(n)是從初始點(diǎn)通過節(jié)點(diǎn)n 到達(dá)目標(biāo)點(diǎn)的估價函數(shù)；

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

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

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

3 改進(jìn)的A*算法球最短路徑

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

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

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

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

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

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

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

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

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

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

例如圖1，為帶權(quán)的有向圖。

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

4)重復(fù)第三步：

若在深度為7的搜索中找到目標(biāo)結(jié)點(diǎn)且僅有一條路徑，則該路徑為最終路徑，返回；

若在若在深度為7的搜索中找到目標(biāo)結(jié)點(diǎn)并且有多條路徑則回朔，比較找到的路徑費(fèi)用，取權(quán)值最小的作為最終路徑；

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

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

第3篇

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

作者簡介

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

第4篇

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

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

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

2 最短路徑問題

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

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

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結(jié)點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復(fù)雜度為[On3]，雖然與重復(fù)執(zhí)行Dijkstra算法n次的時間復(fù)雜度相同，但其形式上略為簡單，且實(shí)際運(yù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ī)劃法是一個很有效的措施，同時易于實(shí)現(xiàn)。

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

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

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

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

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

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

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

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

3）集合[ξ2]中包括點(diǎn) 2、3、4、5，不超過三步就可到達(dá)點(diǎn)12；

4）集合[ξ1]中包括點(diǎn)1，不超過四步可到達(dá)點(diǎn)12；

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

第5篇

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

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

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

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

1 路徑規(guī)劃方法

1.1 相關(guān)研究

1) A*算法

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

2) 人工勢能法

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

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

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

2 環(huán)境構(gòu)造

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

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

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

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

4 實(shí)現(xiàn)過程

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

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

第3步:建立柵格,對柵格進(jìn)行初始化。

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

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

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

5 仿真結(jié)果及結(jié)論

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

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

6 總結(jié)

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

參考文獻(xiàn):

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

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

第6篇

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

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

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

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

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

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

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

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

中心線上一點(diǎn)的切向量和法向量則可以表示成：

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

2 RRT算法原理

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

算法的一般步驟如下：

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

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

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

原算法主體程序如下：

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

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

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

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

道路長度/m

3 RRT算法的改進(jìn)

3.1 期望路徑模型

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

3.1.1 直道模型

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

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

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

則提前避障距離

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

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

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

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

道路長度/m（b）隨機(jī)采樣點(diǎn)高斯分布

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

旋轉(zhuǎn)角度：

3.1.2 彎道模型

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

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

3.2 約束條件

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

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

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

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

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

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

3.3 啟發(fā)式搜索

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

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

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

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

3.4 平滑處理

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

當(dāng)有m+1個控制頂點(diǎn)Pi（i=0，1，…，m）時，3次B樣條曲線表示為：

3.5 算法流程

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

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

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

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

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

4 仿真實(shí)驗(yàn)驗(yàn)證

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

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

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

4.2 規(guī)劃路徑對比

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

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

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

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

4.3 路徑跟隨驗(yàn)證

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[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]. 工程設(shè)計學(xué)報， 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ìn)蟻群算法的搜索機(jī)器人路徑規(guī)劃[J]. 吉林大學(xué)學(xué)報：工學(xué)版， 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].湖南大學(xué)學(xué)報：自然科學(xué)，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篇

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

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A DOI：10.3969/j.issn.1003-6970.2013.06.012

0 前言

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

1 需求分析

1.1 總體框架

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

1.2 功能設(shè)計

設(shè)計的軟件從功能上來說，主要包括以下幾點(diǎn)：

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

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

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

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

（3）設(shè)置倉庫及客戶點(diǎn)。

a.隨機(jī)生成倉庫及客戶點(diǎn)。在地圖中，用戶可隨機(jī)生成若干個客戶點(diǎn)和倉庫點(diǎn)。

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

c.可以對倉庫及客戶點(diǎn)進(jìn)行增刪。

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

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

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

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

圖2 功能模塊圖

2 算法描述

2.1 貪婪算法

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

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

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

2.2 A-Star算法

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

（1）

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

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

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

（2）

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

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

3 實(shí)驗(yàn)仿真設(shè)計

3.1 軟件概述

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

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

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

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

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

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

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

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

1.初始化

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

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

（2）通過鼠標(biāo)右鍵選擇初始化選項(xiàng)。

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

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

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

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

（2）也可以在地圖上，點(diǎn)擊鼠標(biāo)右鍵來設(shè)置易堵車而導(dǎo)致前行速度下降的未知路況。

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

圖5 道路模擬圖

3.倉庫點(diǎn)及客戶點(diǎn)的生成

客戶點(diǎn)和倉庫點(diǎn)的生成包括兩種情況：

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

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

在如圖5的道路設(shè)計下，在地圖上隨機(jī)添加了10個客戶點(diǎn)和1個倉庫點(diǎn)，如圖6所示。

圖6 場景界面圖

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

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

圖7 路徑最短的配送路徑

圖8 時間最短的配送路徑

4 認(rèn)識與結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第8篇

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

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：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 引言

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

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

2 問題描述

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

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

路徑規(guī)劃得到的是一條從初始位置到目標(biāo)位置的路徑，即二維平面內(nèi)一條從初始位置點(diǎn)到目標(biāo)位置點(diǎn)的曲線，曲線上的每一個點(diǎn)表示車在行駛過程中的一個狀態(tài)。考慮到實(shí)現(xiàn)方便，本文將路徑描述成離散點(diǎn)序列[Sstart，S1，???，Sn，Sgoal]，如圖1所示，序列中每一個點(diǎn)[Si（xi，yi，θi）]表示車的一個狀態(tài)，其中[（xi，yi）]表示此時刻車輛的位置，[θi]表示車輛的航向，[Sstart]和[Sgoal]分別表示車輛的初始狀態(tài)和目標(biāo)狀態(tài)。圖1中的圓[（xobs1，yobs1，robs1）]表示環(huán)境中的障礙物，[（xobs1，yobs1）]表示障礙物的位置信息，[robs1]表示障礙物的半徑。

2.2 B樣條曲線

如果給定[m+n+1]個控制點(diǎn)[Pi（i=0，1，???，m+n）]，就可以構(gòu)造[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]為控制點(diǎn)，[Fk，n（t）]為B樣條基。依次連接全部[n]階B樣條曲線段就組成了整條B樣條曲線。

3 本文算法

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

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

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

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

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

（a） 路徑簇

（b） 最大曲率約束

（c） 碰撞檢測

3.2 分步路徑規(guī)劃

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

3.2.1 路徑簇生成

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

3.2.3 最大曲率約束

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

3.2.4 碰撞檢測

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

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

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

3.2.2 最優(yōu)路徑

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

[traoptimal=arg mintraids] （3）

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

[traoptimal=arg mintraiκ2] （4）

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

1 A*算法原理

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

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

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

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

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

1.1.1 曼哈頓距離

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

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

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

1.1.2 歐式幾何平面距離

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

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

即平面幾何中兩點(diǎn)之間的幾何距離。

1.1.3 切比雪夫距離

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

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

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

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

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

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

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

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

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

搜索效率的對比結(jié)果如表2所示。

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

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

3 結(jié) 語

從Dijkstra算法和A*算法[2]的實(shí)現(xiàn)可知，Dijkstra算法的時間復(fù)雜度是其中是有向圖中頂點(diǎn)的個數(shù)。對于不含負(fù)權(quán)邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優(yōu)先搜索算法的特點(diǎn)，在速度和準(zhǔn)確性之間有很大的靈活性。除了調(diào)整和可以獲得不同的效果外，A*算法還有很多可以提高效率的改進(jìn)方法。比如，在地圖比較大的情況下使用二叉堆來維護(hù)OPEN表以獲得更好的運(yùn)算效率。

參考文獻(xiàn)

[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ī)器人路徑規(guī)劃快速算法[J].計算機(jī)工程與應(yīng)用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學(xué)約束的機(jī)器人無碰運(yùn)動規(guī)劃[J].機(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] 李得偉，韓寶明，韓宇.一種逆向改進(jìn)型A*路徑搜索算法[J].系統(tǒng)仿真學(xué)報，2007，19（22）：5175?5177.

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

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