移動機器人的路徑規劃綜述與發展趨勢

文/陳 浩 王光林 郝 詢

自主移動機器人屬于智能型機器人范疇，是集環境感知、動態決策與規劃、行為控制與執行等多種功能于一體的綜合系統。近年來，自主移動機器人技術在工業、農業、醫學、航空航天等許多領域發揮了重要作用，顯示了其廣泛的應用前景。

在移動機器人相關技術研究中，路徑規劃是一個重要的環節和組成部分。根據機器人對環境信息掌握的程度，將路徑規劃分為全局路徑規劃和局部路徑規劃。本文重點對全局路徑規劃和局部路徑規劃進行分析與總結，最后對移動機器人路徑規劃的未來發展趨勢進行了展望。

一、路徑規劃的問題概述

路徑規劃是指移動機器人按照某一性能指標（如距離、時間等）搜索一條從起始狀態到目標狀態的最優或次優路徑。根據對環境信息的把握程度可把路徑規劃分為基于先驗信息的全局路徑規劃和基于傳感器信息的局部路徑規劃。其中，從獲取障礙物信息是靜態或是動態的角度看，全局路徑規劃屬于靜態規劃（又稱離線規劃）。全局路徑規劃需要掌握所有的環境信息，根據環境地圖的所有信息進行路徑規劃；局部路徑規劃只需要有傳感器實時采集環境信息，了解環境地圖信息，然后確定出所在地圖的位置及其障礙物分布情況，從而可以選出從當前節點到某一子目標的最優路徑。

二、全局路徑規劃

1.環境建模方法

（1）自由空間法

自由空間法是用提前定義好的例如凸多邊形等常用的幾何形狀表示機器人工作空間，然后再轉換為拓撲結構上的連通圖。如圖1。

在移動機器人相關技術研究中，路徑規劃是一個重要的環節和組成部分

（2）柵格法

柵格法是將移動機器人的工作空間分解為許多網格狀的單元，這些單元一般用0、1兩個數值來表示，工作環境中的障礙物的形狀和大小是一致的，而且移動機器人在行走的過程中，障礙物的位置、形狀和大小是固定不變化的。對于移動機器人的工作環境用大小相同的柵格進行劃分，柵格大小一般根據機器人的尺寸來確定。如圖2。

（3）拓撲法

拓撲法是根據拓撲結構上的一些特征將工作環境分成許多小空間，再由小空間之間連通還是不連通的關系建立一個有拓撲結構關系的網絡。如圖3。

2.基于搜索的路徑規劃方法

（1）Dijkstra算法

Dijkstra算法從物體所在的初始點開始，訪問圖中的節點。它迭代檢查節點集中的結點，并將和該節點最靠近的尚未檢查的結點加入待檢查點集。該結點集從初始結點向外擴展，直到到達目標節點。Dijkstra算法保證能夠找到一條從初始點到目標點的最短路徑。

Dijkstra算法是一種經典的廣度優先的狀態空間搜索算法，算法會搜索整個空間直到到達目標點，這就導致了Dijkstra算法計算時間和數據量很大，而且搜索得到的大量數據對于移動機器人的運動是無用的。

（2）A★算法

A＊算法在Dijkstra算法的基礎上增加了啟發式特性，搜索的效率大大提升。A＊算法按照Dijkstra算法類似的流程運行，不同的是它能夠評估任意結點到達目標節點的代價。與Dijkstra算法選擇離初始結點最近的結點不同，它根據啟發式函數選擇離目標最近的節點。A＊算法無法保證找到最優路徑，但是速度比Dijkstra速度快很多。如圖4。

3.基于采樣的規劃方法

（1）概率路圖法

概率路圖法，是一種基于圖搜索的方法，它利用隨機采樣技術將連續空間轉換為離散空間，再利用A＊等搜索算法在路線圖上尋找路徑，以提高搜索效率。

這種方法能夠用相對較少的隨機采樣點來找到一個解，對多數問題而言，相對少的樣本足以覆蓋大部分可行空間，并且找到路徑的概率為1。但是，當采樣點太少，或者分布不合理時概率路圖法是不完備的。如圖5。

（2）快速搜索隨機樹法

快速搜索隨機樹算法是一種增量式采樣的搜索方法，該方法在應用中不需要任何參數整定，擁有良好的使用性能。

基于快速擴展隨機樹的路徑規劃算法，通過對狀態空間中的采樣點進行碰撞檢測，避免了對空間的建模，能夠有效的解決高維空間和復雜約束的路徑規劃問題。

