廣播信號下非一致多智能體系統的能控性

王曉曉，紀志堅

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

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

1 圖論準備知識和模型

1.1 圖論準備知識

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

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

1.2 模型

考慮如下多智能體系統:

(1)

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

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

?Γ]x+(In?B)u

(2)

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

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

1)系統是能控的。

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

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

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

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

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

(A?B)T=AT?BT

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

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

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

2 能控性分析

2.1 主要結果

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

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

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

證明系統的能控性矩陣為

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

因為C是對角矩陣，拉普拉斯L是對稱矩陣，所以C-L是對稱矩陣。在Γ是對稱矩陣的條件下，(C-L)?Γ也是對稱的，且根據文獻[16]可以表示為(C-L)?Γ=PΛPT，其中Λ是對角矩陣，其主對角線元素為(C-L)?Γ的特征值，而相似變換矩陣P的列向量是對應于(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)應沒有非零行向量，這要求不存在P的列向量與(In?B)的所有列向量正交。否則，該矩陣就會出現一整行均是零的情況，在這一情形下，該矩陣就不是行滿秩的，從而系統的能控性矩陣也不是行滿秩的。因為相似變換矩陣P的列向量是對應于(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

因此，系統能控，當且僅當：

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

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

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

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

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

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

2.2 [Γ B]的能控性

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

(3)

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

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

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

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

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

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

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

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

可以簡化為

Q=[BUDUTBUD2UTB…UDm-1UTB]

將U提出，矩陣Q可以轉換成：

Q=U[UTBDUTBD2UTB…Dm-1UTB]

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

[UTBDUTBD2UTB…Dm-1UTB]

(4)

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

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

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

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

2.3 路和完備圖的能控性

為了更全面理解系統能控性，本小節針對多智能體系統信息交換拓撲中的2類特殊構形路和完備圖討論(C-L)?Γ的特征值，進而發現非一致多智能體系統能控性更多的特點。

對具一致動態的多智能體系統而言，當信息交換拓撲結構為路PN時，系統可控[1,3,8]。下面的研究表明，對非一致的多智能體系統，情況發生變化，路既可能可控，也可能不可控。原因如下：

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

那么，具有非一致動態路徑的拉普拉斯矩陣為

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

圖1 三節點的路徑Fig.1 The path of three nodes

2)設

則C-L的特征值分別為-0.170 1, 1.688 9, 3.481 2。根據命題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)可得：非一致多智能體系統中，若其信息交換圖為路，系統既可能可控，也可能不可控。

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

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

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

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

上述討論表明，具非一致動態的多智能體系統其能控性比一致動態的多智能體系統更加復雜，其特殊構形的能控性結論通常發生改變。

2.4 改善方法

1) 改變節點的非一致動態，即各節點參數ci。例如：例1、例2的(1)、(2)，通過改變節點參數使得路和完備圖由不能控變為能控。

2) 改變多智能體系統的拓撲結構。例如：可以通過增加或去掉節點間的聯系，將不能控的拓撲結構轉換成接近的能控的拓撲結構。

3 結束語

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

參考文獻:

[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]. 北京：科學出版社， 2001: 5-6, 160-164.