崔 煒，朱發(fā)證

長春理工大學 電子信息工程學院，長春 130022

機器人自主導航一般分為感知、定位、路徑規(guī)劃與控制，而路徑規(guī)劃作為機器人導航的關(guān)鍵技術(shù)也成為了當下的研究熱點。路徑規(guī)劃旨在通過規(guī)劃算法在配置空間中找到從初始位置到目標位置的可行路徑，而不會與任何障礙物發(fā)生碰撞[1]?，F(xiàn)如今已在工業(yè)機器人[2]、仿生機器人[3]、無人車[4]、無人機[5]等領(lǐng)域得到了廣泛應用。良好的路徑規(guī)劃算法可以快速規(guī)劃出最優(yōu)路徑，提高運行效率，減少機器人的磨損[6]。

路徑規(guī)劃算法有多種分類方式，按照是否具有環(huán)境信息的先驗知識分為已知環(huán)境下的全局路徑規(guī)劃算法和未知環(huán)境下的局部路徑規(guī)劃算法[7]。全局規(guī)劃是一種靜態(tài)規(guī)劃，主要為局部路徑規(guī)劃提供導向和約束，局部規(guī)劃是一種動態(tài)規(guī)劃，用于未知環(huán)境中的實時避障。不過這種分類方法僅從實際應用的角度出發(fā)，難以清晰表述算法間的區(qū)別與聯(lián)系。

本文系統(tǒng)總結(jié)了機器人的路徑規(guī)劃算法，將現(xiàn)有的算法劃分為基于圖搜索、基于仿生、基于勢場、基于速度空間和基于采樣的規(guī)劃算法。由于基于采樣的算法一般通過碰撞檢測獲得可行軌跡的節(jié)點信息避免了顯式構(gòu)造配置空間提高了規(guī)劃效率，有效避免了維度災難，日益成為解決路徑規(guī)劃問題最流行的算法，因此本文簡述基于圖搜索、基于仿生、基于勢場和基于速度空間的路徑規(guī)劃算法，而重點分析基于采樣的路徑規(guī)劃算法并將其分為單查詢算法和多查詢算法，即快速擴展樹類和概率路線圖類。

1 基于圖搜索的算法

基于圖搜索的算法是遍歷的確定性搜索方法，通常用于維度較低的空間，如二維空間，一般將地圖離散成柵格圖后利用搜索策略以盡可能小的代價找到路徑，但是這類算法的性能取決于所選的地圖分辨率大小。如果分辨率太小，則可能找不到合適的路徑，如果分辨率太大，則可能需要耗費很長時間[8]。并且隨著地圖規(guī)模的增大，它們的搜索性能也會越來越差。該類算法主要用于在靜態(tài)地圖中求解最短路徑，其搜索過程直觀，是解決環(huán)境已知時的全局路徑搜索問題的算法[9]。

（1）Dijkstra算法[10]是一種廣度優(yōu)先搜索算法（breadthfirst search，BFS），雖然能夠獲得到達終點最短的路徑，但是運算量大，規(guī)劃效率很低。

（2）A*算法由Hart等[11]于1968年發(fā)表，是一種常用的路徑查找和圖形遍歷算法。它融合了Dijkstra算法和啟發(fā)函數(shù)，搜索權(quán)值函數(shù)如式（1）：

其中，g(n)是節(jié)點n距離起點的代價，h(n)是節(jié)點n到達終點的預估代價，即啟發(fā)函數(shù)。

A*算法不僅利用啟發(fā)函數(shù)提高了路徑搜索的效率，還能在給定相同信息的情況下，保證不會比任何其他最優(yōu)算法擴展更多的狀態(tài)（即它是最有效的）。但是實時性差，隨著地圖的增大或維數(shù)的增加，規(guī)劃時間也成倍數(shù)地增長。