它以一個初始點作為根結點，通過隨機采樣增加葉子結點的方式，生成一個隨機擴展樹，當隨機樹中的葉子結點包含了目標結點或進入了目標區域，便可以在隨機樹中找到一條由初始點到目標點的路徑。該方法的特點是能夠快速有效地搜索高維空間，通過狀態空間的隨機采樣點，把搜索導向空白區域，從而尋找到一條從起始點到目標點的規劃路徑，適合解決多移動機器人在復雜環境中的路徑規劃問題。如圖6。

圖1 自由空間法

圖2 柵格法

圖3 拓撲法

圖4 A＊路徑規劃算法

三、局部路徑規劃

1.人工勢場法

人工勢場法是由哈提卜提出的一種虛擬的力場法。假設移動機器人在空間中運動的時候受到了引力和斥力的共同作用，這是人工勢場法的基本思想。其中障礙物具有排斥勢場，對移動機器人產生斥力，移動機器人離障礙物越近，斥力越大。目標具有吸引勢場，對移動機器人產生引力，移動機器人離目標越近引力越小。

引力和斥力的合力根據牛頓定律會對移動機器人產生加速度，從而控制移動機器人的運動方向和速度等。在移動機器人上選擇一些用來測試的點，計算這些測試點與各個障礙物之間的排斥勢和目標之間的吸引勢，對獲得的這些排斥勢和吸引勢相加。最后，通過計算勢函數梯度下降的方向來找到一條無碰路徑。如圖7。

人工勢場法適合應用在環境不斷變化的情況。這種方法有利于底層的、在線的控制移動機器人的運動，而且構造起來簡單，在運動路線的平滑控制方面和在線避免與障礙物相撞方面應用越來越廣。

圖5 概率路圖規劃算法

圖6 RRT算法路徑規劃

圖7 人工勢場法

2.動態窗口法

動態窗口法DWA是在曲率速度法基礎上提出的，將移動機器人的位置控制轉化為速度控制，將避障問題描述為速度空間帶約束的優化問題。該算法在速度空間中采樣多組速度，將有限的速度和加速度的運動約束考慮到動態窗口的設計中，模擬移動機器人以一定的速度在一定時間內的運動軌跡。

在得到運動軌跡后，通過一個評價函數對這些軌跡打分，選取最優軌跡對應的速度來驅動移動機器人的運動。

動態窗口法和A＊算法進行融合，構造一種估計全局最優路徑評價函數，可實時避障，路徑更加平滑，曲率變化的連續性以及可輸出的運動控制參數更符合移動機器人動力學控制。動態窗口法充分考慮了移動機器人的物理限制、環境約束以及當前速度等因素，得到的路徑安全可靠，適用于局部路徑規劃。如圖8。

圖8 DWA規劃算法

四、自主路徑規劃的發展趨勢

隨著科學技術的不斷發展，自主路徑規劃技術面對的環境將更為復雜多變。這就要求路徑規劃算法具有迅速響應復雜環境變化的能力。這不是目前單個或單方面算法所能解決的問題，因此在未來的路徑規劃技術中，除了研究發現新的路徑規劃算法外，還有以下幾個方面值得關注：

1.局部路徑規劃與全局路徑規劃相結合

全局路徑規劃一般是建立在已知環境信息的基礎上，適應范圍相對有限。局部路徑規劃能適應未知環境，但有時反應速度不快，對局部路徑規劃系統品質要求較高，因此，如果把兩者結合即可達到更好的規劃效果。

2.傳統路徑規劃方法與新的智能方法相結合

近年來，一些新的智能技術逐漸被引入到自主路徑規劃中來，也促使了各種方法的融合發展，例如：人工勢場法與神經網絡、模糊控制的結合，以及模糊控制與人工神經網絡、遺傳算法及行為控制之間的結合等。

3.多傳感器信息融合用于局部路徑規劃

移動機器人在動態環境中進行路徑規劃所需的信息都是從傳感器獲得，單一傳感器難以保證輸入信息的準確性與可靠性，多傳感器所獲得的信息具有冗余性、互補性、實時性，且可快速并行分析現場環境。目前的方法有：采用概率方法表示信息的加權平均法、貝葉斯估計法、卡爾曼濾波法、統計決策理論法、仿效生物神經網絡的信息處理方法、人工神經網絡法等。

4.局部路徑規劃與動態環境路徑規劃相結合

類似足球機器人比賽，需要考慮目標點情況。這類規劃由于要考慮機器人及目標點狀態，使得規劃問題更為復雜，同時也賦予移動機器人更高的自主性以及智能水平。

5.多智能移動機器人協調規劃

該智能技術正在逐漸成為新的研究熱點，受到業內人士的廣泛關注。由于障礙物與移動機器人數目的增加，極大地提高了自主路徑規劃的難度，這將是一個更加貼近現實的研究課題，也是移動機器人技術亟需拓展的領域。