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

1.廣東技術(shù)師范大學(xué) 自動化學(xué)院，廣州510665

2.廣東技術(shù)師范大學(xué) 廣東工業(yè)實(shí)訓(xùn)中心，廣州510665

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

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

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

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

1 智能搜索算法

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

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

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

1.1.1 蟻群算法

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

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

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

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

1.1.2 粒子群算法

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

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

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

1.1.3 遺傳算法

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

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

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

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

1.2 隨機(jī)型智能搜索法

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

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

1.2.1 快速搜索隨機(jī)樹算法

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

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

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

1.2.2 概率路圖法

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

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

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

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

2 基于人工智能算法

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

2.1 Q-Learning算法

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

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

2.2 深度學(xué)習(xí)

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

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

3 基于幾何模型算法

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

3.1 A*算法

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

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

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

3.2 Voronoi圖

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

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

4 用于局部避障算法

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

4.1 人工勢場法

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

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

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

4.2 動態(tài)窗口法

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

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

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

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

5 多算法融合

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

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

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

6 討論

本文對各種算法進(jìn)行簡要?dú)w納，列舉相關(guān)的算法的機(jī)制、改進(jìn)措辭、分析存在的優(yōu)缺點(diǎn)以及適用場景，結(jié)果如表1所示。

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

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

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

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

7 總結(jié)

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

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

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

（2）擴(kuò)展算法的應(yīng)用范圍

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

（3）網(wǎng)絡(luò)協(xié)同、物聯(lián)網(wǎng)等新一代信息技術(shù)結(jié)合傳統(tǒng)路徑規(guī)劃的應(yīng)用

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

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

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