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

沈葭櫟，李燕，2，季建楠，佘宇

（1.南京信息工程大學，自動化學院，南京210044；2.南京信息工程大學濱江學院，物聯網學院，無錫214105）

0 引言

移動機器人的路徑規劃在機器人技術中尤為重要。移動機器人可通過人類的設計規劃，替代人類進行危險復雜的工作。移動機器人路徑規劃常用的算法有Dijkstra算法［1］、A*算法［2］、人工勢場法［3］等。在較多障礙物的情況下，仿生智能算法能夠幫助移動機器人尋找到較優路徑。近年來一些學者通過粒子群算法［4］、遺傳算法［5］、DNA計算［6］、蟻群算法等來解決機器人路徑規劃問題。

Marco Dorigo于1992年在他的博士論文中提出蟻群算法，是一種啟發式全局優化算法。蟻群算法具有正反饋、并行性，易與其他算法相結合的優點［7］。但傳統蟻群算法存在收斂速度慢，易陷入局部最優等問題。近年來一些學者提出了一些改進的蟻群算法。2014年杜鵬楨等人提出一種面向對象的多角色蟻群算法，對蟻群結構進行優化分為分工不同地三種蟻群，僅各蟻群最優個體進行信息素更新，對于大規模TSP問題有較好的結果［8］。2020年杜玉紅等人提出了一種粒子群參數優化的改進蟻群算法，實驗結果表明改進算法可提高移動機器人到達目標點的速度并降低機器人運動過程中的損耗［9］。2020年官娟等人提出一種基于MIMIC算法和RPCA的混合蟻群算法，通過實驗對比表明在連續域上尋優能力和收斂性方面都有明顯的提高［10］。

研究機器人路徑規劃問題可分為兩部分。第一部分是機器人運動環境的搭建，將機器人的運動空間解析成機器人能識別的數學模型，在機器人全局路徑規劃問題中，柵格法是最常用的環境建模方法。第二部分是路徑規劃方法的選擇。為解決蟻群算法收斂慢，易陷入局部最優解的問題。本文提出一種對蟻群算法中信息素的更新進行改進的方法，引入了懲罰系數的概念，使當前最優路徑上的信息素濃度下降，從而達到跳出局部最優的目的。將信息素濃度設置為分級動態變化，隨迭代次數增加而逐漸衰減，當迭代到一定次數后，不再衰減，達到加速收斂的目的。

1 環境建模

柵格法是將機器人的工作環境建立在二維直角坐標系上，根據機器人運動空間的實際情況，將地圖分割成固定大小的柵格。柵格環境為X行Y列，每個柵格邊長都為1。柵格地圖內的可分為三種柵格：第一種是障礙柵格，第二種是可移動柵格，第三種是起始點柵格。

起點坐標為（0，0），終點坐標為（19，19）。在本文中螞蟻只能朝上、下、左、右、左上、右上、左下、右下八個方向運動。柵格地圖如圖1所示，其中黑色為障礙物。

圖1 柵格地圖

2 傳統蟻群算法（AS）

以旅行商（TSP）問題為例，將m只螞蟻放入有n個城市的環境中，當t時刻，隨機選取一個城市i，讓第k只螞蟻從該城市出發，以公式（1）計算得到的概率采取蒙特卡洛算法來選擇這只螞蟻下一個到達的城市。

每個螞蟻在搜素的過程中，會在已走過的路徑上留下一定濃度的信息素，加大整個系統的正反饋，使算法加速收斂。AS的信息素更新有三種模型：①蟻周模型；②蟻量模型；③蟻密模型。蟻周模型是使用比較多的一種，信息素更新方式見公式（2）。

公式（2）中：ρ是信息素揮發因子，表示信息素的持久度，該系數增大會使之前螞蟻在路徑上留下的信息素揮發變快，導致算法隨機性加強，收斂速度也降低了；反之，該系數的減小會使之前遺留在路徑上的信息素揮發減慢，能夠加速算法的收斂，也會導致算法陷入局部最優的情況。Δτij是螞蟻搜索完成后，在路徑上留下的信息素增量，要與之前地圖中的信息素進行疊加。在達到設定的迭代次數，或得到期望的解時，結束整個過程，輸出最優解。

3 改進蟻群算法

3.1 優化路徑搜索策略

（1）后退策略。螞蟻在路徑搜索的過程中將螞蟻已經走過的路徑節點存入禁忌表，禁忌表中已有節點在選擇下一個節點時不會被選取，當螞蟻進入U型障礙會使螞蟻找不到可選擇的下一節點，如圖2所示。

圖2 U型障礙

針對U型障礙會使螞蟻找不到可選擇的下一節點，或其他找不到可選擇的下一節點的問題，引入后退策略。螞蟻沿著原路徑返回，每后退一個節點，判斷是否有未走過的節點，如果找到了就走新的節點，更新禁忌表中已走過節點，繼續算法的進行。

（2）修正策略。除了上述無法找到可選擇的下一節點的問題。在搜索過程中，因為路徑信息素濃度的影響，螞蟻在路徑選擇大概率選擇信息素濃度高的節點從而出現了繞路，會存在兩種路徑缺陷，如圖3和圖4所示。

圖3 路徑缺陷1

圖4 路徑缺陷2

在每次迭代結束后，對迭代的最優路徑進行分析，判斷是否存在路徑缺陷問題，并通過修正策略進行修正，修正后的路徑就是此次迭代的最優路徑。路徑修正如圖5和圖6所示。

圖5 修正后路徑缺陷1

圖6 修正后路徑缺陷2

