動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的研究

張 艷, 張明路, 蔣志宏, 呂曉玲

(1.河北工業(yè)大學(xué) 機(jī)械工程學(xué)院,天津 300130; 2.北京理工大學(xué) 機(jī)電學(xué)院智能機(jī)器人研究所,北京 100081)

0 引 言

隨著科學(xué)和機(jī)器人技術(shù)的不斷發(fā)展進(jìn)步,人們對(duì)機(jī)器人在運(yùn)動(dòng)過程中適應(yīng)周圍環(huán)境自主采取相應(yīng)措施的能力要求越來越高[1]。路徑規(guī)劃的本質(zhì)是在障礙物與目標(biāo)物之間建立一條從起始位置到終點(diǎn)位置無碰撞且最優(yōu)的路徑[2]。而在動(dòng)態(tài)環(huán)境中障礙物和目標(biāo)物的位置都是實(shí)時(shí)變化的,易與機(jī)器人發(fā)生碰撞,導(dǎo)致機(jī)器人的損壞以及無法完成規(guī)定的任務(wù),極大地限制了機(jī)器人的應(yīng)用。因此,在動(dòng)態(tài)環(huán)境下對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃研究具有重要的意義。

本文對(duì)現(xiàn)有的路徑規(guī)劃相關(guān)文獻(xiàn)進(jìn)行分析與研究,從算法應(yīng)用本身的特點(diǎn)出發(fā),結(jié)合算法的模型以及每種算法的基本原理進(jìn)行歸類,提出了4種不同的劃分方法,即智能仿生、幾何模型搜索、虛擬勢(shì)場(chǎng)、強(qiáng)化學(xué)習(xí)。根據(jù)每種算法模型,具體指出每類算法所針對(duì)的主要問題;并根據(jù)每種算法的特點(diǎn)將不同算法相互結(jié)合運(yùn)用,以解決動(dòng)態(tài)環(huán)境下機(jī)器人的路徑規(guī)劃問題。

1 智能仿生算法

隨著人工智能的興起,越來越多的智能算法被應(yīng)用在路徑規(guī)劃中,以改善傳統(tǒng)路徑規(guī)劃算法的不足。智能算法的一個(gè)重要特性是其運(yùn)行機(jī)理與自然界的生物群體行為或生態(tài)機(jī)制類似,為了區(qū)分智能算法與其他算法,把智能算法定義為智能仿生算法。文獻(xiàn)[3]從算法本身的起源及其特點(diǎn)進(jìn)行分析,指出智能仿生算法是一種受自然策略啟發(fā)的啟發(fā)式算法,但對(duì)于智能仿生算法的定義不夠具體,無法充分將智能仿生算法的特點(diǎn)進(jìn)行總結(jié);文獻(xiàn)[4]以算法的發(fā)展歷程為切入點(diǎn),對(duì)比分析了現(xiàn)有的智能仿生算法與傳統(tǒng)仿生算法之間的聯(lián)系和區(qū)別。通過對(duì)文獻(xiàn)[5-8]的研究與分析得出,智能仿生算法是模擬生物進(jìn)化和自然界中各種生物覓食、筑巢行為的新興智能化方法,主要分為受生物群體行為的啟發(fā)、受生物體結(jié)構(gòu)或組織啟發(fā)、受生物進(jìn)化啟發(fā)3類[9]。

智能仿生算法包括受生物群體行為啟發(fā)而產(chǎn)生的粒子群(particle swarm optimization,PSO)算法和細(xì)菌覓食算法(bacterial foraging algorithm,BFA)、受生物體結(jié)構(gòu)或組織啟發(fā)的人工免疫算法、受生物進(jìn)化啟發(fā)的入侵雜草算法以及其他智能仿生算法(遺傳算法、蟻群算法)等。

1.1 PSO算法

PSO算法的基本原理是通過在群體中個(gè)體對(duì)信息的共享,讓整個(gè)群體的運(yùn)動(dòng)在求解問題的過程中從空間產(chǎn)生無序到有序的演化過程,從而獲得問題的最優(yōu)解,算法流程如圖1所示。

根據(jù)PSO算法的定義,算法的數(shù)學(xué)公式描述如下。

在d維空間中,粒子i的速度更新公式為:

(1)

在d維空間中,粒子i的位置更新公式為:

(2)

其中,Xi為粒子i的位置;Vi為粒子i的速度;Pbesti為粒子i所搜尋到的最好位置;Gbesti為種群所經(jīng)歷的最好位置;c1、c2為常數(shù);rand()為[0,1]的隨機(jī)數(shù);ω為慣性的權(quán)重,用于調(diào)節(jié)對(duì)解空間的搜索范圍。

