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

李曉旭，馬興錄，王先鵬

(青島科技大學 信息科學技術學院，山東 青島 266061)

0 引言

隨著科技的發展與產業變革，移動機器人被廣泛應用于生產與生活的各個領域之中。由于機器人工作環境的不確定性與復雜性，如何快速準確地搜索出一條由初始狀態至目標狀態的無碰撞路徑成為當前機器人避障的技術難點[1-2]。由于機器人任務的不同，評價路徑的指標也存在一定的差異，一般通過最短路徑、最短時間、最小能量消耗、安全性最高等指標評價選擇最佳路徑。性能優越的路徑規劃算法往往能夠在不確定的復雜環境中規劃出適合機器人運動的高效路徑，這不僅能提高移動機器人的工作效率，還能降低移動機器人損耗。路徑規劃算法作為移動機器人的關鍵技術之一，已成為國內外研究熱點[3]。

本文對主流的移動機器人路徑規劃算法進行總結綜述，根據移動機器人路徑規劃算法的特性，將其劃分為傳統規劃算法、智能規劃算法以及基于采樣的規劃算法。隨后對各類算法進一步劃分，并介紹各種算法的原理以及其自身的局限性，同時總結分析各類算法的優缺點。最后，根據目前移動機器人路徑規劃算法的研究現狀做出進一步展望，分析其發展趨勢。移動機器人路徑規劃主流算法如圖1所示。

圖1 移動機器人路徑規劃算法分類圖

1 傳統規劃算法

傳統規劃算需要在結構化的環境內對障礙物進行準確地建模描述。該類算法依賴環境的顯示表達。

1.1 人工勢場法

Khatib在1985年提出了人工勢場法(Artificial potential field，APF)[4]，用于移動機器人路徑規劃實現避障功能。該算法借助物理學中“勢場”的概念，將障礙物等價位斥力源，對移動機器人產生“排斥力”；將目標點等價位引力源，對移動機器人產生“引力”。機器人在移動的過程中，“引力”與“斥力”不斷發生變化，機器人通過本身所受的合力實時改變移動方向，實現移動過程中躲避障礙物。該方法實時性高，且實現結構較為簡單，因此有一定的應用價值。人工勢場法示意圖如圖2所示。

圖2 人工勢場法示意圖

人工勢場法自身具有局限性。當移動機器人處于障礙物附近時，規劃的路徑會產生“振蕩”現象，這影響機器人在運行過程中的穩定性[5]。該方法容易出現局部極小值，例如當障礙物位于移動機器人與目標點的中心位置時，移動機器人所受“引力”與“斥力”相互抵消，此時機器人無法確定移動方向，進而導致路徑規劃失敗。為此許多學者在不同方向上對此方法作出改進。Li G通過設置虛擬局部目標的方法克服人工勢場法中的振蕩效應[6]。叢玉華等[7]通過設置探測窗口、距離影響因子的方法解決了軌跡振蕩以及軌跡不可達問題。邱博[8]等在斥力勢能函數中引入變增益系數，解決了振蕩問題。王兵根據環境信息動態設置虛擬目標點，快速逃離路徑局部極小值點[9]。石為人[10]針對勢力場局部極小值問題，提出一種拼接局部極小值區域分散障礙物的方法，實驗證明，該方法較好地解決了局部極小值問題。Liu等[11]提出一種雙勢場融合自適應路徑規劃算法，提高了機器人對不同速度與不同障礙物場景的適應能力。

1.2 Bug算法

圖3 Bug算法示意圖

Bug算法結構較為簡單，但使用該算法時，移動機器人在運動過程中僅依靠最新獲得的數據，當傳感器提供的信息不足時，容易導致規劃失敗。針對Bug算法的缺陷，學者們做出了很多研究。Bug2算法[13]對“邊界跟蹤”過程作出改進，一定程度上降低了移動機器人的路徑代價。Kamon提出了Tangent Bug算法[14]，該算法引入路徑代價函數，通過范圍探測器輔助，動態選擇機器人移動方向，進一步減少了移動機器人“邊界追蹤”過程中產生的代價。Dist-Bug[15]算法對遇到障礙物時，移動機器人繞行方向問題作出了改進。彭艷[16]提出了Multi-Bug算法，該算法加入爬蟲分裂規則以及爬蟲死亡條件判斷規則，當移動機器人遇到障礙物時，通過爬蟲分裂規則并行計算路徑代價尋找最優路徑，實驗證明該算法較Dist-Bug算法在降低路徑代價、實時性、通用性等方面皆有一定的提高。蔡存成[17]等在Bug算法中加入“避行”過程，通過避障轉向角索引圖與轉向時機提前量控制移動平臺躲避障礙物，并在“邊界跟蹤”過程中通過模糊控制器控制移動平臺繞行的精確度。

