多智能體網(wǎng)絡(luò)系統(tǒng)的能控性代數(shù)條件

董潔，紀(jì)志堅(jiān)，王曉曉

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

多智能體網(wǎng)絡(luò)系統(tǒng)的能控性代數(shù)條件

董潔，紀(jì)志堅(jiān)，王曉曉

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

能控性是多智能體系統(tǒng)研究的核心問題，主要包括結(jié)構(gòu)可控性和精準(zhǔn)可控性。對多智能體系統(tǒng)的模型和能控性代數(shù)條件進(jìn)行了總結(jié)。在相對協(xié)議和絕對協(xié)議條件下，運(yùn)用圖論和矩陣論的知識系統(tǒng)分析了多智能體系統(tǒng)能控性的代數(shù)條件。按照同質(zhì)多智能體到異質(zhì)多智能體的順序，對現(xiàn)有的多智能體系統(tǒng)模型和代數(shù)條件進(jìn)行了梳理，并在已有結(jié)論的基礎(chǔ)上對多智能體系統(tǒng)能控性的代數(shù)條件進(jìn)行了改善，進(jìn)一步提出了新的代數(shù)條件。多智能體能控性代數(shù)條件的改進(jìn)大大簡化了能控性的計(jì)算量。

多智能體系統(tǒng)；結(jié)構(gòu)可控性；精準(zhǔn)可控性；相對協(xié)議；絕對協(xié)議；代數(shù)條件；圖論；矩陣論

自然界中普遍存在著群體行為，例如鳥的成群結(jié)隊(duì)、魚和昆蟲協(xié)作捕食等，都顯示出一些群體特質(zhì)：相對簡單的生物個(gè)體可以通過群體共同完成更為復(fù)雜的任務(wù)。自然界中的群體行為使得它們能夠很好地生存繁衍下去，同時(shí)也給人類很大的啟發(fā)：與單個(gè)智能體相比，多智能體系統(tǒng)的合作可以大大提高系統(tǒng)的性能，完成更復(fù)雜的任務(wù)。

多智能體技術(shù)是近年來新興的一門控制學(xué)科，它具有自主性、協(xié)調(diào)性、自組織能力和推理能力等特點(diǎn)。采用多智能體系統(tǒng)解決問題在魯棒性、可靠性和對未知環(huán)境的適應(yīng)性等方面也有很多的潛在優(yōu)勢［1］。因此，多智能體系統(tǒng)的研究已經(jīng)成為控制領(lǐng)域的一個(gè)熱點(diǎn)［2?4］，并且已經(jīng)廣泛的應(yīng)用在各個(gè)領(lǐng)域，如智能交通、機(jī)器人的編隊(duì)控制，甚至是軍事用途［5?11］。