目前對(duì)PSO算法的理論分析與研究主要集中在對(duì)其關(guān)鍵參數(shù)的改進(jìn)與模型的變化上。文獻(xiàn)[10]提出了高粒子群全局搜索策略,使其在二維多邊形地圖動(dòng)態(tài)環(huán)境下有較強(qiáng)的預(yù)測(cè)能力,并通過實(shí)驗(yàn)證明該方法可以有效地避免碰撞;文獻(xiàn)[11-13]通過對(duì)罰函數(shù)的改變研究PSO算法的改進(jìn)或模型的改變,但粒子的評(píng)估值由于在發(fā)生碰撞時(shí)會(huì)與實(shí)際值發(fā)生偏差,導(dǎo)致不能反映出與障礙物碰撞的嚴(yán)重程度。因此,文獻(xiàn)[14-16]設(shè)計(jì)出一種特殊的適應(yīng)度函數(shù)以提高PSO算法全局搜索和預(yù)測(cè)能力,然后利用局部最優(yōu)粒子群算法使移動(dòng)機(jī)器人在不碰撞障礙物的情況下達(dá)到目標(biāo),并找到了迭代次數(shù)最少、總圓弧代價(jià)最小、占用時(shí)間最少的最優(yōu)路徑;文獻(xiàn)[17]提出在全局最優(yōu)位置加上微小的隨機(jī)擾動(dòng),幫助粒子跳出當(dāng)前停滯狀態(tài),同時(shí)引進(jìn)自適應(yīng)機(jī)制微調(diào)粒子的控制參數(shù),使得改進(jìn)后的算法能夠在搜索最優(yōu)解時(shí)達(dá)到動(dòng)態(tài)平衡;文獻(xiàn)[18]基于PSO算法和渦流搜索算法,提出了一種適合于移動(dòng)機(jī)器人在復(fù)雜家庭環(huán)境中規(guī)劃可行、安全、最優(yōu)的多目標(biāo)路徑規(guī)劃方法,將2種算法合理地進(jìn)行結(jié)合,得到的路徑規(guī)劃具有效率高、計(jì)算量小的特點(diǎn);文獻(xiàn)[19]提出了一種具有不同學(xué)習(xí)策略的自適應(yīng)學(xué)習(xí)PSO算法,將路徑規(guī)劃問題轉(zhuǎn)化為最小化多目標(biāo)優(yōu)化問題,并考慮路徑長度、碰撞風(fēng)險(xiǎn)度和平滑度3個(gè)目標(biāo)建立目標(biāo)函數(shù),再開發(fā)一種新的自適應(yīng)學(xué)習(xí)機(jī)制,在優(yōu)化過程的不同階段自適應(yīng)選擇最合適的搜索策略,提高PSO算法的搜索能力。

通過對(duì)現(xiàn)有的文獻(xiàn)研究可知,即使改進(jìn)后的PSO算法能夠快速找到最優(yōu)解,但在產(chǎn)生新的種群時(shí)阻礙了隨機(jī)產(chǎn)生粒子的速度,降低了粒子的收斂速度,也存在陷入局部極值點(diǎn)、得不到全局最優(yōu)解的問題。粒子的多樣性與PSO算法本身的參數(shù)設(shè)置有關(guān),只有粒子的多樣性參數(shù)設(shè)置得當(dāng),才能夠使算法收斂到全局極值點(diǎn)。

1.2 BFA算法

BFA算法是基于Ecoli大腸桿菌在人體腸道內(nèi)吞噬食物行為提出的一種新型智能仿生算法[20]。BFA算法的最大特點(diǎn)在于能夠在群體中進(jìn)行智能并行搜索、具有方便快捷地跳出局部極小值的特點(diǎn)。基于BFA算法的搜索過程如圖2所示。

圖2 基于BFA算法的搜索過程

近年來,BFA算法在路徑規(guī)劃中得到了進(jìn)一部發(fā)展。文獻(xiàn)[21]在BFA算法原理的基礎(chǔ)上結(jié)合自適應(yīng)搜索策略,并將該算法運(yùn)用到移動(dòng)機(jī)器人的路徑規(guī)劃中,使得模擬細(xì)菌行為的機(jī)器人能夠在被障礙物包圍的環(huán)境中確定從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)無碰撞路徑。文獻(xiàn)[22]基于細(xì)菌最優(yōu)覓食理論提出了新型生物啟發(fā)計(jì)算方法,該改進(jìn)的BFA算法通過采取自適應(yīng)與局部區(qū)域搜索相結(jié)合的形式提高了動(dòng)態(tài)優(yōu)化能力,將算法應(yīng)用于真實(shí)場(chǎng)景中的結(jié)果表明，改進(jìn)的算法不僅能快速、準(zhǔn)確地到達(dá)目的地,還能有效求解此類動(dòng)態(tài)路徑規(guī)劃問題。文獻(xiàn)[23]通過對(duì)BFA算法關(guān)鍵參數(shù)的改進(jìn),模擬隨機(jī)分布在機(jī)器人周圍的粒子能夠避開移動(dòng)障礙物,規(guī)劃出一條朝向目標(biāo)位置的最佳路徑;選擇最佳粒子的準(zhǔn)則是目標(biāo)距離和粒子的高斯代價(jià)函數(shù),然后使用高層決策策略進(jìn)行選擇,最后對(duì)結(jié)果進(jìn)行處理；實(shí)驗(yàn)結(jié)果表明，該改進(jìn)的BFA算法比基本覓食算法的搜索時(shí)間更短、效率更高。文獻(xiàn)[24]將細(xì)菌覓食仿生策略運(yùn)用到移動(dòng)機(jī)器人路徑規(guī)劃中,使模擬細(xì)菌行為的機(jī)器人能夠在障礙物包圍的環(huán)境中確定最佳的無碰撞路徑。

1.3 人工免疫法

人工免疫算法是一種以生物免疫系統(tǒng)為基礎(chǔ)的啟發(fā)式隨機(jī)搜索算法,該算法的主要特點(diǎn)是能夠在全局進(jìn)行分步式搜索，魯棒性強(qiáng)。人工免疫算法流程如圖3所示。

圖3 人工免疫算法流程

