多信號輸入下多智能體系統(tǒng)的圖可控性分類

李自強，紀志堅，晁永翠，董潔

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

?

多信號輸入下多智能體系統(tǒng)的圖可控性分類

李自強，紀志堅，晁永翠，董潔

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

在多信號輸入情形下，對多智能體系統(tǒng)的圖可控性分類進行了分析，構建了新的基于多信號輸入下的系統(tǒng)模型。進而利用秩判據(jù)和PBH判據(jù)，在新的模型下得到系統(tǒng)與可控性的關系，新的模型更方便地表現(xiàn)多智能體系統(tǒng)的一般性。此外，在拉普拉斯矩陣下，對多智能體系統(tǒng)與可控性的關系做了詳細的分析與研究，特別是在拉普拉斯矩陣的特征值與系統(tǒng)能控性的關系方面進行了分析。解決了多信號輸入下可控性分類的問題，并提高了研究可控性的準確性。而且，在已有結論的基礎上對多智能體系統(tǒng)可控性的內(nèi)容進行了完善。

多信號輸入系統(tǒng)；圖可控性分類；秩判據(jù)和PBH判據(jù)；拉普拉斯矩陣；可控性

近幾年來學術界對多智能體系統(tǒng)已經(jīng)有了廣泛的研究和關注[1-14]，并且已經(jīng)應用在多個領域中，如無人機的編隊控制、機器人的編隊控制，甚至在軍事上也有廣泛的應用[15-17]。多智能體系統(tǒng)的核心問題是關于可控性的問題，可控性能夠使每個智能體的狀態(tài)達到人們所期望的結果，并且使多智能體系統(tǒng)發(fā)揮最大的作用。所以，多智能體系統(tǒng)的可控性研究具有重要的意義。

在多智能體系統(tǒng)中，對具有領導者—跟隨者結構的圖可控性研究大都是基于單信號輸入下或者是更為簡單的模型下[13,18]，在多智能體中，模型的建立對系統(tǒng)的可控性有著重要的影響。在所建立的模型下，充分認識系統(tǒng)與可控性的關系，并理解系統(tǒng)對可控性的影響，這些無疑對解決多智能體系統(tǒng)的可控性問題提供了很好的方法和幫助。所以研究特定模型下系統(tǒng)的可控性成為一個熱點。

Tanner是最早通過系統(tǒng)中各節(jié)點之間的聯(lián)系來研究可控性的[19]。他通過鄰居信息，提出了其中一個節(jié)點為領導者時系統(tǒng)可控的充分必要條件，并得到了無向圖下的能控性定理。這對后續(xù)有關可控性的研究給予了很大的幫助。早在Aguilar的文章中[18]，Aguilar就整個圖的可控性進行分類，根據(jù)圖選取不同的領導者時圖是否可控，來定義了3種圖可控性，并就3種分類進行了詳細的分析，但是Aguilar的文章內(nèi)容是在單信號輸入的特殊模型下進行研究的，即每個領導者節(jié)點受到同一個信號的輸入，而本文是在更一般的多信號輸入模型下進行研究，每個領導者節(jié)點可能受到不同的多個信號的輸入，這種多信號輸入的模型更能準確地表現(xiàn)多智能體系統(tǒng)的一般性，而且本文糾正了Aguilar文章[18]中關于齊次向量的條件可控圖問題。

一些研究者[19-22]近幾年對基于拉普拉斯矩陣下的可控性作了很多的研究，本文也是在拉普拉斯矩陣下，結合矩陣論的知識[23-25]，對系統(tǒng)的可控性與拉普拉斯矩陣的關系進行了研究，特別是在拉普拉斯矩陣的特征值和特征向量等對系統(tǒng)可控性的影響方面進行了深入的研究，另外，本文主要在多輸入信號情況下，對多智能體系統(tǒng)中的圖可控性進行分類，具體分為多信號輸入下本質(zhì)可控圖，多信號輸入下完全不可控圖以及多信號輸入下條件可控圖，并就這3種分類的特殊性進行了描述，而且對它們的性質(zhì)進行了相應的闡述。

