基于改進(jìn)分配法的多智能體隊(duì)形形成

陳 梅,梅 樂,陳艷燕

(合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院,安徽 合肥 230009)

?

基于改進(jìn)分配法的多智能體隊(duì)形形成

陳 梅,梅 樂,陳艷燕

(合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院,安徽 合肥 230009)

多機(jī)器人是當(dāng)今研究熱點(diǎn),機(jī)器人編隊(duì)是多機(jī)器人的一個(gè)重要問題,編隊(duì)行為在自然界中廣泛存在,大雁、魚群的有秩序的聚集并編隊(duì)運(yùn)動(dòng)啟示編隊(duì)運(yùn)動(dòng)具有重要的意義和作用。文章針對(duì)多機(jī)器人隊(duì)形問題,提出了一個(gè)基于多智能體(multi-agent)結(jié)構(gòu)的優(yōu)化算法,多智能體的體系結(jié)構(gòu)具有良好的自適應(yīng)特點(diǎn),適合運(yùn)用到多機(jī)器人控制中,對(duì)于隊(duì)形形成問題,改進(jìn)分配算法具有良好的特性。

多智能體;多機(jī)器人;隊(duì)形形成;改進(jìn)分配算法

0 引 言

關(guān)于多智能體隊(duì)形形成的問題研究,主要需要解決的是各個(gè)智能體如何確定自身的隊(duì)形目標(biāo)點(diǎn)以及如何快速無(wú)碰撞地到達(dá)目標(biāo)點(diǎn)。文獻(xiàn)[1]提出對(duì)直線隊(duì)形和圓形隊(duì)形形成的算法,這一類方法可以歸為傳統(tǒng)方法,也有學(xué)者運(yùn)用勢(shì)場(chǎng)法進(jìn)行問題的求解；文獻(xiàn)[2]用相對(duì)距離來(lái)確定隊(duì)形并采用分布式的導(dǎo)航函數(shù)形成隊(duì)形；文獻(xiàn)[3]通過自主切換控制率形成期望隊(duì)形;文獻(xiàn)[4]研究了未指定隊(duì)形位置的群體隊(duì)形聚集方法;文獻(xiàn)[5]提出了基于梯度的分散式控制率,這種方法使機(jī)器人群體收斂到某種隊(duì)形。

基于多智能體的機(jī)器人系統(tǒng)主要是借鑒多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建體系結(jié)構(gòu)。體系結(jié)構(gòu)是多機(jī)器人系統(tǒng)研究的重要內(nèi)容,通常將體系結(jié)構(gòu)分為群體和個(gè)體體系結(jié)構(gòu)。本文僅根據(jù)多個(gè)智能體的初始分布情況來(lái)選擇形成常用編隊(duì)隊(duì)形中的某種隊(duì)形,這樣可以避免智能體的移動(dòng)距離過遠(yuǎn),并減少智能體之間的沖突發(fā)生情況。對(duì)于隊(duì)形形成中的路徑規(guī)劃,在選擇好編隊(duì)隊(duì)形后,通過各個(gè)聯(lián)盟體中的通信智能體進(jìn)行各自的規(guī)劃,然后分享各自的規(guī)劃結(jié)果后再根據(jù)幾項(xiàng)指標(biāo)擇優(yōu),來(lái)完成隊(duì)形目標(biāo)點(diǎn)的分配。

1 智能體模型

智能體(agent)可以指一個(gè)具有自治能力的、能夠自適應(yīng)的、以認(rèn)識(shí)與模擬人類某種智能行為為目標(biāo)的硬件、軟件或其他實(shí)體。作為智能體,應(yīng)具有自治能力、社交能力、反應(yīng)能力以及主動(dòng)性,能夠感知周圍的環(huán)境,自治地運(yùn)行,并能夠影響和改變環(huán)境[6]。智能體由3個(gè)基本部分組成,如圖1所示。

圖1 智能體通用模型