智能體系統(tǒng)研究的核心問題是能控性問題，能控性是現(xiàn)代控制理論的一個(gè)基本概念，由卡爾曼（Klaman）在20世紀(jì)60年代首次提出［12］。多智能體系統(tǒng)的能控性是指基于系統(tǒng)內(nèi)部智能體之間的相互連接關(guān)系，通過對多智能體內(nèi)部的領(lǐng)航者施加外部控制輸入，使得跟隨者由任意給定的初始狀態(tài)到達(dá)期望的最終狀態(tài)。能控性能使每個(gè)智能體的狀態(tài)達(dá)到人們預(yù)定的結(jié)果，使系統(tǒng)發(fā)揮最大的作用，因此多智能體系統(tǒng)能控性的研究具有非常重要的意義。Tanner在2004年最早提出了多智能體網(wǎng)絡(luò)系統(tǒng)的能控性概念，敘述了單輸入線性系統(tǒng)領(lǐng)航－跟隨者的經(jīng)典可控性，即領(lǐng)航者接受外部控制信號，對跟隨者發(fā)布指令，從而影響跟隨者的運(yùn)動。但是這種結(jié)構(gòu)的引入也帶來了新的問題，如領(lǐng)航者的選取，領(lǐng)航者的丟失問題等［13］。文獻(xiàn)［14］提出了控制協(xié)議，介紹了多智能體網(wǎng)絡(luò)系統(tǒng)能控的代數(shù)條件和圖論條件。近年來，越來越多的研究者開始從圖論的角度研究多智能體的能控性［15?16］，拓展了多智能體系統(tǒng)能控性的理論研究范圍。多智能體網(wǎng)絡(luò)系統(tǒng)的能控性不僅在理論方面具有重要研究價(jià)值，同時(shí)也具有重要的實(shí)踐意義，例如可以借助多智能體網(wǎng)絡(luò)研究編隊(duì)控制，即通過調(diào)整領(lǐng)航者的行為來驅(qū)動跟隨者達(dá)到理想的位置［17］。很多現(xiàn)實(shí)中的網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)、電網(wǎng)、食物網(wǎng)和神經(jīng)網(wǎng)絡(luò)等都存在內(nèi)在節(jié)點(diǎn)間的動態(tài)關(guān)系，但是文獻(xiàn)［13?18］沒有考慮到節(jié)點(diǎn)之間具有內(nèi)在動力的情況。因此，從理論和實(shí)踐的角度來看，異構(gòu)動態(tài)多智能體網(wǎng)絡(luò)系統(tǒng)的可控性研究具有極其重要的意義和價(jià)值［19?20］。Cai基于高階異質(zhì)多智能體系統(tǒng)的分析建立了復(fù)雜異質(zhì)多智能體系統(tǒng)模型，并且提出了系統(tǒng)不能控的2個(gè)充分條件［21?28］。Ji等研究了具有狀態(tài)時(shí)間延遲和切換拓?fù)涞亩嘀悄荏w系統(tǒng)的能控性［22?24］。Liu研究了含多個(gè)領(lǐng)航者和時(shí)滯情況下切換離散時(shí)間多智能體系統(tǒng)的能控性，提出系統(tǒng)的能控性僅僅是由領(lǐng)航者與跟隨者之間的交互信息所決定的［25］。在絕對協(xié)議下，文獻(xiàn)［26?27］研究了在廣播控制信號下多智能體系統(tǒng)的能控性。與領(lǐng)航者－跟隨者結(jié)構(gòu)相比，廣播信號在現(xiàn)實(shí)生活中應(yīng)用更為廣泛。文獻(xiàn)［28］研究了一致性協(xié)議下單智能體的能控性。本文基于相對協(xié)議和絕對協(xié)議，總結(jié)了多智能體網(wǎng)絡(luò)系統(tǒng)的模型和能控性的代數(shù)條件。闡述了圖論的基本知識，敘述了在相對協(xié)議下，多智能體網(wǎng)絡(luò)系統(tǒng)的模型和能控性的代數(shù)條件?？偨Y(jié)了在絕對協(xié)議下多智能體網(wǎng)絡(luò)系統(tǒng)的模型和能控性的代數(shù)條件，指出了該領(lǐng)域新的研究方向。

1 圖論的準(zhǔn)備知識

本文使用的通信結(jié)構(gòu)均為無向圖，關(guān)于無向圖更全面的內(nèi)容見文獻(xiàn)［29］。

一個(gè)無向圖G＝（V，E）包括一個(gè)頂點(diǎn)集V＝｛v1，v2，…，vn｝和一個(gè)邊集E＝｛（vi，vj）｜vi，vj∈V｝，邊是指在圖G里不同的無序節(jié)點(diǎn)對。如果節(jié)點(diǎn)vi，vj∈V，并且互為鄰居，那么它們之間的關(guān)系可以用vi～vj表示。令Ni表示節(jié)點(diǎn)i的鄰居集，Ni＝j(luò){｜vi～vj}。路徑vi0vi1…vis是一個(gè)vik－1～vik，k＝1，2，…，s的有限序列。如果在任意2個(gè)不同的節(jié)點(diǎn)對之間都有路徑，那么就說G是連通的。完備圖是指圖中任意2個(gè)節(jié)點(diǎn)都是相鄰的關(guān)系。圖G＝（V，E）是無向圖，其中vi∈V，與節(jié)點(diǎn)vi鄰接的節(jié)點(diǎn)數(shù)就是vi的度數(shù)。不含圈和重邊的無向圖稱為簡單圖。各頂點(diǎn)的度均相同的無向簡單圖稱為正則圖。

