移動機器人路徑規劃綜述

(西安工業大學 電子信息工程學院，西安 710021)

0 引言

路徑規劃是機器人研究的核心內容之一，近年來在很多領域都具有廣泛的應用，如室內服務機器人的自主運動[1]；無人機的避障突防飛行[2]；物流管理中的車輛問題[3]及類似的資源管理、資源配置問題。機器人的路徑規劃按照“感知-建模-規劃-執行”的過程依次進行。首先機器人用自身攜帶的傳感器感知環境，對環境形成兩類信息，一類是靜態的長期信息反映環境中靜態障礙物的分布，另一類是動態的短期信息反映環境中動態障礙物的分布。然后選擇合適的建模方法對整個工作空間建立一個便于計算機進行路徑規劃的環境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間[4]。接下來根據已有的長期信息和在運動過程中感知到的動態障礙物，依據最低耗損原則規劃出最優化路線，使預定的性能函數獲得最優值。最后執行系統執行該條線路，使得機器人無碰撞的安全到達目標點[5-9]。

本文重點對全局路徑規劃和局部路徑規劃進行了總結與評價，全局路徑規劃注重尋求最優解，局部路徑規劃注重避障，同時介紹了基于仿生學的算法，最后對移動機器人路徑規劃的未來發展趨勢進行了展望。

1 全局路徑規劃方法

1.1 柵格法

柵格法將工作空間解耦為多個簡單的區域，建立一個便于計算機進行路徑規劃的環境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間，實現相互間的映射。每個柵格點或者在自由空間中，用“0”表示，或者在障礙物空間中，用“1”表示，通過搜索柵格圖找到一條從起始柵格到目標柵格的最短路徑[10-12]。若柵格較小，環境信息將會非常清晰，但會需要存儲較多的信息，規劃速度降低，實時性得不到保證；若柵格較大，信息存儲量將會少，規劃速度加快，但環境信息劃分會變得模糊，不利于有效路徑的規劃，所以需要在地圖網格分辨率與路徑規劃實時性上尋求平衡。

柵格法是公認的最成熟的算法，也是安全系數最高的算法，直觀明了，常與其他方法集成使用，但方法受制于傳感器，消耗過多運算資源。鄭秀敏[13]等人采用柵格法表示環境，局部路徑規劃基于模擬退火法，用模擬退火法擺脫局部極小值，達到全局最優，同時也對模擬退火法進行了改進；于紅斌[14]等人在柵格法的基礎上，在結點中加入記憶力，修改兩個結點之間的關聯程度，形成正反饋機制，最終得到一條最優路徑，該算法在靜態路徑規劃中切實可行，并且搜索效率高于遺傳算法，但參數是依據經驗值確定的，普遍性不高；朱磊[15]等人針對發生礦難的井下環境，采用柵格法建模，改進的負反饋遺傳算法規劃全局路徑，并以全局規劃的結果為基礎，設計了基于自由柵格和障礙柵格的相互轉換的局部避障方法，該方法具有較強魯棒性；王曙光[16]等人提出實時柵格法將其應用于多機器人協作建立空間地圖，通過機器人的編隊在探索環境中直接完成環境建模，不再局限于單個機器人各自劃分一個小區域，柵格也不再局限于正方形，實時柵格法檢測障礙計算簡單，不需要進行局部地圖的拼接，但在實際情況下，由于地形起伏的環境因素，隊形會出現偏差，造成柵格位置的誤差，影響檢測結果。

1.2 A*算法

A*算法是一種在工作空間中求解最短路徑搜索方法，它將啟發式函數BFS和常規方法Dijkstra算法結合在一起[17-20]，在進行啟發式搜索提高效率的同時，可以保證找到一條最優路徑。代價函數定義為f(m)=g(m)+h(m)。其中f(m)是從初始點S經由中間點M到目標點E的代價估計，g(m)是初始點S到達中間點M的實際距離，h(m)是是中間點M到目標點E的估計距離，它是一種啟發式函數，評估任意結點到目標點的代價，快速地導向目標結點，省略大量無效的搜索節點。

