有向路徑下的一類多智能體系統的能控性分析

張志偉，紀志堅

(青島大學 a.自動化學院；b.山東省工業控制技術重點實驗室，山東 青島 266071)

0 引言

近些年，隨著計算機網絡技術、通信技術的日益發展，系統正逐漸從單一的傳統模式演化成智能化的新型模式。智能體系統的發展也是如此，由于單個智能體解決問題的能力十分有限，通過智能體之間的相互聯系，彼此協調可以解決超過單個智能體能力之外更復雜的問題，這也就形成了多智能體系統。多智能體系統具有諸多顯著優勢，目前已經在編隊控制[1-3]，能控性[4-7]，能觀性[8-10]，一致性[11-13]等方面得到了廣泛研究。

在當前世界背景下，普遍受到國內外學者關注的一個問題是系統的能控性問題，能控性是現代控制理論的一個基本概念，是對系統進行研究和分析的基礎。有關能控性的研究最早可以追溯到20世紀60年代，由Kalman提出[14-15]。之后學者研究發現將能控性的概念擴展到多智能體系統之中是非常有必要的。多智能體系統的能控性是指選定部分節點作為領導者(leader)施加外部控制輸入，通過系統內部個體之間的相互連接關系，可以使跟隨者(follower)由任意初始狀態轉移到所期望的狀態。多智能體系統能控性的這一概念首先是在2004年由Tanner提出，同時他還提出了一種基于leader-follower結構(領導者—跟隨者結構)的網絡模型[16]。在這一結構模型下，多智能體系統能控性的研究得到了進一步的發展。從代數角度出發，Ji等[17]在leader-follower結構下得到了系統能控的充分必要條件是Lf和L不共享特征值。Ji Z等[18]得到了一個基于特征值的系統能控的充分必要條件，即對應領導者位置的特征向量的元素不為0。從圖論刻畫的角度出發，文獻[17]首次提出了等價劃分的概念，此后文獻[19-21]利用等價劃分對不同拓撲條件下的多智能體系統的能控性進行了分析。除此之外，特殊拓撲的能控性研究也一直都是學者們關注的熱點。Rahmani等[22]通過對無向路圖的研究發現了研究特殊拓撲結構的能控性具有重要意義。Palangeli等[23]進行了進一步研究，得到了無向環圖拓撲下多智能體系統能控的相關結論。2018年Liu等[24]綜合研究了無向路圖和環圖下多智能體系統的能控性問題，提出了使系統能控時領導者位置的選取方式。文獻[25]基于無向路圖和環圖研究了無向符號條件下多智能體系統能控性保持問題。

可以看出，上面有關系統能控性的研究主要是在無向無符號拓撲下進行的，即個體之間的信息傳遞都是雙向的，且個體之間的聯系權重都為正值，而有向符號拓撲條件下多智能體系統能控性的研究成果相對較少。有向符號條件下系統Laplacian矩陣區別于無向無符號圖的地方主要是矩陣不再是實對稱矩陣，且矩陣的行和不再一定為零。基于以上兩點，許多無向無符號拓撲條件下的性質將不再適用，這也給研究有向符號拓撲條件下多智能體系統的能控性帶來了困難和挑戰。

本文的貢獻主要包含以下3個方面：1)基于有向符號拓撲條件下的leader-follower結構模型，研究發現該模型下增加或刪除網絡中特定的一類邊對于系統的能控性沒有影響。2)從特殊拓撲能控性的角度出發，得到了有向路徑拓撲下系統單領導者能控的領導者位置的選取方式。在此基礎上進一步發現在有向路徑中增加逆向邊不改變系統的能控性，而這一結果并不適用于增加順向邊的情況，有向路徑增加順向邊時系統的能控性取決于跟隨者節點中是否存在非平凡胞腔。3)基于上述有向拓撲中特定連接不改變系統能控性的特點以及使得特殊拓撲能控的領導者位置的選取方式，給出了一個有向符號條件下能控復雜拓撲的構造方式。

1 預備知識