1 預備知識

在圖G中，對于點集合的兩個節(jié)點i和節(jié)點j，定義節(jié)點i和節(jié)點j之間的距離為dG(i,j)，表示為節(jié)點i和節(jié)點j之間最短的通道。當圖中任意一對節(jié)點之間存在一條通道時，我們說圖G是連通的。拉普拉斯矩陣是半正定且實對稱的，因此L的特征值可以給定順序為λ1≤λ2≤…≤λn，其中特征值λ1=0對應的特征向量為[1 1 … 1]T。如果圖G是連通的，則λ1=0是L的非重特征根，此時有λ2>0，本文中圖G的特征值或特征向量即為圖拉普拉斯矩陣L的特征值或特征向量。

本文主要分析G=(V,E)上的可控性問題，其中xi(t)∈R代表了節(jié)點i∈V在時刻t時的狀態(tài)，節(jié)點間的相互關系由邊集E來表示。在時刻t時，一個外部控制向量通過一狀態(tài)向量bm∈Rq施加在節(jié)點i上。單個節(jié)點的狀態(tài)方程可以表示為

另外，在時刻t，輸出方程y(t)∈Rp由輸出矩陣C∈Rn×p表示。所以對于連通圖G=(V,E)，整個系統(tǒng)方程表示為

式中B=[b1b2…bn]T∈Rn×q。

定義1 如果所有領導者節(jié)點都受到同一個信號的輸入，那稱這樣的系統(tǒng)為單信號輸入系統(tǒng)。當系統(tǒng)受到多個信號輸入時，稱這樣的系統(tǒng)為多信號輸入系統(tǒng)。

另一種情況是在n個點的圖中，定義輸入節(jié)點集合S，每個點可能收到多個信號的輸入，相應的輸入矩陣為

2 主要結論

首先討論單信號輸入下系統(tǒng)可控性與多信號輸入下系統(tǒng)可控性的區(qū)別和聯(lián)系。

多信號輸入下系統(tǒng)可控性與單信號輸入下系統(tǒng)可控性是有很大區(qū)別的，在選取的領導者下，有些圖在單信號輸入系統(tǒng)下是不可控的，但在多信號輸入系統(tǒng)下卻不一定不可控。

圖1 具有4個節(jié)點的圖

當任意選取領導者節(jié)點時，有些圖在單信號輸入系統(tǒng)下是完全不可控的，但在多信號輸入系統(tǒng)下并非完全不可控的。

圖2 具有6個節(jié)點的圖

通過上文，可以看出多信號輸入下可控性與單信號輸入下可控性有很大的區(qū)別，那么就有必要討論基于拉普拉斯矩陣下的多信號輸入系統(tǒng)與系統(tǒng)可控性的關系，本文通過下面的定理給出。

定理 1假定可對角化矩陣L無重特征值，矩陣U是由L的線性無關的單位特征向量構成的矩陣，那么〈L;B〉的維數(shù)等于W=U-1B中非零列向量的個數(shù)。特別地，系統(tǒng)(L,B)是可控的充要條件是W矩陣中無零列向量。當L有重特征值，且wi≠0q時，系統(tǒng)(L,B)是不可控的，當且僅當重特征值λi所對應的向量組wi中，存在線性相關的向量，其中i=1,2，…,n。

由于U是非奇異矩陣，所以它不影響式(3)右邊矩陣的秩，右邊的矩陣展開后即為

對上式進行列變換得

(4)

當特征值不同時，式(4)后面的矩陣是滿秩的，只需考慮式(4)前面1×q矩陣，其中每個元素為n×n的對角矩陣，則此矩陣實際上是具有n行，n×q列的矩陣:

當L有重特征值情況時，根據(jù)無重特征值的情況，證明如下：