圖G的度矩陣D（G）是一個(gè)對稱矩陣，它的對角線元素就是節(jié)點(diǎn)的度數(shù)。圖G的鄰接矩陣A（G）表達(dá)了圖G中各頂點(diǎn)之間的相鄰關(guān)系，任意一個(gè)無向圖都可以由鄰接矩陣A（G）來表示，它是一個(gè)只含有元素0和元素1的對稱矩陣，如果節(jié)點(diǎn)vi和vj是相鄰的，則aij是1，否則就是0。圖的拉普拉斯矩陣L（G）是一個(gè)實(shí)對稱矩陣，它定義為度矩陣與鄰接矩陣之差：L（G）＝D（G）－A（G），經(jīng)過計(jì)算可得：

2 相對協(xié)議下多智能體網(wǎng)絡(luò)系統(tǒng)的可控性

多智能體網(wǎng)絡(luò)系統(tǒng)的相對協(xié)議是ui＝本節(jié)基于相對協(xié)議，總結(jié)了多智能體網(wǎng)絡(luò)系統(tǒng)能控性的模型和代數(shù)條件，同時(shí)提出了一些新的代數(shù)條件。

2．1 同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

將按照從一階同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)到高階同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的方式，對能控性代數(shù)條件進(jìn)行總結(jié)。

2．1．1 一階同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

采用多智能體系統(tǒng)如下：

式中：xi代表智能體i的狀態(tài)，wij代表G的邊權(quán)重，n和l分別是領(lǐng)航者和跟隨者的數(shù)目。假設(shè)圖G代表該系統(tǒng)的通信拓?fù)鋱D，其相應(yīng)的拉普拉斯矩陣為L。定義一個(gè)含有n個(gè)跟隨者，l個(gè)領(lǐng)航者的多智能體，令系統(tǒng)（1）可以寫成如下形式：

式中：xf和xl分別代表跟隨者和領(lǐng)航者狀態(tài)的迭加向量，Lff∈Rn×n和Lll∈Rl×l分別對應(yīng)于系統(tǒng)跟隨者和領(lǐng)航者的編號，Llf表示從跟隨者到領(lǐng)航者的通信連接關(guān)系，Lfl表示從領(lǐng)航者到跟隨者的通信連接關(guān)系。只要系統(tǒng)中的領(lǐng)航者能驅(qū)動跟隨者到達(dá)期望的狀態(tài)，那么系統(tǒng)就是可控的。本文研究的能控性問題是領(lǐng)航者對跟隨者的控制能力，即系統(tǒng)（3）的能控性問題。

如果存在輸入信號u（t），能使系統(tǒng)在規(guī)定的時(shí)間內(nèi)從任意的初始狀態(tài)xf（0）被驅(qū)使到理想狀態(tài)xf（T），則系統(tǒng)（3）是能控的。

定義1［30］如果將矩陣L劃分成式（2）的形式，最后l個(gè)智能體為領(lǐng)航者，當(dāng)且僅當(dāng)可控，則系統(tǒng)就是能控的。

引理1［31］給定系統(tǒng)x·f＝－Lffxf－Lflxl，可以得出以下的說法是等同的：

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

2）能控性矩陣

是行滿秩的；

3）對于系統(tǒng)所有的特征值λ∈R，矩陣對［λI－LffLfl］都是行滿秩的，也就是說如果vTLff＝λvT則vTLfl≠0，其中v是矩陣Lff的特征值λ所對應(yīng)的非零的左特征向量。

注釋1 學(xué)術(shù)界已經(jīng)廣泛研究了一階動力學(xué)多智能體網(wǎng)絡(luò)系統(tǒng)的模型，例如文獻(xiàn)［13?18］。而系統(tǒng)（1）是一般的加權(quán)系統(tǒng)模型。

命題1 系統(tǒng)（3）是能控的，也就是［LffLfl］是可控的，那么當(dāng)且僅當(dāng)矩陣L和矩陣Lff沒有相同的特征值。

定理1 系統(tǒng)（3）是可控的，即矩陣對［LffLfl］是可控的，那么矩陣L不存在與領(lǐng)航者節(jié)點(diǎn)所對應(yīng)向量元素全為0的左特征向量。

證明 根據(jù)引理1，如果矩陣Lff中存在與特征值λ所對應(yīng)的左特征向量vf∈Cn，使得vTfLfl＝0成立，那么矩陣對［LffLfl］是不可控的。構(gòu)造一個(gè)向量v∈Cn＋l，令，那么下式成立：則有