（3）A*的各種改進算法如圖1所示，其中，Li等[12]提出的一種改進的雙向A*（bidirectional A*）算法在A*算法的基礎(chǔ)上引入了雙向交替搜索策略，即分別從起點和終點開始搜索，直到路徑相遇，提高了算法的搜索效率。Likhachev等[13]提出的ARA*（anytime repairing A*）算法是A*算法的anytime變體，先快速規(guī)劃出一條初始路徑，然后在時間允許的范圍內(nèi)不斷優(yōu)化這條路徑。Stentz等[14]提出的D*算法是A*算法的動態(tài)變體，即從終點開始搜索路徑，當出現(xiàn)新的障礙物時就可以將已有的代價值作為啟發(fā)函數(shù)重新進行規(guī)劃，所以可用于動態(tài)環(huán)境中的路徑規(guī)劃。Koenig 等[15]提出的LPA*（lifelong planning A*）算法是A*算法的增量變體，當環(huán)境發(fā)生變化后就可以利用先前存儲的信息進行增量式搜索，雖然可以應用于動態(tài)環(huán)境，但是不適用于起點和終點變化的情況。如果機器人前進過程中某些節(jié)點發(fā)生變化，則可以使用Koenig等[16]提出的D* Lite算法，該算法在LPA*算法的增量搜索的基礎(chǔ)上添加了反向搜索，不過當?shù)貓D變動過大時可能耗時更長。Likhachev等[17]提出的AD*（anytime dynamic A*）算法也稱Anytime D*算法，結(jié)合了ARA*算法和D*Lite算法的優(yōu)點，適用于動態(tài)環(huán)境中的路徑重規(guī)劃，并且追求有限時間內(nèi)的次優(yōu)路徑。上述改進算法的主要目的是縮短A*的規(guī)劃時間，不過規(guī)劃出的路徑轉(zhuǎn)折點仍較多，需要進行平滑處理。

圖1 A*的各種改進算法Fig.1 Various improved algorithms of A*

基于圖搜索的算法搜索過程簡單直接，多用于機器人的全局路徑規(guī)劃，但是當?shù)貓D精度高時規(guī)劃路徑所需的計算量大且轉(zhuǎn)折點較多。另外，基于圖搜索的算法被不少學者用于計算初始路徑或利用啟發(fā)式思想優(yōu)化其他算法。

2 基于仿生的算法

基于仿生的算法是模擬自然界中生物進化或群體行為的一種路徑規(guī)劃方法，算法原理容易理解，對環(huán)境具有良好的適用性，多用于全局的路徑規(guī)劃。

（1）遺傳算法（genetic algorithm，GA）于1962 年被Holland[18]提出，它主要通過選擇、交叉、變異來模擬生物進化進行搜索，有利于全局搜索。但是其收斂速度慢，且屬于隨機類算法，不能穩(wěn)定地得到最優(yōu)解。徐力等[19]通過加入插入算子與刪除算子對交叉和變異概率進行了自適應調(diào)整。Pehlivanoglu等[20]提出了初始種群的增強方法來加速算法的收斂過程。Hao等[21]提出了一種基于碰撞檢測的自適應遺傳算法解決了路徑質(zhì)量低、收斂所需迭代次數(shù)多的問題。

（2）蟻群（ant colony optimization，ACO）算法于1991年被Dorigo等[22]提出，它是模擬蟻群在自然界中尋找食物的行為特征而形成的一種正反饋機制算法，其關(guān)鍵為狀態(tài)轉(zhuǎn)移和信息素更新。Luo等[23]提出了一種通過差異化分配初始信息素來避免早期盲目搜索的方法，根據(jù)當前最優(yōu)解和迭代次數(shù)計算狀態(tài)轉(zhuǎn)移概率，并引入最優(yōu)解和最差解來改進全局信息素的更新。Miao 等[24]在蟻群算法的轉(zhuǎn)移概率中引入了角度引導因子和障礙物排除因子來縮短規(guī)劃時間。Liu等[25]提出了一種基于概率的隨機游走策略，通過交替使用高斯分布和柯西分布來生成隨機游走的步長，而不是僅使用高斯分布來構(gòu)造新的解。

（3）粒子群算法（particle swarm optimization，PSO）于1995年被Kennedy等[26]提出，它是模擬鳥群等種群覓食生存行為提出的一種群優(yōu)化算法，每個個體只有位置和速度兩種屬性。其核心思想是利用集群中的信息共享使群體從無序到有序[27]。Phung 等[5]提出了一種通過球向量優(yōu)化的粒子群算法，通過制定成本函數(shù)將路徑規(guī)劃轉(zhuǎn)換為優(yōu)化問題，重點關(guān)注路徑的安全性和可行性。Yu等[28]通過融合模擬退火算法改進了PSO算法的更新策略，提高了群體的多樣性，避免陷入局部最優(yōu)解。Fernandes 等[29]提出了一種使種群具有多峰值的算法以有效避免局部極小值。

（4）螢火蟲算法（firefly algorithm，F(xiàn)A）于2008 年被Yang[30]提出，它是一種基于螢火蟲閃光特征的隨機的群體智能算法，吸引行為、光強編碼和距離依賴性使FA能夠有效地處理非線性、多峰優(yōu)化等問題[31-32]。Patle 等[33]進行了FA在不確定環(huán)境中移動機器人導航的應用和實現(xiàn)，減少了計算量，避免了螢火蟲的隨機移動。Xu等[34]研究了用于移動機器人路徑規(guī)劃的優(yōu)化FA，優(yōu)化后的高性能算法可以提高移動機器人在路徑規(guī)劃中的計算能力和響應速度。Li等[35]提出了一種基于FA的最優(yōu)路徑規(guī)劃方法，用于自適應種群大小。Zhang 等[36]提出了一種新的基于GA和FA的混合算法，將新的混合算法應用于路徑規(guī)劃可以提高機器人在路徑規(guī)劃中的反應能力和計算能力。

