優(yōu)化多步長蟻群算法求解機(jī)器人路徑規(guī)劃問題*

胡佳斌,王祥澍,張 琪,全瑞坤

(1.重慶大學(xué) 重慶大學(xué)—辛辛那提大學(xué)聯(lián)合學(xué)院,重慶 400044；2.重慶大學(xué) 電氣工程學(xué)院,重慶 400044)

0 引 言

機(jī)器人路徑規(guī)劃問題指在有障礙物的環(huán)境中,搜索規(guī)劃一條從起點到終點距離最短的無碰撞路徑。路徑規(guī)劃問題是機(jī)器人導(dǎo)航與控制的基礎(chǔ)問題,在無人駕駛技術(shù)快速發(fā)展,智慧城市建設(shè)過程中,其作為一項核心技術(shù)得到更多的重視?，F(xiàn)有的路徑規(guī)劃算法包括粒子群算法[1]、遺傳算法[2]、人工勢場算法[3]、模擬退火算法[4]和A*算法[5]。粒子群算法計算簡單,但其后期收斂緩慢且易于局部最優(yōu)解；遺傳算法魯棒性較強(qiáng),能夠得到全局最優(yōu)解,但其所需計算量大,收斂過慢,局部搜索能力差；人工勢場法計算量小,路徑平滑,但易陷入局部最優(yōu)；模擬退火算法局部搜索能力強(qiáng),運算較快,但初始參數(shù)對結(jié)果影響較大,易陷入局部最優(yōu)。A*算法效率高,操作簡單,但其受到評估函數(shù)影響,后期計算量大且路徑未必最優(yōu)[6]。

蟻群優(yōu)化(ant colony optimization,ACO)算法因具有正反饋,較強(qiáng)的魯棒性,易于與其他算法結(jié)合等優(yōu)點,一直受到了研究人員的廣泛關(guān)注。但其存在搜索時間長,收斂慢,易被初始參數(shù)影響,易局部最優(yōu)等問題。很多學(xué)者針對其缺陷進(jìn)行研究和改進(jìn)。文獻(xiàn)[7]通過加大對迭代過程最優(yōu)解的利用,加快算法的收斂速度,但是容易限于局部最優(yōu)解；文獻(xiàn)[8]以自適應(yīng)信息素?fù)]發(fā)系統(tǒng)改進(jìn)信息素更新的方式,增強(qiáng)算法的全局搜索能力；文獻(xiàn)[9]通過將螞蟻每次固定移動一個步長擴(kuò)大至多個步長,加快蟻群算法的收斂程度；文獻(xiàn)[10]通過對于螞蟻信息素初始的分配加快蟻群算法前期的收斂。

本文基于蟻群算法對機(jī)器人的路徑規(guī)劃問題進(jìn)行求解。

將多步長蟻群算法與簡化算子[4]結(jié)合,并對蟻群算法的啟發(fā)函數(shù)以及信息素更新公式進(jìn)行改進(jìn),從而加快蟻群算法的收斂速度,獲得更優(yōu)化的蟻群算法路徑長度。

1 柵格法

路徑規(guī)劃的地圖構(gòu)建方法主要包括柵格法、幾何法和拓?fù)浞╗5]三種方法,本文采用柵格法進(jìn)行地圖建模,使用20×20的柵格地圖,每個柵格的邊長為1,將機(jī)器人視為處于柵格中心,機(jī)器人只能從一個柵格中心移至另一柵格中心。

2 蟻群算法的基本原理

蟻群算法是模擬自然界螞蟻運動中隨機(jī)過程的一種算法。螞蟻在移動過程中會留下信息素,信息素會隨著時間的推移而不斷揮發(fā)。多個螞蟻經(jīng)過的地方,留下的信息素濃度會不斷增加,進(jìn)而吸引更多的螞蟻選擇,形成正向反饋，最后,螞蟻便會形成一條最優(yōu)路徑。

2.1 狀態(tài)轉(zhuǎn)移概率

在蟻群算法中,第k輪第m只螞蟻從i點到j(luò)點的概率為

(1)

式中allowedm為可選節(jié)點；τij為i點到j(luò)點的信息素濃度；ηij為啟發(fā)函數(shù)；ηij為j點到i點距離的倒數(shù);α為信息素的啟發(fā)因子,其值越大,信息素的影響就越大,隨機(jī)性就越差;β為啟發(fā)函數(shù)影響因子,其值越大,越容易陷入局部最優(yōu)。

2.2 信息素更新

自然界的信息素會隨著時間推移不斷揮發(fā),在蟻群算法中,每一輪所有螞蟻完成自己的路線后,路徑上的信息素濃度都會被更新

τij(n+1)=(1-p)τij(n)+Δτij

