移動機器人路徑規劃算法的研究綜述

林韓熙，向 丹，歐陽劍，蘭曉東

1.廣東技術師范大學 自動化學院，廣州510665

2.廣東技術師范大學 廣東工業實訓中心，廣州510665

隨著科技的進步和社會的發展，移動機器人智能化和自動化的水平逐步提高，已經逐漸滲透到日常的生活中。移動機器人在工業和日常居家中都能出色地完成任務，減少人們的勞動負擔。移動機器人需要在工作場景中規劃出一條從初始位置到目標位置的路徑[1-2]，該路徑應滿足路徑短、高效能、安全性高等一系列要求，并且必須能夠避開沿途的靜態和動態障礙物[3]。同時移動機器人應具備一定的計算能力來實時計算最短和最安全的路線，以節省時間和儲備能量。良好的移動機器人路徑規劃技術不僅可以節省大量的時間，還可以減少移動機器人的磨損和資本投資。由于移動機器人的路徑規劃具有重要的應用價值，已成為國內外的研究熱點[4]。

本文對移動機器人路徑規劃問題進行系統性的總結，根據移動機器人路徑規劃的特點，將其劃分為智能搜索算法、基于人工智能算法、基于幾何模型算法和基于局部避障算法。隨后對路徑規劃算法進行細分，從算法本身的特點出發，對算法的模型和基本原理進行解析，并指出每類算法在應用上的局限性；在此基礎上，闡述各類算法的優缺點，對路徑規劃算法的發展具有重要意義。

移動機器人路徑規劃算法圖如圖1所示。

圖1 路徑規劃算法分類圖Fig.1 Classification diagram of path planning algorithm

1 智能搜索算法

智能搜索算法通過隨機生成的初始解或采樣點，經多次迭代來逼近最優的解。該類算法的最大特性是具有隨機性，因而其解不具備唯一性。

1.1 啟發型智能搜索法

啟發型智能搜索法是相對于最優化算法提出的。路徑規劃中存在很多NP-hard問題，每一個問題都有最優解，但不一定能求解出來。因此，啟發型智能搜索算法通過隨機的可行初始解出發以及迭代改進的策略，去逼近最優路徑。現階段，啟發型智能搜索法以仿自然體算法為主，主要有蟻群算法（Ant Colony Optimization，ACO）、粒子群算法（Particle Swarm Optimization，PSO）、遺傳算法（Genetic Algorithm，GA）等。

1.1.1 蟻群算法

ACO算法是意大利學者Dorigol[5]在1992年提出的正反饋機制算法，其中信息素集中的路徑對搜索下一個節點具有啟發式影響。通常螞蟻往信息素高的地方移動。在單移動機器人的靜態環境中得到廣泛應用。螞蟻覓食示意圖如圖2所示。

圖2 螞蟻覓食示意圖Fig.2 Schematic diagram of ants foraging

ACO算法進行路徑規劃時有很強的魯棒性，但容易陷入局部最優點。為了解決該問題，不少研究者對算法的信息素濃度進行改進。Liu等[6]針對ACO算法容易陷入局部最優和搜索效率低下的問題，提出一種自適應搜索步長和信息素揮發策略的改進算法。實驗結果表明，該方法收斂后的最小迭代次數分別比傳統的ACO算法降低了43.97%和59.25%。并且在此基礎上提出一種負載均衡策略的方法來解決多機器人路徑沖突的問題。然而該方法沒有解決規劃的路線穿過相接障礙物的邊角問題，無法在實際得到應用。Dai等[7]提出一種改進的ACO算法。仿真實驗表明，與傳統的蟻群算法相比，改進的蟻群算法迭代次數減少了65%以上，彎曲抑制次數減少了41%。進而證明改進的算法更有效和快速性。

