邊破壞對(duì)多智能體系統(tǒng)能控性的影響

肖朋朋，紀(jì)志堅(jiān)

（1.青島大學(xué) 自動(dòng)化學(xué)院，山東青島 266071；2.山東省工業(yè)控制重點(diǎn)實(shí)驗(yàn)室，山東青島 266071）

隨著社會(huì)的發(fā)展和科技的進(jìn)步，國內(nèi)外眾多學(xué)者對(duì)多智能體系統(tǒng)的研究逐步深入，網(wǎng)絡(luò)拓?fù)錇檠芯慷嘀悄荏w系統(tǒng)提供了一種分析工具。近年來，多智能體系統(tǒng)不僅在控制領(lǐng)域，在無人機(jī)編隊(duì)等領(lǐng)域[1-8]也進(jìn)行了深入研究。

能控性概念是上個(gè)世紀(jì)60 年代由卡爾曼首次提出，2004 年能控性的概念被引入到多智能體的研究當(dāng)中。近些年，多智能體系統(tǒng)研究取得了顯著的成就，如自適應(yīng)控制[9-11]、博弈控制[12-14]、切換系統(tǒng)[15]等都已應(yīng)用于多智能體系統(tǒng)中。一類邊集失效對(duì)復(fù)雜網(wǎng)絡(luò)能控性的影響已經(jīng)有過討論[16]，但不同類型的邊失效對(duì)多智能體系統(tǒng)能控性的影響，以及對(duì)拉普拉斯矩陣秩的影響，目前還沒有給出確切的結(jié)論。因此，為了解決此問題，將系統(tǒng)中的邊進(jìn)行分類，并從理論層面給出不同類型的邊失效對(duì)系統(tǒng)能控性影響的確切結(jié)論。文中提出了一種邊的分類方式，將多智能體系統(tǒng)中的邊分為三種類型，邊組合分為四種組合類型，并提供了一種辨識(shí)邊類型的算法，給出了不同類型的邊失效后系統(tǒng)能控性的變化規(guī)律。同時(shí)，為了保證邊失效后的系統(tǒng)是能控的，給出了領(lǐng)導(dǎo)者的選擇方法，最后通過實(shí)例驗(yàn)證了結(jié)論。

1 預(yù)備知識(shí)

1.1 圖論知識(shí)

對(duì)于含有N個(gè)節(jié)點(diǎn)的多智能體系統(tǒng)G(A)=(V,E,A)，其中V={v1,v2,…,vN} 表示系統(tǒng)的節(jié)點(diǎn)集，E={e1,e2,…,eN}表示系統(tǒng)的邊集，A=[aij]∈RN×N表示加權(quán)鄰接矩陣，aij表示節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的影響程度，若無特殊說明，aij=1。文中不考慮存在自環(huán)的情況，即(vi,vi)?E。Ni={j∈V∣(j,i)∈E}表示節(jié)點(diǎn)i的鄰居集合。在有向圖G中，對(duì)于不同的節(jié)點(diǎn)i、j，都有一條從i開始到j(luò)結(jié)束的定向路徑，則稱圖G為強(qiáng)連通圖。di=||Ni表示節(jié)點(diǎn)i的度，有向圖G的度矩陣為D(G)=diag(d1,d2,…,dN)。拉普拉斯矩陣(Laplacian matrix)是相較于度矩陣的另一種表達(dá)圖中頂點(diǎn)關(guān)系的矩陣，拉普拉斯矩陣可以用L(G)=D(G)-A(G)表示。

1.2 數(shù)學(xué)符號(hào)

R表示實(shí)數(shù)集，Rn表示n維實(shí)向量空間。XY表示屬于X但不屬于Y的集合，I為單位矩陣，O表示文中合適維度的零矩陣，?表示空集。

1.3 系統(tǒng)模型

其中，L∈RN×N為拉普拉斯矩陣，B∈RN×P為外部控制輸入矩陣。

對(duì)于線性時(shí)不變系統(tǒng)（1），若存在一個(gè)分段連續(xù)的輸入u(t)能夠在有限時(shí)間[t0,tf]內(nèi)使得系統(tǒng)從任意初始狀態(tài)轉(zhuǎn)移到任意終止?fàn)顟B(tài)，則稱此系統(tǒng)的狀態(tài)是完全能控的?？梢酝ㄟ^能控性判據(jù)來判斷系統(tǒng)是否是能控的，即系統(tǒng)完全能控的充分必要條件是矩陣C=[B,LB,…LN-1B] 滿秩，即rankC=N。此時(shí)，我們稱該系統(tǒng)是完全能控的。

