基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃問題研究

牛龍輝，季野彪

（西安工程大學(xué)電子信息學(xué)院，西安710600）

1 引 言

在智能體的研究中，路徑規(guī)劃問題一直擔(dān)任著重要角色，是一個涉及智能控制、材料工程、人工智能和信息處理等相關(guān)專業(yè)學(xué)科的復(fù)雜系統(tǒng)工程[1]。機(jī)器人規(guī)劃路徑時，需要以一定的標(biāo)準(zhǔn)評判。在已知起始點(diǎn)和目標(biāo)點(diǎn)的障礙環(huán)境下，機(jī)器人需要進(jìn)行從起始點(diǎn)到目標(biāo)點(diǎn)最優(yōu)路徑的尋找，即解決機(jī)器人的路徑規(guī)劃問題。文獻(xiàn)[2]提出了一種基于粒子群優(yōu)化的路徑規(guī)劃算法，在障礙環(huán)境下對機(jī)器人進(jìn)行導(dǎo)航。首先定義一個隸屬函數(shù)來評價路徑的風(fēng)險程度，考慮風(fēng)險度和路徑距離這兩個性能優(yōu)點(diǎn)，對機(jī)器人進(jìn)行有效的路徑規(guī)劃。文獻(xiàn)[3]著重介紹和評價了模擬退火（SA）的人工勢場方法，改進(jìn)了人工勢場法中易陷入局部最優(yōu)值的缺陷。模擬退火作為一種有效的局部極小值逃逸技術(shù)，已被應(yīng)用于局部和全局路徑規(guī)劃中。文獻(xiàn)[3]針對移動機(jī)器人室內(nèi)定位技術(shù)的特點(diǎn)，在結(jié)構(gòu)化環(huán)境下開發(fā)了室內(nèi)移動機(jī)器人路徑規(guī)劃系統(tǒng)，針對路徑規(guī)劃的不足，提出了一種改進(jìn)的A*算法，能夠計算具有拐點(diǎn)、旋轉(zhuǎn)方向和最小旋轉(zhuǎn)角度的移動機(jī)器人定位。移動機(jī)器人定位試驗(yàn)表明，改進(jìn)算法不僅簡化了路徑規(guī)劃，而且可以調(diào)整機(jī)器人在拐點(diǎn)的姿態(tài)，能夠滿足機(jī)器人自主運(yùn)動的要求。采用改進(jìn)后的蟻群算法對機(jī)器人路徑規(guī)劃進(jìn)行研究，提高了路徑規(guī)劃的實(shí)現(xiàn)效率[4]。

蟻群算法在全局路徑規(guī)劃中有著極大優(yōu)勢，擁有著計算簡便，具有良好魯棒性且易與其他算法相結(jié)合的優(yōu)點(diǎn)，在此，采用改進(jìn)后的蟻群算法對機(jī)器人進(jìn)行路徑規(guī)劃，有效降低路徑長度。

2 環(huán)境建模

首先，在機(jī)器人路徑規(guī)劃前，要進(jìn)行障礙環(huán)境的建模。此處采用柵格法進(jìn)行建模，在建模前需滿足以下假設(shè)條件：考慮機(jī)器人的工作環(huán)境為二維空間，不考慮高度的影響，且障礙物處于靜止?fàn)顟B(tài)；已知機(jī)器人的起始點(diǎn)和目標(biāo)點(diǎn)，并將機(jī)器人視為質(zhì)點(diǎn)，忽略自身尺寸的影響[5]。

用黑白網(wǎng)格表示環(huán)境。黑色柵格代表障礙物，白色柵格代表可行區(qū)，矩陣中1 代表障礙物，0 代表自由柵格。建立的環(huán)境模型如圖1 所示。

圖1 柵格地圖

以機(jī)器人所在柵格為中心，機(jī)器人行走的方向節(jié)點(diǎn)共8 個，螞蟻對柵格的訪問是以訪問一個柵格的中心點(diǎn)為準(zhǔn)，如圖2 所示。

圖2 機(jī)器人運(yùn)動范圍

圖中左上角第一個柵格為序號1，向右序號逐次加一，序號1 的柵格坐標(biāo)是(0.5,19.5)，序號7 的柵格坐標(biāo)是(6.5,19.5)，以此類推序號400 的柵格坐標(biāo)為(19.5,0.5)，也就是右下角柵格。

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

3.1 基本蟻群算法

蟻群系統(tǒng)（Ant System 或 Ant Colony System）是由意大利學(xué)者Dorigo、Maniezzo 等人于20 世紀(jì) 90年代首先提出的[6]。他們對螞蟻覓食行為進(jìn)行研究時，發(fā)現(xiàn)蟻群整體處于一種智能的行為中。螞蟻在覓食過程中總是可以找到一條最短的路徑進(jìn)行食物的搬運(yùn)。這是因?yàn)橄伻簝?nèi)的螞蟻可以通過某種信息機(jī)制實(shí)現(xiàn)信息的傳遞。后又經(jīng)進(jìn)一步研究發(fā)現(xiàn)，螞蟻會在其經(jīng)過的路徑上釋放一種可稱之為“信息素”的物質(zhì)，蟻群內(nèi)的螞蟻對“信息素”具有感知能力，它們會在短時間內(nèi)找到信息素濃度較高的路徑，并在下一次搬運(yùn)食物時走信息素濃度較高的路徑，同時依舊留下信息素，形成一種正反饋的機(jī)制，這樣經(jīng)過一段時間后，整個蟻群就會沿著最短路徑到達(dá)食物源[7]。