3.2 動態分級信息素濃度

在傳統蟻群算法中，如果使用的是蟻周模型，信息素的更新都取決于上一次迭代中的結果最好的一次，影響信息素的更新，其中求解質量較差的路徑就會影響算法后續迭代的解的質量，導致算法收斂速度變慢。為降低質量較差的迭代結果對算法的負優化，提高質量較高的迭代結果對算法的影響，引入了信息素濃度的分級策略。根據柵格地圖大小，設定每個級別的路徑長度界限，將每次迭代的結果分為：優質路徑，信息素濃度為Q1；較優路徑，信息素濃度Q2；較差路徑，信息素濃度Q3；低質路徑，信息素濃度為Q4。

在傳統蟻群算法中，信息素濃度Q和揮發系數ρ的值對于整個算法的收斂速度是起決定作用的。Q的值偏大，而揮發系數ρ的值偏小時，算法容易陷入局部最優。而Q的值偏小，揮發系數ρ的值偏大時，算法整體的全局搜索能力變得極低。針對這一問題，提出一種動態變化信息素濃度Q的方式，隨著迭代次數的增加，逐漸降低各級信息素濃度，達到設定好的迭代次數時，停止信息素濃度的衰減，此時Q的值固定為常量，后續的迭代Q的值不再發生變化。動態衰減信息素濃度的策略，可以使算法在初期獲得較快收斂速度，逐漸降低的信息素濃度可以保證算法不陷入局部最優問題。

結合以上兩點改進的動態分級信息素濃度Q的設置如下，見公式（3）。

公式（3）中：Q1、Q2、Q3、Q4分別是各級信息素濃度的初始值；length是每代的最短路徑；iter是迭代的次數；k1、k2、k3是每次迭代后各級信息素濃度的衰減系數。當迭代次數超過50次后，信息素濃度Q就為固定值。

這種方式，達到了加快收斂速度的目的，也能避免因為信息素濃度突然增加，導致算法容易陷入局部最優的情況。

3.3 引入懲罰系數

當算法迭代多次以后，相對優秀的路徑上的信息素濃度會遠高于其他較差的路徑上的濃度，使算法隨機性大大降低，不利于尋找更優的路徑。為解決這一問題，引入了懲罰系數ε，當算法迭代到K代以后，判斷當前最優路徑L代未發生變化，下一次更新信息素時，將當前最優路徑上的信息素濃度衰減。信息素衰減公式，如公式（4）所示。

3.4 蟻群算法相關參數

蟻群算法中，參數的選取影響收斂速度和尋優結果，主要涉及的參數有螞蟻數量、信息素揮發系數ρ、信息素啟發因子α與期望啟發因子β、迭代次數。具體分析如下：

（1）蟻群大小。蟻群大小直接影響搜索效率，蟻群數量過小，無法遍歷全地圖獲取全局最優路徑。

（2）揮發系數。信息素是螞蟻在走過的路徑上留下的信息量之和，影響后面螞蟻的路徑選擇。隨著算法的迭代，路徑上的信息素會揮發。信息素揮發系數對收斂速度和尋優能力起主要影響。揮發系數變大，算法的收斂速度加快，搜索能力降低；揮發系數減小，算法收斂速度減慢，搜索能力提高。

（3）信息素啟發因子α與期望啟發因子β。信息素啟發因子表示信息素濃度對選擇路徑的影響大小；期望啟發因子表示路徑長度對路徑選擇的影響。α影響蟻群選擇之前走過路徑的概率，β影響算法的搜索效率。

（4）迭代次數。迭代次數過小，會導致算法提前結束，求解結果不理想。迭代次數過大會使算法效率降低，影響求解速度。

4 實驗仿真與分析

基于以上分析，在20×20的柵格地圖中進行實驗仿真分析。對于本文算法公式中出現的參數進行賦值：每一次迭代螞蟻的數量M為50只；最大迭代次數為100次；信息素啟發因子α為1，期望啟發因子β為7；信息素揮發系數ρ為0.3；動態分級信息素濃度Q中，Q1、Q2、Q3、Q4分別為2.5、2、1.5、1；啟用懲罰系數的迭代次數K為30，最優路徑連續未改變的次數L為5次，懲罰系數ε為2。仿真結果如圖7所示。

圖7 兩種蟻群算法仿真結果

表1記錄了傳統蟻群算法和本文算法最優路徑長度，以及第一次出現最優路徑的迭代次數，來進行比較。

表1 算法對比

從仿真結果來看，兩種蟻群算法都能對路徑進行規劃，但與傳統蟻群算法相比，本文算法具有更強的路徑規劃能力，在路徑長度上有較強的優化效果。

從圖8兩種蟻群算法的收斂曲線來看，與傳統蟻群算法相比，本文算法具有更快的收斂速度，對于迭代次數也有很好的優化能力。

圖8 兩種蟻群算法收斂曲線

5 結語

本文針對移動機器人路徑規劃問題，提出了一種改進的蟻群算法。將傳統蟻群算法中固定的信息素濃度，改進為動態分級的信息素濃度，達到了加速收斂的目的。引入了后退策略來避免螞蟻陷入死鎖導致的算法失效。通過修正策略，對螞蟻搜索路徑過程中存在的一些路徑行為進行修正，縮短了路徑距離。通過設置懲罰函數，來提高提高算法運行到中后期的隨機性避免陷入局部最優，影響算法的搜索結果。仿真數據顯示：本文所提出的改進的蟻群算法，在路徑長度的優化以及迭代次數的優化方面都具有不錯的效果，具有良好的全局搜索效果。