基于變步長蟻群算法的移動機器人路徑規(guī)劃

徐玉瓊，婁柯，李志錕

（1. 廣州大學松田學院 電氣與汽車工程系，廣東 廣州 511370; 2. 高端裝備先進感知與智能控制教育部重點實驗室，安徽 蕪湖 241000; 3. 安徽工程大學 安徽省電氣傳動與控制重點實驗室，安徽 蕪湖 241000）

在移動機器人領域，路徑規(guī)劃技術一直都是重要研究內容，其任務是在地圖環(huán)境中為移動機器人從起點至終點避開障礙物而規(guī)劃出的最優(yōu)路徑。目前國內外學者針對路徑規(guī)劃技術做了諸多研究，并取得相應成果，常用的傳統(tǒng)路徑規(guī)劃算法有遺傳算法、模擬退火算法、人工勢場法、A*算法[1]等。隨著人工智能技術的高速發(fā)展，群智能算法在路徑規(guī)劃技術中得到廣泛應用和發(fā)展，如人工魚群算法、蜂群算法、蟻群算法[2-4]、蛙跳算法等，人工魚群算法是一種擅長隨機搜索的算法，其算法原理簡單，對初始值要求較低，但在算法后期存在收斂速率緩慢、計算結果不夠精確。蜂群算法作為模仿蜜蜂行為提出的啟發(fā)式算法，通過對單一的蜜蜂進行局部尋優(yōu)，突出全局最優(yōu)值，容易陷入局部最優(yōu)，其算法魯棒性不強。傳統(tǒng)的群智能算法已經無法滿足移動機器人在復雜環(huán)境下進行路徑規(guī)劃，因此，大量學者通過對傳統(tǒng)的群智能算法進行改進，如多策略人工魚群算法[5-7]、雙層蟻群算法[8]、啟發(fā)機制下的蟻群算法[9]等。改進的群智能算法已經明顯提高復雜環(huán)境下移動機器人的路徑規(guī)劃[10-15]能力。

蟻群算法作為啟發(fā)式全局優(yōu)化算法是由意大利學者Dorigo在1992年提出，該算法得益于采用正反饋機制，收斂性能大幅提升，通過分布式計算方式進行搜索以及不同個體同時并行計算，提高了該算法的運算效率以及計算能力，但仍存在收斂速度慢以及死鎖問題。因此，文獻[9]對蟻群算法進行改進，提出了基于啟發(fā)式機制的蟻群算法，該算法通過當前節(jié)點到終點的距離動態(tài)的調整啟發(fā)函數(shù)，當算法處于局部最優(yōu)時，引入懲罰函數(shù)機制，降低最優(yōu)路徑的信息素，減少蟻群算法的正反饋影響而跳出局部最優(yōu)。文獻[14]主要針對于蟻群算法收斂速度慢進行改進，合理分配信息素初始濃度，動態(tài)調整信息素揮發(fā)因子，進行二次路徑規(guī)劃，有效縮短了移動機器人的路徑長度。文獻[8]設計了雙層蟻群算法，對移動機器人二維柵格環(huán)境進行凸化處理，同時用外層蟻群探索出一條路徑作為一個小環(huán)境，內層蟻群在該環(huán)境下重新探索，兩條路徑擇優(yōu)篩選，提高蟻群算法路徑搜索質量。

為了提高蟻群算法收斂速度以及縮短路徑長度，本文提出變步長蟻群算法，尋找移動機器人可以達到的跳點，得到不同長度的路徑，根據(jù)路徑長度的不同，不均勻分配初始信息素濃度，以降低邊緣障礙物對移動機器人的影響，從而提高算法的計算能力。改進啟發(fā)式信息矩陣，提高蟻群避障能力，增強蟻群全局路徑搜索能力，快速找到最優(yōu)路徑。

1 蟻群算法原理

1.1 環(huán)境表示

移動機器人需要在二維空間環(huán)境下進行路徑規(guī)劃，因此，需要對移動機器人工作環(huán)境進行建模，常規(guī)環(huán)境建模方法如柵格圖法[16-18]、可視圖空間法、自由空間法、幾何信息法等。本文選取柵格圖法對移動機器人二維空間進行建模，將柵格分為黑色區(qū)域和白色區(qū)域，其中黑色區(qū)域為障礙物柵格，白色區(qū)域為自由柵格，機器人可以在白色區(qū)域自由移動，如圖1所示，假設每個柵格為邊長為1 m的正方形，不考慮機器人自身身高和體積的影響，機器人始終處于正方形的正中心位置。