不少研究者對ACO算法進行優化處理。楊洋等[8]針對多AGV避障路徑優化問題，提出一種改進ACO算法和彈性時間窗相結合的多AGV避障路徑優化策略。實驗結果表明，該方法能在無人倉庫中實現多AGV快速規劃的同時找到最優的避障路徑。Ajeil等[3]針對靜態環境下尋優的問題，提出一種衰老的螞蟻蟻群優化算法并且與GA算法、PSO算法作比較。實驗結果表明，該方法在不同模型中規劃的路徑長度相比于GA算法、PSO算法平均降低了18%和17%。

1.1.2 粒子群算法

PSO算法是模仿鳥類尋找食物的行為，當鳥群尋找食物時，會共享各自當前位置的信息。通過個體與群體成員的適當交流，整個鳥群都能達到最終的食物源。其基本原理是個體與群體協作和信息共享，從而獲得最優解。它由Eberhart和Kennedy[9]在1995年提出，是一個以當前搜索到的最優值來尋找全局最優值的算法。它不僅能夠進行單機器人規劃，也適用于多機器人的路徑規劃。

目前研究者主要關注PSO算法關鍵參數的改進和模型的變化。Song[10]針對PSO算法生成的路徑不平滑而造成不必要的轉彎問題，提出一種機器人路徑平滑策略。該策略是在PSO算法的基礎上引入使用自適應分數階速度來提高搜索空間的能力，并通過使用高次貝塞爾曲線增加移動機器人路徑的“平滑性”。實驗結果表明，與幾種標準PSO算法在一些基準函數上的比較，驗證了改進PSO算法的優越性，并通過若干移動機器人平滑路徑規劃的綜合仿真實驗，驗證了新策略的優越性。羅陽陽等[11]針對PSO算法能快速收斂但是容易陷入局部最優的問題，設計了一種突變算子來提高全局尋優能力。實驗結果表明，改進后的PSO算法比原來算法的收斂速度提高了約13.3%和路徑長度降低了6.5%。但是路徑趨于收斂的迭代次數卻大幅度增加。Ma等[12]針對動態雙層倉庫多移動機器人的路徑規劃問題，提出一種改進的方法，該方法將雙重倉庫下機器人最短路徑問題轉變為時變非線性規劃問題來降低難度。仿真結果表明，該方法能夠成功地解決雙倉庫環境下多移動機器人路徑規劃問題。

通過文獻研究可知，粒子群算法的收斂性理論、參數設置等方面都缺乏嚴格的數學證明，其應用大多數是依靠經驗和實驗。改進后的PSO算法能迅速收斂，但新隨機產生的粒子依舊存在陷入局部最優點的可能性。只有合理地設置參數，才能避免該問題。同時，不同的粒子群拓撲結構是對不同社會的模擬，有其不同的適用范圍，應針對不同問題的特點來設計相應的算法和改進策略。

1.1.3 遺傳算法

遺傳算法由美國的Bremermann[13]于1960年提出，它是一種通過模擬生物朝著更加“適應”方向發展的搜索最優解方法。它利用遺傳算子進行選擇、交叉和變異來模擬進化，產生適合環境的新種群。該算法廣泛應用于單機器人的場景。遺傳算法工作原理圖如圖3所示。

圖3 遺傳算法工作原理圖Fig.3 Genetic algorithm working principle diagram

