基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃

張曉玲,王正存,吳作君

(中國(guó)石油大學(xué)勝利學(xué)院 機(jī)械與控制工程學(xué)院,山東 東營(yíng) 257061)

機(jī)器人路徑規(guī)劃問(wèn)題是指,在已知機(jī)器人的起始和目的地坐標(biāo),明確環(huán)境信息條件下,找到一條能連接起始坐標(biāo)和目的地坐標(biāo)的最短路徑?，F(xiàn)有的機(jī)器人路徑規(guī)劃方法有蟻群算法(Ant Colony Algorithm,ACO)[1],神經(jīng)網(wǎng)絡(luò)算法[2],人工勢(shì)場(chǎng)法[3],模擬退火算法[4]等。其中智能路徑規(guī)劃算法中的蟻群算法在機(jī)器人路徑規(guī)劃中被廣泛應(yīng)用。蟻群算法是由意大利學(xué)者M(jìn).Dorigo[5]在1991年提出的一種受自然界生物的自催化行為啟發(fā)而產(chǎn)生的通用啟發(fā)式進(jìn)化算法。它采用正反饋機(jī)制、分布式計(jì)算方法,具有較強(qiáng)的優(yōu)化能力和較強(qiáng)的魯棒性[6],經(jīng)常用來(lái)解決各種分布式環(huán)境下的組合優(yōu)化問(wèn)題。蟻群算法不足之處在于,尋優(yōu)過(guò)程中當(dāng)問(wèn)題規(guī)模變大時(shí),存在收斂精度變低問(wèn)題。筆者采用改進(jìn)的蟻群算法在搜索路徑過(guò)程中,使用模擬退火算法迭代和蟻群算法進(jìn)行搜索路徑,利用回火條件,可以尋找到最優(yōu)路徑。

1　機(jī)器人運(yùn)行環(huán)境建模

機(jī)器人路徑規(guī)劃首先需要對(duì)其運(yùn)行環(huán)境或工作空間建模,考慮到柵格分解法具有精度高、方便實(shí)現(xiàn)等優(yōu)點(diǎn),因此選用柵格法對(duì)機(jī)器人環(huán)境進(jìn)行劃分。

設(shè)機(jī)器人的工作環(huán)境為二維平面上的方格區(qū)域,起始坐標(biāo)和目的地坐標(biāo)分別表示為S和T。每個(gè)柵格采用經(jīng)緯度坐標(biāo)進(jìn)行位置標(biāo)示,并以地圖左下角的柵格S為機(jī)器人的起點(diǎn),右上角柵格T為機(jī)器人的目的地。采用序號(hào)法對(duì)圖1中每一個(gè)柵格進(jìn)行編號(hào),其中黑色方塊表示環(huán)境中的障礙物,并采用八叉樹(shù)表示路徑搜索方向。

如果機(jī)器人在柵格地圖上t時(shí)刻所在的經(jīng)緯度為L(zhǎng)t(xt,yt),則在下一時(shí)刻的位置為L(zhǎng)t+1(xt+1,yt+1),此次移動(dòng)長(zhǎng)度dt為

(1)

假設(shè)從設(shè)置的起始點(diǎn)開(kāi)始移動(dòng),要經(jīng)過(guò)n步到達(dá)所設(shè)目標(biāo)終點(diǎn),則此次所尋找路徑的長(zhǎng)度為

(2)

用柵格法建立機(jī)器人的運(yùn)行環(huán)境和工作空間模型后,下一步則需要結(jié)合合理有效的優(yōu)化方法尋找所有路徑中最短的路徑。

圖1　柵格地圖模型

2　基于傳統(tǒng)蟻群算法的路徑規(guī)劃

2.1　蟻群覓食分析

研究發(fā)現(xiàn),每只螞蟻覓食過(guò)程中在其行走路徑上會(huì)留下一種為信息素的化學(xué)物質(zhì),一定范圍內(nèi)的其他螞蟻能感覺(jué)到這種物質(zhì),且傾向于朝信息素濃度高的方向移動(dòng)[7]。如果在某一條所走過(guò)的路徑上被留下的信息素總量的濃度越高,則其他螞蟻傾向選擇這條路徑的概率就會(huì)越大,因此有了信息素這種媒介物質(zhì),最終使得絕大多數(shù)螞蟻選擇最短的路徑行走。

2.2　基于傳統(tǒng)蟻群算法的機(jī)器人路徑規(guī)劃步驟

步驟1:將算法中各類(lèi)參數(shù)初始化,如蟻群中螞蟻數(shù)量、最大迭代次數(shù)等;