A*算法能快速實現移動機器人的無碰最短路徑規劃，主要的計算量在于對節點狀態的檢測和最小代價的選擇[21]。Dan[22]等將A*算法用于對隨機語法進行解析，通過與各種算法的比較，可以看出A*算法大大減少了找到解析所需的時間，并且能給出最佳的、準確的解析；Kagan[23]等將A*算法用于在離散空間中在線搜尋特定信息，啟發函數定義為搜索空間上信息距離，該算法具有較強的收斂性，獲得的結果可以用于彌補信息理論搜索過程的不足；由于算法本身原理的限制，規劃出的路徑折線多、轉折次數多、累積轉折角度大，王紅衛[24]等人提出平滑A*算法，取出相鄰的3個節點，當某一節點前后節點連線上無障礙物時，刪除中間節點，該算法優化了路徑，減少了路徑長度，降低了轉折次數；A*算法規劃出的路徑曲率非連續，導致在轉折點處運動參量發生跳變，王殿君[25]在平滑A*算法基礎上加入了在拐點處調整自身位姿，更好實現自主定位功能，但兩者需要在A*算法規劃好的基礎上平滑路徑，增加了運行時間，實時性不高，尋路效率不高；規劃的場景較大時，往往由于龐大的計算量導致運行時間過長、內存占用嚴重，趙曉[26]等人在A*算法的基礎上，結合跳點搜索算法將添加到OpenList和ClosedList的不必要節點用跳點代替，減少了算法的覆蓋面，大大加快了尋路速度，但規劃出來的路徑轉折點較多，不利于機器人直接執行；王小紅[27]等人提出對鄰域進行擴展，將8鄰域擴展到24鄰域，使得機器人可以小角度行進，從而軌跡更加平滑，并且將啟發式函數不再單一的選擇曼哈頓距或者歐幾里得距離，將其進行融合以適應具體環境，使得A*算法更加靈活，規劃出來的轉折點少，同時全局路徑更加平滑。

2 局部路徑規劃算法

2.1 人工勢場法

人工勢場是抽象的人造受力場，其中目標點產生“引力”，障礙物產生“斥力”，最后通過求合力來控制移動機器人的運動[28-30]。人工勢場法主要用于局部環境中躲避動態避障物，此時的引力極是局部環境中的中間目標，斥力極則是局部環境中的障礙物。該方法結構簡單，便于底層的實時控制。但其存在局部極值點，易在狹窄的通道中擺動，當臨近目標點的地方存在障礙物時不能發現路徑等問題[31-32]。

Borenstein[33]等人提出了基于向量場直方圖方法的VFH算法，對人工勢場方法進行了改進，機器人可在多障礙物環境或狹窄通道中找出局部較優的路徑，且運行軌跡合理。但是，此方法將機器人理想化為一個點，沒有考慮機器人的尺寸、動力學和運動學特性，這使得機器人很難按照VFH算法計算出來的預定軌線移動；Iwan[34]等人充分考慮機器人的尺寸、軌跡和運動學性能，提出了改進的VFH+方法，但只是一種純局部避障算法，容易在多個障礙物中迷失方向；之后他們加入了接下來幾個周期機器人的位置和周圍環境的關系的預測，在幾個可能方向角之間進行優化選擇，提出了VFH*[35]算法，使得機器人能夠選擇一個局部較優的方向，但本質上仍然是局部避障算法，沒有考慮到周圍障礙物的速度，選擇出的運動方向有可能不是最優的，章蘇書[36]提出可VFH#算法，考慮了障礙物的速度，并預測了機器人沿某方向前進會遇到的環境，使得機器人能找到最優最安全的運動方向；S.S.Ge[37]等首次提出人工勢場法在臨近目標點存在障礙物不可達問題，然后將機器人與目標點的距離考慮到斥勢場函數中，保證目標點為全局最小點；唐志榮[38]等人將道路邊界勢能場考慮在內引入道路邊界斥力場模型，利用橢圓化距離代替傳統斥力勢場中的實際距離，從而在較小車道空間獲得汽車避障局部路徑，保證汽車在避障過程中具有良好的穩定性和舒適性。

2.2 動態窗口法DWA

