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

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

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

0 引 言

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

文中提出了一種融合蟻群-A*算法來進(jìn)行求解,引入A*算法的估價(jià)函數(shù),對蟻群算法的啟發(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é)模型

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

(1)

(2)

整個(gè)循環(huán)中螞蟻會不斷的釋放信息素,同時(shí)先前螞蟻釋放的也會不斷消失,可以設(shè)定一個(gè)參數(shù)ρ(0<ρ<1)表示信息素的揮發(fā)程度。循環(huán)完成后,需要對其進(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)之間的距離,這在一定的程度上會使得算法的搜索速度和效率降低。因此,在蟻群算法的基礎(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)路徑和最長路徑,如果此次路徑長度沒有上次短,則將其引入信息素更新策略中,從而降低陷入局部最優(yōu)的可能,并且又能保證快速求解的能力,新的信息素更新方式為

(6)

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

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

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

2) 對算法的參數(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), 如若螞蟻無路可走判定該螞蟻已陷入自鎖,進(jìn)入步驟6)。

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

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

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

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

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

為了驗(yàn)證文中的算法,在Matlab仿真軟件上進(jìn)行實(shí)驗(yàn),先后采用2種不同環(huán)境對其進(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)的收斂曲線和最優(yōu)路徑軌跡對比圖如圖3和圖4所示。 表1為環(huán)境1仿真結(jié)果對比, 表2為環(huán)境2仿真結(jié)果對比。

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

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

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

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

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

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

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

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

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

從圖5和圖6可知,在相對復(fù)雜的環(huán)境模型2中,本文算法相對于蟻群算法可以相對快速的進(jìn)行收斂。而從表2的數(shù)據(jù)中可以具體看出相對復(fù)雜的環(huán)境下本文的算法最優(yōu)路徑長度為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)境變得相對復(fù)雜時(shí),本文的算法也可快速進(jìn)行收斂,并且在最優(yōu)路徑上明顯優(yōu)于蟻群算法,這表明改進(jìn)后的算法是有效的,并且能夠適用于不同的復(fù)雜環(huán)境。

4 結(jié) 語

蟻群算法在路徑規(guī)劃時(shí)收斂速度比較慢,并且容易陷入“自鎖”等問題,本文提出了一種改進(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í)用。