改進(jìn)蟻群算法及其在機(jī)器人避障中的應(yīng)用

裴振兵，陳雪波

（1.遼寧科技大學(xué) 電子與信息工程學(xué)院，遼寧 鞍山 114051；2. 遼寧科技大學(xué) 研究生院，遼寧 鞍山 114051）

?

改進(jìn)蟻群算法及其在機(jī)器人避障中的應(yīng)用

裴振兵1，陳雪波2

（1.遼寧科技大學(xué) 電子與信息工程學(xué)院，遼寧 鞍山 114051；2. 遼寧科技大學(xué) 研究生院，遼寧 鞍山 114051）

提出了一種改進(jìn)蟻群算法. 首先針對(duì)蟻群算法在構(gòu)造解過程中收斂速度慢且容易陷入局部最優(yōu), 提出了在蟻群搜索路徑過程中, 通過建立α（信息素啟發(fā)式因子）和β（期望啟發(fā)式因子）的互鎖關(guān)系,動(dòng)態(tài)自適應(yīng)調(diào)整α、β; 其次針對(duì)蟻群算法在面對(duì)凹形障礙物易陷入死鎖, 降低搜索效率, 提出了廣義信息素更新規(guī)則; 最后利用柵格法進(jìn)行靜態(tài)已知環(huán)境建模, 通過不同規(guī)模TSP的仿真驗(yàn)證了該方法的可行性和有效性, 同時(shí)將其應(yīng)用到機(jī)器人避障并取得了較好實(shí)驗(yàn)效果。

改進(jìn)蟻群算法；互鎖；機(jī)器人；避障；柵格法；建模；凹形障礙物；死鎖

路徑規(guī)劃是移動(dòng)機(jī)器人領(lǐng)域中一個(gè)重要的研究方向，而在面對(duì)各種障礙的環(huán)境中，如何成功地避開障礙物尋找一條最優(yōu)路徑，又是機(jī)器人路徑規(guī)劃中的重要研究課題。根據(jù)螞蟻“尋找食物”的群體行為，意大利學(xué)者Dorigo M等于1991年在法國(guó)巴黎召開的第一屆歐洲人工生命會(huì)議（European Conference on Artificial Lif, ECAL）上最早提出了一種新型的仿生算法——蟻群算法[1], 蟻群搜索食物的過程與機(jī)器人路徑規(guī)劃有著驚人的相似，都是尋找一條從起始點(diǎn)到終點(diǎn)避障的最優(yōu)路徑。蟻群算法固然具有分布式并行計(jì)算機(jī)制、易于與其他方法結(jié)合、具有較強(qiáng)的魯棒性等優(yōu)點(diǎn)，但搜索時(shí)間長(zhǎng)、易陷于局部最優(yōu)、面對(duì)凹形障礙物容易陷入死鎖是其最為突出的缺點(diǎn)[2]。

文中首先簡(jiǎn)單介紹蟻群算法數(shù)學(xué)模型，然后引入改進(jìn)蟻群算法，針對(duì)一般蟻群算法在構(gòu)造解的過程中，蟻群收斂速度慢且容易陷入局部最優(yōu)，通過建立α（信息素啟發(fā)式因子）β（期望啟發(fā)式因子）的互鎖關(guān)系，動(dòng)態(tài)自適應(yīng)調(diào)整α、β；其次針對(duì)蟻群算法在面對(duì)凹形障礙物易陷入死鎖，降低搜索效率，提出了廣義信息素更新規(guī)則。接著將改進(jìn)算法與傳統(tǒng)蟻群算法進(jìn)行仿真對(duì)比（以TSP作為仿真算例），通過仿真結(jié)果證明了改進(jìn)算法在提高收斂速度，避免蟻群算法陷入局部最優(yōu)方面的可行性和優(yōu)越性。并將改進(jìn)蟻群算法運(yùn)用到機(jī)器人避障，通過仿真實(shí)驗(yàn)，取得了較好實(shí)驗(yàn)效果，進(jìn)一步驗(yàn)證了該改進(jìn)算法的有效性和實(shí)用性（利用柵格法進(jìn)行環(huán)境建模）。最后，進(jìn)行了進(jìn)一步總結(jié)與分析。

