基于MAS的合作—競爭編隊(duì)研究

王 瀟，紀(jì)志堅(jiān)

(青島大學(xué)自動(dòng)化學(xué)院，山東 青島 266071)

0 引言

近年來，多智能體系統(tǒng)(MAS)的編隊(duì)運(yùn)動(dòng)問題引起了國內(nèi)外學(xué)者的廣泛關(guān)注[1-2]，與傳統(tǒng)控制系統(tǒng)相比，多智能體系統(tǒng)具有巨大的優(yōu)越性、可靠性、靈活性和對不確定環(huán)境的適應(yīng)性。多智能體編隊(duì)運(yùn)動(dòng)在自然界、工程實(shí)踐和軍事應(yīng)用中都是重要的，從天體運(yùn)動(dòng)到電子運(yùn)動(dòng)，從動(dòng)物的群集或訓(xùn)練行為到生物細(xì)胞運(yùn)動(dòng)，編隊(duì)運(yùn)動(dòng)廣泛存在于宏觀和微觀之中。

在自然界中，動(dòng)物集體聚集通過避免捕食者和有效覓食而使同類動(dòng)物受益。在自然現(xiàn)象的啟發(fā)下，研究人員開發(fā)了一些重要的方法來實(shí)現(xiàn)一組智能體的編隊(duì)運(yùn)動(dòng)。在開創(chuàng)性的工作中，Craig Reynolds建立了一個(gè)模擬的“Boids”模型，并提出3個(gè)行為規(guī)則：凝聚、分離、調(diào)整規(guī)則[3]。在過去的幾年里，人們對編隊(duì)控制問題進(jìn)行了很多改進(jìn)，目前編隊(duì)控制方法主要可分為3類：基于行為法[4]、虛擬結(jié)構(gòu)法[5-6]、領(lǐng)導(dǎo)者—跟隨者法[7-13]。基于行為法通過調(diào)節(jié)權(quán)重以實(shí)現(xiàn)多智能體系統(tǒng)的最優(yōu)編隊(duì)控制，是從動(dòng)物的群體行為中抽象出來的一種方法，此方法適用于分散控制，但在控制設(shè)計(jì)和穩(wěn)定性分析方面存在困難。虛擬結(jié)構(gòu)法由M.Anthony Lewis提出，將所有智能體視為單個(gè)實(shí)體，編隊(duì)控制精度較高，此方法下編隊(duì)隊(duì)形可任意設(shè)定，但是很難確定虛擬參考點(diǎn)并傳輸其狀態(tài)信息，很難實(shí)現(xiàn)編隊(duì)中各智能體的信息同步。在這3類多智能體系統(tǒng)編隊(duì)控制方法中，領(lǐng)導(dǎo)者—跟隨者法最為流行，由于其方便、易分析、易實(shí)現(xiàn)而在多智能體編隊(duì)控制問題中得到了廣泛的研究[14]。在領(lǐng)導(dǎo)者—跟隨者方法中，領(lǐng)導(dǎo)者是明確的和突出的[15]，指定一些智能體作為領(lǐng)導(dǎo)者，其余智能體為跟隨者，通過控制協(xié)議引導(dǎo)跟隨者與相應(yīng)的領(lǐng)導(dǎo)者保持所需的相對位置和方向,在本文中主要研究了基于領(lǐng)導(dǎo)者—跟隨者方法的多智能體編隊(duì)控制問題。

在上述參考文獻(xiàn)中，智能體通常與一些簡單的控制協(xié)議互連，通過合作關(guān)系交換信息來實(shí)現(xiàn)和保持期望的編隊(duì)。也就是說，多智能體系統(tǒng)的通信權(quán)值是非負(fù)的，事實(shí)上，合作與競爭在自然界與社會制度中廣泛存在，有些智能體可能會合作，而另一些智能體則會反對[16-17]。然而，對于具有合作—競爭關(guān)系的智能體，在編隊(duì)控制方面幾乎沒有結(jié)果，這可能是未來戰(zhàn)場的潛在應(yīng)用。本文首先利用有向符號圖提出了具有合作—競爭關(guān)系的多智能體系統(tǒng)的編隊(duì)控制問題，然后為每一個(gè)智能體設(shè)計(jì)編隊(duì)控制算法，以實(shí)現(xiàn)期望的編隊(duì)隊(duì)形。

