肖朋朋,紀志堅,劉允剛,林 崇

(1.青島大學自動化學院,山東 青島 266071;2.山東省工業(yè)控制重點實驗室,山東 青島 266071;3.山東大學控制科學與工程學院,濟南 250061 )

0 引言

隨著計算機技術的發(fā)展,以分布式網絡化系統(tǒng)為代表的新型系統(tǒng)模式,在實際應用中充分體現了相對于單個系統(tǒng)更加方便和智能的優(yōu)勢,多智能體系統(tǒng)越來越受到人們的關注。不僅在控制領域,在無人機編隊等領域[1-5]也對多智能體系統(tǒng)進行了研究。

眾所周知,要實現對一個系統(tǒng)的控制,前提是保證系統(tǒng)的能控性。能控性概念是20世紀60年代由卡爾曼[6-7]首次提出,2004年[8]能控性的概念被引入到多智能體的研究中,文章利用領導者-跟隨者框架定義了系統(tǒng)的能控性。近些年對多智能體系統(tǒng)能控性[9-11]和能觀性的研究逐漸增多,在She等[12]的文章中利用拓撲特征來研究有符號路圖和循環(huán)圖領導者的選擇,以確保領導者-跟隨者的能控性。在Guan等[13]的文章中研究了用有向加權符號圖表示有符號網絡的多智能體系統(tǒng)的能控性。Sun等[14]研究了一類符號多智能體網絡的能控性,在廣義等價劃分的基礎上,提出了能控子空間上界的圖論刻畫。在Tian等[15]的文章中研究了切換系統(tǒng)的等價劃分定義及應用。在Zhao等[16]的文章中研究了異構多智能體系統(tǒng)的能控性。在Liu等[17]的文章中研究了離散時間多智能體系統(tǒng)的能觀性問題。

對多智能體系統(tǒng)的研究大多是從代數和圖論角度出發(fā)的,其中從圖論角度得到的結論,在使用時僅依靠網絡結構就可以描述系統(tǒng)的能控性,這極大減少了計算量,在實際應用中具有重要意義。之前的工作揭示了對稱性、自同構和等價劃分等結構對能控性的影響,但這類結構并不能包含所有情況,還需要挖掘新的特殊結構,并分析其對能控性的影響。本文提出一種新的拓撲結構輸入強連通分量(InSCC),用于解決含有輸入強連通分量的一類多智能體系統(tǒng)的能控性問題。

本文的貢獻主要包含4個方面:1)提出了InSCC結構,利用PBH判據等工具,分析了含有InSCC結構的網絡拓撲的能控性,相應地給出了保證系統(tǒng)能控的領導者選擇方法;2)以InSCC結構為基礎,在不同的InSCC結構之間及路圖中增加通訊邊,證明了按本文提出的方式增加通訊邊并不改變多智能體系統(tǒng)的能控性,這為通過加邊的方式構造更為一般的能控圖提供了一種可嘗試的方法;3)依據InSCC結構的特性,提供了一類能控拓撲的構造方法;4)給出了含有InSCC結構的多智能體系統(tǒng)在切換拓撲下能控的充要條件。

1 預備知識

圖論知識:一個由n個節(jié)點構成的有向拓撲圖G(V,E,A),圖的點集用V={v1,v2,…,vn}表示,圖的邊集用E={(vi,vj)|vi,vj∈V,i≠j}表示,A=[aij]∈Rn×n表示加權鄰接矩陣,aij表示頂點j到頂點i的權重,若無特殊說明,aij=1。本文不考慮存在自環(huán)的情況,即不存在(vi,vi)∈E。Ni={j∈V∣(j,i)∈E}表示節(jié)點i的鄰居集合。如果在每一對不同的頂點i,j之間都有一條從i開始到j結束的定向路徑,那么圖G就是一個強連通圖。對于一個集合U,|U|代表集合中元素的個數,對于有向圖G,di=|Ni|表示節(jié)點i的度,有向圖G的度矩陣用D(G)=diag(d1,d2,…,dn)表示。拉普拉斯矩陣是相較于度矩陣的另一種表達圖中頂點關系的矩陣,拉普拉斯矩陣用L(G)=D(G)-A(G)表示。

