李曉旭，馬興錄，王先鵬

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院，山東 青島 266061)

0 引言

隨著科技的發(fā)展與產(chǎn)業(yè)變革，移動(dòng)機(jī)器人被廣泛應(yīng)用于生產(chǎn)與生活的各個(gè)領(lǐng)域之中。由于機(jī)器人工作環(huán)境的不確定性與復(fù)雜性，如何快速準(zhǔn)確地搜索出一條由初始狀態(tài)至目標(biāo)狀態(tài)的無碰撞路徑成為當(dāng)前機(jī)器人避障的技術(shù)難點(diǎn)[1-2]。由于機(jī)器人任務(wù)的不同，評(píng)價(jià)路徑的指標(biāo)也存在一定的差異，一般通過最短路徑、最短時(shí)間、最小能量消耗、安全性最高等指標(biāo)評(píng)價(jià)選擇最佳路徑。性能優(yōu)越的路徑規(guī)劃算法往往能夠在不確定的復(fù)雜環(huán)境中規(guī)劃出適合機(jī)器人運(yùn)動(dòng)的高效路徑，這不僅能提高移動(dòng)機(jī)器人的工作效率，還能降低移動(dòng)機(jī)器人損耗。路徑規(guī)劃算法作為移動(dòng)機(jī)器人的關(guān)鍵技術(shù)之一，已成為國內(nèi)外研究熱點(diǎn)[3]。

本文對(duì)主流的移動(dòng)機(jī)器人路徑規(guī)劃算法進(jìn)行總結(jié)綜述，根據(jù)移動(dòng)機(jī)器人路徑規(guī)劃算法的特性，將其劃分為傳統(tǒng)規(guī)劃算法、智能規(guī)劃算法以及基于采樣的規(guī)劃算法。隨后對(duì)各類算法進(jìn)一步劃分，并介紹各種算法的原理以及其自身的局限性，同時(shí)總結(jié)分析各類算法的優(yōu)缺點(diǎn)。最后，根據(jù)目前移動(dòng)機(jī)器人路徑規(guī)劃算法的研究現(xiàn)狀做出進(jìn)一步展望，分析其發(fā)展趨勢。移動(dòng)機(jī)器人路徑規(guī)劃主流算法如圖1所示。

圖1 移動(dòng)機(jī)器人路徑規(guī)劃算法分類圖

1 傳統(tǒng)規(guī)劃算法

傳統(tǒng)規(guī)劃算需要在結(jié)構(gòu)化的環(huán)境內(nèi)對(duì)障礙物進(jìn)行準(zhǔn)確地建模描述。該類算法依賴環(huán)境的顯示表達(dá)。

1.1 人工勢場法

Khatib在1985年提出了人工勢場法(Artificial potential field，APF)[4]，用于移動(dòng)機(jī)器人路徑規(guī)劃實(shí)現(xiàn)避障功能。該算法借助物理學(xué)中“勢場”的概念，將障礙物等價(jià)位斥力源，對(duì)移動(dòng)機(jī)器人產(chǎn)生“排斥力”；將目標(biāo)點(diǎn)等價(jià)位引力源，對(duì)移動(dòng)機(jī)器人產(chǎn)生“引力”。機(jī)器人在移動(dòng)的過程中，“引力”與“斥力”不斷發(fā)生變化，機(jī)器人通過本身所受的合力實(shí)時(shí)改變移動(dòng)方向，實(shí)現(xiàn)移動(dòng)過程中躲避障礙物。該方法實(shí)時(shí)性高，且實(shí)現(xiàn)結(jié)構(gòu)較為簡單，因此有一定的應(yīng)用價(jià)值。人工勢場法示意圖如圖2所示。

圖2 人工勢場法示意圖

人工勢場法自身具有局限性。當(dāng)移動(dòng)機(jī)器人處于障礙物附近時(shí)，規(guī)劃的路徑會(huì)產(chǎn)生“振蕩”現(xiàn)象，這影響機(jī)器人在運(yùn)行過程中的穩(wěn)定性[5]。該方法容易出現(xiàn)局部極小值，例如當(dāng)障礙物位于移動(dòng)機(jī)器人與目標(biāo)點(diǎn)的中心位置時(shí)，移動(dòng)機(jī)器人所受“引力”與“斥力”相互抵消，此時(shí)機(jī)器人無法確定移動(dòng)方向，進(jìn)而導(dǎo)致路徑規(guī)劃失敗。為此許多學(xué)者在不同方向上對(duì)此方法作出改進(jìn)。Li G通過設(shè)置虛擬局部目標(biāo)的方法克服人工勢場法中的振蕩效應(yīng)[6]。叢玉華等[7]通過設(shè)置探測窗口、距離影響因子的方法解決了軌跡振蕩以及軌跡不可達(dá)問題。邱博[8]等在斥力勢能函數(shù)中引入變?cè)鲆嫦禂?shù)，解決了振蕩問題。王兵根據(jù)環(huán)境信息動(dòng)態(tài)設(shè)置虛擬目標(biāo)點(diǎn)，快速逃離路徑局部極小值點(diǎn)[9]。石為人[10]針對(duì)勢力場局部極小值問題，提出一種拼接局部極小值區(qū)域分散障礙物的方法，實(shí)驗(yàn)證明，該方法較好地解決了局部極小值問題。Liu等[11]提出一種雙勢場融合自適應(yīng)路徑規(guī)劃算法，提高了機(jī)器人對(duì)不同速度與不同障礙物場景的適應(yīng)能力。

1.2 Bug算法

圖3 Bug算法示意圖

Bug算法結(jié)構(gòu)較為簡單，但使用該算法時(shí)，移動(dòng)機(jī)器人在運(yùn)動(dòng)過程中僅依靠最新獲得的數(shù)據(jù)，當(dāng)傳感器提供的信息不足時(shí)，容易導(dǎo)致規(guī)劃失敗。針對(duì)Bug算法的缺陷，學(xué)者們做出了很多研究。Bug2算法[13]對(duì)“邊界跟蹤”過程作出改進(jìn)，一定程度上降低了移動(dòng)機(jī)器人的路徑代價(jià)。Kamon提出了Tangent Bug算法[14]，該算法引入路徑代價(jià)函數(shù)，通過范圍探測器輔助，動(dòng)態(tài)選擇機(jī)器人移動(dòng)方向，進(jìn)一步減少了移動(dòng)機(jī)器人“邊界追蹤”過程中產(chǎn)生的代價(jià)。Dist-Bug[15]算法對(duì)遇到障礙物時(shí)，移動(dòng)機(jī)器人繞行方向問題作出了改進(jìn)。彭艷[16]提出了Multi-Bug算法，該算法加入爬蟲分裂規(guī)則以及爬蟲死亡條件判斷規(guī)則，當(dāng)移動(dòng)機(jī)器人遇到障礙物時(shí)，通過爬蟲分裂規(guī)則并行計(jì)算路徑代價(jià)尋找最優(yōu)路徑，實(shí)驗(yàn)證明該算法較Dist-Bug算法在降低路徑代價(jià)、實(shí)時(shí)性、通用性等方面皆有一定的提高。蔡存成[17]等在Bug算法中加入“避行”過程，通過避障轉(zhuǎn)向角索引圖與轉(zhuǎn)向時(shí)機(jī)提前量控制移動(dòng)平臺(tái)躲避障礙物，并在“邊界跟蹤”過程中通過模糊控制器控制移動(dòng)平臺(tái)繞行的精確度。

