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

朱顥東，孫 振，吳 迪，申 圳

(鄭州輕工業學院 計算機與通信工程學院 河南 鄭州 450002)

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

朱顥東，孫 振，吳 迪，申 圳

(鄭州輕工業學院 計算機與通信工程學院 河南 鄭州 450002)

針對蟻群算法應用于移動機器人路徑規劃時存在易于陷入局部最優解、收斂速度慢的問題，提出了一種適用于靜態障礙環境下基于改進蟻群算法的移動機器人路徑規劃方法。該方法改進了節點間的狀態轉移規則，增加了得到最優路徑的概率；自適應調整啟發函數，提高了算法的搜索效率；基于狼群法則對信息素進行更新，有效避免了算法陷入局部最優解；動態調整了衰減系數，在后期增加了螞蟻對最優路徑的選擇概率，加快了算法的收斂速度。仿真實驗表明，與其他算法在相同環境下比較，該改進算法在路徑規劃結果相同的情況下具有較快的收斂速度；且改進算法在不同復雜程度環境中均得到了最優路徑，也表明了該算法的有效性和可靠性。該算法具有良好的尋優能力，可以適用于不同復雜環境中的移動機器人路徑規劃。

移動機器人；蟻群算法；路徑規劃

0 引 言

移動機器人路徑規劃是近年來機器人研究領域的重要分支和研究熱點之一。移動機器人路徑規劃是指移動機器人在有障礙物的環境中，找到一條從起始點到目的點最優的無碰路徑[1-2]。路徑規劃問題具有復雜性、多約束性和多目標性等特點。傳統的路徑規劃算法有Dijkstra，A*算法等，Dijkstra是一種經典的最短路徑搜索算法，它是一種貪心算法，雖然能很好地規劃出路徑，但是由于該算法是以起始點向外層層擴展，直到搜索到目的節點為止，需要遍歷節點，計算復雜度高，效率比較低；A*算法是一種啟發式算法，它是通過估價函數來確定當前點到目標點的距離和搜索方向，在復雜的環境中一個不理想的估計函數容易導致搜索不到路徑或者規劃路徑效果不理想。近年來，在移動機器人路徑規劃方法中，國內外專家學者提出了許多仿生智能優化算法[3]，如：遺傳[4]、人工魚群[5]、蛙跳[6]、神經網絡[7]以及蟻群[8]等算法。

1992年，Marco Dorigo在博士論文中提出了蟻群算法，通過觀察螞蟻尋找食物源時發現路徑的行為而獲得啟發。傳統的蟻群算法主要是解決旅行商問題(travelling salesman problem，TSP)，文獻[9]借鑒最大-最小蟻群系統的方法，限制了信息素的值域范圍，有效地避免了算法陷入局部最優解問題。文獻[10]構建了權重可調的引力概率函數，并且把它作為啟發因子，有效地提高了算法的收斂速度。文獻[11]改進了算法的信息素更新規則，并加入拐點作為評價路徑質量的參數之一，提高了算法的效率。文獻[12] 分析了影響蟻群優化中的關鍵參數，自適應地設置了算法參數，調高了算法的精度和效率。文獻[13]提出了一種基于人工勢場法的移動機器人路徑規劃方法，定義了一種新的引力函數，有效地提高了路徑規劃的性能。文獻[14]提出了自適應調整啟發函數、路徑平滑策略，有效地提高了路徑的質量。目前，不少算法在求解機器人全局路徑問題中存在著局限性，遺傳算法由于運算進化代數眾多，規劃路徑時占用大量的存儲空間，導致運算速度較慢。人工魚群算法雖然具有較快的收斂速度，但是很難得到精確的解，規劃出的路徑質量不理想；混合蛙跳算法易于陷入局部最優解，求解精度較低，而且收斂速度較慢，限制了該算法在路徑規劃領域的應用；神經網絡算法雖然具有較強的學習能力，但是當機器人在復雜的環境中，很難用數學公式來描述。人工勢場法是以其數學計算上的簡單明了而被廣泛應用到路徑規劃中，但是，人工勢場法存在局部極小點和目標不可達等問題。而蟻群算法是一種模擬進化算法，具有自組織性、較強的魯棒性、分布式計算、尋優能力強、易于和其他算法相結合等優點，非常適合應用到移動機器人路徑規劃問題。