本文符號：Rn和Rn×n分別表示n維歐氏空間和n×n實(shí)矩陣的集合。In是n×n維單位矩陣，?表示克羅內(nèi)克積。給定兩個(gè)集合X和Y，XY表示其元素屬于X但不屬于Y的集合，C>0和C<0分別表示復(fù)平面的右半開平面和左半開平面。

1 預(yù)備知識

考慮一個(gè)由有向符號圖G=(V,E,A)表示的多智能體網(wǎng)絡(luò)，其中V={v1,…,vn}表示圖的頂點(diǎn)集，邊集E∈V×V表示智能體與智能體之間的交互。在有向圖中，邊是由兩個(gè)頂點(diǎn)組成的有序?qū)Γ?vi,vj)表示一條有向邊，vi表示邊的起點(diǎn)，vj表示邊的終點(diǎn)，即(vi,vj)和(vj,vi)是兩條不同的有向邊。在有向圖中，有向邊也稱為弧，始點(diǎn)稱為弧尾，終點(diǎn)稱為弧頭。有向圖G中eij=(vj,vi)∈E,則稱頂點(diǎn)vj為vi的鄰居，vi的鄰居集合可以表示為Ni={vj∈N:eij=(vj,vi)∈E,j≠i}。如果(vi,vi)∈E，則稱有向圖G帶有自環(huán)。沒有多重邊結(jié)構(gòu)以及環(huán)結(jié)構(gòu)的圖稱為簡單圖，本文研究的都為簡單圖。在有向圖G中，如果對于每一對vi、vj，vi≠vj，從vi到vj和從vj到vi都存在路徑，則稱圖G是強(qiáng)連通圖。對于有向圖，將所有的有向邊替換為無向邊，所得到的圖稱為原圖的基礎(chǔ)圖，如果一個(gè)有向圖的基礎(chǔ)圖是連通圖，則有向圖被稱為弱連通圖。將多智能體個(gè)體按照是否接受外部控制輸入分為領(lǐng)導(dǎo)者與跟隨者，領(lǐng)導(dǎo)者集合表示為Vl={v1,v2,…,vm}，并且滿足v1

圖G的鄰接矩陣A=[aij]∈Rn×n描述一個(gè)圖節(jié)點(diǎn)之間的信息交流，定義為

(1)

其中，wij表示邊的權(quán)重，本文中wij:E→{±1}用正或者負(fù)權(quán)重來捕獲智能體之間的合作和競爭關(guān)系。具體地說，如果wij=1，vj稱為vi的正鄰居；如果wij=-1，則稱vj是vi的負(fù)鄰居，其中正鄰居表示合作交互，而負(fù)鄰居表示vj和vi的競爭交互。

有向圖G的拉普拉斯矩陣L=(lij)定義為

(2)

有向圖G中的度矩陣定義為Δ=[Δij]，其中當(dāng)i=j時(shí)，Δ=ID(vi)；否則，Δij=0。由此可見，圖G的拉普拉斯矩陣可以表示為

L=Δ-A

(3)

如圖1所示，每個(gè)圓圈中的數(shù)字表示節(jié)點(diǎn)集N={1,2,…,12}中的節(jié)點(diǎn)。為了簡潔起見，省略了拓?fù)鋱D的權(quán)重。圖中有3個(gè)獨(dú)立強(qiáng)連通分量，由節(jié)點(diǎn)集{1}、{2}和{5,6}誘導(dǎo)組成。有向圖中的極大強(qiáng)連通子圖稱作為有向圖的強(qiáng)連通分量(SCC)，一個(gè)圖的極大強(qiáng)連通子圖加入任何一個(gè)不在它點(diǎn)集中的點(diǎn)都會導(dǎo)致它不再強(qiáng)連通，值得

圖1 12節(jié)點(diǎn)拓?fù)鋱D

注意的是，由節(jié)點(diǎn)集{7,8,9}、{10,11,12}誘導(dǎo)的并不是iSCC而是SCC。由于有向圖的一個(gè)頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，所以任何有向圖都包含最多m(1≤m≤n)個(gè)獨(dú)立強(qiáng)連通分量。

引理1[18]假設(shè)方陣A是不可約矩陣，D是對角矩陣。那么A+D也是不可約矩陣。

引理2[18]A=[aij]∈Rn×n是圖G的鄰接矩陣，假設(shè)λ是A的特征值，滿足不等式：

如果圖G是強(qiáng)連通的，則：

1)每個(gè)蓋爾圓通過λ，

