王康，紀志堅，晁永翠

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

二階鄰居協(xié)議下多智能體系統(tǒng)能控能觀性保持

王康，紀志堅，晁永翠

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

為了研究多智能體系統(tǒng)的一致性特點及能控、能觀性保持策略，分析了具有時變拓撲結(jié)構(gòu)的多智能體系統(tǒng)在一階鄰居協(xié)議和二階鄰居協(xié)議下的一致性速度，針對拓撲結(jié)構(gòu)的特殊性，利用結(jié)構(gòu)能控性性質(zhì)和拉普拉斯矩陣第二小特征值與一致性速度之間存在的關(guān)系設計出一種使能控性和能觀測性保持的控制策略。此外，得出多智能體系統(tǒng)在二階鄰居協(xié)議下，具有更快的一致性速度的結(jié)論。文中2個主要定理分別通過算例和仿真進行驗證，算例和仿真結(jié)果與定理結(jié)論一致。

多智能體系統(tǒng)；二階鄰居協(xié)議；時變拓撲結(jié)構(gòu)；結(jié)構(gòu)能控性；能控性；能觀測性；圖論

近些年，隨著計算機網(wǎng)絡系統(tǒng)、無人機、衛(wèi)星系統(tǒng)的高速發(fā)展，關(guān)于多智能體系統(tǒng)的研究也成為人們研究的熱點。由于多智能體系統(tǒng)間各智能體的協(xié)調(diào)控制能實現(xiàn)我們所需要的復雜運動，因此有關(guān)多智能體系統(tǒng)的研究具有十分重要的意義。在研究多智能體系統(tǒng)時，我們利用代數(shù)圖論[1]的知識，把多智能體系統(tǒng)用拓撲圖表示。其中，拓撲圖的節(jié)點代表各智能體，拓撲圖的邊代表各智能體間的連接關(guān)系。在研究過程中，產(chǎn)生了兩個重大的結(jié)果，能控性和一致性。多智能系統(tǒng)的能控性首先是由Tanner[2]提出來的，通過利用經(jīng)典能控性概念，把拉普拉斯矩陣分塊為子矩陣，得到能控性判據(jù)。近年來，多智能體系統(tǒng)的能控性研究受到國內(nèi)外科研工作者的廣泛關(guān)注[3-8]。然而，在能控性保持方面的研究工作則剛剛起步，目前主要是以L.Sabattini[9-12]的研究為主。

一致性問題的研究可以追溯到20 世紀70 年代的管理科學和統(tǒng)計領(lǐng)域[13-14]。目前關(guān)于一致性問題的研究很大程度上以T．Vicsek[15]提出的Vicsek模型為基礎。多智能體系統(tǒng)的一致性主要是研究如何基于多智能體系統(tǒng)中個體之間有限的信息交換，實現(xiàn)所有智能體的某個或某些狀態(tài)量趨于相等的問題。對一致性協(xié)議的研究能讓我們清楚地了解到智能體之間信息交換的過程。Olfati-Saber[16]提出了解決多智能體網(wǎng)絡系統(tǒng)的一致性協(xié)議的理論框架,并且得到在連續(xù)時間一階多智能體系統(tǒng)中，當通信拓撲結(jié)構(gòu)表示的圖為無向圖時，多智能體系統(tǒng)的一致速度取決于圖的拉普拉斯矩陣的第二小特征值的結(jié)論，即一致性速度與拓撲圖的拉普拉斯矩陣第二小特征值λ2之間存在正相關(guān)的關(guān)系。同時在文獻[1,16-18]中，對第二小特征值λ2的物理意義也做出了說明，并指出了λ2不僅可以度量一致性速度，也可以表示智能體系統(tǒng)的穩(wěn)定性。

