基于人工勢場的多Agent路徑規(guī)劃方法研究

焦紅艷

（河南科技學(xué)院,河南新鄉(xiāng)453003）

基于人工勢場的多Agent路徑規(guī)劃方法研究

焦紅艷

（河南科技學(xué)院,河南新鄉(xiāng)453003）

智能機器人自身運動路徑的規(guī)劃是其完成任務(wù)的基礎(chǔ).主要針對實際應(yīng)用中常用的柵格法和人工勢場法兩種路徑規(guī)劃算法進行研究,針對多Agent運行的復(fù)雜陸地環(huán)境,利用柵格法構(gòu)建環(huán)境模型,給出了一種基于人工勢場法的路徑規(guī)劃方法.分析了勢函數(shù)的選取方式,得出了參數(shù)選取的基本原則,并結(jié)合常用的沖突消解辦法,使得規(guī)劃出的路徑更加平滑,效率更高.

多Agent；路徑規(guī)劃；柵格法；人工勢場法；沖突消解

在Agent運動規(guī)劃中較常用的方法有人工勢場法、構(gòu)型空間法、人工智能法以及各種啟發(fā)式搜索方法等[1].其中人工勢場法是在運動規(guī)劃中引入了虛擬力場的概念對Agent的運動進行規(guī)劃,Agent根據(jù)勢場來確定它自身所受到的虛力,通過所受虛力來確定運動方向[2].本文采用柵格法建立環(huán)境模型,然后利用人工勢場法進行路徑規(guī)劃,解決多Agent系統(tǒng)中的各種沖突.

1 用柵格法進行地形描述

在動態(tài)環(huán)境下,可能存在靜態(tài)和動態(tài)兩類障礙物,當不考慮這些障礙物存在的問題時,Agent就可以按照既定的路線前進,自然有些障礙物會和Agent相撞,有些則不會[3].利用人工勢場法規(guī)劃路徑,為了避障,結(jié)果會導(dǎo)致運動路徑變長,能源與時間損耗變大.

對于可能發(fā)生碰撞的障礙物,計算它對Agent所產(chǎn)生的斥力是非常必要的,對于安全的障礙物免于計算,從而達到優(yōu)化算法和節(jié)約資源的目的[4].

1.1 地形的柵格化

地形的柵格化是指將Agent所處的實際的復(fù)雜環(huán)境用簡單、規(guī)則的柵格表示出來.通常情況下,柵格地圖中的柵格單元共有3種狀態(tài)：①未知狀態(tài),表明該柵格單元離Agent較遠,尚未被傳感器探測到,目前屬于未知區(qū)域；②占有狀態(tài),表明該柵格單元已經(jīng)被障礙物占據(jù)；③空閑狀態(tài),表明該柵格單元歸屬于空閑區(qū)域,即Agent可以從該柵格通過.柵格法是一種非常流行的地形柵格化方法,其主要思想就是將環(huán)境劃分為離散的柵格,并將柵格看作一個連通圖,路徑規(guī)劃即是在這個連通圖上利用相應(yīng)的搜索算法搜索出無碰路徑,路徑是由柵格序號組成的,最后將序號轉(zhuǎn)化為地圖坐標即可.

1.2 信息編碼

環(huán)境模型建立之后的信息編碼是非常重要的一個環(huán)節(jié),編碼方式為：1表示障礙柵格,0表示自由柵格.計算機中以柵格序號為索引進行存儲：

以序號為36的柵格為例,它的環(huán)境信息將存儲在kj[36]的這個結(jié)構(gòu)體數(shù)組元素中.

obs={z1,z2,z3…}為障礙柵格集合；qd表示起點,zd表示終點,這兩點不屬于obs.電子地圖就可以通過柵格與數(shù)組的對應(yīng)關(guān)系建立.之后的路徑規(guī)劃將在建立的電子地圖的基礎(chǔ)上進行.

2 用人工勢場法進行路徑規(guī)劃

