基于領導者對稱的多智能體系統可控性研究

仉 偉，紀志堅，渠繼軍

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

0 引言

本文的工作主要包括兩部分：首先，基于對非平凡等價劃分的不可控情形的研究，考慮了自同構結構對系統可控性產生的影響，本文在命題1中給出了系統存在自同構的判定條件，然后討論了單領導者系統和多領導者系統的可控性。其次，通過理解領導者對稱，將具有對稱性的單領導者系統利用置換矩陣推廣到多領導者對稱，與文獻[19,23]所做的有所不同，本文研究的不僅僅是具有對稱性的單領導者系統，而是更為一般的系統，并在定理2給出了多領導者對稱的判定條件，同時指出領導者對稱與系統可控性的關系，從而為系統可控性研究提供了新的視角。

1 預備知識

1.1 圖論

首先，介紹圖論的一些基本內容，在多智能體網絡系統中，圖中的節點表示智能體，邊表示智能體之間的相互連接，具有相同邊的節點相互交流。無向圖G表示為G=(V,E)，由頂點集V(G)和邊集E(G)?V×V組成。其中V={1,2,…,n}，E={(i,j)|i,j∈V(G)}，n表示圖中節點的個數。沒有環結構及多重邊結構的圖稱為簡單圖，本文研究的都為簡單圖。頂點i的相鄰點集合為N(i)={j∈V(G)|(i,j)∈E(G)}。如果圖G中任意兩個不同的頂點i,j間都存在一條道路，則稱圖G是連通的。外部控制輸入信號施加在輸入節點上，輸入節點集合為S={i1,i2,…,iq}，并且滿足i1

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

(1)

其中，wij表示邊的權重，論文中沒有特殊說明的權重皆設為1，鄰接矩陣都為對稱矩陣。度矩陣D(G)=(dij)n×n，dij定義為

(2)

圖G的對角矩陣D的對角線元素等于圖G的鄰接矩陣相對應行的所有元素相加之和，也可表示為D(G)=diag(d1,…,dn)，dn為與頂點相連接的邊的總個數。

拉普拉斯矩陣L(G)∈Rn×n為表示圖中頂點之間關系的另一種矩陣，L(G)=(lij)n×n，lij定義為

(3)

下面介紹劃分，等價劃分和松弛等價劃分。

定義2如果對于任意的s,t∈Ci，有

(4)

定義3無向圖G的頂點集V(G)的一個劃分π的特征矩陣為這樣的矩陣Pπ∈Rn×r，當頂點i∈Cj時，pπ(ij)=1，否則pπ(ij)=0。

1.2 系統模型

對含有n個智能體的一階積分器線性系統，其連續時間動力學模型可以表示為

(5)

其中，xi(t)∈Rn為第i個節點在時間t的狀態，ui為第i個節點的外部控制輸入i∈{1,2,…,n}，式(5)即為系統的一致性協議。在無加權的多智能體網絡系統中，控制輸入協議描述為

(6)

在控制輸入協議(6)下，系統(5)可寫成具有n個節點的整合形式

(7)

若用集合Ic={i1,…,im}?{1,…,n}表示控制節點集。加入外部輸入控制后，系統(7)可轉化為以下動態系統

(8)

2 自同構及系統可控性分析

2.1 自同構及其判定條件

定義4設ψ為圖G=(V,E)上的置換，若存在任意節點i,j∈V和(i,j)∈E，ψ將節點i映射為ψ(i)，節點j映射為ψ(j)，當且僅當(ψ(i),ψ(j))∈E，則稱ψ為圖G的自同構映射，簡稱自同構(AUT)。

其中，節點i,j和(ψ(i),ψ(j))有相同的鄰居關系，即置換ψ保持各節點之間的鄰接關系不變。若i≠ψ(i)，則稱i,ψ(i)為自同構節點。G的所有自同構映射構成G的自同構群記為T。

定義5設A(G)是圖G的鄰接矩陣，ψ為G的頂點集合V(G)上的一個置換，則ψ是圖G的一個自同構，當且僅當AP=PA(等效地LP=PL)，則稱P為ψ的置換矩陣。顯然地，P為非單位矩陣。P表示為

(9)