步驟2:在柵格地圖初始化時(shí),將機(jī)器人看做一只螞蟻,螞蟻運(yùn)動(dòng)時(shí)受到各路徑上信息素濃度影響,根據(jù)每條路徑上的信息濃度決定下一步方向。螞蟻在t時(shí)刻當(dāng)前位置為i,往位置j移動(dòng)的概率Pij(t)為

(3)

式中,α,β為控制信息素和啟發(fā)信息影響大小的參數(shù);allowed是可選的前進(jìn)方向集合。

步驟3:計(jì)算每個(gè)螞蟻所產(chǎn)生的路徑長(zhǎng)度。

步驟4:更新信息素濃度。

τij(t+1)=ρτij(t)+Δτij(t,t+1).

(4)

(5)

式中,τij(t+1)為在第t次迭代時(shí)邊ij上的螞蟻釋放的信息素;ρ為信息素維持因子;Δτij(t,t+1)為每個(gè)螞蟻在某個(gè)邊ij上留下所產(chǎn)生信息素之和。

步驟5:使所有螞蟻執(zhí)行步驟2,得到n條路徑,找出所有路徑中最短的可行路徑,并按式(4)更新信息素矩陣。

步驟6:將當(dāng)前迭代值與設(shè)定的最高迭代值進(jìn)行比較,若超過(guò)限定值則終止循環(huán)迭代,否則回到步驟2,進(jìn)入下一次迭代過(guò)程,直到滿(mǎn)足該條件退出。

3　基于改進(jìn)蟻群算法的路徑規(guī)劃

3.1　模擬退火算法

模擬退火算法是對(duì)金屬退火過(guò)程的模擬,先用高溫將金屬融化,然后逐漸冷卻,直到形成良好的晶體結(jié)構(gòu),即進(jìn)入一種具有最小能量的狀態(tài)[8]。模擬退火算法也可用于路徑規(guī)劃算法以避免陷入局部最優(yōu)。

模擬退火算法迭代過(guò)程如下。

第一步:某個(gè)溫度T下得到一個(gè)解(結(jié)合蟻群算法時(shí),指用蟻群算法優(yōu)化得到的解)。

第二步:若當(dāng)前溫度T下得到的解比前一時(shí)刻溫度的解好,則采用這個(gè)新的解,否則轉(zhuǎn)第三步。

第三步:計(jì)算溫度T下接受劣解的概率。

(6)

其中,隨機(jī)產(chǎn)生一個(gè)[0,1]區(qū)間的隨機(jī)數(shù)X,如果X

從P的計(jì)算公式可以看到,隨著溫度T的上升,P的值是越來(lái)越小的,隨著迭代的進(jìn)行,接受劣解的概率下降,與自然界中晶體退火結(jié)晶的過(guò)程非常相似,從而實(shí)現(xiàn)了模擬退火算法。

3.2　帶回火的模擬退火-蟻群算法路徑規(guī)劃步驟

采用模擬退火-蟻群算法進(jìn)行路徑尋優(yōu)時(shí),加入回火,回火機(jī)制是指當(dāng)溫度低于設(shè)定回火下限溫度時(shí),溫度慢慢升溫到回火上限溫度。回火本質(zhì)上是在一段溫度范圍內(nèi)反復(fù)循環(huán)降溫過(guò)程,使得當(dāng)前解不斷得到優(yōu)化,可以得到更好的解,消除快速降溫時(shí)產(chǎn)生的局部最優(yōu)[8]。因此帶回火的模擬退火-蟻群算法的迭代步驟如下。

步驟1:初始化算法中各類(lèi)參數(shù),如蟻群中螞蟻的數(shù)量antnumber,迭代次數(shù)maxgen,冷卻系數(shù)q,初始溫度T0,回火溫度下限Tmin,回火溫度上限Tmax,回火次數(shù)Hmax等。

步驟2:設(shè)置蟻群算法的啟發(fā)值和信息素濃度的初始大小進(jìn)行模擬退火-蟻群算法的尋優(yōu)。

步驟3:進(jìn)行螞蟻搜索,設(shè)置起點(diǎn)并根據(jù)式(3)計(jì)算螞蟻向各個(gè)方向移動(dòng)的概率Pij,并根據(jù)概率公式移動(dòng)到新位置后再進(jìn)一步計(jì)算下一步移動(dòng)的概率并移動(dòng),重復(fù)這個(gè)過(guò)程直到搜索到所設(shè)定的目的地或者找不到目的地直接退出。

步驟4:計(jì)算目標(biāo)函數(shù),判斷新路線(xiàn)是否優(yōu)于原有路線(xiàn),如果優(yōu)于則接受新路線(xiàn),轉(zhuǎn)到步驟5;否則根據(jù)模擬退火機(jī)制按照式(6)計(jì)算接受較劣新線(xiàn)路(劣解)的概率,若概率滿(mǎn)足條件則接受劣解,否則放棄。