圖 1 柵格地圖Fig. 1 Raster map

1.2 搜索方式

傳統(tǒng)蟻群算法中蟻群為單步長[19-20]移動方式，每步移動距離為1或個單元格，在不碰撞障礙物的情況下，可以向四周共8個方向移動，如圖2所示。

圖 2 移動方式Fig. 2 Moving method

蟻群在尋路過程中，利用信息素相互通信，在經過的路徑上釋放信息素，當某一條路徑通過的螞蟻越來越多時，該路徑的信息素濃度就越高，其他螞蟻選擇該路徑的概率就越大，起到正反饋作用，同時也容易陷入局部最優(yōu)及存在死鎖現(xiàn)象。信息素會隨著時間的增長而揮發(fā)，動態(tài)的調整各路徑的信息素濃度，螞蟻在選擇路徑時，會對信息素濃度、啟發(fā)因子、路徑方向等因素進行綜合判斷選擇下一步移動位置，并利用輪盤算法計算當前節(jié)點到下一到達節(jié)點的概率：

式中：τij為路徑(i,j) 上的信息素；ηij為位置i到位置j的啟發(fā)因子；ak為螞蟻k下一步可到達節(jié)點的集合；α 表征信息素重要程度；β表征啟發(fā)因子重要程度；dij是螞蟻從位置i到位置j構建的路徑長度。

為了避免螞蟻選擇已經達到過的節(jié)點，采用禁忌表記錄螞蟻k當前所達到過的位置，經過t時刻，所有螞蟻都已完成了一次路徑規(guī)劃，計算所有螞蟻完成的有效路徑長度，篩選出最短路徑長度，同時更新各路徑上的信息素，經過時間的增長，信息素將揮發(fā)一部分：

式中：ρ 是信息素揮發(fā)系數(shù)，同時，螞蟻也將在路徑中釋放信息素：

式中：Δτkij是第k只螞蟻在所經過的路徑上釋放的信息素，定義如下：

由式(5)可知，螞蟻所構建的路徑長度dij越小，那么各路徑將得到更多的信息素，在以后的迭 代中該路徑被其他螞蟻選擇的概率也將更大。

2 變步長蟻群算法

傳統(tǒng)蟻群算法步長選擇為單步長，蟻群僅能向相鄰柵格位置移動，不能滿足移動機器人實際需求，且搜索效率低及路徑長度無法滿足最優(yōu)，因此，本文提出變步長選擇策略，在避開障礙物的條件下，移動機器人可以從當前位置向全局地圖的任何位置移動，大幅提高移動機器人搜索效率。

2.1 步長選擇策略

跳點的選擇即步長的選擇，所謂跳點就是移動機器人在搜索過程中從當前節(jié)點可以到達下一步的節(jié)點。如圖3所示。移動機器人從起點到終點有4條路徑可供選擇，方案1為當前節(jié)點1跳躍至節(jié)點2再到終點3，節(jié)點1到節(jié)點2步長為3.16 m，節(jié)點2至節(jié)點3路徑長度為2 m，因此，方案1路徑總長度為5.16 m，方案2為節(jié)點1變步長跳躍至節(jié)點4再到節(jié)點5，最后由節(jié)點5單步移動至終點3，方案2路徑總長度為4.65 m，方案3為傳統(tǒng)蟻群算法的單步長移動方式，從當前節(jié)點1到節(jié)點6，再移動到節(jié)點7，再移動到節(jié)點8，最后再到終點3，該方案路徑總長度為4.83 m，方案4為節(jié)點1跳躍至節(jié)點9，從節(jié)點9單步長移動到節(jié)點8，最后移動到終點3，該方案路徑總長度為5.16 m，顯然，方案2作為變步長移動方式優(yōu)于其他方案，變步長蟻群算法在尋路過程中，對每種方案的路徑長度進行評估，最終挑選出路徑最短的方案。

圖 3 步長選擇Fig. 3 Step size selection

