基于改進蟻群算法的移動機器人全局路徑規(guī)劃

占偉 屈軍鎖 蘆鑫 侯磊超

關(guān)鍵詞： 仿生優(yōu)化; 蟻群算法; 柵格法; 移動機器人; 路徑規(guī)劃; 啟發(fā)因子; 信息素更新策略

中圖分類號： TN929.5?34; TP242 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）24?0170?04

Global path planning based on improved ant colony algorithm for mobile robot

ZHAN Wei， QU Junsuo， LU Xin， HOU Leichao

（School of Communications and Information Engineering， Xian University of Posts & Telecommunications， Xian 710121， China）

Abstract： The ant colony algorithm is an intelligent bionic optimization algorithm， whose self?organization and intelligence is of guiding significance to the study of global path planning. Based on this， an improved ant colony algorithm is proposed. The environment model is established by using the grid method. The traditional ant colony algorithm is improved by studying and improving the inspiring factor and pheromone updating strategy of the algorithm. The simulation results show that the improved ant colony algorithm has the characteristics of rapid convergence speed and good optimization performance in comparison with the traditional ant colony algorithm.

Keywords： bionic optimization; ant colony algorithm; grid method; mobile robot; path planning; inspiring factor; pheromone updating strategy

0 ?引 ?言

隨著人工智能領(lǐng)域的高速發(fā)展，機器人路徑規(guī)劃問題已成為時代熱點之一。全局路徑規(guī)劃問題的研究是研究機器人動態(tài)路徑規(guī)劃方法的重要基礎(chǔ)。近年來，國內(nèi)外學(xué)者相繼提出遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、人工勢場法和蟻群算法等算法[1?2]用于該問題。遺傳算法應(yīng)用性廣但存在進化速度下降快，迭代次數(shù)冗余等問題[3];人工勢場法具有高效性的特點但也存在易陷入陷阱區(qū)等問題[4];神經(jīng)網(wǎng)絡(luò)算法計算量大且結(jié)構(gòu)復(fù)雜[5]。

蟻群算法作為一個智能模式，其具有較強的適應(yīng)性和協(xié)作性，適應(yīng)性主要表現(xiàn)在通過信息素的積累不斷優(yōu)化結(jié)構(gòu)達到最優(yōu)目標，沒有外界作用力的情況下系統(tǒng)熵動態(tài)增加[6]保證系統(tǒng)朝著最優(yōu)解的方向進行。而機器人路徑規(guī)劃問題是典型的組合優(yōu)化問題，該問題可模擬成螞蟻尋找最優(yōu)路徑覓食的群體行為[7]，傳統(tǒng)的蟻群算法雖然具有發(fā)現(xiàn)最優(yōu)解的能力，但存在一定的缺陷：收斂速度慢，易陷入局部最優(yōu)解[7]?，F(xiàn)擬提出一種改進的蟻群算法，通過改進的蟻群算法搜索到最優(yōu)路徑，根據(jù)信息素的數(shù)量大小參照概率自主選擇路徑，通過調(diào)整啟發(fā)因子函數(shù)提高算法收斂速度。

1 ?基于蟻群算法的移動機器人全局路徑規(guī)劃

1.1 ?問題描述與模型建立

當(dāng)移動機器人協(xié)作完成某任務(wù)時，對于移動機器人而言，首先要做的是獲取周邊環(huán)境信息，建立環(huán)境模型，按照自身算法進行定位和避障，最后獲得一條最優(yōu)路徑，因此路徑規(guī)劃是完成這一系列工作的首要前提。例如多機器人機場搬運貨物問題，貨物地點隨機分布，機器人如何進行最優(yōu)路徑的選擇而高效地進行貨物的搬運。本文研究的全局路徑規(guī)劃問題的條件是：

1） 已知全局環(huán)境條件，即障礙物的所有位置已知;

2） 機器人與障礙物之間無碰撞，機器人相互之間的碰撞不考慮;

3） 機器人起始位置和目標位置已知。多移動機器人路徑規(guī)劃需達到的效果是：最優(yōu)結(jié)果，即各移動機器人需找到從出發(fā)位置到目的位置的最優(yōu)（最短）路徑。