人工免疫算法在路徑規(guī)劃中運(yùn)用效果較好,但直接運(yùn)用到機(jī)器人路徑規(guī)劃中會(huì)經(jīng)常出現(xiàn)局部最優(yōu)、全局解不理想且收斂速度慢等問題。文獻(xiàn)[25]提出了一種改進(jìn)的免疫算法,首先根據(jù)障礙物和目標(biāo)物在空間分布狀況對(duì)機(jī)器人的影響,定義了抗體新編碼格式;然后根據(jù)對(duì)機(jī)器人的不同影響選擇不同的動(dòng)力學(xué)模型;最后針對(duì)動(dòng)態(tài)環(huán)境中的局部極小值,通過特定的免疫機(jī)制選擇合適的規(guī)避策略,有效地解決了局部極小值的問題。此外,根據(jù)抗體濃度學(xué)習(xí)策略,可以解決鎖死現(xiàn)象。文獻(xiàn)[26]同樣對(duì)人工免疫算法進(jìn)行了改進(jìn),將機(jī)器人行為和機(jī)器人周圍環(huán)境分別看做抗體和抗原,通過抗體和抗原之間的相互作用構(gòu)造人工免疫網(wǎng)絡(luò),并在網(wǎng)絡(luò)中搜索最優(yōu)路徑。人工免疫算法雖有動(dòng)態(tài)適應(yīng)性、多樣性等優(yōu)點(diǎn),但該算法局部搜索能力過強(qiáng)，易陷入局部最優(yōu)的局面中,同時(shí)計(jì)算成本太高。

1.4 模糊神經(jīng)網(wǎng)絡(luò)

在動(dòng)態(tài)環(huán)境下,移動(dòng)機(jī)器人無法獲得完整的地圖信息,導(dǎo)致神經(jīng)網(wǎng)絡(luò)訓(xùn)練的結(jié)果不理想,經(jīng)常會(huì)出現(xiàn)錯(cuò)誤或冗余的路徑,給機(jī)器人目標(biāo)搜索帶來干擾。為此,將模糊系統(tǒng)與神經(jīng)網(wǎng)絡(luò)相結(jié)合,充分發(fā)揮兩者優(yōu)勢(shì),在解決非線性、模糊性及復(fù)雜性的技術(shù)問題上有較強(qiáng)的優(yōu)越性。

國內(nèi)外始終對(duì)模糊神經(jīng)網(wǎng)絡(luò)算法保持著相當(dāng)高的關(guān)注,在研究過程中,基于模糊神經(jīng)網(wǎng)絡(luò)模型與學(xué)習(xí)算法相結(jié)合的新算法不斷被提出[27]。

模糊神經(jīng)結(jié)構(gòu)分為5層:① 第1層為輸入層，作用是直接將輸入值x=[x1x2…xn]T傳送到下一層;② 第2層為模糊化層,將輸入的變量進(jìn)行相應(yīng)的模糊化;③ 第3層為規(guī)則層, 主要是將相應(yīng)的模糊規(guī)則進(jìn)行存儲(chǔ);④ 第4層為求“或”層,實(shí)現(xiàn)的是歸一化的計(jì)算;⑤ 第 5層為去模糊化層，也就是輸出層,作用是實(shí)現(xiàn)清晰化的計(jì)算[28]。

模糊神經(jīng)網(wǎng)絡(luò)先對(duì)機(jī)器人傳感器得到的信息進(jìn)行模糊處理,處理后的信息根據(jù)經(jīng)驗(yàn)形成模糊規(guī)則,再將模糊規(guī)則作用于樣本,然后用神經(jīng)網(wǎng)絡(luò)對(duì)樣本進(jìn)行訓(xùn)練。

文獻(xiàn)[29]在模糊理論和神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上,提出了一種新的模糊神經(jīng)網(wǎng)絡(luò)算法,利用模糊神經(jīng)網(wǎng)絡(luò)對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃,充分兼顧模糊理論和神經(jīng)網(wǎng)絡(luò)各自的優(yōu)點(diǎn),得到從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。文獻(xiàn)[30]將模糊神經(jīng)網(wǎng)絡(luò)轉(zhuǎn)化為模型構(gòu)造,利用模糊神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)系統(tǒng)與周圍環(huán)境的相互作用,實(shí)時(shí)地檢測(cè)環(huán)境變化,有效利用空間中的極點(diǎn)值跟蹤最短路徑。文獻(xiàn)[31]采用網(wǎng)格法建立了周邊環(huán)境的數(shù)學(xué)模型,提出了模糊神經(jīng)網(wǎng)絡(luò)的避障策略,用模糊神經(jīng)網(wǎng)絡(luò)搜索下一個(gè)可行節(jié)點(diǎn),實(shí)現(xiàn)避障功能;針對(duì)模糊神經(jīng)網(wǎng)絡(luò)的參數(shù)優(yōu)化問題,將改進(jìn)的PSO算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)進(jìn)行參數(shù)優(yōu)化,避免參數(shù)選擇不當(dāng)造成系統(tǒng)不穩(wěn)定的問題。文獻(xiàn)[32]用動(dòng)態(tài)環(huán)境中物體的信息動(dòng)態(tài)調(diào)整模糊神經(jīng)網(wǎng)絡(luò)的權(quán)值，以加快整個(gè)神經(jīng)網(wǎng)絡(luò)的收斂速度,達(dá)到對(duì)機(jī)器人下一步動(dòng)作進(jìn)行動(dòng)態(tài)控制的目的,最終實(shí)現(xiàn)路徑的動(dòng)態(tài)規(guī)劃；然而動(dòng)態(tài)環(huán)境下模糊神經(jīng)網(wǎng)絡(luò)算法進(jìn)行路徑規(guī)劃需要大量的訓(xùn)練樣本,且不能保證位置精度,同時(shí)它本身是一個(gè)開環(huán)控制系統(tǒng),穩(wěn)定性差,對(duì)動(dòng)態(tài)障礙物缺少避碰策略[33]。

1.5 蟻群算法

蟻群算法的原理來源于螞蟻通過特有的方式感知信息素濃度的高低,通常是向著濃度高的地方移動(dòng),因此蟻群算法也是運(yùn)用此方法來尋找最優(yōu)路徑。