將一個包含n個智能體的多智能體系統表示為G=(V,E,A)，其中，V={v1,…,vn}表示節點集，E?V×V表示邊集，A=(aij)∈Rn×n表示鄰接矩陣。有向邊(vi,vj)∈E表示存在一條從vi→vj的有向邊，個體之間的連接關系通過鄰接矩陣A∈Rn×n來表示，其中如果(vi,vj)∈E，那么aij≠0，否則aij=0。本文不考慮存在自環的情況。

可得

(1)

假定包含n個個體的節點集V可以分為一個領導者集Vl∈V和一個跟隨者集Vf∈V，且Vl∪Vf=V，因此便形成了一個經典的leader-follower結構下的網絡模型。不失一般性，假定前m個個體形成跟隨者集Vf={v1,…,vm}，其它個體形成領導者集Vl={vm+1,…,vn}。則上述的Laplacian矩陣可以劃分為

(2)

其中，Lf∈Rm×m，Lfl∈Rm×(n-m),Llf∈R(n-m)×m,Ll∈R(n-m)×(n-m)。基于式(1)和(2)，可得

對于跟隨者來說

(3)

在leader-follower結構中，領導者通過直接接收外部控制信號受到外部信號的控制，又因為領導者是一階積分器系統，因此領導者是必可控的。

定義1 leader-follower結構下系統能控性假定領導者接受外部控制信號后是必能控的，leader-follower結構下系統能控的含義是系統中跟隨者的狀態xf(t)可以從任意初始狀態到達期望的狀態。

定義2m-領導者能控當使得多智能體系統能控時所選定的領導者的最小數量為m時，稱系統是m-領導者能控。特別地，當m=1時，若多智能體系統是能控的，此時稱系統是單領導者能控。

在leader-follower結構下，為判斷系統的能控性，給出如下所示系統的能控性判據。

引理1 能控性判據[26]對于式(3)所示的多智能體系統，以下說法是等價的。

1)式(3)所示的多智能體系統在leader-follower結構下是能控的。

3)矩陣[sI-Lf,Lfl],s∈C或[λiI-Lf,Lfl]是滿秩的，其中C表示復數域，λi(i=1,…,m)表示對應矩陣Lf的特征值。

從定義1可以看出，不同領導者的選取會使得系統的能控性不同，這也說明有向符號圖下使得系統能控的領導者的選取并非任意的。

2 leader-follower結構下系統能控性的圖論表征

命題1給定一個有向符號拓撲圖G，其中跟隨者動力學如式(3)所示，則leader-follower結構下系統的能控性不受領導者和領導者之間以及跟隨者指向領導者的連接關系的變化影響。

證明：leader-follower結構下系統的能控性僅取決于Laplacian矩陣L分塊中的Lf和Lfl，而不受矩陣Ll和矩陣Llf的影響。在圖G中，若改變領導者與領導者之間的連接關系和從跟隨者指向領導者的連接關系，矩陣Lf和矩陣Lfl都保持不變，因此leader-follower結構下系統的能控性不變。

命題1說明了單個拓撲圖中連接關系出現上述兩種情況時系統的能控性不變，不同拓撲圖之間增加上述兩種連接關系會給系統的能控性帶來的影響，我們在命題2中進行論證。

考慮leader-follower結構下的n個有向符號圖Gi=(Vi,Ei,Ai),i=1,…,n，其中Gi有一個跟隨者集合Vfi={v1,…,vmi}和一個領導者集合Vli={vmi+1,…,vni}，且Vfi∪Vli=Vi,Vfi∩Vli=φ，其中子圖Gi中跟隨者和領導者節點的個數分別為mi和ni-mi，Ei和Ai分別表示子圖Gi的邊集和鄰接矩陣。

命題2給定一系列能控的有向符號圖Gi,i=1,…,n，分別都是能控的，且個體狀態按照鄰居協議進行更新。若圖G=(V,E,A)按照如下的規則進行構造，其能控性可以保持:

3)A表示圖G中個體之間連接關系的鄰接矩陣，其中Alifj和Alilj分別表示圖G的鄰接矩陣中對應從子圖Gj中的跟隨者指向子圖Gi中領導者的連接部分以及從對應子圖Gj中的領導者指向子圖Gi中的領導者的連接部分，i,j=1,2,…,n，且i≠j。

