多策略蟻群算法在機器人路徑規劃中的應用

劉雙雙，黃宜慶

1.安徽工程大學 高端裝備感知與智能控制教育部重點實驗室，安徽 蕪湖 241000

2.安徽工程大學 安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000

路徑規劃[1]指的是在環境中具有若干障礙物時，從起點開始，規劃出一條到終點的有效安全路徑，該路徑需要具有轉折點少、長度短等特點。目前使用的規劃方法有A*算法[2]、人工勢場法[3]、粒子群算法[4]、遺傳算法[5]、蟻群算法[6]、深度強化學習[7-8]等。

蟻群算法因其具有較好的環境適應性和魯棒性且便于融合其他算法的優點而廣受關注。但蟻群算法隨機性較強，易發生陷入死鎖、規劃路徑非最優以及收斂較慢等問題。針對這些問題，不少學者也提出了相關優化方案。文獻[9]中設置了一個菱形區域，并增加其內部的初始信息素含量來提高算法前期搜索效率，但是菱形區域內的信息素濃度沒有區別，提高效果有限，且其獎懲策略會降低解的多樣性影響得到最優解。文獻[10]中增大了螞蟻的視野范圍，增加螞蟻可行節點數來減少路徑長度，但是螞蟻的可行節點數量過多會增加算法的不確定性，且運行環境單一，未體現出算法的適應能力。文獻[11]先是用基本蟻群算法得到全局路徑后，根據全局路徑外擴一定空間再利用蟻群算法尋找局部路徑最優路徑，若局部尋優得到路徑更短，則更新該路徑信息素，該方法雖增大了找到最優路徑的概率，但是由于外擴空間的局限性依舊會陷入局部最優。文獻[12]擴大了螞蟻搜索范圍，用向量夾角作為啟發信息并引入了轉移概率控制參數，雖然提升了算法的尋優性和收斂性，但是算法最終得到的路徑并非最佳。文獻[13]構建了全局優選區域，提高該區域初始信息素指導蟻群初期搜索，利用局部分塊優化策略更新信息素，引入了信息素增強因子和反向學習策略，算法屬性雖提升卻有限，且有的路徑出現回折情況。文獻[14]將信息素釋放在路徑節點上，用先驗方位引導策略和交替雙向引導策略來提高蟻群探索能力和速度，有效提升算法對復雜障礙物分布大規模地圖的求解能力，但算法結構的復雜度較大。

本文針對柵格環境下的路徑規劃問題提出一種新的改進方法，首先利用經過加權處理的A*算法啟發函數對初始信息素進行非均勻化處理，使得算法前期的螞蟻擁有一定的方向分辨性，減少無效搜尋；采用定向鄰域擴展策略，擴大螞蟻的方向選擇性，提高搜索效率并縮短路徑長度；在狀態轉移概率中增加角度引導因子以及障礙物影響因子，前者增大目的點的引導能力，加快算法中解的建立速度，后者為降低螞蟻陷入死鎖以及因下一步路徑點選擇不當而出現的曲折路徑的概率；在更新信息素時，利用雙重精英思想更新最佳路徑上的信息素含量，加大螞蟻找到最佳路徑的可能，同時也可以加快迭代的收斂。

1 問題描述

1.1 環境模型的建立

為了在地圖上體現出環境的相關特征，從而更加合理有效地規劃出路徑，對相關環境地圖柵格化處理。其中，障礙物用黑色柵格表示，自由區域用白色柵格表示。首先，對環境中存在的障礙物，以機器人的尺寸半徑將障礙物向外膨脹一定距離，如圖1（a）所示，黑色三角形表示障礙物的原始狀態，灰色表示膨化部分。之后將地圖柵格化，若出現部分柵格中存在障礙物未占滿整個柵格的情況，為便于算法運行，也將其認為是障礙柵格，如圖1（b）。

圖1 障礙物膨脹示意圖Fig.1 Schematic diagram of obstacle expansion

在靜態的柵格地圖中，采用蟻群算法規劃路徑時，先輸入地圖環境矩陣。其中，矩陣中元素1表示障礙柵格，元素0表示空白柵格，可讓機器人通行。柵格的編碼順序為：由最上行最左列編號為1開始，向右依次編號到達邊界后，再對下一行按照從左到右的順序繼續編碼，直至每個柵格都有自己的序號為止。將地圖左下角設為原點O，橫坐標由左向右依次增大，縱坐標由下到上依次增大。柵格坐標和序號的對應關系如式（1）所示：

其中，x為柵格中心點的橫坐標，y為其縱坐標；a為柵格邊長，設為1 m；i表示柵格序號；MM表示地圖中柵格的行數；mod()為求余函數，ceil()為向上取整函數。

