改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃中的應(yīng)用

李國(guó)濤 李丹 曹蒙

摘要：路徑規(guī)劃對(duì)移動(dòng)機(jī)器人具有極其重要的意義，傳統(tǒng)的蟻群算法存在收斂速度慢、容易陷入死鎖以及容易陷入局部最優(yōu)解等缺陷;本文采用柵格法進(jìn)行地圖空間建模，并且在蟻群算法中引入人工勢(shì)場(chǎng)的概念，以此優(yōu)化現(xiàn)有的蟻群算法;仿真結(jié)果顯示該算法明顯優(yōu)于傳統(tǒng)蟻群算法，可以讓機(jī)器人在復(fù)雜環(huán)境中選擇更好的前進(jìn)路線。

關(guān)鍵詞：蟻群算法;人工勢(shì)場(chǎng)法;移動(dòng)機(jī)器人;路徑規(guī)劃

0 引言

移動(dòng)機(jī)器人是集環(huán)境感知、路徑規(guī)劃、動(dòng)態(tài)決策和行為執(zhí)行于一體的的復(fù)雜控制系統(tǒng)。其中路徑規(guī)劃是機(jī)器人研究領(lǐng)域的技術(shù)重點(diǎn)，經(jīng)過(guò)幾十年的發(fā)展，路徑規(guī)劃算法分為三大類：傳統(tǒng)路徑規(guī)劃算法、啟發(fā)式算法及智能仿生路徑規(guī)劃算法。其中傳統(tǒng)路徑規(guī)劃算法包括可視圖法、人工勢(shì)場(chǎng)法、模擬退火法、模糊邏輯算法等;啟發(fā)式算法具有很強(qiáng)的路徑搜索能力，可以很好的在離散的路徑拓?fù)浣Y(jié)構(gòu)中運(yùn)用，常見(jiàn)的啟發(fā)式搜索算法有A*算法、Dijkatra算法及Floyd算法;智能仿生算法是人們通過(guò)仿生學(xué)的研究，在一系列的自然現(xiàn)象中發(fā)現(xiàn)的算法，主要包括：蟻群算法、粒子群算法、遺傳算法和神經(jīng)網(wǎng)絡(luò)算法。其中蟻群算法是人們受螞蟻覓食的啟發(fā)而產(chǎn)生的算法，螞蟻在覓食的過(guò)程中會(huì)分泌一種信息素，并在其尋找食物的途中在道路上留下一定濃度的信息素，信息素會(huì)隨時(shí)間揮發(fā)。在覓食的過(guò)程中，路程越短則螞蟻遍歷的次數(shù)越多，信息素濃度也就越高，螞蟻將信息素濃度作為選擇路徑的依據(jù)，信息素濃度越高，路徑被選擇的概率越大，隨著時(shí)間的推移，最短路徑上的信息素濃度會(huì)越來(lái)越高，最終所有螞蟻都會(huì)選擇最短路徑，從而達(dá)到路徑規(guī)劃的目的。蟻群算法本質(zhì)上是一種并行算法，易于計(jì)算機(jī)實(shí)現(xiàn)，蟻群算法最早是作為一種解決組合優(yōu)化問(wèn)題的元啟發(fā)式算法被提出，具有易與其他方法結(jié)合、魯棒性較強(qiáng)等優(yōu)點(diǎn)，但是傳統(tǒng)蟻群算法同時(shí)存在搜索時(shí)間長(zhǎng)、容易陷入局部最優(yōu)、面對(duì)凹形障礙物容易陷入死鎖等缺點(diǎn)。本文主要研究改進(jìn)后的蟻群算法在機(jī)器人路徑規(guī)劃中的應(yīng)用。

1 環(huán)境建模

設(shè)機(jī)器人運(yùn)動(dòng)環(huán)境為二維靜止空間，由于柵格法地圖表達(dá)規(guī)范、易于實(shí)現(xiàn)，所以對(duì)機(jī)器人運(yùn)動(dòng)空間進(jìn)行柵格法建模。將機(jī)器人視為質(zhì)點(diǎn)，占據(jù)一個(gè)柵格，同時(shí)如果靜態(tài)障礙物只占據(jù)某柵格的一部分，則將其視為完全占據(jù)此柵格。機(jī)器人的運(yùn)動(dòng)方向共有8個(gè)運(yùn)動(dòng)方向，同時(shí)機(jī)器人可在勻速和靜止兩個(gè)運(yùn)動(dòng)狀態(tài)中自由切換。運(yùn)用柵格法進(jìn)行環(huán)境建模的好處在于對(duì)于任何形式的障礙物都能很好的描述，而可視圖法或自由空間法對(duì)于圓形障礙物無(wú)法建模，此外，運(yùn)用一系列二值信息存儲(chǔ)障礙物特征及位置，方便計(jì)算機(jī)的存儲(chǔ)與更新，因此，選用柵格法進(jìn)行環(huán)境建模具有顯著的優(yōu)勢(shì)。

2 蟻群算法基本原理

2.1 傳統(tǒng)蟻群算法

