基于勢(shì)函數(shù)的多智能體避撞隊(duì)形控制

姚立強(qiáng),宋艷榮,張術(shù)東

(1. 煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005; 2. 海軍航空工程學(xué)院系統(tǒng)科學(xué)與數(shù)學(xué)研究所,山東 煙臺(tái) 264001)

多智能體系統(tǒng)是控制領(lǐng)域的一個(gè)熱點(diǎn)研究方向.隊(duì)形控制是多智能體系統(tǒng)控制中的一類重要問(wèn)題.隊(duì)形控制是指多個(gè)移動(dòng)智能體在前進(jìn)過(guò)程中,整個(gè)智能體系統(tǒng)實(shí)現(xiàn)并維持預(yù)先給定的隊(duì)形,同時(shí)又要適應(yīng)環(huán)境約束的控制技術(shù).隊(duì)形控制問(wèn)題屬于多智能體系統(tǒng)的幾何問(wèn)題[1].現(xiàn)實(shí)生活中,隊(duì)形控制廣泛應(yīng)用于多移動(dòng)機(jī)器人編隊(duì)[2]、自治水下無(wú)人機(jī)組[3]、人造衛(wèi)星[4]、航天器等的協(xié)作中.

近年來(lái),隨著隊(duì)形控制問(wèn)題研究的深入,提出了多種隊(duì)形控制策略,主要包括Leader-follower法、Virtual structure 法、Behavior-based法和Artificial potential field法等.文獻(xiàn)[5]研究了在通信拓?fù)浣Y(jié)構(gòu)固定條件下,利用智能體之間的相對(duì)位置信息,設(shè)計(jì)反饋控制律,實(shí)現(xiàn)了對(duì)無(wú)領(lǐng)導(dǎo)者的多智能體系統(tǒng)隊(duì)形控制問(wèn)題.鄭軍將文獻(xiàn)[5]的結(jié)論推廣到離散系統(tǒng)[6],得到了確保多智能體系統(tǒng)漸近收斂的充要條件和反饋控制參數(shù)的取值范圍.文獻(xiàn)[7]對(duì)單積分模型系統(tǒng),利用多智能體之間相對(duì)位置的測(cè)量,提出了基于分布式位置估計(jì)的隊(duì)形控制策略.文獻(xiàn)[8]研究了在跟隨者未知參考速度的情況下,基于相對(duì)位置信息,利用自適應(yīng)方法設(shè)計(jì)動(dòng)態(tài)反饋控制器,使得系統(tǒng)實(shí)現(xiàn)期望隊(duì)形.

本文主要利用人工勢(shì)場(chǎng)法對(duì)無(wú)領(lǐng)導(dǎo)者的多智能體系統(tǒng)進(jìn)行隊(duì)形控制問(wèn)題研究.對(duì)目前現(xiàn)有文獻(xiàn)中運(yùn)用的避撞勢(shì)函數(shù)進(jìn)行一定程度的改進(jìn),使勢(shì)函數(shù)的形式更加簡(jiǎn)潔,更易于構(gòu)造,并運(yùn)用所提出的勢(shì)函數(shù)方法研究多智能體系統(tǒng)的隊(duì)形控制問(wèn)題,并且要求在形成期望隊(duì)形的過(guò)程中,智能體之間避免發(fā)生碰撞.

1 問(wèn)題的提出

考慮一類由N個(gè)智能體組成的多智能體系統(tǒng),第i(i=1,2,…,N)個(gè)智能體的位置模型如式(1)所示

(1)

其中:qi∈Rn是智能體i的位置向量,ui∈Rn是控制輸入.

注1 該系統(tǒng)是典型的分布式控制系統(tǒng).控制的目的就是在給定智能體通信規(guī)則的基礎(chǔ)上建立互相協(xié)作的控制策略,實(shí)現(xiàn)隊(duì)形控制目標(biāo).

注2 本文研究無(wú)領(lǐng)導(dǎo)者多智能系統(tǒng)避撞隊(duì)形控制問(wèn)題,信息接收方式是基于通信和避撞感知的,這里通信的拓?fù)浣Y(jié)構(gòu)固定,避撞感知拓?fù)浣Y(jié)構(gòu)是變化的.

為了更好地描述多智能體系統(tǒng)的隊(duì)形控制問(wèn)題,我們引入以下定義.

定義1[9](基于通信的智能體的鄰居集) 在由N個(gè)智能體組成的多智能體系統(tǒng)中,如果智能體i可以接收并利用智能體j的信息,則稱智能體j是智能體i的鄰居.由智能體i的所有鄰居組成的集合Ni(i=1,2,…,N)稱為智能體i的鄰居集.

