改進(jìn)的足球機(jī)器人局部極小值的研究

張 莉,周 杰

(西安工程大學(xué) 電子信息學(xué)院,陜西 西安 710048)

0 引 言

路徑規(guī)劃是足球機(jī)器人系統(tǒng)[1]研究的熱點(diǎn)問題之一,目前足球機(jī)器人路徑規(guī)劃中常用到的方法有人工勢場法、柵格法和遺傳算法.其中人工勢場法因其結(jié)構(gòu)簡單,使用方便,便于數(shù)學(xué)描述,在足球機(jī)器人路徑規(guī)劃中受到了國內(nèi)外學(xué)者越來越廣泛的關(guān)注并取得了良好的效果[2-3].

人工勢場法是由Khatib提出的一種虛擬力法[4],它的基本思想是將機(jī)器人在周圍環(huán)境中的運(yùn)動(dòng)設(shè)計(jì)成一種抽象的人造力場中的運(yùn)動(dòng),目標(biāo)點(diǎn)對移動(dòng)機(jī)器人產(chǎn)生“引力”,障礙物對移動(dòng)機(jī)器人產(chǎn)生“斥力”,最后通過求合力來控制移動(dòng)機(jī)器人的運(yùn)動(dòng).人工勢場法在路徑規(guī)劃中主要存在目標(biāo)不可達(dá),局部極小值和不適應(yīng)動(dòng)態(tài)環(huán)境等問題.而局部極小值和不適應(yīng)動(dòng)態(tài)環(huán)境問題成為研究的重點(diǎn)與熱點(diǎn)問題.為此,研究人員對勢場函數(shù)進(jìn)行了大量的改進(jìn)工作,張琪在文獻(xiàn)[5]中通過引入障礙物速度建立了動(dòng)態(tài)勢場函數(shù),姚進(jìn)在文獻(xiàn)[6]中采用位置矢量的方法對機(jī)器人路徑進(jìn)行規(guī)劃.本文在解決目標(biāo)不可達(dá)問題基礎(chǔ)上通過改進(jìn)算法重點(diǎn)解決路徑規(guī)劃中的局部極小值和算法不適應(yīng)動(dòng)態(tài)環(huán)境問題,并通過MATLAB仿真驗(yàn)證算法的有效性.

1 人工勢場法下的機(jī)器人路徑規(guī)劃

1.1 人工勢場法勢場函數(shù)

人工勢場法是在機(jī)器人的運(yùn)動(dòng)空間創(chuàng)造一個(gè)勢場E,該勢場由兩部分組成:一個(gè)是引力勢場Eatt,它隨著機(jī)器人和目標(biāo)點(diǎn)的距離增加而單調(diào)遞增,方向指向目標(biāo)點(diǎn);另一個(gè)是斥力勢場Erep,當(dāng)機(jī)器人處在障礙物位置時(shí)有一極大值,并隨著機(jī)器人到障礙物的距離的增大而單調(diào)遞減,方向?yàn)檫h(yuǎn)離障礙物的方向.整個(gè)勢場Etotal是引力勢場部分和斥力勢場部分的疊加.機(jī)器人沿著合勢場力方向運(yùn)動(dòng),繞開障礙物,向目標(biāo)點(diǎn)運(yùn)動(dòng).

(1) 引力勢場函數(shù) 目標(biāo)點(diǎn)對機(jī)器人產(chǎn)生引力,且距離越遠(yuǎn)吸引作用越強(qiáng),機(jī)器人距目標(biāo)越遠(yuǎn),所具有的勢場能就越大,反之就越小.當(dāng)距離為零時(shí),機(jī)器人的勢能為零,此時(shí)機(jī)器人到達(dá)目標(biāo)點(diǎn).這種特性與重力勢能和彈性勢能的特性相類.通常引力勢場函數(shù)可以取為

Eatt(p)=(1/2)k(Pgoal-P)2.

(1)

其中P和Pgoal分別表示機(jī)器人和目標(biāo)點(diǎn)的位置;k是可調(diào)參數(shù).

(2) 斥力勢場函數(shù) 為克服目標(biāo)點(diǎn)附近有障礙物時(shí)機(jī)器人在接近障礙物的過程中受到的引力減小,斥力增加最終導(dǎo)致無法達(dá)到目標(biāo)點(diǎn)的情況,在斥力勢場中引入P-Pgoal乘子,以保障整個(gè)勢場函數(shù)在機(jī)器人到達(dá)目標(biāo)點(diǎn)時(shí)達(dá)到最小值,其中n是一個(gè)正常數(shù),η為斥力系數(shù).通常斥力勢場可以取為