因此，論文提出利用改進蟻群算法規劃移動機器人路徑，并提出了動態調整揮發系數、自適應調整啟發函數等策略，能夠在不同復雜程度的環境中得到全局最優路徑，提高了算法的搜索速率，并加快了算法的收斂速度，通過在Matlab軟件中仿真實驗，表明了該算法是有效和可行的。

1 問題描述與建模

機器人路徑規劃中重要的問題之一是環境建模。建模就是根據已知機器人周圍的環境信息，通過提取和分析，將現實中物理空間轉換為機器人可以理解的空間，通過建立良好的環境模型，有效地減少了路徑搜索過程中的麻煩。論文中主要用柵格法對機器人的二維環境進行劃分，從左到右，從上到下對柵格進行編號，論文中以10×10的柵格環境為例來說明，如圖1所示。

圖1 柵格坐標與序號關系Fig.1 Grid coordinate relates with serial number

圖1中，坐標原點0在左下方，水平從左向右為x軸正方向，垂直從下到上為y軸正方向，柵格的大小由移動機器人自身的大小和它運動步長決定，為了簡化計算路徑的長度，一個柵格的邊長為機器人的運動步長，即一個單位長度。序號與坐標的對應關系如下

(1)

(1)式中：Ni表示柵格的序號；N表示每一列的柵格數量；mod表示取余數；ceil表示向后取整數。

為了建立機器人可以理解的環境，根據環境地圖建立相應的矩陣來表示每個柵格的狀態(可行柵格和障礙柵格)，在下面矩陣中，0代表可行柵格；1代表障礙柵格，每一個障礙可能占用一個或多個柵格，若障礙物占用不足一個柵格，視為占用一個完整柵格；機器人被視為一個點狀機器人；將障礙物以機器人半徑的大小進行膨化，確保機器人可以安全地通過障礙物邊界。10×10的棚格環境可用矩陣表示為

(2)

2 基于改進蟻群算法的路徑規化

研究表明螞蟻會在經過的路徑上會留下信息素，并且可以在一定范圍內感知信息素進而引導自己的運動，因此，蟻群會表現出一種正反饋現象：越多的螞蟻經過一條路徑，就會在這條路徑上釋放越多的信息素，后面的螞蟻選擇這條路徑的概率就越大，螞蟻之間就是通過這種信息素的交流來選擇路徑，進而找到食物源[3]。蟻群算法具有局部尋優能力強、自組織性等優點，能很好地應用到路徑規劃中，但傳統蟻群算法存在容易陷入局部最優解、收斂速度慢等問題，為了提高蟻群算法的搜索效率和路徑規劃質量，論文對傳統蟻群算法做了以下改進。

2.1 改進節點狀態轉移規則

螞蟻會根據啟發函數η和路徑上的信息素濃度τ來選擇下一步的可行節點，設定螞蟻的種群數量為m，假設當前螞蟻k在節點i處，比較q和q0的大小，按照(3)式的概率進行選擇下一步可行節點j。

(3)

(4)

2.2 自適應調整啟發函數

在傳統的蟻群算法中，啟發函數η是2個節點之間距離的倒數。A*算法是一種啟發式算法，表示為f(n)=g(n)+h(n)，其中，g(n) 表示從初始節點到當前節點的實際代價；h(n) 表示當前節點到目的節點的估計代價，在g值一定的情況下，h值越小，f值就越小，能保證最短路經的搜索向著目標點方向進行。由啟發式A*算法獲得啟發，下一可行節點j和目標點之間的距離可用于啟發函數ηij，即dij和djt被用于啟發函數上，即為