通過濃度高低的反饋信息以加快收斂速度,會(huì)導(dǎo)致蟻群多樣性減小,全局搜索能力減弱。蟻群算法最大的弱點(diǎn)在于環(huán)境復(fù)雜的情況下,引發(fā)死鎖狀態(tài)的概率較高。為了解決這種死鎖現(xiàn)象,蟻群算法要能收斂到全局最優(yōu)解或者近似最優(yōu)解附近。文獻(xiàn)[34]采用最近鄰居搜索策略和趨近導(dǎo)向函數(shù)相互協(xié)作完成全局最優(yōu)路徑搜索,并以多組螞蟻為研究對(duì)象,使實(shí)驗(yàn)數(shù)據(jù)更具有說服力。文獻(xiàn)[35]提出不考慮任何動(dòng)態(tài)障礙的雙相蟻群算法,設(shè)計(jì)了全局最優(yōu)路徑,解決了局部最優(yōu)問題。

蟻群算法的規(guī)劃技術(shù)無法單獨(dú)完成路徑規(guī)劃問題,只是對(duì)計(jì)算進(jìn)行優(yōu)化。文獻(xiàn)[36]主要是應(yīng)對(duì)突發(fā)的環(huán)境狀況,根據(jù)動(dòng)態(tài)環(huán)境中障礙物和目標(biāo)的運(yùn)行方向提出相應(yīng)的解決方案,引入Follow-wall對(duì)行為進(jìn)行改進(jìn),可以有效地適應(yīng)動(dòng)態(tài)環(huán)境的變化,獲取最優(yōu)或次優(yōu)解。文獻(xiàn)[37]將蟻群優(yōu)化問題擴(kuò)展到多目標(biāo)路徑規(guī)劃中,采用蟻群框架與采樣點(diǎn)對(duì)點(diǎn)規(guī)劃的混合算法,解決障礙物下多目標(biāo)規(guī)劃問題。文獻(xiàn)[38]為改進(jìn)的蟻群算法尋找最優(yōu)路徑,提出了針對(duì)局部環(huán)境模型的動(dòng)態(tài)可視方法;其次,根據(jù)已知的動(dòng)態(tài)環(huán)境,基于運(yùn)動(dòng)速度模型和海上避碰規(guī)則設(shè)計(jì)了反偏心膨脹法來處理動(dòng)態(tài)障礙物;然后,針對(duì)蟻群算法收斂速度慢的特點(diǎn),提出一種改進(jìn)的偽隨機(jī)比例規(guī)則來選擇蟻群狀態(tài)轉(zhuǎn)移;最后,采用狼群分配原則和最大、最小蟻群系統(tǒng)對(duì)全局信息素進(jìn)行更新,避免搜索陷入局部最優(yōu),并通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)蟻群算法的實(shí)時(shí)性和穩(wěn)定性。文獻(xiàn)[39]提出將信息素更新策略與節(jié)點(diǎn)策略相結(jié)合,用最優(yōu)節(jié)點(diǎn)來調(diào)節(jié)信息素的分布,通過建立區(qū)域網(wǎng)絡(luò)模型,將其應(yīng)用到路徑規(guī)劃問題中,縮短規(guī)劃時(shí)間。文獻(xiàn)[40-41]基于蟻群算法把模糊規(guī)則優(yōu)化的參數(shù)應(yīng)用于動(dòng)態(tài)環(huán)境下的在線路徑規(guī)劃,實(shí)現(xiàn)在動(dòng)態(tài)和未知環(huán)境下沿著理想的路徑到達(dá)目標(biāo)。

1.6 遺傳算法

遺傳算法是一種模擬自然進(jìn)化而來的隨機(jī)化搜索最優(yōu)解的方法。遺傳算法流程如圖4所示。

圖4 遺傳算法流程

在遺傳算法中,在線計(jì)算時(shí)間決定了算法的運(yùn)算速率,而固定的適應(yīng)度函數(shù)、編碼長度和搜索空間大小等因素影響計(jì)算時(shí)間。文獻(xiàn)[42]采用適度函數(shù)求解移動(dòng)機(jī)器路徑規(guī)劃問題,加速了算法實(shí)時(shí)運(yùn)算速率,提高了運(yùn)算精度。遺傳算法計(jì)算大量路徑占據(jù)了較大的存儲(chǔ)空間,而且運(yùn)行速度慢,增加了計(jì)算量和時(shí)間成本,易產(chǎn)生無效路徑,得到的解往往是最優(yōu)解附近的近似解,無法收斂到全局最優(yōu)解,在進(jìn)化過程的群體中最好的染色體可能會(huì)丟失,且可靠性不易保證。文獻(xiàn)[43]采用粗糙集理論和遺傳算法解決機(jī)器人路徑規(guī)劃效率低、精度低的問題，考慮到障礙物在環(huán)境中的位置及移動(dòng)機(jī)器人起點(diǎn)與終點(diǎn)的關(guān)系,去除了不影響規(guī)劃結(jié)果的冗余障礙物,簡化了環(huán)境模型,減少了路徑規(guī)劃過程中備選路徑的數(shù)量。文獻(xiàn)[44]將遺傳算法與Q學(xué)習(xí)算法相結(jié)合,進(jìn)行先離線后在線的動(dòng)態(tài)路徑規(guī)劃,使移動(dòng)機(jī)器人具有自主學(xué)習(xí)的能力,完善了遺傳算法。

