移動機器人的路徑規劃技術研究*

李晨輝，王澤峰，胡德燕，胡連信，孫凱悅，崔 琳，吳 晟※

（1.哈爾濱工程大學煙臺研究（生）院，山東煙臺 264000；2.湖州師范學院信息工程學院，浙江湖州 313000；3.煙臺市海洋經濟研究院，山東煙臺 264000；4.天津威圖測控技術有限公司，天津 300392）

0 引言

近年來，移動機器人技術得到了進一步發展，是國家科學技術和工業自動化的重要指標之一。機器人技術在提高社會生產力的過程中所占的比重也越來越大。移動機器人在工業場景和家用場景中都有著龐大的需求，具有廣闊的前景。如家庭場景下的娛樂機器人、康復機器人、服務機器人、安全保護防護機器人；在工業場景下的快遞分揀車AGV（Automated Guided Vehicle）、化學危害氣體中的有害氣體檢測機器人、在路況復雜下的人員搜救機器人。

對于移動機器人，準確的導航對機器人至關重要，而路徑規劃是決定導航是否精確的重要一環。路徑規劃是在已知的應用場景中根據初始起點和目標點規劃出一條路徑。該路徑能夠滿足高效、安全等要求，并且能夠及時避開路徑上的各種障礙物。移動機器人的路徑規劃技術主要包括全局路徑規劃和局部路徑規劃，其核心內容是實現規劃路線的平滑性和冗余性，在外部環境中能夠正確地行進。路徑規劃主要分兩步進行：第一步是根據靜態障礙物區域和自由可移動區域進行全局路徑規劃，找出最優路徑；第二步是移動機器人在目標點行進中，動態感知周圍的局部環境，及時通過局部規劃對障礙物進行避障。本文闡述了從全局路徑規劃到局部路徑規劃的常用算法的應用機制，在現實場景下的應用情況，并對其算法進行了優缺點分析，對部分研究路徑規劃的國內外文獻進行了概述，并對其進行了分析和討論。

1 全局路徑規劃算法對比分析

全局路徑規劃是依照當前的靜態地圖，參考地圖上障礙物的位置和可行路徑，根據系統給出的出發點和目標點，規劃出一條最優路徑。其相關算法主要應用于場景預知的室外環境中，面對復雜多變的地理環境，通過對算法的優化來提高機器人路徑規劃的能力。主要包括A*算法、遺傳算法、蟻群算法、粒子群算法和快速探索隨機樹等。

1.1 A＊算法

1968年Nils Nilsson[1]提出了A＊算法，其主要用于在靜態環境中求解最短路徑，因為其屬于遍歷的確定性搜索方式，搜索過程直觀簡潔，所以是解決地圖環境預知的情況下全局路徑搜索問題的典型算法。在全局網絡中，A＊算法會依據擴展節點選擇當前“代價”最低的方塊進行下一步搜索，直到搜索到終點，從而規劃出成本最低的路徑。A＊算法是當前流行的比較重要的啟發式搜索算法之一，該算法廣泛應用于單機器人的全局靜態環境中。

A＊算法示意圖如圖1所示，其中f()n是關于目的地n的估價函數，g()n是“當前代價”，即起點到目的地n的最短路徑值；h()n是“預估代價”，即當前移動機器人位置到目的地n的最優路經的啟發值。張新艷等[2]引入了基于時間因子的改進型算法來尋找轉彎次數較少的路徑方案。

圖1 A＊算法示意圖

1.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是美國的Bre?mermann[3]于1960年提出，通過選擇和交叉變異手段，模擬達爾文的物竟天擇、適者生存的法則。在初始化階段根據表現的外部性狀，對種群進行編碼，根據適用度函數評估每條路徑的適用度，參考適應度越高，選擇的概率越大，選擇出適應度高的路徑，低于適應度選擇閾值的進行淘汰處理，在已選出的路徑個體中再進行交叉、變異，直至產生達到要求的路徑。遺傳算法示意圖如圖2所示。

圖2 遺傳算法示意圖

基于提高遺傳算法的全局性，減少陷入局部最優的概率，John Hollnd探索出增加變異算子和交叉算子方法，通過模擬自然狀態下的遺傳模式并加入了選擇算子[4]。對于該算法易于過早的收斂而導致迭代效果不佳，Ge等[5]決定改進原本算法：首先是通過增加了新的預測機制，不在是隨機對染色體編碼，另外也通過對適應度函數進行改進，提高其評價廣度。2018年，A Z Zambom等[6]通過優化遺傳算法的執行策略，可在復雜環境中搜索機器人的最優路徑。Qu等[7]設計了一種修改算子的方法，能夠較好地解決局部最優問題，改善了遺傳算法的收斂性差，種群間交叉變異少的問題。