(5)

(5)式中：dij是當前節點i和可行節點j間的歐氏距離；djt是可行節點j和目的節點t間的歐式距離，把目的節點引用到啟發函數中，加強了路徑搜索的方向性，減少了算法的搜索空間，有效提高搜索的效率。但是過早的引入方向性啟發信息，使得初始的搜索空間太小從而導致算法容易陷入局部最優解；在初始階段引進起始節點S和當前節點i之間的距離dsi，作為衡量搜索空間大小的標準，隨著后期擴大搜索空間后，方向啟發信息將會被引進。啟發函數為

(6)

(6)式中：dst是起始節點和目的節點的歐式距離；閥值ε是一個常數，由dst的長度具體決定。

2.3 改進信息素更新方式

在傳統的蟻群算法中，最差螞蟻的信息素經過正反饋之后可能導致算法搜索陷入局部最優解，為了避免這個問題，論文借用狼群法則對信息素進行更新，在一次循環中，找到經過局部最優的路徑和局部最差路徑的螞蟻，分別增加和減少釋放信息素濃度的量[3]，各條路徑按照(6)-(8)式進行信息素濃度更新。

(7)

(8)

(9)

2.4 動態調整衰減系數

在全局路徑規劃中信息素的衰減系數ρ起到重要作用，當環境復雜時，一個比較大的衰減系數會增加信息素的正反饋，減少搜索空間以至于降低了找到最優路徑的可能性；一個比較小的衰減系數會增加搜索時間。隨著時間和迭代次數的增加，傳統蟻群算法容易陷入局部最優解，為了避免這個問題，減少算法搜索時間并且能夠保證找到最優路徑，論文提出動態地設置衰減系數，表示為

(9)

3 算法流程

步驟1初始化參數。生成已知環境中的障礙物柵格地圖，設置柵格的序號。設定種群個數m，起始點S，目的點T，蟻群最大迭代次數Nmax，柵格的行數M和列數N，設置信息素的影響權值α和啟發式信息影響權值β。

步驟2所有螞蟻進行路徑選擇。將m只螞蟻放到起始點，螞蟻k(k=1,2,3,…,m)從起始點S出發，并將起始點添加到禁忌表tabuk中，按照(3)式尋找下一個可行節點j，若j∈allowedk，選擇下一個柵格j，并將當前節點j添加到禁忌表tabuk中。

步驟3判斷螞蟻是否到達目的點T。若螞蟻到達目的點T，則記錄螞蟻走過的柵格序號和長度，若沒有到達目的點T，則繼續搜索下一節點，直到找到目的點T為止。若某個螞蟻k陷入停滯，則剔除螞蟻k。如果本代中所有螞蟻都搜索完畢，轉到步驟4。

步驟4更新信息素。計算本代中所有螞蟻得到的可行路徑的長度，找出本次循環中到達目的節點的局部最優和最差螞蟻，按照(6)式對每個柵格進行信息素更新。

步驟5判斷是否達到最大的迭代次數Nmax。若算法達到最大迭代次數，則輸出當前群體中最短的路徑的長度，否則，清空禁忌表tabuk，令N=N+1，轉到步驟2，繼續搜索，直到達到最大的迭代次數Nmax，算法結束，輸當前群體中最短路徑的長度。

4 算法仿真

使用Matlab軟件對改進蟻群算法進行了仿真實驗，比較了仿真結果，并對仿真結果進行了分析。

1)用論文提出的算法和文獻[11]所提出的算法進行比較，在文獻[11]中的柵格環境(20×20)進行仿真實驗，設置相同的蟻群數量100，通過仿真實驗，文獻[11]和本文改進算法中路徑規劃圖分別如圖2、圖4所示，文獻[11]和本文算法迭代圖分別如圖3、圖5所示。