1.3 向量場直方圖法

Borenstein于1991年提出了向量場直方圖法(Vector filed histogram，VFH)[18]。該方法將機器人周圍的環境用直方圖表示，因此該方法對處理傳感器和建模誤差要求非常高。該方法首先構建一個二維笛卡爾直方圖柵格，并根據傳感器數據實時更新柵格圖。然后通過減少機器人當前位置周圍的笛卡爾直方圖，構建一維極坐標直方圖。最后通過極坐標直方圖上的候選波谷確定機器人移動方向。向量場直方圖如圖4所示，該極坐標系的兩坐標軸分別表示以機器人為圓心感知到障礙物的角度、對應方向上障礙物可能存在的概率，一般情況下，極坐標直方圖存在波峰與波谷，波峰表示障礙物密度較高，波谷表示障礙物密度較低，障礙物密度低于給定閾值的波谷成為候選波谷。

圖4 向量場直方圖

VFH算法具有可靠性高、計算效率高、魯棒性強等優點，但是該算法不完備，在狹窄區域中，容易陷入局部極小值。Ulrich提出了VFH+算法[19]，該算法考慮了機器人的體型，提高了算法的通用性；通過閾值滯后增加了軌跡的平滑度；添加成本函數表征算法性能。Ulrich提出了VFH*算法[20]，該算法通過前瞻距離，探測并選擇機器人的最佳移動方向。婁虎[21]等針對水面無人艇雷達避障問題，提出了一種自調節VFH+算法。改進后的算法能夠根據無人船所處的位置對障礙物閾值進行實時更新，提高了無人船的靈活性。

1.4 柵格法

柵格(Grid map，GM)法將機器人所處的環境通過某種方法劃分為具有局部環境信息的網格單元，即柵格[22]。如圖5所示，柵格可分為自由柵格與占用柵格兩種，其中占用柵格包含環境中的障礙物信息。將自由柵格按照一定的順序構成連通圖，并采用搜索算法在該連通圖上構建一條由初始柵格至目標柵格的無碰撞路徑，記為規劃路徑[23]。柵格法在規劃速度方面性能優越，但其規劃效率受柵格精度的制約。柵格法已被廣泛應用于移動機器人，柵格法常用的搜索算法有Dijkstra最短路徑算法、A*算法、D*算法等。

圖5 柵格示意圖

1.4.1 Dijkstra算法

1973年Johnson提出了Dijkstra算法[24]。Dijkstra算法多用于求解有權圖中一個頂點到其他頂點的最短距離。該算法通過數組D保存起始點至各個頂點的最短距離，通過集合T保存已遍歷的最短路徑對應的頂點。執行算法時，通過迭代的方式，每次從集合T之外的頂點中求取距離起始點距離最小的頂點，將該點加入集合T中，并通過該點刷新數組D中的值，直至集合T中包含所有頂點。

Dijkstra算法具有很強的魯棒性，且其能計算出兩點之間的最優路徑解，但是該算法是無向搜索算法，隨著節點數量的增加，該算法的計算效率降低。基于Dijkstra算法的缺點，學者作出了許多改進。目前，有研究通過改變有權圖中的權重標準改善Dijkstra算法的性能[25]，但是多數研究中通過限定搜索區域提高Dijkstra算法的搜索效率。例如，張超等[26]將搜索區域縮小為以起始點和目標點為對角線的矩形區域內，當該區域搜索不到路徑時，逐漸擴大采樣區域；宮金良等[27]按照路徑權值、時間權值分別創建鄰接矩陣，縮小了迭代過程中的最小路徑搜索域和最優路徑更新域；郭夢詩等[28]用連通域表示障礙物區域，并通過鏈表存儲連通域中相鄰節點的距離信息，使搜索范圍保持在避障空間內；賈文友等[29]將起始點、目標點與障礙物通過數學方式構造凸包模型，將全地圖路徑求解問題轉換為求解凸包內起止點至目標點最短路徑問題。

1.4.2 A*算法

1972年Hart等人提出了A*算法[30]。A*算法本質上是一種啟發式搜索算法，即通過一定的評價指標指引算法運行。A*算法引入了代價函數，并將其作為評價指標，代價函數如公式(1)所示。

f(n)=g(n)+h(n)

(1)

其中：g(n)代表節點n至起點的代價，是當前的實際代價；h(n)代表節點n至目標點的代價，是估計代價，一般通過節點n至目標點估計代價的額計算方法有兩種：歐氏距離、曼哈頓距離；g(n)代表節點n的總代價。