數學符號:R表示實數集,Rn為n維實向量空間。X/Y表示屬于X但不屬于Y的集合,I為單位矩陣,0表示文中合適維度的零矩陣,φ表示空集。

(1)

其中,L∈Rn×n是拉普拉斯矩陣,B∈Rn是控制輸入矩陣。

定義1對于一個加權有向圖G(V,E,A),當且僅當G1=(V1,E1,A1)滿足1)V1?V,2)E1?E,3)A1是A的子矩陣時,稱G1是G的一個子圖。

定義2對于有向圖G的一個子圖G′,如果G′為單向強連通環(huán)圖,且對于任意j∈V/V′,i∈V′,都有(i,j)?E,強連通子圖G′整體只有單個輸入,這種結構稱為InSCC。含有節(jié)點數目不同的InSCC結構稱為不同的InSCC。在本文中把沒有入度的節(jié)點作為初始節(jié)點,即節(jié)點1為初始節(jié)點,如圖1 所示。

圖1 InSCC結構

2 含有不同InSCC結構的多智能體系統(tǒng)的能控性分析

在目前為止的所有文獻中,關于能控圖構造的文獻很少,大部分都是非能控圖,本節(jié)為構造能控圖提供了圖論基礎。分析只含有不同InSCC結構的多智能體系統(tǒng)的能控性,以及含有InSCC結構和路圖的多智能體系統(tǒng)的能控性,給出領導者的選擇方法以實現系統(tǒng)能控。對于一個有向拓撲圖G,如果含有相同InSCC結構,則存在對稱節(jié)點[18],此時網絡不能控,故不探究。本文著重分析含有不同InSCC結構的多智能體系統(tǒng)的能控性。

2.1 單領導者時僅含有InSCC的多智能體系統(tǒng)的能控性分析

本節(jié)討論含有不同InSCC結構的多智能體系統(tǒng)的能控性,如圖2所示。

圖2 僅含有InSCC結構的有向拓撲

命題1在含有不同InSCC的多智能體系統(tǒng)中,當選擇初始節(jié)點為領導者時,多智能體系統(tǒng)是能控的。

證明:不失一般性,假設多智能體系統(tǒng)含有m個InSCC結構,則系統(tǒng)的拉普拉斯矩陣為

(2)

(3)

為了進一步體現有向圖與無向圖的區(qū)別,考慮圖2所對應的無向圖(見圖3)。當選擇初始節(jié)點1為領導者時,經驗證得到無向圖的能控子空間維數為8,而有向圖的能控子空間維數為10,對于本文考慮的情況,有向圖的表現在一定程度上更為出色,這里面的區(qū)別是值得研究的。注意到,基于無向圖等價劃分[20]的定義,在圖3中存在2對自同構節(jié)點,因此選擇初始節(jié)點1為領導者時,能控子空間的維數就等于節(jié)點數n和等價劃分胞腔數之差。因此相較于無向圖,本文利用有向圖去構造能控圖是有優(yōu)勢的。

圖3 與僅含有InSCC的有向拓撲所對應的無向拓撲

2.2 多領導者時僅含有InSCC的多智能體系統(tǒng)的能控性分析

命題2在含有InSCC結構的多智能體系統(tǒng)中,選擇初始節(jié)點和第k個InSCC結構中的部分節(jié)點為領導者,且控制輸入矩陣為單列矩陣,第k(k=1,2,…,m)個InSCC結構中領導者數量嚴格小于其節(jié)點的數量時,多智能體系統(tǒng)是能控的。

2.3 含有InSCC和路圖的多智能體系統(tǒng)能控性分析

