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

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

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

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

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

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

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

1 智能搜索算法

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

1.1 啟發(fā)型智能搜索法

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

1.1.1 蟻群算法

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

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

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

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

1.1.2 粒子群算法

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

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

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

1.1.3 遺傳算法

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

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

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

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

1.2 隨機型智能搜索法

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

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

1.2.1 快速搜索隨機樹算法

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

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

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

1.2.2 概率路圖法

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

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

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

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

2 基于人工智能算法

人工智能路徑規(guī)劃是讓移動機器人從環(huán)境中自主學習，并預測出可行路徑，以實現移動機器人自主規(guī)劃出最優(yōu)路徑。

2.1 Q-Learning算法

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

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

2.2 深度學習

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

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

3 基于幾何模型算法

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

3.1 A*算法

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

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

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

3.2 Voronoi圖

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

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

4 用于局部避障算法

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

4.1 人工勢場法

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

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

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

4.2 動態(tài)窗口法

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

圖7 動態(tài)窗口示意圖Fig.7 Schematic diagram of dynamic window

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

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

5 多算法融合

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

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

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

6 討論

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

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

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

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

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

7 總結

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

（1）更高效的路徑規(guī)劃算法融合

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

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

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

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

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

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

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