A*算法的優點是計算方式簡單、規劃路徑短等，但該方法計算量大，規劃路徑往往拐點較多。針對路徑不平滑問題，Min Haitao[31]在啟發式函數設計中加入了路徑曲率的代價，提高了路徑的平滑性。槐創鋒等[32]將傳統A*算法的搜索領域進行擴展，并通過優化搜索角度的方式提高了路徑平滑度。也有一些研究通過對生成路徑進行優化，增加路徑平滑度。例如文獻[33-36]結合Floyd算法思想優化路徑；文獻[37]通過B樣條曲線平滑路徑。針對傳統A*算法計算效率問題，鄒文等[38]在柵格地圖上建立拓撲地圖，通過A*算法在柵格地圖上獲取初始全局路徑，然后結合Floyd算法思想在拓撲地圖中對初始全局路徑進行優化。通過該種方式，在優化過程中減少了大量計算，提高了其優化效率。其次，通過增加狀態函數優化傳統的動態窗口算法，并將其應用于局部路徑規劃的避障與移動，這也提高了獲取路徑的速度。還有一些研究通過優化評價函數提高算法計算效率[39-40]，也有很多研究通過融合A*算法與動態窗口提高算法速度，例如文獻[32]、文獻[33]、文獻[36]、文獻[40]。

1.4.3 D*算法

1994年Stentz提出了D*算法[41]，該算法由A*算法發展而來，適用于環境未知的或者環境存在動態變化的場景。D*算法對A*算法做了兩個重要改進。

1)出現動態障礙物時，D*算法可以更新動態障礙物附近的柵格信息。

2)D*算法的啟發函數可傳遞。當中心柵格向周圍柵格擴展時，可將其啟發值傳遞給周圍鄰點。

D*算法的代價公式由A*函數發展而來，如公式(2)所示。

F(s)=G(s)+H(s)

(2)

其中:G(s)為起始點至s的代價值，H(s)為啟發值，其計算方式如公式(3)所示。

(3)

式中，s′為s的拓展節點，H(s′)為s′的啟發值，C(s,s′)為相鄰節點的代價值，sgoal為目標點。進行柵格擴展的過程中，被擴展節點s的啟發值由其拓展點s′的代價值以及拓展點s′的啟發值計算得來。D*算法啟發函數示意圖如圖6所示。

圖6 啟發函數示意圖

D*算法對A*算法有一定的提升，其搜索路徑的速度更快、路徑更為優異，但是D*算法并沒有改善路徑曲折的缺點，而且D*算法規劃的路徑貼近障礙物邊緣。與A*算法類似，對于D*算法的改進主要集中于兩個方面：提高路徑平滑度、提高搜索效率。一些研究通過縮小搜索區域提高算法的搜索效率，例如文獻[42]、文獻[43]引入Voronoi圖法在一定程度上縮小搜索路徑；有一些研究通過優化節點選擇方式等方法，對D*算法進行單次優化，提高算法搜索效率，例如文獻[42]引入二級子節點概念放棄擴展無用節點、文獻[44]引入跳點搜索與元胞鄰居結構跳過對無用節點的擴展、文獻[45]通過導向函數限制單次搜索節點范圍；還有一些研究通過更改代價函數縮小搜索空間，例如文獻[48]在代價函數中增加碰撞因子，放棄在可能存在碰撞的區域內搜索路徑，一定程度上提高了路徑搜索效率。對于路徑平滑的改進思想主要有兩種：路徑生成中考慮平滑處理、路徑生成后進行平滑處理。在路徑生成過程種對路徑進行平滑處理主要通過更改代價函數實現，例如，文獻[43]增加產生尖角的節點的啟發值，減少拐點；文獻[45]在原有代價函數基礎上增加平滑度函數，增加路徑平滑度。對生成路徑的平滑工作一般通過借助數學理論實現，例如文獻[46]、文獻[47]引入三次B樣條對生成的路徑進行平滑處理。

1.5 Voronoi圖法

Voronoi圖法采用路徑距離盡可能遠的方式劃分自由空間[48-49]。Voronoi圖法的核心思想是通過一系列種子點將空間劃分為若干個子區域，每個子區域中點到該區域對應的種子節點的距離小于它們到其他種子節點的距離。通過該特性，將空間中障礙物邊界取做種子節點，則每個子區域的邊界都可以作為移動機器人無碰撞路徑的一部分。將機器人的初始點和目標點分別連接到Voronoi圖上，采用搜索算法可獲得由初始點至目標點的無碰撞路徑。

