何 雨， 張志安， 韓明明， 陳慶武， 黃學功

(南京理工大學 機械工程學院， 江蘇 南京 210094)

近年來， 移動機器人發(fā)展迅速， 其中運動靈活的全向移動機器人脫穎而出， 被廣泛應用于各類平臺. 路徑規(guī)劃技術(shù)作為移動機器人智能化的重要象征， 掀起了國內(nèi)外的研究熱潮. 所謂機器人路徑規(guī)劃， 就是要找到一個從起點到目標點機器人能夠安全繞過障礙且沒有碰撞的路徑[1]. 為此， 國內(nèi)外的研究學者們提出了很多機器人路徑規(guī)劃方法， 例如人工勢場、 遺傳算法、 粒子算法、 蟻群算法等[2].

蟻群算法是模擬螞蟻覓食過程中可以找到最短路徑的行為而設計的一種仿生算法[3]. 近些年來， 學者們對于蟻群算法在機器人路徑規(guī)劃上的研究取得了很好的成果. 如文獻[4]將蟻群算法應用于智能水下機器人的路徑規(guī)劃中， 使水下機器人能夠高效地避過障礙尋找到最優(yōu)路徑. 文獻[5]將蟻群算法應用于受災現(xiàn)場的搜救機器人路徑規(guī)劃中， 使得其在復雜的障礙環(huán)境中也能正確到達目標點.

傳統(tǒng)的自動導航機器人主要是在裝備有電磁或光學等自動導引裝置上沿著導引路徑行駛, 這樣的機器人對于外界環(huán)境要求較高， 適應性較差. 本文將蟻群算法應用于全向移動的自動導航機器人的路徑規(guī)劃中， 在算法上為該機器人提供一種可行的方案. 同時本文通過理論分析， 在傳統(tǒng)的蟻群算法背景下， 對原有算法進行改進， 并且對蟻群算法中的關(guān)鍵參數(shù)進行了篩選優(yōu)化， 最后通過仿真軟件進行對比分析， 驗證了算法的可行性.

1 問題描述與環(huán)境建模

環(huán)境建模的方法有很多， 例如可視圖法[6]、 拓撲法[7]、 自由空間法[8]、 柵格法[9]等等. 柵格法結(jié)構(gòu)簡單， 適用性強， 因此本文將選取柵格法來構(gòu)建環(huán)境空間. 對于本文研究的機器人來說， 活動空間可以為任意二維地形， 且在該空間中存在著有限靜態(tài)障礙物,其中障礙物的位置、 大小已知， 且忽略障礙物高度.

假定序號為i的柵格對應的坐標為(xi,yi)， 假設每行格數(shù)為Nx， 每列格數(shù)為Ny， 令左上角第一個柵格的序號為1， 取每個柵格的中點為坐標點， 則序號為1的柵格坐標為(0.5,4.5)， 序號為2的柵格坐標為(1.5,4.5)， 序號為3的柵格坐標為(2.5,4.5)， 依此類推， 柵格坐標與序號的對應關(guān)系為

圖 1 帶障礙的柵格環(huán)境模型Fig.1 The grid environment model with obstacles

(1)

由于環(huán)境空間存在著靜態(tài)障礙物的分布， 所以地圖需要區(qū)分存在障礙物和沒有障礙物的環(huán)境. 在柵格法中， 如果某一柵格內(nèi)不含任何障礙物， 則稱此柵格為可行柵格， 用白色柵格表示； 如果存在障礙物， 則稱其為障礙柵格， 在柵格圖中用黑色柵格表示， 如圖 1 所示， 白色柵格處機器人可以正常通過， 黑色柵格為障礙柵格， 機器人在此處不可通行.

2 蟻群算法及其改進

2.1 蟻群算法的基本原理

