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

李國濤 李丹 曹蒙

摘要：路徑規劃對移動機器人具有極其重要的意義，傳統的蟻群算法存在收斂速度慢、容易陷入死鎖以及容易陷入局部最優解等缺陷;本文采用柵格法進行地圖空間建模，并且在蟻群算法中引入人工勢場的概念，以此優化現有的蟻群算法;仿真結果顯示該算法明顯優于傳統蟻群算法，可以讓機器人在復雜環境中選擇更好的前進路線。

關鍵詞：蟻群算法;人工勢場法;移動機器人;路徑規劃

0 引言

移動機器人是集環境感知、路徑規劃、動態決策和行為執行于一體的的復雜控制系統。其中路徑規劃是機器人研究領域的技術重點，經過幾十年的發展，路徑規劃算法分為三大類：傳統路徑規劃算法、啟發式算法及智能仿生路徑規劃算法。其中傳統路徑規劃算法包括可視圖法、人工勢場法、模擬退火法、模糊邏輯算法等;啟發式算法具有很強的路徑搜索能力，可以很好的在離散的路徑拓撲結構中運用，常見的啟發式搜索算法有A*算法、Dijkatra算法及Floyd算法;智能仿生算法是人們通過仿生學的研究，在一系列的自然現象中發現的算法，主要包括：蟻群算法、粒子群算法、遺傳算法和神經網絡算法。其中蟻群算法是人們受螞蟻覓食的啟發而產生的算法，螞蟻在覓食的過程中會分泌一種信息素，并在其尋找食物的途中在道路上留下一定濃度的信息素，信息素會隨時間揮發。在覓食的過程中，路程越短則螞蟻遍歷的次數越多，信息素濃度也就越高，螞蟻將信息素濃度作為選擇路徑的依據，信息素濃度越高，路徑被選擇的概率越大，隨著時間的推移，最短路徑上的信息素濃度會越來越高，最終所有螞蟻都會選擇最短路徑，從而達到路徑規劃的目的。蟻群算法本質上是一種并行算法，易于計算機實現，蟻群算法最早是作為一種解決組合優化問題的元啟發式算法被提出，具有易與其他方法結合、魯棒性較強等優點，但是傳統蟻群算法同時存在搜索時間長、容易陷入局部最優、面對凹形障礙物容易陷入死鎖等缺點。本文主要研究改進后的蟻群算法在機器人路徑規劃中的應用。

1 環境建模

設機器人運動環境為二維靜止空間，由于柵格法地圖表達規范、易于實現，所以對機器人運動空間進行柵格法建模。將機器人視為質點，占據一個柵格，同時如果靜態障礙物只占據某柵格的一部分，則將其視為完全占據此柵格。機器人的運動方向共有8個運動方向，同時機器人可在勻速和靜止兩個運動狀態中自由切換。運用柵格法進行環境建模的好處在于對于任何形式的障礙物都能很好的描述，而可視圖法或自由空間法對于圓形障礙物無法建模，此外，運用一系列二值信息存儲障礙物特征及位置，方便計算機的存儲與更新，因此，選用柵格法進行環境建模具有顯著的優勢。

2 蟻群算法基本原理

2.1 傳統蟻群算法

受螞蟻覓食過程的啟發，1991年首次提出了蟻群算法[10]。在人工蟻群算法中，設m為螞蟻總數，螞蟻從某個節點轉移到另一個節點是由路徑上的信息素決定的，在t時刻，螞蟻k從節點i轉移到節點j的狀態轉移概率? 為：

所有螞蟻完成一次覓食后，需要對信息素進行更新，隨著時間的推移信息素會逐漸揮發，同時在螞蟻經過的路段信息素量會增加，更新公式為：

2.2 改進蟻群算法

基本蟻群算法雖然能夠規劃出從起始點到目標點的路徑，并有較強的魯棒性，但依然存在很多不足，主要有容易過早停滯、搜索時間過長、效率較低等缺點。本文針對傳統蟻群算法的先天不足，對基本蟻群算法做出以下幾點改進，從而加快算法收斂速度，優化算法路徑選擇，提高算法性能，使算法更加適合移動機器人的實際使用。

（1）U形柵格優化

在蟻群算法中，螞蟻很容易陷入U形障礙物并發生死鎖，從而導致算法時間過長甚至停滯，劉徐迅等人提出了螞蟻回退策略[11]，以此增加算法的魯棒性。但是當U形障礙物過多時，螞蟻需要反復回退、反復判斷，因此增加了很多計算量，使搜索時間過長。本文采用填補的方式對U形障礙物進行填補，對于柵格中任意節點，如果與其相鄰的上下左右四個方向中的三個方向都存在障礙物或禁忌柵格，則將該節點標記為禁忌柵格，不允許螞蟻通過。同時，如果填補過后出現新的滿足填補條件的柵格，則繼續填補，直至柵格地圖中所有滿足條件的柵格都被填補。

障礙物，因與10號柵格相鄰的三個方向的柵格同時存在障礙物，因此將10號柵格標記為禁忌柵格，對于6號柵格，因與其相鄰的5號、7號柵格都存在障礙物，且10號柵格為禁忌柵格，因此將6號柵格也標記為禁忌柵格。

（2）人工勢場法確定初始信息素

在基本蟻群算法中，初始信息素? ? ? ，即總是被設置為一個常數。地圖上相同的信息素濃度導致螞蟻在前期沒有足夠信息找到較優的路徑，使算法在前期收斂速度過慢，因此設置合理的初始信息素對于提高算法初期的收斂速度具有重要作用，可以顯著的提高算法初期收斂速度。本文提出一種基于人工勢場法的設置初始信息素的方法，即在出發點設計斥力勢函數，降低出發點的初始信息素濃度，在目的地設置引力勢函數，提高目的地的初始信息素濃度。

式中ω為固定系數，di和dj分別為柵格節點到出發點和目標點的距離，為一閾值，保證所有柵格的初始信息素都不低于這個閾值，在一定程度上這也保證了算法避免過早陷入局部最優。

2.3 基于改進蟻群算法的路徑規劃

在蟻群算法中通過對U型柵格進行優化以及引入人工勢場法確定初始信息素來提高蟻群算法的性能，把改進后的蟻群算法應用到移動機器人路徑規劃中，具體步驟如下。

（1）對環境采用柵格法建模，并且初始化機器人起始位置、方向等相關參數以及目標點的位置及相關參數。

（2）對柵格法地圖中的U形障礙物進行填充，并且根據人工勢場法設置出發點和目的地的信息素濃度。

（3）當一只螞蟻到達終點時根據蟻群算法信息素濃度更新公式對其經過路段上的信息素濃度進行更新。