(2)

(3)

式中Q為信息素濃度常量,而Lk為本次螞蟻迭代所經(jīng)歷的距離長度。

3 改進(jìn)蟻群算法設(shè)計

傳統(tǒng)蟻群算法存在收斂速度慢和路徑會出現(xiàn)冗余拐點。因此,本文從信息素更新方法和增加規(guī)劃路徑平滑度方面對算法進(jìn)行了改進(jìn)。

3.1 改進(jìn)的啟發(fā)函數(shù)

初始的蟻群算法采用啟發(fā)函數(shù)為

(4)

式中dij為機(jī)器人目前位置到下一個位置的距離。

此函數(shù)設(shè)計將導(dǎo)致機(jī)器人傾向于向正向移動,使算法陷入局部最優(yōu)。故本文將啟發(fā)函數(shù)改為

(5)

式(5)即只考慮機(jī)器人下一個可移動節(jié)點與終點的距離關(guān)系。這樣機(jī)器人就更傾向于選擇更靠近終點的節(jié)點,從而加快算法的收斂速度。

3.2 視野域與活動域[9]

傳統(tǒng)蟻群算法中,機(jī)器人只能向周圍8個方向移動,這種移動方法會導(dǎo)致最終規(guī)劃路徑存在大量冗余拐點。多步長蟻群算法中,其引入視野域與活動域的概念。機(jī)器人移動的可選節(jié)點為視野域范圍內(nèi)的可活動域[9]。如圖1所示,此圖為7×7的機(jī)器人視野域,機(jī)器人位于正中心的柵格中,節(jié)點{4,5,6,7,9,10,11,12,15,16,17,18,19,20,21,22,23,24,26,27,28,29,30,33,34,40}為機(jī)器人的可行域。機(jī)器人可移動方向增加,移動靈活性增強(qiáng),全局搜索能力增強(qiáng)。

圖1 多步長蟻群算法range為3時的視野域

3.3 簡化算子[4]

簡化算子可以減少規(guī)劃路徑冗余拐點,縮短路徑長度。假設(shè)一條原始路徑為P,將路徑上的拐點依次記為P1,P2,P3,…,Pn,如圖2所示，此圖中n=4。

圖2 未經(jīng)過簡化算子的路徑

接著對路徑進(jìn)行簡化循環(huán),將簡化起始點Ps(第一次循環(huán)時s=1)依次與下一個點Pk(s+2,s+3,...,n)相連并進(jìn)行判斷,若兩點間無障礙物,則保留此點Pk。選擇此次循環(huán)最大的k值,連接Ps與Pk,保留該條連線,同時將s更新為k-1,繼續(xù)循環(huán),直到s=n-2 時,停止循環(huán)。此時所有的點都進(jìn)行過簡化判斷,簡化過程結(jié)束。簡化完成的路徑如圖3所示。

圖3 經(jīng)過簡化算子后的路徑

每次迭代的所有螞蟻走完全程后,對所有到達(dá)終點的螞蟻路徑使用簡化算子進(jìn)行簡化,并用簡化后的新路徑替代原有路徑。經(jīng)過簡化算子處理的路徑拐點更少,路徑長度更短。

簡化過程中,需要判斷兩點之間是否存在障礙,所需運算量較為龐大。為了簡化計算,本文加入了黑名單機(jī)制。初始黑名單將設(shè)置一個400×400的矩陣,表示點與點之間的通行關(guān)系,1表示不能通行,0表示可以通行。簡化過程中,先通過黑名單判斷Ps與Pk之間是否可以連通。如果連通，則進(jìn)行簡化運算并更新這兩點的活動域；反之且這兩點不在黑名單內(nèi),則先更新黑名單再進(jìn)行簡化運算。黑名單機(jī)制在算法后期可以大量縮減計算量,增加運算速度。

3.4 差異化信息素更新

傳統(tǒng)蟻群算法中,不管是對于優(yōu)質(zhì)解還是劣質(zhì)解,信息素更新方法都對它們一視同仁。該方法既未排除劣質(zhì)解的干擾也未能發(fā)揮優(yōu)質(zhì)解的指導(dǎo)作用,減慢了算法的收斂。因此,本文將會采用差異化的信息素更新方法。同時,因為簡化算子的加入,新的算法將在對路徑進(jìn)行簡化運算前后分別進(jìn)行兩次更新

(6)