在一致性問題中，以一階鄰居協(xié)議的研究最為普遍，即考慮智能體的鄰居信息。一階鄰居協(xié)議具有適用面廣泛、作用原理簡單的優(yōu)點。然而由于多智能體系統(tǒng)越來越復雜，一階鄰居協(xié)議的信息交換方式已經(jīng)不能滿足我們的需要，例如在復雜的全球衛(wèi)星網(wǎng)絡(GPS)中，采用一階鄰居協(xié)議顯然會使信息的交換效率低下，整個衛(wèi)星系統(tǒng)協(xié)同控制效果并不好。而采用二階鄰居協(xié)議，由于系統(tǒng)收斂性比前者更好，這就為復雜衛(wèi)星網(wǎng)絡系統(tǒng)的運轉(zhuǎn)提供更高效的保障。因此，對二階鄰居協(xié)議的研究就顯得尤為重要。和一階鄰居協(xié)議相比，二階鄰居協(xié)議不僅利用智能體鄰居的信息，還利用其二階鄰居的信息，而系統(tǒng)實際的通信拓撲結(jié)構(gòu)并未發(fā)生變化。本文通過對上述兩種一致性協(xié)議進行比較，得出了多智能體系統(tǒng)采用二階鄰居協(xié)議時，多智能體系統(tǒng)中各智能體達到一致性速度更快的結(jié)論。同時，針對現(xiàn)實中具有時變拓撲結(jié)構(gòu)的系統(tǒng)，為了使網(wǎng)絡系統(tǒng)能夠更穩(wěn)定運轉(zhuǎn)，避免受外部環(huán)境的影響，以達到人們需要的工作狀態(tài)，這就對系統(tǒng)的能控性和能觀測性提出了很大要求，就需要領(lǐng)航者對跟隨者的控制能力一直保持下去。本文通過借助結(jié)構(gòu)能控性的概念和性質(zhì)[19-20]，設計了一種全新的控制策略，使多智能體系統(tǒng)的能控性和能觀測性得到保持。這對于易受外界環(huán)境干擾的多智能體系統(tǒng)的研究具有較高的理論價值。

1 預備知識

拉普拉斯矩陣是表示拓撲圖節(jié)點與邊關(guān)系的一種矩陣,也是我們研究多智能體系統(tǒng)需要借助的一個重要概念。對于一個包含N個節(jié)點的無向圖G, 其拉普拉斯矩陣定義為L=D-A，拉普拉斯矩陣還可以表示為L=ITI，其中矩陣I=[iij]表示把無向圖G規(guī)定為具有任意方向有向圖的關(guān)聯(lián)矩陣，元素

拉普拉斯矩陣具有如下性質(zhì)：

1)對于一個所有元素均為1的列向量，L與該列向量的乘積為零矩陣;

2)令λ1,λ2,…,λN為拉普拉斯矩陣的特征值，則0=λ1≤λ2≤…≤λN;

3)第1個非零特征值(第2個最小的特征值λ2) 稱為代數(shù)連通度。

2 系統(tǒng)模型

(1)

(2)

(3)

式中：wij為實際圖中節(jié)點之間的權(quán)值，wik為虛擬圖節(jié)點之間權(quán)值。

在式(3)中，每個智能體在獲取自己的狀態(tài)信息時不僅利用其鄰居的狀態(tài)信息，還利用其二階鄰居的狀態(tài)信息。由于智能體i與其二階鄰居之間并不存在實際的通信鏈路，所以智能體i的二階鄰居的信息由智能體i的鄰居間接傳遞給i。由式(1)和式(3)，系統(tǒng)中每個智能體的狀態(tài)可以表示為

(4)

令wij=wik=1，則

所以系統(tǒng)可以寫為如下這種形式：

(5)

引理1[16]拉普拉斯矩陣Lc的第二小特征值λ2可用于表征系統(tǒng)一致收斂的速度。

證明 構(gòu)造一個李雅普諾夫函數(shù)：

對此函數(shù)求導可得

結(jié)合式(5)得

因為圖G是無向連通圖，所以[16]：

證畢。

定理1 對于一階多智能體系統(tǒng)(1)，它在二階鄰居協(xié)議(3)下達到一致性的速度比在一階鄰居協(xié)議(2)下更快。

(6)

因此

(7)

顯然，式(7)大于式(6)，即多智能體系統(tǒng)在二階鄰居協(xié)議下達到一致性的速度比在一階鄰居協(xié)議下更快。證畢。