(2)

1.2 傳統(tǒng)人工勢場法在路徑規(guī)劃中的問題

(1) 局部極小值問題 當(dāng)機(jī)器人運(yùn)動(dòng)到某一障礙物的影響范圍內(nèi),如果機(jī)器人與目標(biāo)的連線垂直于障礙物的一條邊,此時(shí)機(jī)器人所受的斥力和引力在同一條直線上,機(jī)器人在合力作用下沿這條直線運(yùn)動(dòng),這時(shí)機(jī)器人無法繞開障礙物,機(jī)器人停止或在機(jī)器人與目標(biāo)的連線上振蕩而無法到達(dá)目標(biāo)點(diǎn),即產(chǎn)生局部極小值.

(2) 不適應(yīng)動(dòng)態(tài)環(huán)境 傳統(tǒng)的人工勢場法僅僅定義為相對位置的函數(shù),這對于障礙物和目標(biāo)點(diǎn)固定的情況比較實(shí)用,但在目標(biāo)點(diǎn)和障礙物都處于高速運(yùn)動(dòng)的動(dòng)態(tài)環(huán)境中則不能有效跟蹤目標(biāo)和避開障礙物.

1.3 機(jī)器人避障過程中問題分析

傳統(tǒng)人工勢場法中存在障礙物附近目標(biāo)不可達(dá),局部極小值,以及不適應(yīng)動(dòng)態(tài)環(huán)境等問題.其中障礙物目標(biāo)不可達(dá)問題通過改造斥力場函數(shù)得到了解決,而算法不適應(yīng)動(dòng)態(tài)環(huán)境的問題主要是由障礙物由靜止變?yōu)檫\(yùn)動(dòng)引起,而靜態(tài)路徑規(guī)劃是機(jī)器人動(dòng)態(tài)路徑規(guī)劃的基礎(chǔ).此外,機(jī)器人動(dòng)態(tài)路徑規(guī)劃中仍然存在局部極小值問題,因而機(jī)器人避障過程中問題暫時(shí)歸結(jié)到一點(diǎn):靜態(tài)路徑規(guī)劃中的局部極小值問題.

2 機(jī)器人靜態(tài)避障問題解決

對于多個(gè)障礙物作用下的局部極小值問題,可以看成是多個(gè)障礙物產(chǎn)生的合效果引起的單個(gè)局部極小值問題.假設(shè)機(jī)器人在靠近這一堆障礙物時(shí),由于障礙物的位置唯一,實(shí)際上機(jī)器人總是和其中某個(gè)障礙物先作用,此時(shí)只要判斷機(jī)器人和此障礙物的位置關(guān)系從而判斷繞過障礙物的方向,就可以繞開此障礙物,由于機(jī)器人受力改變從而打破之前斥力不發(fā)生偏轉(zhuǎn)時(shí)的受力平衡,這樣就成功克服了此處的局部極小值情況.機(jī)器人繞開其他障礙物的方法與之類似.因此，可以得出(1)當(dāng)障礙物位于機(jī)器人與目標(biāo)的連線的左上方時(shí),斥力逆時(shí)針偏轉(zhuǎn)一個(gè)角度(可以取90°).(2)當(dāng)障礙物位于機(jī)器人與目標(biāo)的連線的右上方時(shí),斥力順時(shí)針偏轉(zhuǎn)一個(gè)角度(可以取90°).(3)當(dāng)障礙物位于機(jī)器人與目標(biāo)的連線上方時(shí),斥力可以順時(shí)針偏轉(zhuǎn)一個(gè)角度,也可以逆時(shí)針偏轉(zhuǎn)一個(gè)角度,可以歸到式(1)或(2)中.

3 機(jī)器人動(dòng)態(tài)避障問題解決

3.1 速度勢場的建立

(1) 速度引力場的建立 機(jī)器人在勢場中所受吸引力如圖1所示.假設(shè)在某t時(shí)刻,機(jī)器人的速度為Vr,目標(biāo)足球的速度為Vg,將Vr分解為目標(biāo)足球速度矢量Vg與相對目標(biāo)物的速度矢量Vrg,方向由機(jī)器人指向目標(biāo)足球,相對速度矢量Vrg=Vr-Vg.如圖1所示,相對速度引力場為

Uattv=(1/2)Vattv(Vr-Vg)2.

(3)

