廣播信號下非一致多智能體系統(tǒng)的能控性

王曉曉，紀(jì)志堅

(青島大學(xué) 自動化工程學(xué)院，山東 青島 266071)

多智能體系統(tǒng)的能控性問題已引起學(xué)術(shù)界的高度重視。對該問題的研究源于自然界中普遍存在的群體行為，例如生物界昆蟲、鳥和魚群等協(xié)作捕食, 共同抵御入侵者等行為。自然界中的群體行為使得它們能很好地生存繁衍下去，同時也給人類以很大的啟發(fā)：與單個智能體相比，多智能體系統(tǒng)的合作可以大大提高系統(tǒng)的性能，完成更復(fù)雜的任務(wù)。H.G.Tanner[1]最早提出了領(lǐng)導(dǎo)者-跟隨者結(jié)構(gòu)下多智能體系統(tǒng)的能控性問題。然后Rahmani等[2]介紹了多智能體能控的代數(shù)和圖論的條件。隨后，許多人開始從圖論的角度[3-5]研究多智能體系統(tǒng)的能控性，并在連續(xù)時間[6]和離散時間[7]2種情形下，對多智能體系統(tǒng)的能控性問題分別進行了討論。多智能體系統(tǒng)的能控性問題具有重要的現(xiàn)實意義，可以通過它研究多智能體網(wǎng)絡(luò)的編隊控制問題[9]，即通過調(diào)節(jié)領(lǐng)航者的行動來驅(qū)動跟隨者到達理想的位置，從而實現(xiàn)系統(tǒng)的能控性。隨著在領(lǐng)導(dǎo)者-跟隨者結(jié)構(gòu)下多智能體系統(tǒng)的不斷發(fā)展，漸漸地有人開始嘗試在新的結(jié)構(gòu)下研究多智能體系統(tǒng)的能控性問題。目前，越來越多的人開始在廣播信號結(jié)構(gòu)[10-11]下研究系統(tǒng)的能控性。然而，到目前為止，這方面的研究成果還不多。廣播信號結(jié)構(gòu)與領(lǐng)導(dǎo)者-跟隨者結(jié)構(gòu)相比有以下優(yōu)勢：1)在現(xiàn)實生活中已得到廣泛應(yīng)用，例如電臺和電視臺等；2)硬件上的優(yōu)勢，不需要提供用于領(lǐng)導(dǎo)者和跟隨者進行信息交流的設(shè)備等。多智能體的能控性問題已取得了長足的進展，但都是在網(wǎng)絡(luò)中的智能體都是相同(即一致動態(tài))的假設(shè)下進行的，采用這種假設(shè)可以更容易地分析網(wǎng)絡(luò)，特別是對網(wǎng)絡(luò)的同步問題和能控性問題。然而，大多數(shù)實際工程中的動態(tài)網(wǎng)絡(luò)具有不同的節(jié)點動態(tài)，例如一個動力系統(tǒng)具有不同的物理參數(shù)，其發(fā)電機和負(fù)載等結(jié)構(gòu)通過運輸線相互連接，共同構(gòu)成一個非一致的動態(tài)網(wǎng)絡(luò)。因此，研究具有非一致動態(tài)[8,12]的多智能體網(wǎng)絡(luò)的能控性問題，無論從理論角度還是從實踐角度來說，都具有極其重要的意義和價值。本文致力于研究在廣播控制信號下，具有非一致動態(tài)的非定向的多智能體網(wǎng)絡(luò)的能控性問題，而非定向的多智能體網(wǎng)絡(luò)是指在無向圖下研究多智能體系統(tǒng)。

1 圖論準(zhǔn)備知識和模型

1.1 圖論準(zhǔn)備知識

本文的信息交換圖均為無向圖，關(guān)于無向圖更全面的結(jié)論可參看文獻[14]。一個無向圖G包含一個頂點集V(G)和一個邊集E(G)。無向圖中的邊可以用(i,j)表示。如果(i,j)∈E(G)，那么i和j是相鄰關(guān)系，可以用i～j表示。令Ni表示vi的鄰集，則Ni={j|vi～vj;j≠i}。路徑i0i1…iL是一個ik-1～ik(k=1,2,…,L)的有限序列。完備圖是指圖中的任意2個節(jié)點都是相鄰關(guān)系。一個節(jié)點的度數(shù)是指其相鄰節(jié)點的個數(shù)。簡單圖是指不含圈和重邊的圖。在本文中，主要考慮簡單圖。