在圖3中，節(jié)點1為起始點，節(jié)點3為終點，移動機器人進行路徑規(guī)劃時，將節(jié)點1作為父節(jié)點，通過變步長選擇策略，將下一步移動機器人要到達的節(jié)點4作為子節(jié)點，再將節(jié)點4作為父節(jié)點確定下一子節(jié)點，以此方法進行迭代，最終確定了本輪迭代后的最優(yōu)路徑{1,4,5,3}，結合變步長蟻群算法的優(yōu)點，移動機器人對于下一步所選擇的節(jié)點越接近于終點，則可以減少節(jié)點轉折的次數(shù)，同時，轉折點越接近于障礙物，則可以減少無效路徑，因此，為了縮短移動機器人路徑長度，引入終點誘導因子 φ 及障礙物誘導因子 μ，其選擇概率為

式中：k為常數(shù)，保證概率范圍為(0,1)；ε 為終點誘導系數(shù)；ω 為障礙物誘導系數(shù)； γis為移動機器人當前節(jié)點到下一步可到達所有節(jié)點的距離總和，σ 為移動機器人下一步到達的節(jié)點與終點之間的距離，其值越小，則距離終點越近，被選擇的概率也將越大，λ 為移動機器人下一步到達的節(jié)點與其最近的障礙物之間的距離，優(yōu)先考慮障礙物相鄰的節(jié)點，可以有效縮短無效路徑，提高移動 機器人避障能力。

2.2 信息素分布策略

在移動機器人路徑規(guī)劃之前，需要給柵格地圖環(huán)境的信息素進行初始化，初始化信息素采用不均勻分布，障礙物柵格的信息素設置為0，加強起點至終點直線所涉及到柵格的信息素濃度，平行的向外衰減，將柵格地圖建立直角坐標系，如圖4所示。

圖 4 信息素分布策略Fig. 4 Pheromone distribution strategy

連接移動機器人的起始點及終點，則該直線方程為

在本文中，C取值為20或30，分別對應簡單柵格環(huán)境和復雜柵格環(huán)境，令τij(0)=τ0為信息素濃度的初始值，根據(jù)初始信息素濃度的衰減方式，障礙物柵格的初始信息素 τ0直接取0，非障礙物柵格初始信息素取值如下：

式中：T為調整系數(shù)，T∈(1,20)，初試信息素的分布有利于蟻群提高搜索速度，快速收斂。

為了防止某條路徑的信息素過高或過低，避免螞蟻集中在某條路徑上，將每條路徑的信息素設置上下限為 [τmin,τmax]，當該條路徑信息素濃度低于信息素下限時，將該條路徑信息素設置為τmin，當該條路徑信息素濃度高于信息素上限時，該條路徑信息素設置為 τmax，這樣可以避免算法陷入局部最優(yōu)解，當蟻群經過一輪迭代后，挑選出最優(yōu)路徑，對其信息素進行更新，加強對最優(yōu)路徑的利用，當所有螞蟻完成一次迭代后，對路徑上的信息素進行全局更新：

為了提高搜索效率，一只螞蟻在一輪迭代中走過的完整路徑將不被以后的螞蟻所選擇，對于需要更新信息素的路徑，可以是本輪迭代的最優(yōu)解 ，也可以是全局最優(yōu)解。

2.3 改進啟發(fā)函數(shù)

結合變步長蟻群算法的優(yōu)點，在直角坐標系中，利用蟻群下一步到達的節(jié)點距離起點至終點連線的長短，對啟發(fā)函數(shù)進行改進，傳統(tǒng)蟻群算法的啟發(fā)函數(shù)為蟻群下一步所選擇的節(jié)點到終點之間距離的倒數(shù)，如式(2)所示，該函數(shù)收斂性不強，且容易使蟻群尋優(yōu)路徑冗長，改進后的啟發(fā)函數(shù)如下：

式中，(xi,yj) 為下一步所選擇節(jié)點的坐標，當其距離起點至終點對角線的長度越小，被選擇概率則越大，與傳統(tǒng)蟻群算法的啟發(fā)函數(shù)相比，改進后的啟發(fā)函數(shù)促使移動機器人將下一步選擇的節(jié)點趨近于移動機器人起點到終點連線處，使移動機器人在路徑尋優(yōu)中能更快地找到最優(yōu)解，提高了算法的收斂速度，因此，改進后的啟發(fā)函數(shù)作用得到加強，有利于提高算法的收斂速度，提高算法的全局搜索能力。

