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

侯欣蕾+于蓮芝

摘要：針對蟻群算法進行機器人路徑規劃時存在搜索空間大、效率低、容易陷入局部最優解、易出現死鎖現象等問題，提出了一種改進的蟻群算法。在蟻群算法基礎上，只對較優螞蟻路徑進行信息素濃度更新；針對U型障礙物，提出了螞蟻回退策略，以及一些仿真實驗策略改進。仿真結果表明：改進后蟻群算法能快速搜索到最優路徑，有效避免死鎖現象，與其它算法相比，具有良好的路徑尋優能力與避障性能。

關鍵詞：移動機器人；路徑規劃；改進蟻群算法

DOIDOI：10.11907/rjdk.172054

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）012-0162-03

Abstract：When the ant colony algorithm（ACA） is used in mobile robot path planning， there are many problems such as large search space、inefficiency、easy to fail into locale optima、prove to deadlock and so on， an improved ant colony algorithm for robot path planning. At first， on the basic of ACA， phenomenon concentrations are updates only for the ant paths； Then the ant back off strategy is put forward for the U type obstacle； last some improvements in simulation experiments. Experiments proof： the improved ACA can fast search to optimal path and it can effectively avoided the deadlock phenomenon， compared with others algorithm， it has good route optimization ability and obstacle avoidance performance.

Key Words：mobile robot； path planning； an improved ant colony algorithm

0 引言

移動機器人研究包括路徑規劃、導航定位、路徑跟蹤與運動控制等技術，其中路徑規劃是機器人研究領域基礎與核心。國內外學者提出了柵格法、人工勢場法等路徑規劃方法[1-2]。柵格法一般用于機器人全局路徑規劃，但隨著機器人工作環境復雜程度不斷提高，柵格存儲空間需求也會增大，從而降低搜索效率。人工勢場法通常應用于機器人局部路徑規劃，但也存在致命缺陷：局部極小點、目標不可達。隨著神經網絡、遺傳算法、模糊控制等智能算法的提出與發展，許多學者將人工智能算法應用于路徑規劃，雖然可以提高求解速度，但存在算法復雜、搜索空間大等問題[3]。如何高效解決復雜環境下機器人路徑規劃問題依然是研究熱點。

受大自然中螞蟻覓食行為啟發，Marco Dorigo于1992年在博士論文中首次提出了蟻群算法。因為機器人路徑規劃類似螞蟻覓食行為，所以可使用蟻群算法進行機器人路徑規劃。使用蟻群算法進行路徑規劃，存在搜索時間長、局部最優解與死鎖現象[4]。因此，本文主要研究改進蟻群算法在機器人路徑規劃中的應用。

1 環境建模

機器人工作環境通過分形算法可以等效為二維平面的有限區域AS。鑒于AS可以為任意形狀，因此，在機器人環境建模時，需要在AS邊界向外補充障礙物柵格，使機器人工作環境補充為正方形或長方形[5]。使用柵格法劃分機器人工作環境AS，劃分柵格分為3種：白色柵格、黑色柵格、混合柵格。如圖1所示，白色柵格表示自由柵格，黑色柵格與混合柵格表示障礙物柵格，機器人可在自由柵格之間移動，且障礙物位置與大小均不發生改變。在建立的柵格空間上，按照從左到右，從上到下順序，依次為柵格標號，記為數字1，2，3，…，n，每一個數字都代表一個柵格；以柵格空間左下方為坐標原點，從左到右為X軸正方向，從下到上為Y軸正方向，柵格長度為單位長度，建立平面直角坐標系XOY。柵格序號與柵格坐標對應關系如下：

機器人路徑規劃過程中，為避免機器人與障礙物發生碰撞，對障礙物邊界進行膨化處理，向外擴展機器人最大長度1/2，則機器人可以等效為質點，其大小與尺寸忽略不計。上述方式劃分機器人工作空間能夠使環境模型與真實情況相符，使機器人路徑規劃暢通無阻。機器人路徑規劃起始位置與終止位置為任意柵格且都屬于AS（不在同一個柵格內且不是障礙柵格）。

2.1.3 迭代循環

完成每輪信息素更新后，將全部螞蟻放到機器人路徑規劃起始點，重新開始新一輪路徑規劃，N次迭代完成后，從中選出一條最優路徑。

2.2 蟻群算法改進

對機器人進行路徑規劃時，使用蟻群算法可規劃出一條從起始點到終止點安全、無碰撞的最優路徑，但也存在搜索時間過長、效率低、易出現死鎖等現象[4，8]。針對上述問題，本文對蟻群算法作出以下改進，使機器人能夠在更短時間內搜索出更短更平滑的路徑。

2.2.1 螞蟻回退策略