1.2 原始蟻群算法

學者從自然中螞蟻尋找食物的過程獲得了靈感，創造出了蟻群算法。其原理是在尋找食物的過程中，螞蟻在走過的路徑上會釋放信息素，后續的其他螞蟻會比較各路徑上的信息素量，傾向選擇信息素更高的路徑。

原始蟻群算法中，采用狀態轉移公式進行路徑選擇，該公式為：

在算法中，螞蟻在走過的路徑上遺留一定量的信息素，同時，路徑上先前存在的信息素也會不斷地蒸發消失，如此，信息素在越短的路徑上越多，最佳路徑被螞蟻找到的可能性越大。此過程中，需要不斷地更新信息素，更新方法為：

式中，τij(t+1)為更新后的路徑(i,j)信息素濃度；ρ是信息素揮發系數，n是螞蟻數目，Q是信息素增量，為一常數值；Lm為螞蟻m所走的路徑長度。

2 多策略蟻群算法

2.1 初始信息素非均勻化分布策略

在求解過程中，螞蟻進行路徑選擇的主要依據之一是柵格間路徑的信息素含量多寡。原始蟻群算法中，各柵格間路徑的初始信息素分布均勻，為一個常數值。在算法初期，螞蟻的啟發函數值將決定狀態轉移概率的大小，依其計算方法可知，不同柵格的啟發函數值差異很小，在沒有信息素引導的情況下，螞蟻搜索的盲目性大，搜索所得解的質量低，收斂速度慢。對柵格間路徑的初始信息素進行非均勻化處理，有利于提升解的質量和加快算法的收斂速度。采用A*算法的啟發函數思想，差異化處理不同柵格間路徑的信息素，根據其在地圖中的坐標賦予相應的信息素濃度，計算過程如下：

式（5）中，τ0為原初始信息素值，Δτij為另外在(i,j)路徑添加的信息素；式（6）中，c為常數值，根據經驗值以及柵格規模取值，f(i)和f(j)由式（7）計算得到；式（7）中，ε為加權值，g(x)為起點和當前點的間距，h(x)為當前點和終點的間距。

依據兩點之間直線最短的距離可知，螞蟻經過的路徑越靠近起終點連線，該路徑越優，當下一步待選柵格越靠近終點，路徑越優，因此，ε應取較小值使終點起主導作用。此外，為算法的整體效果考慮，非均勻信息素值差距若過大，會造成算法過早收斂導致局部最優問題的出現，若過小，則該策略所起作用有限。因此，多次對c和ε的取值進行實驗比較，確定最終取值為：c=2×4×4=32,ε=0.1。

2.2 定向鄰域擴展策略

在基于柵格地圖的原始算法中，螞蟻只能夠在其周圍的相鄰四個或者八個柵格選擇下一步路徑節點，搜索方向有限，因步長的限制所找到的最優路徑長度也較長。文獻[12]將螞蟻的搜索方向擴展到16個，將螞蟻的最小轉角降低到了22.5°，有效擴大螞蟻搜索范圍以及縮短路徑長度，但是也在某種程度上提高了算法的計算量。引入該擴展鄰域的思想，根據地圖起點和終點的相對位置，對鄰域進行定向擴展，如圖2所示。

圖2中，S為起點，E為終點，i表示機器人當前位置。實線代表原始蟻群算法的可行柵格，虛線代表定向鄰域擴展之后增加的可行柵格。采用定向鄰域擴展策略不但能夠豐富螞蟻的搜索方向，達到通過一次搜索找到更短路徑的目的，而且可以降低算法的計算量，加快算法的運行。由于改進算法中螞蟻的可搜索柵格范圍的增加，對螞蟻的搜索方式進行重設。

圖2 定向鄰域擴展后的可行柵格Fig.2 Feasible grid after directional neighborhood expansion

在當前柵格的周圍八個柵格中，螞蟻不可選擇障礙柵格作為下一步的移動路徑節點，在擴展得到的鄰域柵格中，螞蟻移動規則如下：若A或者C柵格中至少存在一個障礙柵格，螞蟻不可從當前節點I直接移動到節點D；若B或者C柵格中至少存在一個障礙柵格，螞蟻不可從當前節點I直接移動到節點J；若C柵格是障礙柵格，螞蟻不可從當前節點I直接移動到節點K。如圖3，C為障礙柵格，則螞蟻無法從I直接移動到節點D、J、K中的任一節點。

圖3 定向擴展鄰域移動情況分析Fig.3 Analysis of directional expansionneighborhood movement

2.3 狀態轉移概率公式改進策略

