改進蟻群算法及其在機器人避障中的應用

裴振兵，陳雪波

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

?

改進蟻群算法及其在機器人避障中的應用

裴振兵1，陳雪波2

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

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

改進蟻群算法；互鎖；機器人；避障；柵格法；建模；凹形障礙物；死鎖

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

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

1 蟻群算法基本原理及數學模型

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

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

Lk為第k只螞蟻在本次循環中所走過的路徑長度，Q為信息素強度。

2 改進蟻群算法

與傳統蟻群算法相比，文中提出的改進算法的特點是：1）改進算法用動態自適應調整α、β的值，代替傳統蟻群算法中固定值α、β，從而提高算法收斂速度，并逃離局部最優；2）為了避免蟻群在面對凹形障礙物時容易陷入其中并進入死鎖狀態，改進算法采用廣義信息素更新規則，代替傳統蟻群算法中的信息素更新規則。

2.1 問題描述

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

圖1 凹形障礙物

對于凹形障礙物，一種常見的處理方法是在環境建模時，將實際環境的凹形障礙物進行凸化處理，即將障礙物進行填補，這種方法雖然可以消除凹形障礙物，但以犧牲對環境的適應性來換取算法的運行速度，且在實際環境中缺乏可行性[10]。

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

2.2 改進算法描述

定義1α、β的動態自適應調整。是指通過建立α（信息素啟發式因子）與β（期望啟發式因子）的互鎖關系，即對不同的迭代次數NC，α、β會對應取不同的值，進而在整個過程中擴大蟻群搜索空間，使搜索路徑逃離局部最優。

根據蟻群算法搜索情況自適應動態調整信息啟發因子α和期望啟發式因子β，采用迭代次數NC的階梯函數α（NC），β（NC）代替常數項α、β，按式（6）和（7）進行調整：

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

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

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

式中：Δxji為t時刻螞蟻i在路徑ji上遺留信息素的增量，與路徑長度dji成反比；Q為常數；1-ρ為信息素強度揮發系數，ρ為絕對值小于1的實數；xji為t時刻路徑ji上遺留信息素的總量；dji為螞蟻i在路徑j上行走的距離；N為陷入凹形障礙物并未進入死鎖的螞蟻數。

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

2.3 改進算法實現步驟

1） 初始化

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

2） 根據轉移概率公式選擇下一個節點

螞蟻按照轉移概率公式（1）進行選擇，其中α、β的值按式（6）、（7）進行動態自適應調整，每次轉移之后對已走過的路徑進行記錄，并將已訪問節點加入禁忌表。

3） 記錄每一代每一只螞蟻的覓食路徑和路徑長度

將蟻群中迭代一次的螞蟻路徑及路徑長度進行記錄，并寫入細胞存儲結構CELL。

4） 更新信息素

對各條路徑的節點進行判斷，若已訪問的節點中包含凹形障礙物節點，則該節點對應的路徑信息素按式（8）～（10）進行更新；否則按式（3）～（5）進行信息素更新。

5） 判斷終止條件

當算法迭代次數大于設定最大迭代次數NCmax或算法給出的最優解滿足目標條件時，則退出程序，輸出最優解。

3 仿真實驗及其分析

3.1 TSP仿真算例驗證

為了驗證文中所提改進算法的可行性和有效性，針對傳統蟻群算法搜索時間長、易陷于局部最優缺點，以傳統蟻群算法為對比，基于TSP仿真算例進行實驗分析。實驗中重要參數設置如表1所示。

表1 參數設置說明Tab1 Parameters setup instructions

圖2 基于32個目標的平均距離與最短距離

圖3 基于56個目標的平均距離與最短距離

圖4 最優路徑

仿真實驗1將改進算法與傳統蟻群算法基于不同規模的TSP進行仿真對比，具體實驗結果如圖2～4所示。 圖2為遍歷32個目標所得仿真圖，圖3為遍歷56個目標所得仿真圖。圖2、3中實線代表改進蟻群算法，點劃線代表傳統蟻群算法 （圖2、3的上半部分是所提的改進蟻群算法與傳統蟻群算法平均距離仿真對比；下半部分是最短路徑距離仿真對比）。圖4為采用改進蟻群算法遍歷56個目標所搜索到的最優路徑（1為起始目標點，56為終止目標點）。

具體仿真數據分析如表2所示：

表2 仿真數據Tab 2 Simulation data

由表2可以看出，基于不同規模的TSP仿真算例，改進的蟻群算法所獲得的最短距離與平均距離明顯優于傳統蟻群算法，且整個運行時間也少于傳統蟻群算法。通過不同規模仿真實驗對比，驗證了所提出的改進算法的可行性和有效性。

3.2 改進算法在機器人避障礙中的應用

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

式中：（xi,yi）為路徑點坐標，n為路徑點數目，L為路徑長度[17]。按從左到右﹑從上到下的順序對柵格進行編號（1～100） ，同時設機器人工作空間由M行N列柵格組成，其中每個柵格是邊長為1的正方形小格，將障礙物地圖用一個二維數組矩陣map（M,N）表示為[18]:

實驗方法是將改進算法和傳統蟻群算法分別在上述所構造的環境中進行移動機器人路徑規劃（其中每一柵格都為1×1正方形，且大小相等，起始柵格和目標柵格是預先指定的）。文中所做的仿真實驗是在MATLAB數值分析工具下進行的。

仿真實驗2實驗環境為10×10柵格環境，設定出發點的柵格序號為1，目標點的柵格序號為100（柵格對應的序號是從左上角開始，從左到右，從上到下依次為1～100），具體實驗結果如圖5～9所示。

圖5 基于改進蟻群算法的機器人各代避障路線

圖6 收斂曲線（基于改進蟻群算法）

圖7 基于傳統群算法的機器人各代避障路線

圖8 傳統蟻群算法收斂曲線

圖9 機器人避障最優路線

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

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

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

3） 圖9的仿真結果進一步驗證了改進算法的可行性及在凹形障礙物中尋優的高效性。

4 結束語

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

[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].機械與電子, 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].計算機技術與發展, 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]柳長安, 鄢小虎, 劉春陽,等. 基于改進蟻群算法的移動機器人動態路徑規劃方法[J]. 電子學報, 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]段海濱. 蟻群算法原理及其應用[M]. 北京: 科學出版社, 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]周明秀, 程科, 王正霞.動態路徑規劃中的改進蟻群算法[J]. 計算機科學, 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]. 計算機工程與應用, 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]. 微型機與應用, 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]溫如春, 湯青波, 楊國亮. 基于改進蟻群算法的移動機器人路徑規劃[J]. 兵工自動化, 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]. 模式識別與人工智能, 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]賈振華, 斯慶巴拉, 王慧娟. 基于啟發式機器人路徑規劃仿真研究[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年生，碩士研究生，主要研究方向為智能優化及機器人路徑規劃。

陳雪波，男，1960年生，教授，博士生導師，中國自動化學會過程控制專業委員會委員。主要研究方向為復雜系統、群集智能等。主持多項國家及省部級科研基金項目，出版專著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 .

國家自然科學基金資助項目（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]. 智能系統學報， 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.