使用蟻群算法進行機器人路徑規劃過程中，螞蟻k遇到U型障礙物時，容易陷入死鎖現象，導致蟻群算法停滯。一旦出現此類情況，假設此時定義螞蟻k死亡，就會影響到算法魯棒性與適應度。因此，本文采用螞蟻回退策略來杜絕這類現象發生。螞蟻移動過程中遇到U型障礙物時，首先判斷螞蟻是否落入陷阱，如果落入陷阱，則螞蟻回退到上一節點，同時將螞蟻所在節點從禁忌表中移除，按照狀態轉移概率公式繼續選擇下一轉移節點，然后判斷是否陷入陷阱，直至螞蟻回退到逃出陷阱為止。endprint

在蟻群算法中加入螞蟻回退策略可保證所有螞蟻都能順利完成路徑搜索，即使螞蟻遇到U型障礙物也不會死亡，進一步保障了算法魯棒性與適應度，提升算法性能。

2.2.2 較優螞蟻路徑信息素更新

假設在每輪路徑搜索結束后，只對較優螞蟻路徑進行信息素更新，而其余路徑信息素則會因信息素揮發逐漸降低，將增大路徑上信息素差異，使螞蟻在搜索路徑過程中更傾向于信息素濃度較大路徑，螞蟻能夠較快集中在較優路徑鄰域，縮短算法求解時間，提高算法效率。

使用蟻群算法進行路徑規劃時，由于路徑規劃起始位置與終止位置已知，且螞蟻同時從起始位置出發進行路徑搜索，所以能夠在較短時間內能找到終止位置的螞蟻就是較優螞蟻，反之則為較差螞蟻。因此，在算法實現中，須找到前面幾只螞蟻的路徑，對其進行信息素更新，加大較優路徑與較差路徑信息素濃度差異，使螞蟻在選擇路徑時更加傾向于較優路徑，大大地降低路徑搜索時間，提高機器人路徑規劃搜索效率。

2.2.3 仿真策略改進

使用改進后蟻群算法進行機器人路徑規劃，采取以下策略：

（1）限制螞蟻下一步柵格選擇范圍。路徑搜索過程中，螞蟻移動到當前柵格時，下一步可選擇柵格只能是與當前柵格相鄰且沒有訪問過的無障礙物柵格。

（2）使用“輪盤賭”方法選擇下一柵格。通過“輪盤賭”方法結合狀態轉移概率公式，增大螞蟻選擇隨機性，提高螞蟻全局搜索能力，可有效防止算法過早收斂。

（3）校正搜索成功的螞蟻路徑。螞蟻在柵格之間移動可能會走彎曲路徑，通過對彎曲路徑的處理，可以進一步縮短搜索路徑總長度，使搜索路徑達到最優。

2.3 改進后蟻群算法流程

改進后蟻群算法流程如圖2所示。

3 實驗結果

將機器人工作空間劃分為20×20柵格，起始位置為（1，1），終止位置為（20，20）。算法參數設置：螞蟻數目m=50；迭代次數N=100；信息素揮發系數=0.3。

本文使用改進蟻群算法進行路徑規劃，搜索得到最優路徑如圖3所示，最短路徑收斂速度如圖4所示。

本文比較了A*算法、蟻群算法、改進蟻群算法性能，結果如表1所示。

由表1可知，改進蟻群算法可快速搜索到最優路徑，有效避免死鎖現象，具有良好路徑尋優能力與避障性能。

4 結語

本文針對機器人路徑規劃中存在問題，改進了蟻群算法，只對路徑較優螞蟻進行信息素更新，大量減少信息素更新計算量，在一定程度上提高算法收斂速度；校正搜索成功的螞蟻路徑，拉直螞蟻在相鄰柵格之間多走的彎曲路徑，縮短搜索路徑長度；處理U型障礙物，提出了螞蟻回退策略，避免陷入局部最優解與死鎖現象。大量仿真實驗證明，改進后蟻群算法能夠快速搜索到最優路徑，有效避免死鎖現象，與其它算法相比，具有良好路徑尋優能力與避障性能。

參考文獻：

[1] 歐陽鑫玉，楊曙光.基于勢場柵格法的移動機器人避障路徑規劃[J].控制工程，2014（1）：134-137.

[2] 溫素芳，郭光耀.基于改進人工勢場法的移動機器人路徑規劃[J].計算機工程與設計，2015（10）：226-230.

[3] 朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010（7）：4-10.

[4] 周明秀，程科，汪正霞.動態路徑規劃中的改進蟻群算法[J].計算機科學，2013（1）：320-322.

[5] 羅榮貴，屠大維.柵格法視覺傳感集成及機器人實時避障[J].計算機工程與應用，2011（24）：237-239.

[6] 萬曉鳳，胡偉，方武義，等.基于改進蟻群算法的機器人路徑規劃研究[J].計算機工程與應用，2014（18）：63-66.

[7] 康冰，王曦輝，劉富.基于改進蟻群算法的搜索機器人路徑規劃[J].吉林大學學報，2014（4）：167-173.

[8] XIONG W， WEI P.A kind of ant colony algorithm for function optimization[C].Proceeding of the 1st International Conference on Machine Learning and Cybernetics，2002：552-555.

（責任編輯：何 麗）endprint