改進(jìn)的勢場蟻群算法的移動機(jī)器人路徑規(guī)劃

曾明如，徐小勇，劉 亮，羅 浩，徐志敏

南昌大學(xué) 信息工程學(xué)院，南昌 330031

在機(jī)器人眾多研究領(lǐng)域中，路徑規(guī)劃是其中一個重要研究對象，其任務(wù)是在一定性能指標(biāo)要求下，在機(jī)器人運(yùn)動環(huán)境中尋找出一條從起始位置到目標(biāo)位置的最優(yōu)或次優(yōu)無碰撞路徑。目前常用路徑規(guī)劃算法主要有蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等，雖然這些算法能夠在一定程度上解決問題，但都存在一些不足，如遺傳算法搜索能力差和收斂性能差[1]，粒子群算法易出現(xiàn)早熟收斂慢的問題[2]。

越來越多的學(xué)者對路徑規(guī)劃問題研究時更注重多種智能算法相結(jié)合[3-7]，不同的智能算法相結(jié)合，優(yōu)勢互補(bǔ)，可提高算法性能。本文綜合人工勢場算法和蟻群算法的優(yōu)點(diǎn)提出人工勢場蟻群算法。利用人工勢場中的勢場力、蟻群算法中機(jī)器人與目標(biāo)位置的距離及勢場力啟發(fā)信息影響系數(shù)來重新構(gòu)造綜合啟發(fā)信息，并以蟻群搜索機(jī)制進(jìn)行全局路徑規(guī)劃。仿真結(jié)果表明勢場蟻群算法路徑規(guī)劃能找到更優(yōu)路徑和收斂速度更快。

1 基本蟻群算法和人工勢場算法簡介

1.1 傳統(tǒng)蟻群算法簡介

蟻群算法是模擬蟻群覓食行為的一種優(yōu)化算法。假設(shè)蟻群中螞蟻的總數(shù)為M，各螞蟻在柵格環(huán)境下移動，并且根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個柵格，假設(shè)在時刻t時，螞蟻k位于柵格i，那么螞蟻k選擇下一柵格j的概率為：

式中V表示螞蟻k可以選擇的下一柵格的集合；α為信息素濃度的啟發(fā)因子，α越大，表明螞蟻k越趨向于選擇多數(shù)螞蟻走過的路徑；β表示能見度啟發(fā)因子，反映了能見度信息對螞蟻選擇下一步位置所起作用的大小，β值越大，表明螞蟻k越趨向于選擇距離終點(diǎn)近的柵格；τij(t)表示t時刻路徑(i,j)上的信息素濃度；ηij(t)表示t時刻路徑(i,j)上的啟發(fā)信息，其定義為：

其中G為目標(biāo)柵格，d(j,G)表示柵格j到G的歐式距離。

蟻群經(jīng)過某個柵格時會留下信息素，而信息素會隨著時間的推移而消逝，所以每只螞蟻走完一個柵格后，要進(jìn)行局部信息素更新，更新公式如下：

式中p(0＜p＜1)是信息素殘留程度；Q是常數(shù)；Lse是螞蟻走過的路徑長度：

w是螞蟻k在本次循環(huán)中走過的步數(shù)，di是螞蟻k的走過的邊長。

1.2 人工勢場算法簡介

人工勢場算法[8]實質(zhì)是對機(jī)器人運(yùn)行環(huán)境虛擬一個抽象勢場，該勢場由兩部分場疊加而成，一部分為目標(biāo)位置形成的引力場；另一部分為已知環(huán)境中障礙物形成的斥力場。人工勢場中的斥力場和引力場均為矢量，斥力場矢量方向背離障礙物位置，引力場矢量方向指向目標(biāo)位置。最后通過求合力來控制機(jī)器人的運(yùn)動。

2 人工勢場蟻群算法

螞蟻在覓食過程中，一方面能夠在所經(jīng)過的路徑上留下一種叫信息素的物質(zhì)，另一方面能夠感知路徑上信息素的強(qiáng)度并沿著信息素強(qiáng)度高的路徑運(yùn)動。大量螞蟻組成的群體覓食行為便體現(xiàn)為一種正反饋現(xiàn)象：越短的路徑走過的螞蟻就越多，留下的信息素濃度就越高，后面的螞蟻選擇該路徑的概率就越大，從而達(dá)到以最短路徑搜索食物的目的。但在路徑規(guī)劃初期的信息素濃度差異較小，蟻群算法正反饋作用不明顯，路徑選擇存在盲目性，較為耗時，收斂速度較慢，在復(fù)雜的環(huán)境下易陷入局部最優(yōu)，出現(xiàn)早熟收斂的情況[9-14]。人工勢場算法的勢場力可引導(dǎo)機(jī)器人朝目標(biāo)柵格前進(jìn)，且其只受環(huán)境信息的影響，路徑搜索初期和后期不存在差異[15]。