不少研究者利用GA算法對移動機器人路徑進行規劃。徐力等[14]針對現有遺傳算法機器人規劃易陷入局部最優點的問題，提出一種改進的方法。該方法通過改變遺傳算子的交叉概率和變異概率來提高算法尋優能力。實驗結果表明，改進后的算法在路徑長度、收斂時間都優于現有算法。而徐夢穎等[15]針對傳統遺傳算法在搜索最短路徑容易陷入局部最優的問題，提出一種免疫克隆自適應遺傳算法，該算法結合了免疫克隆算子、自適應算子從而提高解的質量，提高收斂速度。仿真實驗表明，此方法相比較PSO算法和模擬退火算法，在靜態障礙物環境中能夠快速地規劃出更短路徑，提高規劃效率。Qu等[16]針對GA算法收斂性差，忽視種群間合作的缺點，提出了一種新的遺傳修改算子。改進后的算法能更好地避開局部最優問題，并擁有更快的收斂速度。其次，針對到多機器人合作的問題，提出利用協同進化機制來實現多機器人無碰撞避障規劃。最后，通過實驗結果證明該算法的有效性。Chen等[17]針對已知環境中輪式移動機器人路徑規劃問題，提出了一種輪式移動機器人的路徑跟蹤方法。實驗結果表明，機器人在有障礙物的環境中能夠穩定移動。Nazarahari等[18]針對GA算法受到環境柵格化大小影響、初始解多次迭代尋不到最優解等問題，提出連續環境下多個移動機器人路徑規劃的混合方法。實驗結果表明，該算法不僅確定了無碰撞路徑，還找到所有機器人接近最優解。

啟發型智能搜索法能夠在已知環境中快速規劃出全局較優的可行路徑。其中，ACO的信息素、PSO的信息共享和GA算法的遺傳變異都帶有隨機性，使得移動機器人能更好適應全局環境。但研究者大多數時候沒有考慮碰撞的可能性，規劃的路徑經常貼近障礙物的邊角，在現實應用中算法需要加入遠離障礙物的目標函數，既要路徑最短，又要考慮運行安全性。同時，啟發型智能搜索法在規劃過程需要認真考慮具體參數之間的關系才能得到最優解。

1.2 隨機型智能搜索法

隨機型智能搜索算法已被證明在實踐中運行良好，并具有理論上的保證，例如概率完整性[19]。它不需要對環境具體建模，就能在環境中隨機探索合適的路徑點，實時調節最優策略得到可行解。但該路徑不一定是平滑的，需要進行優化處理，從而實現移動機器人平滑運動。

概率路線圖（Probabilistic Roadmaps，PRM）和快速探索隨機樹（Rapidly-exploring Random Tree，RRT）算法及其變化是一些最常用的算法。

1.2.1 快速搜索隨機樹算法

RRT算法從起始點開始，通過隨機生成樹的方法建立，將生成的樹與起始點的樹干連接起來，構成一棵搜索樹，直到樹的枝葉與目標點相連。該算法常用于單移動機器人的靜態路徑規劃中。RRT算法工作原理圖如圖4所示。

圖4 RRT算法工作原理圖Fig.4 RRT algorithm working principle diagram

不少研究者對RRT及其變體在路徑規劃的應用進行研究。陳敏等[20]針對RRT算法存在搜索效率低等問題，提出一種改進學習方法。將最短路徑作為距離度量引入RRT算法，加快規劃速度和縮短路徑距離。實驗結果表明，該方法縮短了規劃時間和路徑長度。朱冰等[21]針對RRT和RRT*算法容易陷入局部最優解和效率低等問題，提出了基于安全場的改進RRT*算法。實驗結果表明，該改進算法與傳統RRT*算法相比，降低了迭代次數和搜索時間，但是路徑長度顯著增加。Li等[22]針對RRT算法收斂速度慢在實際應用中導致效率低下的問題，提出一種結合了P-RRT*和Quick-RRT*優勢的PQRRT*混合算法，實驗結果表明，該算法的有效性。為了提高路徑規劃的質量，Wang等[23]提出了一種雙向快速探索隨機樹（KB-RRT*）方法。該方法保留了雙向搜索的優勢，以節省計算資源，以及高效分支修剪策略的優勢，從而生成更短的路徑。仿真實驗表明，KB-RRT*在路徑長度上表現更好，與K-RRT、K-RRT*和KB-RRT相比，在迭代次數和節點數量上實現比較性能。王樂樂等[24]針對多機器人規劃需要考慮協同避障、對空間建模等問題，提出一種改進RRT算法，該算法可以實現機器人編隊一致的規劃和避障。實驗結果表明，該方法能夠實現多個機器人路徑規劃的同時動態改變編隊朝向。Zhang等[25]針對RRT算法搜索樹方向隨機性較高和步長不靈活等問題，提出自適應混合動態步長與目標引力的路徑規劃算法。與基本的RRT算法相比，該方法提高了通過狹窄通道的能力以及開放區域的前進速度。仿真實驗表明：與傳統RRT、DS-RRT、TAF-RRT和DSTAFRRT算法相比，平均路徑長度和平均分支數都是最優的。