Voronoi圖能夠使機器人與障礙物保持一定的距離，這提高了機器人運行的安全性，但是該方法獲取的路徑代價較大，且在高維空間的規劃能力較差。針對移動機器人在動態環境中的路徑規劃問題，Ayawli等[50]提出一種基于Voronoi圖和計算幾何技術的動態路徑規劃算法。該算法使用Voronoi圖以幾何形狀計算路線圖，并將節點添加到初始路線圖節點以計算用于重新規劃的新路徑，在后續重新規劃路徑值前，失效節點被丟棄，從而節省時間與空間資源。實驗結果表明，該算法可以在復雜和動態的環境中實現安全、更少的路徑成本和時間的路徑規劃計算。Hu等[51]提出一種深度學習強化的基于Voronoi的多機器人協同探索算法。該算法通過Voronoi圖法動態劃分環境區域，然后通過將分區中不同的目標位置分配給各個機器人來最小化重復的探索區域。實驗結果表明，該算法可以確保每個機器人探索區域時而不會與其他機器人發生沖突，從而最大限度地減少任務完成時間并節省更多資源和能源。

由上述可知，傳統的移動機器人路徑規劃算法需要對環境進行建模與描述。因此，隨著環境復雜度的增加傳統路徑規劃算法的搜索效率將大大降低。

2 智能規劃算法

智能算法具備一定的學習能力，對環境的適應能力強，能夠在規劃中不斷獲取新的信息用于優化路徑。

2.1 蟻群算法

1991年Colorni與Dorigo提出了蟻群算法(ACO，ant colony optimization)[52]，該算法是一種仿生學算法，受螞蟻覓食行為啟發而來。螞蟻覓食偏向于走信息素高的路徑，螞蟻覓食示意圖如圖7所示。蟻群算法被廣泛應用于移動機器人動態路徑規劃中。

圖7 螞蟻覓食示意圖

蟻群算法雖然具有較高的魯棒性，但是該算法容易出現局部最優問題。針對該缺點，許多學者對蟻群算法作出改進。Sangeetha等[53]提出一種基于智能增益的蟻群路徑規劃算法并將其應用于無人地面車輛(UGV,unmanned ground vehicles)。當UGV遇到障礙物時，會在障礙物周圍構建許多路徑，因此需要耗費大量時間選擇最優路徑。該算法通過消除需要穿越障礙物周圍所有的路徑減少能量。實驗結果證明，該算法相對于傳統ACO算法在獲取路徑速度上有一定的提升，但是該方法對路徑代價的優化效果不明顯。基于此點，陳禮琪[54]在文獻[53]的基礎上對ACO算法作出了改進。該算法通過更改轉移概率公式，減少螞蟻陷入死區間，即解決了局部極小值問題；通過增益函數更改信息素函數，提高算法搜索效率。實驗結果證明，與傳統ACO算法相比，該算法不僅提高了算法的搜索效率，還降低了路徑代價。對于蟻群算法優化問題，一些研究通過優化信息素更新方式提高算法效率[54-57]；一些研究通過算法融合彌補ACO算法缺陷[58-61]。

蟻群算法采用分布式計算方式，對多個個體同時計算，每個個體在實時感受環境變化的同時，通過釋放信息素改變周圍環境。蟻群算法的正反饋機制使得個體逐漸向信息素高的地方靠攏，這使該算法在搜索路徑的過程中不斷收斂。但是該算法中，初始信息素值相同，因此在選擇下一節點是傾向于隨機選擇，這導致該算法需要較長時間才能發揮正反饋作用，從而降低了算法收斂速度。當蟻群算法獲得的初始解為次優解時，正反饋機制很容易使得次優解占據優勢，即使得算法陷入局部最優，而且難以逃出局部最優。另外，蟻群算法參數眾多且具有一定的關聯性，通過調整參數可以提高蟻群算法的性能，但是參數的調整依賴于經驗和試錯。因此，對于蟻群算法的優化除了上述研究的改進外，還可以對信息素的初始化方式進行改進，為算法提供較好的探索方向，不僅可以解決局部最優問題，還可以提高算法收斂速度。另外，對蟻群算法的結構進行優化也具有重要意義，通過改進參數的關聯方式、對參數進行優化，可以增加算法的可調性，提高算法優化能力。

2.2 遺傳算法

1958年，Bremermann首次提出遺傳算法(GA，genetic algorithm)概念[62]。遺傳算法是一種模仿生物體在繁衍后代過程中自然遺傳、進化的全局優化算法，主要包括路徑編碼、構建適應度函數等過程。該算法可以并行地對解空間的不同區域進行搜索，使得搜索趨于最優解，從而克服傳統優化算法容易陷入局部極小值的缺點。該算法被廣泛應用于移動機器人路徑規劃場景中。