圖1 一階鄰居協(xié)議下各智能體的狀態(tài)軌跡Fig.1 The state trajectory of each agent under the first-order neighbors protocol

圖2 二階鄰居協(xié)議下各智能體的狀態(tài)軌跡Fig.2 The state trajectory of each agent under the second-order neighbors protocol

通過對圖1和圖2進行比較分析，我們發(fā)現(xiàn)多智能體系統(tǒng)(1)在二階鄰居協(xié)議(3)下的收斂性更好，即在二階鄰居協(xié)議(3)下各智能體達到一致性的速度要比在一階鄰居協(xié)議(2)下更快。因此，在設計多智能體系統(tǒng)時，盡可能地選用基于二階鄰居的一致性協(xié)議，會使系統(tǒng)更快速地達到一致性。

(8)

(9)

式中：矩陣F∈RNF×NF代表跟隨者之間的傳遞關(guān)系，矩陣B∈RNL×NL代表領(lǐng)航者之間的傳遞關(guān)系，矩陣r∈RNF×NL代表領(lǐng)航者和跟隨者之間的傳遞關(guān)系。

當在系統(tǒng)中選取任意多個節(jié)點為領(lǐng)航者時，假設系統(tǒng)中有NL個領(lǐng)航者，我們規(guī)定矩陣r取自矩陣Lc中這NL個節(jié)點所在的列向量減去這NL個節(jié)點所在行向量和列向量的共同元素后剩余元素所組成的NF×NL矩陣。矩陣-F為合并圖拉普拉斯矩陣Lc減去這NL個節(jié)點所在行和所在列后剩下的NF×NF矩陣。

3 實例分析

對于一個具有5個節(jié)點的拓撲圖，我們?nèi)〉?個和第4個節(jié)點作為領(lǐng)航者，如圖3。

圖3 具有5個節(jié)點的拓撲圖Fig.3 Topology with 5 nodes

所以

假設領(lǐng)航者能夠獲得輸出向量y，且y∈RNL×1，那么，網(wǎng)絡系統(tǒng)的動態(tài)方程可以寫為文獻[9]所描述的那樣：

(10)

定理2 若合并圖的拉普拉斯矩陣Lc的子矩陣F所對應的正交特征向量組成的矩陣U不與向量r正交，則此拓撲圖所對應的多智能體系統(tǒng)既是能控的，又是能觀測的。

證明 根據(jù)式(10)，可得能控性判別矩陣：

(11)

可寫為

因為U是非奇異矩陣，若使能控性判別矩陣C滿秩，只需要保證矩陣

(12)

同理，若使能觀性判別矩陣O滿秩,則也需使UTr≠0。也就是說，若多智能體系統(tǒng)是能控的，那么它也是能觀測的。證畢。

綜上所述，在二階鄰居協(xié)議下，多智能體系統(tǒng)既能控又能觀測的條件為：矩陣F所對應的特征向量U不與向量r正交。

4 對結(jié)構(gòu)能控性維持策略的研究

在基于二階鄰居協(xié)議(3)下具有時變拓撲結(jié)構(gòu)的多智能體系統(tǒng)(1)隨時間變化過程中，各節(jié)點之間邊的條數(shù)和距離可能發(fā)生變化，進而影響系統(tǒng)合并圖的拉普拉斯矩陣Lc，并根據(jù)定理2和文獻[1]，在某一時刻，可能也會導致代數(shù)連通度λ2發(fā)生改變以及使得系統(tǒng)不能控。因此，為了避免具有時變拓撲結(jié)構(gòu)的多智能體系統(tǒng)(1)的能控性發(fā)生改變，我們引入了結(jié)構(gòu)能控性的概念。

4.1 結(jié)構(gòu)能控性

定義1 對于一個無權(quán)重的多智能體系統(tǒng)，如果能夠找到至少一組權(quán)重，使得相應的系統(tǒng)變?yōu)槟芸兀敲捶Q這個多智能體系統(tǒng)是結(jié)構(gòu)能控的。