1.3 向量場直方圖法

Borenstein于1991年提出了向量場直方圖法(Vector filed histogram，VFH)[18]。該方法將機(jī)器人周圍的環(huán)境用直方圖表示，因此該方法對(duì)處理傳感器和建模誤差要求非常高。該方法首先構(gòu)建一個(gè)二維笛卡爾直方圖柵格，并根據(jù)傳感器數(shù)據(jù)實(shí)時(shí)更新柵格圖。然后通過減少機(jī)器人當(dāng)前位置周圍的笛卡爾直方圖，構(gòu)建一維極坐標(biāo)直方圖。最后通過極坐標(biāo)直方圖上的候選波谷確定機(jī)器人移動(dòng)方向。向量場直方圖如圖4所示，該極坐標(biāo)系的兩坐標(biāo)軸分別表示以機(jī)器人為圓心感知到障礙物的角度、對(duì)應(yīng)方向上障礙物可能存在的概率，一般情況下，極坐標(biāo)直方圖存在波峰與波谷，波峰表示障礙物密度較高，波谷表示障礙物密度較低，障礙物密度低于給定閾值的波谷成為候選波谷。

圖4 向量場直方圖

VFH算法具有可靠性高、計(jì)算效率高、魯棒性強(qiáng)等優(yōu)點(diǎn)，但是該算法不完備，在狹窄區(qū)域中，容易陷入局部極小值。Ulrich提出了VFH+算法[19]，該算法考慮了機(jī)器人的體型，提高了算法的通用性；通過閾值滯后增加了軌跡的平滑度；添加成本函數(shù)表征算法性能。Ulrich提出了VFH*算法[20]，該算法通過前瞻距離，探測并選擇機(jī)器人的最佳移動(dòng)方向。婁虎[21]等針對(duì)水面無人艇雷達(dá)避障問題，提出了一種自調(diào)節(jié)VFH+算法。改進(jìn)后的算法能夠根據(jù)無人船所處的位置對(duì)障礙物閾值進(jìn)行實(shí)時(shí)更新，提高了無人船的靈活性。

1.4 柵格法

柵格(Grid map，GM)法將機(jī)器人所處的環(huán)境通過某種方法劃分為具有局部環(huán)境信息的網(wǎng)格單元，即柵格[22]。如圖5所示，柵格可分為自由柵格與占用柵格兩種，其中占用柵格包含環(huán)境中的障礙物信息。將自由柵格按照一定的順序構(gòu)成連通圖，并采用搜索算法在該連通圖上構(gòu)建一條由初始柵格至目標(biāo)柵格的無碰撞路徑，記為規(guī)劃路徑[23]。柵格法在規(guī)劃速度方面性能優(yōu)越，但其規(guī)劃效率受柵格精度的制約。柵格法已被廣泛應(yīng)用于移動(dòng)機(jī)器人，柵格法常用的搜索算法有Dijkstra最短路徑算法、A*算法、D*算法等。

圖5 柵格示意圖

1.4.1 Dijkstra算法

1973年Johnson提出了Dijkstra算法[24]。Dijkstra算法多用于求解有權(quán)圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短距離。該算法通過數(shù)組D保存起始點(diǎn)至各個(gè)頂點(diǎn)的最短距離，通過集合T保存已遍歷的最短路徑對(duì)應(yīng)的頂點(diǎn)。執(zhí)行算法時(shí)，通過迭代的方式，每次從集合T之外的頂點(diǎn)中求取距離起始點(diǎn)距離最小的頂點(diǎn)，將該點(diǎn)加入集合T中，并通過該點(diǎn)刷新數(shù)組D中的值，直至集合T中包含所有頂點(diǎn)。

Dijkstra算法具有很強(qiáng)的魯棒性，且其能計(jì)算出兩點(diǎn)之間的最優(yōu)路徑解，但是該算法是無向搜索算法，隨著節(jié)點(diǎn)數(shù)量的增加，該算法的計(jì)算效率降低?；贒ijkstra算法的缺點(diǎn)，學(xué)者作出了許多改進(jìn)。目前，有研究通過改變有權(quán)圖中的權(quán)重標(biāo)準(zhǔn)改善Dijkstra算法的性能[25]，但是多數(shù)研究中通過限定搜索區(qū)域提高Dijkstra算法的搜索效率。例如，張超等[26]將搜索區(qū)域縮小為以起始點(diǎn)和目標(biāo)點(diǎn)為對(duì)角線的矩形區(qū)域內(nèi)，當(dāng)該區(qū)域搜索不到路徑時(shí)，逐漸擴(kuò)大采樣區(qū)域；宮金良等[27]按照路徑權(quán)值、時(shí)間權(quán)值分別創(chuàng)建鄰接矩陣，縮小了迭代過程中的最小路徑搜索域和最優(yōu)路徑更新域；郭夢詩等[28]用連通域表示障礙物區(qū)域，并通過鏈表存儲(chǔ)連通域中相鄰節(jié)點(diǎn)的距離信息，使搜索范圍保持在避障空間內(nèi)；賈文友等[29]將起始點(diǎn)、目標(biāo)點(diǎn)與障礙物通過數(shù)學(xué)方式構(gòu)造凸包模型，將全地圖路徑求解問題轉(zhuǎn)換為求解凸包內(nèi)起止點(diǎn)至目標(biāo)點(diǎn)最短路徑問題。

1.4.2 A*算法

1972年Hart等人提出了A*算法[30]。A*算法本質(zhì)上是一種啟發(fā)式搜索算法，即通過一定的評(píng)價(jià)指標(biāo)指引算法運(yùn)行。A*算法引入了代價(jià)函數(shù)，并將其作為評(píng)價(jià)指標(biāo)，代價(jià)函數(shù)如公式(1)所示。

f(n)=g(n)+h(n)

(1)

其中：g(n)代表節(jié)點(diǎn)n至起點(diǎn)的代價(jià)，是當(dāng)前的實(shí)際代價(jià)；h(n)代表節(jié)點(diǎn)n至目標(biāo)點(diǎn)的代價(jià)，是估計(jì)代價(jià)，一般通過節(jié)點(diǎn)n至目標(biāo)點(diǎn)估計(jì)代價(jià)的額計(jì)算方法有兩種：歐氏距離、曼哈頓距離；g(n)代表節(jié)點(diǎn)n的總代價(jià)。