通過下面情況的論述都能夠驗證定理1中無重特征值時的情況。對于具有個n個節(jié)點的圖，節(jié)點2和節(jié)點4為領導者節(jié)點時，此時W=U-1B=

在L無重特征值下，僅當存在wi2=wi4=0時，〈L;B〉的維數(shù)小于n，〈L;B〉的維數(shù)等于wi中非零向量的個數(shù)。而且當且僅當wi≠0時，dim(〈L;B〉)=n，即此時系統(tǒng)可控。

由于U是非奇異矩陣，所以它不影響式(5)右邊矩陣的秩，對式(5)右邊矩陣進行列變換得

在λ1≠λ2下，上式后面的矩陣是滿秩的，根據(jù)前面的矩陣，只有當w11=w12=0或w21=w22=0時，〈L;B〉的維數(shù)小于2，而且當且僅當wi≠0時，dim(〈L;B〉)=2，即此時系統(tǒng)可控。

令En為n×q維的矩陣，并且矩陣中的每個元素為1;0n為n×q維的矩陣，并且矩陣中的每個元素為0;1n為n維列向量，且每個元素都為1;0q為q維列向量，且每個元素都為0。下面推論由定理1的證明可得。

注釋單信號輸入系統(tǒng)下，對應的拉普拉斯矩陣如果存在重特征值，則系統(tǒng)不可控；但是在多信號輸入系統(tǒng)下，并不能單純依靠存在重特征值來判斷系統(tǒng)的不可控性。

證明同理定理1證明為

即

通過上文的闡述，可以給出多信號輸入下圖可控性分類的定義。

定義2在連通圖G中，對于系統(tǒng)(1)

1)如果除去圖中每個點都是輸入節(jié)點以及每個點都不是輸入節(jié)點的2種情況后，任意選取圖中的點為輸入節(jié)點時，系統(tǒng)(L,B)是可控的，則圖關于B是多信號輸入下本質(zhì)可控圖；

2)如果在圖中選取任意點為輸入節(jié)點時，系統(tǒng)(L,B)都是不可控的，則圖關于B是多信號輸入下完全不可控圖；

3)如果圖關于B即不是多信號輸入下本質(zhì)可控圖也不是多信號輸入下完全不可控圖，則圖關于B是多信號輸入下條件可控圖。

下面是分情況討論3種情況下的圖性質(zhì)。

2.1 多信號輸入下本質(zhì)可控圖

在本節(jié)中，主要給出2個多輸入下本質(zhì)可控圖的必要條件，通過下面的命題論證。

命題1多輸入下本質(zhì)可控圖是不對稱的。

證明設G是多輸入下本質(zhì)可控圖，則L必須有不同的特征值。在這用反證法，假設多輸入下本質(zhì)可控圖是對稱的，則G有一個非平凡自同構群，設J是置換矩陣代表G的一個非恒等自同構，那么存在2個不同的標準正交基ei和ej，使得Jei=ej和Jej=ei。則有J[ei0n…]=[ej0n…]和J[0nej…] = [0nei…]。并且有JL(G)=L(G)J，令B=[ei0n…]+[0nej…]?？梢缘玫絁B=B。設λ為矩陣L的特征值，其對應的特征向量為v，滿足Lv=λv。兩邊同乘以J，有JLv=Jλv，因為JL(G)=L(G)J，則有L(Jv)=λ(Jv)，即Jv也是對應于特征值λ的特征向量。因為L有一系列正交特征向量，v-Jv也是L的特征向量。而且JB=JTB=B，則有(v-Jv)TB=vTB-vTJTB=vTB-vTB=0即B正交于L的特征向量。因此系統(tǒng)(L,B)是不可控的。這與G是多輸入下本質(zhì)可控圖相矛盾。所以多輸入下本質(zhì)可控圖是不對稱的。結論得證。

任何少于6個點的圖都可以改為對稱的圖。如圖3(a)中，5個點的情況可以改為圖3(b)中對稱的圖形。由此啟發(fā)可以得到下面的命題。

