文/尤潤川

（湖北工業(yè)大學(xué) 湖北省武漢市 430068）

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

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

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

1 基本的蟻群算法

1.1 環(huán)境的建模

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

柵格編號與坐標(biāo)的轉(zhuǎn)換公式如下：

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

1.2 蟻群算法的基本原理

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

其中djE表示位置j到位置E的距離。α，β分別表示信息素濃度和啟發(fā)式信息對轉(zhuǎn)移概率的影響程度，體現(xiàn)了螞蟻對記憶的優(yōu)質(zhì)路徑和先驗知識的傾向性。

當(dāng)一代螞蟻全部從起點移動到終點或者走到?jīng)]有位置可以移動的節(jié)點，表示這一代螞蟻工作結(jié)束，開始對信息素進(jìn)行更新。更新公式為：

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

2 靜電勢場法

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

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

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

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

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

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

圖2：死鎖示意圖

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

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

傳統(tǒng)的蟻群算法在前期的搜索過程中盲目性強，在地形復(fù)雜的環(huán)境中，如U形障礙，容易陷入死鎖，導(dǎo)致本次螞蟻搜索無效。

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

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

蟻群算法前幾代螞蟻的路徑的參考價值相對較低，這里動態(tài)的改變信息素?fù)]發(fā)因子的ρ，使其在蟻群算法早期有一個相對較大的值，降低蟻群算法前期的信息素對轉(zhuǎn)移概率的影響，然而到后期有一個相對較小的值使信息素對轉(zhuǎn)移概率的影響較大，加快收斂速度?；陟o電勢場法的蟻群算法路徑規(guī)劃步驟如下：

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

圖3：改進(jìn)前后的蟻群算法在障礙物較多的環(huán)境下仿真結(jié)果

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

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

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

4 仿真結(jié)果與分析

本文利用MATLAB 2014b軟件進(jìn)行仿真，實現(xiàn)了基本蟻群算法的路徑規(guī)劃以及改進(jìn)后的蟻群算法路徑規(guī)劃?；鞠伻核惴ǖ膮?shù)為，改進(jìn)的蟻群算法參數(shù)為，信息素?fù)]發(fā)速率采用式(12)，啟發(fā)函數(shù)采用式(10)。本文在復(fù)雜環(huán)境下分別利用基本蟻群算法和改進(jìn)的蟻群算法進(jìn)行路徑規(guī)劃，仿真結(jié)果如圖3所示。

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

5 結(jié)束語

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