1 蟻群算法基本原理及數(shù)學(xué)模型

蟻群算法是科學(xué)家受自然界中真實(shí)蟻群覓食行為的啟發(fā)，經(jīng)過長(zhǎng)期研究發(fā)現(xiàn)：?jiǎn)蝹€(gè)螞蟻雖沒有視覺，也無法掌握附近地理信息，但運(yùn)動(dòng)時(shí)會(huì)通過在路徑上釋放出一種特殊的分泌物——信息素來尋找路徑[3]。當(dāng)運(yùn)動(dòng)路徑上突然出現(xiàn)障礙物時(shí)，螞蟻會(huì)通過信息素相互傳遞信息而最終找到一條躲避障礙物的最優(yōu)路徑[4]。蟻群算法具有分布式并行計(jì)算機(jī)制，易于與其他方法結(jié)合且實(shí)現(xiàn)簡(jiǎn)單的優(yōu)點(diǎn)。這也正是其最早成功應(yīng)用解決著名TSP問題的原因[5]。

式（1）中,τij（t）表示t時(shí)刻在路徑（i,j）上的信息素量;allowedk={C—tabuk}表示螞蟻k下一步允許選擇的節(jié)點(diǎn);α為信息啟發(fā)因子（α反映信息素積累量在指導(dǎo)蟻群搜索中的相對(duì)重要性），β為期望啟發(fā)式因子（β反映了下一個(gè)目標(biāo)點(diǎn)的距離在指導(dǎo)蟻群搜索過程中的相對(duì)重要性）且β值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則;ηij（t）為啟發(fā)函數(shù)，其表達(dá)式如式（2）[7]：

Lk為第k只螞蟻在本次循環(huán)中所走過的路徑長(zhǎng)度，Q為信息素強(qiáng)度。

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

與傳統(tǒng)蟻群算法相比，文中提出的改進(jìn)算法的特點(diǎn)是：1）改進(jìn)算法用動(dòng)態(tài)自適應(yīng)調(diào)整α、β的值，代替?zhèn)鹘y(tǒng)蟻群算法中固定值α、β，從而提高算法收斂速度，并逃離局部最優(yōu)；2）為了避免蟻群在面對(duì)凹形障礙物時(shí)容易陷入其中并進(jìn)入死鎖狀態(tài)，改進(jìn)算法采用廣義信息素更新規(guī)則，代替?zhèn)鹘y(tǒng)蟻群算法中的信息素更新規(guī)則。

2.1 問題描述

蟻群算法在實(shí)現(xiàn)過程中，利用禁忌表對(duì)已訪問的節(jié)點(diǎn)進(jìn)行存儲(chǔ)，即下一步選擇的節(jié)點(diǎn)只能為未訪問節(jié)點(diǎn)。這樣就會(huì)導(dǎo)致有些螞蟻在面對(duì)凹形障礙物時(shí)，極易陷入其中并出現(xiàn)后續(xù)無節(jié)點(diǎn)可選的情況，進(jìn)而進(jìn)入“死鎖”狀態(tài)。凹形障礙物如圖1所示。路徑1→4→3,1→4→2,2→4→3,2→4→1,3→4→1,3→4→2是陷入凹形障礙物而未進(jìn)入“死鎖”的路徑；而路徑1→4→5,2→4→5,3→4→5是陷入凹形障礙物并進(jìn)入“死鎖”的路徑。顯然，若螞蟻陷入凹形障礙物并進(jìn)入“死鎖”路徑，將會(huì)使最終的有效螞蟻的數(shù)量小于初始螞蟻數(shù)量，這不但會(huì)影響最優(yōu)解的探尋，降低算法收斂速度，還會(huì)減緩局部最優(yōu)的逃離；若螞蟻陷入凹形障礙物并未進(jìn)入“死鎖”路徑，螞蟻雖然并未停止搜索，但路徑1→4→3，1→4→2的距離顯然長(zhǎng)于路徑1→2→3，1→2，也即該路徑上的螞蟻?zhàn)隽藷o用功，從而導(dǎo)致整個(gè)蟻群能量損耗，在一定程度上降低了蟻群搜索速度，延長(zhǎng)了搜索時(shí)間。