(a)改變前

(b)改變后

命題 2多輸入下本質(zhì)可控圖至少有6個點。

證明根據(jù)命題1，并且由任何不對稱的圖形至少有6個點得證。

對于系統(tǒng)(1)，不對稱的圖并不都是多輸入下本質(zhì)可控圖。通過圖(4)可以進行驗證。

圖4 具有6個節(jié)點的不對稱圖

圖4是一個在給定點標記下的不對稱圖，它的拉普拉斯矩陣為

2.2 多信號輸入下完全不可控圖

相對于多信號輸入下本質(zhì)可控圖，圖對稱與否并不與多信號輸入下完全不可控圖有關聯(lián)。對于系統(tǒng)(1)，對稱的圖并不都是多輸入下完全不可控圖。如圖1為對稱圖，當B=[e2e4]時，根據(jù)秩判據(jù)，此時系統(tǒng)可控。

給定圖G，則可以寫出圖的拉普拉斯矩陣，也可以求出圖的特征值，特征值所對應的特征向量也可以求出，由此啟發(fā)，給出下面的命題。

證明根據(jù)定理1，得證。

證明根據(jù)定理1，得證。

2.3 多信號輸入下條件可控圖

在本節(jié)中，主要提出文獻[18]中的錯誤，并舉例進行闡述。

對于文獻[18]中的模型(2)實際上是系統(tǒng)(1)的特殊情況，即單信號輸入系統(tǒng)，此時要在系統(tǒng)(2)下進行分析與討論文獻[18]中的問題。

對于文獻[18]中推論4.2：G是一個含有n個點的連通圖，并且n≥3時，如果G有一個(r,s)-齊次可控向量，則G是條件可控的。

如圖5，在系統(tǒng)(2)下，令b=[0 0 1 1 0 0]T，其中i∈Vb={3,4}，若i=3，則Ni={1,2}且j∈VVb={1,2,5,6}，得r=2，即領導節(jié)點3與2個跟隨者鄰接，若j=1，則Nj={3}，得s=1，即跟隨者節(jié)點1與1個領導者鄰接。由此稱b=[0 0 1 1 0 0]T在圖G中是一個(2,1)-齊次可控向量。則根據(jù)文獻[18]中推論4.2得圖G是條件可控的。

圖5 具有6個節(jié)點的對稱圖

圖5的拉普拉斯矩陣為

可以求出它有一個兩重的特征值為3。即圖5具有重特征值，根據(jù)注釋，在單信號輸入系統(tǒng)下可以得到圖G是完全不可控的，顯然是矛盾的，所以文獻[18]中推論4.2是錯誤的。在多信號輸入系統(tǒng)下，更不能通過齊次向量來判斷圖的條件可控性。

3 結束語

本文就多信號輸入系統(tǒng)下的可控性分類問題進行了詳細的研究與分析，并對拉普拉斯矩陣下特征值和特征向量與可控性的關系進行了闡述和論證，論述了單信號輸入系統(tǒng)與多信號輸入系統(tǒng)的區(qū)別和聯(lián)系，而且糾正了文獻[18]中關于齊次可控向量應用在條件可控圖上的錯誤。本文對可控性分類的研究方法和結果，為以后研究更復雜的圖可控性問題提供了方向和幫助。

[1]OLFATI-SABER R, MURRAY R M. Consensus problems in networks of agents with switching topology and time-delays[J]. IEEE transactions on automatic control, 2004, 49(9): 1520-1533.

[2]JADBABAIE A, LIN J, MORSE A S. Coordination of groups of mobile autonomous agents using nearest neighbor rules[J]. IEEE transactions on automatic control, 2003, 48(6): 988-1001.

[3]JI Z J, LIN H, LEE T H. Controllability of multi-agent systems with switching topology[C]//Proceeding of the 2008 IEEE Conference on Robotics, Automation and Mechatronics. Chengdu: IEEE, 2008: 421-426.