為了便于研究與分析，本文采用柵格法進行環(huán)境建模，即將機器人二維環(huán)境信息通過提取與分析轉(zhuǎn)換成可理解的數(shù)學(xué)空間模型，便于機器人的研究與分析。假定全局環(huán)境的空間范圍為[S]，[S]為有限工作空間，柵格地圖如圖1所示。圖中白色方塊表示可行域，黑色方塊表示障礙物域。機器人可到達的位置為以其向周圍擴展的8個方位，每個柵格圖代表一定比例的大小。

從左下方位開始進行編號，各柵格點對應(yīng)的坐標數(shù)學(xué)關(guān)系如下：

[xi=mod（i-1，Nx）+0.5yi=fix（i-1）Ny+0.5] ? ?（1）

式中：[mod]表示取余;[fix]表示取整;[xi，yi]表示每個柵格的坐標位置;[Nx，Ny]分別表示每行、每列的柵格數(shù)目。

1.2 ?基于傳統(tǒng)蟻群算法的多機器人路徑規(guī)劃問題

螞蟻在尋找食物源的過程中會留下信息素，螞蟻根據(jù)信息素的數(shù)量大小參照概率自主選擇路徑，因此螞蟻可以找到從住巢到食物地之間的最優(yōu)路徑即最短路徑[8?9]。螞蟻行走示意圖如圖2所示。

初始狀態(tài)，設(shè)定每條路徑上的信息素含量相等，螞蟻[k]從柵格[i]轉(zhuǎn)移到柵格[j]的狀態(tài)轉(zhuǎn)移概率[p（k）ij（t）]由信息素量[τij]、啟發(fā)函數(shù)[ηij（t）]、信息啟發(fā)因子[α]以及期望啟發(fā)式因子[β]決定[10]。

（2）

式中：[τij]表示t時刻柵格點[ni，nj]之間的信息素含量;[Aa]表示禁忌表之外的螞蟻允許走的節(jié)點。在完成一次循環(huán)對路徑上的信息素上進行更新，假定完成一次周游所需時間為[Δt]，[t+Δt]時刻路徑[i，j]上的信息素[11]為：

[τijt+Δt=1-ρ?τijt+Δτijt] （3）

[Δτij（t）=k=1mΔτkij（t）] （4）

[Δτkij（t）=QLk，螞蟻k經(jīng)過（i，j）0] ?（5）

[ηij（t）=1dij] ? （6）

式中：[ρ]表示信息素揮發(fā)系數(shù)，[ρ∈0，1];[Q]表示信息素強度其值為常數(shù);[dij]表示柵格[i]到柵格[j]的距離;[Lk]表示在本次循環(huán)結(jié)束時螞蟻所走路徑的長度。

2 ?基于改進蟻群算法的多機器人路徑規(guī)劃

改進的蟻群算法流程圖如圖3所示。

步驟1：建模和環(huán)境描述，利用柵格法進行建模，設(shè)置算法參數(shù);

步驟2：將[m]只螞蟻放在初始位置;

步驟3：根據(jù)概率矩陣選擇路徑，并且將已走過的路徑添加至禁忌表，同時對下一步需走的路徑依照算法進行選擇;

步驟4：死鎖防止，若螞蟻搜索出現(xiàn)死鎖現(xiàn)象，終止搜索并設(shè)置當(dāng)前路徑長度為無窮大;

步驟5：找出此次迭代最小路徑[dbest]、最長路徑[dworse]以及之前迭代的最小路徑，并判定其與[dbest]的大小;

步驟6：更新信息素;

步驟7：重復(fù)步驟3～步驟6，直至迭代次數(shù)=設(shè)定的迭代次數(shù)，得到最短路徑;對傳統(tǒng)算法進行了如下改進。

2.1 ?啟發(fā)因子

算法中，啟發(fā)因子為[ηij（t）]與節(jié)點之間的距離成反比，蟻群算法作為自組織結(jié)構(gòu)存在搜索時間長的缺陷，而算法對時間度要求較高。本文對搜索因子即啟發(fā)因子做出了改進：根據(jù)所求空間的具體特征（兩個節(jié)點之間的距離），給定蟻群算法一個初步引導(dǎo)方向，改進的蟻群算法的啟發(fā)因子[ηij（t）]，[ηij（t）=1d2ij]，跟距離平方成反比，大大增加算法的時間有效性，能夠減小算法收斂的時間，同時保證最短路徑的搜索方向向著最短目標最優(yōu)方向進行。