綜上所述,智能仿生算法在機(jī)器人路徑規(guī)劃上主要應(yīng)用于仿生機(jī)器人的設(shè)計(jì)與開發(fā),其中涉及水下、陸面以及空中機(jī)器人3類。這3類機(jī)器人在設(shè)計(jì)路徑規(guī)劃的過程中,主要是通過對(duì)相關(guān)生物特征的模仿來進(jìn)行設(shè)計(jì)與開發(fā),即根據(jù)相關(guān)生物的特性,模擬其運(yùn)動(dòng)特征,并與算法結(jié)合,從而提高機(jī)器人的環(huán)境適應(yīng)性。因此,在開發(fā)大自然環(huán)境的機(jī)器人設(shè)計(jì)中,根據(jù)其研究背景,路徑規(guī)劃算法的選擇應(yīng)該優(yōu)先選擇智能仿生算法,使機(jī)器人更好地適應(yīng)動(dòng)態(tài)環(huán)境。

另外,智能仿生算法還有多種分支與細(xì)節(jié),如何從多種不同的算法中找到一種適合的且能夠快速處理的算法最為重要。通常情況下,每種算法的原理只是一個(gè)基礎(chǔ),想要得到合適的算法,需要考慮其中的具體參數(shù)或多種算法結(jié)合才能達(dá)到解決問題的目的。

2 基于幾何模型的路徑規(guī)劃

動(dòng)態(tài)環(huán)境下路徑規(guī)劃是根據(jù)動(dòng)態(tài)環(huán)境的情況構(gòu)建幾何模型,再去選擇合適的搜索算法,實(shí)時(shí)調(diào)節(jié)基于最優(yōu)策略得到的可行解。實(shí)時(shí)調(diào)節(jié)得到的路徑也不是最光滑的,需要對(duì)這些非光滑的解進(jìn)行優(yōu)化，從而滿足移動(dòng)機(jī)器人的運(yùn)動(dòng)機(jī)理。

目前,對(duì)于環(huán)境幾何模型主要有快速擴(kuò)展隨機(jī)樹(rapid-exploration random tree,RRT)、雙重A*算法、基于區(qū)域分類的安全路徑規(guī)劃方法等。

2.1 RRT算法

RRT算法是對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行搜索的算法,在搜索過程中,將擴(kuò)展樹中任意2點(diǎn)建立聯(lián)系,使得2點(diǎn)進(jìn)行連通。RRT算法在路徑規(guī)劃時(shí),不僅能夠進(jìn)行單軌跡的路徑規(guī)劃,還能進(jìn)行多軌跡的路徑規(guī)劃。RRT算法工作原理如圖5所示。

圖5 RRT算法工作原理

RRT算法進(jìn)行路徑規(guī)劃時(shí),在復(fù)雜多樣的動(dòng)態(tài)環(huán)境下,可以基于環(huán)境信息實(shí)現(xiàn)隨時(shí)調(diào)整規(guī)劃參數(shù),并且調(diào)整其算法的應(yīng)用范圍。文獻(xiàn)[45]提出了一種基于改進(jìn)RRT算法的機(jī)器人自主路徑規(guī)劃方法；該方法引入回歸機(jī)制,防止配置空間的過度搜索，并采用自適應(yīng)擴(kuò)展機(jī)制,通過對(duì)節(jié)點(diǎn)空間邊界節(jié)點(diǎn)的細(xì)化,不斷提高可達(dá)空間信息,避免了對(duì)擴(kuò)展節(jié)點(diǎn)的重復(fù)搜索、機(jī)器人正運(yùn)動(dòng)學(xué)解的不必要迭代和笛卡爾空間中耗時(shí)的碰撞檢測(cè)；該方法可以快速規(guī)劃到目標(biāo)點(diǎn)的路徑,并能從局部最小區(qū)域加速出來,提高路徑規(guī)劃效率；在復(fù)雜環(huán)境下進(jìn)行的仿真結(jié)果表明,改進(jìn)RRT算法在不損失其他性能的前提下,顯著提高了規(guī)劃的成功率和效率。文獻(xiàn)[46]提出了區(qū)域分類的安全路徑規(guī)劃方法,根據(jù)節(jié)點(diǎn)區(qū)域穩(wěn)定性和擁塞程度,進(jìn)行不同方式的擴(kuò)展；該方法的特點(diǎn)是規(guī)劃少、時(shí)間持續(xù)性較長。文獻(xiàn)[47]結(jié)合B樣條與RRT的優(yōu)點(diǎn),基于滾動(dòng)約束思想將優(yōu)化方法融合到快速擴(kuò)展隨機(jī)搜索樹中,克服了隨機(jī)擴(kuò)展樹搜索過于單一、無啟發(fā)的缺點(diǎn);但是仍存在動(dòng)態(tài)環(huán)境下搜索樹規(guī)模被限制,使得有效節(jié)點(diǎn)無法被搜索到,避障效果不佳。文獻(xiàn)[48]將D*算法引入到RRT*算法中,減少了搜索階段碰撞檢測(cè)的頻率,可以更快地到達(dá)目標(biāo)物,當(dāng)突發(fā)狀況發(fā)生時(shí),該算法可以快速找到替代路徑。

2.2 改進(jìn)的A*算法

A*算法與RRT算法相比是一種啟發(fā)式搜索方法,其應(yīng)用于全局信息已知的路徑規(guī)劃中,主要是用來搜索空間中的最短路徑,指導(dǎo)搜索朝最優(yōu)的方向進(jìn)行[49]。A*算法主要思想在于估計(jì)函數(shù)的設(shè)計(jì),在選擇當(dāng)前結(jié)點(diǎn)的下一個(gè)考察節(jié)點(diǎn)時(shí)引入了估價(jià)函數(shù),即

f(x)=g(x)+h(x)

(3)

其中,f(x)為節(jié)點(diǎn)x的估價(jià)函數(shù);g(x)為狀態(tài)空間中從初始節(jié)點(diǎn)到x節(jié)點(diǎn)的實(shí)際代價(jià);h(x)為從x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最優(yōu)路徑的估計(jì)代價(jià)。

