基于改進蟻群算法的機器人路徑規(guī)劃研究

摘 ?要：在將蟻群算法應用于機器人路徑規(guī)劃時，針對如何調節(jié)收斂速度與種群多樣性之間矛盾的問題，提出了改進的蟻群算法。在狀態(tài)轉移規(guī)則中，引入防死鎖因子，改進啟發(fā)函數，提升收斂效率;在信息素更新過程中，提出一種全局信息素分步更新策略;在整體結構上，提出了多層并行蟻群模型，極大縮減了整體運行時間。改進的蟻群算法可保持種群多樣性與收斂速度之間的一種平衡。

關鍵詞：機器人;蟻群算法;路徑規(guī)劃;種群多樣性;收斂速度

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2096-4706（2021）12-0018-05

Abstract： When applying ant colony algorithm to robot path planning， an improved ant colony algorithm is proposed to solve the problem of adjusting the contradiction between convergence speed and population diversity. In the state transition rule， the anti deadlock factor is introduced to improve the heuristic function and improve the convergence efficiency; in the process of pheromone updating， a global pheromone step-by-step updating strategy is proposed; in the overall structure， a multi-layer parallel ant colony model is proposed， which greatly reduces the overall running time. The improved ant colony algorithm can maintain a balance between population diversity and convergence speed.

Keywords： robot; ant colony algorithm; path planning; population diversity; convergence speed

0 ?引 ?言

隨著新興技術產業(yè)的快速發(fā)展，移動機器人路徑規(guī)劃研究已成為移動機器人技術研究的重中之重。在移動機器人自動導航過程中，有效的路徑規(guī)劃可以幫助移動機器人避開工作場所中的障礙，縮短途經路徑的長度。蟻群算法是一種啟發(fā)算法，在解決移動機器人路徑規(guī)劃問題上有著良好的魯棒性與并行性，目前有很多學者將其廣泛應用于解決路徑規(guī)劃的問題中。王曉燕等[1]提出了一種根據柵格位置不均衡性分配初始信息素的方法。許凱波等[2]提出了一種基于信息素二次更新策略的雙蟻群算法，提升了尋優(yōu)能力，但卻導致運行時間的增加。王秀繁等[3]將粒子群算法與蟻群算法相融合，提出了一種解決物流配送路徑規(guī)劃問題的算法。羅艷媚等[4]將人工勢場法與蟻群算法相融合，提出了一種新算法。其他算法與蟻群算法相融合的方法雖然提高了路徑搜索效率，但是運行時間較長、算法結構較復雜。大多數學者在平衡蟻群算法的多樣性與收斂速度、優(yōu)化算法架構等方面的研究較少。因此，本文作者設計了一種改進的多層運行蟻群算法，從狀態(tài)轉移規(guī)則、信息素更新策略、蟻群算法整體結構等多個方面來平衡蟻群算法的收斂速度與種群多樣性兩者之間的矛盾。

1 ?柵格法環(huán)境建模

在對移動機器人路徑進行規(guī)劃時，需要先完成對移動機器人行駛環(huán)境的建立。本文采用柵格法中的直角坐標法對移動機器人所在的工作場所構建二維模型，將移動機器人可選擇的柵格顏色設置為白色，將移動機器人不可經過、不可選擇的柵格顏色設置為黑色，稱為障礙柵格，從而得到與移動機器人行駛環(huán)境相似的柵格地圖，如圖1所示。

2 ?改進的蟻群算法在機器人路徑規(guī)劃中的應用

蟻群算法是由Dorigo、Maniezzo等人提出的，主要用于尋求最優(yōu)路徑，基本思路是：相關參數的初始化，取得可行路徑、構建可行路徑空間，更新信息素，是否滿足終止條件，得到最優(yōu)路徑。

2.1 ?初始化

在蟻群算法中，相關參數的初始化設定為：

M為種群規(guī)模，即種群中螞蟻數量，選取時需要考慮算法的收斂速度與全局搜索能力，取值為10～50。