2.1 傳統(tǒng)人工勢場法所面臨的問題

對于如圖1所示的U型障礙物環(huán)境,Agent會因多處受力而震蕩,對于狹窄通道也容易來回擺動,最終無法到達終點.另外,Agent本身也具有一定尺寸,當障礙物之間通道的尺寸本來就小于Agent的尺寸時,Agent自然也是無法通過此通道的.

圖1 U型環(huán)境結(jié)構(gòu)Fig.1 U environment structure

2.2 人工勢場法的改進措施

經(jīng)過長時間的實踐與研究,研究人員發(fā)現(xiàn),傳統(tǒng)的人工勢場法在路徑規(guī)劃時對于規(guī)則障礙物規(guī)劃正常,但是對于不規(guī)則障礙物容易路徑規(guī)劃失敗而發(fā)生碰撞.

本文實現(xiàn)了把選擇策略加入到路徑規(guī)劃算法中,使Agent在每步動作之前就可以對下一步動作提前做出預(yù)判,以提高下一步動作的效率.也就是說我們期望通過此方法使得Agent可以付出最小的代價來規(guī)避障礙物從而到達目標點,這里所指的代價不僅僅包括速度,而且也包括規(guī)避障礙物的效率.

現(xiàn)將Agent自身的速度和加速度矢量分別引入到人工勢場法中.則可推導(dǎo)出如下的公式

分析假如發(fā)生碰撞的情況下,要考慮當時臨界點的情況：①如果障礙物的運動速度較大,則障礙物有可能在Agent的右側(cè)與它發(fā)生碰撞；②如果障礙物的運動速度相對較小,則障礙物就有可能在Agent的左側(cè)與它發(fā)生碰撞.

由此,可以通過計算得到ΔVx的兩個臨界值A(chǔ)和B.按照上述情況①和情況②所進行的分析,此時應(yīng)該分別滿足以下公式由公式（1）和（2）可以推出

Agent下一步行為的具體的判斷方法如下：

（1）如果ΔVx介于A和B之間,則存在發(fā)生碰撞的可能,所以Agent需要做出規(guī)避的動作.但是因為障礙物對Agent來說,在速度上有優(yōu)勢,所以即使Agent做出了規(guī)避動作,仍有可能發(fā)生碰撞.

（2）如果ΔVx＞B,由于障礙物在x軸正方向的速度上存在巨大的優(yōu)勢,Agent無法從此方向避障,只能選擇其反方向.

（3）如果ΔVx＜A,因為障礙物在x軸正方向上對Agent所存在的優(yōu)勢不足,使得Agent與障礙物不存在碰撞的可能,因此,在這種情況下,就可以利用傳統(tǒng)的人工勢場法來實現(xiàn)對障礙物的規(guī)避.

（4）如果障礙物與Agent之間的距離大于200（單位與Agent的半徑單位相同）,因超出距離范圍而無需考慮.

結(jié)合上面所論述的避碰原理,首先需要分析所要加的這個修正力的大小以及如何將這個修正力實現(xiàn).可以看出,當Agent需要做出向右規(guī)避動作的時候,就需要給Agent施加一個指向x軸正方向的修正力,具體定義如下

這里的c是指與所增加修正力相關(guān)的一個參數(shù).這里這個修正力的方向與ΔVx同向.最后所得到的合力的方向是原來人工勢場的合力與后來增加的修正力的合力的方向.最后可以得出合力的定義

當Agent需要做出向左的規(guī)避動作時,就需要對Agent施加一個指向x軸負方向的修正力,從而使得Agent能夠擺脫障礙物.可以看出,在傳統(tǒng)的人工勢場法中,障礙物對Agent的排斥力和目標點對Agent的吸引力的合力是使得Agent做出向右的規(guī)避動作.明顯違背了規(guī)劃路徑要求最短的原則.此時,就需要Agent能夠聰明地“分析”一下當前的局勢,從而做出向左的規(guī)避動作.在這里僅僅需要Agent能夠做出這個向左的規(guī)避動作,而不需要把當前障礙物和Agent的具體位置考慮進來,即可以不用考慮當前的障礙物i對Agent所產(chǎn)生的排斥力的大小.這個時侯,我們需要考慮的修正力的大小,就是目標物對Agent的引力和當前障礙物之外的其他障礙物對Agent的排斥力之和的合力,公式如下