1.3 蟻群算法

蟻 群 算 法（Ant Colony Optimization，ACO）是Dorigol[8]基于正反饋機制提出的一種路徑規劃算法，結合真實環境下螞蟻的行為，模擬螞蟻根據信息素濃度的高低進行路徑決策。根據這一特性，在覓食行為中，總能求得一條從出發點到目標點的最優路徑。圖3顯示了這樣一個覓食的過程。如圖所示，存在一定數量的螞蟻，設定N點為螞蟻的巢穴，F為螞蟻要尋找的食物。蟻群會沿著蟻穴和食物之間的直線距離移動，假設在蟻穴和食物之間出現了障礙物，這時螞蟻就要做出決策，是向左還是向右行進，由于前面的螞蟻沒有留下信息素，螞蟻在兩個方向的概率是相同的。只有在有螞蟻停留的地方，就會在相應的地段分泌一定的信息素，而且信息素會隨時間的流逝濃度逐漸變低，該物質是蟻群進行信息交流的載體。后面的螞蟻通過信息素的濃度來做出相應的決策，很明顯，沿著較短距離的路徑，信息素會越來越濃，進而吸引更多的螞蟻。

圖3 蟻群算法示意圖

為了解決蟻群算法容易陷入局部最優點的問題，不少研究者對算法的信息素濃度進行改進。面對蟻群算法搜索速度慢和局部最優，Liu等[9]在該算法基礎上加入信息素揮發機制和自適應搜索步長，大大減少了蟻群算法的迭代次數。基于此，Dai等[10]認為改進每次迭代的方法是有效的，通過改進迭代的步長實驗表明，與傳統的蟻群算法相比，使得改進的ACO迭代次數減少了2/3，快速高效地對路徑進行規劃證明改進的算法更有效。除此之外，對于多物流機器人的路徑規劃，楊洋等[11]認為蟻群算法結合彈性時間窗技術，能夠實現多物流機器人的路徑規劃相，經仿真實驗表明：快速規劃的同時能夠實現最優的避障路徑。王雷等[12]針對蟻群算法容易陷入局部優化的問題，提出了通過實時調整信息素啟發因子和預期啟發因子，自適應地改變揮發因子。針對蟻群算法初始信息素不足和收斂速度慢和的問題。張瑋等[13]通過加入煙花蟻群混合算法來求解靜態環境下的避障問題。

1.4 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是由Kennedy和Eberhart[14]在1995年提出。粒子群算法通過不斷搜索當前的最優值，通過迭代不斷更新粒子的速度和位置，類似于鳥類覓食的過程。通過個體與群體成員的適當交流，整個鳥群都能達到最終的食物源。該算法是通過模擬鳥群，單個鳥與鳥群之間的信息共享，通過計算分析優化，求出最優解。其基本原理是個體與群體協作和信息共享，從而獲得最優解。它是一個以當前搜索到的最優值不斷更新迭代來尋找全局最優值的算法。粒子群算法是概率型的全局路徑規劃算法，因為在迭代的過程中充滿更多的可能性。PSO通過讓單個粒子在路徑規劃空間里找出此粒子的最優解，再將個體最優解共享給粒子群的其他粒子，找出個體中最優解作為全局最優解，因此整個粒子群在搜索的過程中覆蓋的范圍更大，更容易找到全局最優解[15]，其算法流程如圖4所示。

圖4 粒子群算法示意圖

針對粒子群算法生成因需要達到全局最優而造成的路徑折線較多的和k-means算法易受初始中心影響等問題。Song[16]提出通過加入自適應階段速度，來減緩機器人路徑的折線，優化路徑平滑度，同時也提高了搜索空間的能力。湯深偉等[17]提出了基于改進粒子群算法的k-means聚類算法，孟慶寬等[18]通過粒子群算法計算得到最優加權因子，進而調整控制規則實現導航車輛的自適應控制。

針對于標準PSO算法在一些基準函數上改進，PSO算法能快速收斂但是容易陷入局部最優的問題。王東風等[19]基于粒子間適應值的差異，提出對粒子位置高斯采樣均值的自適應調整策略，減緩粒子在中心的聚集趨勢。Ma等[20]提出將雙重倉庫下機器人最短路徑問題轉變為時變非線性規劃問題來降低難度。Ajeil等[21]針對靜態環境下尋優的問題，通過與GA算法、PSO算法比較，提出通過設置蟻群不同的個體的壽命的優化算法，實驗結果表明，在路徑規劃長度的減少有顯著的效果。