G為最大迭代次數，即螞蟻遍歷次數，一般為算法的終止條件，取值為100～500。

Q為蟻群循環(huán)一次后釋放的信息素總量，受算法正反饋機制的影響，取值為1～100。

ρ為信息素的揮發(fā)系數，其取值對算法的搜索力與收斂能力都有影響，取值為0～1。

α為信息啟發(fā)式因子，其取值影響螞蟻對信息素的反應能力，取值越大，螞蟻對信息素的反應能力越強，取值為0～2。

β為期望啟發(fā)式因子，其取值影響螞蟻對起點、終點、路徑長度的反應能力，取值為0～20。

2.2 ?改進的狀態(tài)轉移規(guī)則

在基本蟻群算法中，由于螞蟻在搜索路徑過程中只能前進不能后退，當遇到障礙物或者是之前已經走過的節(jié)點時，會陷入死鎖狀態(tài)，發(fā)生停滯。為此，引入防死鎖因子Sj：

其中，Sj為節(jié)點j的防死鎖因子，Gj為節(jié)點j相鄰的柵格總數量，Bj為與節(jié)點j相鄰的障礙柵格數量，Lj為螞蟻之前走過的且與節(jié)點j相鄰的柵格數量。防死鎖因子的引入，可以讓螞蟻在搜索過程中有效避開障礙物或是之前已經走過的節(jié)點，降低死鎖概率。

與此同時，基本算法的啟發(fā)函數僅涉及了當前節(jié)點與下一節(jié)點之間的距離，并沒有考慮與起點、終點的距離，這樣也容易導致螞蟻在選擇下一節(jié)點時陷入死鎖狀態(tài)，被迫停止搜索，為此，改進啟發(fā)函數ηij：

其中，daj表示t時刻，起點a與下一節(jié)點j之間的距離， daj= ，（xi，yi）為當前節(jié)點i的位置坐標，（xa，ya）為起點a的位置坐標;dij表示t時刻，當前節(jié)點i與下一節(jié)點j之間的距離;djz表示t時刻，下一節(jié)點j與終點z之間的距離;改進的啟發(fā)函數不僅涉及了當前節(jié)點與下一節(jié)點之間的距離，還涉及了與起點、終點的距離，使得螞蟻在選擇下一節(jié)點時遠離起點，向終點靠近。

引入防死鎖因子，改進啟發(fā)函數后，得到新的狀態(tài)轉移概率公式：

其中，τij（t）表示t時刻，兩節(jié)點（i，j）之間的信息素濃度;ηij（t）表示t時刻，節(jié)點i選擇節(jié)點j的啟發(fā)函數;Sj為防死鎖因子，allowk表示節(jié)點i可選擇的下一節(jié)點的集合;改進的狀態(tài)轉移規(guī)則降低了螞蟻選擇障礙物柵格節(jié)點與之前已經過的節(jié)點的概率，減少了探索時間，提高了整體的收斂效率，但并沒有減弱種群的多樣性，使得收斂效率與種群多樣性之間保持較好的平衡關系。

2.3 ?信息素更新

在基本的蟻群算法中，信息素的更新主要是對從起點到終點的整條路徑進行信息素濃度的增加，容易陷入局部最優(yōu)[5]。

本文提出了一種全局信息素分步更新策略。將最大迭代次數設為N，在前面的N/2次迭代過程中，任何螞蟻都不釋放信息素，充分保證螞蟻對最優(yōu)路徑的探索，保持了種群多樣性;在之后的N/2次迭代過程中，每次迭代皆對螞蟻構建的所有路徑進行排序，并按照路徑的優(yōu)劣實施不同程度的信息素獎勵政策，并記錄每條路徑出現(xiàn)次數，當該路徑出現(xiàn)次數達到一定數值后，該條路徑不再更新，從而避免出現(xiàn)局部最優(yōu)現(xiàn)象。具體公式為：

