等價劃分下多智能體系統能控性的一種判定方法

紀志堅

(1. 青島大學 自動化學院 系統科學研究院,山東 青島 266071;2. 山東省工業控制技術重點實驗室,山東 青島 266071)

1 引言

能控性是現代控制理論的一個基本概念,也是多智能體系統性能分析的一個核心問題,該問題的研究有助于認識系統的基本結構特性,促進建立多智能體動力學系統的性質與系統結構的關系,而等價劃分是智能體間信息交換網絡圖拓撲結構的一個典型劃分方法,是系統結構分解的一個重要方面,對它的研究,是深入理解系統動態演化規律的一個不可忽視的途徑,這是文章研究等價劃分下系統分布式能控性的主要原因。能控性概念最早是由卡爾曼(R.E.Kalman)等人在20世紀60年代初首次提出的[1],作為系統的一個基本性質,多智能體系統的能控性在近年來得到了越來越多的關注和研究,相關成果不斷涌現[2-5, 31-35]。其中,得到最多研究的一個能控性定義如下:對系統中的部分節點(個體)施加外部控制輸入,通過個體間的信息傳遞規則(即協議),在一定的時間內,將系統的全部節點從任意的初始狀態轉移到任意指定的終端狀態,其中,被施加控制輸入的節點被稱為領航者(leader),其余節點則被稱為跟從者(follower)。該定義借鑒了傳統能控性的定義方式,它反映了將所有節點的狀態驅動到任何所期望狀態的能力。多智能體系統的能控性定義在網絡辨識、隊形控制、分布估計和生物網絡等研究中均有所應用[6-13]。在2004年,Tanner首先提出了領航者-跟從者框架下的分布式能控問題,并給出了單積分器系統能控的代數充要條件,文中還指出,代數條件在圖論意義上的解讀是問題進一步解決的關鍵,這也為之后的科研工作者指出了一個重要的努力目標[14]。例如,Ji和Egerstedt基于拓撲圖的等價劃分給出了系統能控的一個必要條件[15]。此外,Ji等人首次證明了多智能體系統能控性只需在連通圖上進行研究,這不僅揭示了多智能體系統能控性由圖拓撲結構唯一決定這一事實,而且還提出了能控性基于特征向量進行判定的充要條件,從而為通過特征向量確定領航者數量和位置提供了一個方法[16]。

從領航者選取和協議設計等角度對能控性問題進行研究,可以得到能控性與拓撲結構之間關系的一些新的理解。例如,Ji等人提出了多智能體系統能控性的一種統一認識方法,表明了能控性作為系統內在性質的價值所在,并給出了非能控拓撲結構的一種構造方法[17]。Cai等人則在Laplacian矩陣結構的基礎上建立了系統能控的條件,并給出了基于路形拓撲的一種能控標準型[18]。Zhao等人通過領航者數量的調整以及邊權重的選取,提高了系統的能控性能,這種做法可以被認為是一種改變信息傳遞圖拓撲結構的另一種方式[19]。

信息交換圖的拓撲結構劃分是拓撲結構分解的一個主要形式,它是能控性研究的一個重要途徑。Lou等人研究了權重-平衡劃分下的能控性問題[20];Zhang和Guan等人基于拓撲圖的距離等價劃分研究了多智能體分布式系統的能控子空間[21,22];Ji等人通過引入坐標劃分研究了能控性的特征結構屬性[23],并通過拓撲結構的另一種形式的劃分,即將兩類圖以適當的形式進行銜接,形成一種新的具有能控性的拓撲結構,從而提出了一種構造能控拓撲圖的方法[24]。除此之外,等價劃分和松馳等價劃分也是研究分布式能控的常用方法[15, 25-28]。例如,Martin 等人在研究中運用了能控性分解,并通過松弛等價劃分給出了能控性的圖論刻畫[29];Su等人結合自同構給出了等價劃分下多智能體系統能控性的技術改進方法[30]。本文基于等價劃分研究了多智能體系統能控性的判定問題,并給出了能控性的一種確定方法。在智能體之間信息交換圖的基礎上,通過分析平凡或(和)非平凡胞腔進入領導者節點集合時的情形,探討了多智能體系統能控性會發生何種變化,給出了分塊矩陣的主子陣的構造方法,并得到了通過選取合適的領航者使得系統能控的方法。文中通過識別領航者使得系統不可控,清楚地給出了使多智能體能控的領航者選擇方法,為判定多智能體系統的分布式能控性提供了一個可供借鑒的新方法。

2 問題描述

多智能體系統描述為

(1)

式中N和l分別表示跟從者和領航者的數量,xi表示第i個智能體的狀態,i=1,…,N+l。設Ni為vi的鄰居集合,即Ni={j|vi～vj;j≠i},且協議定義為

(2)

使xN+1,…,xN+l扮演領航者角色,并將這些智能體重命名為