定義2[9](避撞感知半徑) 在基于感知的多智能體系統(tǒng)中,為了實(shí)現(xiàn)智能體之間的避撞目的,智能體i與其能夠接收并利用信息的智能體之間距離的最大值稱為智能體i的避撞感知半徑,記為Ri.

定義3[9](基于感知的智能體的鄰居集) 如果多智能體系統(tǒng)中的智能體j位于智能體i的避撞感知區(qū)域內(nèi),即2個(gè)智能體的相對(duì)位置滿足‖qi-qj‖

Nαi={j|‖qi-qj‖

j≠i;j=1,2,…,N} (i=1,2,…,N)

(2)

稱為智能體i的鄰居集.

智能體之間的避撞控制目標(biāo)用數(shù)學(xué)形式可以描述為

?t>0,

‖qi(t)-qj(t)‖→/ 0. (i≠j;i,j=1,…,N)

(3)

描述智能體的隊(duì)形以一組向量來(lái)表示,我們稱這組向量為期望隊(duì)形.為了清楚地描述隊(duì)形,引入期望隊(duì)形的定義,并根據(jù)期望隊(duì)形給出多智能體系統(tǒng)實(shí)現(xiàn)隊(duì)形控制的目標(biāo).

定義4[6](期望隊(duì)形) 期望隊(duì)形就是某個(gè)向量h=col(h1,h2,…,hN),其中hi是智能體i相對(duì)某個(gè)參照點(diǎn)的相對(duì)位置.

如果多智能體系統(tǒng)中任意智能體的位置向量滿足

qi-qj=hi-hj.(i≠j;i,j=1,2,…,N)

則稱多智能體系統(tǒng)實(shí)現(xiàn)期望隊(duì)形h.等價(jià)地,如果存在r(t)使得

qi=r(t)+hi.(i=1,2,…,N)

(4)

則稱多智能體系統(tǒng)實(shí)現(xiàn)期望隊(duì)形h.

注3 期望隊(duì)形中兩智能體之間的距離總是大于它們的避撞感知半徑.

若記智能體通信拓?fù)鋵?duì)應(yīng)的無(wú)向圖為G,智能體避撞感知拓?fù)鋵?duì)應(yīng)的無(wú)向圖為Gα.本文控制問(wèn)題可以描述為:在給定通信拓?fù)銰的條件下,建立基于通信拓?fù)涞膮f(xié)作控制輸入ui,使得多智能體系統(tǒng)(1)滿足避撞控制目標(biāo)(3)和隊(duì)形控制目標(biāo)(4).

2 準(zhǔn)備工作

令G=(ν,ε)表示帶n個(gè)節(jié)點(diǎn)的圖,其中ν={v1,v2,…,vn}為節(jié)點(diǎn)集合,ε?ν×ν為邊集合.如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在信息交互,則這2個(gè)節(jié)點(diǎn)有邊相連.在無(wú)向圖G中,如果任意2個(gè)節(jié)點(diǎn)間都有路徑,則稱無(wú)向圖G是連通的.

為了描述節(jié)點(diǎn)與邊的關(guān)系,對(duì)于有n個(gè)節(jié)點(diǎn)的無(wú)向圖G,我們可以定義鄰接矩陣A(G)=[aij](i,j=1,2,…,n)為

對(duì)于無(wú)向圖,鄰接矩陣A是對(duì)稱的,對(duì)于有向圖,該矩陣不具備這樣的性質(zhì).

圖G的Laplace矩陣L=[lij](i,j=1,2,…,n)定義為L(zhǎng)=ΔG-A(G).

引理1[10]無(wú)向圖G的Laplace矩陣L具有以下性質(zhì)

1)L是對(duì)稱的且半正定;0是矩陣L的特征值,其對(duì)應(yīng)的特征向量為1N;

2) 如果無(wú)向圖G是連通的,則0是矩陣L的代數(shù)重度為1的特征值;

3) 根據(jù)Gershgorin圓盤(pán)定理,L的所有特征值位于一個(gè)以Nmax為半徑的圓盤(pán)中(其中Nmax是圖G中頂點(diǎn)的最大鄰居數(shù)).

3 控制策略的設(shè)計(jì)

隊(duì)形控制對(duì)智能體的相對(duì)位置有特定的要求,所以必須構(gòu)造相應(yīng)的勢(shì)函數(shù),該勢(shì)函數(shù)能產(chǎn)生指向相對(duì)位置的“力場(chǎng)”驅(qū)使智能體實(shí)現(xiàn)相對(duì)位置,使得整個(gè)系統(tǒng)進(jìn)入平衡狀態(tài).否則,“力場(chǎng)”會(huì)一直發(fā)揮作用,直至整個(gè)系統(tǒng)進(jìn)入平衡狀態(tài).