根據(jù)上面的描述,在每個仿真周期開始時,就需要根據(jù)環(huán)境中的障礙物、目標物、Agent的位置以及Agent的速度矢量對Agent的下一步動作做出預(yù)判,這樣就可以更好地消除無謂或者徒勞的避障.

經(jīng)過采用上述方法對人工勢場法所做的改進,問題的解決情況如下：

（l）局部最優(yōu)問題的解決.當Agent所受障礙物合力為0時,通過上述的改進,使得Agent不斷地更新自身位置與目標位置之間的距離,從而解決問題.

52.13 %（49/94）的學(xué)員希望固定時間進行課堂教學(xué)，39.36%（37/94）的學(xué)員希望以英語角形式進行學(xué)習(xí)，37.23%（35/94）的學(xué)員希望在科室業(yè)務(wù)學(xué)習(xí)中進行雙語教學(xué)。

（2）狹窄通道中的擺動問題.遇到狹窄通道,將會適當?shù)販p小障礙物對Agent的影響系數(shù),與此同時,增大目標點對Agent的影響系數(shù).當然,減小和增大系數(shù)的數(shù)量級要是一致的,從而使得Agent可以安全地通過狹窄通道.

（3）多障礙物時斥力函數(shù)的調(diào)整.當遇到多障礙物的情況時,容易出現(xiàn)各個障礙物對Agent所產(chǎn)生的斥力方向不太一致的問題,如圖2所示,目標點對Agent所產(chǎn)生的引力F引的大小方向與圖3中一致,經(jīng)過合力作用可以繞過障礙物而到達目標.

圖2 傳統(tǒng)人工勢場法多障礙物路徑規(guī)劃失敗情況Fig.2 The failures of traditional artificial potential field method more obstacles path planning

圖3 改進人工勢場法多障礙物路徑規(guī)劃成功情況Fig.3 The success of improved artificial potential field method more obstacles path planning

（4）障礙物之間的通道不足以讓Agent通過.由于Agent本身是有一定尺寸的,當障礙物之間通道的尺寸小于Agent的尺寸時,Agent是無法從此通道通過的,所以為了避免這種情況的出現(xiàn),通過將通道邊緣向外擴展Agent一半尺寸,使得通道被視為障礙物而達到避障目的[5].

2.3 用人工勢場法對多Agent進行實時路徑規(guī)劃

為了實現(xiàn)多個Agent的有效避碰,除了要考慮環(huán)境中的障礙物以外,還需要考慮到其他Agent的位置信息以及其他Agent對該Agent的斥力[6].本文在利用改進的人工勢場法進行多Agent系統(tǒng)局部路徑規(guī)劃時,將人工勢場法與沖突消解法結(jié)合在一起,并加入了Avoid-Agent行為,用于躲避其他Agent.

在Agent的路徑規(guī)劃過程中,如果沒有出現(xiàn)沖突,則按人工勢場法規(guī)劃,一旦發(fā)生沖突,則按優(yōu)先級法解決[7].具體規(guī)劃方式如下.

（1）當兩個Agent相遇時,有以下兩種可能：

②兩個Agent不在同一直線上,但如果檢測到有沖突的可能,則低優(yōu)先級減速避碰.

（2）如果有多個Agent的沖突需要消除,則執(zhí)行如下步驟：

①如果Agent之間的距離小于某一個規(guī)定值,則表明進入沖突區(qū)；

②低優(yōu)先級停止讓行；

③如果不同優(yōu)先級出現(xiàn)在同一線路,則低優(yōu)先級避讓高優(yōu)先級[8].

