關于路徑規劃的相關算法綜述

梁曉輝 慕永輝 吳北華 江宇

摘要：路徑規劃算法是智能領域中一項新興的關鍵支撐技術;依據路徑規劃算法的實現原理，將其分為進化型算法與非進化型算法;再依據數學特征將非進化型算法細分為經典數學與幾何圖論兩類;針對每類算法，分別從發展背景、設計思想、優缺點、改進與發展等方面簡要歸納分析;最后對路徑規劃算法的未來發展趨勢進行展望。

Abstract： Path planning algorithm is an emerging key supporting technology in the field of intelligence; According to the implementation principle of path planning algorithm， it is divided into evolutionary algorithm and non-evolutionary algorithm; Then based on the mathematical characteristics， the non-evolutionary algorithm can be divided into two types： classical mathematics and geometric graph theory; For each type of algorithm， the paper will give a brief summary and analysis from some aspects： the background of development，design ideas， advantages and disadvantages， improvement. Finally the future development trend of the path planning algorithm is forecasted.

關鍵詞：路徑規劃;進化型算法;非進化型算法;未來展望

Key words： path planning;evolutionary algorithm;non-evolutionary algorithm;future development

中圖分類號：TP242? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）03-0295-05

0? 引言

路徑規劃（Path Planning）[1]是智能技術中的熱點研究問題，已在多領域有所突破并成功得以應用。

在軍事領域涉及到的有無人機飛行路徑自動規劃[2]，導彈回避威脅[3]，智能機器人控制[4]，水下無人航行器（Unmanned underwater vehicle UUV）的自主航行[5]以及美國國防高級研究計劃局“小精靈”項目[6]等;在日常方面涉及的有基于地理信息系統（Geographic Information System，GIS）的路徑規劃[7]，城市智能交通動態路徑規劃[8]，物流或外賣配送[9]以及自動導引裝置（Automated Guided Vehicle，AGV）的路徑規劃與調度[10]等。[11]

路徑規劃的實現主要依靠高級語言編制出的算法，其主要包含：模擬退火法，A*算法，Dijkstra算法，遺傳算法，粒子束算法，人工勢場法，Voronoi法等。少部分路徑規劃也可通過硬件加以改善，例如可以使用微電子器件或光學器件解決路徑規劃在實時系統中速度慢的缺陷[12]。

1? 路徑規劃算法

依據算法實現原理，可將路徑規劃算法歸類為非進化型與進化型兩種。

1.1 非進化型算法

非進化型算法具有簡潔的設計思想流程和較高效率的處理能力。但在“機械式”解決路徑規劃問題時，不易產生最優路徑，且無法在過程中實現自我學習和自我完善，不具備記憶能力。在處理高維空間形式下的路徑規劃問題時，結果與期望有較大偏差。

依據算法數學特征，可將非進化型算法分成經典數學與幾何圖論兩類型。

1.1.1 經典數學

①圖搜索概率法。

20世紀90年代初期，M.H.Overmars提出PRM（Probabilistic? Roadmaps? Method）圖搜索概率法[13-14]。PRM主要包含離線學習階段和在線學習階段，依據搜索算法在終始點之間的優化規則形成路標圖，并在一定條件的約束下有效的解決在多維空間和復雜環境中的路徑規劃問題。

PRM圖搜索概率法的尋徑方式簡便，整個規劃場景的大小與構形空間的多維性沒有特別強烈的關系，因此復雜度較低，不需要精確建模。但由于所采集樣點隨機分布，無法覆蓋自由空間中的全部路徑，易出現搜索路徑不是所需的最優路徑，同時在規劃路徑時遇到狹窄通路或是復雜度較高的障礙集合時，算法效率就會顯得十分低下。

在對PRM的改進中，夏炎等人通過節點增強法將原路徑上的節點代替，利用圓弧替代路徑上的折線，達到減小節點拐點個數，縮短規劃路徑長度，并實現搜索路徑有較高的平滑度[15]。G.Sanchez等人在PRM的基礎上提出了SBL-PRM算法，即通過從兩個基本位姿點出發，找到路徑后再經過碰撞檢測等手段使得計算更加實時高效[16-17]。