受螞蟻覓食過(guò)程的啟發(fā)，1991年首次提出了蟻群算法[10]。在人工蟻群算法中，設(shè)m為螞蟻總數(shù)，螞蟻從某個(gè)節(jié)點(diǎn)轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)是由路徑上的信息素決定的，在t時(shí)刻，螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的狀態(tài)轉(zhuǎn)移概率? 為：

所有螞蟻完成一次覓食后，需要對(duì)信息素進(jìn)行更新，隨著時(shí)間的推移信息素會(huì)逐漸揮發(fā)，同時(shí)在螞蟻經(jīng)過(guò)的路段信息素量會(huì)增加，更新公式為：

2.2 改進(jìn)蟻群算法

基本蟻群算法雖然能夠規(guī)劃出從起始點(diǎn)到目標(biāo)點(diǎn)的路徑，并有較強(qiáng)的魯棒性，但依然存在很多不足，主要有容易過(guò)早停滯、搜索時(shí)間過(guò)長(zhǎng)、效率較低等缺點(diǎn)。本文針對(duì)傳統(tǒng)蟻群算法的先天不足，對(duì)基本蟻群算法做出以下幾點(diǎn)改進(jìn)，從而加快算法收斂速度，優(yōu)化算法路徑選擇，提高算法性能，使算法更加適合移動(dòng)機(jī)器人的實(shí)際使用。

（1）U形柵格優(yōu)化

在蟻群算法中，螞蟻很容易陷入U(xiǎn)形障礙物并發(fā)生死鎖，從而導(dǎo)致算法時(shí)間過(guò)長(zhǎng)甚至停滯，劉徐迅等人提出了螞蟻回退策略[11]，以此增加算法的魯棒性。但是當(dāng)U形障礙物過(guò)多時(shí)，螞蟻需要反復(fù)回退、反復(fù)判斷，因此增加了很多計(jì)算量，使搜索時(shí)間過(guò)長(zhǎng)。本文采用填補(bǔ)的方式對(duì)U形障礙物進(jìn)行填補(bǔ)，對(duì)于柵格中任意節(jié)點(diǎn)，如果與其相鄰的上下左右四個(gè)方向中的三個(gè)方向都存在障礙物或禁忌柵格，則將該節(jié)點(diǎn)標(biāo)記為禁忌柵格，不允許螞蟻通過(guò)。同時(shí)，如果填補(bǔ)過(guò)后出現(xiàn)新的滿足填補(bǔ)條件的柵格，則繼續(xù)填補(bǔ)，直至柵格地圖中所有滿足條件的柵格都被填補(bǔ)。

障礙物，因與10號(hào)柵格相鄰的三個(gè)方向的柵格同時(shí)存在障礙物，因此將10號(hào)柵格標(biāo)記為禁忌柵格，對(duì)于6號(hào)柵格，因與其相鄰的5號(hào)、7號(hào)柵格都存在障礙物，且10號(hào)柵格為禁忌柵格，因此將6號(hào)柵格也標(biāo)記為禁忌柵格。

（2）人工勢(shì)場(chǎng)法確定初始信息素

在基本蟻群算法中，初始信息素? ? ? ，即總是被設(shè)置為一個(gè)常數(shù)。地圖上相同的信息素濃度導(dǎo)致螞蟻在前期沒(méi)有足夠信息找到較優(yōu)的路徑，使算法在前期收斂速度過(guò)慢，因此設(shè)置合理的初始信息素對(duì)于提高算法初期的收斂速度具有重要作用，可以顯著的提高算法初期收斂速度。本文提出一種基于人工勢(shì)場(chǎng)法的設(shè)置初始信息素的方法，即在出發(fā)點(diǎn)設(shè)計(jì)斥力勢(shì)函數(shù)，降低出發(fā)點(diǎn)的初始信息素濃度，在目的地設(shè)置引力勢(shì)函數(shù)，提高目的地的初始信息素濃度。

式中ω為固定系數(shù)，di和dj分別為柵格節(jié)點(diǎn)到出發(fā)點(diǎn)和目標(biāo)點(diǎn)的距離，為一閾值，保證所有柵格的初始信息素都不低于這個(gè)閾值，在一定程度上這也保證了算法避免過(guò)早陷入局部最優(yōu)。

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

在蟻群算法中通過(guò)對(duì)U型柵格進(jìn)行優(yōu)化以及引入人工勢(shì)場(chǎng)法確定初始信息素來(lái)提高蟻群算法的性能，把改進(jìn)后的蟻群算法應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃中，具體步驟如下。

（1）對(duì)環(huán)境采用柵格法建模，并且初始化機(jī)器人起始位置、方向等相關(guān)參數(shù)以及目標(biāo)點(diǎn)的位置及相關(guān)參數(shù)。

（2）對(duì)柵格法地圖中的U形障礙物進(jìn)行填充，并且根據(jù)人工勢(shì)場(chǎng)法設(shè)置出發(fā)點(diǎn)和目的地的信息素濃度。

（3）當(dāng)一只螞蟻到達(dá)終點(diǎn)時(shí)根據(jù)蟻群算法信息素濃度更新公式對(duì)其經(jīng)過(guò)路段上的信息素濃度進(jìn)行更新。