（5）灰狼優(yōu)化（grey wolf optimizer，GWO）算法于2014年被Mirjalili等[37]提出。該算法受到了灰狼捕食獵物活動的啟發(fā)，在本質(zhì)上模擬了灰狼的領(lǐng)導層次和狩獵機制，具有收斂快、參數(shù)少、易實現(xiàn)等特點。Mirjalili等[38]首次提出了一種多目標灰狼優(yōu)化算法（MOGWO），用于多目標問題的優(yōu)化。Gupta等[39]提出了一種基于隨機移動的改進RW-GWO 算法來提高灰狼搜索能力。Nadimi-Shahraki 等[40]提出了一種改進的灰狼優(yōu)化算法（Ⅰ-GWO）以解決種群多樣性不足、早熟收斂等問題。

除了上述算法，國內(nèi)外學者在機器人路徑規(guī)劃中還采用了一些其他優(yōu)化算法，如海洋捕食者算法[41]、搜索與救援優(yōu)化算法[42]。海洋捕食者算法通過模擬海洋生物的捕食行為，利用捕食算子和消除個體聚集算子實現(xiàn)規(guī)劃目的。不過存在前期收斂慢、收斂精度低等缺陷。張貝等[43]提出了融合趨向最優(yōu)的反向?qū)W習策略和信息共享策略的海洋捕食者算法，有效避免了算法陷入局部最優(yōu)，加快了算法的前期搜索速度。搜索與救援優(yōu)化算法通過模擬人類的搜救行為，利用個人階段和社會階段兩個算子進行規(guī)劃。該算法簡單、不易陷入局部最優(yōu)，但是收斂慢且難以自適應地調(diào)整搜索區(qū)域。周文娟等[44]提出了一種基于強化學習改進的搜索與救援優(yōu)化算法，通過訓練強化學習模型使算法具有自適應選擇能力。Zhang等[45]提出了一種啟發(fā)式交叉搜索和救援優(yōu)化算法，保持群體多樣性的同時提高了收斂速度。

基于仿生的算法對環(huán)境的適應性強，常用于全局規(guī)劃，不過易出現(xiàn)迭代次數(shù)多、收斂速度慢、路徑質(zhì)量低等問題。研究新算法或融合算法可以獲得更好的規(guī)劃性能，如獵豹優(yōu)化算法[46]、鯨魚優(yōu)化算法[47-48]、模擬退火算法與自適應大規(guī)模鄰域搜索算法相融合[49]、遺傳算法與螢火蟲算法相融合[36]。

3 基于勢場的算法

基于勢場的算法通過跟蹤由引力部分和斥力部分組成的勢場的最陡下降來找到可行路徑，合力的方向表示期望的運動方向，大小表示期望的速度[50]。其中，引力由終點產(chǎn)生，斥力由障礙物產(chǎn)生，機器人的受力如圖2所示。該算法結(jié)構(gòu)簡單，計算負擔較小，常用于在線規(guī)劃進行實時避障。

圖2 基于勢場的算法示意圖Fig.2 Schematic diagram of potential field-based algorithm

人工勢場法（artificial potential fifield approach，APF）[51]結(jié)構(gòu)簡單，易于計算，不過當引力與斥力相差較大、合力為零或機器人在狹窄通道時易存在目標點不可達和局部極值兩個主要問題。另外，當機器人周圍存在多個障礙物時，可能會導致加速度振蕩，從而出現(xiàn)高能耗問題[52]。為了避免出現(xiàn)人工勢場法的局部極小值問題，Tian等[53]基于已知目標位置和最小安全距離構(gòu)造了一個內(nèi)部無障礙物的虛擬導引管道（virtual guiding pipeline，VGP）來構(gòu)造導向勢場，Sang 等[54]通過切換子目標點來改進算法，Souza 等[55]引入了一個三維渦流場進一步避免震蕩問題，Duhe等[52]也提出了四種排斥場的替代公式來減少由障礙物造成的加速度震蕩現(xiàn)象。

4 基于速度空間的算法

基于速度空間的算法核心思想借鑒了預測控制的相關(guān)原理，是一種移動機器人在線避碰策略。該算法不僅考慮了機器人本身的物理約束，還通過考慮環(huán)境約束和當前速度為機器人規(guī)劃一條合適的路徑，并在出現(xiàn)動態(tài)障礙物時快速采取相應的避障行動[56]。