[4]劉菲, 紀志堅. 時滯二階離散多智能體系統(tǒng)的可控性[J]. 系統(tǒng)科學與數(shù)學, 2015(3): 298-307. LIU Fei, JI Zhijian. Controllability of second-order discrete-time multi-agent systems with time-delay[J]. Journal of systems science and mathematical sciences, 2015(3): 298-307.

[5]董潔, 紀志堅, 王曉曉. 多智能體網(wǎng)絡系統(tǒng)的能控性代數(shù)條件[J]. 智能系統(tǒng)學報, 2015, 10(5): 747-754. DONG Jie, JI Zhijian, WANG Xiaoxiao. Algebraic conditions for the controllability of multi-agent systems[J]. CAAI transactions on intelligent systems, 2015, 10(5): 747-754.

[6]晁永翠, 紀志堅, 王耀威, 等. 復雜網(wǎng)絡在路形拓撲結構下可控的充要條件[J]. 智能系統(tǒng)學報, 2015, 10(4): 577-582. CHAO Yongcui, JI Zhijian, WANG Yaowei, et al. Necessary and sufficient conditions for the controllability of complex networks with path topology[J]. CAAI transactions on intelligent systems, 2015, 10(4): 577-582.

[7]王曉曉, 紀志堅. 廣播信號下非一致多智能體系統(tǒng)的能控性[J]. 智能系統(tǒng)學報, 2014, 9(4): 401-406. WANG Xioaxiao, JI Zhijian. Controllability of non-identical multi-agent systems under a broadcasting control signal[J]. CAAI transactions on intelligent systems, 2014, 9(4): 401-406.

[8]JI M, EGERSTEDT M. A graph-theoretic characterization of controllability for multi-agent systems[C]//Proceeding of the American Control Conference, 2007. New York: IEEE, 2007: 4588-4593.

[9]JIANG Fangcui, WANG Long, XIE Guangming, et al. On the controllability of multiple dynamic agents with fixed topology[C]//Proceeding of the American Control Conference, 2009. St. Louis, Missouri, USA: IEEE, 2009: 5665-5670.

[10]JI Zhijian, WANG Zidong, LIN Hai, et al. Controllability of multi-agent systems with time-delay in state and switching topology[J]. International journal of control, 2010, 83(2): 371-386.

[11]LIU Bo, CHU Tianguang, WANG Long, et al. Controllability of a leader-follower dynamic network with switching topology[J]. IEEE transactions on automatic control, 2008, 53(4): 1009-1013.

[12]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.

[13]MARTINI S, EGERSTEDT M, BICCHI A. Controllability analysis of multi-agent systems using relaxed equitable partitions[J]. International journal of systems, control and communications, 2010, 2(1/2/3): 100-121.

[14]CHAPMAN A, MESBAHI M. On symmetry and controllability of multi-agent systems[C]//Proceeding of the 2014 IEEE 53rd Annual Conference on Decision and Control. Los Angeles, CA, USA: IEEE, 2014: 625-630.

[15]劉金琨, 爾聯(lián)潔. 多智能體技術應用綜述[J]. 控制與決策, 2001, 16(2): 133-140, 180. LIU Jinkun, ER Lianjie. Overview of application of multiagent technology[J]. Control and decision, 2001, 16(2): 133-140, 180.

[16]朱戰(zhàn)霞, 鄭莉莉. 無人機編隊飛行控制器設計[J]. 飛行力學, 2007, 25(4): 22-24. ZHU Zhanxia, ZHENG Lili. The controller design of UAV formation flight[J]. Flight dynamics, 2007, 25(4): 22-24.

[17]LANE D M, MCFADZEAN A G. Distributed problem solving and real-time mechanisms in robot architectures[J]. Engineering applications of artificial intelligence, 1994, 7(2): 105-117.

[18]AGUILAR C O, GHARESIFARD B. Graph controllability classes for the laplacian leader-follower dynamics[J]. IEEE transactions on automatic control, 2014, 60(6): 1611-1623.

