基于MAS的合作—競爭編隊研究

王 瀟，紀志堅

(青島大學自動化學院，山東 青島 266071)

0 引言

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

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

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

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

1 預備知識

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

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

(1)

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

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

(2)

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

L=Δ-A

(3)

如圖1所示，每個圓圈中的數字表示節點集N={1,2,…,12}中的節點。為了簡潔起見，省略了拓撲圖的權重。圖中有3個獨立強連通分量，由節點集{1}、{2}和{5,6}誘導組成。有向圖中的極大強連通子圖稱作為有向圖的強連通分量(SCC)，一個圖的極大強連通子圖加入任何一個不在它點集中的點都會導致它不再強連通，值得

圖1 12節點拓撲圖

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

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

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

如果圖G是強連通的，則：

1)每個蓋爾圓通過λ，

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

2 MAS編隊控制協議

如何實現多智能體系統的合作—競爭編隊運動，具有重要的理論和現實意義，但同時也是當前我們面臨的一大挑戰。本文試圖對這一復雜問題進行研究。為了便于描述，我們在這里研究了6個和8個多智能體系統的合作—競爭編隊運動。

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

(4)

其中xi∈Rn代表多智能體的狀態，ui稱為控制協議。設Vl={i1,…,im}是有外部控制輸入的領導者集合，Vf代表剩余的多智能體集合，即跟隨者集合。每個智能體i的動力學為

(5)

其中ri是多智能體系統的外部控制輸入。

圖2 6智能體合作—競爭交互網絡

圖3 8智能體合作—競爭交互網絡

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

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

(6)

我們認為合作—競爭編隊形成。

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

(7)

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

(8)

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

ri=-Ki(xi-di)

(9)

因此，多智能體i的動力學可修改為

(10)

(11)

(12)

3 MAS編隊穩定性

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

虛線代表負加權邊。圖4 兩個結構平衡的有向圖

虛線代表負加權邊。圖5 兩個結構不平衡的有向圖

一個有向圖G中的極大強連通子圖稱為有向圖的獨立強連通分量(iSCC)。如果iSCC是結構平衡的，則有符號圖G的獨立強連通分量被稱為結構平衡的獨立強連通分量(SBiSCC)。否則，iSCC被稱為結構不平衡的獨立強連通分量(SUiSCC)。

定理1假設有向符號圖G是弱連通的，圖G包含c個不同的結構平衡的獨立強連通分量，則結構平衡的獨立強連通分量的拓撲圖Gs=(Vs,Es),s∈Nc。當且僅當Vl∩Vs≠φ，由動力學(5)和控制協議(7)控制的多智能體系統是穩定的，即多智能體系統中的所有智能體的狀態滿足式(6)，可以形成期望的合作—競爭編隊運動。此外，接收外部控制輸入的最小節點數等于結構平衡的獨立強連通分量的數目。

證明：注意有符號圖的穩定性問題不同于無符號圖的穩定性問題。由于有符號圖G包含c個不同的結構平衡的獨立強連通分量，在不喪失一般性的情況下，假設(11)的L和D是

4 數值仿真

例1考慮一個具有xi:=(xi1,xi2)∈R2的多智能體系統，由6個節點的有符號有向圖表示，如圖2所示。我們已經知道這個圖中有2個結構平衡的獨立強連通分量，將節點1和節點6被選擇為領導者，其余節點為跟隨者。圖2的拉普拉斯矩陣為

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

雖然多智能體的初始位置是隨機選擇的，但多智能體可以實現三角形的編隊隊形，如圖6所示。

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

圖7 6個智能體x軸方向位置差

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

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

圖8 6個智能體y軸方向位置差

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

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

圖11 8個智能體y軸方向位置差

5 結論

本文基于牧羊犬與羊群的自然現象研究了多智能體系統新的編隊控制問題。基于有向符號圖，針對每個智能體提出了一種分布式編隊控制算法，實現了多智能體系統的合作—競爭編隊運動。利用結構平衡的獨立強連通分量推導出了一個充分條件，以確保所有智能體以分布方式進行合作—競爭編隊運動，達到期望的編隊隊形。最后，通過數值仿真驗證了理論結果的有效性。