A*算法的優(yōu)點(diǎn)是計(jì)算方式簡單、規(guī)劃路徑短等，但該方法計(jì)算量大，規(guī)劃路徑往往拐點(diǎn)較多。針對(duì)路徑不平滑問題，Min Haitao[31]在啟發(fā)式函數(shù)設(shè)計(jì)中加入了路徑曲率的代價(jià)，提高了路徑的平滑性。槐創(chuàng)鋒等[32]將傳統(tǒng)A*算法的搜索領(lǐng)域進(jìn)行擴(kuò)展，并通過優(yōu)化搜索角度的方式提高了路徑平滑度。也有一些研究通過對(duì)生成路徑進(jìn)行優(yōu)化，增加路徑平滑度。例如文獻(xiàn)[33-36]結(jié)合Floyd算法思想優(yōu)化路徑；文獻(xiàn)[37]通過B樣條曲線平滑路徑。針對(duì)傳統(tǒng)A*算法計(jì)算效率問題，鄒文等[38]在柵格地圖上建立拓?fù)涞貓D，通過A*算法在柵格地圖上獲取初始全局路徑，然后結(jié)合Floyd算法思想在拓?fù)涞貓D中對(duì)初始全局路徑進(jìn)行優(yōu)化。通過該種方式，在優(yōu)化過程中減少了大量計(jì)算，提高了其優(yōu)化效率。其次，通過增加狀態(tài)函數(shù)優(yōu)化傳統(tǒng)的動(dòng)態(tài)窗口算法，并將其應(yīng)用于局部路徑規(guī)劃的避障與移動(dòng)，這也提高了獲取路徑的速度。還有一些研究通過優(yōu)化評(píng)價(jià)函數(shù)提高算法計(jì)算效率[39-40]，也有很多研究通過融合A*算法與動(dòng)態(tài)窗口提高算法速度，例如文獻(xiàn)[32]、文獻(xiàn)[33]、文獻(xiàn)[36]、文獻(xiàn)[40]。

1.4.3 D*算法

1994年Stentz提出了D*算法[41]，該算法由A*算法發(fā)展而來，適用于環(huán)境未知的或者環(huán)境存在動(dòng)態(tài)變化的場景。D*算法對(duì)A*算法做了兩個(gè)重要改進(jìn)。

1)出現(xiàn)動(dòng)態(tài)障礙物時(shí)，D*算法可以更新動(dòng)態(tài)障礙物附近的柵格信息。

2)D*算法的啟發(fā)函數(shù)可傳遞。當(dāng)中心柵格向周圍柵格擴(kuò)展時(shí)，可將其啟發(fā)值傳遞給周圍鄰點(diǎn)。

D*算法的代價(jià)公式由A*函數(shù)發(fā)展而來，如公式(2)所示。

F(s)=G(s)+H(s)

(2)

其中:G(s)為起始點(diǎn)至s的代價(jià)值，H(s)為啟發(fā)值，其計(jì)算方式如公式(3)所示。

(3)

式中，s′為s的拓展節(jié)點(diǎn)，H(s′)為s′的啟發(fā)值，C(s,s′)為相鄰節(jié)點(diǎn)的代價(jià)值，sgoal為目標(biāo)點(diǎn)。進(jìn)行柵格擴(kuò)展的過程中，被擴(kuò)展節(jié)點(diǎn)s的啟發(fā)值由其拓展點(diǎn)s′的代價(jià)值以及拓展點(diǎn)s′的啟發(fā)值計(jì)算得來。D*算法啟發(fā)函數(shù)示意圖如圖6所示。

圖6 啟發(fā)函數(shù)示意圖

D*算法對(duì)A*算法有一定的提升，其搜索路徑的速度更快、路徑更為優(yōu)異，但是D*算法并沒有改善路徑曲折的缺點(diǎn)，而且D*算法規(guī)劃的路徑貼近障礙物邊緣。與A*算法類似，對(duì)于D*算法的改進(jìn)主要集中于兩個(gè)方面：提高路徑平滑度、提高搜索效率。一些研究通過縮小搜索區(qū)域提高算法的搜索效率，例如文獻(xiàn)[42]、文獻(xiàn)[43]引入Voronoi圖法在一定程度上縮小搜索路徑；有一些研究通過優(yōu)化節(jié)點(diǎn)選擇方式等方法，對(duì)D*算法進(jìn)行單次優(yōu)化，提高算法搜索效率，例如文獻(xiàn)[42]引入二級(jí)子節(jié)點(diǎn)概念放棄擴(kuò)展無用節(jié)點(diǎn)、文獻(xiàn)[44]引入跳點(diǎn)搜索與元胞鄰居結(jié)構(gòu)跳過對(duì)無用節(jié)點(diǎn)的擴(kuò)展、文獻(xiàn)[45]通過導(dǎo)向函數(shù)限制單次搜索節(jié)點(diǎn)范圍；還有一些研究通過更改代價(jià)函數(shù)縮小搜索空間，例如文獻(xiàn)[48]在代價(jià)函數(shù)中增加碰撞因子，放棄在可能存在碰撞的區(qū)域內(nèi)搜索路徑，一定程度上提高了路徑搜索效率。對(duì)于路徑平滑的改進(jìn)思想主要有兩種：路徑生成中考慮平滑處理、路徑生成后進(jìn)行平滑處理。在路徑生成過程種對(duì)路徑進(jìn)行平滑處理主要通過更改代價(jià)函數(shù)實(shí)現(xiàn)，例如，文獻(xiàn)[43]增加產(chǎn)生尖角的節(jié)點(diǎn)的啟發(fā)值，減少拐點(diǎn)；文獻(xiàn)[45]在原有代價(jià)函數(shù)基礎(chǔ)上增加平滑度函數(shù)，增加路徑平滑度。對(duì)生成路徑的平滑工作一般通過借助數(shù)學(xué)理論實(shí)現(xiàn)，例如文獻(xiàn)[46]、文獻(xiàn)[47]引入三次B樣條對(duì)生成的路徑進(jìn)行平滑處理。

1.5 Voronoi圖法

Voronoi圖法采用路徑距離盡可能遠(yuǎn)的方式劃分自由空間[48-49]。Voronoi圖法的核心思想是通過一系列種子點(diǎn)將空間劃分為若干個(gè)子區(qū)域，每個(gè)子區(qū)域中點(diǎn)到該區(qū)域?qū)?yīng)的種子節(jié)點(diǎn)的距離小于它們到其他種子節(jié)點(diǎn)的距離。通過該特性，將空間中障礙物邊界取做種子節(jié)點(diǎn)，則每個(gè)子區(qū)域的邊界都可以作為移動(dòng)機(jī)器人無碰撞路徑的一部分。將機(jī)器人的初始點(diǎn)和目標(biāo)點(diǎn)分別連接到Voronoi圖上，采用搜索算法可獲得由初始點(diǎn)至目標(biāo)點(diǎn)的無碰撞路徑。