蟻群算法是從螞蟻群體的覓食行為中得到啟發(fā)， 通過轉(zhuǎn)移概率來引導螞蟻群體從當前位置移動到下一個目標點， 同時通過信息素的揮發(fā)與更新,保留較優(yōu)路徑在后續(xù)迭代中的優(yōu)勢. 在基本蟻群算法中， 螞蟻k在覓食過程中， 從節(jié)點i轉(zhuǎn)移到節(jié)點j的轉(zhuǎn)移概率

(2)

螞蟻完成一次循環(huán)后進行信息素的更新， 各路徑上的信息素更新規(guī)則為

τij(t+1)=(1-ρ)τij(t)+Δτij(t),

(3)

(4)

式中：ρ為信息素揮發(fā)系數(shù)， (1-ρ)表示信息素殘留系數(shù)， 主要作用是防止信息素的無限積累， 一般取值為 (0,1]；m為螞蟻群體的個數(shù)， 可根據(jù)實際情況的大小來選擇螞蟻個數(shù)； Δτij(t)是第k只螞蟻在此次迭代中， 在所經(jīng)過的路徑上留下的信息素的量， 在一般情況下會默認為螞蟻在每一次的迭代中所釋放的信息素的總量是固定的. 為了提高蟻群的全局搜索能力， 信息素的計算采用如下模型， 即

(5)

式中：Q為一個定值， 表示的是信息素的總量；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度.

2.2 蟻群算法的改進

2.2.1 轉(zhuǎn)移概率的改進

圖 2 算法步驟流程圖Fig.2 The flow chart of the algorithm steps

此外， 通過轉(zhuǎn)移概率公式計算出當前柵格周圍的可行柵格的概率之后， 選用輪盤賭法來選擇下一步的柵格點. 所謂輪盤賭法， 就是將各個選擇概率做累計概率統(tǒng)計,然后產(chǎn)生一個隨機數(shù),該隨機數(shù)所在累計概率對應的節(jié)點作為螞蟻下一選擇的節(jié)點,雖然不是概率最大的節(jié)點才能被選中,但概率越大者被選中的幾率也越大[11]. 這樣可以避免蟻群算法陷入局部最優(yōu)值.

2.2.2 蟻群算法參數(shù)優(yōu)化

在進行蟻群算法的路徑規(guī)劃時， 算法中相關(guān)參數(shù)的設定是否恰當對算法性能的體現(xiàn)至關(guān)重要. 參數(shù)的優(yōu)化是一項必不可少的工作， 本文的第4節(jié)將重點討論蟻群算法的關(guān)鍵參數(shù)對于算法的影響.

3 算法的實現(xiàn)

3.1 算法步驟

對基本蟻群算法做出相應改進， 將改進算法運用到本文的路徑規(guī)劃中， 算法步驟如下：

1) 首先對算法進行初始化， 同時將環(huán)境地圖柵格化， 設置初始位置和終點位置.

2) 初始化信息素矩陣， 初始化鄰接矩陣， 初始化禁忌表.

3) 每只螞蟻根據(jù)概率轉(zhuǎn)移公式計算下一個可以前往柵格點的轉(zhuǎn)移概率,并利用輪盤賭法選擇下一步的初始點. 把選定的柵格節(jié)點序號加入到螞蟻的路徑表中, 并且更新禁忌表和螞蟻的路徑長度.

4) 更新路徑和路徑長度， 直至螞蟻到達終點位置， 輸出爬行路線.

5) 重復步驟3)～4)， 直到某一代m只螞蟻迭代結(jié)束.

6) 按照算法的信息素濃度更新公式， 對其經(jīng)過路段上的信息濃度進行更新， 同時更新信息素矩陣， 并將迭代次數(shù)加1.

7) 重復步驟3)～6)， 直到到達最大迭代次數(shù).

8) 將最終結(jié)果進行輸出， 算法結(jié)束. 算法流程如圖 2 所示.

3.2 仿真實驗與結(jié)果