在文章[18]中，可以知道多智能體系統(tǒng)是結(jié)構(gòu)能控的，當且僅當系統(tǒng)的拓撲圖是連通的，即代數(shù)連通度λ2>0。可以借助結(jié)構(gòu)能控性的概念，通過給拓撲圖的邊賦予相應的權(quán)值，使本來不能控的系統(tǒng)變?yōu)槟芸?，以達到對多智能體系統(tǒng)的狀態(tài)要求。

4.2 實例分析

所以基于二階鄰居協(xié)議下多智能體系統(tǒng)的拉普拉斯矩陣為

圖4 權(quán)圖Fig.4 Weight graph

由式(11)得，能控性判別矩陣為

根據(jù)結(jié)構(gòu)能控性的定義和文獻[18]，可得到圖5所示的多智能體系統(tǒng)能控性和結(jié)構(gòu)能控性的關(guān)系:

圖5 多智能體系統(tǒng)能控性和結(jié)構(gòu)能控性的關(guān)系Fig.5 Relationship between controllability and structural controllability of multi-agent system

3.3 結(jié)構(gòu)能控性的保持方法

在本文中，具有時變拓撲結(jié)構(gòu)的多智能體系統(tǒng)(1)，隨著時間的變化，可能會導致已連通的節(jié)點之間的距離增加，從而使連通強度改變，導致系統(tǒng)的能控性發(fā)生變化。我們的目的只考慮如何使已連通節(jié)點間的連通強度不隨時間消失，而關(guān)于不連通的節(jié)點是否會隨時間而靠近從而連通的情況則不進行相關(guān)分析。如圖6所示，其中(a)為網(wǎng)絡系統(tǒng)的初始位置，設點1為領(lǐng)航者，并給它注入某一控制輸入，則各智能體在到達一致狀態(tài)的過程中，顯然由(b)可看出，由于第2點和第3點的距離變大，致使兩點的連接強度減弱，這顯然不符合多智能體系統(tǒng)的設計要求。

圖6 時變拓撲結(jié)構(gòu)Fig.6 Time varying topology

因此，為了避免上述情況的出現(xiàn)，在本章節(jié)提出了一個控制策略，如式(13)所示：

(13)

時，兩個智能體間有通信聯(lián)系，節(jié)點xi、xj之間存在邊eij，此時wij>0。 那么

(14)

式中：κ滿足e-R2/κ2=ω，ω是一個比0大的常數(shù)。當wij=0時，說明智能體xi、xj之間沒有通信聯(lián)系，即不存在邊eij。同理，虛擬圖gv的權(quán)值：

(15)

2)能量函數(shù)是非負的。

因此，可以寫出能量函數(shù)的表達式為

(16)

所以網(wǎng)絡系統(tǒng)的動態(tài)方程可以修改為式(7)形式：

(17)

(18)

(19)

能量函數(shù)對時間的導數(shù)可以寫為以下形式：

由式(13)和式(18)可得，能量函數(shù)的導數(shù)也可寫為

根據(jù)式(19)，并由

可得下列不等式：

因此，如果不等式

(20)

(21)

那么，式(20)所描述的不等式就可以寫為

(22)

(23)

因此由上述結(jié)論可知：如果在初始時刻拓撲圖連通，那么隨著時間的變化，即使拓撲圖的結(jié)構(gòu)發(fā)生變化，其所對應的拉普拉斯矩陣的第2個特征值λ2也會永遠大于零。那么多智能體系統(tǒng)的結(jié)構(gòu)能控性得到了保持。證畢。

根據(jù)能量函數(shù)的圖像可以進一步理解上述結(jié)論。能量函數(shù)的圖像如圖7所示。

圖7 能量函數(shù)Ε的圖像Fig.7 Image of energy function E

