InSCC拓撲結構的能控性分析

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

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

0 引言

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

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

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

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

1 預備知識

圖論知識:一個由n個節點構成的有向拓撲圖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。本文不考慮存在自環的情況,即不存在(vi,vi)∈E。Ni={j∈V∣(j,i)∈E}表示節點i的鄰居集合。如果在每一對不同的頂點i,j之間都有一條從i開始到j結束的定向路徑,那么圖G就是一個強連通圖。對于一個集合U,|U|代表集合中元素的個數,對于有向圖G,di=|Ni|表示節點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′為單向強連通環圖,且對于任意j∈V/V′,i∈V′,都有(i,j)?E,強連通子圖G′整體只有單個輸入,這種結構稱為InSCC。含有節點數目不同的InSCC結構稱為不同的InSCC。在本文中把沒有入度的節點作為初始節點,即節點1為初始節點,如圖1 所示。

圖1 InSCC結構

2 含有不同InSCC結構的多智能體系統的能控性分析

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

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

本節討論含有不同InSCC結構的多智能體系統的能控性,如圖2所示。

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

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

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

(2)

(3)

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

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

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

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

2.3 含有InSCC和路圖的多智能體系統能控性分析

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

圖4 含有InSCC和單條路的多智能體系統

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 一類能控圖的構造

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

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

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

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

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

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

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

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

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

(4)

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

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

引理3[21]當且僅當rank(Qs(-Li,Bi))=n時,多智能體系統(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結構在切換拓撲下的系統(4)是能控的。

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

本文命題1證明在固定拓撲下含有InSCC結構的多智能體系統,當選擇初始節點為領導者時,多智能體系統是能控的。因此在Gk={V,Ek,Ak}中,當選擇初始節點為領導者時,子網絡均是能控的。在矩陣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所示的有向拓撲中,節點2、3和節點4、5、6、7,以及節點8、9、10、11、12、13分別組成了3個不同的InSCC結構,選擇在不同的InSCC結構之間增加單向邊,如圖5所示,增加的通訊邊已用紅色作為區分,在節點2和節點4、節點3和節點7、節點5和節點13、節點6和節點11之間分別加一條正單向邊。下面將用具體實例來驗證本文的結論,當選擇初始節點1為領導者時

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

7 結論

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