移動(dòng)機(jī)器人的路徑規(guī)劃綜述與發(fā)展趨勢(shì)

文/陳 浩 王光林 郝 詢

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

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

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

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

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

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

（1）自由空間法

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

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

（2）柵格法

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

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

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

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

（1）Dijkstra算法

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

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

（2）A★算法

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

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

（1）概率路圖法

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

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

（2）快速搜索隨機(jī)樹法

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

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

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

圖1 自由空間法

圖2 柵格法

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

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

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

1.人工勢(shì)場(chǎng)法

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

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

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

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

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

圖7 人工勢(shì)場(chǎng)法

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

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

在得到運(yùn)動(dòng)軌跡后，通過(guò)一個(gè)評(píng)價(jià)函數(shù)對(duì)這些軌跡打分，選取最優(yōu)軌跡對(duì)應(yīng)的速度來(lái)驅(qū)動(dòng)移動(dòng)機(jī)器人的運(yùn)動(dòng)。

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

圖8 DWA規(guī)劃算法

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

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

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

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

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

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

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

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

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

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

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

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