圖1 凹形障礙物

對(duì)于凹形障礙物，一種常見的處理方法是在環(huán)境建模時(shí)，將實(shí)際環(huán)境的凹形障礙物進(jìn)行凸化處理，即將障礙物進(jìn)行填補(bǔ)，這種方法雖然可以消除凹形障礙物，但以犧牲對(duì)環(huán)境的適應(yīng)性來換取算法的運(yùn)行速度，且在實(shí)際環(huán)境中缺乏可行性[10]。

鑒于以上問題，通過引入文中改進(jìn)蟻群算法提高蟻群收斂速度，擴(kuò)大蟻群搜索空間，有效避開凹形障礙物是非常有必要和有意義的。

2.2 改進(jìn)算法描述

定義1α、β的動(dòng)態(tài)自適應(yīng)調(diào)整。是指通過建立α（信息素啟發(fā)式因子）與β（期望啟發(fā)式因子）的互鎖關(guān)系，即對(duì)不同的迭代次數(shù)NC，α、β會(huì)對(duì)應(yīng)取不同的值，進(jìn)而在整個(gè)過程中擴(kuò)大蟻群搜索空間，使搜索路徑逃離局部最優(yōu)。

根據(jù)蟻群算法搜索情況自適應(yīng)動(dòng)態(tài)調(diào)整信息啟發(fā)因子α和期望啟發(fā)式因子β，采用迭代次數(shù)NC的階梯函數(shù)α（NC），β（NC）代替常數(shù)項(xiàng)α、β，按式（6）和（7）進(jìn)行調(diào)整：

在搜索過程中為了達(dá)到平衡,式（6）、（7）中信息啟發(fā)因子α和期望啟發(fā)式因子β是互鎖的關(guān)系,即αi+βi=M（其中M為一定值）。由于α、β值過大或過小都易使蟻群的搜索過早陷入局部最優(yōu)[11]。結(jié)合其他改進(jìn)算法中α、β的取值經(jīng)驗(yàn)與分析,同時(shí)通過仿真實(shí)驗(yàn)分析,確定當(dāng)1≤α≤9,1≤β≤9更有利于整個(gè)改進(jìn)算法動(dòng)態(tài)調(diào)整。開始時(shí)信息素濃度差別不大，以各個(gè)節(jié)點(diǎn)之間的距離為主要調(diào)整因素,這樣有利于提高路徑搜索速度,即信息啟發(fā)因子α（1≤α1<5）先取值較小,相對(duì)應(yīng)的期望啟發(fā)式因子β（5<β1≤9）取值較大[12];隨著迭代次數(shù)增加,各條路徑的信息素也得到了積累,此時(shí)選擇信息素濃度為主要調(diào)整因素進(jìn)行全局搜索,即信息啟發(fā)因子α（5<α2≤9）先取較大值,相對(duì)應(yīng)的期望啟發(fā)式因子β（1≤β2<5）取值較小；隨著迭代次數(shù)的繼續(xù)增加,為了防止由于信息素積累的正反饋機(jī)制作用而陷入局部最優(yōu),進(jìn)而改為各個(gè)節(jié)點(diǎn)距離為主要調(diào)整因素,即信息啟發(fā)因子α（1<α3≤5）先取值較小,相對(duì)應(yīng)的期望啟發(fā)式因子β（5≤β3<9）取值較大。