在本文2.1和2.2小節(jié)中,給出了領導者的選擇方法以實現系統(tǒng)能控。為了使結論更加一般化,在只含有InSCC結構的多智能體系統(tǒng)中引入路圖,將路圖的端節(jié)點與初始節(jié)點相連接,如圖4所示。

圖4 含有InSCC和單條路的多智能體系統(tǒng)

命題3在一個含有不同InSCC結構和單條路的多智能體系統(tǒng)中,選擇初始節(jié)點為領導者,那么它對應的多智能體系統(tǒng)是能控的。

證明:假設多智能體系統(tǒng)中共有n+t個節(jié)點,包含m個不同的InSCC和1條含有t個節(jié)點的路圖,系統(tǒng)的拉普拉斯矩陣L1為

當選擇初始節(jié)點為領導者時,輸入矩陣B1=[1,0,…,0]T,B1∈Rn+t,

所以,rank[λI-L1|B1]=n+t,由引理1可得選擇初始節(jié)點為領導者時,多智能體系統(tǒng)是能控的。

3 含有不同InSCC結構的拓撲加邊后的能控性分析

在第2節(jié)中討論了含有InSCC結構和路圖的一類拓撲的能控性問題,給出了領導者的選擇方法以實現系統(tǒng)能控。從中可以看出,除了共同接收初始節(jié)點的信息,InSCC結構之間沒有通訊,是一個比較理想的假設。實際上對于更一般的圖,不同InSCC結構之間往往存在耦合關系。本文首先在僅含有InSCC結構的拓撲圖中,InSCC結構之間加單向邊,其中每個InSCC結構中都有偶數個節(jié)點。其次,討論在InSCC結構之間加單向邊,同時在路圖中增加逆向邊,得到了不影響系統(tǒng)能控性的加邊方法。

3.1 含有InSCC結構的多智能體系統(tǒng)加邊后的能控性分析

在不同InSCC結構之間加單向邊,如圖5所示。

圖5 增加正單向邊后的拓撲

定義3對于只含有不同InSCC結構的多智能體系統(tǒng),把不同的InSCC結構看作不同的胞腔,不同胞腔之間僅內部節(jié)點數量存在差異,且不存在兩個相同的胞腔。兩個不同的胞腔Ci,Cj之間增加由Ci指向Cj的通訊邊,其中Ci中的節(jié)點數量小于Cj中的節(jié)點數量,增加的這種邊稱為正單向邊,反之為負單向邊,正單向邊和負單向邊構成的集合分別為P+,N-。

定理1在只含有不同InSCC的多智能體系統(tǒng)中,增加正單向邊后,當選擇初始節(jié)點為領導者時,多智能體系統(tǒng)是能控的,加邊前后兩種系統(tǒng)的能控性相同。

同理,增加負單向邊也不改變多智能體系統(tǒng)的能控性,這為構造更復雜的能控圖提供了加邊的方法。

3.2 含有InSCC結構和單條路圖的多智能體系統(tǒng)加邊后的能控性分析

在2.3小節(jié)中,分析了InSCC結構和路圖共同組成的拓撲結構的能控性,給出了領導者的選擇方法以實現系統(tǒng)能控。根據定理1的分析,在不同InSCC結構之間加單向邊不改變多智能體系統(tǒng)的能控性,同樣能夠實現單領導者能控。本節(jié)考慮在不同InSCC結構之間加單向邊,同時在路圖上增加逆向邊,路圖中增加的逆向邊是從節(jié)點vj指向節(jié)點vi,i,j∈{n+1,n+2,…,n+t}且j>i,如圖6所示。

圖6 InSCC增加正單向邊和路圖增加逆向邊的拓撲

定理2在只含有不同InSCC結構和路圖的拓撲中,在不同InSCC結構之間加正單向邊,同時在路圖上增加逆向邊,當選擇初始節(jié)點為領導者時,加通訊邊前后能控性相同。若含有InSCC結構和單條路圖加邊后的多智能體系統(tǒng)是能控的,則在領導者的選擇中必然有初始節(jié)點。