定義1對(duì)于有向圖G的一個(gè)子圖G′，如果G′為單向強(qiáng)連通環(huán)圖，且對(duì)于任意j∈V/V′，i∈V′，都有(i,j)?E，強(qiáng)連通子圖G′整體只有單個(gè)輸入，這種結(jié)構(gòu)稱為InSCC。在文中將InSCC 結(jié)構(gòu)外且沒有入度的節(jié)點(diǎn)作為初始節(jié)點(diǎn)，即節(jié)點(diǎn)1 為初始節(jié)點(diǎn)，如圖1所示。

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

2 多智能體系統(tǒng)中邊的分類辨識(shí)

在含有InSCC 結(jié)構(gòu)的多智能體系統(tǒng)中，邊失效后，系統(tǒng)的能控性怎樣變化以及如何再次選擇領(lǐng)導(dǎo)者保證系統(tǒng)能控，都是十分有意義的問題。

2.1 多智能體系統(tǒng)中邊的分類

含有InSCC 結(jié)構(gòu)的多智能體系統(tǒng)通常由節(jié)點(diǎn)和有向邊組成，其中節(jié)點(diǎn)存在三種類型，邊也存在三種類型。

2.1.1 邊的分類

類型1：如圖2（a）所示，對(duì)于多智能體系統(tǒng)中的一條邊，如邊(v1→v2)，如果和初始節(jié)點(diǎn)相連，則這條邊為關(guān)鍵邊，記作xK。

圖2 節(jié)點(diǎn)和邊在網(wǎng)絡(luò)中的關(guān)系

類型2：如圖2（a）所示，對(duì)于多智能體系統(tǒng)中的一條邊，如邊(v2→v3)或(v3→v4)，如果一條邊由關(guān)鍵節(jié)點(diǎn)指向順承節(jié)點(diǎn)或者由順承節(jié)點(diǎn)指向順承節(jié)點(diǎn)，則這條邊為順承邊，記作xF。

類型3：如圖2(a)所示，對(duì)于系統(tǒng)中的一條邊，如邊(v6→v2)，如果一條邊由順承節(jié)點(diǎn)指向關(guān)鍵節(jié)點(diǎn)，則這條邊為冗余邊，記作xR。

2.1.2 節(jié)點(diǎn)分類

類型1：如圖2（b）所示，對(duì)于多智能體系統(tǒng)中的一個(gè)節(jié)點(diǎn)，獨(dú)立于InSCC 結(jié)構(gòu)外且沒有入度的節(jié)點(diǎn)作為初始節(jié)點(diǎn)，如節(jié)點(diǎn)1。

類型2：如圖2（b）所示，對(duì)于多智能體系統(tǒng)中的一個(gè)節(jié)點(diǎn)，和初始節(jié)點(diǎn)相連的邊指向的節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，如節(jié)點(diǎn)2。

類型3：如圖2（b）所示，對(duì)于多智能體系統(tǒng)中的一個(gè)節(jié)點(diǎn)，順承邊指向的節(jié)點(diǎn)為順承節(jié)點(diǎn)，如節(jié)點(diǎn)3、4、5 和6。

2.2 多智能體系統(tǒng)中邊組合失效類型

根據(jù)節(jié)點(diǎn)和邊的類型，對(duì)不同邊的組合進(jìn)行分類，每個(gè)組合有且僅有兩條邊。

類型1：關(guān)鍵邊和順承邊遭到破壞而失效，則失效組合為關(guān)鍵邊-順承邊組合，記xK-F。

類型2：關(guān)鍵邊和冗余邊遭到破壞而失效，則失效組合為關(guān)鍵邊-冗余邊組合，記xK-R。

類型3：順承邊和順承邊遭到破壞而失效，則失效組合為順承邊-順承邊組合，記xF-F。

類型4：順承邊和冗余邊遭到破壞而失效，則失效組合為順承邊-冗余邊組合，記xF-R。

2.3 邊組合的辨識(shí)算法

為了更好地探究邊失效對(duì)多智能體系統(tǒng)能控性的影響，需要找出多智能體系統(tǒng)中邊的類型，下面給出多智能體系統(tǒng)中邊的辨識(shí)算法，具體步驟如下：