②模擬退火算法。

1953年， N. Metropolis等人將模擬退火算法SA的思想提出。它通過模擬熱力學中固體物質的退火過程與一般組合優化問題之間的相似性并結合概率突跳特性，使得局部最優解能概率性地跳出并最終趨于全局最優的模式。

模擬退火法在算法實行中需要一個輸入作為初始解，在求解的過程中對于壞解具有包容性，不會局限于初始解所在的收斂域內。模擬退火在計算中可跳出局部極小值點，造成了所獲得的解不一定是最優解，卻一定是全局的次優解，不可避免地使算法整體受參數影響，導致全局搜索能力變差[18]。

1985年，多目標模擬退火算法MOSA被Ulungu提出，解決傳統的SA算法只針對單個目標求解并表現出了良好的性能[19]。2011年，SankaraoB等人提出了一種具有魯棒性的多目標退火算法rMOSA，能夠在較少的模擬次數下熟練到Pareto解集，使得在MOSA算法的基礎上實施擾動選擇新解，從而具有魯棒性[20]。2005年，田東平等人將適合全局搜索的遺傳算法（GA）和適合局部搜索的模擬退火算法（SA）相結合，提出了混合GA-SA計算方法，有效提高了收斂速度，并有效防止種群早熟現象，且驗證了該算法的可行性和有效性[21]。

③人工勢場法。

1986年，人工勢場法由Khatib博士[22]提出。它是一種虛擬力法，通過在目標位置與障礙物周圍構造出起共同作用的引力場與斥力場，再通過搜索勢函數的下降方向來規劃出無碰的最優路徑，整個勢場力正是由引力部分和斥力部分組成[23]。

由于人工勢場法高效的實時控制性，可以實現實時路徑規劃和平滑軌跡處理，因而也得到了廣泛應用。但是當在勢場空間中同時出現多個障礙物時，易出現零勢能點，使勢能法陷入局部最小點，造成混亂，無法完成勢場空間中的路徑規劃任務[24]。

很多學者針對勢場原理的幾個缺點進行了改進，使其具備學習能力，從而可以適應未知復雜環境或者能在多障礙物情況下消除零勢能 [25]。日本的Ya-Chun chang等人結合人工勢場法和Voronoi圖表法提出了一種混合的路徑規劃算法，在此計算中分別利用了兩種方法的優點同時解決勢場信息構造最優路徑的選擇[26]。喬莎莎等人對于遺傳算法與人工勢場法進行結合仿真，有效避免基于行為的盲目性，增加了路徑節點和平滑度，但對于全局規劃帶來的問題把握不夠[27]。

④A*算法。

1968年，A*算法由Stanford研究院的Peter Hart等人共同發表，是一種常用的路徑查找和圖形遍歷算法。它通過尋找最小路徑來估算節點的代價評估函數并作為節點的綜合優先級，當選擇下一個需要遍歷的節點時，再選取綜合優先級最高的節點一步步地找到最優路徑。A* 算法的一般過程可在文獻中查到[28]。

A*算法可以方便的找到開銷最小，路程最短的路徑，但是隨著數據量的增大，無用節點會導致A*算法搜索時間增長，同時也可以通過調節啟發函數來控制算法的速度和精確度。

Szczerba等人提出了稀疏A*搜索算法（SAS），通過將約束條件與搜索算法結合起來，可有效剪裁搜索空間 [29]。高蝦蝦等人通過搜索節點進行優化，解決了二維航線中存在的局限性問題，減少運行時間和消耗內存[30]。占偉偉等人也提出一種改進的A*算法解決大范圍三維戰場環境的無人機航跡規劃問題，但是由于戰場環境動態變化，無法達到實時航跡規劃。

⑤Dijkstra算法。