所以vTL＝λvT。這說明向量v是L的左特征向量，并且對應(yīng)于所有領(lǐng)航者的最后l項(xiàng)全為零元素。因此定理1成立。

2．1．2 高階同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性采用文獻(xiàn)［21，32］的多智能體網(wǎng)絡(luò)系統(tǒng)模型：

式中：xi∈Rd，F(xiàn)∈Rd×d，wij∈R，B∈Rd×m，ui∈Rm；xi表示智能體i的狀態(tài)；wij表示圖G的邊權(quán)重，代表了節(jié)點(diǎn)i和j之間的連接強(qiáng)度；B是控制輸入矩陣。如果輸入ui＝0，那么智能體i就是跟隨者，反之就是領(lǐng)航者。定義則系統(tǒng)（4）就可以寫成

假設(shè)前q個(gè)智能體是領(lǐng)航者，那么

注釋2 文獻(xiàn)［21，32］的狀態(tài)方程為X·＝－FXLT＋BU。為了使分析一致，將X·＝－FXLT＋BU進(jìn)行拉直處理轉(zhuǎn)化成式（5）進(jìn)行分析。

引理2 實(shí)矩陣A、B、C、D的維數(shù)兼容，那么有以下結(jié)論［33］：

4）A為m×m的矩陣，它的特征值λ1，λ2，…，λm所對應(yīng)的左特征向量分別是α1，α2，…，αm，B為n× n的矩陣，它的特征值μ1，μ2，…，μn所對應(yīng)的左特征向量分別是β1，β2，…，βn。則A?B的特征值是λiμj（i＝1，2，…，m；j＝1，2，…，n），對應(yīng)的左特征向量是αi?βj。

定理2［21］要使系統(tǒng)（5）能控，那么以下2個(gè)條件必須同時(shí)成立。

1）［F B］是一個(gè)能控矩陣對；

2）矩陣L不存在前q項(xiàng)全是零元素的左特征向量。

證明 根據(jù)PBH判據(jù)，如果系統(tǒng)（5）是不可控的，那么矩陣L?F中存在與特征值λ相對應(yīng)的左特征值向量v，使得vT（Λ?B）＝0成立。假設(shè)矩陣L和F對應(yīng)的左特征向量分別是α∈Cn和β∈Cd，由引理2可知，v＝α?β和（αT?βT）（Λ?B）＝0同時(shí)成立，所以得到

要使式（6）成立，則有以下2種情況：

1）如果αTΛ＝0，也就是說矩陣L存在這樣的左特征向量，其前q項(xiàng)都是零元素；或者

2）βTB＝0，即［F B］是不可控的。

分析以上2種情況，可知定理2成立。

2．2 異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

按照從簡單異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)到復(fù)雜異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的順序?qū)δ芸匦缘木€性代數(shù)條件進(jìn)行總結(jié)。

2．2．1 簡單異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

1）領(lǐng)航－跟隨者框架下簡單異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的模型與文獻(xiàn)［19］相似：

式中：xi∈Rd，ci∈R，F(xiàn)∈Rd×d，wij∈R，B∈Rd×m，ui∈ Rm。ciFxi表示節(jié)點(diǎn)i之間的內(nèi)部動態(tài)關(guān)系。如果輸入ui＝0，那么智能體i就是跟隨者，否則就是領(lǐng)航者。定義則系統(tǒng)（7）可以寫成：

定理3［19］要使系統(tǒng)（8）能控，那么以下2個(gè)條件必須同時(shí)成立。

1）［F B］是一個(gè)能控矩陣對；

2）（C－L）不存在前q項(xiàng)都為零的左特征向量。證明 定理3的證明過程與定理2相似。

2）廣播信號下簡單異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的模型與文獻(xiàn)［20］中相似，系統(tǒng)模型為

式中：xi∈Rd，ci∈R，F(xiàn)∈Rd×d，wij∈R，B∈Rd×m，u∈Rm。ciFxi表示節(jié)點(diǎn)i之間的內(nèi)部動態(tài)關(guān)系。由于系統(tǒng)（9）中所有的智能體都接收相同的控制信號，所以稱u為廣播控制信號。定義，則系統(tǒng)（9）可以寫成如下形式：