任何無向圖都可以由它的鄰接矩陣A(G)來表示，鄰接矩陣能充分表達圖上頂點相鄰的關(guān)系，是一個只含有元素0和1的對稱矩陣。如果i和j是相鄰的，則aij是1，否則為0。度數(shù)矩陣D(G)是一個對角矩陣，其中aii是節(jié)點vi的度數(shù)。拉普拉斯矩陣L(G)=D(G)-A(G)，也是一個對稱矩陣。拉普拉斯矩陣與節(jié)點的互聯(lián)拓?fù)溆嘘P(guān)。

1.2 模型

考慮如下多智能體系統(tǒng):

(1)

式中：xi∈Rm是第i個智能體的狀態(tài)，ui∈Rp是控制輸入信號。因為每個節(jié)點都接受ui，所以稱為廣播控制信號。B∈Rm×p是該系統(tǒng)的控制輸入矩陣。ciΓxi(ci∈R,ci≠0)描述了系統(tǒng)中非一致的節(jié)態(tài)。?！蔙m×m為表示節(jié)點分量之間內(nèi)部耦合關(guān)系的常數(shù)矩陣。LijΓ(xi-xj)指的是相鄰節(jié)點之間的信息交流，即所謂的鄰域信息交互,其中Lij是拉普拉斯矩陣L(G)的元素。

為了更好地分析系統(tǒng)能控性，可以將系統(tǒng)轉(zhuǎn)換成緊湊的矩陣形式。令x=[x1Tx2T…xnT]T∈Rm×n，u=[u1Tu2T…unT]T∈Rp×n，系統(tǒng)(1)可以改寫成：

?Γ]x+(In?B)u

(2)

式中：C=diag(c1,c2,…,cn)。

定義1 對具有如(1)動態(tài)的多智能體系統(tǒng)，如果對任意的初始狀態(tài)，都存在一個控制輸入信號使得系統(tǒng)在有限的時間內(nèi)從該初始狀態(tài)到達任意期望的狀態(tài)，那么就稱多智能體系統(tǒng)是能控的。

1)系統(tǒng)是能控的。

2)系統(tǒng)能控性矩陣[BABA2B…An-1B]滿秩。

3)對于所有的λ∈R，矩陣[λI-AB]滿秩，即如果vTA=λvT，則vTB≠0T，其中v是A對應(yīng)于特征值λ的非零左特征向量(PBH判據(jù))。

命題2 矩陣的Kronecker積有以下性質(zhì)[16]：

(A+B)?C=A?C+B?C；

(A?B)(C?D)=(AC)?(BD)；

(A?B)T=AT?BT

4)設(shè)A∈Cm×m的全體特征值為λ1,λ2,…,λm，其相應(yīng)的特征向量α1,α2,…,αm，B∈Cn×n的全體特征值為μ1,μ2,…,μn，其相應(yīng)的特征向量是β1,β2,…,βn，那么，αi?βj是A?B對應(yīng)于特征值λiμj的特征向量(i=1,2,…,m;j=1,2,…,n)。

定義2 如果當(dāng)|i-j|≤1時,Jij>0，而當(dāng)|i-j|≥2時，Jij=0，稱J是雅可比矩陣[13]，表示成矩陣形式為

式中：ai,bi>0。在這里，只介紹下文用到的雅可比矩陣的一個性質(zhì)：雅可比矩陣的特征值各不相同。

2 能控性分析

2.1 主要結(jié)果

定理1 設(shè)Γ是對稱的，則具有如式(1)動態(tài)的多智能體系統(tǒng)能控當(dāng)且僅當(dāng)下面的2個條件同時成立：

1)[Γ,B]是能控矩陣對；

2) (C-L)?Γ的特征值各不相同。

證明系統(tǒng)的能控性矩陣為

[(In?B) [(C-L)?Γ](In?B) …[(C-L)?Γ]mn-1(In?B)]