由能量函數(shù)的圖像可知，如果在初始時刻給具有結(jié)構(gòu)能控性的系統(tǒng)賦予一組權(quán)重不為1的權(quán)值，那么不僅說明λ2恒大于零，系統(tǒng)結(jié)構(gòu)能控性得到保持，還說明拓撲圖恒連通，任意節(jié)點都會與其他至少一個節(jié)點相連接。即‖xi-xj‖≤R，存在權(quán)值wij。又因為權(quán)值wij=1時，由式(14)和式(15)得，‖xi-xj‖=0，顯然無意義。因此權(quán)值wij≠1，所以結(jié)構(gòu)能控性得到保持的系統(tǒng)必定存在一組邊的權(quán)值，且權(quán)值不為1。因此多智能體系統(tǒng)(1)具有能控性和能觀測性。

4 結(jié)束語

由于二階鄰居協(xié)議式(3)在到達一致性的速度上比一階鄰居協(xié)議式(2)更有優(yōu)勢，所以本文對二階鄰居協(xié)議式(3)下的多智能體方面進行了研究，并對相關(guān)定理通過算例進行驗證。而對于智能體與二階鄰居通信過程中可能會出現(xiàn)時滯的情況，這將是未來的一個重點研究的問題。本文對具有時變拓撲結(jié)構(gòu)的多智能體系統(tǒng)的一致性協(xié)議的選取和能控性保持方面的研究提供了一個方向和基礎。

[1]GODSILC,ROYLEG.Algebraicgraphtheory[M].NewYork:Springer, 2001.

[2]TANNERHG.Onthecontrollabilityofnearestneighborinterconnections[C]//Proceedingsofthe43rdIEEEConferenceondecisionandControl.Nassau, 2004, 3: 2467-2472.

[3]JIZhijian,LINHai,YUHaisheng.Protocolsdesignanduncontrollabletopologiesconstructionformulti-agentnetworks[J].IEEEtransactionsonautomaticcontrol, 2015, 60(3): 781-786.

[4]JIZhijian,LINHai,YUHaisheng.Leadersinmulti-agentcontrollabilityunderconsensusalgorithmandtreetopology[J].Systems&controlletters, 2012, 61(9): 918-925.

[5]JIZhijian,WANGZidong,LINHai,etal.Interconnectiontopologiesformulti-agentcoordinationunderleader-followerframework[J].Automatica, 2009, 45(12): 2857-2863.

[6]晁永翠, 紀志堅, 王耀威, 等. 復雜網(wǎng)絡在路形拓撲結(jié)構(gòu)下可控的充要條件[J]. 智能系統(tǒng)學報, 2015, 10(4): 577-582.CHAOYongcui,JIZhijian,WANGYaowei,etal.Necessaryandsufficientconditionsforthecontrollabilityofcomplexnetworkswithpathtopology[J].CAAItransactionsonintelligentsystems, 2015, 10(4): 577-582.

[7]董潔, 紀志堅, 王曉曉. 多智能體網(wǎng)絡系統(tǒng)的能控性代數(shù)條件[J]. 智能系統(tǒng)學報, 2015, 10(5): 747-754.DONGJie,JIZhijian,WANGXiaoxiao.Algebraicconditionsforthecontrollabilityofmulti-agentsystems[J].CAAItransactionsonintelligentsystems, 2015, 10(5): 747-754.

[8]王曉曉, 紀志堅. 廣播信號下非一致多智能體系統(tǒng)的能控性[J]. 智能系統(tǒng)學報, 2014, 9(4): 401-406.WANGXiaoxiao,JIZhijian.Controllabilityofnon-identicalmulti-agentsystemsunderabroadcastingcontrolsignal[J].CAAItransactionsonintelligentsystems, 2014, 9(4): 401-406.

[9]SABATTINIL,SECCHIC,FANTUZZIC.Controllabilityandobservabilitypreservationfornetworkedsystemswithtimevaryingtopologies[C]//Proceedingsofthe19thWorldCongressontheInternationalFederationofAutomaticControl.CapeTown,SouthAfrica, 2004: 1837-1842.

[10]SABATTINIL,CHOPRAN,SECCHIC.Ondecentralizedconnectivitymaintenanceformobileroboticsystems[C]//Proceedingsofthe2011 50thIEEEConferenceonDecisionandControlandEuropeanControlConference.Orlando,USA, 2011: 988-993.

