基于領導者對稱的多智能體系統(tǒng)可控性研究

仉 偉，紀志堅，渠繼軍

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

0 引言

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

1 預備知識

1.1 圖論

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

圖G的鄰接矩陣A(G)∈Rn×n描述一個圖的節(jié)點之間信息交流，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為與頂點相連接的邊的總個數(shù)。

拉普拉斯矩陣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 系統(tǒng)模型

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

(5)

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

(6)

在控制輸入?yún)f(xié)議(6)下，系統(tǒng)(5)可寫成具有n個節(jié)點的整合形式

(7)

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

(8)

2 自同構及系統(tǒng)可控性分析

2.1 自同構及其判定條件

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

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

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

(9)

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

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

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

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

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

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

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

引理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時，存在非平凡胞腔，使得系統(tǒng)的拓撲結構存在自同構。

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

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

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

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

圖2 七節(jié)點無向圖Fig.2 Seven-node undirected graph

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

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

2.2 可控性分析

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

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

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

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

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

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

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

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

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

圖3 六節(jié)點無向圖Fig.3 Six-node undirected graph

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

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

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

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

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

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

定理2若自同構誘導的劃分為非平凡的等價劃分πl(wèi)1,l2,…,lN，系統(tǒng)為領導者對稱系統(tǒng)，跟隨者系統(tǒng)存在非平凡胞腔，則系統(tǒng)不可控。

證明：系統(tǒng)的拓撲結構圖G存在自同構誘導的非平凡等價劃分πl(wèi)1,l2,…,lN，設劃分含有m+N個胞腔，若|Ci|=θi，即胞腔Ci中含有θi個節(jié)點，對Ci中的點用θi個連續(xù)數(shù)字進行標記，考慮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的每行元素之和相等。已知跟隨者系統(tǒng)存在自同構，那么至少存在兩個自同構節(jié)點，使可控性判別矩陣C中同一胞腔中的點對應的行向量相等，故rank(C)≤m。又因為πl(wèi)1,l2,…,lN是非平凡的劃分，可知rank(C)

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

圖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]。此時選取不同的領導者，來分析系統(tǒng)存在自同構誘導的等價劃分時，系統(tǒng)不可控的情況。

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

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

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

3 總結

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