改進蟻群算法在機器人路徑規劃上的應用

周敬東， 楊 磊， 高偉周， 汪 宇

(1 湖北工業大學機械工程學院， 湖北 武漢 430068；2 湖北省農業機械工程研究設計院， 湖北 武漢 430068)

作為機器人實現智能自主規劃的關鍵技術，根據可支配的外界環境有效信息的程度，路徑規劃[1-2]可分為靜態路徑規劃和動態路徑規劃[3]。相較于模糊算法、人工勢場法[4]以及D*算法[5]等，蟻群算法擁有強魯棒性、隱含并行點而被廣泛地應用到動態路徑規劃中。但是，傳統蟻群算法規劃路徑時存在搜索精度不高、容易早斂、搜索時間較長且收斂速度慢等問題[6-7]。為解決上述不足，本文對蟻群算法中存在的具體問題進行局部改進。仿真分析的結果表明，改進后的蟻群算法求解速度更加迅速，路徑更優且不會陷入U形陷阱，驗證了改進算法的可行性。

1 蟻群算法原理

作為個體，螞蟻只有有限的視覺和嗅覺，但它們以群體形式存在的時候，卻能非常高效、有組織地完成筑巢、覓食、搬運等大型活動。Dorigo等通過研究螞蟻群體尋找食物的行為，結合螞蟻之間團隊協作覓食的特點提出了蟻群算法[8]，其原理：螞蟻在尋找食物的過程中會沿途釋放信息素，信息素不會立即揮發而是會逐漸累積，而信息素累計的濃度會影響下一個螞蟻選擇該路徑的概率，即濃度越大，選擇概率也會越大。圖1上方的路徑長度會比下方的短，而路徑的長度和信息素累積的濃度隨著時間呈反比關系，所以上方的信息素累計會相對多一些。最終螞蟻會全部走上方的路徑。

圖 1 蟻群覓食

由于蟻群算法和機器人路徑規劃的目標都是尋找從起點到終點的一條最短路徑，故非常合適將蟻群算法運用到路徑規劃中。具體執行流程見圖2。

圖 2 蟻群算法路徑規劃流程

蟻群算法用于機器人路徑規劃時，主要由初始化、解構建和信息素更新三部分組成。

1)初始化。主要設置信息素、啟發信息、種群規模、信息素揮發率、迭代次數等參數的初始值。

2)解構建。解構建是蟻群算法用來實施迭代最關鍵的步驟，主要內容是依據狀態轉移規則選擇下一路徑點，最終形成完整路徑。

3)信息素更新。信息素更新對螞蟻搜索路徑起到無比關鍵的影響。在其所經過的路徑上釋放信息素，將加強對螞蟻未來選擇該路徑的影響，增強算法的開發能力。每次迭代后降低路徑上的信息素，將減小正反饋效果，從而增強算法的探索能力。

2 蟻群算法的改進

2.1 非均勻分布初始信息素

由于蟻群算法前期初始信息素值相同，螞蟻在搜索路徑時會以最短距離為標準來選擇下一個節點，而忽視了全局信息。這種方式使得螞蟻會往返搜索，導致規劃出來的路徑存在回路。這種情況的產生會使搜索效率降低且增加路徑長度。

為解決這個問題，本文以起點和終點為對角頂點劃定一個矩形區域，并且增加該區域信息素初始值。這樣做能夠使得機器人在早期的移動過程中具有向目標點的方向前行的啟發性，有利于減少螞蟻盲目搜索，大大提高了收斂速度。

2.2 基于A*算法的啟發式信息

傳統蟻群算法依據相鄰柵格之間的距離進行啟發式搜索，這種搜索方式造成柵格之間數值差別不明顯。針對此問題，本文采用A*算法作為路徑搜索的啟發式信息，使其移動的總體方向偏向于目標點，從而獲得較好的路徑。

A*算法[9]同時具備Dijkstra算法和貪心搜索算法的優勢，能夠在啟發函數指引下快速靠近目標點的同時，確保規劃路徑最優。A*算法的評價函數

f(n)=g(n)+h(n)

(1)

式中：f(n)代表由出發點途經當前點并到達目標點的總代價值；g(n)代表f(n)總代價的前一部分代價，即當前點到出發點的代價；h(n)代表f(n)總代價的后一部分代價，即當前點到目標點的代價。改進后啟發式為

(2)

這里Q2是大于1的常量。

2.3 改進轉移概率

信息素分布差異越大則正反饋效果越明顯，算法能夠更快地收斂。而蟻群算法由于早期天然存在各節點信息素分布差異不明顯的特點，算法規劃的路徑容易出現大量的交叉路徑。與此同時，螞蟻在尋路時會將之前走過的路徑點加入到禁忌表中，這種單向行走不能往返的方式使得螞蟻在交叉路徑中會進入死鎖階段，最終迷失方向。為了解決這個問題，可以加入避障策略[10]到前期的搜索流程中：

