何 雨， 張志安， 韓明明， 陳慶武， 黃學(xué)功

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

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

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

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

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

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

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

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

(1)

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

2 蟻群算法及其改進(jìn)

2.1 蟻群算法的基本原理

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

(2)

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

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

(3)

(4)

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

(5)

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

2.2 蟻群算法的改進(jìn)

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

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

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

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

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

3 算法的實(shí)現(xiàn)

3.1 算法步驟

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

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

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

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

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

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

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

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

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

3.2 仿真實(shí)驗(yàn)與結(jié)果

通過上述分析， 為驗(yàn)證算法的性能， 通過軟件編寫仿真程序， 仿真中各參數(shù)的設(shè)定為： 螞蟻的個(gè)數(shù)m=50； 啟發(fā)式因子α=1； 期望式因子β=10 ； 信息素?fù)]發(fā)系數(shù)ρ=0.4； 信息素增加強(qiáng)度系數(shù)Q=1； 最大迭代次數(shù)為N=100； 信息素初始濃度Δτij(t)為1 . 利用柵格法構(gòu)建環(huán)境地圖信息， 環(huán)境規(guī)模設(shè)定為20*20柵格,起始柵格和目標(biāo)柵格序號(hào)1和400. 為了更好地測(cè)試算法的適應(yīng)性和環(huán)境兼容性， 分別在簡單、 中等和復(fù)雜3種環(huán)境下進(jì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 復(fù)雜環(huán)境中的算法曲線Fig.5 The algorithm curves in the complex environment

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

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

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

4.1 啟發(fā)因子

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

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

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

4.2 期望啟發(fā)因子

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

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

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

4.3 揮發(fā)因子

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

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

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

4.4 螞蟻數(shù)目

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

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

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

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

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

表 1 算法性能對(duì)比

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

5 結(jié) 論

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