文/陳 浩 王光林 郝 詢

自主移動機器人屬于智能型機器人范疇，是集環(huán)境感知、動態(tài)決策與規(guī)劃、行為控制與執(zhí)行等多種功能于一體的綜合系統(tǒng)。近年來，自主移動機器人技術(shù)在工業(yè)、農(nóng)業(yè)、醫(yī)學(xué)、航空航天等許多領(lǐng)域發(fā)揮了重要作用，顯示了其廣泛的應(yīng)用前景。

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

一、路徑規(guī)劃的問題概述

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

二、全局路徑規(guī)劃

1.環(huán)境建模方法

（1）自由空間法

自由空間法是用提前定義好的例如凸多邊形等常用的幾何形狀表示機器人工作空間，然后再轉(zhuǎn)換為拓?fù)浣Y(jié)構(gòu)上的連通圖。如圖1。

在移動機器人相關(guān)技術(shù)研究中，路徑規(guī)劃是一個重要的環(huán)節(jié)和組成部分

（2）柵格法

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

（3）拓?fù)浞?/p>

拓?fù)浞ㄊ歉鶕?jù)拓?fù)浣Y(jié)構(gòu)上的一些特征將工作環(huán)境分成許多小空間，再由小空間之間連通還是不連通的關(guān)系建立一個有拓?fù)浣Y(jié)構(gòu)關(guān)系的網(wǎng)絡(luò)。如圖3。

2.基于搜索的路徑規(guī)劃方法

（1）Dijkstra算法

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

Dijkstra算法是一種經(jīng)典的廣度優(yōu)先的狀態(tài)空間搜索算法，算法會搜索整個空間直到到達(dá)目標(biāo)點，這就導(dǎo)致了Dijkstra算法計算時間和數(shù)據(jù)量很大，而且搜索得到的大量數(shù)據(jù)對于移動機器人的運動是無用的。

（2）A★算法

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

3.基于采樣的規(guī)劃方法

（1）概率路圖法

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

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

（2）快速搜索隨機樹法

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

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

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

圖1 自由空間法

圖2 柵格法

圖3 拓?fù)浞?/p>

圖4 A＊路徑規(guī)劃算法

三、局部路徑規(guī)劃

1.人工勢場法

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

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

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

圖5 概率路圖規(guī)劃算法

圖6 RRT算法路徑規(guī)劃

圖7 人工勢場法

2.動態(tài)窗口法

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

在得到運動軌跡后，通過一個評價函數(shù)對這些軌跡打分，選取最優(yōu)軌跡對應(yīng)的速度來驅(qū)動移動機器人的運動。

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

圖8 DWA規(guī)劃算法

四、自主路徑規(guī)劃的發(fā)展趨勢

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

1.局部路徑規(guī)劃與全局路徑規(guī)劃相結(jié)合

全局路徑規(guī)劃一般是建立在已知環(huán)境信息的基礎(chǔ)上，適應(yīng)范圍相對有限。局部路徑規(guī)劃能適應(yīng)未知環(huán)境，但有時反應(yīng)速度不快，對局部路徑規(guī)劃系統(tǒng)品質(zhì)要求較高，因此，如果把兩者結(jié)合即可達(dá)到更好的規(guī)劃效果。

2.傳統(tǒng)路徑規(guī)劃方法與新的智能方法相結(jié)合

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

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

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

4.局部路徑規(guī)劃與動態(tài)環(huán)境路徑規(guī)劃相結(jié)合

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

5.多智能移動機器人協(xié)調(diào)規(guī)劃

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