Voronoi圖能夠使機(jī)器人與障礙物保持一定的距離，這提高了機(jī)器人運(yùn)行的安全性，但是該方法獲取的路徑代價(jià)較大，且在高維空間的規(guī)劃能力較差。針對(duì)移動(dòng)機(jī)器人在動(dòng)態(tài)環(huán)境中的路徑規(guī)劃問題，Ayawli等[50]提出一種基于Voronoi圖和計(jì)算幾何技術(shù)的動(dòng)態(tài)路徑規(guī)劃算法。該算法使用Voronoi圖以幾何形狀計(jì)算路線圖，并將節(jié)點(diǎn)添加到初始路線圖節(jié)點(diǎn)以計(jì)算用于重新規(guī)劃的新路徑，在后續(xù)重新規(guī)劃路徑值前，失效節(jié)點(diǎn)被丟棄，從而節(jié)省時(shí)間與空間資源。實(shí)驗(yàn)結(jié)果表明，該算法可以在復(fù)雜和動(dòng)態(tài)的環(huán)境中實(shí)現(xiàn)安全、更少的路徑成本和時(shí)間的路徑規(guī)劃計(jì)算。Hu等[51]提出一種深度學(xué)習(xí)強(qiáng)化的基于Voronoi的多機(jī)器人協(xié)同探索算法。該算法通過Voronoi圖法動(dòng)態(tài)劃分環(huán)境區(qū)域，然后通過將分區(qū)中不同的目標(biāo)位置分配給各個(gè)機(jī)器人來最小化重復(fù)的探索區(qū)域。實(shí)驗(yàn)結(jié)果表明，該算法可以確保每個(gè)機(jī)器人探索區(qū)域時(shí)而不會(huì)與其他機(jī)器人發(fā)生沖突，從而最大限度地減少任務(wù)完成時(shí)間并節(jié)省更多資源和能源。

由上述可知，傳統(tǒng)的移動(dòng)機(jī)器人路徑規(guī)劃算法需要對(duì)環(huán)境進(jìn)行建模與描述。因此，隨著環(huán)境復(fù)雜度的增加傳統(tǒng)路徑規(guī)劃算法的搜索效率將大大降低。

2 智能規(guī)劃算法

智能算法具備一定的學(xué)習(xí)能力，對(duì)環(huán)境的適應(yīng)能力強(qiáng)，能夠在規(guī)劃中不斷獲取新的信息用于優(yōu)化路徑。

2.1 蟻群算法

1991年Colorni與Dorigo提出了蟻群算法(ACO，ant colony optimization)[52]，該算法是一種仿生學(xué)算法，受螞蟻覓食行為啟發(fā)而來。螞蟻覓食偏向于走信息素高的路徑，螞蟻覓食示意圖如圖7所示。蟻群算法被廣泛應(yīng)用于移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃中。

圖7 螞蟻覓食示意圖

蟻群算法雖然具有較高的魯棒性，但是該算法容易出現(xiàn)局部最優(yōu)問題。針對(duì)該缺點(diǎn)，許多學(xué)者對(duì)蟻群算法作出改進(jìn)。Sangeetha等[53]提出一種基于智能增益的蟻群路徑規(guī)劃算法并將其應(yīng)用于無人地面車輛(UGV,unmanned ground vehicles)。當(dāng)UGV遇到障礙物時(shí)，會(huì)在障礙物周圍構(gòu)建許多路徑，因此需要耗費(fèi)大量時(shí)間選擇最優(yōu)路徑。該算法通過消除需要穿越障礙物周圍所有的路徑減少能量。實(shí)驗(yàn)結(jié)果證明，該算法相對(duì)于傳統(tǒng)ACO算法在獲取路徑速度上有一定的提升，但是該方法對(duì)路徑代價(jià)的優(yōu)化效果不明顯?；诖它c(diǎn)，陳禮琪[54]在文獻(xiàn)[53]的基礎(chǔ)上對(duì)ACO算法作出了改進(jìn)。該算法通過更改轉(zhuǎn)移概率公式，減少螞蟻陷入死區(qū)間，即解決了局部極小值問題；通過增益函數(shù)更改信息素函數(shù)，提高算法搜索效率。實(shí)驗(yàn)結(jié)果證明，與傳統(tǒng)ACO算法相比，該算法不僅提高了算法的搜索效率，還降低了路徑代價(jià)。對(duì)于蟻群算法優(yōu)化問題，一些研究通過優(yōu)化信息素更新方式提高算法效率[54-57]；一些研究通過算法融合彌補(bǔ)ACO算法缺陷[58-61]。

蟻群算法采用分布式計(jì)算方式，對(duì)多個(gè)個(gè)體同時(shí)計(jì)算，每個(gè)個(gè)體在實(shí)時(shí)感受環(huán)境變化的同時(shí)，通過釋放信息素改變周圍環(huán)境。蟻群算法的正反饋機(jī)制使得個(gè)體逐漸向信息素高的地方靠攏，這使該算法在搜索路徑的過程中不斷收斂。但是該算法中，初始信息素值相同，因此在選擇下一節(jié)點(diǎn)是傾向于隨機(jī)選擇，這導(dǎo)致該算法需要較長時(shí)間才能發(fā)揮正反饋?zhàn)饔?，從而降低了算法收斂速度。?dāng)蟻群算法獲得的初始解為次優(yōu)解時(shí)，正反饋機(jī)制很容易使得次優(yōu)解占據(jù)優(yōu)勢，即使得算法陷入局部最優(yōu)，而且難以逃出局部最優(yōu)。另外，蟻群算法參數(shù)眾多且具有一定的關(guān)聯(lián)性，通過調(diào)整參數(shù)可以提高蟻群算法的性能，但是參數(shù)的調(diào)整依賴于經(jīng)驗(yàn)和試錯(cuò)。因此，對(duì)于蟻群算法的優(yōu)化除了上述研究的改進(jìn)外，還可以對(duì)信息素的初始化方式進(jìn)行改進(jìn)，為算法提供較好的探索方向，不僅可以解決局部最優(yōu)問題，還可以提高算法收斂速度。另外，對(duì)蟻群算法的結(jié)構(gòu)進(jìn)行優(yōu)化也具有重要意義，通過改進(jìn)參數(shù)的關(guān)聯(lián)方式、對(duì)參數(shù)進(jìn)行優(yōu)化，可以增加算法的可調(diào)性，提高算法優(yōu)化能力。

2.2 遺傳算法

1958年，Bremermann首次提出遺傳算法(GA，genetic algorithm)概念[62]。遺傳算法是一種模仿生物體在繁衍后代過程中自然遺傳、進(jìn)化的全局優(yōu)化算法，主要包括路徑編碼、構(gòu)建適應(yīng)度函數(shù)等過程。該算法可以并行地對(duì)解空間的不同區(qū)域進(jìn)行搜索，使得搜索趨于最優(yōu)解，從而克服傳統(tǒng)優(yōu)化算法容易陷入局部極小值的缺點(diǎn)。該算法被廣泛應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃場景中。