智能體都有一個(gè)感知器來(lái)感知外部環(huán)境,能根據(jù)環(huán)境的狀態(tài)來(lái)改變自己的結(jié)構(gòu)和內(nèi)部狀態(tài),同時(shí)通過一個(gè)效應(yīng)器作用于外部環(huán)境,改變外部環(huán)境的狀態(tài)[7]。近年來(lái)將多智能體系統(tǒng)的理論應(yīng)用到多機(jī)器人系統(tǒng)中去,基本思想都是將每個(gè)機(jī)器人視為具有智能行為的智能體,從而借鑒多智能體系統(tǒng)理論來(lái)研究多機(jī)器人系統(tǒng)。本文將沿用這個(gè)思想,將兩輪差動(dòng)的智能移動(dòng)機(jī)器人模型視為智能體。

圖2 運(yùn)動(dòng)模型

由模型可知:

(1)

智能體的旋轉(zhuǎn)半徑可以表示為:

(2)

可以看出:當(dāng)vL=vR時(shí),Rω→∞,智能體沿直線行走;當(dāng)vL=-vR時(shí),Rω=0,智能體在原地旋轉(zhuǎn),旋轉(zhuǎn)半徑為0;其余情況下,智能體做圓弧運(yùn)動(dòng)。

本文智能體的感知器模擬聲納傳感器的工作機(jī)制來(lái)探測(cè)周圍環(huán)境,其分布示意圖如圖3所示。該傳感器僅探測(cè)智能體的前進(jìn)方向及其正負(fù)45°范圍內(nèi)的障礙物或智能體,因此設(shè)立3個(gè)傳感器,分別分布在前進(jìn)方向正前方,以及與正前方相隔±45°的方向,從左到右標(biāo)號(hào)為傳感器1～3,探測(cè)半徑設(shè)為700 cm,感知障礙物和智能體,并確定其方位。

圖3 智能體傳感器分布示意圖

2 隊(duì)形形成及其選擇算法

目標(biāo)位置優(yōu)化選擇算法[9]按照距離進(jìn)行隊(duì)形點(diǎn)的優(yōu)化分配規(guī)劃:

(1) 計(jì)算所有隊(duì)形點(diǎn)與所有智能體之間的距離,存入距離信息矩陣。

(2) 對(duì)每個(gè)隊(duì)形點(diǎn),將各個(gè)智能體與其的距離ρ進(jìn)行一個(gè)排序,將智能體按照最小ρ初步分配隊(duì)形點(diǎn)。

(3) 在隊(duì)形點(diǎn)初步分配之后,若出現(xiàn)多個(gè)智能體同時(shí)競(jìng)爭(zhēng)一個(gè)隊(duì)形點(diǎn)的情況,比較進(jìn)行競(jìng)爭(zhēng)的智能體的狀態(tài),將隊(duì)形點(diǎn)分配給相距隊(duì)形點(diǎn)距離較遠(yuǎn)的智能體。

(4) 更新距離信息矩陣,繼續(xù)隊(duì)形點(diǎn)的分配,直到完成隊(duì)形點(diǎn)分配。

目標(biāo)位置優(yōu)化選擇算法能夠在一定程度上優(yōu)化分配,減少隊(duì)形形成間的沖突,快速地形成隊(duì)形;但其僅將智能體與目標(biāo)點(diǎn)的直線距離作為一個(gè)衡量標(biāo)準(zhǔn),忽略了智能體方向角的問題,而通常智能體作為移動(dòng)式機(jī)器人時(shí),是無(wú)法以任意的角度進(jìn)行運(yùn)動(dòng)的,因此該算法并不能保證這個(gè)優(yōu)化結(jié)果是時(shí)間上最優(yōu)的結(jié)果。

2.1 隊(duì)形形成中的路徑規(guī)劃