2.3.1 角度引導因子

在原始蟻群算法中，狀態轉移公式主要由啟發函數和信息素含量兩者組成。在算法初期，由于相鄰柵格和終點之間的距離差異不明顯，螞蟻往往無法做出正確的選擇導致解的質量差，搜索到最優路徑的速度較慢。引入角度引導因子，可有效增加終點坐標對螞蟻的引導作用，在保證螞蟻具有足夠大的搜索范圍情況下，驅動螞蟻向較佳方向進行搜索，使得螞蟻可以更快到達終點。

角度引導因子定義：i為螞蟻的當前柵格，其坐標為(ix,iy)；j為下一步可以到達的柵格，坐標為(jx,jy)；E為終點柵格，坐標為(Ex,Ey)。θij=∠jiE為角度引導因子中的角度，該角度的范圍為[ ]0,180°。由于角度差值較大會影響狀態轉移公式計算，因此取角度的余弦值進行歸一化處理后作為角度引導因子[12]νij，定義為：

角度引導因子νij的函數變化圖像如圖4所示，角度影響因子值越接近1，說明螞蟻下一步前進方向越貼近理想搜索方向，搜索效果越好。

圖4 角度引導因子變化趨勢Fig.4 Change trend of angle guidance factor

2.3.2 障礙物影響因子

在路徑規劃中，障礙物的位置和分布情況也會對路徑尋優產生極大的影響，原始蟻群算法并未對障礙物造成的影響進行分析并做出對應策略。如圖5，令螞蟻下一步潛在移動節點為j，若柵格4、5、6為障礙柵格，則會造成路徑曲折；若柵格j周圍柵格存在連續6個柵格為障礙柵格，則會極大增加螞蟻陷入死鎖的概率。一些改進算法從人工勢場算法中得到啟發，將障礙物斥力思想引入算法中，得到了很好的規劃效果。為防止曲折路徑和死鎖的發生，引入障礙物影響因子Oifj(t)定義如下：

圖5 障礙物影響因子設定示意圖Fig.5 Schematic diagram of obstacle impact factor setting

障礙物影響因子的引入可有效降低路徑曲折的概率，有效避免螞蟻陷入死鎖情況的發生，使得算法規劃得到的路徑更合理。

綜上所述，在原始蟻群算法的基礎上增加角度引導因子和障礙物影響因子，計算如式（8）～（10）所示，改進后的狀態轉移概率為

式中，除原始蟻群算法相關參數含義不變外，νij(t)表示t時刻的角度引導因子，γ為其重要程度；Oifj(t)表示t時刻的障礙物影響因子，δ為其重要程度。

2.4 雙層精英蟻信息素更新策略

所有路徑上的信息素部分揮發過程和螞蟻在走過的路上留下新的信息素過程共同構成了信息素更新。但是原始蟻群算法中，算法中后期由于各路徑長度差異不大，可能會出現不同長度路徑上具有大致相同的信息素濃度，導致算法尋優速度過慢或者無法搜尋到最佳路徑。為解決該問題，引入精英思想[15]，對每次迭代過程中的最優路徑額外增加部分信息素，增強該路徑對后面螞蟻的引導作用。同時，該思想的引入有可能會造成算法收斂震蕩，即因蟻群算法的隨機性較強，會出現前一次迭代已經找到最優路徑，但是因部分螞蟻在一些次優路徑片段上留下的信息素濃度疊加后高于最優路徑，后一次迭代陷入局部最優，此類情況反復出現造成收斂震蕩。為此，再次引入精英思想，對本次迭代最佳路徑和歷史迭代中的最佳路徑進行長度對比，若前者長于后者，則加大歷史最佳路徑上的信息素含量。根據該信息素更新法的特點，將其稱為雙層精英蟻信息素更新策略，計算如下式：

3 改進算法的執行步驟

步驟1建立柵格地圖的0-1矩陣，確定螞蟻起點柵格S和終點柵格E；將算法中所有參數初始化：迭代次數K，單次迭代螞蟻數量M，啟發因子β，信息素因子α，信息素揮發因子ρ，信息素初始值τ0，信息素強度值Q、Q1以及Q2。

步驟2利用加權處理的A*啟發函數對初始信息素值進行非均勻處理，根據公式（6）、（7）計算每段柵格路徑的信息素增量Δτij，根據式（5）計算出柵格地圖的信息素初始值τij(0)。

步驟3將M只螞蟻放在起點柵格S中，首先將每只螞蟻的禁忌表清零，設置路徑點集合為空，路徑長度為零。將起點加入禁忌表，根據起始點相對位置在當前柵格位置進行定向鄰域擴展，根據式（8）～（10）計算下一步可行柵格點的角度引導因子及障礙物影響因子。

