勢(shì)場(chǎng)改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究

李林喜 李衛(wèi)國(guó) 任超群 王利利

摘 要：在復(fù)雜環(huán)境中工作的移動(dòng)機(jī)器人，針對(duì)其避障及路徑優(yōu)化問(wèn)題，對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法和基本蟻群優(yōu)化算法進(jìn)行了分析研究，提出了改進(jìn)的人工勢(shì)場(chǎng)蟻群算法，并利用仿真實(shí)驗(yàn)進(jìn)行了分析。結(jié)果表明，改進(jìn)后的人工勢(shì)場(chǎng)法能夠得到最優(yōu)的路徑，提高了算法的收斂性，且速度快、過(guò)程穩(wěn)定，可用于解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。

關(guān)鍵詞：移動(dòng)機(jī)器人;路徑規(guī)劃;蟻群算法;人工勢(shì)場(chǎng)

近年來(lái)，隨著人工智能技術(shù)的發(fā)展，移動(dòng)機(jī)器人作為當(dāng)前機(jī)器人領(lǐng)域的一個(gè)重要分支，在工業(yè)制造、海洋探測(cè)、家庭服務(wù)、醫(yī)療護(hù)理、資源開(kāi)發(fā)、巡檢排險(xiǎn)、航空航天和國(guó)防等諸多領(lǐng)域得到了成功的應(yīng)用。

路徑規(guī)劃是移動(dòng)機(jī)器人完成各種自主移動(dòng)任務(wù)的關(guān)鍵環(huán)節(jié)之一，是機(jī)器人領(lǐng)域的一個(gè)重要研究課題。路徑規(guī)劃簡(jiǎn)單的理解，就是讓機(jī)器人從初始位置到達(dá)目標(biāo)位置，作出最優(yōu)行走路徑應(yīng)遵循的某種性能指標(biāo)（如距離，時(shí)間等）。目前，路徑規(guī)劃的求解方法主要有人工勢(shì)場(chǎng)法和基于人工智能的啟發(fā)式方法，如蟻群算法、遺傳算法和粒子群等。蟻群算法是一種受到生物界蟻群覓食行為的啟發(fā)式搜索算法，本文為校級(jí)科研項(xiàng)目，在項(xiàng)目開(kāi)展過(guò)程中，對(duì)上述各種算法進(jìn)行反復(fù)比對(duì)實(shí)驗(yàn)，最終提出一種移動(dòng)機(jī)器人路徑規(guī)劃算法——?jiǎng)輬?chǎng)改進(jìn)的蟻群算法，并測(cè)試了其有效性和優(yōu)越性。

1 建立足球機(jī)器人路徑規(guī)劃模型

移動(dòng)機(jī)器人的路徑規(guī)劃模型如圖1所示，起始點(diǎn)為當(dāng)前移動(dòng)機(jī)器人的位置，當(dāng)機(jī)器人遇到障礙物時(shí)，在避開(kāi)障礙物，避免發(fā)生碰撞的前提下，找到一條從起始位置到目標(biāo)位置長(zhǎng)度最優(yōu)的路徑。

2 基本蟻群算法的缺點(diǎn)

基本的蟻群算法具有其不足和局限性： 相對(duì)于其他方法它的搜索時(shí)間更長(zhǎng);容易出現(xiàn)停滯（算法結(jié)束在不是最優(yōu)解或次優(yōu)解）;描述復(fù)雜問(wèn)題的能力還不夠強(qiáng)等等。對(duì)于復(fù)雜環(huán)境存在的缺陷之處主要在于：

（1）參數(shù)α、β的選擇對(duì)算法的影響。