上述沖突消解法是各種方法的綜合應(yīng)用[9].改進人工勢場法的流程如圖4所示.

圖4 基于混合算法的路徑規(guī)劃流程Fig.4 Path planning based on hybrid algorithm flow chart

部分代碼如下：

3 仿真實驗

按照以上的規(guī)劃策略進行仿真.假設(shè)Agent都是以不變的速度在前進,4個Agent首先各自按照傳統(tǒng)的人工勢場法所規(guī)劃的最短路徑運動,并且都是向各自的目標點處前進,如圖5-a.當R1和R4進入彼此的安全半徑后,利用改進的人工勢場法進行局部避障,其余兩個按原來的路徑規(guī)劃法,最終均安全抵達目的地,如圖5-e所示.

圖5 仿真實驗Agent路徑Fig.5 The simulation Agent path graph

對比加入了各種避碰策略的改進的人工勢場法的路徑仿真結(jié)果,路線平滑且高效.

4 小結(jié)

本文提出將柵格法和人工勢場法相結(jié)合應(yīng)用在Agent路徑規(guī)劃中的思路,針對多Agent的沖突問題,將傳統(tǒng)人工勢場法及柵格法與各種沖突消減法相結(jié)合,并加入Avoid-Agent行為等思想[10],使得多Agent的路徑規(guī)劃更加高效.實驗證明該方法和理論正確有效.

[1]蔡自興,徐光枯.人工智能及其應(yīng)用[M].3版.北京：清華大學(xué)出版社,2004.

[2]趙鋒.動態(tài)環(huán)境下移動機器人的路徑規(guī)劃[D].北京：北京工業(yè)大學(xué),2003.

[3]張棋,楊宜民.基于改進人工勢場法的足球機器人避碰控制[J].機器人,2002,24（1）：12-15.

[4]王肖青,王齊志.傳統(tǒng)人工勢場的改進[J].計算機技術(shù)與發(fā)展,2006（4）：96-99.

[5]王娟娟.機器人路徑規(guī)劃方法研究[D].淄博：山東理工大學(xué),2010.

[6]賈潤亮.多機器人系統(tǒng)路徑規(guī)劃研究[D].太原：太原理工大學(xué),2008.

[7]王俊松,崔世鋼,邴志剛,等.基于Multi-Agnet的多機器人控制技術(shù)[J].天津職業(yè)技術(shù)師范學(xué)院學(xué)報,2004,14（2）：4-7.

[8]王凡.基于Agent的多機器人路徑規(guī)劃的研究[D].武漢：武漢理工大學(xué),2006.

[9]唐振民,趙春霞,楊靜宇,等.基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報,2003,27（5）：610-615.

[10]CHONG J O,ELMER G G.Growth oistances：new measures for object separation and penetration[J].IEEE Transaction on Roboties and Automation,1996,12（6）：888-903.

（責任編輯：盧奇）

Multi-Agent path planning method based on artificial potential field

JIAO Hongyan
（Henan Institute of Science and Technology,Xinxiang 453003,China）

Intelligent mobile robot motion path planning is the basis of fulfillment of its mandate.Two path planning algorithms,i.e.the grid method and the artificial potential field method was studied in this paper.According to the Multi-Agent complex dynamic environment,environmental model was made by the grid method.A path design method based on the artificial potential field,which is aimed at the complex environment of running the Multi-Agent,was presented using a model mad by grip method.The selection of the potential function was analyzed,and obtained parameters selected basic principles,a smoother,more efficient path planning was obtained by combined with the usual conflict resolution approach.

Multi-Agent；path planning；grid method；artificial potential field method；confilict resolution

TP391

A

1008-7516（2016）04-0056-06

10.3969/j.issn.1008-7516.2016.04.012

2016-05-27

焦紅艷（1981―）,女,山西榆次人,碩士,講師.主要從事計算機理論教學(xué)及研究.