隊(duì)形形成問題中要進(jìn)行路徑規(guī)劃首先要解決隊(duì)形選擇問題。多智能體的編隊(duì)通常采用“一”字形、柱形、“人”字形等一些形狀對(duì)稱的隊(duì)形,如圖4所示。

圖4 常用編隊(duì)隊(duì)形

一個(gè)合理的隊(duì)形對(duì)于完成任務(wù)的效率有很大的影響,比如為了捕捉獵物,必須選擇大圓形或小圓形的隊(duì)形,又如在比較復(fù)雜、障礙物比較多的環(huán)境中,采用柱形的隊(duì)形能更有效地避開障礙物。

2.2 隊(duì)形選擇生成方法

利用智能體群體的分布情況,本文提出一種比較簡(jiǎn)單的隊(duì)形選擇生成的方法:

(1) 收集所有智能體的信息狀態(tài)。

(2) 收集好信息之后,記錄當(dāng)前工作正常的智能體數(shù)量以及各個(gè)智能體的位姿情況。

(3) 將各個(gè)智能體橫坐標(biāo)以及縱坐標(biāo)分別形成向量,計(jì)算2個(gè)向量的均方差σx與σy,這2個(gè)均方差值分別代表了智能體群體在x軸與y軸的分散程度。

(4) 將2個(gè)均方差相減得到σΔ,與一個(gè)根據(jù)仿真所得到的經(jīng)驗(yàn)臨界值σλ進(jìn)行比較,判斷接近于哪個(gè)隊(duì)形。

(5) 隊(duì)形選擇完畢之后,以智能體當(dāng)前分布的橫縱坐標(biāo)平均值為隊(duì)形中心,按照一定的隊(duì)形點(diǎn)距離生成與工作正常的智能體一致數(shù)量的隊(duì)形點(diǎn)目標(biāo)。隊(duì)形選擇生成流程如圖5所示。

圖5 隊(duì)形選擇生成流程

2.3 改進(jìn)分配法

針對(duì)靜態(tài)隊(duì)形形成,本文的隊(duì)形選擇生成使得隊(duì)形圖的生成更加智能,有利于下一步的目標(biāo)點(diǎn)分配;相比于目標(biāo)位置優(yōu)化選擇算法,本文結(jié)合其優(yōu)點(diǎn),考慮智能體角度方面的影響,提出了改進(jìn)的目標(biāo)點(diǎn)優(yōu)化分配法，即改進(jìn)分配法。

改進(jìn)分配法規(guī)劃過程如下:

(1) 將前面生成的隊(duì)形點(diǎn)信息、收集到的所有智能體的位姿信息及智能體的數(shù)量送入規(guī)劃控制器,計(jì)算所有隊(duì)形點(diǎn)與所有智能體之間的距離,存入距離信息矩陣。

(2) 對(duì)每個(gè)隊(duì)形點(diǎn),將各個(gè)智能體與其的距離ρ進(jìn)行一個(gè)排序,可以得到各個(gè)智能體對(duì)于每個(gè)隊(duì)形點(diǎn)的遠(yuǎn)/近情況。

(3) 將隊(duì)形點(diǎn)進(jìn)行一個(gè)初步分配,每個(gè)智能體選出距離ρ最小或者在一定的誤差范圍內(nèi)的所有隊(duì)形點(diǎn)。

(4) 在隊(duì)形點(diǎn)初步分配之后,通常會(huì)出現(xiàn)多個(gè)智能體同時(shí)競(jìng)爭(zhēng)一個(gè)隊(duì)形點(diǎn)的情況,這時(shí)雖然從個(gè)體自私的角度考慮是各自最理想的狀態(tài),但整體上看是不能滿足每個(gè)智能體要求的,因此要從整體上再次進(jìn)行調(diào)整分配,解決分配沖突。