動態(tài)窗口法（dynamic window approach，DWA）[57]首先根據(jù)機器人的運動學模型和當前速度獲得速度的采樣窗口，然后通過評估函數(shù)評估在窗口內(nèi)生成的所有軌跡，最終找到下一時刻的最佳速度。其中評價函數(shù)通?？紤]障礙物距離、速度和路徑角度三個因素。該方法主要用于移動機器人的自主避障，能夠用于計算機器人達到目標所需的最大無碰撞速度[58]。DWA雖然考慮了多種約束，但是前瞻性不足且易出現(xiàn)局部極值。起初DWA 主要用于靜態(tài)障礙物環(huán)境[57，59]，Ogren 等[59]利用李雅普諾夫函數(shù)框架提出了一種易于處理且收斂的DWA。而當障礙物動態(tài)移動時，DWA 的性能便會下降。為了克服此限制，已經(jīng)開展了大量在動態(tài)障礙環(huán)境中進行避障的研究[60]。Molinos 等[61]提出了采用兩級窗口的DW4DO（dynamic window for dynamic obstacles）算法以解決算法的迭代速度很高或機器人的加速度很低時出現(xiàn)的局部窗口很小的問題。而提出的另一種DW4DOT（dynamic window for dynamic obstacles tree）算法提高了規(guī)劃路徑的優(yōu)化程度，減少了評估的路徑數(shù)量，不過同時增加了計算成本。Lee等[60]提出了FDEDWA（finite distribution estimation-based dynamic window approach），通過FMF（finite memory filtering）估計障礙物的總體分布，并預測未來的動態(tài)障礙物分布，提高了機器人軌跡的最優(yōu)性，同時保持了實時性能，不過還沒有擴展到三維空間。Chang 等[62]通過Q-learning 自適應地學習所提出的DWA 的參數(shù)，并獲得一個經(jīng)過訓練的Agent以適應未知環(huán)境。

5 基于采樣的算法

基于采樣的算法不使用環(huán)境的顯式表示，一般通過碰撞檢測獲得可行軌跡的節(jié)點信息。然后將空間中的無碰撞節(jié)點連接起來形成一個可行軌跡圖（路線圖）。最后，在路線圖中獲得從起點到終點的可行路徑[63]。基于采樣的算法通過采樣避免了顯式構(gòu)造配置空間，建模簡單，成為近年來解決高維規(guī)劃問題最流行的算法，主要分為單查詢算法和多查詢算法?；诓蓸拥乃惴ǖ墓?jié)點擴展步驟如圖3所示。

圖3 基于采樣的算法節(jié)點擴展示意圖Fig.3 Schematic diagram of sampling-based algorithm node expansion

5.1 單查詢算法

單查詢算法通常解決只有一對起點和終點的路徑規(guī)劃問題，常用的例子包括RRT算法[64]與它的漸進最優(yōu)版本RRT*算法[65]、FMT*算法[66]和BⅠT*算法[8，67]等。

RRT（rapidly exploring random tree）算法[64]從起點開始生長一棵樹，以增量方式近似狀態(tài)空間，如果在達到最大迭代次數(shù)時未找到從起點到終點的可行路徑，則該規(guī)劃被視為失敗。而且采取隨機順序搜索策略，使它的搜索效率很低。Wang等[68]提出了一種在動態(tài)環(huán)境中的EB-RRT（elastic band-based rapidly exploring random tree）算法，將EB（elastic band）方法與基于時間的RRT樹相結(jié)合，在優(yōu)化當前軌跡的同時實現(xiàn)實時運動規(guī)劃。不過當動態(tài)障礙物的運動方向突然反轉(zhuǎn)時，該算法難以及時避免碰撞。Chi 等[69]提出了一種基于廣義Voronoi圖的啟發(fā)式路徑規(guī)劃算法，用于生成啟發(fā)式路徑，指導采樣過程，進一步提高運動規(guī)劃效率。然而它只討論了在具有廣泛可行區(qū)域的較不復雜環(huán)境中的性能，對于更加復雜的情況具有不確定性。

RRT*算法[65]擴展了RRT 算法，當添加新節(jié)點時，RRT*算法通過重新選擇父節(jié)點以確保新節(jié)點對應的路徑具有局部最小值，并且在添加新節(jié)點后重新布線以減小路徑代價。該算法在樣本數(shù)接近無窮大時以概率1收斂到最優(yōu)，不過其狀態(tài)空間的全局搜索仍然是隨機的，且由于收斂速度慢和初始路徑代價高，使其規(guī)劃效率較低。曹凱等[70]通過APF引導RRT*解決了在多障礙物等復雜環(huán)境中的收斂慢、采樣點多的問題。Arslan等[71]提出的RRT#算法使用啟發(fā)式在快速搜索隨機樹逐步構(gòu)建的圖中查找和更新樹。Otte 等[72]提出的RRTX算法將重新布線擴展到了動態(tài)環(huán)境，在導航期間使用相同的搜索樹，當檢測到狀態(tài)空間的變化時不斷對其進行優(yōu)化和修復。不過與RRT*和RRT#一樣，它不會對圖本身的構(gòu)造進行排序。Liao 等[73]提出了F-RRT*算法，通過為隨機點創(chuàng)建靠近障礙物的父節(jié)點（不是在現(xiàn)有頂點中選擇）來優(yōu)化路徑成本，生成的初始路徑比RRT*更好，收斂速度更快。