命題2［19］如果系統(tǒng)（10）是能控的，那么當(dāng)且僅當(dāng)以下2個(gè)條件同時(shí)滿足：

1）［F B］是一個(gè)能控矩陣對；

2）矩陣（C－L）?F的所有特征值各不相同。

2．2．2 復(fù)雜異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

文獻(xiàn)［21］的復(fù)雜異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)寫成

式中：xi∈Rd，wij∈R，F(xiàn)ij∈Rd×d，ui∈Rm，Bi∈Rd×m。將標(biāo)量wij與Fij合并為一項(xiàng)，那么方程（11）可以變形為

將方程（12）與方程（1）相比較，如果把方陣Mij∈Rd×d看作是拓?fù)鋱DG的邊權(quán)重，那么系統(tǒng)的鄰接矩陣為

命題4［21］如果文獻(xiàn)［21］中異質(zhì)多智能體系統(tǒng)的拓?fù)鋱DG是結(jié)構(gòu)不能控的，那么整個(gè)系統(tǒng)都是不能控的。

2．3 一般多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

采用文獻(xiàn)［25］的一般動力學(xué)多智能體網(wǎng)絡(luò)系統(tǒng)模型：

式中：xi∈Rp代表智能體i的狀態(tài)，ui∈Rs是智能體i的耦合變量，ul∈Rq是智能體i的外部輸入。A＝Rp×p，B∈Rp×q，C∈Rp×s。

注釋3 文獻(xiàn)［19］中，ci∈R表示節(jié)點(diǎn)i之間的異質(zhì)動態(tài)關(guān)系，文獻(xiàn)［21］中Fij∈Rd×d表示節(jié)點(diǎn)i之間的異質(zhì)動態(tài)關(guān)系。文獻(xiàn)［21］的異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性是非常復(fù)雜的，所以對于這樣一個(gè)異質(zhì)網(wǎng)絡(luò)系統(tǒng)，只得到了系統(tǒng)不能控的2個(gè)充分條件。

命題3［21］如果方程（11）表示的加權(quán)矩陣圖是雙向的，即Mik＝Mki（?i，k＝1，2，…，n），并且矩

每個(gè)智能體i的耦合變量ui∈Rs是由鄰居間的耦合擴(kuò)散變量決定的。也就是說，系統(tǒng)的相對協(xié)議為

令x＝col（x1，x2，…，xn），u＝col（u1，u2，…，um），則系統(tǒng)（15）可以寫成矩陣形式：

定理4［25］是能控的，當(dāng)且僅當(dāng)以下2個(gè)條件同時(shí)成立：

1）（L，M）是能控的；

2）對于矩陣L的每一個(gè)特征值λ，矩陣對（A－λCK，B）都是可控的。

證明 （必要性）只證明矩陣（L，M）能控的必要條件，（A－λCK，B）能控的必要條件可以用相似的方法來證明。假設(shè)（L，M）是不能控的，則存在非零向量x∈Rn使得xTL＝λxT和xTM＝0成立。令（θ，y）∈C×Cp是矩陣（A－λCK，B）的左特征向量，那么

由xTL＝λxT，可得xTL／λ＝xT，即L／λ＝In。所以式（18）可轉(zhuǎn)化成1／λ｛L?（A－λCK）｝＝1／λ｛L?A－λL?CK｝＝In?A－L?CK＝L＾。由引理2，（θ，x?y）是L＾的一個(gè)左特征向量，則有

式中：λi是矩陣L的特征值。引入2個(gè)矩陣L＾和M～：

和

1）（UTM）s＝0，也就是說（L，M）是不能控的；

2）假如（UTM）s≠0，那么（A－λsCK，B）是不能控的。

因此矛盾，故結(jié)論成立，定理證明完畢。

注釋4 定理4的證明比較復(fù)雜，是一個(gè)新的證明方法，并且有一定的參考價(jià)值。

3 絕對協(xié)議下多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

3．1 一階同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

采用文獻(xiàn)［26］的多智能體網(wǎng)絡(luò)系統(tǒng)模型，它由廣播信號控制：

式中：xi表示智能體i的狀態(tài)，Ni＝｛j｜vi～vj；j≠i｝是節(jié)點(diǎn)vi的鄰居集，u是控制輸入。多智能體系統(tǒng)（20）的所有智能體都接受相同的控制信號，即u，稱這個(gè)信號為廣播信號。