1.2.2 概率路圖法

PRM算法是Kavraki和Svestka[26]在1996年提出的算法，它是基于空白空間和障礙物空間的給定地圖內構成的可能路徑的網絡圖。這種方法能用相對少的隨機采樣點來找到一個解。但當采樣點太少，或者分布不合理時，算法可能找不到解。該方法不僅能應用于單機器人的路徑規劃，也可以進行多機器人規劃。PRM算法工作示意圖如圖5所示。

圖5 PRM算法工作示意圖Fig.5 PRM algorithm working diagram

周相坡等[27]提出遠離障礙物的改進采樣PRM方法。實驗結果表明，該方法提高移動機器人的安全性，但卻增加了路徑長度和消耗時間。Mohanta等[28]提出了一種新的概率路線圖模糊控制系統，使得移動機器人到達尖銳的拐點處能平滑轉彎。仿真結果表明，該方法縮短了5%以上的規劃長度，同時不僅能夠在存在復雜的障礙物的環境中找到最優的移動路徑，而且保證移動機器人在轉彎路口平滑轉彎。劉洋等[29]針對PRM算法存在處理窄通道時效果差的問題，提出一種改進的PRM算法。實驗結果表明，該方法提高了規劃效率，同時在突發威脅的情況下也有較好表現。Ravankar[30]針對PRM算法在復雜環境中計算成本高、實時性能差的問題，提出一種改進的基于采樣的移動機器人導航算法。實驗結果表明，無論在全局環境還是局部環境，規劃成功率都在95%以上。

綜上可知，隨機型智能搜索算法的共同點在于建立采樣點進行路徑規劃，優勢在于對障礙物建模簡單，能快速對高維空間進行規劃處理，并根據采集到的信息進行調整。但由于隨機性太強，規劃出的路徑往往不是最優解，實際應用中需要進行二次優化處理，規劃速度因此相對較慢，常用于起點和終點建立一條單向路徑。

2 基于人工智能算法

人工智能路徑規劃是讓移動機器人從環境中自主學習，并預測出可行路徑，以實現移動機器人自主規劃出最優路徑。

2.1 Q-Learning算法

Q-learning是一種在線學習算法，是目前強化學習中最有效的路徑規劃算法[31]。其基本原理是移動機器人通過與環境的交互，對移動機器人動作做出獎勵和懲罰，進而學習找到合適的路徑。

不少研究者利用Q-learning對移動機器人進行路徑規劃。Soong等[32]針對Q-learning向最優解收斂的速度很慢的問題，提出一種改進的Q-learning算法。其中利用花授粉算法改進Q-learning的初始化。實驗結果表明，適當初始化Q值可以加快Q-learning的收斂速度。此外，在一個三輪移動機器人的實際實驗中驗證了該算法的有效性。Bae等[33]針對由實際任務引起的多個機器人無沖突路徑規劃的問題，提出了一種基于Q-learning與卷積神經網絡（Convolution Neural Network，CNN）算法相結合的多機器人路徑規劃算法。實驗結果表明，該方法使得多移動機器人在不同的環境下快速規劃出路徑的同時高效地完成任務。Zhao等[34]針對收斂速度慢的問題，提出了基于當前狀態節點最短距離連續更新的經驗記憶學習（EMQL）算法。在規劃時間、迭代次數和路徑長度等方面的對比結果表明，EMQL算法在收斂速度和優化能力方面優于Q-learning算法。此外，在Turtlebot3機器人的實際實驗中驗證了所提算法的實用性。