命題2提供了一個通過能控有向拓撲子圖構造復雜有向能控拓撲圖的方法，除此之外，也給出了一個保證拓撲圖能控的領導者位置選取方式。例如，如果一個給定拓撲圖可以分為多個拓撲子圖，只要在每個拓撲子圖中選擇保證每個子圖能控的領導者，且不同子圖間通過各自的領導者之間的有向邊或者跟隨者指向領導者的有向邊建立連接關系，便可以構成一個更復雜的有向拓撲圖，此時該拓撲圖在原有領導者位置的選取下仍然是能控的。

3 基于有向符號路徑下的一類拓撲的能控性分析

本節研究使得給定特殊有向符號拓撲能控的充分條件。有向路徑作為有向拓撲里面最基礎且最簡單的拓撲結構，本文首先將對它的能控性問題進行分析研究，進而研究更復雜結構的能控性問題。

3.1 有向符號路徑的能控性

假定一個由n+1個節點構成的有向路徑圖，為了便于后面的研究，將初始節點編號為n+1，并依次將初始節點后面的子節點從1到n進行編號。

定理1對于有向符號路徑圖G，如果選擇路徑中的初始節點為領導者，那么它對應的多智能體系統是單領導者能控的。

證明：將n+1個節點構成的有向符號路徑的Laplacian矩陣按照式(2)的分塊形式寫作

其中，Lf∈Rn×n,Lfl∈Rn×(n-1)。構造矩陣[λI-Lf,Lfl]∈Rn×(n+1)如下：

該矩陣是n×(n+1)階的，取該矩陣的前n-1列及最后一列元素構成一個新矩陣Hp∈Rn×n。利用矩陣的初等列變換計算矩陣Hp的行列式

在有向符號路徑圖中，存在從vn+1到v1,v1到v2，v2到v3，…，vn-1到vn的有向邊，即系統中存在這些個體之間的信息傳遞，aij≠0。即|Hp|=(-1)na1na21a32…an,n-1≠0，矩陣Hp可逆且滿秩，rank(Hp)=n。由于矩陣Hp是通過矩陣[λI-Lf,Lfl]去掉第n列得到的矩陣，故rank(λI-Lf,Lfl)≥rank(Hp)=n。且[λI-Lf,Lfl]∈Rn×(n+1)，所以rank(λI-Lf,Lfl)=n，由引理1(3)可知系統能控。

3.2 有向路徑增加逆向邊對系統能控性的影響

假定一個由n+1個節點構成的有向路徑，在上述節點編號下，增加逆向邊是指增加一條從節點vj指向節點vi的有向邊，其中1)跟隨者vj指向領導者vi：i=n+1,j=1,…,n或2)跟隨者vj指向跟隨者vi:i,j=1,…n，且j>i。在有向路徑中增加逆向邊，相應的Laplacian形式如下：

其中，“*”位置的元素根據拓撲圖是否存在相應的逆向邊，可能為零可能不為零，即

進一步可以得到定理2。

定理2對于有向符號路徑中增加逆向邊形成的新拓撲圖G，如果選擇有向路徑中的初始節點為領導者，那么它對應的多智能體系統是單領導者能控的。

證明：1)假定增加的逆向邊是從跟隨者節點vi,i=1,…,n指向領導者節點，這種情況相當于增加了從跟隨者指向領導者的有向邊，由命題1可知增加這種連接關系不改變原有系統的能控性，此時系統仍是選擇路徑初始節點為領導者時系統單領導者能控的。

2)假定增加的逆向邊是從節點vj指向節點vi,i,j=1,2,…,n且j>i。跟隨者節點的狀態按照式(3)更新，此時的能控性與Lf和Lfl有關，利用Lf和Lfl構造矩陣[λI-Lf,Lfl]，采用與定理1相似的思路，可以得到該矩陣是滿秩的，即rank(λI-Lf,Lfl)=n，所以該系統是選擇路徑初始節點為領導者時單領導者能控的。

通過上面的分析可以看出在有向路徑中增加逆向邊形成的新的網絡拓撲的能控性等價于未加逆向邊時有向路徑的能控性。這也給我們在判斷一個較為復雜的有向網絡拓撲的能控性時，提供了一種新的思路：很多網絡拓撲都可以看作是由有向路徑增加逆向邊而得到的，如圖1所示的幾類特殊的網絡拓撲。