動態窗口法DWA是在曲率速度法[39]的基礎上提出的，將機器人的位置控制轉化為速度控制，將避障問題描述為速度空間帶約束的優化問題。該算法在速度空間中采樣多組速度，將有限的速度和加速度的運動約束考慮到動態窗的設計中，模擬這些速度在一定時間內的運動軌跡，再通過一個評價函數對這些軌跡打分，選擇出最優的速度。充分考慮了機器人的物理限制、環境約束以及當前速度等因素，得到的路徑安全可靠，適用于局部路徑規劃[40-43]。

Piyapat[44]等提出field Dynamic Window Approach,將動態窗口法中只涉及了機器人軌跡上的障礙物改變為不僅考慮了軌跡上的障礙物，也考慮了臨近軌跡的障礙物，以避免機器人可能會撞到一些靠近軌跡但不在軌跡上的障礙物。該算法具有較好的魯棒性，經驗證在涉及近軌跡障礙物時可以更安全地行進；Pablo[45]等提出了一種稱為共享控制動態窗口方法的共享控制方法。它通過控制界面接受用戶命令，提供最合適的、動態可行的軌跡，并提供導航輔助，在非結構化環境中以及動態約束發揮重要作用的其他場景中駕駛車輛；程傳奇等[46]將動態窗口法和改進A*算法進行融合，構造一種顧及全局最優路徑的評價函數，可實時避障，路徑更加平滑，曲率變化的連續性及可輸出的運動控制參數更符合機器人的動力學控制；在障礙物較稠密區域，動態窗口法在穿越稠密障礙物時，存在繞行于稠密障礙物區域外側，造成總長度增加且速度和安全性不能兼顧的問題。

3 智能方法

3.1 遺傳算法

遺傳算法是一種模擬自然界進化過程，搜索最優解的算法，在進化過程中進行遺傳操作，如選擇、交叉、變異[47-50]。選擇的目的是把優化的個體直接遺傳到下一代，使適應度值較好的路徑具有較大的生存機會；交叉的目的是通過配對交叉產生新的路徑個體，在遇到障礙物時多一種選擇；變異有增加一個點，減少一個點，移動一個點以及替換一段路徑，具有不確定性。

遺傳算法可以同時處理多個個體，具有內在的隱并行性，且具有較高的自組織性、自適應性和自學習性。但是針對復雜環境設計相應的遺傳算子存在著較大困難，經常會產生非法個體，Vincent[51]等在自主無人機上將遺傳算法與粒子群算法相融合去處理在三維環境下復雜問題，產生的路徑由線段，圓弧和垂直螺旋組成，通過使用“單程序，多數據”并行編程縮短執行時間，并在現成多核CPU上實現了實時性能，可以實現無人機的實時路徑規劃，此外遺傳算法可以為粒子群算法產生出色的軌跡；陳剛等[52]設計了有效的路徑遺傳因子，提出了用翻越障礙物的能力替代穿越障礙物的長度的新適應度計算方法，且充分運用背景知識進行啟發式變異，避免變異的盲目性，該算法有很強的魯棒性，適合于復雜環境下的路徑規劃；在三維空間中隨著維數的增加，傳統避障方法會出現計算量的加劇增加和實時性的大幅度降低問題，陳志軍等[53]采用基于模糊神經網絡和遺傳算法建立機器人三維路徑規劃，模糊神經網絡建立了三維路徑的五層結構，遺傳算法來優化模糊神經網絡，優化后的網絡輸出結果和期望輸出結果高度吻合，具有較高的適應性。

3.2 蟻群算法

蟻群算法就是模擬蟻群覓食行為的優化算法[54-57]。螞蟻在覓食過程中會在所經過的路徑上留下信息素，并且在覓食過程中感知信息素的存在以及強度以此指導運動方向，某一路徑越短，選擇該路徑的螞蟻數量就越多，留下的信息素越強，被選擇的機率也就越高，因此大量螞蟻組成的集體覓食行為便表現出一種信息正反饋現象。