RRT-Connect 算法[74]分別從起點和終點開始生長樹，并使它們的生長既偏向于未探索的空間，又偏向于彼此，會快速得到一個初始路徑，但未探索空間的搜索仍然是由增量采樣隨機排序的，且它不是一個漸進最優(yōu)的算法，無法改進初始路徑。Wang 等[75]提出了一種基于RRT-Connect 搜索的高效路徑規(guī)劃算法，采取“雙向到單向”策略，即當兩棵樹相遇時，后向樹將作為一種啟發(fā)式，引導前向樹不斷向目標狀態(tài)生長，算法將切換到單向搜索模式。因此，避免了連接過程中的兩點邊值問題，大大加快了擴展過程，不過它只是將后向樹用來啟發(fā)前向樹，所以搜索速度低于RRT-Connect算法。

Ⅰnformed RRT*算法[76]改變了傳統(tǒng)算法的采樣方式，在找到第一條路徑之前與RRT*相同，而在找到第一條路徑之后Ⅰnformed RRT*將超橢球啟發(fā)式納入RRT*，減少無用區(qū)域的采樣，加快了收斂速度，同時保留了RRT*的概率完備性和漸進最優(yōu)性。由于Ⅰnformed RRT*使用啟發(fā)式將規(guī)劃問題縮小到的是原始空間的子集，因此它本質(zhì)上依賴于所找到的初始路徑。Wang等[63]提出了一種基于目標偏向采樣和啟發(fā)式優(yōu)化策略的TBⅠT*算法，該算法在尋找初始路徑的搜索階段采用“向日葵”區(qū)域和目標牽引區(qū)域組合的目標偏向采樣策略，引導隨機樹向目標方向快速增長，從而減少冗余節(jié)點的生成，提高算法的搜索效率。搜索初始路徑后，算法將依次選擇路徑中的三個節(jié)點，形成一個超橢球進行路徑優(yōu)化，減少了無用的計算，并提高了算法的收斂能力。不過由于它優(yōu)化的是初始路徑本身，因此對于一些存在狹窄通道的復雜場景可能規(guī)劃不出最優(yōu)路徑。

FMT*（fast marching tree）算法[66]使用惰性碰撞檢測來減少對障礙物碰撞檢查的數(shù)量，使用行進法處理一組樣本，搜索結(jié)果按成本排序，比RRT*算法的收斂速度更快[77]。其近似和搜索的分離使得搜索順序與采樣順序無關(guān)，但很難選擇合適的樣本數(shù)量，當需要較低成本的路徑時，必須增加樣本數(shù)量再重新規(guī)劃，并且在搜索結(jié)束之前，不會給出可行路徑，如果沒有找到合適的路徑，搜索就必須重新開始。Salzman 等[78]提出的MPLB（motion planning using lower bounds）算法是FMT*算法的anytime變體，同時處理多個節(jié)點以有效計算所有節(jié)點的估計成本，并使用下限將RRT*的漸進最優(yōu)放寬到了漸進近似最優(yōu)，不過沒有提出具體的方法來重用信息。Starek 等[79]提出的BFMT*（bidirectional fast marching tree）算法執(zhí)行雙向惰性搜索，當兩棵樹相交或某一節(jié)點在一棵樹的開放集中而不在另一棵樹的開放或未訪問集中時終止搜索。并且該算法保留了概率完備性和漸進最優(yōu)性。Reid等[80]提出的HBFMT*（hierarchical bidirectional fast marching tree）算法是一種分層雙向快速行進樹，將配置空間分解成多個子空間的層次結(jié)構(gòu)，利用雙向搜索快速找到一組通過這樣的子空間的路徑，這個初始路徑用于生成一個有偏采樣分布，然后探索所有空間找到一個路徑。每個子空間由FMT*變體搜索，保留了FMT*的概率完備性和漸進最優(yōu)性，不過其性能依賴最初采樣的子空間和生成的分布。Xu等[81]提出的BBⅠ-FMT*（Batch-to-batch Ⅰnformed Fast Marching Tree）算法是一種anytime算法，利用批量采樣的增量搜索和“懶惰”最優(yōu)搜索快速找到初始路徑后，再通過批量知情采樣的增量搜索快速優(yōu)化樹并獲得最優(yōu)路徑。隨后，Xu 等[82]又提出的ⅠAFMT*（informed anytime fast marching tree）算法使用了一種平衡批量和單次采樣、“非懶惰”和“懶惰”搜索優(yōu)點的策略，即采用混合增量搜索和動態(tài)最優(yōu)搜索?；旌显隽克阉鳂?gòu)建了一個低成本的生成樹，兼顧了批量采樣搜索的效率和單次采樣搜索的靈活性。動態(tài)最優(yōu)搜索考慮了“非惰性”和“惰性”搜索之間的權(quán)衡，以快速改進所生成樹并獲得高質(zhì)量的可行 路 徑。Wang 等[1]提 出 的ⅠABFMT*（informed anytime bi-directional fast marching tree）算法是一種基于漸進最優(yōu)采樣的anytime算法，結(jié)合了BFMT*算法的雙向搜索和ⅠAFMT*算法的anytime的優(yōu)點。ⅠABFMT*算法首先通過雙向“惰性”搜索較少數(shù)量的樣本以有效地找到可行的初始路徑，再通過知情采樣將樣本數(shù)加倍快速改進為最優(yōu)。與ⅠAFMT*相比，ⅠABFMT*只搜索可以優(yōu)化當前路徑的區(qū)域，而不是整個知情集。Wu 等[83]提出的ST-FMT*（secure tunnel fast marching tree）算法由預處理和探索兩部分組成，分別負責建立“安全通道”和優(yōu)化路徑，其中通過障礙物到初始路徑的最小距離建立的“安全通道”有助于采樣的集中。