圖1 有向路徑中增加逆向邊形成的幾類拓撲圖Fig.1 Several classes of topological graphs formed by adding reverse edges to a directed path

圖1所示的4個拓撲結構都是通過在有向路徑的基礎上增加逆向邊(圖1中的紅色邊)得到的。以拓撲圖1b為例，拓撲圖1b是在有向路徑9→1→2→…→8的基礎上增加一條8→3的逆向邊形成的，此時選擇有向路徑的初始節點9為領導者,給定控制輸入信號，對應的多智能體系統是單領導者能控的，這也進一步印證了定理2中的結論。

由以上分析可知，在有向路徑中增加逆向邊并不會改變系統選擇路徑初始節點為領導者時系統單領導者能控的性質。

3.3 有向路徑增加順向邊對系統能控性的影響

在有向路徑中增加順向邊時，選擇路徑初始節點為領導者的情況下，利用前面的節點編號規則，即在有向路徑的基礎上，增加一條從節點vi指向節點vj的有向邊或者增加一條從節點vn+1指向節點vj的有向邊，其中i,j=1,…,n，且i

其中，“*”位置的元素根據拓撲圖是否存在相應的順向邊，可能為零也可能不為零。通過Laplacian矩陣的形式可以看出，該矩陣無法利用前面的分析方法得到選擇路徑初始節點為領導者時對應多智能體系統是單領導者能控的結論。圖2為一個由5個節點構成的有向路徑拓撲結構，且增加了一條從v2指向v4的順向邊，驗證發現此時系統的能控性與權重a32與a42的取值是否相等有關，在其他邊權重取值任意的情況下，當a32=a42時系統是不

圖2 5節點有向路徑增加順向邊拓撲圖Fig.2 5-node topology graph formed by adding a forward edge to a directed path

能控的，而當a32≠a42時系統能控。這也可以得出，有向路徑增加順向邊形成的拓撲圖的能控性是不能直接確定的，根據某些邊權重取值的不同，可能導致不同的能控性。有向路徑增加順向邊導致系統能控性的不同可以借助圖的劃分來進行理解，首先給出leader-follower結構下跟隨者節點集的幾乎等價劃分的定義，在此基礎上進行分析。

定義4 跟隨者節點集的幾乎等價劃分假定圖G=(V,E,A)是一個符號有向圖，π=πf∪πl={C1,C2,…,Cr}∪{Cr+1,…,Cn}是圖G的一個劃分。πf={C1,C2,…,Cr}是對應跟隨者節點的一個幾乎等價劃分，對任意的vs,vt∈Ci,i=1,…,r,j=1,…,r,r+1,…,n,i≠j，下列等式成立：

其中，ask和atk分別表示節點vk∈Cj指向vs∈Ci的有向邊權重以及vk∈Cj指向vt∈Ci的有向邊權重。

定義5 基于單領導者的跟隨者節點集的非平凡劃分假定π=πf∪πl={C1,C2,…,Cr}∪{Cr+1}是圖G的一個劃分，πf={C1,C2,…,Cr}是跟隨者集的非平凡幾乎等價劃分，且Cr+1中僅包含一個領導者節點，那么稱此時的劃分πf為基于單領導者的跟隨者節點集的非平凡劃分。

定義6 跟隨者特征矩陣跟隨者節點集Vf={v1,v2,…,vn}的一個劃分πf={C1,C2,…,Cr}的特征矩陣Pf∈Rn×r是由跟隨者節點形成的每個胞腔的特征向量作為其列向量形成的矩陣。矩陣Pf中的元素定義為

引理3[26]對于矩陣M∈Rn×n和P∈Rn×r，im(P)是M的不變子空間的充要條件是存在一個矩陣Q∈Rr×r滿足MP=PQ。

引理4[27]給定矩陣A∈Rn×n和B∈Rn×r，用〈A,B〉表示包含im(B)的最小A-不變子空間。矩陣對(A,B)是能控的條件是dim(〈A,B〉)=n。

定理3對于有向路徑增加順向邊形成的新拓撲圖G，如果跟隨者節點中存在非平凡胞腔，那么該拓撲結構對應的多智能體系統是選擇初始節點為領導者不能控的。