步驟4根據式（11）算出下一步每個可行柵格的狀態轉移概率，利用輪盤賭策略確定螞蟻下一步柵格，更新該螞蟻的禁忌表。

步驟5判斷螞蟻有無到達終點。若沒有到達終點，則返回執行步驟3和步驟4，直到螞蟻到達終點，否則執行步驟6。

步驟6當該次迭代中所有螞蟻均完成搜索后，利用雙層精英蟻信息素更新策略對所有成功抵達終點的螞蟻經過的路徑更新信息素。

步驟7判斷迭代次數是否等于最大次數K，若等于，則輸出最優路徑及迭代曲線，若不等于，將迭代次數加1，再次執行步驟3到步驟6。

算法流程圖如圖6所示。

圖6 算法流程圖Fig.6 Flow chart of proposed algorithm

4 仿真實驗及分析

通過仿真實驗對本文改進蟻群算法的相關性能進行驗證分析，選取障礙物分布不同的20×20和30×30的柵格地圖各兩個，對本文的多策略蟻群算法進行仿真，并且與原始蟻群算法以及其他的改進算法對比。仿真實驗所需的運行環境：操作系統Windows 10（64位），處理器Inter?CoreTMi5-7200U，CPU 2.5 GHz，內存12 GB，仿真平臺Matlab R2018a。

4.1 算法仿真參數的選取

蟻群算法中各參數的設值對算法性能影響頗大，為得到合理的參數值組合，采用試湊法對多組參數進行實驗對比，選擇較優值作為實驗用值。本文依據經驗法對算法中的主要參數在其變化范圍內分別取5個不同的值，以一組默認參數組合為基準，每次只改變其中一個參數的值，為保證參數的合理性，進行10次仿真取平均值作為最終結果，仿真環境為障礙分布相同的20×20柵格地圖。通過對實驗結果的對比，取每個參數的最優值作為本文實驗的參數參考值。

默認參數組合：α=1,β=1,γ=3,δ=3,ρ=0.4。各參數變化值：α∈{0.5,1,1.5,2,2.5},β∈{0.5,1,1.5,2,2.5},γ∈{1 ,3,5,7,9},δ∈{1 ,2,3,4,5},ρ∈{0.2,0.4,0.6,0.7,0.8}。實驗中每次只改變一個參數值，其他參數值為默認值，所得實驗結果如表1。

由表1可知：α的最優值在1附近，β的最優值在1附近，γ的最優值在5附近，δ的最優值在3附近，ρ的最優值在0.6附近。

表1 主要參數測試實驗結果Table 1 Test results of main parameters

Q為基礎信息素強度，設為基礎值1，Q1和Q2是在最優路徑額外增加的信息素強度，經多次實驗驗證，Q1=1.2,Q2=4為宜，算法收斂速度較快且局部最優概率低。算法的具體參數設置如表2所示。

表2 仿真參數參考值Table 2 Reference value of simulation parameters

4.2 20×20柵格地圖仿真實驗

分別采用文獻[13]和文獻[16]中規格為20×20的兩個障礙物分布不同的柵格地圖中，對原始蟻群算法和本文的多策略蟻群算法進行仿真，并與文獻[13]和文獻[16]中的相關改進算法仿真結果進行對比。

4.2.1 與文獻[13]算法和原始蟻群算法仿真對比

采用文獻[13]的柵格環境，利用原始蟻群算法及本文改進算法進行仿真實驗，結果如圖7所示，與文獻[13]的數據對比如表3所示。

圖7 算法仿真結果對比圖Fig.7 Comparison of algorithm simulation results

表3 算法仿真結果數據對比Table 3 Comparison of algorithm simulation results data

由表3可知，原始蟻群算法的路徑長為29.455 8 m，文獻[13]算法的路徑長為28.038 0 m，本文的多策略蟻群算法的路徑長為27.685 4 m，相較前兩種算法，本文算法所得路徑更短更平滑，在迭代收斂方面，本文算法只需8次即可收斂于全局最優路徑，優于原始蟻群算法的30次和文獻[13]算法的12次，在局部最優方面，原始蟻群算法在尋找到最優路徑后依舊收斂于局部最優解，而本文由于雙層精英蟻策略并未發生此類情況。由仿真結果對比得出，多策略蟻群算法的尋優性和收斂性更好。

4.2.2 與文獻[16]算法和原始蟻群算法仿真對比

采用文獻[16]的相應柵格地圖再次進行仿真比較以驗證算法的環境適應能力，結果如圖8所示，路徑規劃仿真數據對比如表4所示。