系統(tǒng)（20）可以寫成如矩陣形式如下：

式中：A∈Rn×n為多智能體系統(tǒng)的鄰接矩陣，b＝［1 1 … 1］T∈Rn。

命題5［13］當(dāng)且僅當(dāng)以下2個(gè)條件同時(shí)成立，系統(tǒng)（21）是能控的。

1）矩陣A的特征值各不相同；

2）A的特征向量都不與b正交。

注釋5 命題5證明過程見文獻(xiàn)［13］。但是命題5只要滿足條件2）系統(tǒng)就是能控的，即條件2）是系統(tǒng)能控的充要條件，條件1）是系統(tǒng)能控的必要條件。

定理5 當(dāng)且僅當(dāng)矩陣A的所有特征向量都不正交于b，則系統(tǒng)（21）是能控的，并且如果系統(tǒng)（21）是能控的，那么矩陣A的特征值各不相同。

證明 假設(shè)向量v是矩陣A的特征向量，在PBH判據(jù)的條件下，如果系統(tǒng)（21）是能控的，那么rank（λiI－A，b）＝n成立。將PBH判據(jù)和對稱的狀態(tài)矩陣結(jié)合起來，如果系統(tǒng)是不能控的，那么矩陣A存在一個(gè)特征向量使得（λiI－A，b）vT＝0成立，則有

簡化成

因此，要使系統(tǒng)實(shí)現(xiàn)全控，A的所有特征向量不能與b正交，也就是說，如果矩陣A存在特征向量與b垂直，則系統(tǒng)（21）是不能控的。所以矩陣A的所有特征向量都不正交于b是系統(tǒng)（21）能控的充要條件。另一方面，A是一個(gè)實(shí)對稱矩陣，因此存在矩陣U使得A＝UDUT成立［33］，U是A的特征向量，那么

向量vi是特征值λi所對應(yīng)的特征向量，即v＝（v1，v2，…，vn）。由于U是非奇異矩陣，所以它不影響［（λiI－D）UTUTb］的秩，只需考慮［（λiI－D）UTUTb］是否滿秩。將[(λiI－D)UTUTb]展開：

從式（22）可以看出，要使系統(tǒng)（21）是能控的，則矩陣A的所有特征值各不相同。

3．2 高階異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性

給定多智能體系統(tǒng)模型：式中：xi∈Rd，ci∈R，F(xiàn)∈Rd×d，B∈Rd×m，和ui∈Rm。cFx表示異質(zhì)多智能體系統(tǒng)中節(jié)點(diǎn)i之間的動態(tài)ii關(guān)系。如果輸入ui＝0，那么智能體i就是跟隨者，反之是領(lǐng)航者。

式中：C＝diag（c1，c2，…，cn），A∈Rn×n是系統(tǒng)的鄰接矩陣。如果前q個(gè)智能體是領(lǐng)航者，那么Λ＝

定理6 假設(shè)F是對稱的，如果系統(tǒng)（24）是能控的，那么必須同時(shí)滿足以下2個(gè)條件：

1）［F B］是一個(gè)能控矩陣對；

2）矩陣（C＋A）不存在前q個(gè)元素都是零元素的左特征向量。

證明 假設(shè)系統(tǒng)（24）是不能控的，根據(jù)PBH判據(jù)，（C＋A）?F就存在左特征向量v使得vT（Λ?B）＝0成立。根據(jù)引理2，矩陣（C＋A）和矩陣F分別存在特征向量v1和v2使得P＝v1?v2和（vT1?vT2）（In?B）≠0成立，那么

當(dāng)且僅當(dāng)以下2個(gè)條件同時(shí)滿足時(shí)，式（25）成立。

顯然，定理6成立。

4 結(jié)束語