遺傳算法運(yùn)算速率較低，且在運(yùn)算過程中占用大量計(jì)算機(jī)資源，這也是制約其發(fā)展的主要因素。針對(duì)遺傳算法的改進(jìn)問題，學(xué)者們做了大量研究。針對(duì)傳統(tǒng)遺傳算法收斂速率慢、局部搜索能力差問題，王豪等[63]提出一種改進(jìn)的自適應(yīng)遺傳算法。該算法通過改進(jìn)適應(yīng)度評(píng)估指標(biāo)與輪盤賭選擇方法提高了算法的搜索效率。實(shí)驗(yàn)表明，該算法獲得的平均路徑比傳統(tǒng)遺傳算法縮短了9.9%，且算法迭代次數(shù)也相應(yīng)地減少。針對(duì)遺傳算法局部局部極小值問題，王吉岱等[64]提出了一種模糊自適應(yīng)遺傳算法，該算法結(jié)合模糊邏輯算法動(dòng)態(tài)自適應(yīng)調(diào)整交叉和變異算子。另外，在適應(yīng)度函數(shù)中引入余弦函數(shù)平滑度評(píng)價(jià)因子，減少了路徑的拐點(diǎn)，提高了路徑的平滑度。實(shí)驗(yàn)表明，該算法與自適應(yīng)遺傳算法相比，收斂速度更快，且銳角拐彎次數(shù)減少了45.16%。針對(duì)傳統(tǒng)遺傳算法局部最優(yōu)問題，Qu等[65]通過協(xié)同進(jìn)化機(jī)制改進(jìn)遺傳算法。該算法通過改進(jìn)遺傳算子與適應(yīng)度函數(shù)，解決了遺傳算法局部最優(yōu)解問題并提高了收斂速度；另外，通過協(xié)同機(jī)制避免了機(jī)器人之間的碰撞，使得該算法可以應(yīng)用于多機(jī)器人路徑規(guī)劃。Nazarahari等[66]提出一種增強(qiáng)遺傳算法結(jié)合，該算法通過5個(gè)定制的交叉和變異算子，解決了傳統(tǒng)遺傳算法初始解迭代多次無法獲取最優(yōu)解問題，另外該算法增加了碰撞消除算子，使其可以應(yīng)用于多移動(dòng)機(jī)器人路徑規(guī)劃中。

遺傳算法與蟻群算法類似，都是從群體的角度出發(fā)，對(duì)多個(gè)個(gè)體并行計(jì)算，在一定程度上提高了一定效率。該算法使用概率方式進(jìn)行迭代，具有一定的隨機(jī)性，而且在搜索過程中使用評(píng)價(jià)函數(shù)啟發(fā)，實(shí)現(xiàn)過程相對(duì)簡單。與蟻群算法類似，該算法參數(shù)較多、參數(shù)關(guān)聯(lián)性強(qiáng)，而且參數(shù)取值對(duì)算法的性能影響較大，但是，對(duì)參數(shù)的調(diào)整往往依賴于經(jīng)驗(yàn)。因此諸多學(xué)者通過優(yōu)化參數(shù)實(shí)現(xiàn)對(duì)算法的優(yōu)化，例如文獻(xiàn)[66]。與蟻群算法相比，遺傳算法對(duì)網(wǎng)絡(luò)反饋信息的利用率較低，因此收斂速度較慢，所以更改遺傳算法結(jié)構(gòu)，提高算法對(duì)反饋信息的利用率，可以加快算法收斂速率。遺傳算法對(duì)初始種群的選擇具有一定的依賴性，因此，通過啟發(fā)式方法選擇更為優(yōu)異的初始種群，可以提高算法的效率。

2.3 神經(jīng)網(wǎng)絡(luò)法

神經(jīng)網(wǎng)絡(luò)(NN，neural network)算法是在研究人腦工作機(jī)理的基礎(chǔ)上提出來的，具有較好的學(xué)習(xí)、容錯(cuò)能力[67]。該算法的基本思想是構(gòu)建一個(gè)針對(duì)移動(dòng)機(jī)器人路徑規(guī)劃的神經(jīng)網(wǎng)絡(luò)模型。該模型的輸入為傳感器信息以及機(jī)器人上一次的運(yùn)動(dòng)狀態(tài)[68]。

神經(jīng)網(wǎng)絡(luò)方法可使機(jī)器人具備適應(yīng)新環(huán)境的能力，但需要事先構(gòu)建數(shù)據(jù)集訓(xùn)練模型，而且訓(xùn)練時(shí)間較長。因此，往往將神經(jīng)網(wǎng)絡(luò)算法與其他智能算法相結(jié)合，以改善神經(jīng)網(wǎng)絡(luò)的規(guī)劃性能。文獻(xiàn)[69]與文獻(xiàn)[70]將神經(jīng)網(wǎng)絡(luò)與遺傳算法相結(jié)合應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，實(shí)驗(yàn)結(jié)果證明了該方法的可行性；文獻(xiàn)[71]融合神經(jīng)網(wǎng)絡(luò)與混合粒子群算法實(shí)現(xiàn)了移動(dòng)機(jī)器人路徑規(guī)劃；文獻(xiàn)[72]與文獻(xiàn)[73]將模糊神經(jīng)網(wǎng)絡(luò)應(yīng)用于路徑規(guī)劃，并證明了該算法的高效性。文獻(xiàn)[74]將使用自適應(yīng)蟻群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)迭代方式解決路徑規(guī)劃問題，試驗(yàn)證明該方法獲取路徑的速度更快。文獻(xiàn)[75]提出一種概率路線圖與神經(jīng)網(wǎng)絡(luò)結(jié)合的路徑規(guī)劃算法實(shí)現(xiàn)了移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃。

神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中包含大量的參數(shù)，參數(shù)的數(shù)量往往比蟻群算法、遺傳算法等其他智能算法更多，且參數(shù)關(guān)聯(lián)性更強(qiáng)，對(duì)算法效率影響更明顯。因此，在構(gòu)建神經(jīng)網(wǎng)絡(luò)時(shí)，調(diào)參過程較為復(fù)雜，且通常會(huì)占用大量時(shí)間，這大大限制了神經(jīng)網(wǎng)絡(luò)的應(yīng)用。另外，神經(jīng)網(wǎng)絡(luò)需要大量的數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練，數(shù)據(jù)量的大小間接影響算法的性能。目前，神經(jīng)網(wǎng)絡(luò)在路徑規(guī)劃領(lǐng)域的應(yīng)用相對(duì)較少，因此，可用的公開數(shù)據(jù)集較為匱乏。學(xué)者往往需要通過大量數(shù)據(jù)事先構(gòu)建數(shù)據(jù)集，這增加了神經(jīng)網(wǎng)絡(luò)的實(shí)現(xiàn)難度。即便目前已有大量研究融合神經(jīng)網(wǎng)絡(luò)與各種智能算法，例如蟻群算法、粒子群算法、遺傳算法等，但將融合算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃的研究不是很多。神經(jīng)網(wǎng)絡(luò)缺陷較為明顯，但是優(yōu)異的網(wǎng)絡(luò)架構(gòu)往往能使算法具有強(qiáng)大的環(huán)境適應(yīng)能力。隨著移動(dòng)機(jī)器人應(yīng)用場景的增加，其面對(duì)的工作環(huán)境復(fù)雜度進(jìn)一步增加，神經(jīng)網(wǎng)絡(luò)的優(yōu)勢將進(jìn)一步展現(xiàn)。因此，將神經(jīng)網(wǎng)絡(luò)應(yīng)用于移動(dòng)機(jī)器人具有重要意義，未來工作中需要對(duì)該應(yīng)用場景做大量研究。

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