Step1：遍歷多智能體系統(tǒng)中的所有節(jié)點(diǎn)，如果存在一條邊(vi→vj)，其中節(jié)點(diǎn)vi為初始節(jié)點(diǎn)，那么由節(jié)點(diǎn)vi指出的邊為關(guān)鍵邊。

Step2：遍歷多智能體系統(tǒng)中的所有節(jié)點(diǎn)，如果存在一條邊(vi→vj)，其中節(jié)點(diǎn)vi為關(guān)鍵節(jié)點(diǎn)或者為順承節(jié)點(diǎn)，節(jié)點(diǎn)vj為順承節(jié)點(diǎn)，那么由節(jié)點(diǎn)vi指向節(jié)點(diǎn)vj的邊為順承邊。

Step3：遍歷多智能體系統(tǒng)中的所有節(jié)點(diǎn)，如果存在一條邊(vi→vj)，其中節(jié)點(diǎn)vi為順承節(jié)點(diǎn)，節(jié)點(diǎn)vj為關(guān)鍵節(jié)點(diǎn)，那么由節(jié)點(diǎn)vi指向節(jié)點(diǎn)vj的邊為冗余邊。

Step4：搜尋第一條與初始節(jié)點(diǎn)相連接的邊為關(guān)鍵邊，如果第二條邊是從關(guān)鍵節(jié)點(diǎn)或順承節(jié)點(diǎn)vj出發(fā)，到順承節(jié)點(diǎn)vj+1結(jié)束，邊(vj→vj+1)為順承邊，則找出關(guān)鍵邊-順承邊組合xK-F，否則進(jìn)行下一步。

Step5：搜尋第一條與初始節(jié)點(diǎn)相連接的邊為關(guān)鍵邊，如果第二條邊是從順承節(jié)點(diǎn)vj出發(fā)，到關(guān)鍵節(jié)點(diǎn)vj+1結(jié)束，邊(vj→vj+1)為冗余邊，找出關(guān)鍵邊-冗余邊組合xK-R。

Step6：搜尋第一條邊從關(guān)鍵節(jié)點(diǎn)或順承節(jié)點(diǎn)vi出發(fā)，到順承節(jié)點(diǎn)vi+1結(jié)束，邊(vi→vi+1)為順承邊，如果第二條邊是從關(guān)鍵節(jié)點(diǎn)或順承節(jié)點(diǎn)vj出發(fā)，到順承節(jié)點(diǎn)vj+1結(jié)束，邊(vj→vj+1) 為順承邊，那么邊(vi→vi+1)與邊(vj→vj+1)的組合為順承邊-順承邊組合xF-F，否則進(jìn)行下一步。

Step7：搜尋第一條邊從關(guān)鍵節(jié)點(diǎn)或順承節(jié)點(diǎn)vi出發(fā)，到順承節(jié)點(diǎn)vi+1結(jié)束，邊(vi→vi+1)為順承邊，如果第二條邊是從順承節(jié)點(diǎn)vj出發(fā)，到關(guān)鍵節(jié)點(diǎn)vj+1結(jié)束，邊(vj→vj+1)為冗余邊，那么邊(vi→vi+1)與邊(vj→vj+1)的組合為順承邊-冗余邊組合xF-R。

3 邊失效對(duì)多智能體系統(tǒng)能控性影響

定理1 對(duì)于含有N個(gè)節(jié)點(diǎn)的多智能體系統(tǒng)，其中含有n個(gè)不同的InSCC 結(jié)構(gòu)。

1）當(dāng)失效n條關(guān)鍵邊時(shí)，多智能體系統(tǒng)的能控子空間維數(shù)降低。rank(LK)=N-n-1，LK為丟失關(guān)鍵邊后的拉普拉斯矩陣。保證丟失n條關(guān)鍵邊后的多智能體系統(tǒng)是能控的，需要選擇初始節(jié)點(diǎn)和n個(gè)關(guān)鍵節(jié)點(diǎn)為領(lǐng)導(dǎo)者。

2）當(dāng)失效n條順承邊時(shí)，多智能體系統(tǒng)的能控子空間維數(shù)降低。其中每個(gè)InSCC 結(jié)構(gòu)失去一條順承邊，rank(LF)=N-n-1，LF為丟失順承邊后的拉普拉斯矩陣。保證丟失n條順承邊后的多智能體系統(tǒng)是能控的，需要對(duì)初始節(jié)點(diǎn)和n個(gè)失效順承邊指向的順承節(jié)點(diǎn)施加外部控制輸入。