此處引入新變量Lk,對于走過不同路徑長的螞蟻選擇不同的Lk值,并且對所有螞蟻走過的路徑長度進(jìn)行排序,并將排名記為n。本文中,第一次更新時,當(dāng)n≤10時,Lk取3;當(dāng)n∈[11,20]時,Lk取0.7；對于其他的n值,Lk都取0。第二次更新時,當(dāng)n≤3時,Lk取10;當(dāng)n∈[4,10]時,Lk取1；對于其他的n值,Lk都取0。差異化的信息素更新方法拉大了劣質(zhì)解和優(yōu)質(zhì)解對算法影響的差異,增加了算法的收斂速度。

4 改進(jìn)的多步長蟻群算法步驟

1)初始化本文算法的參數(shù)；2)根據(jù)起止點位置建立柵格地圖,初始化地圖信息素分布；3)基于參數(shù)和地圖信息,設(shè)置機(jī)器人的視野域以及初始黑名單；4)每只螞蟻尋找未走過的柵格,用式(1)～式(4)計算出每一個可選格子的概率,用Random函數(shù)進(jìn)行下一步選擇,不斷重復(fù)此步,直至螞蟻沒有可選柵格或達(dá)到終點；5)根據(jù)式(6)更新本輪所有螞蟻留下的信息素信息；6)使用簡化算子對路徑進(jìn)行優(yōu)化,更新每個格子的活動域與黑名單；7)根據(jù)式(6)更新簡化算子后的螞蟻留下的信息素信息；8)通過循環(huán)步驟(4)～步驟(7),直到達(dá)到最大迭代次數(shù),并最終找出最優(yōu)路徑。

5 仿真對比分析

本文針對多步長蟻群算法的不足,做出了相應(yīng)改變。并在CPU為酷睿i7—8750H@2.20GHz的電腦上,MATLAB R2018a軟件進(jìn)行仿真驗證。機(jī)器人初始位置為(1,1),目標(biāo)點位置為(20,20)。蟻群算法參數(shù)為：信息素影響因子α=1,激勵函數(shù)影響因子β=7,初始鄰域范圍range=3,信息素?fù)]發(fā)因子ρ=0.3,迭代次數(shù)k=100,螞蟻數(shù)量m=50。

與傳統(tǒng)蟻群算法以及文獻(xiàn)[9]的多步長蟻群優(yōu)化(multi-step ant colony optimization,MACO)算法進(jìn)行對比,圖4(a)是ACO算法的路徑規(guī)劃,圖4(b)是結(jié)合了改進(jìn)的啟發(fā)函數(shù),簡化算子,差異化信息素更新的簡化算子蟻群優(yōu)化(simplified ant colony optimization,SACO)算法的路徑規(guī)劃,圖4(c)是文獻(xiàn)[9]的MACO算法的路徑規(guī)劃,圖4(d)是在SACO的基礎(chǔ)上添加視覺域與活動域形成的簡化算子多步長蟻群優(yōu)化(simplified multi-step ant colony optimization,SMACO)算法的路徑規(guī)劃。

圖4 四種算法的路徑規(guī)劃

四種算法對應(yīng)的長度分別是42.83,30.77,32.19和29.70。

為避免隨機(jī)誤差,表1中ACO,SACO以及SMACO的值均為10次實驗的平均數(shù)。根據(jù)表1可以看出,SACO,MACO和SMACO與傳統(tǒng)的ACO算法在收斂趨勢,拐點數(shù),最優(yōu)路徑長度均有明顯優(yōu)勢,證明其三種算法均優(yōu)于ACO算法。在路徑長度上,SMACO算法與SACO算法小于MACO算法,證明改進(jìn)的啟發(fā)函數(shù),簡化算子,差異化信息素更新這三種改進(jìn)措施的結(jié)合可以增強(qiáng)算法的全局搜索能力。此外,與SACO算法相對比,SMACO算法的拐點數(shù)有所減小,且SMACO算法與SACO算法再路徑規(guī)劃上相差小于0.5,證明視野域與活動域在不影響路徑規(guī)劃長度的情況下,本文算法在平滑度上起到了優(yōu)化作用。圖5所示為四種算法的收斂變化趨勢。

表1 四種算法對比

圖5 四種算法的收斂變化趨勢

6 結(jié) 論

本文提出結(jié)合簡化算子和多步長的蟻群算法用于解決機(jī)器人路徑規(guī)劃問題。簡化算子可以減少規(guī)劃路徑的冗余拐點,進(jìn)一步提升全局搜索能力；差異化信息素更新方法拉大優(yōu)劣質(zhì)解的差異,加快收斂速度。仿真實驗表明：本文算法在收斂速度上不是最優(yōu),且參數(shù)增多更加難以控制,但是迭代收斂速度明顯優(yōu)于原蟻群算法,最終規(guī)劃路徑在三種蟻群算法中最短,全局搜索能力最強(qiáng)。同時,本文算法的路徑拐點數(shù)最少,方便機(jī)器人的移動。