定義5(位置匹配勢(shì)函數(shù)生成函數(shù)) 與給定的向量h匹配的勢(shì)函數(shù)生成函數(shù)V(x,h)是一個(gè)非負(fù)、連續(xù)可微的函數(shù),且滿足

1)V(x,h)=V(-x,-h);

2)V(x,h)=0成立當(dāng)且僅當(dāng)x=h;

3) 當(dāng)‖x-h‖→∞時(shí),V(x,h)→∞.

注4 位置匹配勢(shì)函數(shù)可以取為V(qi-qj,hi-hj).為了區(qū)分不同智能體的位置匹配勢(shì)函數(shù),我們用Vij(qi-qj,hi-hj)表示智能體i和智能體j之間的位置匹配勢(shì)函數(shù),簡(jiǎn)記為Vij.

當(dāng)2個(gè)智能體之間的距離很小時(shí),2個(gè)智能體之間會(huì)產(chǎn)生“力場(chǎng)”,該“力場(chǎng)”使智能體能夠向著距離增大的方向運(yùn)動(dòng)就可以解決智能體之間的避撞問(wèn)題.我們將“力場(chǎng)”作用在智能體上的力稱為反作用力.與智能體i產(chǎn)生反作用力相關(guān)的特定值就是智能體i的避撞感知半徑的大小.

注5 避撞勢(shì)函數(shù)生成函數(shù)中的a就是智能體i的避撞感知半徑Ri.

注6 避撞勢(shì)函數(shù)要比現(xiàn)有文獻(xiàn)中已有的避撞勢(shì)函數(shù)形式簡(jiǎn)潔得多.

證明定義智能體i總的避撞勢(shì)函數(shù)為

(5)

定義智能體i總的位置匹配勢(shì)函數(shù)為

(6)

定義多智能體系統(tǒng)(1)總的能量W為系統(tǒng)智能體總的位置匹配勢(shì)函數(shù)和避撞勢(shì)函數(shù)之和,簡(jiǎn)稱能量函數(shù).它的表達(dá)式如下

(7)

從能量函數(shù)W的表達(dá)式可以知道該函數(shù)是一個(gè)半正定的函數(shù),并且

(8)

設(shè)計(jì)智能體i的控制輸入的形式為

(9)

由于

(10)

(11)

將式(9)、(10)、(11)代入式(8)中,得到

(12)

W(t)≤W0.

(13)

qi-hi=qj-hj. (i≠j;i,j=1,2,…,N)

(14)

即

(15)

其中:L是圖G的Laplace矩陣.

即

qi=r(t)1n+hi. (i=1,2,…,N)

(16)

這樣,由式(16)可知,在控制輸入(9)的作用下,多智能體系統(tǒng)(1)最終形成預(yù)先給定的期望隊(duì)形,從而實(shí)現(xiàn)隊(duì)形控制目標(biāo)(4).

為了實(shí)現(xiàn)避撞控制目標(biāo)(3),需要證明系統(tǒng)中的智能體在任何時(shí)刻都不會(huì)發(fā)生碰撞.下面,用反證法來(lái)證明這個(gè)問(wèn)題.

假設(shè)多智能體系統(tǒng)中至少有2個(gè)智能體r和e在時(shí)刻t1>0相撞,即r和e在時(shí)刻t1的位置滿足

qr(t1)=qe(t1), (r≠e;r,e=1,2,…,N)

由避障勢(shì)函數(shù)定義和式(5)可知

由于t=t1時(shí),qr(t1)=qe(t1),即t→t1時(shí)有

(17)

另一方面,由式(7)、定義5、定義7可知

(18)

由于系統(tǒng)總的能量W0為有限數(shù),這樣式(18)和(17)產(chǎn)生矛盾.說(shuō)明假設(shè)錯(cuò)誤,即多智能體系統(tǒng)在行進(jìn)過(guò)程中智能體之間不會(huì)發(fā)生碰撞.

由上面的分析可知,在設(shè)計(jì)的控制輸入(9)的作用下,多智能體系統(tǒng)(1)可以實(shí)現(xiàn)避撞控制目標(biāo)(3)和隊(duì)形控制目標(biāo)(4).證畢.

4 仿真實(shí)例

Vij=(qi-qj-hi+hj)T(qi-qj-hi+hj).

(i≠j;i,j=1,2,…,49)

選取的避撞勢(shì)函數(shù)為

其中:qi=(xi,yi)T,Ri是智能體i的避撞感知半徑,Ri=0.2.

