離散多智能體系統(tǒng)分組一致性分析

林瑜陽， 李鐘慎

(華僑大學(xué) 機電及自動化學(xué)院， 福建 廈門 361021)

離散多智能體系統(tǒng)分組一致性分析

林瑜陽， 李鐘慎

(華僑大學(xué) 機電及自動化學(xué)院， 福建 廈門 361021)

在有向拓撲結(jié)構(gòu)下，研究離散多智能體系統(tǒng)的分組一致問題，提出無入度平衡假設(shè)條件的控制協(xié)議設(shè)計方法.首先，根據(jù)系統(tǒng)模型，設(shè)計離散多智能體系統(tǒng)的分組一致控制協(xié)議.其次，利用代數(shù)圖論和矩陣論，分析并得到離散多智能體系統(tǒng)實現(xiàn)分組一致的充要條件.最后，仿真結(jié)果驗證了理論分析結(jié)論的正確性.數(shù)值仿真結(jié)果表明:系統(tǒng)實現(xiàn)分組一致僅要求有向圖Gn含有一個有向生成樹，不要求拓撲結(jié)構(gòu)滿足入度平衡條件.

多智能體系統(tǒng)； 離散時間系統(tǒng)； 入度平衡； 分組一致性

自然界中生物群體的群集現(xiàn)象，如螞蟻聚集、大雁編隊飛行等，均呈現(xiàn)出整體一致行為.多智能體一致性問題來源于自然界的群集現(xiàn)象，是指系統(tǒng)中所有個體通過局部間的彼此通信，最終狀態(tài)收斂至一個值.一致性問題的研究可揭示生物群集現(xiàn)象的內(nèi)在規(guī)律，解釋生物群體行為[1-2].同時，由于多智能體系統(tǒng)比單一系統(tǒng)更具有靈活性、經(jīng)濟性，其一致性的研究在無人機編隊控制、通信網(wǎng)絡(luò)擁塞控制、機器人設(shè)計和搜索優(yōu)化等領(lǐng)域得到廣泛地應(yīng)用[3-5].近年來，多位學(xué)者從智能體動態(tài)模型、通信拓撲和一致性協(xié)議等3個基本方面對一致性問題展開大量研究[6-10].考慮實際問題的復(fù)雜性，個體的最終狀態(tài)往往不能收斂至一個值.當(dāng)個體最終狀態(tài)收斂至多個值時，一致性問題轉(zhuǎn)化為分組一致問題，分組一致問題是一致性問題的推廣，在理論研究上也具有重要意義[11-18].然而，相關(guān)的研究均基于入度平衡假設(shè)條件展開，忽略了組間彼此影響.本文研究無入度平衡條件下離散多智能體系統(tǒng)的分組一致問題，提出分組一致控制策略，得到實現(xiàn)分組一致的充要條件，并通過數(shù)值仿真驗證所得結(jié)論的正確性.

1 預(yù)備知識與問題描述

考慮具有n個智能體的系統(tǒng)，智能體之間的通信拓撲可用有向圖G={V,E}表示.其中，節(jié)點集合V={v1,v2,…,vn}；邊集合E?V×V.節(jié)點vi的鄰居集合為Ni={vj∈V：(vi,vj)∈E}.圖G的鄰接矩陣A={ai,j}∈Rn×n.其中，矩陣元素ai,j為與有向邊(vi,vj)對應(yīng)的連接權(quán)重.當(dāng)(vi,vj)∈E時，ai,j>0；反之，ai,j=0.如果(vi,vj)∈E，則表示從節(jié)點vi有一條有向路徑指向節(jié)點vj，節(jié)點vi稱為父節(jié)點，節(jié)點vj稱為子節(jié)點.如果有向圖中除了一個節(jié)點(根節(jié)點)沒有父節(jié)點外，其余每個節(jié)點有且僅有一個父節(jié)點，且根節(jié)點可以通過一條有向路徑到達其余所有節(jié)點，則稱該圖為有向樹.當(dāng)一個有向圖中的有向樹含有與該圖相同的節(jié)點集，則稱該有向樹為有向圖的有向生成樹.在包含多個分組的多智能體系統(tǒng)中，節(jié)點入度平衡條件要求一個分組中每個節(jié)點到其他分組中所有節(jié)點的鄰接權(quán)重和等于零.

包含n個智能體的一階離散系統(tǒng)模型為