(5) 使用新的距離信息矩陣,重復(fù)步驟(2)～步驟(4)的分配過程,直到不再出現(xiàn)有沖突的隊(duì)形點(diǎn),再將其余隊(duì)形點(diǎn)依次按其最優(yōu)的分配即步驟(2) 、步驟(3)的方法進(jìn)行配對(duì)即可。最后輸出隊(duì)形點(diǎn)的分配信息,并按步驟(3)的方法輸出分配信息中最大距離ρ以及相應(yīng)的角度δe,同時(shí)輸出總距離以及總角度。流程圖如圖6所示。

圖6 改進(jìn)分配法的流程

計(jì)算智能體當(dāng)前角度δc與各隊(duì)形點(diǎn)的期望運(yùn)動(dòng)角度δR、相差角度δe最小的隊(duì)形點(diǎn),如圖7所示。

圖7 智能體和目標(biāo)點(diǎn)

智能體當(dāng)前位姿為[xcycδc]T,某一隊(duì)形目標(biāo)點(diǎn)為[xRyR]T,當(dāng)智能體與隊(duì)形點(diǎn)的直線方向角度δR與智能體當(dāng)前角度δc相差較大時(shí),即使兩者之間直線距離比較短,但仍需要先將角度調(diào)整到期望運(yùn)動(dòng)角度再直行,或者弧線進(jìn)行運(yùn)動(dòng)繞行,這不僅浪費(fèi)時(shí)間,還容易增加智能體之間的碰撞幾率。

因此對(duì)于只考慮了智能體與隊(duì)形點(diǎn)直線距離進(jìn)行分配的目標(biāo)位置優(yōu)化選擇算法,本文提出的改進(jìn)分配法同時(shí)考慮了智能體與隊(duì)形目標(biāo)點(diǎn)的距離以及角度,有利于隊(duì)形的快速生成。

3 Matlab仿真

選用5個(gè)智能體,位姿任意指定,并假設(shè)所有智能體工作都正常,沒有故障。仿真環(huán)境為無(wú)障礙(60×40) m2的地區(qū),智能體用小圓球表示,車身半徑取0.6 m,車輪半徑取0.08 m,智能體的朝向在圖中形象地表示出來(lái)。最大距離表示為maxLen,最大距離對(duì)應(yīng)的轉(zhuǎn)彎角為maxtheta,單位為弧度,總直線距離為totalLen,總轉(zhuǎn)彎角為totaltheta,單位為弧度,完成時(shí)步數(shù)為step。對(duì)使用改進(jìn)分配法和不使用改進(jìn)分配法進(jìn)行仿真實(shí)驗(yàn),結(jié)果如圖8所示,其中圖8b、圖8d、圖8f、圖8h為使用了改進(jìn)分配法的仿真結(jié)果。圖8a、圖8b中各個(gè)智能體初始位姿矩陣相同,最終輸出分別為:

圖8c、圖8d中各個(gè)智能體初始位姿矩陣相同,最終輸出分別為:

圖8e、圖8f中各個(gè)智能體初始位姿矩陣相同,最終輸出分別為:

圖8g、圖8h中各個(gè)智能體初始位姿矩陣相同,最終輸出分別為:

圖8 仿真實(shí)驗(yàn)結(jié)果

4 結(jié) 論

從圖8可以看出,規(guī)劃器按照智能體的分布智能選擇更易形成的隊(duì)形方案,形成步數(shù)都非常少,在50步左右就完成了隊(duì)形形成。從輸出看出,不使用分配法,增大了運(yùn)用步數(shù),增長(zhǎng)了行走的總距離,而且還容易發(fā)生碰撞。另外,對(duì)于中小數(shù)量的智能體,改進(jìn)分配法使用的是直接決策方法,對(duì)比于決策性算法,具有一定的時(shí)間優(yōu)勢(shì)。但是對(duì)于數(shù)量比較多的智能體,分析的內(nèi)容太多,不具有優(yōu)勢(shì),需要加入優(yōu)化策略改進(jìn)。