定義2廣義信息素更新規(guī)則。是指每只螞蟻在路徑的搜索過程中，碰到凹形障礙物采用新的信息素更新規(guī)則。當(dāng)遇到凹形障礙物并陷入“死鎖”則對(duì)該路徑上的信息素更新采用“清零”方式；當(dāng)遇到凹形障礙物并未陷入“死鎖”時(shí)，為了保證整個(gè)蟻群的搜索空間，對(duì)該路徑上的信息素更新采用“漸滅”方式。

設(shè)第i（i=1,2,…,k）只螞蟻在t時(shí)刻所對(duì)應(yīng)的ji（i=1,2,…,k）這條路徑為陷入凹形障礙物的路徑，則該路徑上的信息素按式（8）～（10）進(jìn)行更新[13]：

式中：Δxji為t時(shí)刻螞蟻i在路徑j(luò)i上遺留信息素的增量，與路徑長(zhǎng)度dji成反比；Q為常數(shù)；1-ρ為信息素強(qiáng)度揮發(fā)系數(shù)，ρ為絕對(duì)值小于1的實(shí)數(shù)；xji為t時(shí)刻路徑j(luò)i上遺留信息素的總量；dji為螞蟻i在路徑j(luò)上行走的距離；N為陷入凹形障礙物并未進(jìn)入死鎖的螞蟻數(shù)。

算法收斂性分析設(shè)k只螞蟻中，第i只螞蟻陷入凹形障礙物并進(jìn)入死鎖，由式（8）～（10）可見，由于X=1，此時(shí)路徑j(luò)i上遺留信息素xji將會(huì)被“清零”；同理對(duì)于陷入凹形障礙物未進(jìn)入死鎖的螞蟻，由式（8）～（10）可見，隨著N的不斷增加且1-ρ∈[0,1），xji將以指數(shù)的方式遞減，也即路徑j(luò)i上遺留信息素xji將會(huì)被“漸滅”最終趨于零。

2.3 改進(jìn)算法實(shí)現(xiàn)步驟

1） 初始化

初始化改進(jìn)蟻群算法的最大迭代次數(shù)NCmax，蟻群的螞蟻數(shù)m，以及ρ，Q等參數(shù)進(jìn)行初始化[14]。

2） 根據(jù)轉(zhuǎn)移概率公式選擇下一個(gè)節(jié)點(diǎn)

螞蟻按照轉(zhuǎn)移概率公式（1）進(jìn)行選擇，其中α、β的值按式（6）、（7）進(jìn)行動(dòng)態(tài)自適應(yīng)調(diào)整，每次轉(zhuǎn)移之后對(duì)已走過的路徑進(jìn)行記錄，并將已訪問節(jié)點(diǎn)加入禁忌表。

3） 記錄每一代每一只螞蟻的覓食路徑和路徑長(zhǎng)度

將蟻群中迭代一次的螞蟻路徑及路徑長(zhǎng)度進(jìn)行記錄，并寫入細(xì)胞存儲(chǔ)結(jié)構(gòu)CELL。

4） 更新信息素

對(duì)各條路徑的節(jié)點(diǎn)進(jìn)行判斷，若已訪問的節(jié)點(diǎn)中包含凹形障礙物節(jié)點(diǎn)，則該節(jié)點(diǎn)對(duì)應(yīng)的路徑信息素按式（8）～（10）進(jìn)行更新；否則按式（3）～（5）進(jìn)行信息素更新。

5） 判斷終止條件

當(dāng)算法迭代次數(shù)大于設(shè)定最大迭代次數(shù)NCmax或算法給出的最優(yōu)解滿足目標(biāo)條件時(shí)，則退出程序，輸出最優(yōu)解。

3 仿真實(shí)驗(yàn)及其分析

3.1 TSP仿真算例驗(yàn)證

為了驗(yàn)證文中所提改進(jìn)算法的可行性和有效性，針對(duì)傳統(tǒng)蟻群算法搜索時(shí)間長(zhǎng)、易陷于局部最優(yōu)缺點(diǎn)，以傳統(tǒng)蟻群算法為對(duì)比，基于TSP仿真算例進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)中重要參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置說明Tab1 Parameters setup instructions