式中y是所有yi的堆棧向量,z是所有zj的堆棧向量,u是所有uN+j的堆棧向量,j=1,…,l。然后,在式(2)下,跟從者的動態方程為

(3)

式中F為G的拉普拉斯矩陣L刪除最后l行和l列后得到的矩陣。R是由被刪除列的前N個元素組成的N×l階子矩陣。

定義1如果系統(3)在控制輸入z下是能控的,那么稱在領航者xN+j,j=1,…,l和固定拓撲下的多智能體系統(1)是能控的。

多智能體系統分布式能控的幾個模型的討論和最新結果,可參閱[31]和[32]。

3 一種能控性的判定方法

本節研究了信息交換圖G的等價劃分,當平凡或(和)非平凡胞腔屬于領航者節點集合時,系統的能控性會發生什么變化。

胞腔C?V是節點集的一個子集。圖的劃分是指將其節點集分組為不同的胞腔。接下來,回顧一下等價劃分的定義。

定義2(等價劃分)對于任意的i,j,如果Cj中的每個節點在Ci中都有相同數量的鄰居,則稱Vg的r-劃分π是等價劃分,其中π中的胞腔為C1,…,Cr。在這種情況下,Ci中任意節點在Cj中的鄰居數用bij表示,且用r=|π|表示劃分π的基數。

在文獻[15,25]中,提出了利用信息交換圖的等價劃分來處理多領航者條件下的能控性問題。根據這個概念,下面的結論給出了系統不能控的圖理論特征。

引理1[25]給定一個信息交換圖G和誘導子圖Gf,如果在G和Gf上分別存在非平凡等價劃分π和πf,則系統(3)是不能控的,此時π的所有非平凡胞腔都包含在πf中。

結果表明,等價劃分是理解多智能體能控性的一個很有效的概念。這促使本文考慮以下問題:給定信息交換圖G的一個等價劃分π,當領航者來自平凡或(和)非平凡胞腔的一部分時,系統能控性如何?下面給出了兩個相關的性質。

設C1,…,Cr表示與等價劃分π相關的所有平凡胞腔,其中1≤γ≤r-1,表示為Γi1,…,ij?Ci1∪…∪Cij,?i1,…,ij∈{1,…,γ},1≤j≤γ?？梢钥吹溅1,…,ij是一個節點集,包含C1,…,Cr中任意j個胞腔中的節點。

命題1 如果從Γi1,…,ij中選擇任意一個節點作為領航者,則多智能體系統(1)是不能控的。

證明 為了簡化命題1,不失一般性,本文假設i1=1,…,ij=j。在這種情況下,領航者從Γi1,…,ij中選擇,因此,跟從者子圖Gf是由節點集Cj+1,…,Cγ組成的誘導子圖。因為C1,…,Cj是同時從原始的信息交換圖G中移除的,Gf中的胞腔Cj+1,…,Cγ被保存得很好。因此,Ck中的每個節點在Ck′中都有相同數量的鄰居,其中?k,k′∈{j+1,…,γ}。也就是說,Cj+1,…,Cγ是Gf的一個等價劃分。因為C1,…,Cj都是平凡胞腔,所以G和Gf共享胞腔集{Cj+1,…,Cγ}中的所有非平凡胞腔。根據引理1可得,這個系統是不能控的。

注釋1命題1表明,當從非平凡胞腔中選擇領航者時,多智能體系統是不能控的。

在命題1中,是從Γi1,…,ij的一組平凡胞腔中選擇領航者。在后續討論中,本文考慮領航者也可以從非平凡胞腔中選取的情況。要繼續研究,此時需要回憶起兩個結果。

引理2[15,25]如果圖G有一個非平凡等價劃分(NEP)π,所對應的特征矩陣為P,則拉普拉斯矩陣L相似于對角塊矩陣

(4)

引理3[15,25]設Gf為跟從者子圖,Lf是Gf的拉普拉斯矩陣L的對角子矩陣。如果Gf中有一個非平凡等價劃分(NEP)πf,并且G中有一個劃分π,這個πf中的所有非平凡胞腔也是π中的胞腔,那么

(5)

式中Tf是上面定義的矩陣。

引理4[15]假設信息交換圖G是連通的,當且僅當L和F不共享任何共同的特征值時,多智能體系統是能控的。

對于信息交換圖G的一個等價劃分π,設C1,…,Cl為非平凡胞腔,Cl+1,…,Cr為平凡胞腔。設{i1,…,ih}是{1,…,l}的任意子集,其中1≤i1≤…≤ih≤l,1≤h≤l-1。并且,{i1,…,ih}中的元素個數最多為l-1個。設{j1,…,js}是{l+1,…,r}的任意子集,其中l+1≤j1≤…≤js≤r,1≤s≤r-l。并且,s的最大值為r-l。在這種情況下,{j1,…,js}的最大集合與{l+1,…,r}重合。這與{i1,…,ih}不同,{i1,…,ih}始終是{1,…,l}的一個子集。對于一個任意的固定索引集{i1,…,ih}和{j1,…,js}。表示為

