融合蟻群-A*算法的移動(dòng)機(jī)器人路徑規(guī)劃

馬 軍,宋栓軍,韓軍政,熊繼淙,張周強(qiáng),閻文利

(1.西安工程大學(xué) 機(jī)電工程學(xué)院， 陜西 西安 710048；2.航空工業(yè)西安飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司 工具管理中心，陜西 西安 710089)

0 引 言

智能機(jī)器人是無(wú)人工廠中不可或缺的一部分,而其中最重要的就是能讓機(jī)器人對(duì)已知的環(huán)境自主進(jìn)行路徑規(guī)劃。現(xiàn)階段有多種算法可用于機(jī)器人路徑規(guī)劃,比如傳統(tǒng)算法中的RRT算法[1-3]、D*算法[4-5]和動(dòng)態(tài)規(guī)劃算法等[6]。上述算法雖然能找到最終路徑,但是也存在各種缺點(diǎn)。RRT算法進(jìn)行搜索時(shí),只要起點(diǎn)到終點(diǎn)可以連線(xiàn),就會(huì)生成路徑,所以不能保證輸出結(jié)果為最優(yōu)路徑;D*算法只考慮相鄰兩點(diǎn)的距離,極容易陷入局部最優(yōu);動(dòng)態(tài)規(guī)劃算法進(jìn)行搜索時(shí),會(huì)占據(jù)大量的空間,不適合較短的路徑規(guī)劃。為了讓算法能更好適應(yīng)于路徑規(guī)劃,也產(chǎn)生了多種改進(jìn)的算法,如Nazarahari等[7]通過(guò)融合勢(shì)場(chǎng)和遺傳算法尋求最優(yōu)解,該方法可以跳出局部最小值,但是在實(shí)際應(yīng)用中還要考慮路徑規(guī)劃的實(shí)時(shí)性,因此還需要進(jìn)一步的研究;滕儒民等[8]通過(guò)對(duì)A*算法的改進(jìn)來(lái)尋找最優(yōu)解,該方法得到的搜索點(diǎn)較少,能夠快速得到最優(yōu)路徑;易欣等[9]通過(guò)對(duì)遺傳算法的選擇算子進(jìn)行改進(jìn)來(lái)求解,提出的方法能夠較為有效地避免陷入局部最優(yōu),但是收斂速度較慢;而在路徑規(guī)劃求解的問(wèn)題上,蟻群算法是最成功的[10],因此眾多有關(guān)路徑規(guī)劃方面的問(wèn)題都用此算法來(lái)進(jìn)行求解,梁嘉俊等[11]提出使用雙蟻群搜索,可以降低陷入局部搜索的概率來(lái)進(jìn)行求解;Hocaoglu等[12]通過(guò)改進(jìn)蟻群算法信息素更新方式，快速求得最優(yōu)解;李二超等[13]提出將模擬退火和遺傳算法等多種智能算法的融合來(lái)求解最優(yōu)路徑,此種方法是對(duì)NSGA-Ⅱ算法進(jìn)行改進(jìn),根據(jù)給定約束條件,將所有的解集合分為可行性和非可行性解,引導(dǎo)可行性解變?yōu)楦玫慕?可大大減少搜索的時(shí)間；劉俊等[14]提出PSO-ACO融合的算法應(yīng)用于室內(nèi)路徑規(guī)劃,此種改進(jìn)的方法雖然對(duì)蟻群算法有時(shí)陷入“自鎖”的問(wèn)題有所改進(jìn),但是當(dāng)數(shù)據(jù)量增大,路徑的復(fù)雜程度增高,其性能也會(huì)有所降低。

文中提出了一種融合蟻群-A*算法來(lái)進(jìn)行求解,引入A*算法的估價(jià)函數(shù),對(duì)蟻群算法的啟發(fā)函數(shù)和信息素更新方式進(jìn)行改進(jìn)調(diào)整,增加了算法搜索時(shí)的指向性,降低了其陷入“自鎖”的概率,提高了其搜索的速度和精度,以便于其在數(shù)據(jù)量較大時(shí)也可快速尋找最優(yōu)路徑。

1 環(huán)境建模

在路徑規(guī)劃的環(huán)境地圖構(gòu)建中,大多是應(yīng)用柵格法進(jìn)行建模,因此本文也利用柵格法建立了2種不同環(huán)境模型下的仿真地圖,如圖1，2所示。

在Matlab中利用柵格法建立20×20的方格,大小為1 m×1 m,其中黑色為不可通行路段,白色為可通行路段,左上角S(0.5,19.5)處為起點(diǎn),右下角T(19.5,0.5)處為終點(diǎn)。