在動(dòng)態(tài)環(huán)境中會(huì)遇到障礙物,需要對(duì)路徑重新規(guī)劃,A*算法同樣適用于路徑的二次規(guī)劃。雙重A*算法是將全局A*算法與局部A*算法相結(jié)合,首先在全局信息已知的情況下進(jìn)行全局最優(yōu)路徑規(guī)劃,移動(dòng)機(jī)器人運(yùn)動(dòng)過程中出現(xiàn)障礙物時(shí),再一次采用A*算法進(jìn)行局部路徑規(guī)劃,實(shí)現(xiàn)在動(dòng)態(tài)環(huán)境中能夠安全無碰撞運(yùn)動(dòng)。

雙重A*算法能夠解決動(dòng)態(tài)環(huán)境下的路徑規(guī)劃,但是需要實(shí)時(shí)避障、實(shí)時(shí)規(guī)劃,每次都需要重新計(jì)算,增加了計(jì)算時(shí)間和成本,不利于廣泛推廣。文獻(xiàn)[50]基于傳統(tǒng)A*算法優(yōu)化了啟發(fā)搜索函數(shù),利用關(guān)鍵點(diǎn)選取策略剔除冗余路徑點(diǎn)和不必要的轉(zhuǎn)折點(diǎn);為了提高路徑規(guī)劃的平滑性和局部規(guī)劃的避障能力,在路徑規(guī)劃的最優(yōu)性基礎(chǔ)上將A*算法與動(dòng)態(tài)窗口法融合,進(jìn)行實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃。

2.3 格柵法

柵格法是機(jī)器人將周圍空間分解成互相連接且不重疊的空間單元——柵格,再把這些柵格組成一個(gè)連通圖, 根據(jù)障礙物占有情況, 在地圖上規(guī)劃出從起始柵格到目標(biāo)柵格無碰撞的最優(yōu)路徑。文獻(xiàn)[51]提出了基于柵格類的多機(jī)器人路徑規(guī)劃,機(jī)器人只需根據(jù)各個(gè)機(jī)器人運(yùn)動(dòng)的優(yōu)先權(quán)來調(diào)整自身的運(yùn)動(dòng)路徑以實(shí)現(xiàn)避碰,該方法具有復(fù)雜性低、實(shí)時(shí)性能好的特點(diǎn),尤其適用于動(dòng)態(tài)環(huán)境。文獻(xiàn)[52]在柵格地圖的基礎(chǔ)上提出了障礙物直線掃描檢測(cè)及回避算法的實(shí)時(shí)路徑規(guī)劃,很好地解決了極小值陷阱問題,可使機(jī)器人以穩(wěn)定光滑合理無振蕩的軌跡快速移動(dòng)到目標(biāo)。文獻(xiàn)[53]用柵格法對(duì)環(huán)境進(jìn)行建模,從目標(biāo)柵格點(diǎn)出發(fā),各個(gè)柵格中心點(diǎn)到目標(biāo)柵格中心點(diǎn)的距離信息不斷向外傳播；經(jīng)過傳播后,逐步尋找信息的傳播來源,即可獲得機(jī)器人的最短路徑;仿真結(jié)果表明,該方法簡單高效,能快速規(guī)劃出動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人的最優(yōu)路徑。文獻(xiàn)[54]提出了動(dòng)態(tài)環(huán)境下實(shí)時(shí)規(guī)劃的自適應(yīng)柵格模型,增強(qiáng)了對(duì)環(huán)境多樣性的適應(yīng)能力;與傳統(tǒng)柵格路徑規(guī)劃方法相比,該方法具有更快的規(guī)劃速度,可根據(jù)環(huán)境類型對(duì)路徑規(guī)劃進(jìn)行區(qū)分,并適用于傳統(tǒng)方法失效的動(dòng)態(tài)環(huán)境,但難以滿足路徑規(guī)劃的通用性。

綜上可知,幾何模型搜索算法的共同點(diǎn)在于建立節(jié)點(diǎn)、網(wǎng)格等進(jìn)行路徑規(guī)劃,優(yōu)勢(shì)在于規(guī)劃過程中搜索路徑最短、耗時(shí)最少,并能根據(jù)采集到的信息進(jìn)行路徑調(diào)整。但這類算法無法做到信息及時(shí)反饋,規(guī)劃速度相對(duì)較慢，通常用于陸面機(jī)器人進(jìn)行目標(biāo)搜索,此時(shí)需要在目標(biāo)物與障礙物之間建立一條單向路徑。

3 基于虛擬勢(shì)場(chǎng)的算法

虛擬勢(shì)場(chǎng)法是障礙物對(duì)機(jī)器人有排斥力且目標(biāo)點(diǎn)對(duì)機(jī)器人有吸引力的算法。人工勢(shì)場(chǎng)法的應(yīng)用相對(duì)比較廣泛,特點(diǎn)在于結(jié)構(gòu)簡單,進(jìn)行規(guī)避障礙物時(shí)能實(shí)時(shí)控制、運(yùn)行平穩(wěn)。人工勢(shì)場(chǎng)示意圖如圖6所示。

圖6 人工勢(shì)場(chǎng)示意圖