本文探究了多智能體網(wǎng)絡(luò)系統(tǒng)的能控性問題，分別在相對協(xié)議和絕對協(xié)議下總結(jié)了多智能體網(wǎng)絡(luò)系統(tǒng)的部分模型和能控性的線性代數(shù)條件。相對協(xié)議下，主要在Leader?Follower模型下利用已有的能控性代數(shù)條件對一階系統(tǒng)和高階系統(tǒng)的能控性代數(shù)條件進(jìn)行了總結(jié)和改進(jìn)，并且還總結(jié)了一般多智能體網(wǎng)絡(luò)系統(tǒng)模型下能控性的充分必要條件。在絕對協(xié)議下，研究了廣播信號下能控性的充分必要條件，使能控性的充要條件得到了簡化。此外，本文不僅討論了同質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性，還討論了異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性問題。由于自然現(xiàn)象和實(shí)際應(yīng)用中，不同生物群體之間動力學(xué)具有較大的差別，異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)的能控性問題是未來研究的一個(gè)重要方向，所以本文對異質(zhì)多智能體網(wǎng)絡(luò)系統(tǒng)能控性研究結(jié)果也具有很大的實(shí)際意義。

［1］LIM H，KANG Y，KIM J，et al．Formation control of leader following unmanned ground vehicles using nonlinear model predictive control［C］／／IEEE／ASME International Confer?ence on Advanced Intelligent Mechatronics．Singapore，2009：945?950．

［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］FAX J A．Optimal and cooperative control of vehicle forma?tions［M］．Pasadena：California Institute Technology，2001：1?11．

［4］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．

［5］劉金琨，爾聯(lián)潔．多智能體技術(shù)應(yīng)用綜述［J］．控制與決策，2001，16（2）：133?140，180．LIU Jinkun，ER Lianjie．Overview of application of multia?gent technology［J］．Control and Decision，2001，16（2）：133?140，180．

［6］FAX J A，MURRAY R M．Information flow and cooperative control of vehicle formations［J］．IEEE Transactions on Au?tomatic Control，2004，49（9）：1465?1476．

［7］OGREN P，F(xiàn)IORELLI E，LEONARD N E．Cooperative control of mobile sensor networks：adaptive gradient climb?ing in a distributed environment［J］．IEEE Transactions on Automatic Control，2004，49（8）：1292?1302．

［8］MU S M，CHU T G，WANG L．Coordinated collective mo?tion in a motile particle group with a leader［J］．Physica A：Statistical Mechanics and its Applications，2005，351（2?4）：211?226．

［9］HONG Y G，HU J P，GAO L X．Tracking control for multi?agent consensus with an active leader and variable topology［J］．Automatica，2006，42（7）：1177?1182．

［10］SHI H，WANG L，CHU T G．Virtual leader approach to coordinated control of multiple mobile agents with asym?metric interactions［J］．Physica D：Nonlinear Phenomena，2006，213（1）：51?65．

［11］LANE D M，MCFADZEAN A G．Distributed problem sol?ving and real?time mechanisms in robot architectures［J］．Engineering Applications of Artificial Intelligence，1994，7（2）：105?117．

［12］KALMAN R E．Mathematical description of linear dynami? cal systems［J］．Journal of the Society for Industrial and Applied Mathematics Series A：Control，1963，1（2）：152?192．

［13］TANNER H G．On the controllability of nearest neighbor interconnections［C］／／Proceedings of the 43rd IEEE Con?ference on Decision and Control．Atlantis，Paradise Island，Bahamas，2004：2467?2472．

［14］RAHMANI A，MESBAHI M．On the controlled agreement problem［C］／／Proceedings of the 2006 American Control Conference．Minneapolis，USA，2006：1376?1381．

［15］RAHMANI A，JI M，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．

［16］JI M，EGERSTEDT M．A graph?theoretic characterization of controllability for multi?agent systems［C］／／Proceedings of the IEEE American Control Conference．New York，USA，2007：4588?4593．

［17］JI Z J，WANG Z D，LIN H，et al．Interconnection topolo?gies for multi?agent coordination under leader?follower framework［J］．Automatica，2009，45（12）：2857?2863．

［18］DAVISON E J．Connectability and structural controllability of composite systems［J］．Automatica，1977，13（2）：109?123．

［19］XIANG L Y，ZHU J J H，CHE F，et al．Controllability of weighted and directed networks with nonidentical node dy?namics［OL／EB］．［2014?01?20］．http：／／www．hindawi．com／journals／mpe／2013／405034．