3 改進算法步驟

圖5為變步長蟻群算法的流程圖，算法的具體步驟如下：

1) 針對各項相關參數(shù)進行初始化：路徑規(guī)劃的起始點及終點、信息素重要程度參數(shù) α、啟發(fā)因子重要程度參數(shù) β、迭代次數(shù)、螞蟻數(shù)量、信息素揮發(fā)系數(shù)及增強系數(shù)等相關參數(shù)，建立地圖二維柵格模型，鄰接矩陣模型。

2) 初始化信息素采用不均勻分布，加強起點至終點直線所涉及柵格的信息素濃度，平行的向外衰減；改進啟發(fā)式信息矩陣，調整移動機器人當前位置到終點位置的啟發(fā)函數(shù)計算方法，建立啟發(fā)式信息矩陣。

3) 建立禁忌表以及對禁忌表初始化，將起點、障礙物節(jié)點、引起死鎖的節(jié)點均加入禁忌表中。

4) 計算啟發(fā)信息，根據(jù)信息素濃度以及概率公式確定螞蟻下一步可以到達的節(jié)點，記錄路徑并更新，更新禁忌表。

5) 當所有螞蟻完成一次迭代后，保存最優(yōu)路徑，更新信息素及禁忌表，如果沒有完成一次迭代，則繼續(xù)開始下一只螞蟻路徑尋優(yōu)。

6) 如果螞蟻完成所有迭代次數(shù)，則輸出最優(yōu)路徑及收斂迭代次數(shù)，如果沒有完成所有迭代次數(shù)，則繼續(xù)開始下一次迭代。

圖 5 變步長蟻群算法流程Fig. 5 Flow chart of variable step size ant colony algorithm

4 算法仿真

為了驗證變步長蟻群算法的有效性，本文分別在簡易環(huán)境和復雜環(huán)境下進行仿真對比，簡易環(huán)境為 20 ×20 的柵格環(huán)境，對傳統(tǒng)蟻群算法、本文算法進行仿真，與文獻[8]進行對比，復雜環(huán)境為 3 0×30 的柵格環(huán)境，對本文算法進行仿真，與文 獻[8]進行對比。

4.1 20×20 柵格環(huán)境

在 20×20 的柵格環(huán)境下，對傳統(tǒng)蟻群算法和本文算法進行仿真，其中，路徑規(guī)劃仿真分別如圖6、7所示，實驗數(shù)據(jù)如表1所示，傳統(tǒng)蟻群算法路徑規(guī)劃長度為30.870 m，文獻[8]算法路徑規(guī)劃長度為32.1421 m，本文算法路徑規(guī)劃長度為28.042 m，顯然，本文算法在路徑規(guī)劃方面優(yōu)于文獻[8]算法及傳統(tǒng)蟻群算法，本文算法較文獻[8]算法、傳統(tǒng)蟻群算法的路徑長度分別縮短了12.76%及9.16%。本文算法提出信息素不均勻分布策略，提高了最優(yōu)路徑上節(jié)點被選擇的概率，通過節(jié)點距離起點至終點對角線的距離，改進啟發(fā)函數(shù)，提高了算法的全局搜索能力，有效縮短了全局 最優(yōu)路徑的長度。

圖 6 傳統(tǒng)蟻群算法路徑規(guī)劃(20×20)Fig. 6 Path planning of traditional ant colony algorithm

圖 7 本文算法路徑規(guī)劃(20×20)Fig. 7 Algorithm path planning in this paper

表 1 各算法實驗結果對比Table 1 Comparison of experimental results of various algorithms

收斂迭代仿真分別如圖8、9所示，傳統(tǒng)蟻群算法收斂迭代次數(shù)為25次，文獻[8]算法收斂迭代次數(shù)為4次，本文算法收斂迭代次數(shù)為2次，顯然，本文算法在收斂速度方面優(yōu)于文獻[8]算法及傳統(tǒng)蟻群算法，本文算法較文獻[8]算法、傳統(tǒng)蟻群算法的收斂迭代次數(shù)分別減少了50%及92%。圖10為本文算法在該環(huán)境下各代螞蟻最優(yōu)路徑規(guī)劃路線，各代路線集中于起點至終點的連線處，表明信息素不均勻分布的有效作用，在 2 0×20 柵格環(huán)境中，本文算法無論是在最優(yōu)路徑上還是在收斂速度上，都優(yōu)于其他兩 種算法。