傳統(tǒng)的人工勢(shì)場(chǎng)法最早由Khatib在1996年提出,該算法主要用于機(jī)器人實(shí)時(shí)避障。在不同的模擬場(chǎng)景中,人工勢(shì)場(chǎng)法的勢(shì)場(chǎng)函數(shù)差別很大,可以根據(jù)不同的場(chǎng)景進(jìn)行不同的設(shè)定。文獻(xiàn)[55]通過搜索斥力值與引力值之和的最小值,建立障礙物全局信息地圖,進(jìn)行全局規(guī)劃；然后與滾動(dòng)窗口算法結(jié)合,找到當(dāng)前滾動(dòng)窗口中最短的路徑,使機(jī)器人在前進(jìn)過程中依靠滾動(dòng)窗口算法的周期性反饋信息,不斷調(diào)整當(dāng)前路徑,使機(jī)器人可以有效避開動(dòng)態(tài)障礙物到達(dá)目標(biāo)物。文獻(xiàn)[56-58]中傳感器只提供局部環(huán)境信息,根據(jù)得到的環(huán)境信息及時(shí)做出反應(yīng)，指導(dǎo)機(jī)器人運(yùn)動(dòng)；該算法簡單、效率較高,可彌補(bǔ)人工勢(shì)場(chǎng)法易陷入局部極小值、無法達(dá)到目標(biāo)點(diǎn)、造成局部最優(yōu)解的問題。文獻(xiàn)[59]提出了基于人工勢(shì)場(chǎng)的機(jī)器人動(dòng)態(tài)路徑規(guī)劃新方法；在傳統(tǒng)人工勢(shì)場(chǎng)方法中引入相對(duì)速度勢(shì)場(chǎng),對(duì)引力與斥力勢(shì)場(chǎng)增益系數(shù)進(jìn)行優(yōu)化,然后用量子粒子群進(jìn)行快速全局搜索；仿真結(jié)果表明，該方法能夠有效實(shí)現(xiàn)動(dòng)態(tài)路徑規(guī)劃。文獻(xiàn)[60]提出了三維動(dòng)態(tài)空間多機(jī)作業(yè)的優(yōu)化人工勢(shì)場(chǎng)算法；經(jīng)典的人工勢(shì)場(chǎng)算法局限于單機(jī)軌跡規(guī)劃,往往無法避免碰撞,為了克服這一挑戰(zhàn),該文提出了一種帶有距離因子和跳躍策略的方法,將無人機(jī)伙伴作為動(dòng)態(tài)障礙物,實(shí)現(xiàn)協(xié)同軌跡規(guī)劃；并在此基礎(chǔ)上采用動(dòng)態(tài)步長調(diào)整方法，解決抖動(dòng)問題。文獻(xiàn)[61]針對(duì)多機(jī)避碰問題提出了一種改進(jìn)的人工勢(shì)場(chǎng)法,其中障礙物簡化為圓柱體,周圍的人工勢(shì)場(chǎng)近似為球面；人工勢(shì)場(chǎng)的吸引力可以跟蹤目標(biāo),動(dòng)態(tài)空間碰撞路徑取決于具有2個(gè)復(fù)合矢量的人工勢(shì)場(chǎng),每架無人機(jī)都可以避開障礙物選擇最優(yōu)路徑；仿真實(shí)驗(yàn)證明了該算法的有效性。

由虛擬勢(shì)場(chǎng)的相關(guān)原理可知,機(jī)器人在運(yùn)動(dòng)過程中,根據(jù)障礙物與目標(biāo)物對(duì)機(jī)器人產(chǎn)生的引、斥力效果進(jìn)行路徑規(guī)劃。虛擬勢(shì)場(chǎng)在局部規(guī)劃算法中,具有結(jié)構(gòu)相對(duì)簡單、實(shí)時(shí)性較高的特點(diǎn),可以將全局路徑規(guī)劃分為不同的局部規(guī)劃,并在其局部規(guī)劃中穿插使用虛擬勢(shì)場(chǎng),效果較好。通常情況下,虛擬勢(shì)場(chǎng)主要應(yīng)用于實(shí)時(shí)避障,且在障礙物不是過于密集的情況下能夠作出合理的路徑規(guī)劃。

4 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的重要分支,在動(dòng)物行為研究和優(yōu)化控制2個(gè)領(lǐng)域獨(dú)立發(fā)展,解決的主要問題是智能體如何直接與環(huán)境進(jìn)行交互學(xué)習(xí)。強(qiáng)化學(xué)習(xí)算法原理如圖7所示。

圖7 強(qiáng)化學(xué)習(xí)算法原理