[11]SABATTINIL,CHOPRAN,SECCHIC.Distributedcontrolofmulti-robotsystemswithglobalconnectivitymaintenance[C]//Proceedingsof2011IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.SanFrancisco,CA, 2011: 2321-2326.

[12]SABATTINIL,SECCHIC,COCETTIM,etal.Implementationofcoordinatedcomplexdynamicbehaviorsinmultirobotsystems[J].IEEEtransactionsonrobotics, 2015, 31(4): 1018-1032.

[13]DEGROOTMH.ReachingaConsensus[J].JournaloftheAmericanstatisticalassociation, 1974, 69(345): 118-121.

[14]CHATTERJEES,SENETAE.Towardsconsensus:someconvergencetheoremsonrepeatedaveraging[J].Journalofappliedprobability, 1977, 14(1): 89-97.

[15]VICSEKT,CZIRóKA,BEN-JACOBE,etal.Noveltypeofphasetransitioninasystemofself-drivenparticles[J].Physicalreviewletters, 1995, 75(6): 1226-1229.

[16]OLFATI-SABERR,MURRAYRM.Consensusproblemsinnetworksofagentswithswitchingtopologyandtime-delays[J].IEEEtransactionsonautomaticcontrol, 2004, 49(9): 1520-1533.

[17]RENWei,BEARDRW,MCLAINTW.Coordinationvariablesandconsensusbuildinginmultiplevehiclesystems[M]//KUMARV,LEONARDN,MORSEAS.CooperativeControl.BerlinHeidelberg:Springer, 2005: 171-188.

[18]FIEDLERM.Algebraicconnectivityofgraphs[J].Czechoslovakmathematicaljournal, 1973, 23(2): 298-305.

[19]ZAMANIM,LINHai.Structuralcontrollabilityofmulti-agentsystems[C]//Proceedingsof2009AmericanControlConference.St.Louis,USA, 2009: 5743-5748.

[20]LINCT.Structuralcontrollability[J].IEEEtransactionsonautomaticcontrol, 1974, 19(3): 201-208.

[21]EGERSTEDTM,MARTINIS,CAOMing,etal.Interactingwithnetworks:howdoesstructurerelatetocontrollabilityinsingle-leader,consensusnetworks[J].IEEEcontrolsystems, 2012, 32(4): 66-73.

王康，男，1992年生，碩士研究生，主要研究方向為多智能體系統(tǒng)的能控性。

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

A control strategy for maitaining controllability and observability ofa multi-agent system with the second-order neighborhood protocol

WANG Kang， JI Zhijian， CHAO Yongcui

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

In order to study the characteristics of the consensus， controllability and observability of multi-agent systems, we analyze the consensus speed of a multi-agent system with time-varying topologies under first-order and second-order neighborhood protocols. By utilizing the properties of the structural controllability and the relationship between the second-smallest eigenvalue of the Laplacian matrix and the consensus speed, we designed a control strategy to maintain both controllability and observability. In addition, we concluded that the multi-agent system had a faster consensus speed under the second-order neighborhood protocol. Using examples and simulations, we verified the two main theorems proposed in this paper, with our observed results in full agreement with the conclusions of our theoretical analysis.

multi-agent system; second-order neighborhood protocol; time varying topologies; structural controllability; controllability; observability; graph theory

2016-01-13.

日期：2017-01-11.

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

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

10.11992/tis.201601022

http://www.cnki.net/kcms/detail/23.1538.tp.20170111.1705.012.html

TP13

A

1673-4785(2017)02-0213-08

王康，紀志堅，晁永翠. 二階鄰居協(xié)議下多智能體系統(tǒng)能控能觀性保持[J]. 智能系統(tǒng)學報， 2017, 12(2): 213-220.

英文引用格式：WANG Kang，JI Zhijian，CHAO Yongcui. A control strategy for maitaining controllability and observability of a multi-agent system with the second-order neighborhood protocol[J]. CAAI transactions on intelligent systems, 2017, 12(2): 213-220.