圖 8 傳統(tǒng)蟻群算法收斂曲線Fig. 8 Convergence curve of traditional ant colony algorithm

圖 9 本文算法收斂曲線Fig. 9 Convergence curve of the algorithm presented inthis paper

圖 10 本文算法各代蟻群最優(yōu)路徑規(guī)劃(20×20)Fig. 10 Optimal path planning of each generation of ant colony in this algorithm (20×20)

4.2 3 0×30 柵格環(huán)境

在 30×30 柵格環(huán)境下，采用文獻[8]中的同一個柵格地圖，對本文算法進行仿真實驗，實驗數(shù)據(jù)如表2所示，本文算法的路徑規(guī)劃如圖11所示，本文算法的最佳路徑長度為41.961 m，文獻[8]的最佳路徑長度為45.112 7 m，本文算法較文獻[8]關于最佳路徑長度縮短了6.99%，因此，在復雜柵格環(huán)境下，本文算法依然保持良好的路徑規(guī)劃能力，通過變步長蟻群算法，有效地縮短了最優(yōu)路徑長度，收斂迭代效率如圖12所示，本文算法的收斂迭代次數(shù)為6次，文獻[8]算法的收斂迭代次數(shù)為8次，本文算法較文獻[8]算法關于收斂迭代次數(shù)減少了25%，柵格地圖越復雜，本文算法的優(yōu)越性越明顯，各代最優(yōu)路徑規(guī)劃路線如圖13所示，各代路徑規(guī)劃的路線依然集中于起點至終點的連線處，移動機器人將快速的尋找出最優(yōu)路 徑。

表 2 兩種算法實驗結果對比Table 2 Comparison of experimental results of various algorithms

圖 11 本文算法路徑規(guī)劃(30×30)Fig. 11 Algorithm path planning in this paper (30×30)

圖 13 本文算法各代蟻群最優(yōu)路徑規(guī)劃(30×30)Fig. 13 Optimal path planning of each generation of ant colony in this algorithm (30×30)

4.3 實驗研究

本文采用自主搭建的移動機器人進行實驗驗證，如圖14及圖15所示，一個紙箱代表兩個正方形障礙物柵格，空白場地為自由柵格，實驗場景為 2 0×20 的柵格環(huán)境，實驗數(shù)據(jù)如表3所示，本文算法路徑規(guī)劃最優(yōu)長度為3.26 m，移動機器人從起點至終點耗時13.56 s，傳統(tǒng)蟻群算法路徑規(guī)劃最優(yōu)長度為5.13 m，耗時19.67 s，驗證了本文算法在移動機器人實際應用中能夠較快地找到最優(yōu)路徑，有效地提高了路徑規(guī)劃的工作 效率。

圖 14 移動機器人起點位置Fig. 14 Starting position of mobile robot

圖 15 移動機器人運行過程Fig. 15 Mobile robot running process

表 3 各算法路徑規(guī)劃實驗數(shù)據(jù)Table 3 Experimental data of path planning for each algorithm

5 結束語

傳統(tǒng)蟻群算法在移動機器人路徑規(guī)劃中存在搜索效率低、路徑過長、收斂較慢等問題，本文在傳統(tǒng)蟻群算法的基礎上引入了變步長策略對其進行改進，擴充蟻群可以到達節(jié)點的集合，在不觸碰障礙物的條件下，從蟻群當前位置的相鄰位置擴大至全局地圖的任意自由柵格位置，達到變步長策略，改進信息素分布策略以及調整啟發(fā)函數(shù)計算方法，大幅提高本文算法的收斂速度，快速地尋找到最優(yōu)路徑。本文基于變步長蟻群算法在收斂速度和路徑尋優(yōu)方面有著較好的性能，不僅適用于簡單柵格環(huán)境，也適用于復雜的柵格環(huán)境，使本文算法在實際應用場景中得到較好的應用，通過對整個地圖狀態(tài)空間的探索點進行采樣，能夠增加搜索區(qū)域，適合解決移動機器人在復雜環(huán)境下的路徑規(guī)劃。