遺傳算法運算速率較低，且在運算過程中占用大量計算機資源，這也是制約其發展的主要因素。針對遺傳算法的改進問題，學者們做了大量研究。針對傳統遺傳算法收斂速率慢、局部搜索能力差問題，王豪等[63]提出一種改進的自適應遺傳算法。該算法通過改進適應度評估指標與輪盤賭選擇方法提高了算法的搜索效率。實驗表明，該算法獲得的平均路徑比傳統遺傳算法縮短了9.9%，且算法迭代次數也相應地減少。針對遺傳算法局部局部極小值問題，王吉岱等[64]提出了一種模糊自適應遺傳算法，該算法結合模糊邏輯算法動態自適應調整交叉和變異算子。另外，在適應度函數中引入余弦函數平滑度評價因子，減少了路徑的拐點，提高了路徑的平滑度。實驗表明，該算法與自適應遺傳算法相比，收斂速度更快，且銳角拐彎次數減少了45.16%。針對傳統遺傳算法局部最優問題，Qu等[65]通過協同進化機制改進遺傳算法。該算法通過改進遺傳算子與適應度函數，解決了遺傳算法局部最優解問題并提高了收斂速度；另外，通過協同機制避免了機器人之間的碰撞，使得該算法可以應用于多機器人路徑規劃。Nazarahari等[66]提出一種增強遺傳算法結合，該算法通過5個定制的交叉和變異算子，解決了傳統遺傳算法初始解迭代多次無法獲取最優解問題，另外該算法增加了碰撞消除算子，使其可以應用于多移動機器人路徑規劃中。

遺傳算法與蟻群算法類似，都是從群體的角度出發，對多個個體并行計算，在一定程度上提高了一定效率。該算法使用概率方式進行迭代，具有一定的隨機性，而且在搜索過程中使用評價函數啟發，實現過程相對簡單。與蟻群算法類似，該算法參數較多、參數關聯性強，而且參數取值對算法的性能影響較大，但是，對參數的調整往往依賴于經驗。因此諸多學者通過優化參數實現對算法的優化，例如文獻[66]。與蟻群算法相比，遺傳算法對網絡反饋信息的利用率較低，因此收斂速度較慢，所以更改遺傳算法結構，提高算法對反饋信息的利用率，可以加快算法收斂速率。遺傳算法對初始種群的選擇具有一定的依賴性，因此，通過啟發式方法選擇更為優異的初始種群，可以提高算法的效率。

2.3 神經網絡法

神經網絡(NN，neural network)算法是在研究人腦工作機理的基礎上提出來的，具有較好的學習、容錯能力[67]。該算法的基本思想是構建一個針對移動機器人路徑規劃的神經網絡模型。該模型的輸入為傳感器信息以及機器人上一次的運動狀態[68]。

神經網絡方法可使機器人具備適應新環境的能力，但需要事先構建數據集訓練模型，而且訓練時間較長。因此，往往將神經網絡算法與其他智能算法相結合，以改善神經網絡的規劃性能。文獻[69]與文獻[70]將神經網絡與遺傳算法相結合應用于移動機器人路徑規劃，實驗結果證明了該方法的可行性；文獻[71]融合神經網絡與混合粒子群算法實現了移動機器人路徑規劃；文獻[72]與文獻[73]將模糊神經網絡應用于路徑規劃，并證明了該算法的高效性。文獻[74]將使用自適應蟻群優化算法和人工神經網絡迭代方式解決路徑規劃問題，試驗證明該方法獲取路徑的速度更快。文獻[75]提出一種概率路線圖與神經網絡結合的路徑規劃算法實現了移動機器人動態路徑規劃。

神經網絡結構中包含大量的參數，參數的數量往往比蟻群算法、遺傳算法等其他智能算法更多，且參數關聯性更強，對算法效率影響更明顯。因此，在構建神經網絡時，調參過程較為復雜，且通常會占用大量時間，這大大限制了神經網絡的應用。另外，神經網絡需要大量的數據對模型進行訓練，數據量的大小間接影響算法的性能。目前，神經網絡在路徑規劃領域的應用相對較少，因此，可用的公開數據集較為匱乏。學者往往需要通過大量數據事先構建數據集，這增加了神經網絡的實現難度。即便目前已有大量研究融合神經網絡與各種智能算法，例如蟻群算法、粒子群算法、遺傳算法等，但將融合算法應用于移動機器人路徑規劃的研究不是很多。神經網絡缺陷較為明顯，但是優異的網絡架構往往能使算法具有強大的環境適應能力。隨著移動機器人應用場景的增加，其面對的工作環境復雜度進一步增加，神經網絡的優勢將進一步展現。因此，將神經網絡應用于移動機器人具有重要意義，未來工作中需要對該應用場景做大量研究。