1959年，Dijkstra算法由荷蘭科學家Edsger W.Dijkstra提出[31]。該算法是單源路徑算法，用來求解一個頂點到其余各項頂點的最短路徑問題，它通過起始點為中心向外層層擴展，直至擴展到終點為止得到最短路徑。

Dijkstra算法十分簡潔，能夠有效的找到最優解，不足之處在數據節點龐大時所需的節點繁多，效率隨著數據節點的增加而下降，耗費大量內存空間與計算時間。

侯莉莉等人以鄰接鏈表和最小二叉堆的數據結構優化了Dijkstra算法，改進后的算法運行時間有所減少，效率有所提高[32];何少佳等利用Dijkstra算法的優點與蟻群算法進行改進，有效提高了搜索效率，縮短路徑長度，改善搜索路徑質量[33-34]。

⑥Floyd算法。

1978 年，Floyd 算法由圖靈獎獲得者教授Robert W. Floyd命名，通過分析有權圖的帶權鄰接矩陣，而后在矩陣中求任意兩點的最短路徑[11]。Floyd 算法適用于任意兩點間的最短路徑，同時也被經常用于計算有向圖的傳遞閉包，規劃效率要高于Dijkstra算法，但其復雜度達到了三次方的級別，不能直觀反映出各個頂點之間最短路徑序列的先后關系。

為了提高查找效率，減少頂點之間長度比較，代修宇等人對傳統的Floyd 算法進行了優化改進[35];王靖東通過對頂點過濾，頂點計算優化和反比例優化來提高路徑規劃成功率和效率[36]。程曉蓉等結合 Dijkstra 算法和 Floyd 算法的優點，提出了一種新的求最短路徑的優化算法——F.D 算法，并將這種更高效、快捷的方法應用于求解基于 GIS 的電力通信路線最短路徑問題上。

1.1.2 幾何圖論

①Voronoi圖算法。

1908年，俄國數學家 Georgy Fedoseevich提出Voronoi圖算法。這種空間分割算法的靈感來源于笛卡爾的凸域分割空間的思想，是計算幾何中的一個重要分支，對于路徑規劃的輔助性意義很大。Voronoi圖目前的生成算法主要有兩大類：矢量法和柵格法[37]。

2007 年，Bhattacharya P 等人提出了一種基于 Voronoi 圖解障礙是簡單多邊形的最短路徑問題提供了詳細算法的描述，及 Voronoi 圖算法的維護和動態的更新，該方法性能優于其他有關路徑規劃算法[38]; 2010 年，徐鵬飛等人利用半平面與 Voronoi 頂點的位置關系，提出了簡單增量構造 Voronoi 圖的算法，此算法在處理 Voronoi 邊與節點的特殊情況，并且該算法的平均時間復雜度接近線性[39]。

1.2.4 遺傳算法

1962年，遺傳算法被John Holland[66]提出。它是模擬生物進化論中的自然選擇和遺傳變異為基礎理論而形成的一種搜索算法。遺傳算法具有自組織，自適應和自學習性，能夠同時處理多個群體中的多個個體，從串集進行搜索，覆蓋面大，有利于全局搜索。但是其屬于隨機類算法，結果的可靠性較差，不能穩定的得到最優解。

王璇通過將遺傳算法與粒子群算法和人工免疫算法相結合形成混合遺傳算法，有效提高收斂速度，且使算法不易陷入局部最優值，并使用測試函數驗證了算法收斂的有效性[67]。在文獻[68]中提出了量子遺傳算法，它是對量子計算和遺傳算法相結合的產物，使得算法的適應性更強，效率更高;2016年，田欣提出新的自適應調整方式，提高了遺傳算法的尋優效率，并通過引入模擬退火算法克服遺傳算法有容易陷入局部最優的缺點[69]。

1.2.5 粒子群算法

1995 年， Eberhart 等人提出 PSO 算法[70]。它是通過模擬鳥群的生存行為提出的一種新型群智能優化算法，兼有進化計算和群智能的特點來實現復雜空間中最優解的搜索。PSO算法在初始時并非十分完善，在實際的應用時往往出現早熟收斂和全局收斂性能差等缺點。