3）當(dāng)失效n條冗余邊時(shí)，多智能體系統(tǒng)的能控性保持不變，對(duì)應(yīng)的拉普拉斯矩陣LR的秩不變。當(dāng)選擇初始節(jié)點(diǎn)為領(lǐng)導(dǎo)者時(shí)，多智能體系統(tǒng)能控性保持不變。

證明：1）當(dāng)n條關(guān)鍵邊失效時(shí)，其所對(duì)應(yīng)的拉普拉斯矩陣為：

因?yàn)橄到y(tǒng)含有n個(gè)不同的InSCC，所以矩陣LKi的維數(shù)不相同。接下來計(jì)算在矩陣LK的特征值中零特征值的重?cái)?shù)：

其中，LK0=0，每個(gè)|λI-LKi|中存在一個(gè)特征值λ=0，所以在LK的特征值中，λ=0 的重?cái)?shù)為n+1，即rank(LK)=N-n-1。

當(dāng)選擇初始節(jié)點(diǎn)為領(lǐng)導(dǎo)者時(shí)，關(guān)鍵邊失效后的系統(tǒng)存在N-1 個(gè)輸入不可達(dá)節(jié)點(diǎn)，系統(tǒng)的能控子空間維數(shù)降低。根據(jù)InSCC 結(jié)構(gòu)的特性，當(dāng)多智能體系統(tǒng)中所有的節(jié)點(diǎn)輸入可達(dá)時(shí)，系統(tǒng)能控。保證丟失n條關(guān)鍵邊后的多智能體系統(tǒng)是能控的，選擇輸入矩陣B=[bK0,bK1,…,bKn]，其 中bK0=[1,0,…,0]T，bKi=[0,…,?,…,?]T，bKi∈RN×1，i∈{1,2,…,n} 。當(dāng)在關(guān)鍵節(jié)點(diǎn)施加外部控制時(shí)，?=1，否則?=0，此時(shí)丟失關(guān)鍵邊后的系統(tǒng)所有節(jié)點(diǎn)是輸入可達(dá)的，系統(tǒng)能控。

2）當(dāng)n條順承邊失效時(shí)，其中每個(gè)InSCC 結(jié)構(gòu)失去一條順承邊。根據(jù)拉普拉斯矩陣行和為零的性質(zhì)，拉普拉斯矩陣LF中出現(xiàn)n+1 個(gè)全零行，丟失n條順承邊后的拉普拉斯矩陣LF的秩減少n，因此有rank(LF)=N-n-1。保證丟失n條順承邊后的多智能體系統(tǒng)是能控的，則需要選擇輸入矩陣B=[bF0,bF1,…,bFn]，其中bF0=[1,0,…,0]T，bFi=[0,…,*,…,*]T，bFi∈RN×1，i∈{1,2,…,n} 。當(dāng)對(duì)失效順承邊指向的順承節(jié)點(diǎn)施加外部控制輸入時(shí)，*=1，否則*=0，此時(shí)系統(tǒng)能控。

3）當(dāng)n條冗余邊失效時(shí)，拉普拉斯矩陣LR中仍有N-1 線性無關(guān)的行向量，LR與冗余邊失效前的拉普拉斯矩陣具有相同的秩。當(dāng)選擇初始節(jié)點(diǎn)為領(lǐng)導(dǎo)者時(shí)，系統(tǒng)中不存在輸入不可達(dá)節(jié)點(diǎn)。因此，冗余邊丟失前后多智能體系統(tǒng)能控性保持不變。

定理2對(duì)于一個(gè)含有N個(gè)節(jié)點(diǎn)的多智能體系統(tǒng)，其中含有n個(gè)不同InSCC 結(jié)構(gòu)，InSCC 結(jié)構(gòu)中節(jié)點(diǎn)數(shù)k≥3 。當(dāng)丟失n組順承邊—順承邊組合(xF-F)時(shí)，每個(gè)InSCC 中丟失一組xF-F，多智能體系統(tǒng)的能控子空間維數(shù)降低。rank(LF-F)=N-2n-1，LF-F為丟失xF-F后的拉普拉斯矩陣。保證丟失n組xF-F后系統(tǒng)能控，則對(duì)初始節(jié)點(diǎn)和失效順承邊指向的順承節(jié)點(diǎn)施加外部控制輸入。