3 基于采樣的規劃算法

基于采樣的方法通過碰撞檢測判斷候選路徑采樣點的可行性，從而避免了對環境約束的顯示表達(不需要對環境建模)。該種方法通過連接所有可行采樣點，進而形成可行路徑圖，最后在該路徑圖中求解一條由初始狀態至目標狀態的可行路徑。基于采樣的規劃算法基本框圖如圖8所示。目前常用的基于采樣的規劃算法是概率路線圖(PRM，probabilistic roadmaps)法和快速擴展隨機樹(RRT，rapidly-exploring random tree)法。

圖8 基于采樣的規劃算法框圖

3.1 PRM算法

1996年Kavraki 和 Svestka[76]提出了PRM算法，該算法是一種基于多次查詢的規劃算法，包括學習和查詢兩個階段。在學習階段，通過自由配置空間隨機生成可行采樣點，并使用快速的路徑規劃器連接這些可行采樣點，從而構成概率路線圖；在查詢階段，可以在概率路線圖中尋找一條由初始狀態至目標狀態的最佳路徑。如圖9所示。

圖9 PRM算法路徑規劃示意圖

PRM算法在高維空間中表現優異，因此該算法得到了廣泛關注與研究。但在一些應用場合中，獲得先驗路標的計算量可能太大甚至導致規劃失敗，這限制了該算法的在線規劃能力。當采樣點較少時，PRM算法規劃的路徑難以通過狹窄通道；增加采樣點數量，可以解決該問題，但是計算代價增大。針對該問題，Ravankar等[77]提出一種基于混合潛力的概率路線圖算法，該算法利用地圖分割來產生高潛力和低潛力的區域，并在路線圖構建過程中減少樣本集分散。實驗結果表明，該方法的局部和全局規劃成功率中均高于95%；Zhong等[78]通過識別狹窄通道并增加狹窄通道中路標密度的方式，提高了路徑規劃的效率以及成功率。程謙等[79]通過改變連接點距離的方式，一定程度上提高了搜索路徑的效率。針對PRM在采樣點較少時難以規劃出路徑的問題，鄒善席[80]等通過隨機采樣點生成函數將落在障礙物內的采樣點變換到自由空間內，提高采樣點的利用率；另外通過節點增強法實現了對路徑的優化。實驗結果表明，相對于傳統的PRM算法，該算法的路徑規劃時間更短，且路徑代價也相應的降低。

3.2 RRT算法

1998年Lavalle提出了RRT算法[81]，該算法通過構建隨機樹的方式獲取由起始點至目標點的無碰撞路徑。RRT算法將起始點作為隨機樹的根節點，通過隨機采樣的方式獲取隨機點，并將符合條件的點(與隨機樹中葉子結點相連時不與障礙物發生碰撞)加入隨機樹中作為葉子結點，直至目標點被加入到隨機樹中，算法迭代結束。RRT算法擴展過程示意圖如圖10所示。

圖10 RRT算法擴展過程

RRT算法簡單，對環境適應性強，而且可用于實時在線規劃[82]。但是RRT算法對空間的探索完全隨機，因此搜索效率較低；另外，RRT算法對路徑缺乏優化能力。針對RRT算法的局限性，學者們做了大量研究。Kuffner等[83]提出了Bi-RRT算法，通過以起始點與目標點分別為根節點同時擴展隨機樹的方式，提高路徑搜索效率。Karaman和Frazzoli[84]提出了RRT*算法，該算法通過重選父節點、重布線兩種方式優化RRT算法，一定程度上降低了RRT算法的隨機性。雖然隨著空間維度的增加，RRT*算法收斂速度有所下降，但是RRT*算法具備漸進優化能力，因此學者們基于此算法作出了大量改進性研究。結合文獻[83]的思想，Jordan和Perez[85]提出了Bi-RRT*算法。Nasir等[86]提出一種在規劃過程中可根據在線信息調整參數的RRT*-Smart算法，以便適應諸如迷宮、狹窄通道等多類型環境。