式(1)中:k∈{0,1,…}為離散時間序列;xi∈Rm,ui∈Rm分別表示第i個智能體的狀態(tài)及控制輸入.不失一般性，設(shè)m=1，對于m>1的情況，通過Kronecker算子容易進行擴展.

考慮系統(tǒng)(1)，假設(shè){X1,X2,…,Xp}為所有智能體的一個分割，給出如下分組一致的定義.

針對一階離散多智能體系統(tǒng)(1)，設(shè)計包含p個分組的一致性協(xié)議,即

(2)

(3)

2 主要結(jié)果

針對離散多智能體系統(tǒng)，分析在一致性協(xié)議(2)下實現(xiàn)分組一致需滿足的充要條件.首先，給出若干引理.

引理1[19]設(shè)矩陣A=[ai,j]∈Rn×n，令

|ai,j|,i=1,2,…,n，

表示矩陣A的去心絕對行和，則A的所有特征值都落在n個圓盤的區(qū)域G(A)中，其中,

|z-ai，i|

定理1 設(shè)非負矩陣A=[ai,j]∈Rn×n具有相同恒定正行和，則μ為矩陣A的一個特征值，對應(yīng)的特征向量為1n，且矩陣A的譜半徑ρ(A)=μ.當(dāng)且僅當(dāng)矩陣A對應(yīng)的有向圖G(A)含有一個有向生成樹時，特征值μ的代數(shù)重數(shù)為1.若ai,i>0，i=1,2,…,n，則對所有λ≠μ的特征值，|λ|<μ.如果G(A)含有一個有向生成樹，且ai,i>0，i=1,2,…,n，則μ為矩陣A的最大特征單根.

證明 定理第1部分，矩陣A具有相同恒定正行和μ，即有A1n=μ1n，μ為矩陣A的一個特征值，對應(yīng)的特征向量為1n，由引理1可知，A的所有特征值都落在n個圓盤的區(qū)域G(A)中，圓盤區(qū)域G(A)為

|z-ai，i||ai,j|

定理第2部分，需對充要性進行論證.

設(shè)矩陣B=A-μIn，有λi(A)=λi(B)+μ，i=1,2,…,n,λi(·)表示第i個特征值.若矩陣A對應(yīng)的有向圖G(A)含有一個有向生成樹，則B對應(yīng)的有向圖G(B)也含有一個有向生成樹.又因為矩陣B滿足引理2的條件，可知B具有一個代數(shù)重數(shù)是1的零特征值，即矩陣A具有代數(shù)重數(shù)為1的特征值μ.

矩陣A的特征值μ的代數(shù)重數(shù)為1，假設(shè)A對應(yīng)的有向圖G(A)不含有一個有向生成樹，由引理2可知，矩陣B=A-μIn的零特征值個數(shù)不為1，即矩陣A特征值μ的個數(shù)不為1，與條件矛盾，因此，有向圖G(A)含有一個有向生成樹.

定理第3部分，如果ai,i>0，易知集合(4)包含于圓形區(qū)域{z∈：|z|=μ}中，且n個圓盤的邊界僅在z=μ處與圓形區(qū)域有一個交點.因此，對A的所有λ≠μ的特征值，均有|λ|<μ.

由定理第2部分和第3部分，可直接得到第4部分的結(jié)論.

推論1 設(shè)隨機矩陣A=[ai,j]∈Rn×n，當(dāng)且僅當(dāng)A對應(yīng)的有向圖G(A)含有一個有向生成樹時，矩陣A具有代數(shù)重數(shù)為1的特征值λ=1，且ρ(A)=1.若ai,i>0,i=1,2,…,n，則對所有非1特征值而言，|λ|<1.如果G(A)含有一個有向生成樹，ai,i>0,i=1,2,…,n，則λ=1為隨機矩陣A的最大特征單根.

引理4[19]如果矩陣A∈Rn×n是非負的，則譜半徑ρ(A)是A的一個特征值，且存在一個正向量x>0，使Ax=ρ(A)x.

對離散多智能體系統(tǒng)

的一致性分析有如下引理.

引理5 當(dāng)且僅當(dāng)

時，離散時間算法(5)可實現(xiàn)漸進一致.其中，A=[ai,j]∈Rn×n是一個隨機矩陣;當(dāng)k→∞時，c是一個n階常系數(shù)列向量.