圖2 基于32個(gè)目標(biāo)的平均距離與最短距離

圖3 基于56個(gè)目標(biāo)的平均距離與最短距離

圖4 最優(yōu)路徑

仿真實(shí)驗(yàn)1將改進(jìn)算法與傳統(tǒng)蟻群算法基于不同規(guī)模的TSP進(jìn)行仿真對(duì)比，具體實(shí)驗(yàn)結(jié)果如圖2～4所示。 圖2為遍歷32個(gè)目標(biāo)所得仿真圖，圖3為遍歷56個(gè)目標(biāo)所得仿真圖。圖2、3中實(shí)線代表改進(jìn)蟻群算法，點(diǎn)劃線代表傳統(tǒng)蟻群算法 （圖2、3的上半部分是所提的改進(jìn)蟻群算法與傳統(tǒng)蟻群算法平均距離仿真對(duì)比；下半部分是最短路徑距離仿真對(duì)比）。圖4為采用改進(jìn)蟻群算法遍歷56個(gè)目標(biāo)所搜索到的最優(yōu)路徑（1為起始目標(biāo)點(diǎn)，56為終止目標(biāo)點(diǎn)）。

具體仿真數(shù)據(jù)分析如表2所示：

表2 仿真數(shù)據(jù)Tab 2 Simulation data

由表2可以看出，基于不同規(guī)模的TSP仿真算例，改進(jìn)的蟻群算法所獲得的最短距離與平均距離明顯優(yōu)于傳統(tǒng)蟻群算法，且整個(gè)運(yùn)行時(shí)間也少于傳統(tǒng)蟻群算法。通過不同規(guī)模仿真實(shí)驗(yàn)對(duì)比，驗(yàn)證了所提出的改進(jìn)算法的可行性和有效性。

3.2 改進(jìn)算法在機(jī)器人避障礙中的應(yīng)用

為了進(jìn)一步驗(yàn)證改進(jìn)蟻群算法的可行性，將所提改進(jìn)蟻群算法運(yùn)用到機(jī)器人避障。為了便于蟻群算法搜索到最優(yōu)路徑，采用柵格法進(jìn)行靜態(tài)已知環(huán)境建模，同時(shí)選取了數(shù)量更多、分布更為復(fù)雜的障礙物[15]。設(shè)機(jī)器人的工作空間為二維平面上的有限區(qū)域AS，起始點(diǎn)B和目標(biāo)點(diǎn)E。文中路徑規(guī)劃的優(yōu)化準(zhǔn)則為路徑最短，即尋找一條從B到E避開障礙物的最短路徑[16]。工作空間AS由200個(gè)1×1大小的方格組成，AS的規(guī)模為10行×10列。最短路徑問題的目標(biāo)函數(shù)可表示為式（11）：

式中：（xi,yi）為路徑點(diǎn)坐標(biāo)，n為路徑點(diǎn)數(shù)目，L為路徑長(zhǎng)度[17]。按從左到右﹑從上到下的順序?qū)鸥襁M(jìn)行編號(hào)（1～100） ，同時(shí)設(shè)機(jī)器人工作空間由M行N列柵格組成，其中每個(gè)柵格是邊長(zhǎng)為1的正方形小格，將障礙物地圖用一個(gè)二維數(shù)組矩陣map（M,N）表示為[18]:

實(shí)驗(yàn)方法是將改進(jìn)算法和傳統(tǒng)蟻群算法分別在上述所構(gòu)造的環(huán)境中進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃（其中每一柵格都為1×1正方形，且大小相等，起始柵格和目標(biāo)柵格是預(yù)先指定的）。文中所做的仿真實(shí)驗(yàn)是在MATLAB數(shù)值分析工具下進(jìn)行的。