因為C是對角矩陣，拉普拉斯L是對稱矩陣，所以C-L是對稱矩陣。在Γ是對稱矩陣的條件下，(C-L)?Γ也是對稱的，且根據(jù)文獻[16]可以表示為(C-L)?Γ=PΛPT，其中Λ是對角矩陣，其主對角線元素為(C-L)?Γ的特征值，而相似變換矩陣P的列向量是對應(yīng)于(C-L)?Γ的特征值的正交特征向量。那么，能控性矩陣可以改寫成

[(In?B)PΛPT(In?B)…(PΛPT)mn-1(In?B)]

簡化為

[(In?B)PΛPT(In?B)…PΛmn-1PT(In?B)]

將P提出，能控性矩陣可以寫成：

P[PT(In?B)ΛPT(In?B)…Λmn-1PT(In?B)]

因為P非奇異，所以P不影響能控性矩陣的秩。因此，僅研究下述矩陣的秩即可。

[PT(In?B)ΛPT(In?B)…Λmn-1PT(In?B)]

要使該矩陣行滿秩，PT(In?B)應(yīng)沒有非零行向量，這要求不存在P的列向量與(In?B)的所有列向量正交。否則，該矩陣就會出現(xiàn)一整行均是零的情況，在這一情形下，該矩陣就不是行滿秩的，從而系統(tǒng)的能控性矩陣也不是行滿秩的。因為相似變換矩陣P的列向量是對應(yīng)于(C-L)?Γ的特征值的正交特征向量，所以要求P的列向量不能正交于(In?B)，也就是說，要求(C-L)?Γ的特征向量不正交于(In?B)。通過命題2的陳述(4)得知：對于(C-L)?Γ的任一特征向量，均存在(C-L)和Γ的2個非零特征向量，分別記其為v1和v2，使得該特征向量可以寫成v1?v2。前面的討論要求v1?v2不與(In?B)的所有列向量正交，即(v1T?v2T)(In?B)≠0T，所以要求

(v1TIn)?(v2TB)≠0T

因此，系統(tǒng)能控，當(dāng)且僅當(dāng)：

1)v1TIn≠0T，即沒有一個C-L的特征向量正交于In，也就是說，C-L的特征向量不為0n。因為特征向量的定義是非零向量，所以這個條件在任何情況下均成立，所以可以不考慮該條件。

2)v2TB≠0T，即沒有一個Γ的特征向量正交于B，根據(jù)命題1的陳述(3)，[ΓB]是一個控制矩陣對。

由于Λ是一個對角非奇異矩陣，故Λ乘以一個矩陣只會使該矩陣的各個元素得到相同比例的縮放。然而，矩陣Λ對角線上的元素不能出現(xiàn)相同的元素，否則，能控性矩陣會出現(xiàn)線性相關(guān)的行，則控制矩陣也不能行滿秩。因為矩陣Λ是一個對角矩陣，且其主對角線元素為(C-L)?Γ的特征值，所以要求(C-L)?Γ的特征值各不相同。

綜上所述：當(dāng)Γ是對稱的，欲使系統(tǒng)(2)能控，當(dāng)且僅當(dāng)下面的2個條件同時成立：

1)[ΓB]是能控矩陣對；

2)(C-L)?Γ的特征值各不相同。

2.2 [Γ B]的能控性

首先，研究定理1的條件1)，即子系統(tǒng)

(3)

的能控性。其中?！蔙m×m，B∈Rm×p的定義同(1)。

定理2Γ是對稱的(同定理1)，則系統(tǒng)(3)能控當(dāng)且僅當(dāng)下述2個條件同時成立：

1)Γ的特征值各不相同；

2)Γ的特征向量不正交于B。

證明： 系統(tǒng)(3)的能控性矩陣是

Q=[BΓBΓ2B…Γm-1B]

因為Γ對稱，所以它可以表達為Γ=UDUT，其中D是一個對角矩陣，其主對角線元素為Γ的特征值，而相似變換矩陣U的列向量是對應(yīng)于Γ的特征值的正交特征向量[16]。那么，矩陣Q可以改寫成：

Q=[BUDUTB(UDUT)2B… (UDUT)m-1B]

可以簡化為

Q=[BUDUTBUD2UTB…UDm-1UTB]

將U提出，矩陣Q可以轉(zhuǎn)換成：

Q=U[UTBDUTBD2UTB…Dm-1UTB]