證明:在不同InSCC結構之間加正單向邊的同時在路圖上增加逆向邊,對應的拉普拉斯矩陣L3為

4 一類能控圖的構造

本節(jié)主要利用InSCC結構和有向路圖的特點,提供一類能控圖的構造方法。

本文對含有不同InSCC結構的多智能體系統(tǒng)的能控性做了分析,發(fā)現了InSCC結構和路圖所具有的特殊性質。在目前的眾多文獻中,很少有能控圖構造的結論。本文利用InSCC結構和路圖的特性來構造一類能控圖。

方法1:如圖7a所示的拓撲圖,在命題1的基礎上,加入一個含有t個節(jié)點的有向路圖,路圖的末端節(jié)點與初始節(jié)點相連接,當選擇端節(jié)點1為領導者時,多智能體系統(tǒng)是能控的。

圖7 構造的含有InSCC結構和路圖的能控拓撲

方法2:如圖7b所示的拓撲圖,利用不同InSCC結構的特性,在一條含有t個節(jié)點的路圖基礎上,從每個節(jié)點引出不同的InSCC結構所構成的復雜拓撲,當選擇端節(jié)點1為領導者時,系統(tǒng)是能控的。

方法3:如圖7c所示的拓撲圖,每個InSCC結構都由偶數個節(jié)點組成,在定理1的基礎上,加入一個含有t個節(jié)點的有向路圖,路圖的末端節(jié)點與初始節(jié)點相連,并且在有向路圖上增加逆向邊,當選擇端節(jié)點1為領導者時,多智能體系統(tǒng)是能控的。

方法4:如圖7d所示的拓撲圖,每個InSCC結構都由偶數個節(jié)點組成,利用不同InSCC結構加單向邊和有向路圖加逆向邊不改變能控性的特性。在一條含有t個節(jié)點的有向路圖上,從每個節(jié)點引出不同的InSCC結構所構成的復雜拓撲,同時不同的InSCC結構之間增加單向邊,有向路圖增加逆向邊。當選擇端節(jié)點1為領導者時,多智能體系統(tǒng)是能控的。

這些結論的證明可以參考本文前邊結論的推導。我們討論了固定拓撲下含有InSCC結構的多智能體系統(tǒng)的能控性,根據InSCC結構的特點,給出了幾種能控圖的構造方法。但在現實生活中,各種情況錯綜復雜,固定拓撲下的多智能體系統(tǒng)往往不能解決很多實際問題,多智能體系統(tǒng)可能是時變的。

5 含有InSCC結構的多智能體系統(tǒng)在切換拓撲下的能控性分析

(4)

其中,Lσ(t)∈Rn×n為Gσ(t)的拉普拉斯矩陣,系統(tǒng)(4)包含N個子系統(tǒng)(-Lk,Bk),k=1,2,…,N,σ(t)=i表示子系統(tǒng)(-Li,Bi)在t時刻被激活。

定義4如果對于任意初始狀態(tài)x0,任意終端狀態(tài)xf,存在切換信號σ(t)和分段連續(xù)輸入函數u(t),t∈[t0,tT],可以使系統(tǒng)從x(t0)=x0驅動到x(tT)=xf,此時系統(tǒng)(4)是能控的。

引理3[21]當且僅當rank(Qs(-Li,Bi))=n時,多智能體系統(tǒng)(4)是能控的,其中

(5)

在矩陣(5)中,從2N列到2N+1列之間加入塊列-L2B1,…,-LNB1,…,-LNBN,再從矩陣(5)的最后增加塊列(-L2)(-L1)n-2B1,…,(-LN)n-1B1,…,(-LN)n-1BN,得到如式(6)的矩陣

