曲寶福 王利利 任超群

(1.內(nèi)蒙古工業(yè)大學(xué)，內(nèi)蒙古 呼和浩特 010051；2.固陽(yáng)縣職業(yè)教育中心，內(nèi)蒙古 包頭 014200)

0 引言

足球機(jī)器人在機(jī)器人發(fā)展領(lǐng)域發(fā)揮著重要的作用，具有廣泛的應(yīng)用前景。而機(jī)器人足球比賽作為檢驗(yàn)機(jī)器人技術(shù)的一種有效手段，成為當(dāng)前學(xué)術(shù)界的研究熱點(diǎn)。

決定足球機(jī)器人勝負(fù)的關(guān)鍵因素就是合理的路徑規(guī)劃。路徑規(guī)劃簡(jiǎn)單的理解就是讓機(jī)器人遵循某種性能指標(biāo)(如距離，時(shí)間等)，從初始位置到達(dá)目標(biāo)位置作出最優(yōu)的行走路徑。目前，路徑規(guī)劃的求解方法主要有人工勢(shì)場(chǎng)法和基于人工智能的啟發(fā)式方法，如蟻群算法、遺傳算法和粒子群等。蟻群算法是一種受到生物界蟻群覓食行為的啟發(fā)式搜索算法，本文為校及科研項(xiàng)目，項(xiàng)目實(shí)施過(guò)程中對(duì)各種算法進(jìn)行實(shí)驗(yàn)比對(duì)，最終提出一種勢(shì)場(chǎng)改進(jìn)蟻群算法的足球機(jī)器人路徑規(guī)劃算法，并測(cè)試其有效性和優(yōu)越性。

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

足球機(jī)器人比賽規(guī)則：要求由多個(gè)機(jī)器人組成足球隊(duì)，在一個(gè)實(shí)時(shí)、噪聲和對(duì)抗性的環(huán)境下進(jìn)行，以機(jī)器人射門得分最高為勝。足球機(jī)器人的路徑規(guī)劃模型如圖1所示，當(dāng)前位置為足球機(jī)器人的起始點(diǎn)，當(dāng)足球機(jī)器人遇到障礙物時(shí)，在避免碰撞的前提下，找到一條從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)長(zhǎng)度最短的路徑。

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

2 人工勢(shì)場(chǎng)法的缺點(diǎn)

傳統(tǒng)的人工勢(shì)場(chǎng)法具有其不足和局限性:局部最小值問題；在障礙物前振蕩前進(jìn)；不能從兩個(gè)距離較近的障礙物之間穿過(guò)等。其中，局部最小值問題是由于機(jī)器人在環(huán)境空間中在某個(gè)位置產(chǎn)生的斥力(或斥力的合力)和引力正好在同一條直線上大小相等，方向相反。則機(jī)器人認(rèn)為已經(jīng)到達(dá)目標(biāo)處故在該點(diǎn)停留或者振蕩徘徊。另外不能從兩個(gè)較近的障礙物之間穿過(guò)也是上述原因，如圖2所示。振蕩前進(jìn)則是如下圖3所示。

圖2 局部最小值的例子

圖3 振蕩前進(jìn)示意圖

3 人工勢(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位置P(n)=r轉(zhuǎn)移到下一步位置P(n+1)=s的概率依據(jù)是由下面的式子決定的：

(1)

(2)

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

τrs(n+1)=(1-ψ)τrs(n)+ψτ0

(3)

當(dāng)0<ψ1為一個(gè)常數(shù)；τ0=m/Cnn為初始信息素的值；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)行一次全局信息素更新，如下式：

τrs(n+1)=(1-ρ)τrs(n)+ρΔτrs(n)

(4)

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

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

(5)

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

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

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

人工勢(shì)場(chǎng)蟻群算法仿真圖及迭代次數(shù)與路徑長(zhǎng)度如圖4、圖5所示，在迭代30次后，算法就趨于穩(wěn)定，最優(yōu)路徑長(zhǎng)度在33.9258，這條路徑也在最優(yōu)路徑上。但從圖上也看出收斂曲線波動(dòng)比較大，說(shuō)明該方法在收斂上存在可以改進(jìn)之處。

圖4 勢(shì)場(chǎng)蟻群算法

圖5 迭代次數(shù)與路徑長(zhǎng)度關(guān)系

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

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

圖6 勢(shì)場(chǎng)改進(jìn)蟻群算法

圖7 迭代次數(shù)與路徑長(zhǎng)度關(guān)系

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

5 算法驗(yàn)證

在實(shí)驗(yàn)平臺(tái)AS-ROII上進(jìn)行真實(shí)環(huán)境驗(yàn)證。將C++的算法代碼用Visual studio2008生成可執(zhí)行文件，利用無(wú)線局域網(wǎng)導(dǎo)入AS-ROII本體。利用此算法，機(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)方向。

6 結(jié)語(yǔ)

本文針對(duì)人工勢(shì)場(chǎng)法的不足，整合人工勢(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)。

[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] 曹宇杰.RobCup中型組足球機(jī)器人路徑規(guī)劃方法研究[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué),2015.

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