二階鄰居協議下多智能體系統能控能觀性保持

王康，紀志堅，晁永翠

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

二階鄰居協議下多智能體系統能控能觀性保持

王康，紀志堅，晁永翠

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

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

多智能體系統；二階鄰居協議；時變拓撲結構；結構能控性；能控性；能觀測性；圖論

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

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

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

1 預備知識

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

拉普拉斯矩陣具有如下性質：

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

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

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

2 系統模型

(1)

(2)

(3)

式中：wij為實際圖中節點之間的權值，wik為虛擬圖節點之間權值。

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

(4)

令wij=wik=1，則

所以系統可以寫為如下這種形式：

(5)

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

證明 構造一個李雅普諾夫函數：

對此函數求導可得

結合式(5)得

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

證畢。

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

(6)

因此

(7)

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

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

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

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

(8)

(9)

式中：矩陣F∈RNF×NF代表跟隨者之間的傳遞關系，矩陣B∈RNL×NL代表領航者之間的傳遞關系，矩陣r∈RNF×NL代表領航者和跟隨者之間的傳遞關系。

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

3 實例分析

對于一個具有5個節點的拓撲圖，我們取第2個和第4個節點作為領航者，如圖3。

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

所以

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

(10)

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

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

(11)

可寫為

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

(12)

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

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

4 對結構能控性維持策略的研究

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

4.1 結構能控性

定義1 對于一個無權重的多智能體系統，如果能夠找到至少一組權重，使得相應的系統變為能控，那么稱這個多智能體系統是結構能控的。

在文章[18]中，可以知道多智能體系統是結構能控的，當且僅當系統的拓撲圖是連通的，即代數連通度λ2>0?？梢越柚Y構能控性的概念，通過給拓撲圖的邊賦予相應的權值，使本來不能控的系統變為能控，以達到對多智能體系統的狀態要求。

4.2 實例分析

所以基于二階鄰居協議下多智能體系統的拉普拉斯矩陣為

圖4 權圖Fig.4 Weight graph

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

根據結構能控性的定義和文獻[18]，可得到圖5所示的多智能體系統能控性和結構能控性的關系:

圖5 多智能體系統能控性和結構能控性的關系Fig.5 Relationship between controllability and structural controllability of multi-agent system

3.3 結構能控性的保持方法

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

圖6 時變拓撲結構Fig.6 Time varying topology

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

(13)

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

(14)

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

(15)

2)能量函數是非負的。

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

(16)

所以網絡系統的動態方程可以修改為式(7)形式：

(17)

(18)

(19)

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

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

根據式(19)，并由

可得下列不等式：

因此，如果不等式

(20)

(21)

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

(22)

(23)

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

根據能量函數的圖像可以進一步理解上述結論。能量函數的圖像如圖7所示。

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

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

4 結束語

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

[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]晁永翠, 紀志堅, 王耀威, 等. 復雜網絡在路形拓撲結構下可控的充要條件[J]. 智能系統學報, 2015, 10(4): 577-582.CHAOYongcui,JIZhijian,WANGYaowei,etal.Necessaryandsufficientconditionsforthecontrollabilityofcomplexnetworkswithpathtopology[J].CAAItransactionsonintelligentsystems, 2015, 10(4): 577-582.

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

[8]王曉曉, 紀志堅. 廣播信號下非一致多智能體系統的能控性[J]. 智能系統學報, 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年生，碩士研究生，主要研究方向為多智能體系統的能控性。

紀志堅，男，1973年生，教授，博士生導師，博士，主要研究方向為群體系統動力學與協調控制、復雜網絡、切換動力系統的分析與控制、系統生物以及基于網絡的控制系統。先后主持國家自然科學基金項目3項、山東省杰出青年科學基金項目1項，山東省杰出青年基金獲得者。先后參與多項國家自然科學基金及“973”和“863”項目的研究。發表學術論文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

王康，紀志堅，晁永翠. 二階鄰居協議下多智能體系統能控能觀性保持[J]. 智能系統學報， 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.