2 融合蟻群-A*算法

2.1 蟻群算法的數(shù)學(xué)模型

蟻群算法用來(lái)解決路徑規(guī)劃等方面問(wèn)題時(shí),基本的思想就是用螞蟻行走過(guò)的路徑集合來(lái)表示要尋求解決問(wèn)題的可行性方案的集合[15-17]。螞蟻尋優(yōu)過(guò)程在正反饋的作用下,逐漸聚集到最優(yōu)的路徑上,也就是最佳的解決方案,而其中的路徑轉(zhuǎn)移概率為[18]

(1)

(2)

整個(gè)循環(huán)中螞蟻會(huì)不斷的釋放信息素,同時(shí)先前螞蟻釋放的也會(huì)不斷消失,可以設(shè)定一個(gè)參數(shù)ρ(0<ρ<1)表示信息素的揮發(fā)程度。循環(huán)完成后,需要對(duì)其進(jìn)行實(shí)時(shí)的更新,更新方式如式(3)所示:

(3)

2.2 算法改進(jìn)

2.2.1 啟發(fā)函數(shù)的改進(jìn) 蟻群算法雖然可用于求解最優(yōu)路徑,但是其啟發(fā)函數(shù)ηij(t)并未考慮到下一個(gè)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離,這在一定的程度上會(huì)使得算法的搜索速度和效率降低。因此,在蟻群算法的基礎(chǔ)上,融合A*算法,使其遇到自鎖時(shí)可進(jìn)行局部規(guī)劃,從而提高算法的效率。估價(jià)函數(shù)的表達(dá)式為

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

(4)

式中:f(n)為當(dāng)前節(jié)點(diǎn)的估價(jià)函數(shù);g(n)為當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的實(shí)際代價(jià),取值為當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)之間的距離;h(n)為下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的估計(jì)代價(jià),取值為下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間距離[19-20]。從而使得改進(jìn)后的蟻群算法的啟發(fā)函數(shù)變?yōu)?/p>

(5)

式中:dij相當(dāng)于估計(jì)函數(shù)中的g(n);diT則相當(dāng)于h(n)。

2.2.2 信息素更新策略的改進(jìn) 蟻群算法中信息素更新方式容易出現(xiàn)“自鎖”的現(xiàn)象,很難尋得最優(yōu)解。因此在每次更新后計(jì)算出平均路徑,并且記錄最優(yōu)路徑和最長(zhǎng)路徑,如果此次路徑長(zhǎng)度沒(méi)有上次短,則將其引入信息素更新策略中,從而降低陷入局部最優(yōu)的可能,并且又能保證快速求解的能力,新的信息素更新方式為

(6)

式中:da為平均路徑;dm為最長(zhǎng)路徑;dl為最優(yōu)路徑；k為迭代次數(shù)。

改進(jìn)后的算法步驟如下:

1) 柵格地圖的構(gòu)建, 建立對(duì)應(yīng)的描述矩陣用于存儲(chǔ)障礙物情況。

2) 對(duì)算法的參數(shù)的初始化。

3) 將螞蟻放置出發(fā)點(diǎn)。

4) 根據(jù)轉(zhuǎn)移概率公式選擇下一節(jié)點(diǎn)。

5) 更新運(yùn)動(dòng)節(jié)點(diǎn)禁忌表并判斷螞蟻是否運(yùn)動(dòng)至目標(biāo)節(jié)點(diǎn), 如若螞蟻無(wú)路可走判定該螞蟻已陷入自鎖,進(jìn)入步驟6)。

6) 隨機(jī)選擇是否進(jìn)行操作, 若未被選擇, 則此螞蟻徹底自鎖。若被選擇, 借助 A*算法進(jìn)行局部路徑規(guī)劃,并將局部路線(xiàn)與已經(jīng)探索路線(xiàn)進(jìn)融合拼接。

7) 對(duì)全局信息素進(jìn)行更新。并將當(dāng)前迭代次數(shù)的平均路徑,最優(yōu)和最長(zhǎng)路徑進(jìn)行記錄。

8) 判斷當(dāng)前最優(yōu)路徑和上代最優(yōu)路徑的大小,如果當(dāng)前路徑較小,則進(jìn)行下一步,否則輸出最優(yōu)路徑的同時(shí)將平均路徑,最優(yōu)和最長(zhǎng)路徑引入信息素更新策略中進(jìn)行下次迭代。