PSO在離散域問題特別是組合優化問題的求解研究還比較少，這方面領域的研究被稱為離散PSO。1997年，J.Kennedy等人[71]提出了粒子群算法的離散二進制版本，將經過簡單的修改，使其應用于搜索二進制的空間。Xiao-Feng Xie等人提出的自組織耗散PSO算法，從熱力學的角度指出PSO的社會模型具有自組織耗散結構的特點，進而引入了混亂算子，避免了群體過早的進入穩定狀態[72]。

2? 未來展望

路徑規劃算法目前多處于理論研究，試驗或試運行階段，應用到實際層面仍需要一段時間。

同其它技術理論一樣，路徑規劃算法的產生與發展主要來自社會進步和軍事需求，同時也受已有技術的限制。針對軍事領域或智能控制領域出現的復雜問題，單一算法顯然無法高效解決。這就需要多學科知識的交叉融合，將具有不同優勢的算法有效結合成更加高效的復合型路徑規劃算法，這也是目前主流的研究方向。

由于非進化類算法具有運算量小、可實現性較強的優勢，依舊占據著一定的生存空間。但隨硬件成本的降低，運算能力水平不斷提升，具備人工智能的進化類算法必將成為該領域的核心。

未來很大概率會有更高效、實時、精確處理路徑規劃問題的新算法誕生，使得軍事武器和生產生活智能化的前景更加廣闊。

參考文獻：

[1]謝娟.路徑規劃算法的研究及應用[D].電子科技大學，2015，03.

[2]馬傳焱.多無人機飛行路徑自動規劃算法研究[J].無線電工程，2015，45（2）：5-7，33.

[3]馬云紅，周德云.一種簡單快速的導彈路徑規劃方法[J].導彈與制導學報，2005，25（3）：23-26.

[4]張佳，陳杰，竇麗華.基于路徑規劃的智能機器人控制實驗[J].實驗技術與管理，2010，27（12）：44-47.

[5]溫志文，蔡衛軍，楊春武.UUV自主航行路徑規劃方法[J].制造業自動化，2016，38（11）：1-5.

[6]袁成.美國國防高級研究計劃局“小精靈”項目[J].兵器知識，2016，9：37-39.

[7]孫蘭會，成鋒，陸愈實.基于GIS的路徑規劃算法研究與實現[J].現代電子技術，2016，39（5）：101-109.

[8]李軍.城市智能交通中的動態路徑規劃研究[D].杭州電子科技大學，2017，04.

[9]高小芳.物流配送最優路徑規劃[D].華僑大學，2017，02.

[10]劉維民AGV路徑規劃與調度系統研究[D].華南理工大學，2017，02.

[11]張廣林，胡小梅，柴劍飛，趙磊，俞濤.路徑規劃算法及其應用綜述[J].現代機械，2011，5：85-90.

[12]曾慶立，李麗華，唐圣學.基于神經網絡路徑規劃的硬件設計[J].吉首大學學報（自然科學版），2007，28（6）：74-76.

[13]L. E. Kavraki， P. Svestka， J. C. Latombe， and M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J]. IEEE Transactions on Robotics and Automation， 1996，12（4）：566-580.

[14]Kavrak i L， Svestka P， Latombe J C， et al. Probabilistic Road Maps for Path Planning in High-dimensional? Configuration- Spaces? [J].? IEEE? Transactions? on? Robotics and Automation， 1996，12（4）： 566-580.

[15]夏炎，隋巖.PRM路徑規劃算法優化研究[J].應用科技， 2010，37（10）：1-5.

[16]Sanchez G.，Latombe J. C. Single-Query Bi-Directional Motion Planning with lazy Collision Checking [C]. International Symposium on Robotics Research， Lorne， Australia， 2001.

[17]Sanchez G.， Latombe J. C. On Delaying Collision Checking in PRM Planning? Application to Multi-Robot Coordination [C]. International Journal of Robotics Research， 2002， 21（1）：? 5-26.

