基于改進分配法的多智能體隊形形成

陳 梅,梅 樂,陳艷燕

(合肥工業大學 電氣與自動化工程學院,安徽 合肥 230009)

?

基于改進分配法的多智能體隊形形成

陳 梅,梅 樂,陳艷燕

(合肥工業大學 電氣與自動化工程學院,安徽 合肥 230009)

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

多智能體;多機器人;隊形形成;改進分配算法

0 引 言

關于多智能體隊形形成的問題研究,主要需要解決的是各個智能體如何確定自身的隊形目標點以及如何快速無碰撞地到達目標點。文獻[1]提出對直線隊形和圓形隊形形成的算法,這一類方法可以歸為傳統方法,也有學者運用勢場法進行問題的求解；文獻[2]用相對距離來確定隊形并采用分布式的導航函數形成隊形；文獻[3]通過自主切換控制率形成期望隊形;文獻[4]研究了未指定隊形位置的群體隊形聚集方法;文獻[5]提出了基于梯度的分散式控制率,這種方法使機器人群體收斂到某種隊形。

基于多智能體的機器人系統主要是借鑒多智能體系統的拓撲結構來構建體系結構。體系結構是多機器人系統研究的重要內容,通常將體系結構分為群體和個體體系結構。本文僅根據多個智能體的初始分布情況來選擇形成常用編隊隊形中的某種隊形,這樣可以避免智能體的移動距離過遠,并減少智能體之間的沖突發生情況。對于隊形形成中的路徑規劃,在選擇好編隊隊形后,通過各個聯盟體中的通信智能體進行各自的規劃,然后分享各自的規劃結果后再根據幾項指標擇優,來完成隊形目標點的分配。

1 智能體模型

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

圖1 智能體通用模型

智能體都有一個感知器來感知外部環境,能根據環境的狀態來改變自己的結構和內部狀態,同時通過一個效應器作用于外部環境,改變外部環境的狀態[7]。近年來將多智能體系統的理論應用到多機器人系統中去,基本思想都是將每個機器人視為具有智能行為的智能體,從而借鑒多智能體系統理論來研究多機器人系統。本文將沿用這個思想,將兩輪差動的智能移動機器人模型視為智能體。

圖2 運動模型

由模型可知:

(1)

智能體的旋轉半徑可以表示為:

(2)

可以看出:當vL=vR時,Rω→∞,智能體沿直線行走;當vL=-vR時,Rω=0,智能體在原地旋轉,旋轉半徑為0;其余情況下,智能體做圓弧運動。

本文智能體的感知器模擬聲納傳感器的工作機制來探測周圍環境,其分布示意圖如圖3所示。該傳感器僅探測智能體的前進方向及其正負45°范圍內的障礙物或智能體,因此設立3個傳感器,分別分布在前進方向正前方,以及與正前方相隔±45°的方向,從左到右標號為傳感器1～3,探測半徑設為700 cm,感知障礙物和智能體,并確定其方位。

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

2 隊形形成及其選擇算法

目標位置優化選擇算法[9]按照距離進行隊形點的優化分配規劃:

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

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

(3) 在隊形點初步分配之后,若出現多個智能體同時競爭一個隊形點的情況,比較進行競爭的智能體的狀態,將隊形點分配給相距隊形點距離較遠的智能體。

(4) 更新距離信息矩陣,繼續隊形點的分配,直到完成隊形點分配。

目標位置優化選擇算法能夠在一定程度上優化分配,減少隊形形成間的沖突,快速地形成隊形;但其僅將智能體與目標點的直線距離作為一個衡量標準,忽略了智能體方向角的問題,而通常智能體作為移動式機器人時,是無法以任意的角度進行運動的,因此該算法并不能保證這個優化結果是時間上最優的結果。

2.1 隊形形成中的路徑規劃

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

圖4 常用編隊隊形

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

2.2 隊形選擇生成方法

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

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

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

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

(4) 將2個均方差相減得到σΔ,與一個根據仿真所得到的經驗臨界值σλ進行比較,判斷接近于哪個隊形。

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

圖5 隊形選擇生成流程

2.3 改進分配法

針對靜態隊形形成,本文的隊形選擇生成使得隊形圖的生成更加智能,有利于下一步的目標點分配;相比于目標位置優化選擇算法,本文結合其優點,考慮智能體角度方面的影響,提出了改進的目標點優化分配法，即改進分配法。

改進分配法規劃過程如下:

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

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

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

(4) 在隊形點初步分配之后,通常會出現多個智能體同時競爭一個隊形點的情況,這時雖然從個體自私的角度考慮是各自最理想的狀態,但整體上看是不能滿足每個智能體要求的,因此要從整體上再次進行調整分配,解決分配沖突。

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

圖6 改進分配法的流程

計算智能體當前角度δc與各隊形點的期望運動角度δR、相差角度δe最小的隊形點,如圖7所示。

圖7 智能體和目標點

智能體當前位姿為[xcycδc]T,某一隊形目標點為[xRyR]T,當智能體與隊形點的直線方向角度δR與智能體當前角度δc相差較大時,即使兩者之間直線距離比較短,但仍需要先將角度調整到期望運動角度再直行,或者弧線進行運動繞行,這不僅浪費時間,還容易增加智能體之間的碰撞幾率。

因此對于只考慮了智能體與隊形點直線距離進行分配的目標位置優化選擇算法,本文提出的改進分配法同時考慮了智能體與隊形目標點的距離以及角度,有利于隊形的快速生成。

3 Matlab仿真

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

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

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

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

圖8 仿真實驗結果

4 結 論

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

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

[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] 張進.基于智能體的多機器人協作的仿真系統[D].南京:南京理工大學，2003.

[7] 倪建軍.復雜系統多Agent建模與控制的理論及應用[M].北京:電子工業出版社，2011.

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

[9] 李強.基于多智能體系統的機器人隊形控制與協作研究[D].無錫:江南大學，2011.

(責任編輯 張 镅)

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-),女,安徽合肥人,合肥工業大學副教授,碩士生導師.

10.3969/j.issn.1003-5060.2016.10.008

TP273.5

A

1003-5060(2016)10-1336-05