2.2 深度學習

相比于其他全局的路徑規劃算法，深度學習是通過學習路徑規劃樣本的內在規律，讓移動機器人自主學習并規劃出可行移動路徑，適用于擁有大量訓練樣本下的機器人動態避障的場景。這是路徑規劃的重點關注方向之一。

不少學者嘗試將深度學習應用在移動機器人中。YU等[35]針對具有安全約束條件的車輛，提出一種基于深度學習的端到端路徑規劃算法。仿真結果表明，所提出的規劃算法能夠成功地實現月球車端到端的路徑規劃，且所生成的路徑與經典路徑規劃算法相比具有更高的安全性保證。針對將深度學習應用到移動機器人中的問題，Gao等[36]提出一種新的訓練增量模式。同時，在這個增量模式的基礎上提出將深度學習算法雙延遲深度確定性策略梯度與概率路線圖相結合的融合算法。實驗結果表明，該模式有效提高了開發效率，而該算法提高了模式的泛化能力。

3 基于幾何模型算法

幾何模型路徑規劃是在已知環境的基礎上構建幾何模型，再選擇合適的路徑，實時調節基于最優策略得到的可行解。該方法得到的路徑都是非光滑路徑，因此需要進行優化，實現移動機器人平滑拐彎。

3.1 A*算法

在全局網絡中，A*（A-Star）算法會依據擴展節點選擇當前“代價”最低的方塊進行下一步搜索，直到搜索到終點，從而規劃出成本最低的路徑。該方法廣泛應用于單機器人的全局靜態環境中。其中，A*算法的估價函數可表示為：

f(n)=g(n)+h(n) （1）這里，f(n)是關于目的地n的估價函數，g(n)是“當前代價”，即起點到目的地n的最短路徑值；h(n)是“預估代價”，即當前移動機器人位置到目的地n的最優路經的啟發值。

張新艷等[37]針對傳統A*算法存在全局優化能力不足的問題，綜合考慮路徑代價、電量及系統效率等因素，提出引入時間因子的改進A*算法以尋找轉彎次數少的路徑方案。其次，結合時間窗與優先級策略解決了多AGV的碰撞沖突問題。實驗結果表明，該方法與ACO算法和RRT算法相比，三臺AGV在倉庫模型下能實現無碰撞路徑規劃，并且路徑長度和規劃時間均有優勢，同時AGV總利用率達到89.1%。劉子豪等[38]針對A*算法進行路徑規劃存在過多的冗余點和拐點的問題，提出跳躍點搜索理論和反向搜索策略相結合的改進A*算法。該算法剔除不需要的節點，減少運算時間。并在拐點處進行優化處理，得到更加平滑的路徑。實驗結果表明，與傳統A*算法相比，運算時間平均為原來的56.09%，路徑長度降低為原來的97.94%。

3.2 Voronoi圖

Voronoi圖是用于機器人移動全局路徑規劃的一種路線圖算法。該方法將目標區域劃分為若干子區域，所有的邊界線都是利用障礙物邊界上相鄰兩點的等距點構造的。移動機器人沿著子區域邊界線移動，規劃出一條從起始點到目標點的路徑。。

不少研究者利用Voronoi圖對移動機器人路徑進行規劃。Ayawli等[39]針對移動機器人在復雜動態環境下的路徑規劃問題，提出了一種Voronoi圖路徑規劃算法。仿真實驗結果表明，該方法可以有效地確定碰撞威脅移動障礙物，避免不必要的重新規劃計算。Hu等[40]針對動態未知環境的多移動機器人問題，提出了一種基于Voronoi分區的多移動機器人協同探索策略和深度強化學習的無碰撞算法。動態Voronoi分區減少了多個機器人重復探索區域。實驗結果表明，與傳統方法相比，該策略降低了任務完成的總體時間和能量消耗，且驗證了無碰撞算法的有效性。