圖2 文獻[11]中最優路徑規劃結果Fig.2 Result of optimal path planning in reference[11]

由于論文中將目標節點引用到啟發函數，以加強算法搜索的方向性，減少了搜索空間，有效提高了算法的搜索效率；自適應地調整了衰減系數，隨著迭代次數的增加衰減系數而增加，直到達到最大值，前期一個較小的衰減系數可以增加搜索空間，以便找到最優解；后期一個較大的衰減系數增加了信息素的正反饋，使得在后期越來越多的螞蟻傾向于經過最優路徑，可以有效地避免算法陷入局部最優解，同時使得算法更快的收斂于全局最優解，提高了算法搜索效率和收斂速度。因此，從以上仿真結果可以看出，在相同的復雜程度(20×20)和相同障礙物情況下，論文提出的算法和文獻[11]中提出的算法規劃最優路徑長度相等，質量(具有相同拐點)相同，但是算法收斂速度略高于文獻[11]，表明本文提出的算法具有一定的優越性。

圖3 文獻[11]中算法迭代曲線Fig.3 Iterative curve of algorithm in literature[11]

圖4 本文改進蟻群算法最優路徑規劃結果Fig.4 Result of optimal path planning based on improved algorithm in the paper

圖5 本文改進蟻群算法迭代曲線Fig.5 Iterative curve of improved algorithm in the paper

2)在不同復雜程度的靜態環境中仿真實驗，實驗數據分別設置為種群數量m=50，最大迭代次數為100，ρmin=0.1，ρmax=0.5，α=1.1，β=7。實驗結果如下。

①在10×10柵格環境中進行仿真試驗，路徑規劃結果如圖6所示，路徑長度為13.90，算法迭代如圖7所示。

圖6 10×10柵格環境中路徑規劃結果Fig.6 Result of path planning in the 10×10 environment

圖7 10×10柵格環境中改進算法迭代曲線Fig.7 Iterative curve of improved algorithm in the 10×10 environment

②在20×20的柵格環境進行仿真試驗，路徑規劃結果如圖8所示，路徑長度為29.21，算法迭代如圖9所示。

圖8 20×20柵格中環境路徑規劃結果Fig.8 Result of path planning in the 20×20 environment

圖9 20×20柵格環境中改進算法迭代曲線Fig.9 Iterative curve of improved algorithm in the 20×20 environment

③在30×30的柵格環境進行仿真試驗，路徑規劃結果如圖10所示，路徑長度為43.36，算法迭代如圖11所示。

圖10 30×30柵格環境中路徑規劃結果Fig.10 Result of path planning in the 30×30 environment

通過在不同的靜態柵格環境(從簡單到復雜的柵格環境)中進行多個仿真試驗，表明算法不僅在簡單的環境中可以規劃出最優路徑，而且在復雜的環境中也可以規劃出最優路徑，并且算法迭代次數較少，收斂速度較快，即該算法在路徑規劃中適用于不同復雜程度的環境，具有可行性和有效性。

圖11 30×30柵格環境中改進算法迭代曲線Fig.11 Iterative curve of improved algorithm in the 30×30 environment

5 結束語

傳統蟻群算法在移動機器人路徑規劃問題中存在收斂速度慢、易陷入局部最優解、路徑效果不理想等問題。針對這些問題，論文對節點間的狀態轉移規則、啟發函數的自適應調整、信息素更新方式、衰減系數的動態調整進行改進，通過在相同的環境中和文獻[11]中的算法比較，在得到路徑質量相同的情況下，論文提出的算法可以通過較少的迭代次數找到最優路徑和較快的收斂速度；通過在不同復雜程度的環境中進行多個仿真實驗，該算法都能規劃出理想的路徑，表明了該算法的可行性和有效性。通過對比試驗和試驗仿真，表明了論文提出的算法具有一定的優越性。論文中主要是針對移動機器人在靜態環境中全局路徑規劃，沒有考慮到存在有限個動態障礙物的情況，這也是論文的不足之處及后續的研究重點。