(3)

式中：Oj記錄節點j鄰域里存在障礙物的柵格總數；Lj記錄節點j鄰域里被禁忌表限制不能通過的柵格總數；Aj記錄節點j相鄰柵格總數；ε為避障系數。算法引入避障策略后，螞蟻死鎖的概率極大降低。

2.4 螞蟻回退策略

螞蟻在面對U型障礙物時會落入“陷阱”中，此時螞蟻四周無路可走且走過的路徑已經加入到禁忌表中，這將導致螞蟻無法走出陷阱。這種現象的發生會使螞蟻處于死亡狀態，最終導致算法進入死鎖。顯然這種情況是不利于路徑規劃的。如圖3所示一共有3處陷阱，分別為N12-N14,N11-N14-N17,N13-N16-N18。陷阱一類是障礙物之間形成的，一類是障礙物與環境邊界形成的。為了增強算法的健壯性以及對環境的適應性，可以采用螞蟻回退策略來應對。

當螞蟻k處于N15時,螞蟻k進入陷阱。此時螞蟻k需要回退到父節點N12，接著從tabuk中刪除N15，然后在可行解集合中選取柵格。假如螞蟻發現依舊無路可走，則繼續回退，圖3中螞蟻k仍需從tabuk中刪除N12，回退到N8,直到脫離陷阱為止。

通過引入螞蟻回退策略,解決了“死鎖”問題，確保每一只螞蟻能夠逃離陷阱。螞蟻在搜索過程中不發生“死亡”，每個螞蟻的作用被充分發揮，增強了算法的魯棒性。

圖 3 具有U形障礙物的柵格圖

3 仿真實驗分析

為驗證改進算法的可行性和適用性，在MATLABR2017b建立的柵格環境下進行仿真。算法開始運行前需要對一些參數的值進行初始化，m=50，α=1，β=9，ρ=0.9，Q=1，epochs=100，分別代表螞蟻個數、信息素因子、啟發因子、信息素蒸發系數、信息素增長強度系數以及迭代次數。接著在兩種不同的實驗環境中對兩種算法進行仿真對比，實驗結果如圖4-7所示。

傳統算法和改進算法在兩種不同仿真環境下路徑長度和迭代次數的兩項指標分別如表1和表2所示。由表1-2可知：相較于傳統算法，本文改進蟻群算法顯著降低了迭代次數，縮短了路徑長度，路徑規劃更高效。

(a)蟻群算法

(b)改進蟻群算法圖 4 蟻群算法規劃路徑實例(環境1)

(a)蟻群算法

(b)改進蟻群算法圖 5 蟻群算法迭代(環境1)

(a)蟻群算法

(b)改進蟻群算法圖 6 蟻群算法規劃路徑實例(環境2)

(a)蟻群算法

為驗證改進算法的通用性和可靠性，本文在不同的仿真環境中進行5組實驗，得到的數據如表3和表4所示。其中goal_distance代表起點到終點的直線路徑，path_cost代表機器人路徑規劃的真實路徑。在表3中，改進蟻群算法通過加入A*算法的啟發式函數搜索函數，使算法移動的總體方向偏向于目標點，從而獲得較好的路徑，相較于傳統的蟻群算法，規劃出的路徑更短。在表4中，改進蟻群算法對初始信息素采取非均勻式分配，避免螞蟻進行無用的搜索行為。改進算法利用改進轉移概率解決了死鎖現象并采用螞蟻回退策略處理U型陷阱。局部改進方案使傳統蟻群算法的迭代次數和搜索時間明顯降低。

表3 蟻群算法與改進蟻群算法路徑長度對比

表4 蟻群算法與改進蟻群算法迭代次數和搜索時間對比

通過對具體數據的對比分析發現，改進蟻群算法相比于傳統蟻群算法規劃出來的路徑更短，尋路效率更高效。5組實驗結果顯示，改進蟻群算法的迭代次數平均減少了34%，搜索時間平均降低了60%，規劃出的路徑平均縮短了7%。

4 結論

本文在算法早期利用非均勻分布初始信息素的方式減少了螞蟻盲目搜索路徑，提高了收斂速度。引入A*算法的啟發信息來改進蟻群算法的啟發函數，從而加快搜索速度。改進轉移概率解決了死鎖現象。最后采用螞蟻回退策略較好地處理了U型陷阱。通過在MATLAB仿真平臺上對改進前后的蟻群算法進行仿真對比分析，由仿真結果可知，本文算法在路徑長度和搜索效率均有所提高且可以應對U形障礙物環境。