4 用于局部避障算法

用于局部避障算法的目的是為了增強移動機器人的避障能力，提高安全性。讓移動機器人遠離障礙物，規劃出一條安全的無碰撞路徑。

4.1 人工勢場法

Khatib[41]在1986年提出人工勢場法（Artificial Potential Fifield approach，APF），用于實時避障。人工勢場法是目標位置對機器人存在“吸引力”；障礙物對機器人存在“排斥力”；最后通過作用在機器人本身的合力來改變機器人運行方向。人工勢場算法結構簡單，能夠實時規避障礙物，在單機器人局部避障路徑規劃中得到廣泛應用。人工勢場示意圖如圖6所示。

圖6 人工勢場示意圖Fig.6 Schematic diagram of artificial potential field

不少研究者對APF算法進行研究和實際應用。王迪等[42]針對路徑過長、APF存在局部極小點等問題，提出一種模糊勢場方法。該方法將虛擬目標點和有限狀態機相結合來適應多種復雜的環境。實驗結果表明：該方法能夠使機器人快速逃離局部最優點的同時縮短路徑長度。李軍等[43]針對道路勢場不完善的問題，提出一種改進的人工勢場模型。研究結果表明，改進的人工勢場滿足動力學約束，且保證行駛的穩定性。針對三維空間無人機與地面目標協同合作的問題，Jayaweera等[44]提出了一種與跟蹤目標保持距離的動態人工勢場路徑規劃技術。該方法能夠避開無人機飛行軌跡上障礙物，緊緊跟蹤目標；仿真結果證明，該算法的性能優于傳統的APF算法，并能有效實現對目標的跟蹤。Liu等[45]針對機器人難以適應不同速度和不同障礙物下路徑規劃的問題，提出了一種雙勢場融合自適應路徑規劃系統。仿真結果表明，該方法具有良好的規劃性能。該方法為無人機和移動機器人路徑規劃提供一種思路。

4.2 動態窗口法

動態窗口方法（Dynamic Window Approach，DWA）是一種在當前時刻對周圍進行采樣，獲取得下一時刻的機器人動作狀態的方法。該方法可以快速到達目標點，同時避免在搜索空間中機器人與障礙物發生碰撞。但它高度依賴于全局參數，容易在未知環境中失敗。機器人動態窗口示意圖如圖7所示。

圖7 動態窗口示意圖Fig.7 Schematic diagram of dynamic window

Chang等[46]針對DWA評價函數不足的問題，提出了一種基于Q學習的改進DWA算法。該算法在原來DWA算法基礎上對評價函數進行修改和擴展，同時增加了兩個評估函數來提高導航性能。實驗結果表明，該方法在復雜的未知環境下顯示了較高的導航效率和成功率。Kiss[47]針對大多數規劃時將機器人視為一個單點，而導致無法通過窄帶的問題，提出了一種基于模型預測控制的無加權目標函數的全局動態窗口導航方案。Henkel[48]針對導航過程中的能耗問題，提出了一種適用于動態環境下全向移動機器人導航的高效局部路徑規劃器。實驗結果表明，與DWA算法相比，能耗降低了9.79%。

用于局部避障算法能快速求解出遠離障礙物的可行路徑，它們具有實時性高、簡單的特點。在實際應用中，人工勢場法需要根據場景進行合理的勢場函數設定。DWA算法由運動學動力方程推到出的，考慮了機器人慣性問題，可以在雜亂的環境以較快的速度運行。通常情況下，它們常與其他算法配合使用，提高算法的性能。

5 多算法融合