引理3[19]假設(shè)有向圖G=(N,E,A)是弱連通的，L是G的拉普拉斯矩陣。當(dāng)且僅當(dāng)G=(N,E,A)包含m個(gè)獨(dú)立強(qiáng)連通分量時(shí)，則Rank(L)=n-m。

2 MAS編隊(duì)控制協(xié)議

如何實(shí)現(xiàn)多智能體系統(tǒng)的合作—競爭編隊(duì)運(yùn)動(dòng)，具有重要的理論和現(xiàn)實(shí)意義，但同時(shí)也是當(dāng)前我們面臨的一大挑戰(zhàn)。本文試圖對這一復(fù)雜問題進(jìn)行研究。為了便于描述，我們在這里研究了6個(gè)和8個(gè)多智能體系統(tǒng)的合作—競爭編隊(duì)運(yùn)動(dòng)。

考慮由n個(gè)智能體組成的多智能體系統(tǒng)，每個(gè)智能體都被看作是有向圖G中的一個(gè)節(jié)點(diǎn)。每條邊(vi,vj)∈E對應(yīng)于智能體之間的信息傳遞通道，假設(shè)第i個(gè)智能體具有式(4)的動(dòng)力學(xué)方程：

(4)

其中xi∈Rn代表多智能體的狀態(tài)，ui稱為控制協(xié)議。設(shè)Vl={i1,…,im}是有外部控制輸入的領(lǐng)導(dǎo)者集合，Vf代表剩余的多智能體集合，即跟隨者集合。每個(gè)智能體i的動(dòng)力學(xué)為

(5)

其中ri是多智能體系統(tǒng)的外部控制輸入。

圖2 6智能體合作—競爭交互網(wǎng)絡(luò)

圖3 8智能體合作—競爭交互網(wǎng)絡(luò)

該6個(gè)和8個(gè)智能體構(gòu)成合作—競爭交互網(wǎng)絡(luò)，用有符號圖G=(V,E,A)來描述。在圖2和圖3中，實(shí)線邊和虛線邊分別表示智能體的合作關(guān)系和競爭關(guān)系。為了方便起見，我們使用正、負(fù)權(quán)值來描述有符號圖理論中的這種關(guān)系。

在編隊(duì)控制問題中，一個(gè)編隊(duì)目標(biāo)向量di∈Rn從一開始就被分配給每個(gè)智能體i∈V。變量di-dj可以表示智能體i和智能體j的相對編隊(duì)向量，它與參考坐標(biāo)無關(guān)。所有的智能體都必須通過收集鄰居的信息來轉(zhuǎn)移到想要的位置。當(dāng)多智能體系統(tǒng)中所有智能體的狀態(tài)滿足：

(6)

我們認(rèn)為合作—競爭編隊(duì)形成。

在農(nóng)場中，牧羊犬必須讓羊群遠(yuǎn)離莊稼，牧羊犬觀察羊群的行為在綿羊看來可能是一種對立競爭的行為。在這種對抗行為下，牧羊犬和羊群可以形成牧羊人所期望的形態(tài)。根據(jù)此局部交互規(guī)則，智能體i的編隊(duì)控制ui(t)設(shè)計(jì)如式(7)：

(7)

其中,Ni是智能體i的鄰居集，aij≠0是有限集合中的加權(quán)因子。B=diag(b1,b2,…,bN)為外部控制輸入矩陣，這里：

(8)

bi=1表示外部控制輸入ri作用于智能體i，否則bi=0。外部控制輸入ri設(shè)計(jì)如式(9)：

ri=-Ki(xi-di)

(9)

因此，多智能體i的動(dòng)力學(xué)可修改為

(10)

(11)

(12)

3 MAS編隊(duì)穩(wěn)定性

定義2[20]如果一個(gè)有符號圖G的節(jié)點(diǎn)集可以劃分為兩個(gè)不相交的子集，其中一個(gè)子集可以是空集。使得同一子集中的兩個(gè)節(jié)點(diǎn)aij≥0，而不同子集中的兩個(gè)節(jié)點(diǎn)的aij≤0，則稱圖G為結(jié)構(gòu)平衡；否則就是結(jié)構(gòu)不平衡。

虛線代表負(fù)加權(quán)邊。圖4 兩個(gè)結(jié)構(gòu)平衡的有向圖

虛線代表負(fù)加權(quán)邊。圖5 兩個(gè)結(jié)構(gòu)不平衡的有向圖