相對速度引力場函數(shù)求負(fù)梯度后得到的相對速度引力

圖1 機(jī)器人和目標(biāo)足球速度分解圖 圖2 機(jī)器人在斥力場中的運(yùn)動(dòng)狀態(tài)圖

(4)

引入相對速度矢量后,引力作用的合力為

Fatt=Fattv+Fattp.

(5)

在引力場中,相對位置引力Fattp使得機(jī)器人沿著目標(biāo)點(diǎn)的最短路徑運(yùn)動(dòng),大小與相對位置成正比,方向指向目標(biāo)點(diǎn),而相對速度引力Fattv使機(jī)器人的速度與目標(biāo)的速度保持一致,規(guī)定其方向?yàn)槟繕?biāo)點(diǎn)相對于機(jī)器人的運(yùn)動(dòng)方向.只有當(dāng)相對位置與相對速度同時(shí)為零時(shí),引力的合力才為零,這時(shí)機(jī)器人才到達(dá)目標(biāo)位置,處于帶球狀態(tài).

(2) 速度斥力勢場的建立 傳統(tǒng)的斥力場函數(shù)只定義為機(jī)器人與障礙物之間的距離函數(shù),也就是相對斥力場函數(shù).而在足球機(jī)器人系統(tǒng)中,障礙物處于不斷運(yùn)動(dòng)中,僅考慮位置斥力不能完全反映環(huán)境信息,為此有必要引入速度斥力函數(shù)[5-6].

如圖2所示,相對速度斥力場為

Urepv=(1/2)Krepv(Vobs-Vr)2.

(6)

同理,相對速度斥力場函數(shù)求負(fù)梯度得到相對速度斥力

Frepv=-▽Urepv=Krepv(Vobs-Vr).

(7)

斥力方向?yàn)榇怪庇跈C(jī)器人相對障礙物的相對速度矢量,且遠(yuǎn)離障礙物的方向.

圖3 障礙物位于機(jī)器人與目標(biāo)的連線上的運(yùn)動(dòng)圖 圖4 障礙物位于機(jī)器人與目標(biāo)的線上時(shí)的受力圖

圖3是機(jī)器人、障礙物、目標(biāo)處于特殊位置下的運(yùn)動(dòng)圖,圖4是此時(shí)的受力圖.由圖4可知,由相對速度產(chǎn)生的斥力與相對速度垂直,在此力的作用下,機(jī)器人的運(yùn)動(dòng)軌跡發(fā)生改變,機(jī)器人就可以擺脫此前的局部極小值.當(dāng)障礙物位于機(jī)器人與目標(biāo)的連線的上方,并向機(jī)器人運(yùn)動(dòng)時(shí)(見圖5),此時(shí)的受力情況如圖6所示.

圖5 障礙物位于機(jī)器人與目標(biāo)的連線左上方時(shí)運(yùn)動(dòng)圖 圖6 障礙物位于機(jī)器人與目標(biāo)的連線左上方時(shí)的受力圖

圖5中障礙物以圖示的方向攔截機(jī)器人,相對速度Vor產(chǎn)生的斥力如圖6所示,此時(shí)必須根據(jù)機(jī)器人、障礙物、目標(biāo)三者的位置確定此斥力的方向,斥力必須是如圖6所示的方向才能合理地避開障礙物；倘若斥力方向取的是圖示方向的反向,則無法合理避開障礙物,是不可取的.

當(dāng)障礙物位于機(jī)器人與目標(biāo)的連線的下方,并向機(jī)器人運(yùn)動(dòng)時(shí),此時(shí)的運(yùn)動(dòng)與受力情況如圖7,8所示.同理此時(shí)的相對速度產(chǎn)生的斥力方向,只能取圖示方向,而不能為其反向.

圖7 障礙物位于機(jī)器人與目標(biāo)的連線右上方時(shí)運(yùn)動(dòng)圖 圖8 障礙物位于機(jī)器人與目標(biāo)的連線右上方時(shí)的受力圖

3.2 引力與斥力場的模型改進(jìn)

足球機(jī)器人動(dòng)態(tài)路徑規(guī)劃中障礙物和機(jī)器人都是運(yùn)動(dòng)的,且二者都有各自的運(yùn)動(dòng)方向,在構(gòu)造勢場函數(shù)時(shí),引入速度項(xiàng),建立速度矢量勢場十分關(guān)鍵.

算法改進(jìn)后相應(yīng)的引力和斥力表達(dá)式為

Fatt=k(Pgoal-P)+Kattv(Vr-Vg)