任何時候，基于采樣的規(guī)劃都可以被視為在問題域中構(gòu)造圖并搜索的算法。一些算法同時進行這種構(gòu)造和搜索（例如RRT*），而另一些算法則單獨進行構(gòu)造和搜索（例如FMT*），但與基于圖搜索的算法一樣，它們的性能始終取決于近似的準確性和搜索的質(zhì)量[8]。

BⅠT*（batch informed tree）算法[8，67]使用RGG（random geometric graph）理論[84]來限制圖的復雜性，以anytime的形式構(gòu)建圖并使用類似于LPA*算法[15，85]的方式進行搜索。anytime 允許BⅠT*無限期運行，直到找到合適的路徑。有序搜索避免了不必要的計算量。增量搜索允許它通過重用以前的信息來有效地更新其不斷增加的批次。Holston 等[86]提出的快速BⅠT*（fast-BⅠT*）算法通過僅按成本進行初始搜索，以降低初始最優(yōu)性為代價來更快地找到初始路徑。一旦找到一條可行路徑，它將使用完整的啟發(fā)式重新排序其隊列，并重新處理所有節(jié)點。雖然保持了幾乎確定的漸進最優(yōu)性，但不必要地重復了以前的搜索工作。Strub等[87]提出的ABⅠT*（advanced batch informed tree）算法利用BⅠT*單個查詢中搜索和近似的分離在基于anytime采樣的近似上使用基于圖形的高級搜索技術(shù)（膨脹和截斷），以進一步提高規(guī)劃性能。通過膨脹其啟發(fā)式來加快初始解時間，類似于ARA*[13]算法，并通過截斷其搜索來平衡探索和近似，類似于截斷LPA*[85]算法。其中，膨脹會使搜索偏向目標，減少規(guī)劃時間，截斷有助于探索狀態(tài)空間的區(qū)域。與BⅠT*使用的增量搜索相比，雖然實現(xiàn)了更快的路徑規(guī)劃，但是犧牲了分辨率的最佳性。Kyaw 等[88]針對存在不規(guī)則障礙物和狹窄通道的復雜環(huán)境，提出了可重構(gòu)機器人的節(jié)能BⅠT*（energy-efficient BⅠT* for reconfigurable robots*，EBⅠTR*）算法，該算法將機器人執(zhí)行器的機械功作為能量成本目標，把搜索重點放在貪婪的知情集上（BⅠT*直接在知情集上采樣），在保持BⅠT*的概率完備性和漸進最優(yōu)性的同時，生成高質(zhì)量、節(jié)能的路徑。Strub等[89-90]提出的AⅠT*（adaptively informed tree）算法是自適應啟發(fā)式的快速漸進最優(yōu)路徑規(guī)劃，建立在BⅠT*的基礎(chǔ)上，使用非對稱雙向搜索來有效地估計和利用每個問題實例的精確啟發(fā)式。正向搜索與BⅠT*算法中的搜索相同，不過使用計算成本更低的反向搜索提供的啟發(fā)式。如圖4（a）所示，BⅠT*采用歐氏距離估算啟發(fā)式成本（虛線）會使其忽略中間的障礙物，而通過使用惰性反向搜索，AⅠT*能夠提供更精確的啟發(fā)式以適應這種場景，如圖4（b）所示。另外，AⅠT*找到初始路徑的速度至少與RRT connect 的速度一樣快。Strub 等[90]提出的EⅠT*（effort informed tree）算法作為AⅠT*的一個擴展，能夠用于優(yōu)化計算成本較高或難以用可接受的先驗成本啟發(fā)式近似的目標，該算法的正向搜索利用反向搜索計算的額外的成本和努力啟發(fā)式，即使沒有可接收的啟發(fā)式，這也會使它能快速的得到初始路徑。