仿真中發(fā)現(xiàn),位置匹配勢(shì)函數(shù)的權(quán)重系數(shù)影響反饋的增益,較大的權(quán)重會(huì)使智能體的隊(duì)形對(duì)齊速度加快,較小的權(quán)重則可以使速度變慢.這里為了得到理想的仿真效果,對(duì)位置匹配勢(shì)函數(shù)做了調(diào)整,令其前面的權(quán)重為0.051,避撞勢(shì)函數(shù)的權(quán)重為1.

當(dāng)49個(gè)智能體的初始位置在[-2,2]×[-2,2]的區(qū)域內(nèi)隨機(jī)選取、通信拓?fù)湓诒ＷC連通的前提下隨機(jī)指定時(shí),仿真結(jié)果如圖1所示.

從圖1中的6幅圖中可以看出,初始時(shí)刻49個(gè)智能體是雜亂無(wú)章的,第8秒時(shí)智能體分散開(kāi)向著圓形隊(duì)形的方位運(yùn)動(dòng),到第17秒時(shí)智能體基本到達(dá)期望隊(duì)形區(qū)域,最終在第40秒實(shí)現(xiàn)圓形隊(duì)形.從仿真結(jié)果可以看出,智能體在位置匹配勢(shì)函數(shù)產(chǎn)生的力場(chǎng)的作用下,向著指定位置逼近,最終會(huì)進(jìn)入事先指定的隊(duì)形,即實(shí)現(xiàn)隊(duì)形控制目標(biāo).

注7 仿真中的49個(gè)智能體最終會(huì)形成圓形隊(duì)形,但是圓形隊(duì)形最終在平面上的位置是不能指定的,該位置和智能體的初始位置的選擇有關(guān),還與智能體的通信拓?fù)浼粗悄荏w之間的協(xié)作方式有關(guān).

5 小 結(jié)

本文利用勢(shì)函數(shù)方法研究了多智能體的隊(duì)形控制問(wèn)題,通過(guò)構(gòu)造位置勢(shì)函數(shù)和避撞勢(shì)函數(shù),給出了隊(duì)形控制的控制策略,并證明了在該控制策略的作用下,系統(tǒng)能夠?qū)崿F(xiàn)期望的隊(duì)形,且不會(huì)發(fā)生碰撞.最后,利用仿真說(shuō)明了該方法的可行性和有效性.

圖1 49個(gè)智能體的隊(duì)形控制圖

參考文獻(xiàn):

[1]任德華,盧桂章.對(duì)隊(duì)形控制的思考[J].控制與決策,2005, 20(6): 601-606.

[2]張明,嚴(yán)衛(wèi)生,高劍.實(shí)時(shí)位置反饋的多機(jī)器人主從式編隊(duì)控制[J].火力與指揮控制,2012,37(2):12-15.

[3]Wang Yintao, Yan Weisheng, Li Junbing. Passivity-based formation control of autonomous underwater vehicles [J]. IET Control Theory & Application, 2012, 6(4): 518-525.

[4]Wu Yunhua, Cao Xinbin, Zheng Pengfei, et al. Variable structure-based decentralized relative attitude-coordinated control for satellite formation [J]. IEEE Aerospace and Electronic Systems Magazine, 2012, 27(12): 18-25.

[5]Lafferriere G, Williams A, Caughman J, et al. Decentralized control of vehicle formations[J]. Systems and Control Letters， 2005, 54(9): 899-910.

[6]鄭軍,顏文俊.一類分布式隊(duì)形控制及其穩(wěn)定性分析[J].自動(dòng)化學(xué)報(bào),2008,34(9):1107-1112.

[7]Oh Kwang-kyo, Ahn Hyo-sung. Formation control of mobile agents based on distributed position estimation [J]. IEEE Transactions on Automatic Control, 2013, 58(3): 737-742.

[8]郭靜.僅基于相對(duì)位置或角度信息的多智能體系統(tǒng)隊(duì)形協(xié)調(diào)控制[D].杭州:浙江大學(xué),2011.

[9]Su Housheng, Wang Xiaofan, Lin Zongli. Flocking of multi-agents with a virtual Leader [J].IEEE Transactions on Automatic Control, 2009, 54(2): 293-307.

[10]Olfati-saber R.Flocking for multi-agent dynamic systems:Algorithms and theory[J].IEEE Transactions on Automatic Control, 2006, 51(3): 401-420.

[11]鐘守銘,劉碧森,王曉梅,等.神經(jīng)網(wǎng)絡(luò)穩(wěn)定性理論[M].北京:科學(xué)出版社,2008:150-151.