本文融合兩者的優(yōu)點(diǎn)，提出一種新的算法——人工勢場蟻群算法：把人工勢場算法的勢場力引入到蟻群算法的啟發(fā)信息中，勢場力啟發(fā)信息可以降低路徑規(guī)劃初期蟻群算法的正反饋作用不明顯導(dǎo)致的搜索的盲目性。但考慮到人工勢場算法易出現(xiàn)目標(biāo)不可達(dá)及易陷入局部穩(wěn)定的問題，且隨著迭代次數(shù)的增加，蟻群的正反饋作用增加，引入勢場力啟發(fā)信息的影響參數(shù)，該參數(shù)會隨著迭代次數(shù)的增加，逐漸減弱人工勢場算法的影響，突出蟻群算法的正反饋作用。提高了算法的收斂速度，解決了易陷入局部最優(yōu)的缺點(diǎn)，同時避免了目標(biāo)不可達(dá)和局部穩(wěn)定情況的產(chǎn)生。

2.1 勢場力信息

在傳統(tǒng)蟻群算法的啟發(fā)信息中引入人工勢場算法的勢場力啟發(fā)信息，人工勢場力信息使機(jī)器人在移動過程中迅速地規(guī)避障礙物，向著目標(biāo)柵格移動，勢場力啟發(fā)信息是由機(jī)器人受到的人工勢場中勢場合力構(gòu)造而成，該部分啟發(fā)信息可為：

式中，a＞1為常數(shù)，F(xiàn)tot表示移動機(jī)器人受到的勢場合力，θ表示勢場合力Ftot與移動機(jī)器人可行路徑方向的夾角。對啟發(fā)信息中的勢場合力Ftot理論推導(dǎo)如下：假設(shè)移動機(jī)器人當(dāng)前所處位置為P，目標(biāo)位置為G，本文斥力勢場函數(shù)可用式：

與傳統(tǒng)的斥力函數(shù)：

相比，引入了當(dāng)前位置與目標(biāo)位置的距離，在新斥力函數(shù)的作用下，保證了整個勢場在目標(biāo)位置處全局最小。從而解決了人工勢場算法易陷入目標(biāo)不可達(dá)和局部穩(wěn)定的問題。

其中

圖1 新的勢場函數(shù)下機(jī)器人受力示意圖

吸引勢場函數(shù)為：

機(jī)器人在復(fù)雜工作環(huán)境移動時，在勢場合力的作用下快速規(guī)避障礙物向著目標(biāo)位置移動，與蟻群算法中的距離啟發(fā)信息結(jié)合，能夠更加快速地實現(xiàn)路徑規(guī)劃目的。

2.2 勢場蟻群算法的勢場力分析

由勢場蟻群算法理論可知，機(jī)器人在柵格環(huán)境移動過程中，一方面受到機(jī)器人與目標(biāo)位置的啟發(fā)作用，另一方面受到人工勢場中的勢場力作用。針對不同柵格環(huán)境下機(jī)器人與障礙物位置關(guān)系，分別對機(jī)器人進(jìn)行受力分析，具體分析如圖2。

根據(jù)柵格環(huán)境模型理論可知，機(jī)器人在自由柵格內(nèi)進(jìn)行下一步移動時有八個方向可供選擇，為研究方便僅討論比較兩個最優(yōu)可行路徑方向。圖中①，②是其可行的方向，θ1，θ2為合力與可行方向的夾角。

圖2（A），當(dāng)前位置與目標(biāo)位置之間沒有障礙物，此時所受的勢場合力僅為目標(biāo)位置產(chǎn)生的吸引力，由式（1）及（6）可知，合力與可行路徑方向夾角越小，ηF(t)值越小，對應(yīng)的轉(zhuǎn)移概率越大，機(jī)器人更有可能選擇該路徑，對機(jī)器人受力分析，勢場合力Ftot與兩條可行路徑的夾角θ1＜θ2，則其下一步沿著路徑①的方向移動。

圖2（B）和（C），機(jī)器人當(dāng)前位置與目標(biāo)位置之間存在簡單的障礙物，對機(jī)器人受力分析，勢場引力與斥力的合力Ftot與兩條可行路徑的夾角θ1＜θ2，則機(jī)器人在勢場力的啟發(fā)下沿著更優(yōu)路徑①的方向移動。