通過上述分析， 為驗證算法的性能， 通過軟件編寫仿真程序， 仿真中各參數(shù)的設定為： 螞蟻的個數(shù)m=50； 啟發(fā)式因子α=1； 期望式因子β=10 ； 信息素揮發(fā)系數(shù)ρ=0.4； 信息素增加強度系數(shù)Q=1； 最大迭代次數(shù)為N=100； 信息素初始濃度Δτij(t)為1 . 利用柵格法構(gòu)建環(huán)境地圖信息， 環(huán)境規(guī)模設定為20*20柵格,起始柵格和目標柵格序號1和400. 為了更好地測試算法的適應性和環(huán)境兼容性， 分別在簡單、 中等和復雜3種環(huán)境下進行仿真研究. 在不同的柵格環(huán)境中， 算法性能曲線如圖 3～圖 5 所示.

圖 3 簡單環(huán)境中的算法曲線Fig.3 The algorithm curves in the simple environment

圖 4 中等環(huán)境中的算法曲線Fig.4 The algorithm curves in the medium environment

圖 5 復雜環(huán)境中的算法曲線Fig.5 The algorithm curves in the complex environment

從上述仿真結(jié)果可知， 在簡單、 中等、 復雜這3種不同的環(huán)境下， 算法都找到了從始發(fā)點行進到終點的路徑， 且最終收斂. 同時可知算法針對復雜地圖也具有較強的適應能力.

4 參數(shù)的優(yōu)化

正如前面所說， 蟻群算法參數(shù)至關(guān)重要， 參數(shù)的選取是否合適會直接影響算法性能， 由于目前還沒有完善的理論依據(jù)來確定最優(yōu)的組合參數(shù)， 各參數(shù)之間也沒有明確的關(guān)系， 因此下面將針對不同的環(huán)境模型， 根據(jù)經(jīng)驗選取參數(shù)范圍， 通過比較仿真來進行啟發(fā)因子α、 期望啟發(fā)因子β、 揮發(fā)因子ρ以及螞蟻數(shù)目m這4個關(guān)鍵參數(shù)對算法性能的影響分析.

4.1 啟發(fā)因子

啟發(fā)因子α反映的是路徑上積累的信息素量對路徑搜索的影響. 若α值較高， 則削弱了算法的隨機性； 若α值較低， 則收斂速度會有所下降. 為了尋找到最佳啟發(fā)因子的值， 仿真時設定β=10，ρ=0.4，m=50， 然后分析α分別取1, 1.5, 2, 3, 4, 5, 6, 7時對算法性能的影響. 仿真結(jié)果如圖 6 所示.

圖 6 啟發(fā)因子對算法性能的影響Fig.6 The effects of heuristic factor on the performance of the algorithm

從仿真結(jié)果中可以看出， 當保持其他參數(shù)不變的時候， 在簡單環(huán)境中， 啟發(fā)因子的變化對于最優(yōu)路徑長度的距離影響不大； 對于中等和復雜環(huán)境來說，α值較小時更易獲得最短路徑的長度， 并且隨著α值的增大， 螞蟻越難以獲得最優(yōu)軌跡. 隨著啟發(fā)因子的增大， 在簡單， 中等和復雜環(huán)境下的迭代次數(shù)開始階段都是立即下降的， 中間階段隨著α值的增大， 迭代次數(shù)略有起伏， 但整體呈下降趨勢. 綜合來看，α值取1.5時， 算法性能最優(yōu).

4.2 期望啟發(fā)因子

期望啟發(fā)因子β反映的是啟發(fā)式信息對路徑搜索的影響， 隨著β值的增大， 算法的隨機性降低；β值越小， 越容易陷入純粹的隨機搜索， 不利于算法的收斂性. 為了尋找到最佳的期望啟發(fā)因子的值， 保持其他參數(shù)不變， 仿真時設α=1，ρ=0.4，m=50 ， 分析β分別取3, 5, 7, 8, 9, 10, 11, 12時對算法性能的影響. 仿真結(jié)果如圖 7 所示.

圖 7 期望啟發(fā)因子對算法性能的影響Fig.7 The effects of expectation inspiring factor on the performance of the algorithm