基于采樣的方法通過碰撞檢測判斷候選路徑采樣點(diǎn)的可行性，從而避免了對(duì)環(huán)境約束的顯示表達(dá)(不需要對(duì)環(huán)境建模)。該種方法通過連接所有可行采樣點(diǎn)，進(jìn)而形成可行路徑圖，最后在該路徑圖中求解一條由初始狀態(tài)至目標(biāo)狀態(tài)的可行路徑。基于采樣的規(guī)劃算法基本框圖如圖8所示。目前常用的基于采樣的規(guī)劃算法是概率路線圖(PRM，probabilistic roadmaps)法和快速擴(kuò)展隨機(jī)樹(RRT，rapidly-exploring random tree)法。

圖8 基于采樣的規(guī)劃算法框圖

3.1 PRM算法

1996年Kavraki 和 Svestka[76]提出了PRM算法，該算法是一種基于多次查詢的規(guī)劃算法，包括學(xué)習(xí)和查詢兩個(gè)階段。在學(xué)習(xí)階段，通過自由配置空間隨機(jī)生成可行采樣點(diǎn)，并使用快速的路徑規(guī)劃器連接這些可行采樣點(diǎn)，從而構(gòu)成概率路線圖；在查詢階段，可以在概率路線圖中尋找一條由初始狀態(tài)至目標(biāo)狀態(tài)的最佳路徑。如圖9所示。

圖9 PRM算法路徑規(guī)劃示意圖

PRM算法在高維空間中表現(xiàn)優(yōu)異，因此該算法得到了廣泛關(guān)注與研究。但在一些應(yīng)用場合中，獲得先驗(yàn)路標(biāo)的計(jì)算量可能太大甚至導(dǎo)致規(guī)劃失敗，這限制了該算法的在線規(guī)劃能力。當(dāng)采樣點(diǎn)較少時(shí)，PRM算法規(guī)劃的路徑難以通過狹窄通道；增加采樣點(diǎn)數(shù)量，可以解決該問題，但是計(jì)算代價(jià)增大。針對(duì)該問題，Ravankar等[77]提出一種基于混合潛力的概率路線圖算法，該算法利用地圖分割來產(chǎn)生高潛力和低潛力的區(qū)域，并在路線圖構(gòu)建過程中減少樣本集分散。實(shí)驗(yàn)結(jié)果表明，該方法的局部和全局規(guī)劃成功率中均高于95%；Zhong等[78]通過識(shí)別狹窄通道并增加狹窄通道中路標(biāo)密度的方式，提高了路徑規(guī)劃的效率以及成功率。程謙等[79]通過改變連接點(diǎn)距離的方式，一定程度上提高了搜索路徑的效率。針對(duì)PRM在采樣點(diǎn)較少時(shí)難以規(guī)劃出路徑的問題，鄒善席[80]等通過隨機(jī)采樣點(diǎn)生成函數(shù)將落在障礙物內(nèi)的采樣點(diǎn)變換到自由空間內(nèi)，提高采樣點(diǎn)的利用率；另外通過節(jié)點(diǎn)增強(qiáng)法實(shí)現(xiàn)了對(duì)路徑的優(yōu)化。實(shí)驗(yàn)結(jié)果表明，相對(duì)于傳統(tǒng)的PRM算法，該算法的路徑規(guī)劃時(shí)間更短，且路徑代價(jià)也相應(yīng)的降低。

3.2 RRT算法

1998年Lavalle提出了RRT算法[81]，該算法通過構(gòu)建隨機(jī)樹的方式獲取由起始點(diǎn)至目標(biāo)點(diǎn)的無碰撞路徑。RRT算法將起始點(diǎn)作為隨機(jī)樹的根節(jié)點(diǎn)，通過隨機(jī)采樣的方式獲取隨機(jī)點(diǎn)，并將符合條件的點(diǎn)(與隨機(jī)樹中葉子結(jié)點(diǎn)相連時(shí)不與障礙物發(fā)生碰撞)加入隨機(jī)樹中作為葉子結(jié)點(diǎn)，直至目標(biāo)點(diǎn)被加入到隨機(jī)樹中，算法迭代結(jié)束。RRT算法擴(kuò)展過程示意圖如圖10所示。

圖10 RRT算法擴(kuò)展過程

RRT算法簡單，對(duì)環(huán)境適應(yīng)性強(qiáng)，而且可用于實(shí)時(shí)在線規(guī)劃[82]。但是RRT算法對(duì)空間的探索完全隨機(jī)，因此搜索效率較低；另外，RRT算法對(duì)路徑缺乏優(yōu)化能力。針對(duì)RRT算法的局限性，學(xué)者們做了大量研究。Kuffner等[83]提出了Bi-RRT算法，通過以起始點(diǎn)與目標(biāo)點(diǎn)分別為根節(jié)點(diǎn)同時(shí)擴(kuò)展隨機(jī)樹的方式，提高路徑搜索效率。Karaman和Frazzoli[84]提出了RRT*算法，該算法通過重選父節(jié)點(diǎn)、重布線兩種方式優(yōu)化RRT算法，一定程度上降低了RRT算法的隨機(jī)性。雖然隨著空間維度的增加，RRT*算法收斂速度有所下降，但是RRT*算法具備漸進(jìn)優(yōu)化能力，因此學(xué)者們基于此算法作出了大量改進(jìn)性研究。結(jié)合文獻(xiàn)[83]的思想，Jordan和Perez[85]提出了Bi-RRT*算法。Nasir等[86]提出一種在規(guī)劃過程中可根據(jù)在線信息調(diào)整參數(shù)的RRT*-Smart算法，以便適應(yīng)諸如迷宮、狹窄通道等多類型環(huán)境。