每一組自同構節點i,ψ(i)可以劃分到同一個胞腔內，進而誘導圖的等價劃分。已知自同構可以誘導等價劃分，則從上述定義可知，等價劃分是松弛等價劃分的一種情況，而自同構誘導的劃分是等價劃分的一種情況，所以我們就可以利用自同構誘導的等價劃分來分析系統的可控性。松弛等價劃分、等價劃分和自同構誘導的劃分之間的關系如圖1所示。

定義6對于有連接的非平凡胞腔b|Ci|=k|Cj|，其中b是Cj中每個節點的鄰居數，k是Ci中每個節點的鄰居數。如果b=|Cj|，k=|Ci|，則稱非平凡胞腔Ci和Cj的連接為完全連接，否則稱為不完全連接。

圖1 AEP、EP和AUT之間的關系Fig.1 The relationship among AEP, EP and AUT

系統結構存在自同構，進而誘導等價劃分時，得到以下幾點。

1)對于非平凡胞腔，若系統為完全連接，其通信路徑是相同的；若系統為不完全連接，則通信路徑是相似的。

2)如果改變非平凡胞腔內節點的順序，拉普拉斯矩陣L行和列均不變。

3)設系統的拓撲結構在等價劃分后存在非平凡胞腔，系統存在自同構，該系統的拓撲結構一定是具有對稱性和循環性的。循環性即按順序將節點位置依次改變，不考慮標號，邊的位置不變。

引理1[22]設G=(V,E)的拉普拉斯矩陣為L，令π={C1,C2,…,Ck}是V的劃分，并且令Pπ是π的特征矩陣。若π是G的松弛等價劃分，則存在k×k階矩陣Q，使得

LPπ=PπQ

(10)

命題1設圖G的拉普拉斯矩陣為L，令P為置換矩陣，當且僅當滿足PTLP=L時，存在非平凡胞腔，使得系統的拓撲結構存在自同構。

注1置換矩陣為每一行和每一列都只有一個元素為1，其余的元素為0。當一個矩陣乘上一個置換矩陣時，得到的新矩陣是原來矩陣的行或列經過置換后得到的。置換矩陣也被定義為單位矩陣的某些行或列交換后得到的矩陣。

證明：設圖G的拉普拉斯矩陣為L，令π是G的松弛等價劃分。以下是對定理1的充分性和必要性的證明。

(充分性)假設可以找出一個非單位矩陣P，使得PTLP=L，此時非單位矩陣P在改變該系統的拉普拉斯矩陣L的行和列后，系統的拉普拉斯矩陣L不變，邊的位置不變，連接情況沒變。則P一定為置換矩陣，G的頂點集合V(G)上存在置換，該系統的拓撲結構一定存在自同構。

例1圖2驗證自同構代數等式條件PTLP=L，圖2a，2b為自同構。

圖2 七節點無向圖Fig.2 Seven-node undirected graph

圖2b為圖2a圖的自同構，經計算得出A1=A2,D1=D2,L1=L2。圖2a到圖2b僅僅是節點2與節點3交換位置，即標號位置發生改變，整體的拓撲結構未發生變化，邊的連接情況也沒發生變化，則可以找到一個P

使得PTL1P=L2，即L1=L2。則可知圖2a所示的系統滿足自同構的代數等式條件，該系統的拓撲結構存在自同構，圖2b為圖2a圖自同構的一種情況，節點2與節點3為自同構節點，顯然地，節點4與節點6也為自同構節點。從圖2上的這兩種自同構可以看出節點2與節點3有對稱關系，節點4與節點6也有對稱關系，由此可以引出以下領導者對稱的定義。

2.2 可控性分析

定義7若系統中只有一個領導者l1，存在n×n階置換矩陣P，使得P(-Lf)=(-Lf)P，則稱系統關于l1對稱，即為單領導者對稱系統。

其中，Lf為選取一個節點作為領導者后跟隨者系統的拉普拉斯矩陣，P(-Lf)=(-Lf)P，PT(-Lf)P=(-Lf)，跟隨者系統中存在自同構，即跟隨者系統是對稱的，系統為單領導者對稱系統。

若圖G的自同構ψ滿足ψ(i)=i，將所有節點i的自同構節點ψ(i)構成的子群記為Ti。保持每個節點不變的置換稱為自同構群的單位元。Ti中元素既保持每個節點間的鄰接關系不變，又固定節點i不動，記Ti>1表示Ti中含有非單位元，下面將對稱性推廣到多領導者系統。在圖G的自同構群T中，所有跟隨者中Ti的集合記為Tf。用Tf>1表示Tf中含有非單位元，對于多領導者對稱系統，定義如下。

