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

南昌大學 信息工程學院，南昌 330031

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

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

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

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

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

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

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

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

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

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

1.2 人工勢場算法簡介

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

2 人工勢場蟻群算法

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

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

2.1 勢場力信息

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

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

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

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

其中

圖1 新的勢場函數下機器人受力示意圖

吸引勢場函數為：

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

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

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

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

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

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

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

經過上述理論分析，勢場蟻群算法的勢場力可以引導機器人快速地避過障礙物朝目標位置移動。

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

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

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

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

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

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

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

3 算法步驟

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

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

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

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

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

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

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

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

4 仿真

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

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

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

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

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

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

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

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

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

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

5 結論

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

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

[2]那日蘇，李強，烏力吉.基于仿生學改進的粒子群算法[J].計算機工程與應用，2014，50（6）：61-63.

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

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

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

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

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

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

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

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

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

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

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

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

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