焦紅艷

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

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

焦紅艷

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

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

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

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

1 用柵格法進(jìn)行地形描述

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

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

1.1 地形的柵格化

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

1.2 信息編碼

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

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

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

2 用人工勢(shì)場(chǎng)法進(jìn)行路徑規(guī)劃

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

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

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

2.2 人工勢(shì)場(chǎng)法的改進(jìn)措施

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 用人工勢(shì)場(chǎng)法對(duì)多Agent進(jìn)行實(shí)時(shí)路徑規(guī)劃

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

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

（1）當(dāng)兩個(gè)Agent相遇時(shí),有以下兩種可能：

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

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

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

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

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

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

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

部分代碼如下：

3 仿真實(shí)驗(yàn)

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

圖5 仿真實(shí)驗(yàn)Agent路徑Fig.5 The simulation Agent path graph

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

4 小結(jié)

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

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

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

[3]張棋,楊宜民.基于改進(jìn)人工勢(shì)場(chǎng)法的足球機(jī)器人避碰控制[J].機(jī)器人,2002,24（1）：12-15.

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

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

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

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

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

[9]唐振民,趙春霞,楊靜宇,等.基于動(dòng)態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報(bào),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.

（責(zé)任編輯：盧奇）

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―）,女,山西榆次人,碩士,講師.主要從事計(jì)算機(jī)理論教學(xué)及研究.