證明 當(dāng)節(jié)點vi和vj位于相同分組時，令ej,i，對系統(tǒng)(3)有

(8)

系統(tǒng)(3)實現(xiàn)分組一致即等價于系統(tǒng)(8)實現(xiàn)一致.現(xiàn)對系統(tǒng)(8)進行一致性證明.

綜上，當(dāng)且僅當(dāng)有向圖Gn含有一個有向生成樹時，系統(tǒng)(8)可實現(xiàn)一致，即系統(tǒng)(3)可實現(xiàn)分組一致.定理得證.

3 數(shù)值仿真

結(jié)合具體實例進行數(shù)值仿真，以驗證所得結(jié)論的正確性.

實驗1 具有5個智能體2個分組的系統(tǒng)，如圖1所示.其中,C1={1,2};C2={3,4,5}.易知系統(tǒng)含有一個有向生成樹，且不滿足入度平衡條件，其隨機矩陣A和組關(guān)聯(lián)矩陣E分別為

智能體初始狀態(tài)x(20)=[3 5 0 4 6]T,在一致性協(xié)議(2)下,系統(tǒng)經(jīng)k=20步響應(yīng)后,智能體狀態(tài)為x(20)=[3.2581 3.2581 2.2581 1.2580 1.2581]T,狀態(tài)響應(yīng)過程,如圖2所示.圖2中:x(k)為智能體狀態(tài);k 為離散時間序列.

圖1 系統(tǒng)通信拓撲圖 圖2 系統(tǒng)的狀態(tài)響應(yīng)Fig.1 Communication topology of system Fig.2 State response of system

由圖2可知：在一致性協(xié)議(2)下，對于圖1的系統(tǒng)，離散智能體狀態(tài)隨著時間的增加趨于分組一致，收斂值關(guān)系與組關(guān)聯(lián)矩陣對應(yīng)，仿真結(jié)果與理論分析結(jié)果相吻合.

實驗2 現(xiàn)將智能體數(shù)目擴充至8個，組數(shù)擴充至3個，其拓撲結(jié)構(gòu)如圖3所示.其中，C1={1,2};C2={3,4,5};C3={6,7,8}.系統(tǒng)含有一個有向生成樹，同樣不滿足入度平衡條件，其隨機矩陣A和組關(guān)聯(lián)矩陣E分別為

智能體初始狀態(tài)x(0)=[1 2 3 4 5 6 7 8]T,在一致性協(xié)議(2)下,經(jīng)過k=30步響應(yīng),智能體狀態(tài)為x(30)=[6.6530 6.6423 4.6530 4.6530 4.6530 3.6450 3.65303.6530]T,狀態(tài)響應(yīng)過程,如圖4所示.

圖3 系統(tǒng)通信拓撲圖 圖4 系統(tǒng)的狀態(tài)響應(yīng) Fig.3 Communication topology of system Fig.4 State response of system

由圖4可知：在一致性協(xié)議(2)下，對于離散多智能體系統(tǒng)，隨著時間的增加，智能體狀態(tài)趨于分組一致，且收斂值之間的關(guān)系與組關(guān)聯(lián)矩陣相對應(yīng)，進一步驗證了理論分析結(jié)果的正確性.此外，結(jié)合實驗1和實驗2可知，系統(tǒng)能否實現(xiàn)分組一致與智能體個數(shù)無關(guān).

4 結(jié)束語

研究無入度平衡條件下的離散多智能體系統(tǒng)分組一致問題.通過引入個體收斂值之差，設(shè)計離散多智能體分組一致協(xié)議，并利用圖論和矩陣論的方法，得到系統(tǒng)實現(xiàn)分組一致的充要條件.數(shù)值仿真結(jié)果表明:系統(tǒng)實現(xiàn)分組一致僅要求有向圖Gn含有一個有向生成樹，不要求拓撲結(jié)構(gòu)滿足入度平衡條件.

[1] COUZIN I D,KRAUSE J,JAMES R,etal.Collective memory and spatial sorting in animal groups[J].Journal of Theoretical Biology,2002,218(1):1-11.

[2] PARRISH J K,VISCIDO S V,GRUNBAUM D.Self-organized fish schools: An examination of emergent properties[J].Biology Bull,2002,202(2):296-305.