2.2 ?信息素的更新策略

傳統(tǒng)蟻群算法信息素的更新方式使得搜索結(jié)果易陷入局部最優(yōu)解，導(dǎo)致出現(xiàn)“死鎖”現(xiàn)象，越來越多的螞蟻選擇同一條路徑而忽略其他路徑，很難尋得最優(yōu)解?；诖?，本文改進信息素的更新策略，通過關(guān)系使信息素不僅進行全局搜索，而且保證信息每次迭代過程中將本次迭代中的最短路徑和最長路徑運用到信息素的更新方式上。全局搜索和局部搜索相結(jié)合使得解不會因收斂過快而陷入局部最優(yōu)解，同時又保持快速發(fā)現(xiàn)最優(yōu)解的能力。

[τijt+Δt=1-ρ?τijt+Δτijt+dbestdworse]

（7）

式中：[dbest]表示迭代過程中的最短路徑;[dworse]表示迭代過程中的最長路徑。

正負反饋的結(jié)合保證系統(tǒng)以最優(yōu)的狀態(tài)尋得最短路徑。正反饋使得系統(tǒng)始終朝著最優(yōu)解的方向進行，算法實現(xiàn)的過程中采用概率搜索，縮小解的范圍;負反饋使得算法不會過早收斂，在兩者的共同作用下，使機器人花費最少的時間代價而尋找一條最優(yōu)路徑。

3 ?結(jié)果及分析

本文采用Matlab作為仿真工具，實驗過程分別選取39，52，80，100螞蟻數(shù)目（[m]值）進行設(shè)定，仿真參數(shù)：最大迭代次數(shù)設(shè)定為400，[α=0.9]，[β=6.8]，[Q=125]，[ρ=0.75]，傳統(tǒng)蟻群與改進蟻群算法選取的螞蟻數(shù)目相同。

3.1 ?傳統(tǒng)蟻群算法

圖4為傳統(tǒng)機器人的最短路徑收斂圖。

由仿真結(jié)果圖看出，算法在迭代240次后得到一個最優(yōu)解值為680，從而其最佳優(yōu)化指標為：

[c1=c0-c*c*=680-c*c*] ? ? ? ? ? （8）

式中：[c*]表示理論上該問題的最優(yōu)解;[c0]表示采用傳統(tǒng)的蟻群算法得到的最優(yōu)解，時間性能指標為：

[t1=E1TE=240TE] （9）

式中：[E1]表示終止條件時迭代的次數(shù);[E]為給定的迭代次數(shù);[T]為迭代一次所需的時間。

3.2 ?改進的蟻群算法

圖5為最優(yōu)路徑搜索圖（其中每個柵格代表一定比例的路徑大?。D6為改進蟻群算法的機器人最短路徑收斂圖。

由圖6得，算法在迭代115次后得到一個最優(yōu)解值455，從而得其最佳優(yōu)化指標：[c2=c0-c*c*=455-c*c*]，時間性能指標[t2=E1TE=115TE]。

3.3 ?結(jié)果分析

選取螞蟻數(shù)目的不同，將改進的蟻群算法與傳統(tǒng)的蟻群算法進行對比，對比表格如表1所示。

其中[c]代表最短路徑，[E]代表迭代次數(shù)，最佳優(yōu)化性能指標表示算法解決問題的優(yōu)化程度（找到最短路徑），針對該問題，其值越小表示算法的解越優(yōu)，根據(jù)點數(shù)不同得到的實驗結(jié)果分析：[c1>c2]，因此改進的蟻群算法相對傳統(tǒng)的蟻群算法優(yōu)化性能更好。時間性能指標與算法搜索的快慢程度有關(guān)，其值的大小與收斂的快慢程度成反比，其值越小收斂越快，值越大收斂越慢。[t1>t2]，因此改進的蟻群算法收斂更快。綜合分析，隨著點數(shù)的增加，研究問題的復(fù)雜度的增加，改進的蟻群算法在最佳優(yōu)化指標和時間優(yōu)化指標的優(yōu)勢越來越明顯。