定義8設系統中有N個領導l1,l2,…,lN，若Tf>1，則稱系統關于l1,l2,…,lN對稱，即為多領導者對稱系統。

定理1當且僅當l1,l2,…,lN的跟隨者子圖中自同構群Tf>1，系統關于領導者l1,l2,…,lN對稱。

證明：設系統中有n個跟隨者和N個領導者l1,l2,…,lN，對所有跟隨者從1到n進行標記，領導者的標號為n+1,n+2,…,n+N。根據跟隨者與領導者的劃分，將圖G的鄰接矩陣和拉普拉斯矩陣寫成如下的分塊矩陣。

其中，Af為所有跟隨者構成的子圖Gf的鄰接矩陣。δn+1,…,δn+N為n維列向量，領導者與跟隨者之間的鄰接情況表示為

(充分性)設系統關于領導者l1,l2,…,lN對稱，則存在n×n階的置換矩陣Pf使得Pf(-Lf)=(-Lf)Pf，即PfAf=AfPf。

注2在圖G中選擇l1,l2,…,lN為領導者，若系統為多領導者對稱的系統，此時跟隨者系統一定至少存在一個自同構Ti，即系統存在自同構，則可利用跟隨者系統中的自同構結構來研究系統可控性。

圖3 六節點無向圖Fig.3 Six-node undirected graph

例2在圖3所示的拓撲結構中，選取不同的領導者來說明單領導者對稱與多領導者對稱。

在圖3所示拓撲結構中，ψ(2)=3，ψ(3)=2，ψ(4)=5，ψ(5)=4，系統存在自同構。選取節點1作為領導者，自同構誘導的劃分為πl1={{1},{2,3},{4,5},{6}}。此時存在6×6階非單位置換矩陣P，使得Pf(-Lf)=(-Lf)Pf，則系統是關于l1對稱的系統。同理，分別選取節點2，3，4，5，6作為領導者，系統都是關于所選領導者對稱的系統，即為單領導者對稱系統，共有6種選取方式。選取節點1，2作為領導者，自同構誘導的劃分為πl1,l2={{1,2},{3},{4,5},{6}}，此時T3=1,T4=2>1,T5=2,T6=1，系統關于l1,l2對稱。選取節點1，2，3作為領導者，自同構誘導的劃分為πl1,l2,l3={{1,2,3},{4,5},{6}}，此時T4=2>1,T5=2>1,T6=1，系統關于l1,l2,l3對稱。選取節點1，2，3，6作為領導者，自同構誘導的劃分為πl1,l2,l3,l6={{1,2,3,6},{4,5}}，此時T4=2>1,T5=2>1，系統關于l1,l2,l3,l6對稱。共有21種選取領導者方式使系統為多領導者系統。若選取節點1，2，4作為領導者，自同構誘導的劃分為πl1,l2,l4={{1,2,4},{3},{5},{6}}，此時T3=1,T5=1,T6=1，系統不是領導者對稱系統。

下面利用等價劃分來分析系統存在領導者對稱與可控性之間的關系，對于具有領導者-跟隨者結構的系統，設系統中共有N個領導者l1,l2,…,lN和n個跟隨者，所有跟隨者及跟隨者之間形成的連接關系圖記為Gf，πf為Gf的等價劃分。

定義9若N個領導者各自獨占一個胞腔Cr+1={l1},Cr+2={l2},…,Cr+N={lN}。令πl1,l2,…,lN=πf∪Cr+1∪Cr+2∪…∪Cr+N，則πl1,l2,…,lN稱為圖G的多領導者的等價劃分。

引理2[20]若系統的拓撲結構圖G存在非平凡的松弛等價劃分，則系統不可控。

注3由等價劃分與松弛等價劃分的定義可知，等價劃分是松弛等價劃分的一種情況，若系統的拓撲結構圖G存在非平凡的等價劃分πl1,l2,…,lN，則系統不可控。

定理2若自同構誘導的劃分為非平凡的等價劃分πl1,l2,…,lN，系統為領導者對稱系統，跟隨者系統存在非平凡胞腔，則系統不可控。