因為矩陣U非奇異，所以U不影響Q的秩。因此，主要研究式(4)矩陣的秩即可。

[UTBDUTBD2UTB…Dm-1UTB]

(4)

欲使Q行滿秩，UTB的行向量應(yīng)是非零的，也就是說，不存在U的列向量，其與B的所有列向量正交。否則將會出現(xiàn)式(4)矩陣的一整行元素均是零的情況，那么式(4)就不是行滿秩的，即Q不是行滿秩的。因為相似變換矩陣U的列向量是對應(yīng)于Γ的特征值的正交特征向量，所以U的列向量不能正交于B，也就是說，Γ的特征向量不正交于B。由于D是一個對角非奇異矩陣，故D乘以一個矩陣只會使該矩陣的各個元素得到相同比例的縮放。然而，D對角線上的元素不能出現(xiàn)相同的元素，否則，Q會出現(xiàn)線性相關(guān)的行，則控制矩陣Q也不能行滿秩。因為D是一個對角矩陣，其主對角線元素為Γ的特征值，所以要求Γ的特征值各不相同。

綜上所述：當(dāng)Γ是對稱的，系統(tǒng)(3)可控，當(dāng)且僅當(dāng)下述2個條件同時成立：

1)Γ的特征值各不相同；

2)Γ的特征向量不正交于B。

2.3 路和完備圖的能控性

為了更全面理解系統(tǒng)能控性，本小節(jié)針對多智能體系統(tǒng)信息交換拓?fù)渲械?類特殊構(gòu)形路和完備圖討論(C-L)?Γ的特征值，進而發(fā)現(xiàn)非一致多智能體系統(tǒng)能控性更多的特點。

對具一致動態(tài)的多智能體系統(tǒng)而言，當(dāng)信息交換拓?fù)浣Y(jié)構(gòu)為路PN時，系統(tǒng)可控[1,3,8]。下面的研究表明，對非一致的多智能體系統(tǒng)，情況發(fā)生變化，路既可能可控，也可能不可控。原因如下：

無向圖路的拉普拉斯矩陣為

那么，具有非一致動態(tài)路徑的拉普拉斯矩陣為

例1 圖1是一個簡單的三節(jié)點的路徑，特殊的是各節(jié)點的狀態(tài)不同(即非一致動態(tài))，且每個節(jié)點都接受控制輸入信號(即廣播信號)。

圖1 三節(jié)點的路徑Fig.1 The path of three nodes

2)設(shè)

則C-L的特征值分別為-0.170 1, 1.688 9, 3.481 2。根據(jù)命題2直接計算可得：(C-L)?Γ的特征值分別為-2.332 1, -1.561 8, -1.131 4, -0.083 0, 0.113 9, 0.823 7, 1.697 8, 15.507 8, 31.965 1。因為(C-L)?Γ的特征值各不相同，所以該路徑能控。

綜合1)、2)可得：非一致多智能體系統(tǒng)中，若其信息交換圖為路，系統(tǒng)既可能可控，也可能不可控。

已有結(jié)果表明，對具一致動態(tài)的多智能體系統(tǒng)來說，完備圖KN不可控[1,3,8]。由例2知，當(dāng)多智能體系統(tǒng)的動態(tài)是非一致時，完備圖既可能可控，也可能不可控。

例2 圖2是一個四節(jié)點的完備圖，特殊的是各節(jié)點的狀態(tài)不同(即非一致動態(tài))，且每個節(jié)點都接受控制輸入信號(即廣播信號)。

圖2 四節(jié)點的完備圖Fig.2 The complete graph of four nodes

綜合(1)、(2)可得：非一致的多智能體系統(tǒng)中的完備圖，既可能可控，也可能不可控。

上述討論表明，具非一致動態(tài)的多智能體系統(tǒng)其能控性比一致動態(tài)的多智能體系統(tǒng)更加復(fù)雜，其特殊構(gòu)形的能控性結(jié)論通常發(fā)生改變。

2.4 改善方法

1) 改變節(jié)點的非一致動態(tài)，即各節(jié)點參數(shù)ci。例如：例1、例2的(1)、(2)，通過改變節(jié)點參數(shù)使得路和完備圖由不能控變?yōu)槟芸亍?/p>