雖然以上改進(jìn)算法的速率有一定提升，但仍難滿足高維空間的規(guī)劃需求。由此誕生了啟發(fā)式RRT算法，該種算法通過直接改變采樣點(diǎn)的生成方式，降低路徑的隨機(jī)性和代價(jià)。Urmson等提出了基于啟發(fā)式引導(dǎo)hRRT算法[87]，該算法結(jié)合啟發(fā)式函數(shù)生成有效節(jié)點(diǎn)，引導(dǎo)隨機(jī)樹生長方向。Gammell等[88]提出了Informed RRT*算法，該算法在RRT*算法的基礎(chǔ)上利用啟發(fā)式方法對(duì)路徑進(jìn)行了優(yōu)化。當(dāng)獲取初始路徑后，該算法將采樣空間限制在特定的超橢球區(qū)域內(nèi)，進(jìn)而提高路徑優(yōu)化的收斂速率?；谠撍枷雽W(xué)者們做出了許多研究與改進(jìn)[89-91]。Gammell等[92]提出了BIT*算法，該算法采用批采樣方式與超橢球優(yōu)化機(jī)制相結(jié)合的方式，提高了獲取路徑速率的同時(shí)，降低了路徑代價(jià)。Strub等[93]提出了一種自適應(yīng)啟發(fā)樹算法(Adaptively Informed Trees，AIT*)，該算法通過使用非對(duì)稱雙向搜索來適應(yīng)每個(gè)問題實(shí)例，以同時(shí)估計(jì)和利用特定問題的啟發(fā)式，這使得其能迅速找到初始解并收斂到最優(yōu)。另一種啟發(fā)方式是基于目標(biāo)偏向的，即goal-biasing RRT算法。該算法包括隨機(jī)擴(kuò)展和目標(biāo)擴(kuò)展兩種方式，并在擴(kuò)展過程中以一定概率選擇擴(kuò)展方式。許多研究基于此思想對(duì)RRT算法作出改進(jìn)[94-96]。Noreen等[97]將路徑搜索區(qū)間限定在包含起始點(diǎn)與目標(biāo)點(diǎn)的可調(diào)邊界區(qū)間內(nèi)，增加了隨機(jī)樹生長的方向性。

4 路徑規(guī)劃算法分析

本文對(duì)目前主流的路徑規(guī)劃算法進(jìn)行簡單的歸納綜述，列舉相關(guān)算法的實(shí)現(xiàn)機(jī)制與原理、優(yōu)點(diǎn)以及局限性，結(jié)果如表1所示。

表1 主流路徑規(guī)劃算法匯總表

現(xiàn)有的規(guī)劃算法及其改良算法都已經(jīng)應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃之中，但是大多數(shù)研究都是將規(guī)劃算法用于單個(gè)移動(dòng)機(jī)器人，對(duì)于多機(jī)器人協(xié)同規(guī)劃的算法相對(duì)較少。

傳統(tǒng)的路徑規(guī)劃算法依賴于環(huán)境中障礙物的顯示表達(dá)，即需要描述環(huán)境中的障礙物。例如，Bug算法在運(yùn)行過程中需要對(duì)遇到的障礙物執(zhí)行“邊界跟蹤”操作；基于柵格的算法需要構(gòu)建環(huán)境柵格地圖；向量場直方圖算法需要根據(jù)障礙物密度構(gòu)建極坐標(biāo)系等。雖然各種算法對(duì)環(huán)境的表達(dá)方式略有不同，但都依賴于環(huán)境，這使得傳統(tǒng)算法受環(huán)境約束較大。例如，Bug算法只適用于二維環(huán)境，當(dāng)環(huán)境維數(shù)增加時(shí)，Bug算法將無法執(zhí)行“邊界跟蹤操作”。傳統(tǒng)算法的結(jié)構(gòu)簡單，這使得大多數(shù)算法的計(jì)算速度更快。一般而言，計(jì)算方式越簡單，其收斂速度越快。柵格法與Voronoi法都是基于圖形的算法，這些算法往往需要構(gòu)建路徑圖形，該操作占用了一定的計(jì)算資源，因此相對(duì)于人工勢場法、Bug算法、向量場直方圖法，基于圖形的算法收斂較慢。雖然柵格法、Voronoi法的收斂速度較慢，但是其路徑優(yōu)化能力更優(yōu)越，獲得的路徑往往代價(jià)更低，而且對(duì)于環(huán)境的適應(yīng)能力有一定提高，具有更強(qiáng)的魯棒性。環(huán)境維度越高，該特性越明顯。結(jié)構(gòu)簡單的算法對(duì)環(huán)境的適應(yīng)力較差，人工勢場法在特殊環(huán)境下(例如，引力與斥力相抵消)、Bug算法與向量場直方圖算法在復(fù)雜環(huán)境下(例如迷宮)，容易陷入局部極小值，進(jìn)而導(dǎo)致規(guī)劃失敗。基于圖形的算法雖然犧牲了規(guī)劃效率，但其較為復(fù)雜的結(jié)構(gòu)使其性能得到提升，一定程度上解決了局部極小值問題，且對(duì)環(huán)境的適應(yīng)能力有一定的提高。

相對(duì)于傳統(tǒng)算法，智能算法結(jié)構(gòu)更為復(fù)雜，而且智能算法自身具有強(qiáng)大的學(xué)習(xí)能力，這使得其對(duì)環(huán)境的適應(yīng)能力非常強(qiáng)，減少了環(huán)境對(duì)算法的約束，極大程度上避免出現(xiàn)局部極小值問題。蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法都具有較多的參數(shù)，往往需要調(diào)參提高算法性能。蟻群依靠信息素的濃度變化實(shí)現(xiàn)對(duì)路徑的漸進(jìn)優(yōu)化，當(dāng)初始解為次優(yōu)解時(shí)，蟻群算法容易出現(xiàn)局部最優(yōu)問題。遺傳算法克服了此缺點(diǎn)，遺傳算法通過交叉和變異操作使算法的漸進(jìn)優(yōu)化能力更強(qiáng)。但遺傳算法的交叉和變異等過程需要大量計(jì)算，因此在獲得優(yōu)化性能的同時(shí)，降低了算法的收斂速度。神經(jīng)網(wǎng)絡(luò)算法的結(jié)構(gòu)更為復(fù)雜，該算法通過模擬人腦機(jī)理，對(duì)模型參數(shù)漸進(jìn)優(yōu)化。該算法的顯著特點(diǎn)是需要大量數(shù)據(jù)訓(xùn)練模型，數(shù)據(jù)量越大，模型越精確，這也體現(xiàn)了該算法強(qiáng)大的學(xué)習(xí)能力。神經(jīng)網(wǎng)絡(luò)算法往往需要結(jié)合其他智能算法實(shí)現(xiàn)性能的提升，例如通過神經(jīng)網(wǎng)絡(luò)模型為遺傳算法適應(yīng)度函數(shù)提供更為合理的輸入。

基于采樣的算法不需要對(duì)障礙物進(jìn)行顯示描述，因此進(jìn)一步降低了環(huán)境約束，這使得該種算法適用于高維空間的路徑規(guī)劃。但該算法的顯著特點(diǎn)是隨機(jī)性較大，生成路徑的代價(jià)較高。PRM算法在學(xué)習(xí)階段通過采樣點(diǎn)構(gòu)建網(wǎng)絡(luò)圖，在查詢階段通過搜索圖獲取路徑。對(duì)圖的操作，使得PRM算法浪費(fèi)大量的計(jì)算資源，因此規(guī)劃速率較慢。隨著環(huán)境維度的增加，構(gòu)建與查詢圖所消耗的時(shí)間隨之增加，因此該算法不適用于復(fù)雜環(huán)境下移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃。RRT算法通過隨機(jī)樹的方式擴(kuò)展路徑，雖然該方式隨機(jī)性較大，但其擴(kuò)展速度極快，因此算法收斂更快，更能滿足規(guī)劃的實(shí)時(shí)性需求。隨著環(huán)境維度的增加，其速度優(yōu)勢更為顯著。RRT算法的隨機(jī)性使獲取路徑的代價(jià)有所提升，且算法性能不穩(wěn)定。