證明：系統的拓撲結構圖G存在自同構誘導的非平凡等價劃分πl1,l2,…,lN，設劃分含有m+N個胞腔，若|Ci|=θi，即胞腔Ci中含有θi個節點，對Ci中的點用θi個連續數字進行標記，考慮N個領導者的情況。

設l1與s個胞腔Co1,Co2,…,Cos相鄰接，l2與t個胞腔Cp1,Cp2,…,Cpt相鄰接，…，lN與k個胞腔Cq1,Cq2,…,Cqk相鄰接，按圖G的劃分形式對矩陣A和B進行相應分塊。

其中，Ai,j為θi×θj階矩陣，

由鄰接矩陣A定義可知，Ai,j的每行元素之和相等。已知跟隨者系統存在自同構，那么至少存在兩個自同構節點，使可控性判別矩陣C中同一胞腔中的點對應的行向量相等，故rank(C)≤m。又因為πl1,l2,…,lN是非平凡的劃分，可知rank(C)

注4系統在選取領導者后系統仍存在自同構，自同構誘導的劃分為非平凡的等價劃分πf，此時系統不可控，領導者無法將存在自同構的非平凡胞腔里的跟隨者區別開來，從而無法將它們實現單獨控制，這便導致了系統的不可控性。

圖4 自同構誘導頂點集合V(G)的等價劃分Fig.4 Automorphism induces the equivalent partion of vertex set V(G)

例3如圖4所示，自同構群T=AUT(G)由轉置ψ1={1,2},ψ2={5,6,7}生成，則自同構誘導頂點集合的等價劃分為π={C1,C2,C3,C4}，其胞腔為C1={1,2},C2={3},C3={4},C4={5,6,7}。施加固定的外部控制輸入，控制輸入矩陣為B=[ei1,…,eim]。此時選取不同的領導者，來分析系統存在自同構誘導的等價劃分時，系統不可控的情況。

1)選取一個節點作為領導者時，系統為單領導者系統。選胞腔C1中的節點1作為領導者施加固定的控制輸入時，T5=3>1,T6=3>1,T7=3>1，系統為單領導者對稱系統，胞腔C4中節點5，6，7，收到的控制輸入是完全一致的，胞腔內不能實現對某個節點的單獨控制，該系統不可控。同理，節點2，3，4，5，6，7作為領導者，系統也不可控，僅考慮單領導者系統有7種選擇是不可控的。

2)選取多個節點作為領導者時，系統為多領導者系統。選取胞腔C1中的節點1，胞腔C4中的節點5作為兩個領導者加控制輸入，此時T6=2>1,T7=2>1，系統為多領導者對稱系統，胞腔C4存在自同構，系統不可控。同理，選取胞腔C1中的節點1，2，胞腔C4中的節點5作為三個領導者加控制輸入，此時T6=2>1,T7=2>1，系統也為多領導者對稱系統，胞腔C4存在自同構，系統不可控。對于多領導者系統，共有72種選擇使系統不可控。

綜上所述，例3假設系統的輸入固定，那么個體間形成的信息交換圖存在自同構時，選取了不同領導者分析可控性，總共有126種領導者選取方式。選取平凡胞腔作為領導者施加控制輸入，系統不可控。選取存在自同構的非平凡胞腔作為領導者施加不同的輸入時，若跟隨者系統中的胞腔仍然有非平凡的，則不論跟隨者之間的連接情況如何，系統總是不可控的，共有79種不可控選擇。

3 總結

本文利用圖論知識作為工具，研究了自同構誘導的等價劃分以及領導者選擇對可控性產生的影響。首先，命題1中給出了自同構的判定條件，即給出了基于圖論來判斷存在自同構的系統可控性的方法。其次，將單領導者對稱系統的概念推廣到多領導者對稱系統，并在定理1中給出了判定條件。最后，利用等價劃分研究了一類由于系統存在自同構造成的不可控系統，同時也研究了跟隨者系統中存在自同構造成的不可控系統。本文可以看出，多智能體可控性與拓撲結構有著密不可分的關系，多智能體可控性可以看作等價于拓撲結構圖的可控性。因此，利用圖論工具來研究可控性具有重要的理論和現實意義，作為未來的研究方向，我們要研究多智能體網絡可控性的充要條件。