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

占偉 屈軍鎖 蘆鑫 侯磊超

關鍵詞： 仿生優化; 蟻群算法; 柵格法; 移動機器人; 路徑規劃; 啟發因子; 信息素更新策略

中圖分類號： 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 ?引 ?言

隨著人工智能領域的高速發展，機器人路徑規劃問題已成為時代熱點之一。全局路徑規劃問題的研究是研究機器人動態路徑規劃方法的重要基礎。近年來，國內外學者相繼提出遺傳算法、神經網絡算法、人工勢場法和蟻群算法等算法[1?2]用于該問題。遺傳算法應用性廣但存在進化速度下降快，迭代次數冗余等問題[3];人工勢場法具有高效性的特點但也存在易陷入陷阱區等問題[4];神經網絡算法計算量大且結構復雜[5]。

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

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

1.1 ?問題描述與模型建立

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

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

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

3） 機器人起始位置和目標位置已知。多移動機器人路徑規劃需達到的效果是：最優結果，即各移動機器人需找到從出發位置到目的位置的最優（最短）路徑。

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

從左下方位開始進行編號，各柵格點對應的坐標數學關系如下：

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

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

1.2 ?基于傳統蟻群算法的多機器人路徑規劃問題

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

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

（2）

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

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

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

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

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

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

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

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

步驟1：建模和環境描述，利用柵格法進行建模，設置算法參數;

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

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

步驟4：死鎖防止，若螞蟻搜索出現死鎖現象，終止搜索并設置當前路徑長度為無窮大;

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

步驟6：更新信息素;

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

2.1 ?啟發因子

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

2.2 ?信息素的更新策略

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

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

（7）

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

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

3 ?結果及分析

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

3.1 ?傳統蟻群算法

圖4為傳統機器人的最短路徑收斂圖。

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

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

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

[t1=E1TE=240TE] （9）

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

3.2 ?改進的蟻群算法

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

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

3.3 ?結果分析

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

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

4 ?結 ?語

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

參考文獻

[1] 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規劃方法研究[J].農業機械學報，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] 屈鴻，黃利偉，柯星.動態環境下基于改進蟻群算法的機器人路徑規劃研究[J].電子科技大學學報，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].電子測量與儀器學報，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].自動化技術與應用，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] 肖國寶，嚴宣輝.一種新型協作多機器人路徑規劃算法[J].計算機科學，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].信息技術，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] 王忠民，曹棟.基于蟻群算法的行為識別特征優選方法[J].西安郵電大學學報，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] 游曉明，劉升，呂金秋.一種動態搜索策略的蟻群算法及其在機器人路徑規劃中的應用[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.