基于靜電勢場法改進的蟻群算法用于路徑規劃

文/尤潤川

（湖北工業大學 湖北省武漢市 430068）

近年來，智能自主移動機器人得到了廣泛的關注。在機器人技術中導航任務十分復雜，其中路徑規劃是非常重要的一項技術。移動機器人的路徑規劃指的是確定移動機器人如何安全地到達目標的策略，以確保避免障礙[1]。

針對移動機器人路徑規劃的問題，國內外學者做了很多方面的研究。文獻[2]中引入激勵函數改進基本蟻群算法的啟發函數，增強了路徑平滑性，降低搜索過程的死鎖現象，文獻[3]中利用機器人當前朝向和下一次位置的方位之間的夾角來改變螞蟻的轉移概率，不僅增強了路徑的平滑性，也縮短了路徑的長度。文獻[4]中提出了靜電勢場法用于路徑規劃，和人工勢場法不同的是，靜電勢場是標量場只有大小沒有方向，便于計算，降低了路徑規劃過程中計算的復雜度，縮短了路徑規劃的時間。

本文將蟻群算法與靜電勢場法結合，將靜電勢場函數引入蟻群算法的啟發函數中，不僅考慮下一個節點到目標點的距離，還考慮障礙物的影響，增加初始搜索階段的目的性；加入回退機制，減少蟻群算法容易死鎖的問題；將揮發因子設置為動態的，增強初始階段的搜索能力，同時保證后期的收斂速度。

1 基本的蟻群算法

1.1 環境的建模

本文主要研究二維平面內移動機器人的路徑規劃問題，不考慮環境中障礙物以及機器人的高度，采用柵格法對環境進行建模，將環境抽象為一個二維平面，根據移動機器人的大小和步長將平面分為若干個等大的正方形柵格，如圖1所示。

柵格編號與坐標的轉換公式如下：

其中a為柵格的邊長，mod為取余運算，Ni為柵格編號，l為每行柵格的個數。ceil為向上取整運算。同時將障礙物也抽象為柵格，黑色的柵格表示障礙物。為了防止障礙物與機器人的碰撞，對障礙物進行膨脹處理，使障礙物的邊界向外膨脹，膨脹的寬度為機器人的半徑。機器人所在位置在沒有障礙的情況下有8個可移動的位置。

1.2 蟻群算法的基本原理

首例蟻群算法由Dorigo提出，被稱為螞蟻系統[5]。在螞蟻系統中，最核心的是轉移概率，表示螞蟻從點i移動到點j的概率,計算公式如下：

其中djE表示位置j到位置E的距離。α，β分別表示信息素濃度和啟發式信息對轉移概率的影響程度，體現了螞蟻對記憶的優質路徑和先驗知識的傾向性。

當一代螞蟻全部從起點移動到終點或者走到沒有位置可以移動的節點，表示這一代螞蟻工作結束，開始對信息素進行更新。更新公式為：

其中t表示迭代次數，ρ表示信息素揮發系數，m表示每代螞蟻的數量，Q是一個常數，表示一只螞蟻在所在路徑上釋放的信息素，Lk表示螞蟻所走過完整路徑的長度。

2 靜電勢場法

靜電勢場法同樣以柵格法對環境建模，然后對每個障礙物建立勢場函數，把每個障礙物看做是帶正電荷的粒子，在周圍產生勢場，勢場函數為：

其中(xi,yi)表示編號為i的障礙物的中心坐標，βi是與障礙物的面積成反比。

Ai表示編號為i障礙物的面積，將所有障礙物的勢場函數累加得到下式。

建立勢場函數意在使移動機器人盡量避開勢場高的地方，從而找到一條沒碰撞的路徑。然而這樣并不能保證能夠找到一條比較優質到達目標點的路徑，因此定義代價函數：

通過找到當前位置周圍8個位置上代價函數最低的位置作為下一次移動的位置，重復這個過程，直到到達終點。

圖1：柵格法環境建模

圖2：死鎖示意圖

3 基于電勢場法的蟻群算法

利用傳統的蟻群算法進行路徑規劃時，前幾代螞蟻留下的信息素少，同時初始化信息素是平均分配的，螞蟻在尋找路徑的過程中，主要在啟發函數的作用下進行移動，避障能力較弱，效率低下，很多路徑都是在重復無用的搜索。因此本文對啟發函數進行改進，讓算法早期的搜索更有目的性，不僅具有向目標點搜索的能力，同時也能具有避開障礙物的能力。在蟻群算法前期，需要快速的找到可行解，不需要過度要求路徑的長度，使用靜電勢場法快速避障的特點，快速找到可行的解。到了蟻群算法后期，要得到更高質量的路徑，即蟻路徑長度要求盡可能的短，因此要降低靜電勢場的影響，使路徑不是主要繞行障礙，而是能夠盡快到達目標點，后期就要降低啟發函數中靜電勢場的影響值。改進的啟發函數如下式：