圖2（D），機(jī)器人當(dāng)前位置與目標(biāo)位置之間存在較為復(fù)雜的障礙物，障礙物距離機(jī)器人當(dāng)前位置最近的有兩個位置，均對機(jī)器人產(chǎn)生斥力作用，則勢場斥力合力Frep再與勢場引力Fatt合成形成綜合勢場力Ftot，經(jīng)分析知Ftot與兩可行路徑的夾角θ1＜θ2，在勢場力的引導(dǎo)下機(jī)器人向著更優(yōu)路徑①的方向移動。

經(jīng)過上述理論分析，勢場蟻群算法的勢場力可以引導(dǎo)機(jī)器人快速地避過障礙物朝目標(biāo)位置移動。

2.3 勢場力啟發(fā)信息影響系數(shù)χ

勢場力啟發(fā)信息影響系數(shù)χ主要用來加強(qiáng)或降低人工勢場力啟發(fā)信息在路徑規(guī)劃過程中的影響作用，其值隨蟻群迭代次數(shù)的增加而減小，為下式：

式中，Nmax為最大迭代次數(shù)，Nm為當(dāng)前迭代次數(shù)。由公式（16）看出：在勢場力啟發(fā)信息影響系數(shù)χ的作用下，勢場蟻群算法在路徑規(guī)劃初期的啟發(fā)信息主要依靠勢場力啟發(fā)信息，這樣既能使螞蟻迅速找到到達(dá)目標(biāo)位置的次優(yōu)解，又能避免由于初期缺乏信息素而產(chǎn)生大量劣質(zhì)解的情況。隨著螞蟻循環(huán)次數(shù)的增加，需要降低勢場力啟發(fā)信息的作用，否則螞蟻過度集中于勢場分布的梯度方向上，導(dǎo)致這些路徑上的信息素濃度過強(qiáng)，從而減弱對更為優(yōu)質(zhì)路徑的探索，路徑搜索過早收斂，出現(xiàn)早熟現(xiàn)象。勢場力函數(shù)影響系數(shù)χ同樣能夠有效地解決這種現(xiàn)象。

2.4 傳統(tǒng)蟻群算法啟發(fā)信息

傳統(tǒng)蟻群算法啟發(fā)信息ηd(t)，如下：

人工勢場蟻群算法的綜合啟發(fā)信息構(gòu)造如下：

在綜合啟發(fā)信息ηij(t)作用下，機(jī)器人可有效避免與障礙物的碰撞，避免在初期盲目的搜索，機(jī)器人能快速地搜索路徑。

3 算法步驟

勢場蟻群算法應(yīng)用于路徑規(guī)劃的具體實現(xiàn)步驟為：

步驟1基于柵格法對機(jī)器人的移動空間進(jìn)行環(huán)境建模，設(shè)置機(jī)器人起始柵格、目標(biāo)柵格及障礙物柵格。

步驟2初始化勢場蟻群算法相關(guān)參數(shù)，包括人工勢場的引力場常量Katt、斥力場常量Krep、障礙物斥力的作用范圍d0；蟻群搜索機(jī)制的螞蟻數(shù)量m、迭代次數(shù)Nmax、啟發(fā)因子α,β、信息素濃度Q以及信息素濃度揮發(fā)系數(shù)ρ等。

步驟3將m只螞蟻放置于起始位置。

步驟4螞蟻在公式（17）的綜合啟發(fā)信息下，根據(jù)轉(zhuǎn)移概率規(guī)則公式（1）選擇下一步到達(dá)位置，將該位置存儲在禁忌表tabuk中。

步驟5判斷m只螞蟻是否到達(dá)目標(biāo)位置，若是，計算每只螞蟻搜索路徑長度，找出當(dāng)前搜索的最優(yōu)路徑，否則轉(zhuǎn)向步驟4。

步驟6 按照公式（3）、（4）和（5）對每條路徑上的信息素濃度進(jìn)行更新。

步驟7判斷是否達(dá)到最大迭代次數(shù)，若已達(dá)到則算法終止，輸出各條搜索路徑長度，找出最優(yōu)路徑，否則轉(zhuǎn)向步驟3。

4 仿真

為了驗證改進(jìn)后的勢場蟻群算法理論在路徑規(guī)劃上的可行性與優(yōu)越性，在20×20柵格環(huán)境模型下對該算法進(jìn)行仿真，并與常規(guī)勢場蟻群算法和基本蟻群算法進(jìn)行比較，仿真過程中的相關(guān)參數(shù)采用蟻群算法路徑規(guī)劃選定的參數(shù)m=20，α=1，β=7，ρ=0.3，Q=100，基于勢場蟻群算法、蟻群算法、常規(guī)蟻群算法在相同環(huán)境下的路徑規(guī)劃仿真圖及收斂曲線如圖3～8所示。