9) 判斷是否迭代到200次,如果是,則輸出最優(yōu)路徑,否則執(zhí)行步驟2)。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證文中的算法,在Matlab仿真軟件上進(jìn)行實(shí)驗(yàn),先后采用2種不同環(huán)境對(duì)其進(jìn)行仿真實(shí)驗(yàn),初始參數(shù)設(shè)定:螞蟻代數(shù)為200代,螞蟻個(gè)數(shù)為50只,α=3,β=7,ρ=0.3,Q=1,每種環(huán)境各仿真100次。

在環(huán)境模型1中進(jìn)行仿真實(shí)驗(yàn), 實(shí)驗(yàn)的收斂曲線(xiàn)和最優(yōu)路徑軌跡對(duì)比圖如圖3和圖4所示。 表1為環(huán)境1仿真結(jié)果對(duì)比, 表2為環(huán)境2仿真結(jié)果對(duì)比。

表 1 環(huán)境1仿真結(jié)果對(duì)比Tab.1 Comparison of environment 1 simulation results

表 2 環(huán)境2仿真結(jié)果對(duì)比Tab.2 Comparison of environment 2 simulation results

圖 3 環(huán)境1收斂曲線(xiàn)對(duì)比Fig.3 Comparison of environment 1convergence curve

從圖3可知,本文算法在前期搜索時(shí),有一定的波動(dòng),但是隨著搜索的進(jìn)行,慢慢趨于平穩(wěn),搜索的路徑越來(lái)越短。從表1可知，蟻群算法從17代進(jìn)行收斂,本文算法從13代開(kāi)始收斂,且收斂速度也快于蟻群算法。

圖 4 環(huán)境1最優(yōu)路徑對(duì)比Fig.4 Comparison of environment 1optimal path

從圖4可知本文算法的路徑明顯優(yōu)于蟻群算法,而表1中數(shù)據(jù)也顯示,將最優(yōu)和最長(zhǎng)路徑引入信息素更新策略中進(jìn)行下次迭代,無(wú)論是最優(yōu)路徑長(zhǎng)度還是平均路徑長(zhǎng)度以及算法的平均耗時(shí)都明顯優(yōu)于蟻群算法,并且最優(yōu)解出現(xiàn)的次數(shù)比蟻群算法多。

在環(huán)境模型2中進(jìn)行仿真實(shí)驗(yàn),實(shí)驗(yàn)的收斂曲線(xiàn)和最優(yōu)路徑軌跡對(duì)比如圖5和圖6所示。

圖 5 環(huán)境2收斂曲線(xiàn)對(duì)比Fig.5 Comparison of environment 2convergence curve

圖 6 環(huán)境2最優(yōu)路徑對(duì)比Fig.6 Comparison of environment 2optimal path

從圖5和圖6可知,在相對(duì)復(fù)雜的環(huán)境模型2中,本文算法相對(duì)于蟻群算法可以相對(duì)快速的進(jìn)行收斂。而從表2的數(shù)據(jù)中可以具體看出相對(duì)復(fù)雜的環(huán)境下本文的算法最優(yōu)路徑長(zhǎng)度為29.799 0 m,優(yōu)于蟻群算法的32.213 2 m;最優(yōu)解出現(xiàn)的次數(shù)為63次,遠(yuǎn)遠(yuǎn)大于蟻群算法的31次,并且程序的耗時(shí)較蟻群算法減少了2 s。

綜上，當(dāng)環(huán)境變得相對(duì)復(fù)雜時(shí),本文的算法也可快速進(jìn)行收斂,并且在最優(yōu)路徑上明顯優(yōu)于蟻群算法,這表明改進(jìn)后的算法是有效的,并且能夠適用于不同的復(fù)雜環(huán)境。

4 結(jié) 語(yǔ)

蟻群算法在路徑規(guī)劃時(shí)收斂速度比較慢,并且容易陷入“自鎖”等問(wèn)題,本文提出了一種改進(jìn)的方法,將A*算法的估價(jià)函數(shù)思想引入蟻群算法的信息素更新方式中,給螞蟻的搜索添加一個(gè)指向性,以便快速的尋找出最優(yōu)的路徑。在Matlab上進(jìn)行仿真,實(shí)驗(yàn)結(jié)果表明本文算法在收斂速度上優(yōu)先于蟻群算法4～6代,在最優(yōu)路徑上也優(yōu)于蟻群算法2～3 m,程序的運(yùn)行速度上也較之快了2～3 s,且在最優(yōu)解出現(xiàn)的次數(shù)上遠(yuǎn)遠(yuǎn)大于蟻群算法,證明本文算法有效、實(shí)用。