證明：因為πf={C1,C2,…,Cr}是圖G中跟隨者節點集Vf={v1,v2,…,vn}的一個幾乎等價劃分，且Pf是劃分πf的特征矩陣，根據引理3和引理4，im(Pf)是Lf的不變子空間。由于跟隨者節點中存在非平凡胞腔，r

由定理3可以得到若跟隨者節點中存在非平凡胞腔，則對應的多智能體系統是不能控的。而如圖2所示，增加順向邊會增加出現非平凡胞腔的可能性。

4 能控復雜有向符號拓撲的構造

在這一部分中，首先考慮將多個能控有向符號路徑圖通過特定連接關系進行連接，形成一個能控的有向樹圖，進而得到有向樹圖能控時的領導者選擇方式。然后將多個有向符號路徑圖加邊形成的能控拓撲圖通過特定連接關系進行連接，形成一類更廣泛的能控復雜有向符號拓撲圖，進而得到該拓撲圖能控時的領導者選擇方式。

4.1 有向符號樹圖

在多個有向符號路徑間增加特殊節點之間的連接關系，便可以得到有向樹圖。需要特別說明的是，之前的許多文獻關于有向樹圖的能控性描述都是基于選擇根節點為領導者，系統單領導者能控的充要條件是不同分支上的邊權重不同。本文的研究工作將不再規定不同分支邊權重不同和選擇單領導者使得系統能控這兩個條件，而是通過在有向樹圖中選擇多個領導者，得到在任意邊權重的情況下有向樹圖能控的條件。通過命題2和定理1可以直接得到關于有向符號樹圖的推論1。

例1給定一個如圖3a所示的有向符號樹圖G表示的多智能體系統，該符號有向樹圖劃分為5個有向符號路徑子圖Gi,i=1,…,5，其中V1={v1,v2,v3,v4},V2={v5,v6,v7,v8},V3={v9,v10,v11}，V4={v12,v13}，V5={v14,v15}。如圖3b所示，選定的領導者集為Vl={v1,v5,v9,v12,v14}，在該領導者位置的選取方式下，根據定理1和命題2，該有向符號樹圖表示的多智能體系統是能控的。

圖3 14個節點構成的有向樹圖Fig.3 A directed tree graph composed of 14 nodes

4.2 一類更廣泛的能控有向符號拓撲的構造

除了上述多個有向符號路徑可以形成有向符號樹圖之外，我們知道許多有向拓撲圖都可以看作是在有向路徑圖或者有向路徑加邊形成的拓撲圖中增加不同拓撲圖之間的連接關系而形成的。具體來說，前面的分析得到了有向路徑以及有向路徑加邊形成的拓撲能控的條件，我們將單個有向路徑或者單個有向路徑加邊形成的拓撲看做是一個個子圖，利用前面得到的定理1～3給定使得每個子圖能控的領導者位置的選取方式，結合命題2，在不同子圖間通過領導者之間以及跟隨者指向領導者的有向邊連接形成的新的拓撲結構仍是能控的結論，可以得到一類更廣泛的能控有向符號拓撲。

圖4 能控復雜有向符號拓撲的構造過程Fig.4 The construction process of controllable complex directed signed topology

5 總結

本文研究的是基于leader-follower結構有向符號多智能體系統的能控性問題。針對leader-follower結構特點，提出了有向拓撲下改變領導者和領導者之間以及跟隨者指向領導者的有向邊，不改變系統能控性的性質(命題1、2)，以有向路徑以及有向路徑加邊形成的新拓撲為基礎，給出了有向路徑以及加逆向邊和順向邊時系統能控的條件。具體來說，首先對有向路徑進行了研究，得到選擇有向路徑中的初始節點為領導者時系統是單領導者能控的(定理1)。進一步，在有向路徑的基礎上增加逆向邊并不改變系統原來的能控性(定理2)，但增加順向邊時能控性的情況比較復雜，能控性可能改變，也可能不改變，這取決于選定初始節點為領導者時，跟隨者節點中是否存在非平凡胞腔(定理3)。最后，在前面的基礎上，給出了一類更廣泛的能控復雜有向符號拓撲的構造方法，可以利用簡單能控拓撲圖通過特殊節點間的連接關系快速得到一類比較復雜的能控拓撲圖。文中利用具體的例子進行了相關的解釋和說明。