仿真實(shí)驗(yàn)2實(shí)驗(yàn)環(huán)境為10×10柵格環(huán)境，設(shè)定出發(fā)點(diǎn)的柵格序號(hào)為1，目標(biāo)點(diǎn)的柵格序號(hào)為100（柵格對(duì)應(yīng)的序號(hào)是從左上角開始，從左到右，從上到下依次為1～100），具體實(shí)驗(yàn)結(jié)果如圖5～9所示。

圖5 基于改進(jìn)蟻群算法的機(jī)器人各代避障路線

圖6 收斂曲線（基于改進(jìn)蟻群算法）

圖7 基于傳統(tǒng)群算法的機(jī)器人各代避障路線

圖8 傳統(tǒng)蟻群算法收斂曲線

圖9 機(jī)器人避障最優(yōu)路線

圖5、6為改進(jìn)蟻群算法經(jīng)過150次迭代后所得到的機(jī)器人各代避障路線及對(duì)應(yīng)的最終收斂曲線；圖7、8為傳統(tǒng)蟻群算法經(jīng)過150次迭代后所得到的機(jī)器人各代避障路線及對(duì)應(yīng)的最終收斂曲線；圖9為基于改進(jìn)蟻群算法得到的機(jī)器人避障礙最優(yōu)路線；通過上述仿真結(jié)果可以得出如下結(jié)論：

1） 由圖5、7對(duì)比分析，可以得出基于改進(jìn)蟻群算法的各代機(jī)器人在面對(duì)凹形障礙物時(shí)有更多的選擇避開凹形障礙物的安全路徑，保障了整個(gè)群體的性能；而基于傳統(tǒng)蟻群算法的各代機(jī)器人，在面對(duì)凹形障礙物時(shí)更易陷入其中并進(jìn)入“死鎖”，減少了群體中有效個(gè)體的數(shù)量，從而影響整個(gè)群體性能。

2） 由圖6、8對(duì)比分析可知，基于改進(jìn)蟻群算法的機(jī)器人在凹形障礙物的環(huán)境中經(jīng)過40多次迭代就收斂到最優(yōu)路徑；而基于傳統(tǒng)蟻群算法的機(jī)器人則要經(jīng)過80多次迭代才能收斂到最優(yōu)路徑，顯然改進(jìn)蟻群算法的收斂速度明顯優(yōu)于傳統(tǒng)蟻群算法。

3） 圖9的仿真結(jié)果進(jìn)一步驗(yàn)證了改進(jìn)算法的可行性及在凹形障礙物中尋優(yōu)的高效性。

4 結(jié)束語

在原有蟻群算法的基礎(chǔ)上，首先針對(duì)蟻群算法在構(gòu)造解的過程中收斂速度慢且容易陷入局部最優(yōu)，提出了動(dòng)態(tài)自適應(yīng)調(diào)整α、β策略；其次針對(duì)蟻群算法在面對(duì)凹形障礙物易陷入死鎖，提出了廣義信息素更新規(guī)則。通過仿真實(shí)驗(yàn)將改進(jìn)蟻群算法與一般蟻群算法進(jìn)行對(duì)比分析，仿真結(jié)果顯示，該改進(jìn)算法在一定程度上提高了搜索速度，有效地彌補(bǔ)了傳統(tǒng)蟻群算法容易陷入局部最優(yōu)的劣勢(shì)[19]。最后將改進(jìn)蟻群算法應(yīng)用到機(jī)器人避障，并取得了較好實(shí)驗(yàn)效果，仿真結(jié)果進(jìn)一步驗(yàn)證了改進(jìn)算法的可行性及在凹形障礙物中成功擺脫陷阱尋找最優(yōu)路徑的高效性。不足之處：該仿真的障礙物環(huán)境為靜態(tài)已知環(huán)境，如果為動(dòng)態(tài)未知環(huán)境，則機(jī)器人不一定能成功擺脫凹形障礙物[20]。這也是以后需要進(jìn)一步改進(jìn)和研究的地方。如果將該改進(jìn)算法應(yīng)用到其他領(lǐng)域，如無人駕駛車輛中進(jìn)行起點(diǎn)和終點(diǎn)已知情況下的最短路徑無碰撞行駛，也是具有指導(dǎo)意義的。