以上所有算法都具有其本身的優(yōu)勢與適用場景，但是往往其局限性限制了自身的發(fā)展，因此大量的工作用來優(yōu)化劃算法。

5 路徑規(guī)劃算法發(fā)展趨勢

本文總結(jié)綜述了移動(dòng)機(jī)器人路徑規(guī)劃主流算法的原理、優(yōu)缺點(diǎn)、研究現(xiàn)狀及其改進(jìn)方法，并將其分為三類：傳統(tǒng)規(guī)劃算法、智能規(guī)劃算法、基于采樣的規(guī)劃算法。接下來對(duì)路徑規(guī)劃技術(shù)做出以下展望。

1)更為高效的算法融合：

目前，對(duì)于算法的大部分研究工作都是基于算法本身特性進(jìn)行改進(jìn)，對(duì)算法進(jìn)行融合的研究相對(duì)較少，但是這些工作都取得了不錯(cuò)的效果，例如文獻(xiàn)[35]、文獻(xiàn)[38]、文獻(xiàn)[50]、文獻(xiàn)[60]等。單一的算法都具有各自的局限性，例如局部極小值、路徑拐點(diǎn)多、規(guī)劃效率低等問題，而并不是所有算法都具有相同的局限性，因此可以通過將互補(bǔ)的算法進(jìn)行融合，實(shí)現(xiàn)更為高效的規(guī)劃方式。例如將A*算法與蟻群算法進(jìn)行融合，引入A*算法的評(píng)價(jià)函數(shù)優(yōu)化蟻群算法的信息素更新方式，既加快了算法的收斂速率又克服了局部極小值問題。因此多算法融合是未來實(shí)現(xiàn)高效路徑規(guī)劃的重要方式。

2)多傳感器融合的動(dòng)態(tài)路徑規(guī)劃：

現(xiàn)有的路徑規(guī)劃算法多用于離線規(guī)劃，即假定環(huán)境不變的情況下進(jìn)行路徑規(guī)劃。然而實(shí)際應(yīng)用場景往往是動(dòng)態(tài)的，移動(dòng)機(jī)器人需要及時(shí)躲避動(dòng)態(tài)的障礙物。因此，動(dòng)態(tài)路徑規(guī)劃算法在未來發(fā)展中需要投入大量研究。在動(dòng)態(tài)路徑規(guī)劃中，往往需要實(shí)時(shí)更新環(huán)境信息，各種傳感器可以用來實(shí)現(xiàn)對(duì)動(dòng)態(tài)場景的更新。例如，深度相機(jī)、雷達(dá)等都可以實(shí)時(shí)傳遞環(huán)境中的障礙物距離以及形狀信息，可以用于實(shí)時(shí)判定機(jī)器人與障礙物之間的距離。將多傳感器應(yīng)用于移動(dòng)機(jī)器人并融合傳感器信息可以實(shí)現(xiàn)更為精確的路徑規(guī)劃，甚至實(shí)現(xiàn)更為復(fù)雜的功能。

3)復(fù)雜環(huán)境中的路徑規(guī)劃：

現(xiàn)階段，路徑規(guī)劃算法在規(guī)劃過程中往往將初始位置與目標(biāo)位置用點(diǎn)代替，該種方式較為簡單；而且一些傳統(tǒng)的路徑規(guī)劃算法僅適用于二維環(huán)境，大多數(shù)算法在環(huán)境維度提高、障礙物增多時(shí)，規(guī)劃效率降低?，F(xiàn)有的應(yīng)用實(shí)例中，大多將移動(dòng)機(jī)器人應(yīng)用于簡單的生活場景中，例如掃地機(jī)器人?，F(xiàn)實(shí)的工作場景往往是復(fù)雜的，因此，提高路徑規(guī)劃算法在復(fù)雜場景下的規(guī)劃效率具有重要意義。

4)物聯(lián)網(wǎng)技術(shù)協(xié)同規(guī)劃：

目前的應(yīng)用場景中，大多是移動(dòng)機(jī)器人自身通過計(jì)算單元實(shí)現(xiàn)路徑規(guī)劃功能。隨著市場需求的增加，移動(dòng)機(jī)器人被應(yīng)用于各種復(fù)雜場景是必然趨勢，而面對(duì)復(fù)雜場景時(shí)，移動(dòng)機(jī)器人所處理的數(shù)據(jù)將大大增加，這使得對(duì)移動(dòng)機(jī)器人的核心處理單元要求非常高。隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)可以通過互聯(lián)網(wǎng)快速傳輸。因此將移動(dòng)機(jī)器人需要處理的大量數(shù)據(jù)通過網(wǎng)絡(luò)傳輸給高性能遠(yuǎn)程服務(wù)器處理，不僅能提高移動(dòng)機(jī)器人的規(guī)劃效率，還能在一定程度上簡化移動(dòng)機(jī)器人自身結(jié)構(gòu)。

5)優(yōu)化已有算法的規(guī)劃性能：

已有的算法雖然具有一定的局限性，且大多應(yīng)用于簡單規(guī)劃場景，但是基礎(chǔ)算法仍有其適用場景，并且這些算法是實(shí)際應(yīng)用的重要基礎(chǔ)。因此，針對(duì)不同的路徑規(guī)劃算法對(duì)其自身局限性進(jìn)行優(yōu)化仍有重要意義，未來的工作中可以探索將更多的數(shù)學(xué)理論應(yīng)用于優(yōu)化路徑規(guī)劃算法，例如改進(jìn)蟻群信息素更新方式、改進(jìn)A*與D*算法的代價(jià)函數(shù)、優(yōu)化遺傳算法的適應(yīng)度函數(shù)等。對(duì)基礎(chǔ)算法的改進(jìn)對(duì)未來的實(shí)際應(yīng)用仍具有重要研究價(jià)值。

6 結(jié)束語

路徑規(guī)劃算法是移動(dòng)機(jī)器人的關(guān)鍵技術(shù)，目前的路徑規(guī)劃算法具有一定的局限性，仍需要大量工作進(jìn)行改進(jìn)，提高算法的性能與適用性。隨著人工智能技術(shù)的發(fā)展，多技術(shù)融合為路徑規(guī)劃算法的發(fā)展提供了發(fā)展契機(jī)。通過提升路徑規(guī)劃算法的性能與適用性，可以使移動(dòng)機(jī)器人的應(yīng)用場景更穩(wěn)廣闊