Xh,s?(Ci1∪…∪Cih)∪(Cj1∪…∪Cjs)。

接下來陳述以下結果。

定理1 如果節點集Xh,s中所有的智能體都被選為領航者,那么可以構造出引理2和引理3中的正交矩陣T和Tf,使LfQ和LfP分別是LQ和LP的主子矩陣,其中LQ、LfQ、LP和LfP分別為式(4)和(5)中介紹的對角塊矩陣。

證明 為了簡化陳述,本文對一個特殊的情況進行證明。一般的情況也可以用同樣的方式來證明。

假設信息交換圖G有一個包含非平凡胞腔C1、C2、C3和平凡胞腔C4、C5、C6的等價劃分π?，F在,選擇胞腔C3和C6中的所有智能體作為領航者。在這種情況下,i1=3,j1=6,X1,1?Ci1∪Cj1。

跟從者子圖Gf由胞腔C1、C2、C4和C5組成。此外,從等價劃分的定義可知,C1、C2、C4和C5構成了Gf的一個等價劃分πf。

對于等價劃分πf={Cf1,Cf2,Cf3,Cf4},其中Cf1=C1,Cf2=C2,Cf3=C4,Cf4=C5,πf的特征矩陣為Pf=[pf1,pf2,pf3,pf4]nf×rf,其中nf代表Gf中的節點個數,rf代表πf中的胞腔個數?；谏鲜稣撟C,πf中的所有非平凡胞腔也是π中的胞腔,因此,根據引理3,可以構造出一個正交矩陣Tf使式(5)成立。

結合Gf的劃分πf,本文將G的等價劃分π重新標記為Cl1?C1,Cl2?C2,Cl3?C4,Cl4?C5,Cl5?C3,Cl6?C6,也就是說,G和Gf共同的胞腔C1、C2、C4和C5在π中以更高的優先級重新標記。于是,π的特征矩陣為P=[p1,…,p6]n×r,其中pi對應于Cli,n代表G中的節點數,r代表π中的胞腔數,i=1,…,6。

(6)

這是因為C1,C2都是π和πf的非平凡胞腔。由于p3和p4分別對應于平凡胞腔C4和C5,pf3和pf4也是如此,所以得到

(7)

(8)

(9)

式中1∈Rni-1是每個元素都是1的向量,ni是胞腔Cfi中的節點數。記

式中LQ是引理2中引入的矩陣。根據式(9),

即,LfQ是LQ的一個主子矩陣。

為了證明LfQ是LP的一個主子矩陣,需要重新回顧式(8)。記

既然

由此得出

即,LfP是LP的一個主子矩陣。

例1 下面這個例子被用來驗證定理1的證明思路。假設G的等價劃分π的胞腔為C1,…,C5,其中C1={v1,v2},C2={v3,v4},C3={v5,v6},C4={v7},C5={v8}。選擇胞腔C3={v5,v6}中的節點為領航者。特征矩陣P和Pf分別為

可以看出

由上述矩陣之間的關聯,可以看到,定理1成立。

注釋2給定G的等價劃分π,是否存在一種識別領航者的方法,從而使相關的多智能體系統不是能控的。定理1提出了一種方法來處理這個問題。例如,可以利用定理1來討論下面推論1中的能控性問題。此外,定理1的證明是構造性的,在證明過程中,蘊含了網絡圖拓撲結構的劃分、領航者的選取和能控性是否成立這三者之間的重要關系,這為將來構造或設計能控或不能控的拓撲結構提供了一個值得借鑒的嘗試途徑。這也是定理1提出來的方法的一個主要優勢。

推論1 當節點集Xh,s中的所有智能體都被選為領航者時,如果G和Gf上分別存在等價劃分π和πf,使得π和πf共享所有的非平凡胞腔,則多智能體系統是不能控的。

可得到

然后,再結合式(4)和(5),就意味著,L和Lf有共同的特征值。根據引理4可得,多智能體系統是不能控的。

注釋3與引理1不同,推論1清楚地給出了使多智能體能控的領航者選擇方法。

4 結論

在本文中,我們主要研究了圖劃分下的多智能體系統能控性的判定問題?；诘葍r劃分,文中得到了多智能體系統能控性的一種判定方法。在智能體之間信息交換圖的基礎上,分析了當平凡或(和)非平凡胞腔進入領航者節點集合時,多智能體系統能控性的變化情況。此外,我們還給出了分塊矩陣的主子陣的構造方法,進而得到了通過選取合適的領航者使得系統能控的方法。文中通過識別領航者使得系統不可控,清楚地給出了使多智能體能控的領航者選擇方法,為判定多智能體系統的分布式能控性提供了一個可供借鑒的新方法。