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

林瑜陽(yáng)， 李鐘慎

(華僑大學(xué) 機(jī)電及自動(dòng)化學(xué)院， 福建 廈門(mén) 361021)

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

林瑜陽(yáng)， 李鐘慎

(華僑大學(xué) 機(jī)電及自動(dòng)化學(xué)院， 福建 廈門(mén) 361021)

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

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

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

1 預(yù)備知識(shí)與問(wèn)題描述

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

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

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

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

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

(2)

(3)

2 主要結(jié)果

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

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

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

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

|z-ai，i|

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

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

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

定理第2部分，需對(duì)充要性進(jìn)行論證.

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

3 數(shù)值仿真

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

實(shí)驗(yàn)1 具有5個(gè)智能體2個(gè)分組的系統(tǒng)，如圖1所示.其中,C1={1,2};C2={3,4,5}.易知系統(tǒng)含有一個(gè)有向生成樹(shù)，且不滿(mǎn)足入度平衡條件，其隨機(jī)矩陣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)過(guò)程,如圖2所示.圖2中:x(k)為智能體狀態(tài);k 為離散時(shí)間序列.

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

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

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

智能體初始狀態(tài)x(0)=[1 2 3 4 5 6 7 8]T,在一致性協(xié)議(2)下,經(jīng)過(guò)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)過(guò)程,如圖4所示.

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

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

4 結(jié)束語(yǔ)

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

[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] 許耀贐,田玉平.線性及非線性一致性問(wèn)題綜述[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] 王強(qiáng),王玉振,楊仁明.一類(lèi)多智能體系統(tǒng)分組一致控制協(xié)議的設(shè)計(jì)與分析[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ì)良浩,廖曉峰,劉群.時(shí)延多智能體系統(tǒng)分組一致性分析[J].物理學(xué)報(bào),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é)任編輯： 錢(qián)筠 英文審校： 崔長(zhǎng)彩)

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-)，男，教授，博士，主要從事先進(jìn)控制理論與控制工程的研究.E-mail:lzscyw@hqu.edu.cn.

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

TP 273

A

1000-5013(2017)03-0306-06