雖然以上改進算法的速率有一定提升，但仍難滿足高維空間的規劃需求。由此誕生了啟發式RRT算法，該種算法通過直接改變采樣點的生成方式，降低路徑的隨機性和代價。Urmson等提出了基于啟發式引導hRRT算法[87]，該算法結合啟發式函數生成有效節點，引導隨機樹生長方向。Gammell等[88]提出了Informed RRT*算法，該算法在RRT*算法的基礎上利用啟發式方法對路徑進行了優化。當獲取初始路徑后，該算法將采樣空間限制在特定的超橢球區域內，進而提高路徑優化的收斂速率。基于該思想學者們做出了許多研究與改進[89-91]。Gammell等[92]提出了BIT*算法，該算法采用批采樣方式與超橢球優化機制相結合的方式，提高了獲取路徑速率的同時，降低了路徑代價。Strub等[93]提出了一種自適應啟發樹算法(Adaptively Informed Trees，AIT*)，該算法通過使用非對稱雙向搜索來適應每個問題實例，以同時估計和利用特定問題的啟發式，這使得其能迅速找到初始解并收斂到最優。另一種啟發方式是基于目標偏向的，即goal-biasing RRT算法。該算法包括隨機擴展和目標擴展兩種方式，并在擴展過程中以一定概率選擇擴展方式。許多研究基于此思想對RRT算法作出改進[94-96]。Noreen等[97]將路徑搜索區間限定在包含起始點與目標點的可調邊界區間內，增加了隨機樹生長的方向性。

4 路徑規劃算法分析

本文對目前主流的路徑規劃算法進行簡單的歸納綜述，列舉相關算法的實現機制與原理、優點以及局限性，結果如表1所示。

表1 主流路徑規劃算法匯總表

現有的規劃算法及其改良算法都已經應用于移動機器人路徑規劃之中，但是大多數研究都是將規劃算法用于單個移動機器人，對于多機器人協同規劃的算法相對較少。

傳統的路徑規劃算法依賴于環境中障礙物的顯示表達，即需要描述環境中的障礙物。例如，Bug算法在運行過程中需要對遇到的障礙物執行“邊界跟蹤”操作；基于柵格的算法需要構建環境柵格地圖；向量場直方圖算法需要根據障礙物密度構建極坐標系等。雖然各種算法對環境的表達方式略有不同，但都依賴于環境，這使得傳統算法受環境約束較大。例如，Bug算法只適用于二維環境，當環境維數增加時，Bug算法將無法執行“邊界跟蹤操作”。傳統算法的結構簡單，這使得大多數算法的計算速度更快。一般而言，計算方式越簡單，其收斂速度越快。柵格法與Voronoi法都是基于圖形的算法，這些算法往往需要構建路徑圖形，該操作占用了一定的計算資源，因此相對于人工勢場法、Bug算法、向量場直方圖法，基于圖形的算法收斂較慢。雖然柵格法、Voronoi法的收斂速度較慢，但是其路徑優化能力更優越，獲得的路徑往往代價更低，而且對于環境的適應能力有一定提高，具有更強的魯棒性。環境維度越高，該特性越明顯。結構簡單的算法對環境的適應力較差，人工勢場法在特殊環境下(例如，引力與斥力相抵消)、Bug算法與向量場直方圖算法在復雜環境下(例如迷宮)，容易陷入局部極小值，進而導致規劃失敗。基于圖形的算法雖然犧牲了規劃效率，但其較為復雜的結構使其性能得到提升，一定程度上解決了局部極小值問題，且對環境的適應能力有一定的提高。

相對于傳統算法，智能算法結構更為復雜，而且智能算法自身具有強大的學習能力，這使得其對環境的適應能力非常強，減少了環境對算法的約束，極大程度上避免出現局部極小值問題。蟻群算法、遺傳算法、神經網絡算法都具有較多的參數，往往需要調參提高算法性能。蟻群依靠信息素的濃度變化實現對路徑的漸進優化，當初始解為次優解時，蟻群算法容易出現局部最優問題。遺傳算法克服了此缺點，遺傳算法通過交叉和變異操作使算法的漸進優化能力更強。但遺傳算法的交叉和變異等過程需要大量計算，因此在獲得優化性能的同時，降低了算法的收斂速度。神經網絡算法的結構更為復雜，該算法通過模擬人腦機理，對模型參數漸進優化。該算法的顯著特點是需要大量數據訓練模型，數據量越大，模型越精確，這也體現了該算法強大的學習能力。神經網絡算法往往需要結合其他智能算法實現性能的提升，例如通過神經網絡模型為遺傳算法適應度函數提供更為合理的輸入。