實際應用中，機器人經常在規劃過程中會出現未知障礙物等突發情況，這可能造成機器人碰撞，于是許多學者將局部避障算法強有力地避障能力和其他算法相融合，提高了機器人的避障能力。Wu等[49]針對動態路徑導航問題，提出甲蟲天線搜索算法和人工勢場算法的混合算法。實驗結果驗證了該方法的有效性和優越性。Kashyap等[50]介紹了基于DWA算法和教與學優化融合技術，實驗結果證明，該技術應用在單個和多個仿人機器人的靜態和動態地形中都能成功實行路徑規劃和避障過程。針對經典的A*算法無法應用在動態環境的問題，勞彩蓮等[51-52]提出改進的A*算法與DWA算法相結合的路徑規劃算法。實驗結果表明，改進后算法規劃的路徑更加平滑和高效。王洪斌等[53]在此基礎上對多個目標點成本的大小依次排序進行規劃。實驗結果表明，規劃路徑長度縮短5%，轉折角總度數減少26.62%。但該目標點存在不足之處，只適用于同一方向上的目標點。

不少學者也在考慮將多種算法融合在一起，以提高單一算法的性能。Ali等[54]針對靜態避障特征未知的機器人路徑規劃質量和效率問題，提出了一種改進的算法。該方法首先適用A*算法來輔助提高蟻群算法的優化性能。其次，引入馬爾科夫決策過程模型來降低全局規劃的銳度。實驗結果表明，該算法在不同約束環境下具有有效性。Wu等[55]針對路徑規劃較少考慮車輛擁堵的問題，提出一種基于改進的蟻群算法的動態路徑規劃方法。實驗結果表明，該動態規劃算法有效降低了平均擁塞率。Liang等[56]針對規劃效率低和成本高問題，提出一種GA和蟻群優化算法（ACOA）相結合的混合算法。實驗結果表明，該混合算法能夠獲得機器人最優路徑，節省時間和成本，具有較高的魯棒性。Zhong等[57]針對移動機器人無碰撞跟蹤等問題，提出一種安全A*與自適應DWA算法的混合算法。實驗結果表明，該算法能夠滿足移動機器人復雜環境下的應用需求。曹凱等[58]針對障礙物和采樣點密集等問題，提出一種RRT變體算法。首先，將渦流場約束引入到改進的RRT*算法中，從而引導產生采樣點，再去除一些無效節點，得到一條較優的路徑。實驗結果表明，相對于RRT算法和VAPF-RRT*算法，路徑成本分別降低了21.1%和10.3%，運算時間分別縮短了12.1%和33.1%。但該方法僅限于圓形障礙物，渦流場在三角形和不規則形狀的障礙物的環境中的效果不佳。Qureshi等[59]針對RRT*算法收斂性慢的問題，提出了基于勢函數的RRT*。實驗證明表明，該算法大大減少迭代次數，從而提高內存利用率和加快收斂速度。Wang等[60]針對RRT算法的初始解比較敏感，收斂到最優解緩慢的問題，提出一種基于卷積神經網絡（CNN）的最優算法。該算法利用CNN模型生成非均勻采樣分布，并對大量A*算法的路徑規劃案例進行訓練。預測出給定的任務在地圖上的最優路徑的概率分布，該過程只需要50 ms。仿真結果表明，與傳統算法相比，該算法具有更好的性能。并在最后對未來的路徑規劃工作進行擴展。

無論是規劃精度還是路徑距離、時間長短等，融合算法規劃路徑的效果都比單一的算法有所提高。它具有收斂性強、快速求可行解等特點，同時降低了陷入局部最優解的概率，提高了解的質量。雖然融合算法有效提升單一算法的求解能力，但是算法的復雜程度和計算成本也隨之增加。同時，即使融合算法也存在一定的改進空間，其難以同時滿足能量最小、時間最優等最優準則。各種算法原理只是一個基礎，需要研究者根據環境模型在多種算法中找出適合的算法來結合，以便解決實際問題。

6 討論

本文對各種算法進行簡要歸納，列舉相關的算法的機制、改進措辭、分析存在的優缺點以及適用場景，結果如表1所示。

表1 主流路徑規劃算法匯總表Table 1 Summary table of mainstream path planning algorithms