[1]COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]// Processings of the 1st European Conference on Artificial Life.Paris, France, 1991: 134-142.

[2] 徐利超, 張世武. 基于改進(jìn)蟻群算法的障礙環(huán)境下路徑規(guī)劃研究[J].機(jī)械與電子, 2013 （7）: 61-64. XU Lichao, ZHANG Shiwu. Study of path planning in obstacle environment based on an improved ant algorithm[J]. Machinery & Electronics, 2013,（7）: 61-64.

[3]朱紹偉,徐夫田,騰兆明.一種改進(jìn)蟻群算法求解最短路徑的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2011（7）: 202-205. ZHU Shaowei, XU Futian, TENG Zhaoming. Application of improvement ants algorithm in solving shortest path[J]. Computer Technology and Development,2011, 21（7）: 202-205.

[4]柳長(zhǎng)安, 鄢小虎, 劉春陽,等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J]. 電子學(xué)報(bào), 2011, 39（5）:1220-1224. LIU Changan, YAN Xiaohu, LIU Chunyang, et al. Dynamic path planning for mobile robot based on improoved ant colony optimization algorithm[J]. Acta Electronica Sinica, 2011, 39（5）: 1220-1224.

[5]段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2005: 176-181.

[6]GUTJAHR W J. A graph-based ant system and its convergence [J]. Future Generation Computer Systems, 2000, 16（8）: 873-888.

[7]周明秀, 程科, 王正霞.動(dòng)態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J]. 計(jì)算機(jī)科學(xué), 2012, 40（1）: 314-316. ZHOU Mingxiu, CHENG Ke, WANG Zhengxia. Improved ant colony algorithm with planning of dynamic path[J]. Computer Science, 2012, 40（1）: 314-316.

[8]王越, 葉秋冬. 蟻群算法在求解最短路徑問題上的改進(jìn)策略[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48（13）: 35-38. WANG Yue, YE Qiudong. Improved strategies of ant colony algorithm for solving shortest path problem[J].Computer Engineering and Applications, 2012, 48（13）:35-38.

[9]趙凱, 李聲晉, 孫娟, 等.改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究[J]. 微型機(jī)與應(yīng)用, 2013, 32（4）: 67-70. ZHAO Kai, LI Shengjin, SUN Juan, et al. Research of improved ant colony algorithm in mobile robot path planning[J]. Microcomputer & its Applications, 2013, 32（4）: 67-70.

[10]溫如春, 湯青波, 楊國(guó)亮. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 兵工自動(dòng)化, 2010, 29（8）: 69-70. WEN Ruchun, TANG Qingbo, YANG Guoliang. Mobile robot’s path planning based on improved ant colony algorithm[J]. Ordance Industry Automation, 2010, 29（8）: 69-70.

[11]張穎, 陳雪波. 廣義蟻群算法及其在機(jī)器人隊(duì)形變換中的應(yīng)用[J]. 模式識(shí)別與人工智能, 2007, 19, 20（3）: 3-8. ZHANG Ying, CHEN Xuebo. General ant colony algorithm and its applications in robot formation[J]. Pattern Recognition and Aitificial Intelligence, 2007, 19, 20（3）: 3-8.

[12]JACKSON D E, HOLCOMBE M, RATNIEKS F L W. Trail geometry gives polarity to ant foraging networks [J].Nature, 2004, 432（7019）:907-909.

[13]賈振華, 斯慶巴拉, 王慧娟. 基于啟發(fā)式機(jī)器人路徑規(guī)劃仿真研究[J]. 計(jì)算機(jī)仿真, 2012, 29（1）: 135-138. JIA Zhenhua, SIQING Bala, WANG Huijuan. Path planning based on heuristic algorithm[J]. Computer Simulation, 2012, 29（1）: 135-138.

[14]AI-TAHARWA I, SHETA A, AI-WESHAN M. A mobile robot path planning using genetic algorithm in static environment [J]. Journal of Computer Sciences, 2008, 4（4）: 341-344.

[15]YAO L M, DUAN H B, SHAO S. Adaptive template matching based on improved ant colony optimization[C]//Proceedings of International Workshop on Intelligence Systems and Applications. [s.l.], 2009:1-4.

[16]BROOKS R A. Solving the find-path problem by good representation of free space [J]. IEEE Trans on System Man and Cybernetics, 1983, 13（3）: 190-197.

[17]JANET J A. The essential visibility graph: an approach to global motion planning for autonomous mobile robots[C]// IEEE International Conference on Robotics and Automation. [s.l.], 1995: 1958-1963.

[18]EMILIO F. Real-time motion planning for agile autonomous vehicles [J]. Journal of Guidance, Control and Dynamics, 2002, 25（1）:116-129.

[19]BONABEAU E, DORIGO M, Theraulaz G. Inspiration for optimization from social insect behavior [J]. Nature, 2000, 406（6）: 39-42.

[20]DORIGO M, DI CARO G, GAMBARDELLA L M. Ant algorithms for discrete optimization [J]. Artificial Life, 1999, 5（2）: 137-172.

裴振兵，男，1989年生，碩士研究生，主要研究方向?yàn)橹悄軆?yōu)化及機(jī)器人路徑規(guī)劃。