1.5 快速擴展隨機樹

快速擴展隨機樹（Rapidly-exploring Random Trees，RRT）是通過隨機構建空間樹來實現快速搜索的一種算法。基本思想是在已知地圖上，通過給定的起始位置和目標位置的規劃任務，在起始位置通過抽樣隨機構建隨機無向圖，類似于樹形結構，在無障礙區域不斷延伸樹形結構。一般來講，路徑規劃算法都是不斷的朝著目標位置延伸，但是由于障礙物的存在，如果不斷的指向目標位置，會有和障礙物相撞的風險。為解決上述問題，RRT算法主要通過隨機采樣的方法，選擇延伸方向時，會設置一定的概率朝著目標位置生長，也有一定的概率隨機在全局地圖任意方向延伸。擴展樹延伸分支選擇距離采樣點位置近的樹節點，并且建立延伸的樹節點是否撞到障礙物；采樣點距離擴展樹的距離要達到設定的閾值，通過兩個約束防止發生碰撞和延伸的樹節點重復。

對于RRT算法對前期的的擴展比較敏感，全局最優解由于擴展樹的結構，導致收斂速度慢的問題。基于此，N Pérez Higueras等[22]通過將強化學習的思想運用到RRT算法上，提出了一種改進型算法，改進初期的代價函數，使其在前期能夠快速的找到較優擴展方向，從而加快收斂速度。符秀輝等[23]通過加入對擴展方向的自適應策略，減少了RRT算法達到最優路徑的迭代次數，并且對RRT算法前期存在的偏差較大的問題有了一定的改善。由于RRT算法在障礙物較多，且空間比較復雜的環境中，容易陷入局部最優值，甚至是找不到最優解，朱冰等[24]通過提出增加約束來調整擴展的方向，分別設定了安全場約束和對于擴展樹的角度進行了限制，增強了RRT系統的魯棒性。Wang等[25]提通過卷積搭建神經網絡，訓練預測模型，提前預測擴展樹的生長方向，提出通過卷積神經網絡與RRT相結合的改進型算法，通過提前將大量成功尋找最優路徑數據作為訓練集，喂入模型，每次給出最優的多個預測的生長方，再通過RRT進行抽樣，大大減少了隨機性較大，偏差性大的問題，提高了整體的搜索效率。

2 局部路徑規劃算法對比分析

局部路徑規劃是移動機器人執行路徑規劃時的重要一環，對機器人自身的傳感器設備依賴性非常高。局部路徑規劃目前主要應用于動態環境的避障，是移動機器人工作的關鍵技術之一。局部路徑規劃技術主要包括動態窗口法以及人工勢場算法。

2.1 人工勢場算法

人工勢場算法由Khatib[26]在1986年提出。該算法是基于物理學上的正負電荷機制，假設起始位置為正電荷，目標位置設置為負電荷，障礙物則設置為正電荷。根據正負相吸引，正正相排斥原則，從而達到機器人與目標點相吸引，與障礙物相排斥的作用。最后通過模擬由正負電荷所激發的電場，根據機器人電場中所受到的合力來改變移動方向，直至到達目標位置。

由于動態障礙物的存在，而全局規劃算法只能在地圖上規劃，無法考慮動態障礙物，一般的局部實時避障容易偏差較大。針對傳統人工勢場法算法無法達到目標和局部優化的缺點，無人機運動避障人工勢場算法本身存在的極小值問題和局部最小值等問題。段建民等[27]為解決路徑規劃時的最優解問題，提出了將遺傳算法與人工勢場法相融合方法，通過并行搜索方法，提高了最優解的搜索速度。陳麟杰等[28]采用增加了無人機之間的斥力，同時定義集群的前置形心作為另一個引力源。丁家如等[29]提出了改進人工勢場法引力函數。毛晨悅等[30]提出通過生成預規劃路徑弱化了目標點對無人機的吸引作用，增加了路徑的連貫性。

針對傳統人工勢場法應用于多坐標系機器人避障時無法約束各關節位姿、陷入局部極小后難以逃離的問題，傳統人工勢場法由于局部極小點問題而導致規劃失敗。曹博等[31]通過在笛卡爾坐標系內引入引力勢場和斥力勢場，主動采用線段球體包絡盒模型，來測試碰撞模型，提高了系統魯棒性，降低了陷入局部最優值的風險。沈文君[32]提出了在改進人工勢場函數的基礎上，通過修改斥力方向的方法來解決傳統人工勢場法下的典型局部極小點問題。

