InSCC拓撲結(jié)構(gòu)的能控性分析

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

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

0 引言

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

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

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

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

1 預(yù)備知識

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

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

(1)

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

定義1對于一個加權(quán)有向圖G(V,E,A),當(dāng)且僅當(dāng)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′整體只有單個輸入,這種結(jié)構(gòu)稱為InSCC。含有節(jié)點數(shù)目不同的InSCC結(jié)構(gòu)稱為不同的InSCC。在本文中把沒有入度的節(jié)點作為初始節(jié)點,即節(jié)點1為初始節(jié)點,如圖1 所示。

圖1 InSCC結(jié)構(gòu)

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

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

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

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

圖2 僅含有InSCC結(jié)構(gòu)的有向拓撲

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

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

(2)

(3)

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

圖3 與僅含有InSCC的有向拓撲所對應(yīng)的無向拓撲

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

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

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

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

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

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

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

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

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

3 含有不同InSCC結(jié)構(gòu)的拓撲加邊后的能控性分析

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

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

在不同InSCC結(jié)構(gòu)之間加單向邊,如圖5所示。

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

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

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

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

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

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

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

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

證明:在不同InSCC結(jié)構(gòu)之間加正單向邊的同時在路圖上增加逆向邊,對應(yīng)的拉普拉斯矩陣L3為

4 一類能控圖的構(gòu)造

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

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

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

圖7 構(gòu)造的含有InSCC結(jié)構(gòu)和路圖的能控拓撲

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

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

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

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

5 含有InSCC結(jié)構(gòu)的多智能體系統(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ù)輸入函數(shù)u(t),t∈[t0,tT],可以使系統(tǒng)從x(t0)=x0驅(qū)動到x(tT)=xf,此時系統(tǒng)(4)是能控的。

引理3[21]當(dāng)且僅當(dāng)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結(jié)構(gòu)在切換拓撲下的系統(tǒng)(4)是能控的。

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

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

(8)

矩陣(8)仍然有n個線性無關(guā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 數(shù)值驗證

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

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

7 結(jié)論

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