[1] 李成兵,郭瑞雪,李敏.改進蟻群算法在旅行商問題中的應用[J].計算機應用,2014,34(S1):131-132. LI Chengbing, GUO Ruixue,LI Min. Application of improved ant colony algorithm in travelling salesman problem[J]. Journal of Computer Applications,2014, 34(S1):131-132.

[2] 張琦,馬家辰,謝偉,等. 基于改進蟻群算法的移動機器人路徑規劃[J].東北大學學報:自然科學版,2013,34(11):1521-1524. ZHANG Qi, MA Jiachen, XIE Wei, et al. Improved Ant Colony Algorithm-Based Path Planning for Mobile Robot[J]. Journal of Northeastern University: Natural Science, 2013, 34(11):1521-1524.

[3] RAJA P, PUGAZHENTHI S. Optimal path planning of mobile robots: A review [J]. International Journal of Physical Sciences,2012,7(9): 1314-1320.

[4] 潘桂彬,潘豐,劉國棟.基于改進混合蛙跳算法的移動機器人路徑規劃[J].計算機應用,2014,34(10)：2850-2853. PAN Guifeng, PAN Feng, LIU Guodong. Path planning for mobile robots based on improved shuffled frog leaping algorithm[J]. Journal of Computer Applications, 2014,34(10)：2850-2853.

[5] 段俊花,李孝安. 基于改進遺傳算法的機器人路徑規劃[J]. 微電子學與計算機,2005,22(1):70-72. DUAN Junhua, LI Xianan. Robot Path Planning Based on Improved Genetic Algorithm[J]. Microelectronics & Computer,2005, 22(1):70-72.

[6] 聶黎明,周永權. 基于人工魚群算法的 機器人路徑規劃[J].計算機工程與應用,2008,44(32):48-50. NIE Liming, ZHOU Yongquan. Path planning of robot based on artificial fish-swarm algorithm[J].Computer Engineering and Applications, 2008,44(32):48-50.

[7] 王愛民,史慶國,呂晨亮.機器人路徑規劃的神經網絡算法及優化[J].河北工業大學學報.1999,28(6):13-16. WANG Aimin, SHI Qingguo, LV Chenliang. Path Planning and Optimizing Algorithm of Robot Based on Neural Network[J]. Journal of Hebei University of Technology. 1999,28(6):13-16.

[8] 柳長安, 鄢小虎, 劉春陽,等，基于改進蟻群算法的移動機器人動態路徑規劃方法[J].電子學報,2011,39(5)：1220-1223. LIU Changan,YAN Xiaohu,LIU Chunyang, et al. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J]. Acta Electronica Sinica, 2011,39(5)：1220-1223.