該算法具有分布式并行計算能力，可在全局的多點同時進行解的搜索，在求解非線性問題方面，具有高度的魯棒性。但是目前對于有約束的函數優化問題，缺乏數學理論基礎，尚無相應算法。Vahid[58]等將蟻群算法和模擬退火算法的融合，解決了無等待流水車間調度問題，改進了信息素路徑更新的方式，檢查搜索空間的一些不同區域并選擇最佳解決方案，蟻群算法中局部搜索的新方法對于解決無等待流水車間問題是有效的；王輝[59]等引入新的距離啟發函數因子于狀態轉移概率，并修改信息素更新規則局部更新和全局更新相結合，將此改進蟻群算法應用于泊車系統自動導引車路徑規劃，規劃出的路徑長度短，收斂迭代次數少，具有較強的全局搜索能力和較好的收斂性能；在復雜環境下蟻群算法表現出收斂速度慢，容易陷入局部最優，李龍澍等[60]通過優化初始信息素的分布解決算法初期的盲目性，在信息素的揮發中注意保留優秀路徑的優勢同時避免過多影響后續螞蟻的選擇，算法陷入局部最優，并通過優化概率轉移規則來增加解的多樣性，強化全局搜索能力；彭凡彬[61]等在群機器人路徑搜索時，產生個別螞蟻開辟的新道路，給出算法跳出局部最優解的一種可能，明顯改變了傳統算法的局部性調整，提高了傳統蟻群的搜索能力，規劃出的路徑更加圓滑，方便機器人的快速行走。

3.3 粒子群算法

粒子群算法是模擬鳥群飛行的仿生算法[62-66]。鳥群在隨機搜尋食物時，盡快找到食物的有效方法就是搜尋目前離食物最近的同伴位置，同伴位置在粒子群系統中為備選解，被稱為一個粒子，每個粒子根據自身的經驗和相鄰粒子群的最佳經驗向更好的位置飛行，不斷迭代尋找全局最優解。

該算法為群體智能優化算法，對目標函數的性質沒有要求，易于實現，魯棒性好，在各類多維連續空間優化問題均取得良好效果，但存在過早收斂的問題，搜索性能對參數的依賴性過也過大，易于陷入局部極小值。Yilmaz[67]等采用改進粒子群優化算法來解決混合模型雙側裝配線平衡問題，提出了組合選擇機制和解碼的新過程，增強了算法在解空間中搜索不同點的有效性；翁理國等[68]針對算法陷入局部最優時較差的搜索能力和較差的收斂速度，提出了一種改進型多目標粒子群算法，該算法引入環境選擇和配對選擇策略于適應度值計算方法，根據此來選擇種群的個體歷史最優值位置和全局歷史最優值位置，采用自適應原理改變對速度權重的計算方法，以此來平衡算法的全局搜索能力與局部搜索能力，使種群粒子快速地收斂于帕累托最優邊界。王學武[69]在離散粒子群算法中加入萊維飛行，增加種群多樣性，很好地解決粒子群算法早熟的缺點，提高算法的尋優能力，優化效果穩定。

4 展望

4.1 多機器人協同

多機器人協同是機器人的一個必然發展趨勢，不僅可以發揮個體功能，而且可以根據環境和任務的變化靈活、高效、快捷的組織多個機器人協同完成任務。在路徑規劃中對于未知區域地圖的建立，可以讓多個機器人并行的完成不同的子任務，成員之間相互交換信息，更有效和更精確地進行定位，且若單個機器人的定位錯誤時，不會對全局任務產生很大的影響，群體化智能使得系統的容錯能力更強，可靠性更高，目前研究的熱點是在火災、地震、礦難、巡檢等復雜環境中，多機器人協同搜索。

4.2 空中機器人與水下機器人研究

移動機器人現如今大多是針對地面，如掃地機器人、足球機器人，針對空中和水下機器人則比較少。空中機器人在搜尋目標、航拍攝影、農業植保方面，水下機器人在探測海底資源，搜救被困人員、維護水下管線方面都有很大的發展空間，所以這將是未來的一個熱點及難點。所面臨的外部環境非常惡劣，且很難利用現有的傳感器獲知環境信息，不確定性更大。因此，路徑規劃與避障更加困難和迫切。

5 結論

機器人路徑規劃是機器人應用中的一項重要技術，采用良好的機器人路徑規劃技術可以節省機器人作業時間，同時節約人力資源，減少資金投入，為機器人在多個行業的應用奠定良好的基礎。將全局路徑規劃和局部路徑規劃相結合，可以在注重全局的情況下，提高機器人路徑規劃的避障精度，加快規劃速度，滿足實際應用的需要。同時多機器人協同、空中機器人與水下機器人的研究也將是研究的熱點及難點問題。