[18]鄭秀敏，顧大鵬，劉相術.基于柵格法-模擬退火算法的機器人路徑規劃[J].機器人技術，1008- 0570（2007）02-2-0247-02.

[19]楊理云.用模擬退火算法求解旅行商問題[J].微電子學與計算機，2007（05）：193-196.

[20]卜文浩.模擬退火算法綜述[D].西安理工大學，2007，08.

[21]田東平，遲洪欽.混合遺傳算法和模擬退火法[J].計算機工程與應用，2006（22）：63-65.

[22]Khatib O.Realtime Abstract Avoidance for Manipulators，and Mobile Robots in Proe[J].IEEE Int Conf.On.Robotics and Automation March 25-381985.500-505，also in Int JRobot Res，1986，5（1）：90-98.

[23]王肖青，王奇志.傳統人工勢場的改進[J].計算機技術與發展，1005-3751（2006）04-0096-03.

[24]王奇志.基于改進人工勢場法的多障礙機器人運動控制[C].北京：2003年中國智能自動化會議論文論文集（上冊）.

[25]許亞.基于改進的人工勢能場的移動機器人的路徑規劃研究[J].科技展望，2016（33）.

[26]Chang? Y-C，Yamamoto Y.Pathplanning of whelled mobile robot with simultaneous free space locating capability，Intelligent Service Robotics，2009，2（1）：19-22.

[27]喬莎莎，吳勇，張建東，史國慶.基于遺傳算法和人工勢場法的路徑規劃[J].現代電子技術，2012，35：75-78.

[28]熊壬浩，劉羽.A*算法的改進及并行化[J].計算機應用，2015，35（7）：1843-1848.

[29]NILSSON N.Problem-solving methods in artificial intelligence[M].IEEE Transactions on Aerospace and Electronic System，2000，36（3）：869-878.

[30]高蝦蝦，郭國龍，徐成華，馮蓉.基于改進A*算法的三維飛行航線規劃.第三屆高分辨率對地觀測學術年會論文集[C].2014，12.

[31]Dijkstra E. A note on two problems in connexi on with graphs[J].Numerische Mathematik，1951，1（1）：269-271.

[32]趙磊，侯莉莉.一種Dijkstra算法的優化實現算法-學術研究，2014.

[33]何少佳，史劍清，王海坤.基于改進蟻群粒子群算法的移動機器人路徑規劃[J].桂林理工大學學報，2014，34（4）：765-770.

[34]王輝，朱龍彪，王景良，陳紅艷，邵小江，朱志慧.基于Dijkstra-蟻群算法的泊車系統路徑規劃研究[J].工程設計學報，2016，05.

[35]代修宇，程國忠.Floyd算法的改進與優化[J].西昌學院學報·自然科學版，2012，03：63-65.

[36]王靖東，楊凌.基于優化Floyd算法的室內機器人路徑規劃研究[D].西北農林科技大學，2015.

[37]徐政超.基于voronoi圖算法的航路規劃方法研究[D].長安大學，2015.

[38]BHATTACHARYA， GAVRILOVA M L. Voronoi Diagrami n Optimal Path Planning[C]. The 4th Int-ernational Symposium on Voronoi Diagrams in Science and Engineering， 2007： 38-47.

[39]徐鵬飛，陳志剛.增量構造Voronoi區域的改進算法[J].計算機工程與應用，2010，46（8）：8-10.

[40]SHAMOS M I， HOEY D. Closest Point Problems[C]. In Proceedings of 16th IEEE Symposium on Foundations of Computer Science， 1975： 151-162.

[41]BARRY J， WANG C A. Duality of Constrained Voronoi Diagrams and Delaunay Triangulations[J]. Algorithmica， 1999， 9（2）： 142-155.

[42]徐鵬.基于模擬退火算法的機器人路徑規劃與研究[J].信息與通信，1671-4792-（2011）1-0042-03.