現有的路徑規劃算法都能成熟應用在移動機器人之中。在實際應用中，單移動機器人路徑規劃模型難以模擬現實多變的情況，多移動機器人路徑規劃更貼近現實。多移動機器人存在協同合作、調度任務等問題，因而需要進行合理的規劃，提高規劃效率和降低能耗。

相比較其他路徑規劃算法，基于機器學習的方法在無人車輛路徑規劃方面有著巨大潛力，但仍需要進一步的研究更加有效的、可靠的路徑規劃方法。如利用攝像頭和激光雷達采集周圍的信息進行數據融合，在使用A*算法最短路徑的基礎上進行避障等決策。實際應用效果有待研究者進一步研究。

同時，不同場景下的算法評價函數有所不同，難以用精確的數學模型表示。在已知的應用中，都是將障礙物近似等效為圓形、矩形等，再對環境進行路徑規劃，在實際應用的泛化能力還有待試驗。

7 總結

本文主要闡述了智能搜索算法、基于人工智能算法、基于幾何模型算法和用于局部避障算法用于規劃路徑的方法，并介紹這些方法的優點、局限性以及適用場景。最后對路徑規劃技術提出以下展望。

（1）更高效的路徑規劃算法融合

目前，移動機器人路徑規劃的研究已相對成熟，能應用于實際生活中，但每種算法都有其優缺點，僅單一的算法無法同時滿足路徑短、實時性強和安全性高等要求，而多種算法融合可以取長補短，彌補各自算法的不足之處，提高算法的性能。如利用神經網絡對PRM算法的采樣點學習和預測，生成有利于最優解的采樣點，減少無效采樣點的產生，最終加快算法的收斂速度。因此，更高效的融合路徑規劃算法也是未來路徑規劃的重點研究對象。

（2）擴展算法的應用范圍

除了隨機型智能搜索算法，其他算法應用于高維空間中的路徑規劃效果較差，如何將算法有效運用在不同的場合需要深入研究。如在三維空間中，以起始點和終點的直線，尋找以當前目標點為單位圓與直線相交點為下一個目標點，再判斷是否經過障礙物進行規劃。此外，當前機器人路徑規劃研究大多是基于理想環境，未來算法的重要研究內容需要考慮極端環境下路徑規劃效率。

（3）網絡協同、物聯網等新一代信息技術結合傳統路徑規劃的應用

現階段，無人駕駛汽車在運行時需要實時處理多個傳感器采集到的大量數據，這要求無人駕駛汽車配備高速的計算模塊。而網絡協同、物聯網等技術能夠很好地解決該問題的同時節省成本和減小體積。該方法將傳感器采集的信息通過5G模塊傳輸到物聯網的云服務器，利用云服務器將高精地圖和大量數據相結合，在此基礎上采用RRT算法規劃出一條安全的無碰撞路徑，再將規劃結果回傳給移動機器人，并讓其運行。相對于無人駕駛汽車本身計算模塊來說，提高了規劃速度與效率。但目前存有一定的局限性。如大規模的傳輸數據信息容易丟失、信號不好導致實時時間延時等，因而解決網絡協同、物聯網等新一代信息技術結合傳統路徑規劃的應用是一種重要的研究方向。

（4）多傳感器信息融合對路徑規劃和避障的影響

多傳感器信息融合技術是提高移動機器人系統感知能力的有效方法，是移動機器人規劃與控制決策的基礎。移動機器人通過激光雷達、攝像頭、GPS傳感器等傳感器來采集周圍環境的信息來進行地圖建模和識別障礙物，再規劃出可行路徑。在這個過程中，需要將各個傳感器采集的信息換算到同一個坐標系下進行有效整合，目的是將數據的冗余信息為數據信息的可靠分析提供依據，從而提高準確率；還需要對比數據并自動排除錯誤的數據信息。因此，準確地處理和分析不同傳感器采集到的信息，構建并提高地圖的精度；這有利于移動機器人實現A*算法、GA算法等路徑規劃。