圖8 算法仿真結果對比圖Fig.8 Comparison of algorithm simulation results

表4 算法仿真結果數據對比Table 4 Comparison of algorithm simulation results data

由表4可得，本文的多策略蟻群算法的路徑收斂長度小于其他兩種算法所得路徑長度，迭代收斂速度高于原始蟻群算法及文獻[16]算法，僅在拐點個數上由于移動規則和障礙物分布的原因，略高于另兩者算法。因此，本文算法的尋優性較其他算法，有很大的改善，且收斂更快。

4.3 30×30柵格地圖仿真實驗

擴大柵格地圖的規模，分別采用文獻[13]和文獻[12]提供的30×30柵格地圖進行路徑規劃。同時，與原始蟻群算法和相應柵格地圖的文獻改進算法進行對比。

4.3.1 與文獻[13]算法和原始蟻群算法仿真對比

采用文獻[13]中的30×30規模的柵格地圖，利用原始蟻群算法和本文算法進行路徑規劃，如圖9所示，并與文獻[13]算法所得仿真結果進行數據對比，如表5。

表5 算法仿真結果數據對比Table 5 Comparison of algorithm simulation results data

根據圖9的對比圖可知，與原始蟻群算法比較，本文算法在路徑尋優方面以及收斂性方面都有了很大的提升。原始蟻群算法會出現路徑曲折的問題導致路徑長度加長以及轉折角過小導致路徑平滑度低的情況，而本文的多策略蟻群算法并沒有此類情況。根據表5的仿真數據對比可知，多策略蟻群算法得到的收斂路徑長度為42.464 6 m，小于其他兩種對比算法的45.598 0 m和43.592 0 m，收斂速度也是最快的，僅需要11次即可收斂于最優路徑，在拐點方面，本文算法得到11個拐點，少于原始蟻群算法拐點數14個，多于文獻[13]算法的8個拐點，路徑平滑度也具有一定的改善。從綜合指標方面考慮，在30×30柵格地圖中，本文的多策略蟻群算法也具有較好效果。

圖9 算法仿真結果對比圖Fig.9 Comparison of algorithm simulation results

4.3.2 與文獻[12]算法和原始蟻群算法仿真對比

根據文獻[12]中的30×30柵格地圖，利用本文多策略蟻群算法和原始蟻群算法比較仿真結果，如圖10所示。同時，選取文獻[12]算法中路徑長度為最優值的仿真結果作數據對比，如表6所示。

圖10 算法仿真結果對比圖Fig.10 Comparison of algorithm simulation results

表6 算法仿真結果數據對比Table 6 Comparison of algorithm simulation results data

為進一步和文獻[12]算法進行對比以驗證本文算法優越性，在該柵格地圖中利用本文算法共進行10次仿真實驗，本文多策略蟻群算法迭代過程如圖11所示。其相關數據對比如表7。

圖11 10次仿真結果迭代圖Fig.11 10 iterations of simulation results

由表6中數據可知，文獻[12]算法和本文的多策略蟻群算法的各項指標均優于原始蟻群算法。從表7可知，本文算法搜索得到的最優路徑長度為43.509 4 m，小于文獻[12]算法的最優路徑長度43.865 7 m。并且，本文算法10次仿真中搜索得到的所有路徑長度均不大于文獻[12]算法的任何一次仿真路徑長度，其平均路徑長度和平均迭代次數也都優于文獻[12]中提出的算法。因此，該對比結果再一次地驗證了本文的多策略蟻群算法具有較強的尋優能力和收斂能力。

表7 10次迭代仿真數據對比Table 7 Comparison of simulation data of 10 iterations

5 結束語

針對原始蟻群算法在較復雜環境中容易陷入次優路徑，找尋不到最優路徑，搜索得到的路徑因螞蟻的移動規則束縛導致過長以及收斂過慢等問題，提出多策略蟻群算法。首先依據柵格所在位置利用加權的A*啟發函數進行計算，額外增加該柵格的初始信息素，提高算法收斂速度；其次，利用定向鄰域擴展策略增加螞蟻的可行柵格數量，加快螞蟻向終點搜索的速度；之后，利用角度引導因子和障礙物影響因子改進狀態轉移概率公式，驅使螞蟻向有效方向進行搜索并減少曲折路徑和死鎖螞蟻出現的概率；最后，采用二次精英蟻策略對路徑上的信息素進行更新，加強較優路徑對螞蟻的引導作用，提高螞蟻的全局搜尋能力，避免局部最優的產生。仿真實驗結果表明，本文找到最佳路徑所需的迭代次數更少，即收斂更快，找到的路徑更短，即尋優性更好。