(8)

(9)

Frep1=η/2(1-p-pobs-(1/d0))(p-pgoal)n/(p-pobs2).

(10)

Frep1=η/2(1-p-pobs-(1/d0))2(p-pgoal)n/(p-pgoaln-1).

(11)

由引力和斥力的表達(dá)式可知:引力場[7]在機(jī)器人運(yùn)動(dòng)過程中始終存在,在機(jī)器靠近目標(biāo)的過程中引力場逐漸減小,引力也隨之逐漸減小,直到機(jī)器人到達(dá)目標(biāo)點(diǎn)時(shí)引力為零.克服目標(biāo)點(diǎn)附近目標(biāo)不可達(dá)問題后的斥力Frep產(chǎn)生兩個(gè)效果,其中Frep1方向由障礙物指向機(jī)器人,Frep2的方向?yàn)橛蓹C(jī)器人指向目標(biāo)點(diǎn)(上文靜態(tài)避障問題中所涉及到的斥力偏轉(zhuǎn)均指Frep1).

斥力場的作用范圍是局部的,位置斥力場和速度斥力場在斥力影響范圍內(nèi)具有不同的作用范圍,當(dāng)機(jī)器人剛進(jìn)入斥力的影響范圍而離障礙物還不是很近時(shí),速度斥力場發(fā)揮作用,速度斥力垂直于機(jī)器人相對于障礙物速度的方向,大小與相對速度大小成正比.當(dāng)機(jī)器人距離障礙物較近時(shí),位置斥力發(fā)揮作用.機(jī)器人與障礙物的相對位置越近,斥力越大,相對速度越大,斥力也最大.

4 算法仿真及對比分析

4.1 靜態(tài)避障算法改進(jìn)前后仿真及分析

圖9 傳統(tǒng)人工勢場法局部極小值 圖10 改進(jìn)人工勢場法克服局部極小值

圖9反映的是單個(gè)和多個(gè)障礙物作用下的局部最小值的產(chǎn)生的兩種情況,圖10是通過上述總結(jié)的方法實(shí)現(xiàn)后的仿真圖.這是障礙物位置比較特殊的情況,而一般位置障礙物的路徑規(guī)劃仿真情況如圖11～13.

圖11 障礙物一般位置 圖12 不能正確判斷方向 圖13 能正確判斷方向

圖11是一般位置障礙物下的軌跡規(guī)劃的仿真圖;圖12是一般位置障礙物下斥力在不能合理判斷方向的情況下的偏轉(zhuǎn)一定角度的仿真圖;圖13是一般位置障礙物下算法改進(jìn)后斥力合理判斷方向的情況下偏轉(zhuǎn)一定角度后的仿真圖.

表1 算法改進(jìn)前后機(jī)器人避障和軌跡步長情況的比較

表1是算法改進(jìn)前后機(jī)器人避障和軌跡步長情況的比較，由表1比較可知，圖9中步長為200說明陷入局部極小值,圖12說明斥力方向偏轉(zhuǎn)的方法能夠有效克服圖9中兩種情況下產(chǎn)生的局部極小值問題,并且能夠繞開特殊位置障礙物.

圖12軌跡共走了87步,明顯比圖10步數(shù)多,軌跡不是最優(yōu);圖13軌跡共走了73步,比圖10更少,路徑規(guī)劃相對最優(yōu).本文改進(jìn)算法通過編程實(shí)現(xiàn)后不僅可以減小局部極小值產(chǎn)生的概率而且對障礙物處于一般位置時(shí)的路徑規(guī)劃有益無害,在一定程度上可以使人工勢場法路徑規(guī)劃算法得到優(yōu)化.

4.2 機(jī)器人動(dòng)態(tài)障礙物避障算法仿真及分析

4.2.1 傳統(tǒng)人工勢場 傳統(tǒng)人工勢場改進(jìn)算法有助于解決靜態(tài)路徑規(guī)劃中存在的局部極小值問題,因此有必要檢驗(yàn)一下此改進(jìn)算法在動(dòng)態(tài)路徑規(guī)劃中的效果,下面通過仿真圖來說明:

圖14中設(shè)置了3個(gè)障礙物的運(yùn)動(dòng)方向,機(jī)器人能夠順利繞開前兩個(gè)攔截的障礙物,而在避開第3個(gè)障礙物時(shí)出現(xiàn)了問題,圖15中也設(shè)置了3個(gè)障礙物的運(yùn)動(dòng)方向,不同的是,第2個(gè)障礙物的運(yùn)動(dòng)方向發(fā)生了變化,從而檢驗(yàn)機(jī)器人在繞開障礙物的過程中能否正確判斷方向,由圖15可知,機(jī)器人能夠順利繞開前2個(gè)攔截的障礙物,而在避開第3個(gè)障礙物時(shí)同樣出現(xiàn)了問題.而兩幅圖中問題出現(xiàn)的原因在于障礙物的運(yùn)動(dòng)方向比較特殊,當(dāng)機(jī)器人靠近運(yùn)動(dòng)的障礙物時(shí),斥力發(fā)生偏轉(zhuǎn)后恰好與障礙物運(yùn)動(dòng)方向垂直,因而此時(shí)繞不開障礙物.

4.2.2 引進(jìn)速度勢場后 圖16是在引入速度勢場改進(jìn)算法后對不同方向運(yùn)動(dòng)的障礙物的動(dòng)態(tài)路徑規(guī)劃.

圖14 靜態(tài)避障改進(jìn)算法用在動(dòng)態(tài)避障中 圖15 靜態(tài)避障改進(jìn)算法用在動(dòng)態(tài)避障中 圖16 引入速度勢場后的動(dòng)態(tài)避障

表2是人工勢場靜態(tài)改進(jìn)算法與引入速度勢場的動(dòng)態(tài)路徑規(guī)劃算法的比較.由表2和圖16可以看出引進(jìn)速度勢場后的算法不僅能克服動(dòng)態(tài)環(huán)境下的局部極小值問題,而且可以合理避開不同方向的運(yùn)動(dòng)障礙物,相對于圖14與圖15更能適應(yīng)動(dòng)態(tài)環(huán)境,從而驗(yàn)證了算法改進(jìn)后的有效性.

5 結(jié)束語

表2 人工勢場靜態(tài)改進(jìn)算法與引入速度勢場的動(dòng)態(tài)路徑規(guī)劃算法的比較

針對人工勢場法在機(jī)器人路徑規(guī)劃中存在的局部極小值問題提出了解決辦法:當(dāng)障礙物是靜止時(shí),可以采用機(jī)器人接近障礙物時(shí)斥力發(fā)生偏轉(zhuǎn)的方法克服局部極小值并優(yōu)化軌跡；當(dāng)障礙物是運(yùn)動(dòng)時(shí),可以采用引進(jìn)速度勢場產(chǎn)生速度斥力的方法克服局部極小值.仿真實(shí)驗(yàn)證明上述改進(jìn)算法對解決機(jī)器人路徑規(guī)劃中存在的局部極小值問題是有效的,并且能夠很好適應(yīng)動(dòng)態(tài)復(fù)雜環(huán)境下的路徑規(guī)劃.文中的參數(shù)是通過MATLAB實(shí)驗(yàn)反復(fù)測試得到的,接下來的工作是通過學(xué)習(xí)使上述參數(shù)設(shè)置更加合理.

參考文獻(xiàn)：

[1] 陳萬米,張冰,朱明,等.智能足球機(jī)器人系統(tǒng)[M].北京:北京大學(xué)出版社,2009:229-230.

[2] 殷路,殷怡欣.基于人工勢場法動(dòng)態(tài)路徑規(guī)劃仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2009,21(11):14-15.

[3] 李惠光,李旭峰,等.動(dòng)態(tài)環(huán)境下基于人工勢場法路徑規(guī)劃[J].國外電子測量技術(shù),2008,27(5):27-29.

[4] KHATIB O.Real time obstacle avoidance for manipulation and mobile robots[J].Int J Robotics Res,1986,5(1):90-98.

[5] 張琪,楊宜民.基于改進(jìn)人工勢場的足球機(jī)器人避障控制[J].機(jī)器人,2006,28(1):45-49.

[6] 姚進(jìn),李洪,曹成才,等.基于矢量勢場法的足球機(jī)器人路徑規(guī)劃[J].四川大學(xué)學(xué)報(bào),2006,38(2):72-99.

[7] 林志雄,張莉.基于神經(jīng)模糊勢場法的足球機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)仿真,2014(1):416-420.

[8] 王佳,吳曉蓓,徐志良,等.避免人工勢場中一類局部極小值的規(guī)劃方法[J].計(jì)算機(jī)仿真,2007,24(1):151-154.

[9] MABROUK M H,MCINNES C R.Solving the potential field Local minimum problem using internal Agent state[J].Robotics and Autonomous Systems,2008,56(12):1050-1060.