[9] 張毅,高永琪,牛興江. 一種改進蟻群優化算法的仿真研究[J].武漢理工大學報:交通科學與工程版,2013,37(6)：1330-1332. ZHANG Yi, GAO Yongqi, NIU Xingjiang. Simulation Research with an Improved Ant Colony Algotithm[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2013,37(6)：1330-1332.

[10] 孫純哲,桂貴生,韓東,等. 基于蟻群算法的移動機器人路徑規劃研究與應用[J].合肥工業大學:自然科學版,2006,29(10):1208-1211. SUN Guizhe, GUI Guisheng, HAN Dong, et al. Algorithm for mobile robot path planning based on the ant colony algorithm and its application[J].Journal of Hefei University of Technology: Natural Science Edition, 2006,29(10):1208-1211.

[11] 萬曉鳳,胡偉,方武義,等.基于改進蟻群算法的機器人路徑規劃研究[J].計算機工程與應用,2014,50(18):63-66.

WANG Xiaofeng, HU Wei, FANG Wuyi,et al. Research on path planning of robot based on improved ant colony algorithm[J].Computer Engineering and Applications, 2014, 50(18)：63-66.

[12] 劉道華, 熊炎, 李為華,等. 蟻群參數自適應調整的優化設計[J].計算機應用研究,2011,28(3):905-908. LIU Daohua, XIONG Yan, LI Weihua, et al. Ant Colony optimization with self-adaptive parameter adjusting[J].Application Research of Computers, 2011,28(3):905-908.

[13] YIN L ,YIN Y X , LIN C J. A new potential field method for mobile robot path planning in the dynamic environments[J]. Asian Journal of Control,2009,11(2): 214-225.

[14] WANG Y T，LI J J. A route planning optimization model based on improved ant colony algorithm[C]//IEEE.2009 Eigth IEEE/ACIS International Conference on Computer and Information Science. ShangHai:IEEE Press, 2009: 82- 86.

朱顥東(1980-),男,河南虞城人,副教授,博士,碩士生導師,主要研究方向為智能信息處理、計算智能。E-Mail:zhuhaodong80@163.com。

孫 振(1989-),男,河南新鄉人,在讀碩士研究生,主要研究方向為智能信息處理、模式識別。

吳 迪(1990-),男,河南南陽人,在讀碩士研究生,主要研究方向為智能信息處理、圖像處理。

申 圳(1989-),男,河南唐河人,在讀碩士研究生,主要研究方向為圖像處理、模式識別。

(編輯：劉 勇)

Path planning for mobile robot based on improved ant colony algorithm

ZHU Haodong, SUN Zhen, WU Di, SHEN Zhen

(School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, P.R. China)

In order to solve the problem that the ant colony algorithm was used in path planning for mobile robot, and is easily falls into local optimum and has a slow convergence speed, the paper proposes a method that the improved ant colony algorithm was used in path planning for mobile robot in the static environment. The method improves the transition rule of node state to increase the probability of searching optimal path. An adaptive heuristic function improves the searching efficiency of the algorithm. Updating the pheromone avoids falling into local optimum based on the assignment rule of wolves. Dynamical adjustment of the decay parameter increases the probability of choosing the optimal path by ants at a later stage, thus accelerating the convergence speed. The simulation results show that the improved algorithm has faster convergence speed under the condition of the same result of path planning when compared to other algorithm in the same environment. The improved algorithm obtains the optimal path in the environments of different complexity levels and it shows the efficiency and feasibility of the improved algorithm, which has good optimization ability and can be applied to path planning for mobile robot in the environments of different complexity levels.

mobile robot; ant colony algorithm; path planning

10.3979/j.issn.1673-825X.2016.06.017

2015-06-18

2016-03-10

朱顥東 zhuhaodong80@163.com

國家自然科學基金(61201447);河南省高等學校青年骨干教師資助計劃項目(2014GGJS-084);河南省科技創新杰出人才計劃項目(134200510025);河南省教育廳科學技術研究重點項目 (13A520367);鄭州輕工業學院校級青年骨干教師培養對象資助計劃項目(XGGJS02);鄭州輕工業學院博士科研基金(2010BSJJ038);鄭州輕工業學院研究生科技創新基金

Foundation Items：The National Natural Science Foundation of China (61201447);The Youth Backbone Teachers Funding Planning Project of Colleges and Universities in Henan Province of China(2014GGJS-084);The Technology Innovation Outstanding Talents Plan Project of Henan Province of China(134200510025);The Science and Technology Research Key Project of Education Department of Henan Province of China (13A520367);The Youth Backbone Teachers Training Targets Funded Project of Zhengzhou University of Light Industry of Henan Province of China(XGGJS02);The Ph.D.Research Funded Project of Zhengzhou University of Light Industry of Henan Province of China (2010BSJJ038) ;The Science and Technology Innovation Fund Project of Postgraduate of Zhengzhou University of Light Industry

TP301

A

1673-825X(2016)06-0849-07