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

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

0 引 言

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

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

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

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

1 柵格法

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

2 蟻群算法的基本原理

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

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

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

(1)

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

2.2 信息素更新

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

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

(2)

(3)

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

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

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

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

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

(4)

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

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

(5)

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

3.2 視野域與活動(dòng)域[9]

傳統(tǒng)蟻群算法中,機(jī)器人只能向周圍8個(gè)方向移動(dòng),這種移動(dòng)方法會(huì)導(dǎo)致最終規(guī)劃路徑存在大量冗余拐點(diǎn)。多步長(zhǎng)蟻群算法中,其引入視野域與活動(dòng)域的概念。機(jī)器人移動(dòng)的可選節(jié)點(diǎn)為視野域范圍內(nèi)的可活動(dòng)域[9]。如圖1所示,此圖為7×7的機(jī)器人視野域,機(jī)器人位于正中心的柵格中,節(jié)點(diǎn){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ī)器人可移動(dòng)方向增加,移動(dòng)靈活性增強(qiáng),全局搜索能力增強(qiáng)。

圖1 多步長(zhǎng)蟻群算法range為3時(shí)的視野域

3.3 簡(jiǎn)化算子[4]

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

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

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

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

每次迭代的所有螞蟻?zhàn)咄耆毯?對(duì)所有到達(dá)終點(diǎn)的螞蟻路徑使用簡(jiǎn)化算子進(jìn)行簡(jiǎn)化,并用簡(jiǎn)化后的新路徑替代原有路徑。經(jīng)過簡(jiǎn)化算子處理的路徑拐點(diǎn)更少,路徑長(zhǎng)度更短。

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

3.4 差異化信息素更新

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

(6)

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

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

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

5 仿真對(duì)比分析

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

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

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

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

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

表1 四種算法對(duì)比

圖5 四種算法的收斂變化趨勢(shì)

6 結(jié) 論

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