4 ?結(jié) ?語

移動機器人全局路徑規(guī)劃問題是一個典型的智能優(yōu)化問題，建立環(huán)境模型抽象成數(shù)學(xué)坐標，在分析傳統(tǒng)蟻群算法的基礎(chǔ)上，對傳統(tǒng)蟻群算法進行了改進：主要從啟發(fā)因子和信息素更新策略兩方面。改進的蟻群算法較傳統(tǒng)的蟻群算法具有良好的優(yōu)化性能，且改進的蟻群算法收斂速度更快。

參考文獻

[1] 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機械學(xué)報，2014，45（6）：53?57.

SHI Enxiu， CHEN Minmin， LI Jun， et al. Research on method of global path?planning for mobile robot based on ant?colony algorithm [J]. Transactions of the Chinese Society for Agricultural Machinery， 2014， 45（6）： 53?57.

[2] 屈鴻，黃利偉，柯星.動態(tài)環(huán)境下基于改進蟻群算法的機器人路徑規(guī)劃研究[J].電子科技大學(xué)學(xué)報，2015，44（2）：260?265.

QU Hong， HUANG Liwei， KE Xing. Research of improved ant colony based robot path planning under dynamic environment [J]. Journal of University of Electronic Science and Technology of China， 2015， 44（2）： 260?265.

[3] YU J， LAVALLE S M. Optimal multi?robot path planning on graphs： structure and computational complexity [J/OL]. [2015?07?12]. https：//arxiv.org/pdf/1507.03289.pdf.

[4] LI J， DONG T， LI Y. Research on task allocation in multiple logistics robots based on an improved ant colony algorithm [C]// Proceedings of International Conference on Robotics and Automation Engineering. Jeju： IEEE， 2016： 17?20.

[5] LIU J， YANG J， LIU H， et al. An improved ant colony algorithm for robot path planning [J]. Soft computing， 2017， 21（19）： 5829?5839.

[6] 張成，凌有鑄，陳孟元.改進蟻群算法求解移動機器人路徑規(guī)劃[J].電子測量與儀器學(xué)報，2016，30（11）：1758?1764.

ZHANG Cheng， LING Youzhu， CHEN Mengyuan. Path planning of mobile robot based on an improved ant colony algorithm [J]. Journal of electronic measurement and instrumentation， 2016， 30（11）： 1758?1764.

[7] 牛治永，李炎，李曉嵐.基于改進蟻群算法的機器人路徑規(guī)劃[J].自動化技術(shù)與應(yīng)用，2011，30（7）：1?4.

NIU Zhiyong， LI Yan， LI Xiaolan. Path planning of detecting robot based on improved ant colony algorithm [J]. Techniques of automation and applications， 2011， 30（7）： 1?4.

[8] 肖國寶，嚴宣輝.一種新型協(xié)作多機器人路徑規(guī)劃算法[J].計算機科學(xué)，2013，40（4）：217?220.

XIAO Guobao， YAN Xuanhui. New cooperative multi?robot path planning algorithm [J]. Computer science， 2013， 40（4）： 217?220.

[9] 邱莉莉，鄭建立.基于改進蟻群算法的機器人路徑規(guī)劃[J].信息技術(shù)，2015（6）：150?152.

QIU Lili， ZHENG Jianli. Based on improved ant colony algorithm for robot path planning [J]. Information technology， 2015（6）： 150?152.

[10] 王忠民，曹棟.基于蟻群算法的行為識別特征優(yōu)選方法[J].西安郵電大學(xué)學(xué)報，2014，19（1）：73?77.

WANG Zhongmin， CAO Dong. A feature selection method for behavior recognition based on ant colony algorithm [J]. Journal of Xian University of Posts and Telecommunications， 2014， 19（1）： 73?77.

[11] 游曉明，劉升，呂金秋.一種動態(tài)搜索策略的蟻群算法及其在機器人路徑規(guī)劃中的應(yīng)用[J].控制與決策，2017，32（3）：552?556.

YOU Xiaoming， LIU Sheng， L? Jinqiu. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot [J]. Control and decision， 2017， 32（3）： 552?556.