在蟻群算法中，信息素因子α反映的前面的螞蟻所釋放的信息素對(duì)后面螞蟻尋找路徑的影響程度，如果α過(guò)大則后面螞蟻選擇其路徑的可能性過(guò)小，會(huì)導(dǎo)致搜索的隨機(jī)性喪失太多，反之則容易過(guò)早陷入局部最優(yōu)的問(wèn)題;期望啟發(fā)式因子β，是對(duì)于前期的信息對(duì)螞蟻的指導(dǎo)程度，值的大小反映尋徑過(guò)程中的預(yù)先確定因素的作用強(qiáng)度，過(guò)大會(huì)導(dǎo)致螞蟻收斂速度加快，搜索隨機(jī)性削弱，尋到局部最優(yōu)的概率增大。由于α和β在通常情況下都是給的定值，它們的影響在從整個(gè)算法的執(zhí)行過(guò)程中都是一直保持和開(kāi)始一樣的影響效果。在比較小的柵格規(guī)模下還可以滿足算法需要，但如果到了規(guī)模很大的柵格環(huán)境時(shí)，螞蟻能經(jīng)過(guò)的位置點(diǎn)會(huì)成倍上漲，這時(shí)螞蟻需要經(jīng)過(guò)的位置點(diǎn)更多，開(kāi)始給定的信息素因子可能已經(jīng)蒸發(fā)了很多，不能保證螞蟻?zhàn)哌^(guò)柵格中的任何一個(gè)位置點(diǎn)都獲得該點(diǎn)的信息素。當(dāng)再經(jīng)歷數(shù)次迭代，能獲得的信息素位置點(diǎn)越來(lái)越少，這時(shí)的蟻群算法不僅更有可能出現(xiàn)次優(yōu)解，也更容易進(jìn)入局部最優(yōu)。

（2）存在不可逆柵格情況。

當(dāng)在柵格模型下的障礙物，出現(xiàn)下圖2（a）的情況時(shí)，螞蟻可能會(huì)按照?qǐng)D上指出方向選擇可行的自由柵格，結(jié)果就會(huì)進(jìn)入無(wú)法繼續(xù)行動(dòng)的狀態(tài)，如果在算法前期出現(xiàn)這種狀態(tài)的螞蟻增多，相當(dāng)于m減小，會(huì)出現(xiàn)停滯狀態(tài)。

解決的方法就是在已知全局信息的情況下將其中的自由柵格作障礙柵格處理如圖2（b）所示。

3 基本蟻群算法的改進(jìn)

本文針對(duì)參數(shù)α和β的給定值進(jìn)行改進(jìn)。在算法執(zhí)行的開(kāi)始階段，對(duì)依靠信息素因子α的尋找路徑的方式的依賴程度還比較低，到了算法后期對(duì)其的依賴程度增高;相反的，對(duì)于期望啟發(fā)因子β，前期依賴程度較高，到算法后期主要依靠螞蟻之間的信息素傳遞來(lái)尋找路徑，對(duì)期望啟發(fā)因子的需求降低。經(jīng)上面的分析可知，我們?cè)谒惴ㄇ捌谧對(duì)律叨對(duì)两档?，以解決前期更多位置點(diǎn)得不到足夠信息素問(wèn)題;同樣道理，到算法后期，讓啟發(fā)值β降低而α升高，也就是后期讓算法利用更具有優(yōu)勢(shì)的信息素的方式尋找最佳路徑。通過(guò)上述分析，我們就是要設(shè)計(jì)一個(gè)規(guī)則讓基本蟻群算法的參數(shù)α和β在算法運(yùn)行過(guò)程中實(shí)行動(dòng)態(tài)變化的形式，在隨時(shí)間執(zhí)行的過(guò)程中，α逐漸遞增至最大值;而β則逐漸遞減至最小。我們將這個(gè)過(guò)程用數(shù)學(xué)公式敘述如下式（1）和（2）：

在上兩個(gè)式子中，m為臨界迭代次數(shù)（即螞蟻個(gè)數(shù)），NC為最大迭代次數(shù)。在本論文中取值分別為m=10;NC=100。

4 人工勢(shì)場(chǎng)的改進(jìn)蟻群算法

結(jié)合人工勢(shì)場(chǎng)法在未知環(huán)境下局部搜索的優(yōu)勢(shì)和蟻群算法在全局路徑規(guī)劃中的特點(diǎn)，用聯(lián)合啟發(fā)因子來(lái)進(jìn)一步提高機(jī)器人在路徑規(guī)劃中的效率。

蟻群中一共有m只螞蟻，當(dāng)其中的螞蟻k在第n位置Pn=r轉(zhuǎn)移到下一步位置Pn+1=s的概率依據(jù)是由下面的式子決定的