其中，n為當前迭代次數，N為最大迭代次數;ρ為螞蟻遺留在路徑上信息素的蒸發(fā)系數;?τij表示螞蟻走完整條路徑后信息素的變化量，主要是增加量;Lk表示第k只螞蟻所走的整條路徑的長度。改進的全局信息素分步更新策略，在迭代前期使所有螞蟻盡可能地搜索所有路徑，保證了螞蟻的探索力與種群的多樣性，在迭代后期，采用全局信息素更新策略，提高了收斂效率，并且引入了當前最優(yōu)路徑次數記錄動作，防止出現(xiàn)局部最優(yōu)。

2.4 ?單層蟻群算法的終止條件

單層蟻群算法的終止主要依靠迭代次數是否已為最大迭代次數，若蟻群迭代次數未達到最大迭代次數，則進入下次搜索;反之，結束搜索，輸出本層的最優(yōu)路線。

2.5 ?算法結構

建立多層并行蟻群模型。在m層并行蟻群模型中，每一層都是一個完整的蟻群算法運算，將每層蟻群算法得到的最優(yōu)路徑進行比較，從中選出最優(yōu)路徑，該模型將多個蟻群算法依次運算的時間總和縮短為單個蟻群算法運行時間，極大縮減了得到最優(yōu)解的整體運行時間，提高了整體運行效率。改進的蟻群算法如圖2所示。

3 ?仿真及結果分析

為了比較改進的蟻群算法與基本蟻群算法，在兩種不同復雜程度的柵格環(huán)境，即分別在10×10簡單柵格地圖環(huán)境、20×20復雜柵格地圖環(huán)境下從收斂迭代次數、行走路線、最優(yōu)路徑長度等角度對兩種算法進行對比分析，如圖3、表2所示。使用MATLAB R2016a仿真平臺，相關參數設置如表1所示。

通過圖3與表2的對比可知，在10×10簡單柵格地圖環(huán)境下，本文改進的蟻群算法在尋求最優(yōu)路徑、迭代次數等方面得出的結果皆優(yōu)于基本蟻群算法。

20×20柵格地圖環(huán)境不僅增加了柵格規(guī)模，還增加了障礙物數量，提高了障礙物分布密度，地圖環(huán)境復雜，如圖4、表3所示。

通過圖4與表3的對比可知，在20×20復雜柵格地圖環(huán)境下，改進蟻群算法尋求的最優(yōu)路徑優(yōu)于基本蟻群算法尋求的最優(yōu)路徑。

4 ?結 ?論

由于基本的蟻群算法應用于移動機器人路徑規(guī)劃時，易出現(xiàn)搜索死鎖、收斂速度與種群多樣性之間的矛盾，本文從狀態(tài)轉移規(guī)則、信息素更新策略、算法整體運行模型多個角度進行了研究，提出了一種多層并行運行的蟻群算法。對兩種算法進行仿真比較分析，結果表明改進的蟻群算法可有效地防死鎖，并且極好地建立了種群多樣性與收斂速度之間的一種平衡，在迭代次數、最優(yōu)路徑長度等方面都有較大的提升。

參考文獻：

[1] 王曉燕，楊樂，張宇，等.基于改進勢場蟻群算法的機器人路徑規(guī)劃 [J].控制與決策，2018，33（10）：1775-1781.

[2] 許凱波，魯海燕，黃洋，等.基于雙層蟻群算法和動態(tài)環(huán)境的機器人路徑規(guī)劃方法 [J].電子學報，2019，47（10）：2166-2176.

[3] 王秀繁，梁峰.基于PSO-ACO融合算法的物流車輛路徑優(yōu)化與控制研究（英文） [J].機床與液壓，2020，48（12）：155-160.

[4] 羅艷媚.一種求解多目標優(yōu)化問題的改進蟻群算法 [J].電腦知識與技術，2020，16（32）：226-229.

[5] 李毅，胡建成.改進的蟻群優(yōu)化算法在機器人路徑規(guī)劃中的應用 [J].內江師范學院學報，2019，34（12）：40-44.

作者簡介：張丹丹（1990—），女，漢族，山東德州人，助教，碩士，研究方向：物流信息技術、智能優(yōu)化算法。