2) 改變多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)。例如：可以通過增加或去掉節(jié)點間的聯(lián)系，將不能控的拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換成接近的能控的拓?fù)浣Y(jié)構(gòu)。

3 結(jié)束語

本文在廣播信號下，對非一致的多智能體系統(tǒng)的能控性進行了研究，得到了使其能控的充分必要條件，并進一步分析證明了該充分必要條件。為了得到更深入的理解，在非一致動態(tài)下還研究了路徑和完備圖的能控性，研究結(jié)果表明，與一致動態(tài)的多智能體系統(tǒng)相比，非一致情形在廣播信號下，路和完備圖的能控性發(fā)生變化，并指出節(jié)點的非一致動態(tài)使多智能體系統(tǒng)的能控性問題更加復(fù)雜。此外，還提出了改善非一致多智能體系統(tǒng)能控性的方法。與領(lǐng)導(dǎo)者-跟隨者結(jié)構(gòu)相比，廣播信號結(jié)構(gòu)在現(xiàn)實生活中(如電臺和電視臺)更為普遍，本文研究的非一致動態(tài)與實際工程中的動態(tài)網(wǎng)絡(luò)更為接近，無論從理論還是實踐角度，本文的研究都有其自身的價值和意義。

參考文獻:

[1]TANNER H G. On the controllability of nearest neighbor interconnections[C]//Proceedings of the 43rd IEEE Conference on Decision and Control. Atlantis Paradise Island, Bahamas, 2004: 2467-2472.

[2]RAHMANI A, MESBAHI M. On the controlled agreement problem[C]//Proceedings of the IEEE American Control Conference. Minneapolis, USA, 2006: 1376-1381.

[3]RAHMANI A, JI Meng, MESBAHI M, et al. Controllability of multi-agent systems from a graph-theoretic perspective[J]. SIAM Journal on Control and Optimization, 2009, 48(1): 162-186.

[4]JI Meng, EGERSTEDT M. A graph-theoretic characterization of controllability for multi-agent systems[C]//Pro- ceedings of the IEEE American Control Conference. NewYork, USA, 2007: 4588-4593.

[5]QI Xiao. On controllability of linear systems from a graph-theoretic perspective[C]//Proceedings of the 31st Chinese Control Conference. Hefei, China, 2012: 152-154.

[6]LIU Bo, XIE Guangming, CHU T, et al. Controllability of interconnected systems via switching networks with a leader[C]//IEEE International Conference on Systems, Man and Cybernetics. Taipei, China, 2006: 3912-3916.

[7]LIU Bo, CHU T, WANG L, et al. Controllability of a leader-follower dynamic network with switching topology[J]. IEEE Transactions on Automatic Control, 2008, 53(4): 1009-1013.

[8]XIANG L Y, ZHU J H, CHEN Fei, et al. Controllability of weighted and directed networks with nonidentical node dynamics[OL/EB]. [2014-01-20].http://www.hindawi.com/journals/mpe/2013/405034/.

[9]JI Z J, WANG Z D, LIN H, et al． Interconnection topologies for multi-agent coordination under leader-follower framework[J]．Automatica, 2009, 45(12)： 2857-2863.

[10]AZUMA S, YOSHIMURA R, SUGIE T. Broadcast control of multi-agent systems[J]. Automatica, 2013, 49(8): 2307-2316.

[11]YOON M G, ROWLINSON P, CVETKOVIC D, et al. Controllability of multi-agent dynamical systems with a broadcasting control signal[J]. Asian Journal of Control, 2014, 16(4): 1-7.

[12]COWAN N J, CHASTAIN E J, VILHENA D A, et al. Nodal dynamics, not degree distributions, determine the structural controllability of complex networks[J]. PLoS ONE, 2012, 7(6): e38398.

[13]BLOEMENDAL A. Jacobi matrices[EB/OL]. [2012-05-30]. http://www.math.harvard.edu/～alexb/rm/Jacobi.pdf.

[14]GODSIL C, ROYLE G. Algebraic Graph Theory[M]. New York: Springer, 2001: 1-2, 163-171, 279-295.

[15]CHEN C T. Linear system theory and design[M]. New York: Oxford University, 1999: 144-153.

[16]徐仲，張凱院，陸全，等. 矩陣論簡明教程[M]. 北京：科學(xué)出版社， 2001: 5-6, 160-164.