當(dāng)0≤q0≤1是一個(gè)常數(shù)，S是按照概率確定的下一個(gè)到達(dá)的位置，其概率分布是按照（2）式來(lái)確定的

其中τrsn與ηrsn分別為從Pn=r到Pn+1=s的路徑所在邊的信息素的濃度和啟發(fā)期望信息;a與β代表信息素因子和啟發(fā)期望因子的相對(duì)重要性;第k個(gè)螞蟻到下步所能允許到達(dá)的位置用allowedkn集合表示，機(jī)器人只能倒退到來(lái)時(shí)的柵格Pn-1，則說(shuō)明Pn位置是一個(gè)死路，這種情形在之后Pn這個(gè)位置將會(huì)作為障礙柵格處理，也就是上邊的凹柵格的“凸”處理方式。

第k只螞蟻在搜索路徑的過(guò)程中，對(duì)走過(guò)的邊的局部信息素更新遵照下式：

當(dāng)0<ψ≤1為一個(gè)常數(shù);τ0=mCnn為初始信息素的值;Cnn為相鄰的啟發(fā)規(guī)則產(chǎn)生的路徑的長(zhǎng)度。這個(gè)蒸發(fā)過(guò)程是為了避免對(duì)其它的螞蟻的過(guò)于強(qiáng)的吸引力，以避免迭代過(guò)早的收斂，讓螞蟻對(duì)其他路徑搜索的可能。當(dāng)m只螞蟻都已經(jīng)走完，完成一次迭代后，對(duì)所有螞蟻的路徑進(jìn)行比較從中找出最短路徑，并對(duì)這條路徑進(jìn)行一次全局信息素更新，如下式：

當(dāng)0<ρ≤1為控制信息素衰減速度的常數(shù);其中Δτrs=1Lgb，Lgb為本次迭代所找到的全局最優(yōu)路徑。

上述將人工勢(shì)場(chǎng)法和蟻群算法的改進(jìn)分別作了詳述。下面將兩種算法融合到一起，讓它們共同構(gòu)成完整的規(guī)劃過(guò)程，可得該勢(shì)場(chǎng)改進(jìn)蟻群算法的啟發(fā)信息ηrs為：

從式中得出，當(dāng)勢(shì)場(chǎng)的合力，也就是機(jī)器人處于勢(shì)場(chǎng)的局部穩(wěn)定點(diǎn)處，這時(shí)若只在人工勢(shì)場(chǎng)中，將陷在局部最優(yōu)中。但在本算法中，由于蟻群算法的加入，在這時(shí)啟發(fā)信息會(huì)為ηrsn=ηdn=1d2P，G，也就是說(shuō)當(dāng)某一位置合力Ftot=0時(shí)，ηd的啟發(fā)信息會(huì)引導(dǎo)機(jī)器人跳出局部最優(yōu)這個(gè)陷阱，繼續(xù)進(jìn)行全局最優(yōu)路徑的搜索。

以上介紹了人工勢(shì)場(chǎng)法和蟻群算法的改進(jìn)分別作了詳述。下面就要介紹一下這兩種算法如何融合到一起，讓它們共同構(gòu)成完整的規(guī)劃過(guò)程。這里就要對(duì)啟發(fā)信息ηrsn進(jìn)行構(gòu)造。

在路徑搜尋過(guò)程中，螞蟻尋找到下一個(gè)位置的啟發(fā)性信息是由兩個(gè)部分構(gòu)成，其中之一是螞蟻受環(huán)境中的勢(shì)場(chǎng)的合力，形成讓螞蟻能沿著合力的方向接近目標(biāo)的啟發(fā)信息，這部分信息為

式子里，a是大于零的常數(shù)，θ為螞蟻可行進(jìn)的方向和勢(shì)場(chǎng)的合力Ftot方向的夾角，如圖3-4所示。這是可知螞蟻會(huì)在這個(gè)合力的影響下向著與勢(shì)場(chǎng)合力方向的夾角θ較小的邊移動(dòng)到下一個(gè)自由位置。該啟發(fā)信息可以幫助機(jī)器人避碰，選擇合適路徑接近目標(biāo)位置。