[19]TANNER H G. On the controllability of nearest neighbor interconnections[C]//Proceeding of the 43rd IEEE Conference on Decision and Control. Nassau, Bahamas: IEEE, 2004: 2467-2472.

[20]HONG Yiguang, GAO Lixin, CHENG Daizhan, et al. Lyapunov-based approach to multiagent systems with switching jointly connected interconnection[J]. IEEE transactions on automatic control, 2007, 52(5): 943-948.

[21]MOREAU L. Stability of multiagent systems with time-dependent communication links[J]. IEEE transactions on automatic control, 2005, 50(2): 169-182.

[22]OGREN P, EGERSTEDT M, HU Xiaoming. A control Lyapunov function approach to multiagent coordination[C]//Proceedings of the 40th IEEE Conference on Decision and Control. Orlando, Florida, USA: IEEE, 2001: 1150-1155.

[23]BIGGS N. Algebraic graph theory[M]. 2nd ed. Cambridge: Cambridge University Press, 1993.

[24]王樹禾. 圖論[M]. 北京: 科學出版社, 2004.

[25]CHARTRAND G, ZHANG Ping. 圖論導引[M]. 范益政, 譯. 北京: 人民郵電出版社, 2007: 1-17. CHARTRAND G, ZHANG Ping. Introduction to graph theory[M]. FAN Yizheng, trans. Beijing: The People's Posts and Telecommunications Press, 2007: 1-17.

李自強，男，1991年生，碩士研究生，主要研究方向為多智能體系統(tǒng)。

紀志堅，男，1973年生，博士，教授，博士生導師，主要研究方向為群體系統(tǒng)動力學與協(xié)調(diào)控制、復雜網(wǎng)絡、切換動力系統(tǒng)的分析與控制、系統(tǒng)生物以及基于網(wǎng)絡的控制系統(tǒng)等。曾主持國家自然科學基金3項、山東省杰出青年科學基金項目1項。山東省杰出青年基金獲得者，發(fā)表學術論文70余篇，其中被SCI檢索23篇，EI 檢索50余篇。

晁永翠，女，1990年生，碩士研究生，主要研究方向為復雜網(wǎng)絡的可控性。

Graph controllability classes of networked multi-agent systems with multi-signal inputs

LI Ziqiang， JI Zhijian， CHAO Yongcui， DONG Jie

(School of Automation Engineering，Qingdao University, Qingdao 266071，China)

In this paper, we analyze graph controllability classes in networked multi-agent systems with multisignal inputs and construct a new system model. To determine the relationship between controllability and networked multi-agent systems, we used a controllability rank criterion and the Popov-Belevitch-Hautus criterion in our proposed model, which is more convenient and more general in its application. In addition, we analyzed in detail the relationship between networked multi-agent systems and controllability, especially, between Laplacian eigenvalue and controllability. Based on our results, we conclude that we have solved the controllable classification problem associated with multisignal input, improved research accuracy with respect to controllability, and improved the controllability of networked multi-agent systems.

multi-signal input systems; graph controllability classes; rank criterion and PBH criterion; Laplacian matrix; controllability

2016-01-08.

日期：2016-09-13.

國家自然科學基金項目(61374062)；山東省杰出青年科學基金項目(JQ201419).

紀志堅.E-mail：jizhijian@pku.org.cn.

TP273

A

1673-4785(2016)05-0680-08

10.11992/tis.201601017

http://www.cnki.net/kcms/detail/23.1538.TP.20160913.0838.002.html

李自強，紀志堅，晁永翠，等.多信號輸入下多智能體系統(tǒng)的圖可控性分類[J]. 智能系統(tǒng)學報， 2016, 11(5):680-687.

英文引用格式：LI Ziqiang，JI Zhijian，CHAO Yongcui，et al.Graph controllability classes of networked multi-agent systems with multi-signal inputs[J]. CAAI transactions on intelligent systems, 2016,11(5):680-687.