[B1,B2,…,BN,-L1B1+…+(-LN)B1,…,-L1BN+…+(-LN)BN,

-L2B1,-L3B1,…,-LNB1,…,-LNBN,…,(-L1)n-1B1+…+(-LN)n-1B1,…,

(-L1)n-1BN+…+(-LN)n-1BN,(-L2)(-L1)n-2B1,…,(-LN)n-1B1,…,(-LN)n-1BN]

(6)

[B1,B2,…,BN,-L1B1,…,-LNB1,…,-LNBN,…,

(-L1)n-1B1,…,(-LN)n-1B1,…,(-LN)n-1BN]

(7)

式(7)為行滿秩矩陣,通過引理3可以得到只含有InSCC結構在切換拓撲下的系統(tǒng)(4)是能控的。

(必要性)假設系統(tǒng)(4)是能控的,即能控性矩陣C行滿秩,其中

本文命題1證明在固定拓撲下含有InSCC結構的多智能體系統(tǒng),當選擇初始節(jié)點為領導者時,多智能體系統(tǒng)是能控的。因此在Gk={V,Ek,Ak}中,當選擇初始節(jié)點為領導者時,子網絡均是能控的。在矩陣C中去掉塊列-L2B1,…,-LNB1,…,-LNBN和(-L2)(-L1)n-2B1,…,(-LN)n-1B1,…,(-LN)n-1BN,得到

(8)

矩陣(8)仍然有n個線性無關的列向量,所以矩陣(8)是行滿秩的。由于列初等變換不改變矩陣的秩,因此我們用向量-L1B1加上-L2B1-…-LNB1,-L1BN加上-L2BN-…-LNBN,(-L1)n-1B1加上(-L2)(-L1)n-2B1+…+(-LN)n-1B1,(-L1)n-1BN加上(-L2)(-L1)n-2BN+…+(-LN)n-1BN,得到

[B1,B2,…,BN,-L1B1+…+(-LN)B1,…,-L1BN+…+(-LN)BN,…,

(-L1)n-1B1+…+(-LN)n-1B1,…,(-L1)n-1BN+…+(-LN)n-1BN]

(9)

6 數值驗證

例:在圖5所示的有向拓撲中,節(jié)點2、3和節(jié)點4、5、6、7,以及節(jié)點8、9、10、11、12、13分別組成了3個不同的InSCC結構,選擇在不同的InSCC結構之間增加單向邊,如圖5所示,增加的通訊邊已用紅色作為區(qū)分,在節(jié)點2和節(jié)點4、節(jié)點3和節(jié)點7、節(jié)點5和節(jié)點13、節(jié)點6和節(jié)點11之間分別加一條正單向邊。下面將用具體實例來驗證本文的結論,當選擇初始節(jié)點1為領導者時

根據引理1得rank[sI-L2|B2]=13,在一個含有InSCC結構的多智能體系統(tǒng)中,當選擇初始節(jié)點為領導者時,多智能體系統(tǒng)是能控的,加邊并不影響多智能體系統(tǒng)的能控性,這與定理1完全一致。

7 結論

本文對一類含有InSCC結構的多智能體系統(tǒng)的能控性進行了研究,結果表明:對于僅包含InSCC結構的多智能體系統(tǒng),選擇初始節(jié)點為領導者時系統(tǒng)是能控的;對于包含InSCC結構和路圖結構的多智能體系統(tǒng),也得到了相應的結論,給出了領導者的選擇方法以實現系統(tǒng)能控。受此啟發(fā),提出了不改變系統(tǒng)能控性的通訊邊增加規(guī)則及一類能控拓撲的構造方法。最后基于得到的結果,對切換拓撲條件下相關系統(tǒng)的能控性進行了討論,得到了含有InSCC結構的多智能體系統(tǒng)在切換拓撲下能控的充要條件。本文得到的結果為研究更為復雜的多智能體系統(tǒng)的能控性提供了一定的理論參考,未來工作中將進一步探索InSCC結構在尋找本質能控圖(在任意領導者選擇下均可控的網絡)方面的潛在作用。