［20］王曉曉，紀(jì)志堅(jiān)．廣播信號下非一致多智能體系統(tǒng)的能控性［J］．智能系統(tǒng)學(xué)報(bào)，2014，9（4）：401?406．WANG Xiaoxiao，JI Zhijian．Controllability of non?identi?cal multi?agent systems under a broadcasting control signal［J］．CAAI Transactions on Intelligent Systems，2014，9（4）：401?406．

［21］CAI N，CAO J W，LIU M H，et al．On controllability problems of high?order dynamical multi?agent systems［J］．Arabian Journal for Science and Engineering，2014，39（5）：4261?4267．

［22］LIU B，CHU T G，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．

［23］JI Z J，WANG Z D，LIN H，et al．Controllability of multi?agent systems with time?delay in state and switching topolo?gy［J］．International Journal of Control，2010，83（2）：371?386．

［24］ZHANG S，CAO M，CAMLIBEL M K．Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents［J］．IEEE Transactions on Automatic Con?trol，2014，59（3）：745?750．

［25］LIU B，SU H S，LI R，et al．Switching controllability of discrete?time multi?agent systems with multiple leaders and time?delays［J］．Applied Mathematics and Computation，2014，228：571?588．

［26］YOON M G，ROWLINSON P，CVETKOVI D，et al．Con?trollability of multi?agent dynamical systems with a broad?casting control signal［J］．Asian Journal of Control，2014，16（4）：1066?1072．

［27］NI W，WANG X L，XIONG C．Consensus controllability，observability and robust design for leader?following linear multi?agent systems［J］．Automatica，2013，49（7）：2199?2205．

［28］Yoon M G．Single agent control for cyclic consensus sys?tems［J］．International Journal of Control，Automation and Systems，2013，11（2）：243?249．

［29］GODSIL C，ROYLE G．Algebraic Graph Theory［M］．New York：Springer，2001：163?171．

［30］CAI N，ZHONG Y S．Formation controllability of high?or?der linear time?invariant swarm systems［J］．IET Control Theory＆Application，2010，4（4）：646?654．

［31］CHEN C T．Linear system theory and design［M］．New York：Oxford University Press，1999：6．

［32］CAI N，CAO J W，KHAN M J．A controllability synthesis problem for dynamic multi?agent systems with linear high?order protocol［J］．International Journal of Control，Auto?mation and Systems，2014，12（6）：1366?1371．

［33］HORN R A，Johnson C R．Matrix analysis［M］．Cam?bridge：Cambridge University Press，1985：11?14．

Algebraic conditions for the controllability of multi?agent systems

DONG Jie，JI Zhijian，WANG Xiaoxiao

（School of Automation Engineering，Qingdao University，Qingdao 266071，China）

Controllability is a key issue in the study of multi?agent systems，especially structural controllability and exact controllability．This paper summarizes the system model and the algebraic conditions for controllability of multi?agent systems．Based on relative and absolute protocols，the algebraic conditions are analyzed systematically for multi?agent system controllability，using graph theory and matrix theory．Going from homogeneous dynamical multi?agent systems to heterogeneous dynamical multi?agent systems，the existing models and algebraic conditions for multi?agent systems are sorted out．The algebraic conditions for controllability of multi?agent systems are im?proved，and some new algebraic conditions are proposed．The improvement of algebraic controllability conditions for multi?agent system simplifies the calculation greatly．

multi?agent system；structure controllability；exact controllability；relative protocol；absolute protocol；algebraic condition；graph theory；matrix theory

董潔，女，1990年生，碩士研究生，主要研究方向?yàn)槎嘀悄荏w系統(tǒng)。

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

王曉曉，女，1989年生，碩士研究生，主要研究方向?yàn)槎嘀悄荏w系統(tǒng)。

TP273

A

1673?4785（2015）05?0747?08

10．11992／tis．201411030

http：／／www．cnki．net／kcms／detail／23．1538．tp．20150930．1556．008．html

董潔，紀(jì)志堅(jiān)，王曉曉．多智能體網(wǎng)絡(luò)系統(tǒng)的能控性代數(shù)條件［J］．智能系統(tǒng)學(xué)報(bào)，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．

2014?11?25．

日期：2015?09?30．

國家自然科學(xué)基金資助項(xiàng)目（61374062）；山東省杰出青年科學(xué)基金資助項(xiàng)目（JQ201419）．

紀(jì)志堅(jiān)．E?mail：jizhijian＠pku．org．cn．