圖3 基本蟻群算法的爬行圖

圖4 基本蟻群算法的收斂曲線

圖5 文獻(xiàn)[4]提出的勢場蟻群算法的爬行路徑圖

圖6 文獻(xiàn)[4]提出的勢場蟻群算法的收斂曲線

圖7 本文的人工勢場蟻群算法的爬行圖

圖8 本文的人工勢場蟻群算法的收斂曲線

為了便于比較勢場蟻群算法的優(yōu)越性，在兩種柵格環(huán)境下多次實驗，記錄相關(guān)數(shù)據(jù)。

表1 相同柵格環(huán)境下的算法相關(guān)數(shù)據(jù)

通過仿真圖及記錄的相關(guān)數(shù)據(jù)可以看出，論文中提及的算法在路徑規(guī)劃上能夠更快地在復(fù)雜環(huán)境下無碰撞搜索到最優(yōu)路徑，進(jìn)一步論證了勢場蟻群算法理論分析的正確性。

5 結(jié)論

針對人工勢場法、蟻群算法的不足，本文提出了勢場蟻群算法。該算法改進(jìn)了勢場算法中的斥力函數(shù)的構(gòu)成，利用人工勢場中的勢場力、蟻群算法中機(jī)器人與目標(biāo)位置的距離及勢場力啟發(fā)信息影響系數(shù)來重新構(gòu)造綜合啟發(fā)信息，并以蟻群搜索機(jī)制進(jìn)行全局路徑規(guī)劃。新啟發(fā)信息可有效地降低路徑規(guī)劃初期蟻群搜索的隨機(jī)性和盲目性，使機(jī)器人快速朝目標(biāo)位置移動，隨著迭代次數(shù)的增多，新啟發(fā)信息中的勢場力影響系數(shù)可有效減弱勢場力的作用，突出蟻群算法的正反饋作用。仿真結(jié)果表明勢場蟻群算法路徑規(guī)劃能找到更優(yōu)路徑和收斂速度更快。

[1]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2012，29（4）：1201-1206.

[2]那日蘇，李強(qiáng)，烏力吉.基于仿生學(xué)改進(jìn)的粒子群算法[J].計算機(jī)工程與應(yīng)用，2014，50（6）：61-63.

[3]Bu Q，Wang Z，Tong X.An improved genetic algorithm for searching for pollution sources[J].水科學(xué)與水工程，2013，6（4）.

[4]羅德林，吳順祥.基于勢場蟻群算法的機(jī)器人路徑規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2010（6）：1277-1280.

[5]王強(qiáng)，張安，吳忠杰.改進(jìn)人工勢場法與模擬退火算法的無人機(jī)航路規(guī)劃[J].火力與指揮控制，2014，39（8）：70-73.

[6]李擎，王麗君.一種基于遺傳算法參數(shù)優(yōu)化的改進(jìn)人工勢場法[J].北京科技大學(xué)學(xué)報，2012，34（2）：202-206.

[7]楊帆，胡春平，顏學(xué)峰.基于蟻群系統(tǒng)的參數(shù)自適應(yīng)粒子群算法及其應(yīng)用[J].控制理論與應(yīng)用，2010，11：1479-1488.

[8]歐陽鑫玉，楊曙光.基于勢場柵格法的移動機(jī)器人避障路徑規(guī)劃[J].控制工程，2014（1）.

[9]王越，葉秋冬.蟻群算法在求解最短路徑問題上的改進(jìn)策略[J].計算機(jī)工程與應(yīng)用，2012，48（13）：35-38.

[10]丁博，于曉洋，孫立鐫.基于遺傳-蟻群算法的CAD產(chǎn)品快速建模[J].計算機(jī)工程與應(yīng)用，2013，49（15）：10-13.

[11]柳長安，鄢小虎.基于改進(jìn)蟻群算法的移動機(jī)器人動態(tài)路徑規(guī)劃方法[J].電子學(xué)報，2011，39（5）：1220-1224.

[12]周之平，華路.復(fù)雜環(huán)境路徑規(guī)劃的改進(jìn)蟻群算法[J].計算機(jī)工程與設(shè)計，2011，32（5）：1773-1776.

[13]何少佳，劉子揚(yáng).基于慣性蟻群算法的機(jī)器人路徑規(guī)劃[J].計算機(jī)工程與應(yīng)用，2012，48（15）：245-248.

[14]張殿富，劉福.基于人工勢場法的路徑規(guī)劃方法研究及展望[J].計算機(jī)工程與科學(xué)，2013，35（6）：88-95.

[15]于振中，閆繼宏，趙杰，等.改進(jìn)人工勢場法的移動機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報，2011，43（1）：50-55.