傳統的蟻群算法在前期的搜索過程中盲目性強，在地形復雜的環境中，如U形障礙，容易陷入死鎖，導致本次螞蟻搜索無效。

如圖2所示，移動機器人在R所標注的位置，當其向圖示方向移動時就會陷入死鎖問題。當移動機器人從位置R移動到位置1時，它下一次移動的位置只能是位置2，到達位置2陷入死鎖，此時采用回退機制，讓移動機器人回退到位置1，位置2加入禁忌表中，然后發現移動機器人依然沒有位置可以移動，繼續回退，退到位置R,將位置1加入禁忌表中，移動機器人回到位置R,可以正常移動。同時對位置R到位置1，位置1到位置2進行懲罰，使其信息素含量降低50%，避免下一只螞蟻進入死鎖。

傳統的蟻群算法中，在一代螞蟻全部移動到終點或出現死鎖的情況之后再對信息素進行更新，所有的螞蟻走過的路徑信息素都會增加，然而早期螞蟻的路徑的隨機性強，所走出來的路徑不夠優質，因此沒有必要將所有的路徑都進行信息素的更新，只需要選擇其中路徑相對較短的路徑進行信息素的更新，使算法更快收斂，更新公式如下式。

蟻群算法前幾代螞蟻的路徑的參考價值相對較低，這里動態的改變信息素揮發因子的ρ，使其在蟻群算法早期有一個相對較大的值，降低蟻群算法前期的信息素對轉移概率的影響，然而到后期有一個相對較小的值使信息素對轉移概率的影響較大，加快收斂速度。基于靜電勢場法的蟻群算法路徑規劃步驟如下：

（1）初始化參數，用矩陣G表示已知的環境模型，確定起始點S和終點E，通過式（1）計算出障礙物的坐標。設定表示信息素和啟發函數重要程度的參數α，β，種群數量為M，迭代次數上限為K。初始化信息素強度Tau,設定信息素增強系數為Q。

圖3：改進前后的蟻群算法在障礙物較多的環境下仿真結果

（2）螞蟻種群從起始位置出發，獲取可行節點，通過式(2)建立概率分布律，利用輪判賭的方式選擇當前這只螞蟻移動的下一個位置，螞蟻移動到所選擇的位置，并將上一個位置加入禁忌表中。如果螞蟻獲取可行節點的數量為零，螞蟻回退到上一次位置，將當前位置加入禁忌表，并降低回退機制觸發時所移動位置的信息素至50%，降低其他螞蟻和后代螞蟻選擇此節點的概率。然后進行下一個節點的選擇，直至到達終點E。

（3）當此代螞蟻全部尋路完畢，記錄M只螞蟻的路徑長度，對沒有到達終點E的螞蟻的路徑長度設置為無窮大。通過式（12）計算當代螞蟻信息素發揮率，然后對路徑長度短的路徑通過式（11）進行信息素更新。

（4）判斷迭代次數是否到達上限，若沒有到達上限，迭代次數加一，然后重復進行步驟（2）、（3）、（4），直到迭代次數到達上限，然后輸出最短的路徑。

4 仿真結果與分析

本文利用MATLAB 2014b軟件進行仿真，實現了基本蟻群算法的路徑規劃以及改進后的蟻群算法路徑規劃。基本蟻群算法的參數為，改進的蟻群算法參數為，信息素揮發速率采用式(12)，啟發函數采用式(10)。本文在復雜環境下分別利用基本蟻群算法和改進的蟻群算法進行路徑規劃，仿真結果如圖3所示。

由圖3可知，基本蟻群算法和改進的蟻群算法均能得到一條可行的路徑到達目標點，改進后的蟻群算法得到了更短的路徑，收斂速度更快，由于回退機制的加入，死鎖情況減少，到達目標點的路徑更多。

5 結束語

針對基本蟻群算法前期搜索能力差并容易出現死鎖的問題，改進了蟻群算法的啟發函數，使蟻群算法前期的搜索能力更強，對死鎖問題進行回退處理，增加路徑的有效性，使搜索能力加強。同時動態化信息素的揮發速率，使得前期信息素影響小，搜索能力強，后期信息素影響大，加快收斂。仿真表明，改進的蟻群算法的搜索能力更強，在復雜環境下比基本蟻群算法規劃的路徑更短，收斂速度更快。