[3] 唐賢倫,張衡,周家林,等.基于多Agent混沌粒子群優(yōu)化的磁懸浮系統(tǒng)PID控制器[J].信息與控制,2013,42(6):758-764.

[4] WERFEL J,PETERSEN K,NAGPAL R.Designing collective behavior in a termite-inspired robot construction team[J].Science,2014,343(6172):754-758.

[5] SHARMA A,SRIVASTAVA S C,CHAKRABARTI S.Multi-agent-based dynamic state estimator for multi-area power system[J].IET Generation, Transmission and Distribution,2016,10(1):131-141.

[6] VICSEK T,CZIROOK A,BEN-JACOB E,etal.Novel type of phase transition in a system of self-driven particles[J].Physical Review Letters,1995,75(6):1226-1229.

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

[8] XIE Guangming,WANG Long.Consensus control for a class of networks of dynamic agents[J].International Journal of Robust and Nonlinear Control,2007,17(10/11):941-959.

[9] YU Wenwu,CHEN Guanrong,CAO Ming,etal.Second-order consensus for multi-agent systems with directed topologies and nonlinear dynamics[J].IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics,2010,40(3):881-891.

[10] 許耀贐,田玉平.線性及非線性一致性問題綜述[J].控制理論與應(yīng)用,2014,31(7):837-849.

[11] YU Junyan,WANG Long.Group consensus in multi-agent systems with switching topologies and communication delays[J].System and Control Letters,2010,59(6):330-348.

[12] YU Junyan,WANG Long.Group consensus of multi-agent systems with undirected communication exchange[J].International Journal of Systems Science,2012,43(2):334-348.

[13] 王強,王玉振,楊仁明.一類多智能體系統(tǒng)分組一致控制協(xié)議的設(shè)計與分析[J].控制與決策,2013,28(3):369-373，378.

[14] XIA Hong,HUANG Tingzhu,SHAO Jinliang,etal.Group consensus of multi-agent systems with communication delays[J].Neurocomputing,2016(171):1666-1673.

[15] XIA Weiguo,CAO Ming.Clustering in diffusively coupled networks[J].Automatica,2011,47(11):2395-2405.

[16] WANG Yuzhen,ZHANG Chenghui,LIU Zhenbin.A matrix approach to graph maximum stable set and coloring problems with application to multi-agent system[J].Automatica,2012,48(7):1227-1236.

[17] 紀(jì)良浩,廖曉峰,劉群.時延多智能體系統(tǒng)分組一致性分析[J].物理學(xué)報,2012,61(22):5-12.

[18] QIN Jiahu,YU Changbin.Cluster consensus control of generic linear multi-agent systems under directed topology with acyclic partition[J].Automatica,2013,49(2):2898-2905.

[19] HORN R A,JOHNSON C R.Matrix analysis[M].Cambridge:Cambridge University Press,1985:344,498,503.

(責(zé)任編輯： 錢筠 英文審校： 崔長彩)

Group Consensus Analysis of Discrete-Time Multi-Agent Systems

LIN Yuyang, LI Zhongshen

(College of Mechanical Engineering and Automation, Huaqiao University, Xiamen 361021, China)

In this paper, the protocol design method without in-degree balanced assumption was presented under the directed graph topology to investigate the grouping consensus problem for a class of discrete-time multi-agent systems. Firstly, based on the model of discrete-time multi-agent systems, a grouping consensus protocol was designed. Then, according to the algebraic graph theory and the matrix theory, the grouping consensus problem was studied. The sufficient and necessary condition of group consensus for the discrete-time multi-agent systems was obtained. Finally, simulation results demonstrated that the grouping consensus of the systems only required that the directed graphGnhad a direct spanning tree however the in-degree balanced assumption was not necessary. Keywords：multi-agent systems; discrete-time systems; in-degree balanced; group consensus

10.11830/ISSN.1000-5013.201703005

2016-04-11

李鐘慎(1971-)，男，教授，博士，主要從事先進控制理論與控制工程的研究.E-mail:lzscyw@hqu.edu.cn.

福建省自然科學(xué)基金資助項目(2013J05077)； 中央高?；究蒲袠I(yè)務(wù)基金資助項目(JB-ZR1107)； 福建省廈門市集美區(qū)科技計劃項目(20137C01)； 華僑大學(xué)研究生科研創(chuàng)新能力培育計劃項目(2014年度)

TP 273

A

1000-5013(2017)03-0306-06