剩下的一部分就是由螞蟻距目標(biāo)所在位置距離提供的。定義這一部分的啟發(fā)信息如下

再將兩者綜合在一起，便可得該勢(shì)場(chǎng)改進(jìn)蟻群算法的啟發(fā)信息ηrs為：

從式子中我們可以了解到，當(dāng)勢(shì)場(chǎng)的合力，也就是機(jī)器人處于勢(shì)場(chǎng)的局部穩(wěn)定點(diǎn)處，這時(shí)若只在人工勢(shì)場(chǎng)中，將陷在局部最優(yōu)中。但在本算法中，由于蟻群算法的加入，在這時(shí)啟發(fā)信息會(huì)為ηrsn=ηdn=1d2P，G，也就是說(shuō)當(dāng)某一位置合力Ftot=0時(shí)，ηd的啟發(fā)信息會(huì)引導(dǎo)機(jī)器人跳出局部最優(yōu)這個(gè)陷阱，繼續(xù)進(jìn)行全局最優(yōu)路徑的搜索。

5 仿真與實(shí)驗(yàn)分析

5.1 人工勢(shì)場(chǎng)蟻群算法

如圖3、圖4為人工勢(shì)場(chǎng)蟻群算法仿真圖，在迭代30次后，算法趨于穩(wěn)定，最優(yōu)路徑長(zhǎng)度在33.9258，并且在最優(yōu)路徑上。但從圖上可以看出，0-30次之間收斂曲線波動(dòng)較大，表明在收斂上存在可以改進(jìn)之處。

5.2 人工勢(shì)場(chǎng)改進(jìn)蟻群算法

如圖5、圖6所示，在迭代15次后，算法就趨于穩(wěn)定，最優(yōu)路徑長(zhǎng)度是33.9053，進(jìn)一步提高了其收斂效率，而且收斂曲線也平滑了很多，收斂效果改進(jìn)明顯。

綜上所述，人工勢(shì)場(chǎng)法的改進(jìn)蟻群算法，在收斂效率上有了明顯的提高，搜索最優(yōu)路徑時(shí)間更快更加趨于合理。該算法克服了人工勢(shì)場(chǎng)法遇到的局部最優(yōu)和目標(biāo)不可達(dá)等問(wèn)題，而且提高了算法的收斂性。

6 算法驗(yàn)證

利用此算法，機(jī)器人在實(shí)際運(yùn)行中的路徑比較平滑，但機(jī)器人行進(jìn)過(guò)程中，當(dāng)挪動(dòng)障礙物形成動(dòng)態(tài)規(guī)劃時(shí)，機(jī)器人在靠近障礙物時(shí)會(huì)出現(xiàn)震蕩前進(jìn)，但最后依然可以到達(dá)目的地。這也為以后的進(jìn)一步研究提出了改進(jìn)方向。

7 結(jié)語(yǔ)

本文針對(duì)基本蟻群算法和人工勢(shì)場(chǎng)法存在的不足，整合兩者的優(yōu)點(diǎn)，提出了人工勢(shì)場(chǎng)改進(jìn)的蟻群算法，并通過(guò)仿真實(shí)驗(yàn)和真實(shí)室內(nèi)環(huán)境下實(shí)驗(yàn)，均驗(yàn)證了其可行性。同時(shí)，也發(fā)現(xiàn)了對(duì)于動(dòng)態(tài)規(guī)劃的不足，有些地方還需要改進(jìn)。

參考文獻(xiàn)

[1]周明秀，程科，汪正霞.動(dòng)態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計(jì)算機(jī)科學(xué)， 2013，40（1）：314-316.

[2]吳晨光.基于改進(jìn)人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃及其在RobCup中的應(yīng)用[D].南京郵電大學(xué)，2012.

[3]曲寶福，王利利等. 基于勢(shì)場(chǎng)改進(jìn)蟻群算法的足球機(jī)器人路徑規(guī)劃研究[D].現(xiàn)代商貿(mào)工業(yè)，2018.

[4]高田田，張莉等.基于改進(jìn)粒子群算法的足球機(jī)器人路徑規(guī)劃[J].西安工程大學(xué)學(xué)報(bào)，2016，30（5）：609-615.