圖4 歐幾里德啟發(fā)式與自適應啟發(fā)式對比圖Fig.4 Comparison diagram of Euclidean heuristic and adaptive heuristic

單查詢算法能夠得到連接一對起點和終點的可行路徑，建模簡單，可以有效解決高維規(guī)劃問題。但是在固定場景中會造成重復性的規(guī)劃，浪費計算資源。

5.2 多查詢算法

許多環(huán)境的底層結(jié)構(gòu)是靜態(tài)的，往往會帶來重復性的規(guī)劃問題[91]。多查詢規(guī)劃算法旨在通過利用這種重復性構(gòu)造一個路線圖減少找到可行路徑所需的計算時間來解決靜態(tài)環(huán)境中的多個不同起點和終點的路徑規(guī)劃問題，常用的例子包括PRM 算法[92]與它的漸進最優(yōu)版本PRM*算法[65]。

PRM（probabilistic roadmaps）算法[92]通過在預處理期間隨機采樣配置空間中的狀態(tài)來構(gòu)建離散化空間的路線圖（保留自由空間中的樣本，丟棄障礙空間中的樣本）。它在預處理階段會驗證路線圖中的所有邊，然后使用此路線圖將單個查詢簡化為路線圖上的圖搜索，從而縮短規(guī)劃時間。如果環(huán)境事先不可用，則需要并行計算可重用信息以解決規(guī)劃問題。而且若采樣點數(shù)過少、鄰域過小，則可能找不到解，若采樣點數(shù)過多、鄰域過大，則會更加耗時。Bohlin 等[93]提出的Lazy PRM 算法通過假設(shè)路線圖中的所有邊和頂點都是有效（無碰撞）地來減少近似階段的成本，然后搜索以找到路徑，接著對這個候選路徑的頂點和邊進行碰撞檢查，如果包含碰撞，則會刪除相應的頂點和邊，并在更新的圖上開始新的搜索。

PRM*、Lazy PRM*算法[94]擴展了PRM 和Lazy PRM 以獲得幾乎確定的漸進最優(yōu)性，但是后續(xù)添加新樣本時并不刪除原有樣本，使得路線圖變得越來越大，會減慢后續(xù)的查詢。Dobson等[95]提出的SPARS算法通過將先前找到的路徑存儲在稀疏圖中來解決圖的無限增長問題，不過稀疏圖的構(gòu)建在計算上是昂貴的，并且可能導致總體上的規(guī)劃時間較慢。Lai 等[96]提出的RRdT*（rapidly-exploring random disjointed-tree*）算法繼承了RRT*的概率完備性和漸進最優(yōu)性，是一種增量式最優(yōu)多查詢規(guī)劃算法，自適應地平衡了規(guī)劃過程中的全局搜索和局部開發(fā)，通過使用多個“獨立樹”來探索空間以有效應對狹窄通道的情況，提高了傳統(tǒng)算法的性能。Lai等[97]通過提議分布的貝葉斯學習改進了RRdT*算法，從過去觀察到的結(jié)果中學習，而不僅僅是丟棄失敗的樣本，最大限度地提高了在狹窄通道內(nèi)具有更高概率形成軌跡的區(qū)域進行采樣的可能性。Hartmann 等[91]提出的EⅠRM*（effort informed roadmaps）算法將EⅠT*擴展到了多查詢算法，通過將近似倒回到第一批樣本來防止高分辨率圖的復雜性對搜索性能產(chǎn)生負面影響，同時使用非對稱雙向搜索識別可能有助于解決單個規(guī)劃的現(xiàn)有路徑以減少計算量，能夠快速找到一條初始可行路徑，后續(xù)再優(yōu)化到最優(yōu)。

多查詢算法通過利用已知的路線圖進行快速規(guī)劃，有效避免了出現(xiàn)重復性的規(guī)劃問題，不過如何利用規(guī)劃成功的路徑信息構(gòu)造路線圖是該類算法的難題，并且與單查詢算法一樣搜索效率受采樣點數(shù)量的影響大。

