基于靜電勢(shì)場(chǎng)法改進(jìn)的蟻群算法用于路徑規(guī)劃

文/尤潤(rùn)川

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

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

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

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

1 基本的蟻群算法

1.1 環(huán)境的建模

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

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

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

1.2 蟻群算法的基本原理

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

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

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

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

2 靜電勢(shì)場(chǎng)法

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

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

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

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

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

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

圖2：死鎖示意圖

3 基于電勢(shì)場(chǎng)法的蟻群算法

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

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

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

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

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

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

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

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

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

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

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

本文利用MATLAB 2014b軟件進(jìn)行仿真，實(shí)現(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)點(diǎn)，改進(jìn)后的蟻群算法得到了更短的路徑，收斂速度更快，由于回退機(jī)制的加入，死鎖情況減少，到達(dá)目標(biāo)點(diǎn)的路徑更多。

5 結(jié)束語(yǔ)

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