通過仿真結(jié)果可以看出， 對于路徑長度來說，β值的變化對于簡單和復雜環(huán)境的影響很小， 在中等環(huán)境中， 當β值上升到5以后， 路徑長度保持不變. 對于迭代次數(shù)來說， 曲線雖略有起伏， 但是整體是呈現(xiàn)下降趨勢的. 由圖7分析可知， 在β值取11的時候算法性能最優(yōu).

4.3 揮發(fā)因子

揮發(fā)因子ρ表示的是信息素揮發(fā)系數(shù)對于算法的影響， 若ρ值過大， 會使蟻群的搜索空間變??； 若ρ值過小， 算法的收斂速度又會降低. 為了找到最佳的揮發(fā)因子的值， 仿真時設β=10，α=1，m=50， 分析ρ分別取0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9時對算法性能的影響. 仿真結(jié)果如圖 8 所示.

圖 8 揮發(fā)因子對算法性能的影響Fig.8 The effects of volatilization factor on the performance of the algorithm

從仿真結(jié)果可以看出， 在3種不同的環(huán)境下， 當揮發(fā)因子ρ取不同值時， 算法最優(yōu)路徑的長度基本保持不變； 迭代次數(shù)隨著ρ值增大而減少， 最終趨于平緩. 綜合來看，ρ的最佳取值為0.9.

4.4 螞蟻數(shù)目

仿真時蟻群算法需要螞蟻群體之間相互協(xié)作來搜索路徑. 隨著螞蟻數(shù)目m的增大， 收斂速度會降低； 若m值較低， 則不利于算法的全局搜索能力. 為了選取最佳的螞蟻數(shù)目， 在仿真中取α=1，β=10，ρ=0.4， 迭代次數(shù)k=80， 分別分析螞蟻數(shù)目m=10, 30, 50, 80, 100, 120，150時對算法性能的影響. 仿真結(jié)果如圖 9 所示.

圖 9 螞蟻數(shù)目對算法性能的影響Fig.9 The effects of the number of ants on the performance of the algorithm

從仿真結(jié)果可以看出， 對于簡單和復雜環(huán)境來說， 隨著螞蟻數(shù)目m值的不斷增加， 算法的最優(yōu)路徑長度下降到一定值后保持不變， 且對于中等環(huán)境的路徑長度影響不大. 對于迭代次數(shù)來說， 在3種不同環(huán)境下， 隨著m值的增大， 開始階段迭代次數(shù)都是立即減小， 之后， 略有起伏后趨于平緩. 綜合來看，m的最佳取值為80.

4.5 參數(shù)最佳匹配比較

綜合分析仿真結(jié)果可知， 當α=1.5,β=11,ρ=0.9,m=80時( 其余參數(shù)保持不變) ， 算法性能最好. 根據(jù)仿真分析， 對于優(yōu)化前后的路徑長度和迭代次數(shù)列出如表 1 所示的參數(shù)優(yōu)化前后算法性能對比表格.

表 1 算法性能對比

從表 1 可以看出， 雖然參數(shù)優(yōu)化前后路徑長度并沒有發(fā)生變化， 但是優(yōu)化后的算法大大降低了迭代次數(shù)， 這也證明了優(yōu)化后的參數(shù)對于算法的性能有了很大的提升， 算法收斂速度加快， 提高了算法的效率， 優(yōu)化后的算法性能更佳.

5 結(jié) 論

本文從全向移動的自動導航移動機器人入手， 結(jié)合適當?shù)穆窂揭?guī)劃算法來提高該機器人的智能化程度. 通過相應的分析研究， 選用柵格法和蟻群算法來進行機器人的路徑規(guī)劃； 并且在經(jīng)典蟻群算法的基礎(chǔ)上做出相應改進， 通過仿真驗證了算法的可行性； 通過在不同環(huán)境中的仿真證明了算法的環(huán)境適應性； 對于蟻群算法的關(guān)鍵參數(shù)進行了篩選優(yōu)化， 證明了參數(shù)優(yōu)化后的算法提高了算法的性能， 使得尋優(yōu)規(guī)劃更加合理.