6 討論

目前國內(nèi)外學者對機器人的路徑規(guī)劃算法進行了應用研究，并取得了大量有價值的研究成果，具有代表性的算法如表1所示。

表1 路徑規(guī)劃代表算法匯總Table 1 Summary of representative algorithms for path planning

基于圖搜索的算法的規(guī)劃效率受限于其精度，精度越高，路徑質(zhì)量越好，但是所需的規(guī)劃時間也越長，且難以找到一個合適的精度，多用于全局路徑規(guī)劃或為其他算法提供初始信息?；诜律乃惴▽Νh(huán)境具有良好的適應性，國內(nèi)外學者通過研究新優(yōu)化算法或與其他算法相融合來提高實際應用效果?；趧輬龊突谒俣瓤臻g的算法雖然簡單、計算負擔較小，但是易出現(xiàn)局部最優(yōu)、震蕩等問題，通常作為局部路徑規(guī)劃算法進行實時避障?；诓蓸拥乃惴ㄋ阉髂芰姡贿^也可能由于無序搜索或不準確的啟發(fā)式而浪費大量的計算資源。另外，單查詢規(guī)劃算法中Ⅰnformed RRT*算法的限制區(qū)域采樣、FMT*算法的惰性碰撞檢測、BⅠT*算法的近似和搜索分離，以及AⅠT*算法的非對稱雙向搜索均有效提升了算法的規(guī)劃性能。而針對一些場景的靜態(tài)底層結(jié)構(gòu)問題，多查詢算法通過構(gòu)造路線圖來避免重復性的路徑規(guī)劃，減小了計算量。

7 結(jié)語

本文主要闡述了基于圖搜索、基于仿生、基于勢場、基于速度空間和基于采樣的路徑規(guī)劃算法，從單查詢算法和多查詢算法等角度重點分析了基于采樣的路徑規(guī)劃算法。從算法的發(fā)展現(xiàn)狀和現(xiàn)實的需求來看，路徑規(guī)劃算法的下一步研究方向主要包括以下五個方面：

（1）狹窄通道環(huán)境中的路徑規(guī)劃

狹窄通道內(nèi)有限的自由空間嚴重限制了算法的性能，如何在存在狹窄通道的復雜場景中進行快速的規(guī)劃出一條可行路徑已成為重難點，而基于采樣的雙向搜索已被證明有助于發(fā)現(xiàn)狹窄通道[80]，因此未來應進一步研究在狹窄通道復雜環(huán)境中的雙向路徑規(guī)劃算法。

（2）多機器人協(xié)同的路徑規(guī)劃

由于無人機集群協(xié)同、無人車編隊協(xié)同等的現(xiàn)實需要，如何為多機器人規(guī)劃出有序、安全、節(jié)能的路徑顯得尤為重要。傳統(tǒng)上多采用粒子群等智能仿生算法，近年來，隨著強化學習和深度學習顯示出的良好的性能，將其應用于路徑規(guī)劃能使多機器人協(xié)同調(diào)度更靈活高效，所以基于強化學習和深度學習等方法進行多機器人協(xié)同的路徑規(guī)劃是重要的研究方向。

（3）多算法融合的路徑規(guī)劃

有的算法注重全局的最優(yōu)性，導致實時避障時性能不佳，有的算法注重躲避障礙物時的快速性和安全性，卻易造成局部極小值。單一的路徑規(guī)劃算法由于其局限性和片面性難以滿足復雜環(huán)境下人們對速度、能耗、安全等的要求，因此結(jié)合多種算法優(yōu)點的融合算法是實現(xiàn)機器人路徑規(guī)劃的發(fā)展趨勢。

（4）高質(zhì)量解的路徑規(guī)劃

算法規(guī)劃出的路徑質(zhì)量可以根據(jù)長度、平滑度和安全距離來衡量，然而算法能否收斂到最優(yōu)解通常是理論上關(guān)注的問題，實際應用需要的是高質(zhì)量的路徑，即代價低于給定閾值的路徑。所以未來應進一步通過設(shè)定閾值函數(shù)、改變障礙物建模半徑或發(fā)明輕量級方法來研究符合實際應用的高質(zhì)量解的路徑規(guī)劃算法。

（5）自適應的路徑規(guī)劃

大部分路徑規(guī)劃算法針對的都是特定場景，當遇到超出預料場景的規(guī)劃問題時，易出現(xiàn)規(guī)劃速度慢甚至失敗的情況，降低了機器人的安全性、實用性，因而通過數(shù)據(jù)、經(jīng)驗或其他方法進行不同場景下的自適應規(guī)劃，是未來機器人路徑規(guī)劃的發(fā)展方向。