[43]鄭秀敏，顧大鵬，劉相術.基于柵格法-模擬退火算法的機器人路徑規劃[J].機器人技術，1008-0570（2007）02- 2- 0247- 02.

[44]雷艷敏，馮志彬.改進的勢場柵格法在機器人路徑規劃中的應用[J].長春大學學報，2009，19（1）：38-42.

[45]鄭秀敏，顧大鵬，劉相術.基于柵格法-模擬退火法的機器人路徑規劃[J].機器人技術，1008-0570（2007）02-2-0247-02.

[46]Glover F.and M. Tabu Search. Boston， Kluwer Academic Publishers，1997.

[47]邢文訓，謝金星.現代優化計算方法[M].清華大學出版社，2005：51-68.

[48]王凌.智能優化算法及其應用[M].清華大學出版社，2001.

[49]王玉晶.基于禁忌搜索算法的生理信號情感識別研究[D].西南大學，2008，05.

[50]J.A. Hageman et. al.， "Hybrid genetic algorithm-tabu search approach for? optimising multilayer optical coatings"， Analytica Chimica Acta， 490， 2003，211-222.

[51]柯坷，張世英.禁忌一遞階遺傳算法研究[J].控制與決策，2001，16（4）：480-483.

[52]孫艷豐，鄭加齊.GATS混合算法及其收斂性研究[J].鐵道學報，22（2）：94-98.

[53]李大衛，王莉，王夢光.遺傳算法與禁忌搜索算法的混合策略[J].系統工程學報，1998，13（3）：28-34.

[54]王超.基于混合遺傳禁忌搜索算法的多目標柔性作業車間調度問題研究[D].重慶大學，2012.

[55]蘭任.基于并行混合粒子群算法的蛋白質結構預測[D].大連理工大學，2011.

[56]袁曾.人工神經元網絡及其應用[M].北京：清華大學出版社，1999，10.

[57]曾顯峰.基于人工神經網絡的入侵檢測技術研究[D].廣州市：華南理工大學，2010.

[58]張雨濃.人工神經網絡的面向對象軟件實現[D].廣州：華南理工大學，1999.

[59]劉品.BP神經網絡結構優化研究及應用[D].中國地質大學，2017，02.

[60]王和杰.基于遺傳算法優化的BP神經網絡的汽車油耗計算模型[D].江蘇科技大學，2017.

[61]劉品.BP神經網絡結構優化研究及應用[D].中國地質大學，2017.

[62]Gambardella L M， Dorigo M.Ant-Q： a reinforcement learning approach to the traveling salesman problem.Proceedings of the 12th International Conference on Machine Learning， 1995： 252-260.

[63]Stutzle T，Hoos H.The MAX-MIN ant system and local search for the traveling salesmanproblem.Proceedings of the IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference，1997：309-314.

[64]徐精明，曹先彬，王煦法.多態蟻群算法[J].中國科學技術大學學報，2005，35（l）：59-65.

[65]李擎，張超，陳鵬.一種基于粒子群參數優化的改進蟻群算法[J].控制與決策，2013，28（6）：873-878.

[66]Holland J.H. Outline for a logical theory of adaptive systems[J]. Journal of the Association for Computing Machinery，1962，9（3）：297-314.

[67]王璇.遺傳算法的改進及其應用研究[D].華北電力大學，2010.

[68]Yang Junan， Zhuang Zhenquan. Research of Quantum Genetic Algorithm and Its Application in Blind Source Separation.

[69]田欣.基于改進遺傳算法的移動機器人路徑規劃研究[D].鄭州大學，2016.

[70]Kenndy J， Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. 1995， 4： 1942-1948.

[71]J.Kennedy and R.C. Eberhart. A Discrete Binary Version of the Particle Swarm Algorithm. In Proceedings of the Conference on Systems， Man，and Cybernetics，1997：4104-4109.

[72]Xiao-Fen Xie， Wen-Jun Zhang， Zhi-Lian Yang. A Dissipative Particle Swarm Optimization.? Congress? on? Evolutionary Computation.2002：1456-1461.