Q-Learning算法使移動(dòng)機(jī)器人具有自學(xué)習(xí)能力[62],移動(dòng)機(jī)器人通過與環(huán)境交互,在錯(cuò)誤中進(jìn)行學(xué)習(xí),使機(jī)器人在動(dòng)態(tài)環(huán)境下能夠通過學(xué)習(xí)找到合適的路線[63]。國外強(qiáng)化學(xué)習(xí)算法在路徑規(guī)劃中的應(yīng)用已經(jīng)相對(duì)成熟,文獻(xiàn)[64]在全局信息已知的基礎(chǔ)上,利用Q-Learning和神經(jīng)網(wǎng)絡(luò)的方法實(shí)現(xiàn)動(dòng)態(tài)環(huán)境下障礙物和目標(biāo)物無規(guī)則移動(dòng)條件下的無碰撞路徑規(guī)劃。在國內(nèi)，強(qiáng)化學(xué)習(xí)算法的應(yīng)用同樣取得了長足進(jìn)步。文獻(xiàn)[65]將Q-Learning算法、BP神經(jīng)網(wǎng)絡(luò)及模糊邏輯技術(shù)相結(jié)合,完成了移動(dòng)機(jī)器人在動(dòng)態(tài)和未知環(huán)境下的路徑規(guī)劃及自主避障。文獻(xiàn)[66]在Q-Learning算法的基礎(chǔ)上提出了動(dòng)態(tài)融合機(jī)制,引力勢(shì)場(chǎng)和環(huán)境陷阱聯(lián)合搜索Q值作為先驗(yàn)信息,避免了復(fù)雜環(huán)境中斥力勢(shì)場(chǎng)計(jì)算量大,有效防止了移動(dòng)體陷入環(huán)境中的陷阱,加快了算法的迭代速度，同時(shí)取消對(duì)障礙物的試錯(cuò)學(xué)習(xí),縮小可行路徑的范圍,使訓(xùn)練能應(yīng)用于實(shí)際環(huán)境中。文獻(xiàn)[67]基于強(qiáng)化學(xué)習(xí)的自適應(yīng)方法研究空間機(jī)器人學(xué)習(xí)多種三維結(jié)構(gòu)裝配和施工任務(wù)系統(tǒng),在學(xué)習(xí)過程中采用啟發(fā)式搜索算法尋找四旋翼的最優(yōu)路徑,使四旋翼在動(dòng)態(tài)過程中進(jìn)行路徑規(guī)劃。文獻(xiàn)[68]為了使機(jī)器人在不進(jìn)行任何特征匹配的情況下直接從原始視覺感知中獲得最優(yōu)運(yùn)動(dòng),提出了基于深度強(qiáng)化學(xué)習(xí)端到端的路徑規(guī)劃方法。首先,設(shè)計(jì)并訓(xùn)練了一個(gè)深度Q網(wǎng)絡(luò)(deep Q network,DQN)來逼近移動(dòng)機(jī)器人狀態(tài)動(dòng)作值函數(shù);然后,每個(gè)移動(dòng)機(jī)器人可能的動(dòng)作(即左轉(zhuǎn)、右轉(zhuǎn)、前進(jìn))對(duì)應(yīng)的Q值由訓(xùn)練有素的DQN確定,這里DQN的輸入是從環(huán)境中捕獲的原始RGB圖像(圖像像素),沒有任何手工制作的特征和特征匹配;最后,當(dāng)前移動(dòng)機(jī)器人最佳動(dòng)作由動(dòng)作選擇策略進(jìn)行選擇。文獻(xiàn)[69]基于深度強(qiáng)化學(xué)習(xí)進(jìn)行路徑規(guī)劃,滿足移動(dòng)機(jī)器人的運(yùn)動(dòng)模型和約束條件,在連續(xù)動(dòng)作空間中找到最優(yōu)策略,通過評(píng)價(jià)準(zhǔn)則得到最優(yōu)路徑,并利用移動(dòng)機(jī)器人的運(yùn)動(dòng)模型得到該路徑,從而直接解決了移動(dòng)機(jī)器人的運(yùn)動(dòng)配置問題。文獻(xiàn)[70]針對(duì)動(dòng)態(tài)環(huán)境下的移動(dòng)機(jī)器人,提出了一種基于改進(jìn)Q-Learning算法和啟發(fā)式搜索策略的路徑規(guī)劃方法；在改進(jìn)的Q-Learning算法中將ε與玻爾茲曼相結(jié)合,展開啟發(fā)式搜索策略,減小了搜索空間,限制了定位角的變化范圍;仿真結(jié)果表明,該方法與經(jīng)典的Q-Learning等規(guī)劃方法相比,具有較好的時(shí)間優(yōu)勢(shì)和最優(yōu)路徑選擇能力。

5 結(jié) 論

目前對(duì)于動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的研究是規(guī)劃領(lǐng)域的一個(gè)重要分支。由本文的分析可知,每種路徑規(guī)劃方法都有自身的局限性,僅用一種算法來完成動(dòng)態(tài)環(huán)境下的路徑規(guī)劃不能完全達(dá)到實(shí)時(shí)性的要求,還需要多種算法相互結(jié)合、取長補(bǔ)短。但在實(shí)際應(yīng)用中還會(huì)存在以下問題:

(1) 避碰策略本文只列舉了3種,其他的形式文中未涵蓋完全。這使得相應(yīng)的避碰方法在實(shí)際中可能不適用,未來要結(jié)合實(shí)際情況,應(yīng)對(duì)不同的碰撞方式。

(2) 智能仿生法的穩(wěn)定性與實(shí)時(shí)性較差,得到的解多為最近似解,而且每次規(guī)劃得到的解并不唯一。這為路徑規(guī)劃尋找最優(yōu)解增加了難度,未來要結(jié)合動(dòng)態(tài)環(huán)境信息和應(yīng)用場(chǎng)景來尋求更加有效、快速的路徑規(guī)劃方法。

(3) 基于幾何模型的路徑規(guī)劃對(duì)環(huán)境的適應(yīng)能力強(qiáng),實(shí)時(shí)性相對(duì)較好。未來研究可以利用這些特點(diǎn)，與其他算法相結(jié)合實(shí)現(xiàn)動(dòng)態(tài)環(huán)境下的路徑規(guī)劃。

(4) 強(qiáng)化學(xué)習(xí)無需任何的環(huán)境先驗(yàn)知識(shí),在經(jīng)過反復(fù)試錯(cuò)后就能進(jìn)行良好的路徑規(guī)劃,這將使其在動(dòng)態(tài)環(huán)境下的路徑規(guī)劃具有更加廣泛的應(yīng)用。

隨著機(jī)器人不斷應(yīng)用于動(dòng)態(tài)環(huán)境中,如軍事、戰(zhàn)爭(zhēng)、水下勘探、太空開發(fā)等領(lǐng)域,其路徑規(guī)劃及其優(yōu)化問題更具有挑戰(zhàn)性。但是目前動(dòng)態(tài)規(guī)劃的方法大多只適用于低速的環(huán)境,如何解決路徑規(guī)劃在中、高速三維環(huán)境中的應(yīng)用,是未來研究的趨勢(shì)與難點(diǎn)。