改進的足球機器人局部極小值的研究

張 莉,周 杰

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

0 引 言

路徑規劃是足球機器人系統[1]研究的熱點問題之一,目前足球機器人路徑規劃中常用到的方法有人工勢場法、柵格法和遺傳算法.其中人工勢場法因其結構簡單,使用方便,便于數學描述,在足球機器人路徑規劃中受到了國內外學者越來越廣泛的關注并取得了良好的效果[2-3].

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

1 人工勢場法下的機器人路徑規劃

1.1 人工勢場法勢場函數

人工勢場法是在機器人的運動空間創造一個勢場E,該勢場由兩部分組成:一個是引力勢場Eatt,它隨著機器人和目標點的距離增加而單調遞增,方向指向目標點;另一個是斥力勢場Erep,當機器人處在障礙物位置時有一極大值,并隨著機器人到障礙物的距離的增大而單調遞減,方向為遠離障礙物的方向.整個勢場Etotal是引力勢場部分和斥力勢場部分的疊加.機器人沿著合勢場力方向運動,繞開障礙物,向目標點運動.

(1) 引力勢場函數 目標點對機器人產生引力,且距離越遠吸引作用越強,機器人距目標越遠,所具有的勢場能就越大,反之就越小.當距離為零時,機器人的勢能為零,此時機器人到達目標點.這種特性與重力勢能和彈性勢能的特性相類.通常引力勢場函數可以取為

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

(1)

其中P和Pgoal分別表示機器人和目標點的位置;k是可調參數.

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

(2)

1.2 傳統人工勢場法在路徑規劃中的問題

(1) 局部極小值問題 當機器人運動到某一障礙物的影響范圍內,如果機器人與目標的連線垂直于障礙物的一條邊,此時機器人所受的斥力和引力在同一條直線上,機器人在合力作用下沿這條直線運動,這時機器人無法繞開障礙物,機器人停止或在機器人與目標的連線上振蕩而無法到達目標點,即產生局部極小值.

(2) 不適應動態環境 傳統的人工勢場法僅僅定義為相對位置的函數,這對于障礙物和目標點固定的情況比較實用,但在目標點和障礙物都處于高速運動的動態環境中則不能有效跟蹤目標和避開障礙物.

1.3 機器人避障過程中問題分析

傳統人工勢場法中存在障礙物附近目標不可達,局部極小值,以及不適應動態環境等問題.其中障礙物目標不可達問題通過改造斥力場函數得到了解決,而算法不適應動態環境的問題主要是由障礙物由靜止變為運動引起,而靜態路徑規劃是機器人動態路徑規劃的基礎.此外,機器人動態路徑規劃中仍然存在局部極小值問題,因而機器人避障過程中問題暫時歸結到一點:靜態路徑規劃中的局部極小值問題.

2 機器人靜態避障問題解決

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

3 機器人動態避障問題解決

3.1 速度勢場的建立

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

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

(3)

相對速度引力場函數求負梯度后得到的相對速度引力

圖1 機器人和目標足球速度分解圖 圖2 機器人在斥力場中的運動狀態圖

(4)

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

Fatt=Fattv+Fattp.

(5)

在引力場中,相對位置引力Fattp使得機器人沿著目標點的最短路徑運動,大小與相對位置成正比,方向指向目標點,而相對速度引力Fattv使機器人的速度與目標的速度保持一致,規定其方向為目標點相對于機器人的運動方向.只有當相對位置與相對速度同時為零時,引力的合力才為零,這時機器人才到達目標位置,處于帶球狀態.

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

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

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

(6)

同理,相對速度斥力場函數求負梯度得到相對速度斥力

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

(7)

斥力方向為垂直于機器人相對障礙物的相對速度矢量,且遠離障礙物的方向.

圖3 障礙物位于機器人與目標的連線上的運動圖 圖4 障礙物位于機器人與目標的線上時的受力圖

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

圖5 障礙物位于機器人與目標的連線左上方時運動圖 圖6 障礙物位于機器人與目標的連線左上方時的受力圖

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

當障礙物位于機器人與目標的連線的下方,并向機器人運動時,此時的運動與受力情況如圖7,8所示.同理此時的相對速度產生的斥力方向,只能取圖示方向,而不能為其反向.

圖7 障礙物位于機器人與目標的連線右上方時運動圖 圖8 障礙物位于機器人與目標的連線右上方時的受力圖

3.2 引力與斥力場的模型改進

足球機器人動態路徑規劃中障礙物和機器人都是運動的,且二者都有各自的運動方向,在構造勢場函數時,引入速度項,建立速度矢量勢場十分關鍵.

算法改進后相應的引力和斥力表達式為

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)

由引力和斥力的表達式可知:引力場[7]在機器人運動過程中始終存在,在機器靠近目標的過程中引力場逐漸減小,引力也隨之逐漸減小,直到機器人到達目標點時引力為零.克服目標點附近目標不可達問題后的斥力Frep產生兩個效果,其中Frep1方向由障礙物指向機器人,Frep2的方向為由機器人指向目標點(上文靜態避障問題中所涉及到的斥力偏轉均指Frep1).

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

4 算法仿真及對比分析

4.1 靜態避障算法改進前后仿真及分析

圖9 傳統人工勢場法局部極小值 圖10 改進人工勢場法克服局部極小值

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

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

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

表1 算法改進前后機器人避障和軌跡步長情況的比較

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

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

4.2 機器人動態障礙物避障算法仿真及分析

4.2.1 傳統人工勢場 傳統人工勢場改進算法有助于解決靜態路徑規劃中存在的局部極小值問題,因此有必要檢驗一下此改進算法在動態路徑規劃中的效果,下面通過仿真圖來說明:

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

4.2.2 引進速度勢場后 圖16是在引入速度勢場改進算法后對不同方向運動的障礙物的動態路徑規劃.

圖14 靜態避障改進算法用在動態避障中 圖15 靜態避障改進算法用在動態避障中 圖16 引入速度勢場后的動態避障

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

5 結束語

表2 人工勢場靜態改進算法與引入速度勢場的動態路徑規劃算法的比較

針對人工勢場法在機器人路徑規劃中存在的局部極小值問題提出了解決辦法:當障礙物是靜止時,可以采用機器人接近障礙物時斥力發生偏轉的方法克服局部極小值并優化軌跡；當障礙物是運動時,可以采用引進速度勢場產生速度斥力的方法克服局部極小值.仿真實驗證明上述改進算法對解決機器人路徑規劃中存在的局部極小值問題是有效的,并且能夠很好適應動態復雜環境下的路徑規劃.文中的參數是通過MATLAB實驗反復測試得到的,接下來的工作是通過學習使上述參數設置更加合理.

參考文獻：

[1] 陳萬米,張冰,朱明,等.智能足球機器人系統[M].北京:北京大學出版社,2009:229-230.

[2] 殷路,殷怡欣.基于人工勢場法動態路徑規劃仿真研究[J].系統仿真學報，2009,21(11):14-15.

[3] 李惠光,李旭峰,等.動態環境下基于人工勢場法路徑規劃[J].國外電子測量技術,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].機器人,2006,28(1):45-49.

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

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

[8] 王佳,吳曉蓓,徐志良,等.避免人工勢場中一類局部極小值的規劃方法[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.