選擇下一節(jié)點(diǎn)的具體實(shí)現(xiàn)公式為：

其中，S 代表按照AS 算法得到的下一節(jié)點(diǎn)的概率，allowedk表示當(dāng)前節(jié)點(diǎn)的可選節(jié)點(diǎn)集合。τij表示i 點(diǎn)到j(luò) 點(diǎn)的信息素量，ηij則是對應(yīng)點(diǎn)之間的啟發(fā)式量，其中表示兩點(diǎn)間的歐式距離[7]。兩點(diǎn)間距離越大，啟發(fā)式量則越小，螞蟻在節(jié)點(diǎn)i 時選擇節(jié)點(diǎn)j 的概率就會較小。α 為信息啟發(fā)式因子，表示此路徑的信息素對后續(xù)探索時螞蟻選擇此條路徑的影響程度，α 越大，后續(xù)螞蟻選擇這條路徑的概率越大，β為期望啟發(fā)式因子，反映啟發(fā)信息對螞蟻路徑選擇的影響程度。每次迭代結(jié)束，路徑信息素都要進(jìn)行更新。全局更新公式為：

其中ρ 表示信息素?fù)]發(fā)因子，τij表示i 與j 點(diǎn)之間的信息素濃度，Δτij表示i 與j 點(diǎn)之間的信息素增量，表示第k 只螞蟻在i 與j 點(diǎn)之間的信息素增量的貢獻(xiàn)量。經(jīng)典AS 算法通過迭代對信息素進(jìn)行更新來選取最優(yōu)路徑[8]。

3.2 改進(jìn)蟻群算法

在ACS 算法迭代過程中，參數(shù)對算法性能有著直接或間接影響，其中信息素?fù)]發(fā)度參數(shù)ρ 的取值會直接影響算法的收斂速度與全局搜索能力。信息素?fù)]發(fā)系數(shù)ρ 過大，會導(dǎo)致算法多樣性降低，易出現(xiàn)搜索提前停滯，但收斂速度加快。ρ 較小時，算法的收斂速度慢，但算法多樣性提高，搜索能力加強(qiáng)。所以對ρ 的選擇需要綜合考慮算法的全局搜索能力和收斂速度。

根據(jù)上述分析，固定的ρ 值存在一定的弊端，因此，構(gòu)造一個動態(tài)改變信息素?fù)]發(fā)度參數(shù)ρ 的函數(shù)如下：

式中，自變量 n 為迭代次數(shù)，σ、μ 為常數(shù)。ρ 與迭代次數(shù)n 有關(guān)，其函數(shù)曲線單調(diào)遞增。前期隨著n 的增大，ρ 曲線平緩上升；中期隨著 n 的繼續(xù)增大，ρ 曲線急速上升；到后期ρ 曲線趨于平緩。在搜索路徑前期，ρ 取較小值是為了保留最優(yōu)路徑的更多信息；在搜索的中后期，ρ 取較大值，是為了加快收斂速度。

4 仿真及分析

為驗(yàn)證本算法的有效性，在MATLAB 2014a 上進(jìn)行仿真實(shí)驗(yàn)。利用上文提到的柵格法構(gòu)建環(huán)境模型，在相同環(huán)境下比較本算法與ACS 算法的仿真結(jié)果，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

算法參數(shù)的設(shè)置如表1 所示。

表1 參數(shù)設(shè)置

障礙物條件下（設(shè)置起點(diǎn)S=49，終點(diǎn)G=369）的兩種算法的路徑規(guī)劃結(jié)果及收斂曲線分別如圖3、圖4 所示。其中實(shí)直路線代表經(jīng)典蟻群算法，點(diǎn)線路線代表改進(jìn)的蟻群算法。

圖3 路徑規(guī)劃圖

圖4 收斂曲線

從對圖3 曲線的分析中可知，經(jīng)典AS 算法在障礙環(huán)境中遇見障礙物會出現(xiàn)徘徊現(xiàn)象，無法逃離局部最優(yōu)解，其多樣性明顯較差，而本算法在快速收斂的同時，可得到全局最優(yōu)路徑。實(shí)驗(yàn)表明本改進(jìn)算法在環(huán)境障礙物條件下是可行且有效的。

從圖4 收斂曲線可見，本算法所得路徑長度明顯較經(jīng)典AS 算法短，收斂速度也不慢。綜上分析，通過在障礙環(huán)境對算法進(jìn)行實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法較經(jīng)典AS 算法具有更強(qiáng)的尋優(yōu)能力，算法多樣性明顯提高，且具有良好的準(zhǔn)確性與魯棒性，在解的質(zhì)量與收斂速度方面表現(xiàn)出更好的性能。

5 結(jié)束語

針對經(jīng)典AS 算法在路徑規(guī)劃中尋優(yōu)能力不足和算法多樣性低等問題，引入自適應(yīng)信息素?fù)]發(fā)系數(shù)，以加強(qiáng)全局尋優(yōu)能力，提高算法多樣性。仿真實(shí)驗(yàn)表明，改進(jìn)算法有效地解決了經(jīng)典AS 算法尋優(yōu)能力不足缺陷，提高算法多樣性，并具有良好的準(zhǔn)確性與魯棒性。