步驟5:根據(jù)式(4)、(5)進(jìn)行信息素濃度更新,并更新溫度(模擬退火冷卻過(guò)程,溫度逐漸降低),判斷是否滿(mǎn)足回火條件(回火次數(shù)未達(dá)到或者溫度低于最小回火溫度),滿(mǎn)足則進(jìn)行回火,回火次數(shù)自增1。

步驟6:判斷模擬退火算法迭代過(guò)程是否已經(jīng)完成,若未完成則繼續(xù)下一步迭代運(yùn)算,相反,若完成則結(jié)束迭代循環(huán)。

步驟7:輸出結(jié)果,算法運(yùn)行結(jié)束。

4　仿真研究

首先隨機(jī)生成一個(gè)15×15的柵格地圖仿真機(jī)器人路徑搜索的運(yùn)行環(huán)境,然后基于同一地圖,分別運(yùn)用傳統(tǒng)蟻群算法和帶回火的模擬退火-蟻群算法進(jìn)行機(jī)器人路徑規(guī)劃的仿真研究,得到結(jié)果如圖2～5所示。

比較圖2和圖4的目標(biāo)函數(shù)值(最優(yōu)路徑長(zhǎng)度)可以看出,傳統(tǒng)蟻群算法穩(wěn)定在175左右,改進(jìn)的帶回火模擬退火-蟻群算法穩(wěn)定在163左右。圖3和圖5的路徑搜索線(xiàn)路也表明,相對(duì)傳統(tǒng)的標(biāo)準(zhǔn)蟻群算法,本文提出改進(jìn)后的優(yōu)化方法查找到的移動(dòng)路徑明顯更短。但通過(guò)觀(guān)察圖2和圖4兩種算法下的迭代次數(shù),發(fā)現(xiàn)改進(jìn)蟻群算法在迭代次數(shù)(63次)上稍遜于傳統(tǒng)蟻群算法(57次)。為更合理地對(duì)比傳統(tǒng)蟻群和改進(jìn)蟻群算法,在不同大小的柵格地圖上對(duì)兩種算法進(jìn)行多次仿真試驗(yàn),結(jié)果如表1所示,分別記錄了各自的迭代次數(shù)、最短路徑值和平均運(yùn)行時(shí)間。

圖2　傳統(tǒng)蟻群算法優(yōu)化過(guò)程

圖3　傳統(tǒng)蟻群算法最優(yōu)路徑

圖4　改進(jìn)蟻群算法優(yōu)化過(guò)程

圖5　改進(jìn)蟻群算法最優(yōu)路徑

柵格地圖大小迭代次數(shù)傳統(tǒng)算法改進(jìn)算法最優(yōu)路徑長(zhǎng)度傳統(tǒng)算法改進(jìn)算法運(yùn)行時(shí)間/s傳統(tǒng)算法改進(jìn)算法 11×114574165.8155.25.96.3 15×155763174.9163.214.914.4 20×205379191.2188.233.731.0 25×254759199.6182.682.880.6 30×307479200.0208.4195.0193.3 35×359196248.1208.7274.9257.0 40×407474222.7199.1452.1438.0

對(duì)表1分析可得,改進(jìn)算法在迭代次數(shù)上雖不占優(yōu)勢(shì),略高于傳統(tǒng)算法,但兩種算法基于同一大小的柵格環(huán)境下實(shí)際運(yùn)行時(shí)間相差無(wú)幾,反而在柵格不斷增多的情況下,改進(jìn)算法的收斂速度要快于傳統(tǒng)蟻群算法。從最優(yōu)路徑方面比較,除了在30×30大小的柵格地圖上改進(jìn)算法得到的最優(yōu)路徑相對(duì)傳統(tǒng)算法稍長(zhǎng),其他結(jié)果均明顯優(yōu)于傳統(tǒng)蟻群算法。因此,綜合看來(lái),在機(jī)器人尋找最優(yōu)路徑上,改進(jìn)蟻群算法有一定的優(yōu)越性。

5　結(jié)束語(yǔ)

針對(duì)基本的蟻群算法在解決移動(dòng)機(jī)器人路徑規(guī)劃尋找最優(yōu)搜索路徑時(shí)存在收斂精度不夠的問(wèn)題,引入帶回火的模擬退火原理處理蟻群算法得到的路徑值,從而提出一種改進(jìn)算法。最終的改進(jìn)蟻群算法相比傳統(tǒng)蟻群算法,具有更強(qiáng)的尋優(yōu)能力,能夠找到更好的機(jī)器人移動(dòng)路徑。