劉學芳, 曾國輝, 劉 瑾

(上海工程技術(shù)大學 電子電氣工程學院,上海 201620)

0 引 言

路徑規(guī)劃是移動機器人研究領域的一個重要技術(shù),是在有障礙物的空間中,按照一定標準規(guī)劃一條從起點到終點的最優(yōu)或者近似最優(yōu)的無碰撞路徑[1,2]。機器人的路徑規(guī)劃主要有全局路徑規(guī)劃和局部路徑規(guī)劃[3～7]。

針對機器人路徑規(guī)劃,國內(nèi)外學者進行了不少研究。文獻[8]提出了一種改進的動態(tài)局部搜索蟻群優(yōu)化算法(dynamic local search ant colony optimization algorithm,DLACA),不同路徑使用不同信息素更新策略,提高了解的質(zhì)量。文獻[9]提出了根據(jù)目標點自適應調(diào)整啟發(fā)函數(shù),借鑒狼群分配機制對信息素進行更新,結(jié)合粒子群算法優(yōu)化蟻群算法參數(shù)的改進蟻群算法路徑規(guī)劃，但該方法搜索時間較長,容易陷入局部最優(yōu)。文獻[10]利用粒子群算法個體加權(quán)平均值并加入慣性權(quán)重提出了一種改進粒子群路徑優(yōu)化算法,但該算法搜索到最優(yōu)解時迭代次數(shù)較多,搜索時間較長。

在解決路徑規(guī)劃上,蟻群算法具有易于與其他算法融合、速度快、精度高、快速找到擬最優(yōu)解[12]等優(yōu)點,與其他算法相比具有顯著優(yōu)勢,但容易陷入局部最優(yōu)。人工勢場法是一種虛擬力算法[13]，它模仿勢力場中引力和斥力對機器人的作用,如將障礙物視為斥力,最終目標點視為引力,建立函數(shù)進行機器人路徑規(guī)劃，方法具有計算量小,結(jié)構(gòu)簡單,便于控制[14],可以規(guī)劃出一條平滑的軌跡路線等優(yōu)點。

將蟻群算法和人工勢場法兩種方法進行融合,提出一種結(jié)合人工勢場和蟻群算法的移動機器人路徑規(guī)劃。提高了算法全局搜索能力,加快收斂速度。

1 環(huán)境建模

1.1 柵格法

圖1 環(huán)境模型與人工勢場下機器人受力分析

1.2 人工勢場法

人工勢場法是一種虛擬力方法,其基本思想是將被控對象在環(huán)境中的運動虛擬為在受力場中的運動,環(huán)境中的障礙物對機器人的運動產(chǎn)生斥力,目標對機器人產(chǎn)生引力,引力和斥力構(gòu)成的合力控制機器人的運動方向。

假設機器人當前所處位置為P,如圖1(b)所示,機器人受到障礙物的排斥力(Frep)和目標的吸引力(Katt),其矢量合力(Ftot)為機器人運動方向

(1)

(2)

Ftot(P)=Fatt(P)+Frep(P)

(3)

(4)

2 傳統(tǒng)蟻群算法

(5)

式中α為信息素啟發(fā)因子,反映了螞蟻在尋找食物過程中殘留在路徑上的信息濃度對當前螞蟻所起的作用,其值越大,表示當前螞蟻選擇此路的可行性越大；β為啟發(fā)函數(shù)因子,表示能見度的重要性。allowedk為螞蟻k下一步可以選擇的路徑的數(shù)組。τij(t)為節(jié)點i和j之間的信息素濃度,ηij(t)為螞蟻k從節(jié)點i到節(jié)點j的啟發(fā)信息

(6)

在搜索的初始階段,蟻群進行盲目搜索。當所有螞蟻完成一次尋找食物時,對各路徑上的信息素更新

(7)

式中ρ為信息素揮發(fā)因子,其數(shù)值通常為0<ρ<1,m為蟻群數(shù)量,τk為第k只螞蟻在當前迭代過程中留下的信息素,可表示為

(8)

式中Q為常量,為螞蟻信息素強度,在一定程度上影響算法收斂速度；Lk為螞蟻k在本次循環(huán)中所走過的路徑總長度。

3 改進蟻群算法

3.1 激勵函數(shù)

為了使機器人更傾向于選擇障礙物包含較少的區(qū)域,螞蟻k從i柵格轉(zhuǎn)移到j柵格,定義激勵函數(shù)

(9)

因此,改進蟻群算法的狀態(tài)轉(zhuǎn)移概率為

(10)

式中γ為激勵函數(shù)影響因子。

3.2 信息素的分配機制改進

傳統(tǒng)蟻群算法中,當所有螞蟻走完路程后才再更新信息素。信息素的增加由所有螞蟻上一輪所走的路徑?jīng)Q定。這種信息素更新機制中,所有螞蟻散發(fā)的信息素無論好壞都參與到信息素更新中。實際上,路徑較長的螞蟻所分泌的信息素對蟻群起到誤導作用,導致算法收斂速度較慢。

改進的信息素分配機制將增強優(yōu)秀螞蟻的影響,降低不好的螞蟻影響程度。具體思路如下：當所有螞蟻尋找到食物以后,對所有螞蟻走過的路徑長度按照從小到大的順序重新排序。對優(yōu)秀螞蟻在其所走路徑上的信息量更新,對中等路徑長度的信息素量減少比例更新,對陷入局部最優(yōu)解的螞蟻路徑取消更新信息素,并將路徑長度設為無窮大,更新方式如下

(11)

(12)

3.3 改進蟻群算法路徑規(guī)劃流程

圖2 改進蟻群算法路徑規(guī)劃流程

4 仿真分析

為了驗證本文提出改進蟻群算法的有效性和優(yōu)越性,在Python3.6環(huán)境下進行機器人路徑規(guī)劃算法仿真。機器人初始位置為(0,0),目標點位置為(19,19)蟻群算法參數(shù)選?。害?1.1,信息素影響因子；β=12,啟發(fā)式影響因子；γ=0.2,激勵函數(shù)影響因子；ρ=0.5,信息素蒸發(fā)系數(shù)；m=20,螞蟻數(shù)量。算法的最大迭代次數(shù)設置為100次。仿真結(jié)果如圖3～圖4。

圖3和圖4為改進蟻群算法和傳統(tǒng)蟻群算法仿真路線,以及二種算法最短路徑長度與迭代次數(shù)變化曲線。本文算法和傳統(tǒng)蟻群算法的最短路徑長度分別為27.455和34.870,迭代次數(shù)分別為45和18?？梢钥闯觯罕疚乃惴ㄔ诼窂介L度和迭代次數(shù)上具有明顯優(yōu)勢。從圖4收斂速度明顯加快,搜索全局路徑長度明顯減少。

圖3 二種算法仿真結(jié)果

圖4 二種算法收斂曲線

5 結(jié) 論

本文提出基于人工勢場環(huán)境下改進蟻群算法用于解決機器人路勁規(guī)劃問題。利用人工勢場建立啟發(fā)信息強度,可以有效降低蟻群在起始階段搜索的盲目性和隨機性。引入激勵函數(shù),有助于增強路徑平滑性,降低搜索過程的死鎖現(xiàn)象；改進信息素的更新機制,增強了優(yōu)秀螞蟻信息素影響程度,降低了路徑較長螞蟻對全局搜索的阻礙。仿真結(jié)果表明:本文提出的改進蟻群算法較傳統(tǒng)蟻群算法能迅速找到全局最優(yōu)解,提高了算法全局搜索能力。