一個(gè)有向圖G中的極大強(qiáng)連通子圖稱為有向圖的獨(dú)立強(qiáng)連通分量(iSCC)。如果iSCC是結(jié)構(gòu)平衡的，則有符號圖G的獨(dú)立強(qiáng)連通分量被稱為結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量(SBiSCC)。否則，iSCC被稱為結(jié)構(gòu)不平衡的獨(dú)立強(qiáng)連通分量(SUiSCC)。

定理1假設(shè)有向符號圖G是弱連通的，圖G包含c個(gè)不同的結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量，則結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量的拓?fù)鋱DGs=(Vs,Es),s∈Nc。當(dāng)且僅當(dāng)Vl∩Vs≠φ，由動(dòng)力學(xué)(5)和控制協(xié)議(7)控制的多智能體系統(tǒng)是穩(wěn)定的，即多智能體系統(tǒng)中的所有智能體的狀態(tài)滿足式(6)，可以形成期望的合作—競爭編隊(duì)運(yùn)動(dòng)。此外，接收外部控制輸入的最小節(jié)點(diǎn)數(shù)等于結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量的數(shù)目。

證明：注意有符號圖的穩(wěn)定性問題不同于無符號圖的穩(wěn)定性問題。由于有符號圖G包含c個(gè)不同的結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量，在不喪失一般性的情況下，假設(shè)(11)的L和D是

4 數(shù)值仿真

例1考慮一個(gè)具有xi:=(xi1,xi2)∈R2的多智能體系統(tǒng)，由6個(gè)節(jié)點(diǎn)的有符號有向圖表示，如圖2所示。我們已經(jīng)知道這個(gè)圖中有2個(gè)結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量，將節(jié)點(diǎn)1和節(jié)點(diǎn)6被選擇為領(lǐng)導(dǎo)者，其余節(jié)點(diǎn)為跟隨者。圖2的拉普拉斯矩陣為

假設(shè)所有智能體的初始位置都是隨機(jī)選擇的，分散的外部控制輸入可以作為r1=-(x1-d1)和r6=-(x6-d6)。多智能體系統(tǒng)的目標(biāo)是獲得一個(gè)三角形的編隊(duì)隊(duì)形，其中位置矢量被假定為

雖然多智能體的初始位置是隨機(jī)選擇的，但多智能體可以實(shí)現(xiàn)三角形的編隊(duì)隊(duì)形，如圖6所示。

注：星號和三角形分別表示t=0 s和t=20 s時(shí)多智能體系統(tǒng)的位置。圖6 6智能體三角形編隊(duì)隊(duì)形圖

圖7 6個(gè)智能體x軸方向位置差

例2考慮一個(gè)具有xi=(xi1,xi2)∈R2的多智能體系統(tǒng)，由8個(gè)節(jié)點(diǎn)的有向符號圖表示，如圖3所示。我們已知這個(gè)圖中有1個(gè)SBiSCC，選擇節(jié)點(diǎn)4作為領(lǐng)導(dǎo)者，其余節(jié)點(diǎn)作為跟隨者。圖3的拉普拉斯矩陣為

假設(shè)所有智能體的初始位置都是隨機(jī)選擇的，分散的外部控制輸入可以為r4=-(x4-d4)。多智能體的目標(biāo)是獲得一個(gè)具有矩形形狀的編隊(duì)隊(duì)形，其中期望位置矢量被定義為

圖8 6個(gè)智能體y軸方向位置差

注：星號和菱形分別表示t=0 s和t=40 s時(shí)多智能體系統(tǒng)的位置。圖9 8智能體矩形編隊(duì)隊(duì)形圖

圖10 8個(gè)智能體x軸方向位置差Fig.10 Position difference in x-axis direction of eight agents

圖11 8個(gè)智能體y軸方向位置差

5 結(jié)論

本文基于牧羊犬與羊群的自然現(xiàn)象研究了多智能體系統(tǒng)新的編隊(duì)控制問題。基于有向符號圖，針對每個(gè)智能體提出了一種分布式編隊(duì)控制算法，實(shí)現(xiàn)了多智能體系統(tǒng)的合作—競爭編隊(duì)運(yùn)動(dòng)。利用結(jié)構(gòu)平衡的獨(dú)立強(qiáng)連通分量推導(dǎo)出了一個(gè)充分條件，以確保所有智能體以分布方式進(jìn)行合作—競爭編隊(duì)運(yùn)動(dòng)，達(dá)到期望的編隊(duì)隊(duì)形。最后，通過數(shù)值仿真驗(yàn)證了理論結(jié)果的有效性。