基于采樣的算法不需要對障礙物進行顯示描述，因此進一步降低了環境約束，這使得該種算法適用于高維空間的路徑規劃。但該算法的顯著特點是隨機性較大，生成路徑的代價較高。PRM算法在學習階段通過采樣點構建網絡圖，在查詢階段通過搜索圖獲取路徑。對圖的操作，使得PRM算法浪費大量的計算資源，因此規劃速率較慢。隨著環境維度的增加，構建與查詢圖所消耗的時間隨之增加，因此該算法不適用于復雜環境下移動機器人動態路徑規劃。RRT算法通過隨機樹的方式擴展路徑，雖然該方式隨機性較大，但其擴展速度極快，因此算法收斂更快，更能滿足規劃的實時性需求。隨著環境維度的增加，其速度優勢更為顯著。RRT算法的隨機性使獲取路徑的代價有所提升，且算法性能不穩定。

以上所有算法都具有其本身的優勢與適用場景，但是往往其局限性限制了自身的發展，因此大量的工作用來優化劃算法。

5 路徑規劃算法發展趨勢

本文總結綜述了移動機器人路徑規劃主流算法的原理、優缺點、研究現狀及其改進方法，并將其分為三類：傳統規劃算法、智能規劃算法、基于采樣的規劃算法。接下來對路徑規劃技術做出以下展望。

1)更為高效的算法融合：

目前，對于算法的大部分研究工作都是基于算法本身特性進行改進，對算法進行融合的研究相對較少，但是這些工作都取得了不錯的效果，例如文獻[35]、文獻[38]、文獻[50]、文獻[60]等。單一的算法都具有各自的局限性，例如局部極小值、路徑拐點多、規劃效率低等問題，而并不是所有算法都具有相同的局限性，因此可以通過將互補的算法進行融合，實現更為高效的規劃方式。例如將A*算法與蟻群算法進行融合，引入A*算法的評價函數優化蟻群算法的信息素更新方式，既加快了算法的收斂速率又克服了局部極小值問題。因此多算法融合是未來實現高效路徑規劃的重要方式。

2)多傳感器融合的動態路徑規劃：

現有的路徑規劃算法多用于離線規劃，即假定環境不變的情況下進行路徑規劃。然而實際應用場景往往是動態的，移動機器人需要及時躲避動態的障礙物。因此，動態路徑規劃算法在未來發展中需要投入大量研究。在動態路徑規劃中，往往需要實時更新環境信息，各種傳感器可以用來實現對動態場景的更新。例如，深度相機、雷達等都可以實時傳遞環境中的障礙物距離以及形狀信息，可以用于實時判定機器人與障礙物之間的距離。將多傳感器應用于移動機器人并融合傳感器信息可以實現更為精確的路徑規劃，甚至實現更為復雜的功能。

3)復雜環境中的路徑規劃：

現階段，路徑規劃算法在規劃過程中往往將初始位置與目標位置用點代替，該種方式較為簡單；而且一些傳統的路徑規劃算法僅適用于二維環境，大多數算法在環境維度提高、障礙物增多時，規劃效率降低。現有的應用實例中，大多將移動機器人應用于簡單的生活場景中，例如掃地機器人。現實的工作場景往往是復雜的，因此，提高路徑規劃算法在復雜場景下的規劃效率具有重要意義。

4)物聯網技術協同規劃：

目前的應用場景中，大多是移動機器人自身通過計算單元實現路徑規劃功能。隨著市場需求的增加，移動機器人被應用于各種復雜場景是必然趨勢，而面對復雜場景時，移動機器人所處理的數據將大大增加，這使得對移動機器人的核心處理單元要求非常高。隨著物聯網技術的發展，數據可以通過互聯網快速傳輸。因此將移動機器人需要處理的大量數據通過網絡傳輸給高性能遠程服務器處理，不僅能提高移動機器人的規劃效率，還能在一定程度上簡化移動機器人自身結構。

5)優化已有算法的規劃性能：

已有的算法雖然具有一定的局限性，且大多應用于簡單規劃場景，但是基礎算法仍有其適用場景，并且這些算法是實際應用的重要基礎。因此，針對不同的路徑規劃算法對其自身局限性進行優化仍有重要意義，未來的工作中可以探索將更多的數學理論應用于優化路徑規劃算法，例如改進蟻群信息素更新方式、改進A*與D*算法的代價函數、優化遺傳算法的適應度函數等。對基礎算法的改進對未來的實際應用仍具有重要研究價值。

6 結束語

路徑規劃算法是移動機器人的關鍵技術，目前的路徑規劃算法具有一定的局限性，仍需要大量工作進行改進，提高算法的性能與適用性。隨著人工智能技術的發展，多技術融合為路徑規劃算法的發展提供了發展契機。通過提升路徑規劃算法的性能與適用性，可以使移動機器人的應用場景更穩廣闊