2.2 動態窗口算法

動態窗口算法（Dynamic Window Approach，DWA）首先要在其速度空間內采取多組的速度，通過計算采樣的多組速度數據進行模擬，模擬出在一定時間內的軌跡，通過一種評價函數，對采樣的速度的軌跡模擬進行評價打分，選取最優的速度進行執行。DWA算法要先模擬出機器人的運動模型，根據機器人的硬件運行性能對其運動軌跡進行模擬，主要是根據是否為全向移動機器人進行區別。確定好機器人模型后下一步進行速度采樣，確定機器人的最小和最大速度的限制，由于機器人的電機力矩有限，存在最大加速度限制，在模擬軌跡是實際達到的速度應該是一個窗口速度。另外，為了保證機器人能夠避免撞到障礙物，在最大減速影響下，對其速度進行約束限制。對速度采樣完成后，對采樣空間內的速度通過評價函數進行評分，記錄評價最優的速度樣本，進行對機器人驅動。動態窗口算法示意圖如圖5所示。

圖5 動態窗口算法示意圖

針對動態窗口法穿越稠密障礙物時存在路徑不合理、速度和安全性不能兼顧等問題，王永雄等[33]通過將其速度采樣改進，提出將其參數自適應的DWA算法。針對于機器人在一些特定場景下，例如：上下坡路面存在的加速度過大、造成局部的路徑偏差過大等問題，張瑜等[34]提出對采樣速度空間的運動模型進行改進，對其速度約束進行優化，然后，基于激光里程計對軌跡模擬，對其進行融合，進行誤差補償，改善了特定場景下偏差較大的問題。

基于DWA算法的移動機器人在障礙物環境比較復雜的環境下，難以選擇最優路徑。基于此常新新等[35]提出一種改進的DWA算法，對移動機器人避障效果進行優化，主要是通過激光雷達探尋到障礙物的方位，根據預先設計的優化方位角范圍，選取在范圍內的軌跡。改進后的算法在較為復雜的障礙物環境下通過選擇較優角度范圍，在一定程度上減少了需要評價的軌跡數目，運行效率有所提高。

3 分析和討論

本文主要對一些常用的路徑規劃算法進行總結，對一些算法的優缺點和應用場景進行概述，結果如表1所示。

表1 常用路徑規劃算法表

目前大部分的路徑規劃算法都已在相應機器人上得以應用。但在現實復雜環境中，一般的算法表現不佳，通過優化已有的常規路徑規劃算法，已在實際應用中比較廣泛，但只能在其特定的理想環境下進行，在實際的場景下，會不可避免地遇到各式各樣的問題。根據移動機器人在現實中的需求，將常規的算法在實時性、收斂速度、魯棒性或者是路徑的平滑性等某一方面或某些方面進行相應的改進，同時也要保證路徑規劃的有效性。針對算法的某一特性進行優化可以快速的提高性能，使其滿足現實需求，對算法進行特定方面的進行一般性的改進在實際中應用的較為廣泛。目前路徑規劃算法已經不僅僅局限在單個機器人，已經逐漸應用到集群機器人，以及多機器人多目標的路徑規劃上，這就提高了規劃的難度，在規劃最優路徑的同時也要將其他機器人算入其中，對實時性、有效性、準確性都有了更高的要求。

由于各種路徑規劃算法的原理不同，不同算法的應用場景也大不相同，傳統的算法具有很強的有效性，但其在實際應用中實用性較差，智能仿生算法一般在收斂速度方面較為迅速，但同時也易于陷入局部最優，單獨的算法往往不能成功應用于實際環境中，借助不同算法的優缺點成為解決問題的關鍵。目前，基于機器學習融合路徑規劃算法的表現較為優異，基于神經網絡，人工智能算法的路徑規劃算法具有很大的應用潛力。

4 結束語

本文通過研究路徑規劃算法的原理機制，分析各種算法的優缺點，對部分的改進算法進行了分析，對其應用場景進行了闡述。目前，大部分路徑算法已廣泛應用移動機器人的路徑規劃算法中，但當面臨現實多變的場景下，移動機器人的路徑規劃仍然難以滿足復雜環境中要求。因此移動機器人在路徑效率、路線的優化等問題上需要提高。同時對于不同算法的評價函數，大多都是對障礙物的表示進行不同程度的簡化，通常都是近似為矩形、圓形等較為簡單的形狀，在現實的場景下，可能因過于簡化對搜尋最優路徑存在影響。