證明：對(duì)于只含有n個(gè)不同InSCC 的多智能體系統(tǒng)，InSCC 結(jié)構(gòu)中節(jié)點(diǎn)數(shù)k≥3。當(dāng)n組邊組合xF-F失效時(shí)，其中每個(gè)InSCC 結(jié)構(gòu)失去一組xF-F，根據(jù)拉普拉斯矩陣行和為零的性質(zhì)，拉普拉斯矩陣LF-F中出現(xiàn)2n+1 個(gè)全零行。在LF-F的特征值中，特征值λ=0 的重?cái)?shù)為2n+1，rank(LF-F)=N-2n-1。當(dāng)選擇初始節(jié)點(diǎn)為領(lǐng)導(dǎo)者時(shí)，邊組合xF-F失效后的多智能體系統(tǒng)存在輸入不可達(dá)節(jié)點(diǎn)，多智能體系統(tǒng)的能控子空間維數(shù)降低。保證丟失n條邊組合xF-F后的多智能體系統(tǒng)是能控的，則需要選擇輸入矩陣B=[bF0,bF1,…,bF2n]，其 中bF0=[1,0,…,0]T，bFi=[0,…,*,…,*]T，bFi∈RN×1，i∈{1,2,…,2n}。當(dāng)對(duì)失效順承邊指向的順承節(jié)點(diǎn)施加外部控制輸入時(shí)，*=1，否則*=0，此時(shí)系統(tǒng)能控。

4 實(shí)例驗(yàn)證

圖3（a）所示為只含有一個(gè)InSCC 的多智能體系統(tǒng)，系統(tǒng)的拉普拉斯矩陣為：

圖3 只含有一個(gè)InSCC的多智能體系統(tǒng)中不同類型邊失效

rank(L)=5。

1）當(dāng)丟失一條關(guān)鍵邊后，如圖3（b）所示，系統(tǒng)的拉普拉斯矩陣為：

rank(LK)=4，關(guān)鍵邊失效后系統(tǒng)的拉普拉斯矩陣的秩減少1。保證丟失關(guān)鍵邊后的系統(tǒng)是能控的，則需要選擇初始節(jié)點(diǎn)和關(guān)鍵節(jié)點(diǎn)為領(lǐng)導(dǎo)者，即選擇輸入矩陣BK，此時(shí)，根據(jù)系統(tǒng)能控性判據(jù)可知系統(tǒng)能控。

2）當(dāng)丟失一條順承邊后，如圖3（c）所示，系統(tǒng)的拉普拉斯矩陣為：

rank(LF)=4，順承邊失效后多智能體系統(tǒng)的拉普拉斯矩陣的秩減少1。保證丟失順承邊后的多智能體系統(tǒng)是能控的，則需要對(duì)初始節(jié)點(diǎn)和失效順承邊指向的那個(gè)順承節(jié)點(diǎn)施加外部控制輸入，即選擇輸入矩陣BF，此時(shí)，根據(jù)系統(tǒng)能控性判據(jù)可知系統(tǒng)能控。

3）當(dāng)丟失1 條冗余邊后，如圖3（d）所示，拉普拉斯矩陣LR為：

其中，存在五個(gè)線性無關(guān)的行向量，因此LR與冗余邊失效前的拉普拉斯矩陣L具有相同的秩。當(dāng)選擇初始節(jié)點(diǎn)為領(lǐng)導(dǎo)者時(shí)，系統(tǒng)中不存在輸入不可達(dá)節(jié)點(diǎn)，因此，冗余邊丟失前后多智能體系統(tǒng)能控性保持不變。

5 結(jié)論

文中研究了只含有InSCC 的多智能體系統(tǒng)在遭受攻擊或破壞后，不同類型的邊失效對(duì)網(wǎng)絡(luò)能控性的影響。當(dāng)關(guān)鍵邊和順承邊失效時(shí)，系統(tǒng)拉普拉斯矩陣的秩減少，多智能體系統(tǒng)的能控子空間維數(shù)降低；當(dāng)冗余邊失效時(shí)，系統(tǒng)拉普拉斯矩陣的秩不發(fā)生改變，多智能體系統(tǒng)的能控性保持不變；當(dāng)邊組合xF-F失效時(shí)，系統(tǒng)拉普拉斯矩陣的秩減少，多智能體系統(tǒng)的能控子空間維數(shù)降低。同時(shí)，為了保證不同類型邊以及邊組合失效后的多智能體系統(tǒng)是能控的，給出了領(lǐng)導(dǎo)者的選擇方法。