陳雪波，男，1960年生，教授，博士生導(dǎo)師，中國(guó)自動(dòng)化學(xué)會(huì)過程控制專業(yè)委員會(huì)委員。主要研究方向?yàn)閺?fù)雜系統(tǒng)、群集智能等。主持多項(xiàng)國(guó)家及省部級(jí)科研基金項(xiàng)目，出版專著1部。

Improved ant colony algorithm and its application in obstacle avoidance for robot

PEI Zhenbing1，CHEN Xuebo2

（1. School of Electronics and Information Engineering, Liaoning University of Science and Technology, Anshan 114051, China; 2. Graduate school, Liaoning University of Science and Technology, Anshan 114051, China）

An improved ant colony algorithm is proposed in this paper. Firstly, in order to overcome the demerits of the ant colony algorithm, such as low convergence speed and easy to get into the local optimum, α and β are dynamically adaptively adjusted by establishing an interlock between alpha （pheromone heuristic factor） and beta （expected heuristic factor） in the searching route process of ant colony. Secondly, in order to prevent the ant colony algorithm from falling into deadlock when facing concave obstacles, which decreases search efficiency, an update rule of the generalized pheromone is proposed. Finally, static modeling for a known environment is conducted by the grid method. The simulation experiments showed that with different scales of TSP, the improved ant colony algorithm is feasible and efficient. In addition, this algorithm is applied to the obstacle avoidance of robots and the results are effective.

improved ant colony optimization; interlock; robots; obstacle avoidance; grid method; modeling; concave obstacle; deadlock

2013-11-07.

日期：2015-01-13 .

國(guó)家自然科學(xué)基金資助項(xiàng)目（60874017）.

陳雪波. E-mail：xuebochen@126.com.

10.3969/j.issn.1673-4785.201311018

http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.005.html

TP242

A

1673-4785（2015）01-0090-07

裴振兵，陳雪波.改進(jìn)蟻群算法及其在機(jī)器人避障中的應(yīng)用[J]. 智能系統(tǒng)學(xué)報(bào)， 2015, 10（1）: 90-96.

英文引用格式：PEI Zhenbing，CHEN Xuebo. Improved ant colony algorithm and its application in obstacle avoidance for robot[J]. CAAI Transactions on Intelligent Systems, 2015, 10（1）: 90-96.