對(duì)比圖8a、8c、8e、8g和圖8b、8d、8f、8h可以發(fā)現(xiàn),每個(gè)隊(duì)形的分配都很合理,圖8b中以最簡(jiǎn)潔的分配形成“一”字形隊(duì)形。圖8d中左一智能體和左四智能體的分配考慮了轉(zhuǎn)彎角。如果不考慮轉(zhuǎn)彎角,即左一和左四兩者分配對(duì)調(diào),那么兩智能體都將轉(zhuǎn)彎180°左右,整體會(huì)更耗時(shí)。因此從整體考慮,采用改進(jìn)分配法更好地實(shí)現(xiàn)了隊(duì)形形成。圖8f中的分配右一和左一智能體在規(guī)劃中出現(xiàn)過沖突,但是以本文的比較參數(shù)來(lái)看,參數(shù)設(shè)定是合理的,對(duì)于左一智能體而言,2條路徑之差大于輪子轉(zhuǎn)動(dòng)一圈的長(zhǎng)度,因此選擇當(dāng)前的分配,這樣的分配也避免了2個(gè)智能體之間運(yùn)動(dòng)過程中的碰撞情況;圖8h中可以更明顯地看出分配沖突的發(fā)生,5個(gè)智能體之間相互都有選擇的沖突,從最終的輸出參數(shù)來(lái)看,整體的分配比較均勻,能以較快的速度形成隊(duì)形,證明了該文算法的合理性和有效性。

[1] SUGIHARA K,SUZUKI I.Distributed algorithms for formation of geometric patterns with many mobile robots[J].Journal of Robotic Systems,1996,13(3):127-139.

[2] DE GENNARO M C，JADBABAIE A.Formation control for a cooperative multi-agent system using decentralized navigation functions[C]//Proceedings of the 2006 American Control Conference，Minnesota:IEEE,2006:6.

[3] FIERRO R，DAS A K，VIJIAY KUMAR R，et al.Hybrid control of formations of robots[C]//Proceedings of the 2001 IEEE Internoational Conference on Robotics and Automation Vol 1 IEEE，2001:157-162.

[4] BELTA C，KUMAR V.Abstraction and control for groups of robots[J].IEEE Transactions on Robotics，2004，20(5): 865-875.

[5] HSIEH M A，KUMAR V，CHAIMOWICZ L.Decentralized controllers for shape generation with robotic swarms[J].Robotica，2008，26(5):691-701.

[6] 張進(jìn).基于智能體的多機(jī)器人協(xié)作的仿真系統(tǒng)[D].南京:南京理工大學(xué)，2003.

[7] 倪建軍.復(fù)雜系統(tǒng)多Agent建模與控制的理論及應(yīng)用[M].北京:電子工業(yè)出版社，2011.

[8] 郁伉,肖本賢,李艷紅.受非完整性約束的移動(dòng)機(jī)器人路徑跟蹤算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,33(9):1315-1319.

[9] 李強(qiáng).基于多智能體系統(tǒng)的機(jī)器人隊(duì)形控制與協(xié)作研究[D].無(wú)錫:江南大學(xué)，2011.

(責(zé)任編輯 張 镅)

Formation of multi-agent based on improved distribution algorithm

CHEN Mei,MEI Le,CHEN Yanyan

(School of Electric Engineering and Automation, Hefei University of Technology, Hefei 230009, China)

Multi-robot is the focus of present research. Robot formation is of importance in multi-robot research. Formation exists widely in nature, and the orderly aggregation and formation movement of geese and fish shows the great significance and effect of formation. Aiming at the formation of multi-robot, an improved algorithm based on the multi-agent structure is put forward. The structure of multi-agent has good adaptive characteristic, which is suitable for the multi-robot control. The improved distribution algorithm has good characteristic for formation.

multi-agent; multi-robot; formation; improved distribution algorithm

2015-04-28；

2015-07-08

陳 梅(1963-),女,安徽合肥人,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2016.10.008

TP273.5

A

1003-5060(2016)10-1336-05