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

占偉 屈軍鎖 蘆鑫 侯磊超

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

中圖分類號(hào)： TN929.5?34; TP242 ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 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ā)展，機(jī)器人路徑規(guī)劃問題已成為時(shí)代熱點(diǎn)之一。全局路徑規(guī)劃問題的研究是研究機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法的重要基礎(chǔ)。近年來，國(guó)內(nèi)外學(xué)者相繼提出遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、人工勢(shì)場(chǎng)法和蟻群算法等算法[1?2]用于該問題。遺傳算法應(yīng)用性廣但存在進(jìn)化速度下降快，迭代次數(shù)冗余等問題[3];人工勢(shì)場(chǎng)法具有高效性的特點(diǎn)但也存在易陷入陷阱區(qū)等問題[4];神經(jīng)網(wǎng)絡(luò)算法計(jì)算量大且結(jié)構(gòu)復(fù)雜[5]。

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

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

1.1 ?問題描述與模型建立

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

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

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

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

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

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

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

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

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

螞蟻在尋找食物源的過程中會(huì)留下信息素，螞蟻根據(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時(shí)刻?hào)鸥顸c(diǎn)[ni，nj]之間的信息素含量;[Aa]表示禁忌表之外的螞蟻允許走的節(jié)點(diǎn)。在完成一次循環(huán)對(duì)路徑上的信息素上進(jìn)行更新，假定完成一次周游所需時(shí)間為[Δt]，[t+Δt]時(shí)刻路徑[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ù)]發(fā)系數(shù)，[ρ∈0，1];[Q]表示信息素強(qiáng)度其值為常數(shù);[dij]表示柵格[i]到柵格[j]的距離;[Lk]表示在本次循環(huán)結(jié)束時(shí)螞蟻所走路徑的長(zhǎng)度。

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

改進(jìn)的蟻群算法流程圖如圖3所示。

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

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

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

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

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

步驟6：更新信息素;

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

2.1 ?啟發(fā)因子

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

2.2 ?信息素的更新策略

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

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

（7）

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

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

3 ?結(jié)果及分析

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

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

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

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

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

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

[t1=E1TE=240TE] （9）

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

3.2 ?改進(jìn)的蟻群算法

圖5為最優(yōu)路徑搜索圖（其中每個(gè)柵格代表一定比例的路徑大小）。圖6為改進(jìn)蟻群算法的機(jī)器人最短路徑收斂圖。

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

3.3 ?結(jié)果分析

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

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[1] 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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] 屈鴻，黃利偉，柯星.動(dòng)態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J].電子科技大學(xué)學(xué)報(bào)，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] 張成，凌有鑄，陳孟元.改進(jìn)蟻群算法求解移動(dòng)機(jī)器人路徑規(guī)劃[J].電子測(cè)量與儀器學(xué)報(bào)，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] 牛治永，李炎，李曉嵐.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[J].自動(dòng)化技術(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] 肖國(guó)寶，嚴(yán)宣輝.一種新型協(xié)作多機(jī)器人路徑規(guī)劃算法[J].計(jì)算機(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] 邱莉莉，鄭建立.基于改進(jìn)蟻群算法的機(jī)器人路徑規(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] 王忠民，曹棟.基于蟻群算法的行為識(shí)別特征優(yōu)選方法[J].西安郵電大學(xué)學(xué)報(bào)，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] 游曉明，劉升，呂金秋.一種動(dòng)態(tài)搜索策略的蟻群算法及其在機(jī)器人路徑規(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.