第15卷第4期 智能系统学报 Vol.15 No.4 2020年7月 CAAI Transactions on Intelligent Systems Jul.2020 D0L:10.11992tis.201901008 异质多智能体系统二分一致性的充要条件 王晓宇，刘开恩，纪志坚2，梁静娴 (1.青岛大学数学与统计学院，山东青岛266071；2.青岛大学自动化工程学院，山东青岛266071) 摘要：针对由一阶智能体和二阶智能体组成的异质多智能体系统的二分一致性问题，对连续和离散系统情形 分别设计了二分一致性协议。基于结构平衡的拓扑，通过规范变换实现了从具有敌对关系的系统到具有非负 连接权重系统的转化，将二分一致性问题转变为一般一致性问题。进一步，运用代数图论和矩阵理论分析闭环 控制系统的动态特性得到了异质多智能体系统渐近实现二分一致性的充要条件。最后通过数值模拟验证了 所得结果的有效性。 关键词：异质多智能体系统；二分一致性；规范变换：结构平衡：连续系统：离散系统：代数图论：矩阵理论 中图分类号：TP18文献标志码：A文章编号：1673-4785(2020)04-0679-08 中文引用格式：王晓宇，刘开恩，纪志坚，等.异质多智能体系统二分一致性的充要条件.智能系统学报，2020,15(4)： 679-686. 英文引用格式：VANG Xiaoyu,,LIU Kaien,.JI Zhijian,et al.Necessary and sufficient conditions for bipartite consensus of hetero- geneous multi-agent systems[J.CAAI transactions on intelligent systems,2020,15(4):679-686. Necessary and sufficient conditions for bipartite consensus of heterogeneous multi-agent systems WANG Xiaoyu',LIU Kaien',JI Zhijian',LIANG Jingxian' (1.School of Mathematics and Statistics,Qingdao University,Qingdao 266071,China;2.School of Automation Engineering,Qing- dao University,Qingdao 266071,China) Abstract:To investigate the bipartite consensus problem of heterogeneous multi-agent systems composed of first-and second-order agents,in this study,we designed bipartite consensus protocols for continuous and discrete systems.Based on a structurally balanced topology,we employ gauge transformation to transform a system with antagonistic interac- tions into one with non-negative connection weights.Accordingly,the bipartite consensus problem is transformed into a general consensus problem.We use algebraic graph theory and matrix theory to analyze the dynamic characteristics of the closed-loop control system and obtain the necessary and sufficient conditions to guarantee that heterogeneous multi- agent systems reach bipartite consensus asymptotically.Finally,we present numerical simulations to illustrate the effect- iveness of the obtained theoretical results. Keywords:heterogeneous multi-agent systems;bipartite consensus;gauge transformation;structural balance;continu- ous systems,discrete systems;algebraic graph theory;matrix theory 多智能体系统的一致性问题作为多智能体系 致性是指随着时间的变化，系统中智能体通过合 统协作控制的基本问题，因具有重要的理论和现 作或竞争的方式调节各自的目标与行为，最终使 实意义受到国内外研究人员的广泛关注。一 智能个体的部分或全部状态（如：位置、速度等） 都收敛到某个共同的值。目前多智能体系统在许 收稿日期：2019-01-08. 多领域中得到广泛应用，如机器人系统的编队控 基金项目：国家自然科学基金项目(61873136,61603288， 61374062):山东省自然科学基金项目(ZR2015FM023. 制、无人机的协作控制、卫星簇的姿态调整、传感 ZR2017MF055):中国博士后科学基金项目 (2015M571995). 器网络的目标跟踪等。 通信作者：刘开恩.E-mail:kaienliu@pku.edu.cn 然而随着系统规模的增加和复杂度的提高
DOI: 10.11992/tis.201901008 异质多智能体系统二分一致性的充要条件 王晓宇1 ，刘开恩1 ，纪志坚2 ，梁静娴1 （1. 青岛大学 数学与统计学院，山东 青岛 266071; 2. 青岛大学 自动化工程学院，山东 青岛 266071） 摘 要：针对由一阶智能体和二阶智能体组成的异质多智能体系统的二分一致性问题,对连续和离散系统情形 分别设计了二分一致性协议。基于结构平衡的拓扑,通过规范变换实现了从具有敌对关系的系统到具有非负 连接权重系统的转化，将二分一致性问题转变为一般一致性问题。进一步,运用代数图论和矩阵理论分析闭环 控制系统的动态特性,得到了异质多智能体系统渐近实现二分一致性的充要条件。最后通过数值模拟验证了 所得结果的有效性。 关键词：异质多智能体系统；二分一致性；规范变换；结构平衡；连续系统；离散系统；代数图论；矩阵理论 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)04−0679−08 中文引用格式：王晓宇, 刘开恩, 纪志坚, 等. 异质多智能体系统二分一致性的充要条件 [J]. 智能系统学报, 2020, 15(4): 679–686. 英文引用格式：WANG Xiaoyu, LIU Kaien, JI Zhijian, et al. Necessary and sufficient conditions for bipartite consensus of heterogeneous multi-agent systems[J]. CAAI transactions on intelligent systems, 2020, 15(4): 679–686. Necessary and sufficient conditions for bipartite consensus of heterogeneous multi-agent systems WANG Xiaoyu1 ，LIU Kaien1 ，JI Zhijian2 ，LIANG Jingxian1 (1. School of Mathematics and Statistics, Qingdao University, Qingdao 266071, China; 2. School of Automation Engineering, Qingdao University, Qingdao 266071, China) Abstract: To investigate the bipartite consensus problem of heterogeneous multi-agent systems composed of first- and second-order agents, in this study, we designed bipartite consensus protocols for continuous and discrete systems. Based on a structurally balanced topology, we employ gauge transformation to transform a system with antagonistic interactions into one with non-negative connection weights. Accordingly, the bipartite consensus problem is transformed into a general consensus problem. We use algebraic graph theory and matrix theory to analyze the dynamic characteristics of the closed-loop control system and obtain the necessary and sufficient conditions to guarantee that heterogeneous multiagent systems reach bipartite consensus asymptotically. Finally, we present numerical simulations to illustrate the effectiveness of the obtained theoretical results. Keywords: heterogeneous multi-agent systems; bipartite consensus; gauge transformation; structural balance; continuous systems; discrete systems; algebraic graph theory; matrix theory 多智能体系统的一致性问题作为多智能体系 统协作控制的基本问题，因具有重要的理论和现 实意义受到国内外研究人员的广泛关注[1-9]。一 致性是指随着时间的变化，系统中智能体通过合 作或竞争的方式调节各自的目标与行为，最终使 智能个体的部分或全部状态 (如：位置、速度等) 都收敛到某个共同的值。目前多智能体系统在许 多领域中得到广泛应用，如机器人系统的编队控 制、无人机的协作控制、卫星簇的姿态调整、传感 器网络的目标跟踪等。 然而随着系统规模的增加和复杂度的提高， 收稿日期：2019−01−08. 基金项目：国家自然科学基金项 目 (61873136， 61603288， 61374062)；山东省自然科学基金项目 (ZR2015FM023， ZR2017MF055) ；中国博士后科学基金项 目 (2015M571995). 通信作者：刘开恩. E-mail：kaienliu@pku.edu.cn. 第 15 卷第 4 期 智 能 系 统 学 报 Vol.15 No.4 2020 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2020
·680· 智能系统学报 第15卷 单一平衡点不能满足控制的要求，因此有学者提 成的有限有序序列：(，V),(,2),…,(,y)。若 出了分组一致性的概念，即同一子系统中所有智 存在一个根节点，使得从它出发到其它任何节点 能体收敛至一个状态，不同子系统中智能体收敛 都存在一条有向路径，则称图G包含一棵有向生 至不同状态10。以上的研究成果都是针对具有 成树。 非负连接权重的多智能体系统获得的，在很多情 定义1（结构平衡）)图G是结构平衡的 况下系统中还存在着一种特殊的“共识”现象，即 当且仅当节点集V可以分成两个非空集合V和 所有的智能体最终能达到大小相同，符号相反的 V2,且满足下面两个条件： 状态。可以理解为，不同智能体之间有的具有合 1)VUV=V.Vinv=0; 作关系，有的具有敌对关系-16.2013年，A1ta 2)a≥0，y,y∈V(qe{1,2 fini1在对具有敌对关系的多智能体系统的研究 a≤0，w:∈Vg,y∈V,q≠r(q,re{1,2) 中，给出了系统达到二分一致性的定义。杜明骏 定义2（规范变换）)借助正交矩阵D对 等研究了具有敌对关系且含通讯时滞的多智 多智能体系统的状态变量x进行的线性变换 能体系统的二分一致性。上述文献研究的都是由 Dx,其中D=diag{c1,2,…,0a,o:∈{±l,其具体取 具有相同动态方程的智能体构成的同质多智能体 值在使用时根据需要选取。 系统。而实际上，受到各种因素的限制，自然界 记R中所有规范变换矩阵的集合为D={D= 的个体和人造工程在功能和结构上都存在差异， diag{c1,2,…,o,c:∈{±1》。当多智能体系统的拓 发生耦合的每个智能体的动态方程可能不同，导 扑结构为结构平衡时，通过选取合适的D∈D可 致其系统描述的是混合多种动态方程的复杂系 以使得DAD中的元素非负，同时保证DLD满足 统。因此研究具有一阶和二阶智能体组成的异质 多智能体系统是很有必要的1。刘聪等讨论 非对角线元素非正且行和为零。 引理12) 给定矩阵B=[b]∈R满足 了具有有向生成树的离散时间异质多智能体系统 的一致性，但对控制增益的要求为a>max(/。Liu b≥0，b≤0，i≠j且∑by=0,则矩阵B至少有一 等！分别对连续和离散异质多智能体系统设计 个零特征值且其余非零特征值都具有正实部。矩 了一致性协议，证明了系统渐近实现一致性，当 阵B仅有简单零特征值，当且仅当矩阵B对应的 且仅当固定有向拓扑包含一棵有向生成树，对于 有向图包含一棵有向生成树。 系统具有切换拓扑情形也有相应结论。修言彬 等研究了具有包含两棵有向生成树的拓扑结 2问题陈述 构的离散异质多智能体系统的分组一致性，但两 考虑由n个智能体组成的异质多智能体系 组的最终收敛状态没有任何关系。 统，此处异质的含义为系统中有m(1≤m<n)个智 基于上面的研究，本文考虑具有包含一棵有 向生成树和结构平衡拓扑结构的由一阶和二阶多 能体具有二阶动态方程，称它们为二阶智能体， 智能体混合而成的多智能体系统的二分一致性问 n-m个智能体具有一阶动态方程，称它们为一阶 题，对连续和离散系统均进行了讨论。 智能体。不失一般性，假设前m个为二阶智能 体，智能体的指标集为11={1,2，…，m以，后n-m个 1 预备知识 为一阶智能体，智能体的指标集为2={m+1,m+ 2,…,n,记1=1U2o 本文中使用有向图表示多智能体系统中智能 假设1本文考虑的拓扑结构，按如下分组 体之间形成的网络拓扑。用G=(V,E,A)表示含 有n个节点的加权有向图，其中V={y:i=1,2,…,n 满足结构平衡关系，设指标集1对应的二阶智能 表示节点集，ESV×V表示有向边集，A=[a]∈R 体构成V,指标集2对应的一阶智能体构成V2, 为加权邻接矩阵。记=(，v）是有向图G中从 即将整个系统中二阶智能体分为一组，一阶智能 父节点v,到子节点：的有向边，与边e相关的 体分为一组，每组内部具有合作关系，两组间具 a称为边的权值。当e∈E时，有a≠0。节点 有敌对关系。 的邻居集用N={y∈V:e∈E)表示。图G的 首先，考虑连续多智能体系统，其个体的动态 Laplacian矩阵定义为L=A-A∈Rmw,其中A=diag 方程为 41,Aa,…,A}为对角阵，Aa=al为节点的 x(t)=(t),:(t)=4(t),i∈Ii (t)=4,(t),ie2 (1) 入度。从到的有向路径为图G不同的边构 式中：x(),(①)∈R和：（①）∈R分别表示第i个智能
α > max 1⩽i⩽m {lii} 单一平衡点不能满足控制的要求，因此有学者提 出了分组一致性的概念，即同一子系统中所有智 能体收敛至一个状态，不同子系统中智能体收敛 至不同状态[10-12]。以上的研究成果都是针对具有 非负连接权重的多智能体系统获得的，在很多情 况下系统中还存在着一种特殊的“共识”现象，即 所有的智能体最终能达到大小相同，符号相反的 状态。可以理解为，不同智能体之间有的具有合 作关系，有的具有敌对关系[13-16]。2013 年，Altafini[13] 在对具有敌对关系的多智能体系统的研究 中，给出了系统达到二分一致性的定义。杜明骏 等 [14] 研究了具有敌对关系且含通讯时滞的多智 能体系统的二分一致性。上述文献研究的都是由 具有相同动态方程的智能体构成的同质多智能体 系统。而实际上，受到各种因素的限制，自然界 的个体和人造工程在功能和结构上都存在差异， 发生耦合的每个智能体的动态方程可能不同，导 致其系统描述的是混合多种动态方程的复杂系 统。因此研究具有一阶和二阶智能体组成的异质 多智能体系统是很有必要的[17-19]。刘聪等[17] 讨论 了具有有向生成树的离散时间异质多智能体系统 的一致性，但对控制增益的要求为 。Liu 等 [18] 分别对连续和离散异质多智能体系统设计 了一致性协议，证明了系统渐近实现一致性，当 且仅当固定有向拓扑包含一棵有向生成树，对于 系统具有切换拓扑情形也有相应结论。修言彬 等 [19] 研究了具有包含两棵有向生成树的拓扑结 构的离散异质多智能体系统的分组一致性，但两 组的最终收敛状态没有任何关系。 基于上面的研究，本文考虑具有包含一棵有 向生成树和结构平衡拓扑结构的由一阶和二阶多 智能体混合而成的多智能体系统的二分一致性问 题，对连续和离散系统均进行了讨论。 1 预备知识 G = (V,E, A) n V = {vi : i = 1,2,··· ,n} E ⊆ V ×V A = [ai j] ∈ R n×n ei j = (vi , vj) G vj vi ei j ai j ei j ∈ E ai j , 0 vi Ni = {vj ∈ V : ei j ∈ E} G Laplacian L = Λ− A ∈ R n×n Λ = diag {Λ11,Λ22,··· ,Λnn} Λii = ∑ j∈Ni |ai j| vi vj vi G 本文中使用有向图表示多智能体系统中智能 体之间形成的网络拓扑。用 表示含 有 个节点的加权有向图，其中 表示节点集， 表示有向边集， 为加权邻接矩阵。记 是有向图 中从 父节点 到子节点 的有向边，与边 相关的 称为边的权值。当 时，有 。节点 的邻居集用 表示。图 的 矩阵定义为 ，其中 为对角阵， 为节点 的 入度。从 到 的有向路径为图 不同的边构 (vi , vk1),(vk1, vk2),··· ,(vkl, vj) G 成的有限有序序列： 。若 存在一个根节点，使得从它出发到其它任何节点 都存在一条有向路径，则称图 包含一棵有向生 成树。 G V V1 V2 定义 1 (结构平衡) [13] 图 是结构平衡的 当且仅当节点集 可以分成两个非空集合 和 ，且满足下面两个条件： 1) V1 ∪V2 = V, V1 ∩V2 = Ø ； ai j ⩾ 0,∀vi 2) , vj ∈ Vq(q ∈ {1,2}); ai j ⩽ 0,∀vi ∈ Vq, vj ∈ Vr ,q , r(q,r ∈ {1,2}) D x Dx D = diag{σ1,σ2,··· ,σn,σi ∈ {±1} 定义 2 (规范变换) [13] 借助正交矩阵 对 多智能体系统的状态变量 进行的线性变换 ，其中 ，其具体取 值在使用时根据需要选取。 R n D = {D = diag{σ1,σ2,··· ,σn},σi ∈ {±1}} D ∈ D DAD DLD 记 中所有规范变换矩阵的集合为 。当多智能体系统的拓 扑结构为结构平衡时，通过选取合适的 可 以使得 中的元素非负，同时保证 满足 非对角线元素非正且行和为零。 B = [bi j] ∈ R n×n bii ⩾ 0,bi j ⩽ 0,i , j ∑n j=1 bi j = 0 B B B 引 理 1 [ 2 ] 给定矩阵 满 足 且 ，则矩阵 至少有一 个零特征值且其余非零特征值都具有正实部。矩 阵 仅有简单零特征值，当且仅当矩阵 对应的 有向图包含一棵有向生成树。 2 问题陈述 n m(1 ⩽ m < n) n−m m I1 = {1,2,··· ,m} n−m I2 = {m+1,m+ 2,··· ,n} I = I1 ∪ I2 考虑由 个智能体组成的异质多智能体系 统，此处异质的含义为系统中有 个智 能体具有二阶动态方程，称它们为二阶智能体， 个智能体具有一阶动态方程，称它们为一阶 智能体。不失一般性，假设前 个为二阶智能 体，智能体的指标集为 ，后 个 为一阶智能体，智能体的指标集为 ，记 。 I1 V1 I2 V2 假设 1 本文考虑的拓扑结构，按如下分组 满足结构平衡关系，设指标集 对应的二阶智能 体构成 ，指标集 对应的一阶智能体构成 ， 即将整个系统中二阶智能体分为一组，一阶智能 体分为一组，每组内部具有合作关系，两组间具 有敌对关系。 首先，考虑连续多智能体系统，其个体的动态 方程为 { x˙i(t) = vi(t), v˙i(t) = ui(t), i ∈ I1 x˙i(t) = ui(t), i ∈ I2 (1) 式中：xi(t), vi(t) ∈ R 和 ui(t) ∈ R 分别表示第 i 个智能 ·680· 智 能 系 统 学 报 第 15 卷
第4期 王晓宇，等：异质多智能体系统二分一致性的充要条件 ·681· 体的位置、速度和控制输入。 式中：y(k)=x()+-v,(k),i∈1，a>0为控制增益；Na 基于假设1设计如下的二分一致性协议： N2的含义同(2)o 4(t)=-ay:(t)+a2 注释1在式(4)协议作用下，式(3)系统虽 然能够实现二分一致性，但是两组最终的收敛状 态没有任何关系。而在式（⑤）协议作用下，式(3) (2) 系统最终实现二分一致性，并且两组的收敛值互 (）=a ∑ac0-x0) 为相反数，这样的收敛状态具有更好的应用价值。 定义3如果对于式(1)系统的任何初始条 件满足： 式中：0=x0+0,iel4,a>0为控制增益：N limxi(t)- ax,0=0. ViEh.jEl +0 N2分别表示第i个智能体在V,和V2中的邻居集。 limv.tl=0Yi∈i (6) 其次，考虑离散多智能体系统，其个体的动态 limx(()- lai 2x()=0,ie2,j∈1 方程为 a x(k+1)=x(k)+Tv(k),iEI 则称式(1)系统渐近实现了二分一致性。 vi(k+1)=vi(k)+Tu(k),iEI (3) 如果对于式(3)系统的任何初始条件满足： x(k+1)=x(k)+T4,(k),i∈2 式中：x()、,()∈R和，()∈R分别表示第i个智 lim .-ud()=0.viehjel 能体在kT(k∈N,N为自然数集)时刻的位置、速度 limlv()=0. Vieh (7) 和控制输入；T>0为采样周期。 Viel,jel 在文献[19]中，针对系统(3)设计的二分一致 画- k+ ()0. a 性协议为 则称式(3)系统渐近实现了二分一致性。 u;(k)=-av;(k)+a a(x(k)-x,(k)+ 3 一致性分析 ∑a 基于所考虑多智能体系统的分组，将图G的 邻接矩阵A表示为 (4) ui(k)=a aii(xik)-x(k))+ A= A3 A (8) ∑a, 式中：A1∈Rmm;A2∈Rma-m:A3∈Ra-mxm,A4∈R-mxr-m。 31连续系统的一致性分析 其中α>0为控制增益。文献[19]中给出了两条 对连续式（①）系统，令=(x1,2,…,xm12,…ym 假定： xm+,xm+2,…,x)。由==a0y-x)和y=元+二= 假定1 a,-0,ie.且2=0.ieh 1 +二。将式(2)协议应用到式(1)系统中，可得： =+1 假定2除去两个单的零特征值外，图G对 E=-L5 (9) 应的Laplacian矩阵L的特征值都具有正实部。 其中 在本文中，基于假设1，删除了对上述两条假 -cIm 0 定的要求并设计了如下的二分一致性协议： a(A1+A2) (10) QA3 0 -A4+M3+M4 4,k)=-v+a22a-- 式中：Im表示m×m维的单位矩阵，0表示合适 维数的零矩阵；A=A(i=1,4):A=-A0=2,3): (5) A=diag ami:A2=diag =m+】 因=aa因- -ami A3=diag -a(m+D)j 一a(m+2j9 .iel (m+2)
体的位置、速度和控制输入。 基于假设 1 设计如下的二分一致性协议： ui(t) = −αvi(t)+α 2 ∑ j∈Ni1 ai j(xj(t)−yi(t))− ∑ j∈Ni2 | ai j | (yi(t)+ xj(t)) , i ∈ I1 ui(t) = α ∑ j∈Ni2 ai j(xj(t)− xi(t))− ∑ j∈Ni1 | ai j | (xi(t)+ xj(t)) , i ∈ I2 (2) yi(t) = xi(t)+ 1 α vi(t),i ∈ I1,α > 0 Ni1 Ni2 i V1 V2 式中： 为控制增益； 、 分别表示第 个智能体在 和 中的邻居集。 其次，考虑离散多智能体系统，其个体的动态 方程为 xi(k+1) = xi(k)+T vi(k),i ∈ I1 vi(k+1) = vi(k)+T ui(k),i ∈ I1 xi(k+1) = xi(k)+T ui(k),i ∈ I2 (3) xi(k)、vi(k) ∈ R ui(k) ∈ R i kT k ∈ N,N T > 0 式中： 和 分别表示第 个智 能体在 ( 为自然数集) 时刻的位置、速度 和控制输入； 为采样周期。 在文献 [19] 中，针对系统 (3) 设计的二分一致 性协议为 ui(k) = −αvi(k)+α 2 ∑ j∈Ni1 ai j(xj(k)− xi(k))+ ∑ j∈Ni2 ai jxj(k) , i ∈ I1 ui(k) = α ∑ j∈Ni2 ai j(xj(k)− xi(k))+ ∑ j∈Ni1 ai jxj(k) , i ∈ I2 (4) 其中 α > 0 为控制增益。文献 [19] 中给出了两条 假定： ∑n j=m+1 ai j=0,∀i ∈ I1 ∑m j=1 假定 1 ，且 ai j=0,∀i ∈ I2。 G L 假定 2 除去两个单的零特征值外，图 对 应的 Laplacian 矩阵 的特征值都具有正实部。 在本文中，基于假设 1，删除了对上述两条假 定的要求并设计了如下的二分一致性协议： ui(k) = −αvi(k)+α 2 ∑ j∈Ni1 ai j(xj(k)−yi(k))− ∑ j∈Ni2 | ai j | (yi(k)+ xj(k)) , i ∈ I1 ui(k) = α ∑ j∈Ni2 ai j(xj(k)− xi(k))− ∑ j∈Ni1 | ai j | (xi(k)+ xj(k)) , i ∈ I2 (5) yi(k) = xi(k)+ 1 α vi(k),i ∈ I1,α > 0 Ni1 Ni2 式中： 为控制增益； 、 的含义同 (2)。 注释 1 在式 (4) 协议作用下，式 (3) 系统虽 然能够实现二分一致性，但是两组最终的收敛状 态没有任何关系。而在式 (5) 协议作用下，式 (3) 系统最终实现二分一致性，并且两组的收敛值互 为相反数，这样的收敛状态具有更好的应用价值。 定义 3 如果对于式 (1) 系统的任何初始条 件满足： lim t→∞ xi(t)− |ai j| ai j xj(t) = 0, ∀i ∈ I1, j ∈ I lim t→∞ |vi(t)| = 0, ∀i ∈ I1 lim t→∞ xi(t)− |ai j| ai j xj(t) = 0, ∀i ∈ I2, j ∈ I (6) 则称式 (1) 系统渐近实现了二分一致性。 如果对于式 (3) 系统的任何初始条件满足： lim k→∞ xi(k)− |ai j| ai j xj(k) = 0, ∀i ∈ I1, j ∈ I lim k→∞ |vi(k)| = 0, ∀i ∈ I1 lim k→∞ xi(k)− |ai j| ai j xj(k) = 0, ∀i ∈ I2, j ∈ I (7) 则称式 (3) 系统渐近实现了二分一致性。 3 一致性分析 G A 基于所考虑多智能体系统的分组，将图 的 邻接矩阵 表示为 A = [ A1 A2 A3 A4 ] (8) A1∈R m×m ; A2∈R m×(n−m) ; A3∈R (n−m)×m A4∈R 式中： (n−m)×(n−m) ， 。 3.1 连续系统的一致性分析 ξ = (x1, x2,··· , xm, y1, y2,··· , ym xm+1, xm+2,··· , xn) T x˙i = vi = α(yi − xi) y˙i = x˙i + 1 α v˙i = vi + 1 α ui 对连续式(1)系统，令 ， 。由 和 ，将式 (2) 协议应用到式 (1) 系统中，可得： ξ˙ = −L¯ ξ (9) 其中 L¯ = αIm −αIm 0 −αA˜ 1 α(Λ1 +Λ2) αA˜ 2 αA˜ 3 0 −αA˜ 4 +αΛ3 +αΛ4 (10) Im m×m A˜ i = Ai(i = 1,4); A˜ j = −Aj(j = 2,3) Λ1 = diag ∑m j=1 a1 j , ∑m j=1 a2 j ,··· , ∑m j=1 am j ; Λ2 =diag ∑n j=m+1 −a1 j , ∑n j=m+1 −a2 j ,··· , ∑n j=m+1 −am j Λ3 =diag ∑m j=1 −a(m+1)j , ∑m j=1 −a(m+2)j , ··· , ∑m j=1 −an j ;Λ4 =diag ∑n j=m+1 a(m+1)j , ∑n j=m+1 a(m+2)j ,··· , ∑n j=m+1 an j 式中： 表示 维的单位矩阵，0 表示合适 维数的零矩阵； ； ； ； 第 4 期 王晓宇，等：异质多智能体系统二分一致性的充要条件 ·681·
·682· 智能系统学报 第15卷 易见A(i=1,2,3,4)中元素全非负。 可看作是具有n+m个节点的图G对应的Laplacian 根据假设l,令D=diag{lm,Im,-In-m,对专进行 矩阵。 如下规范变换：专=D5,从而式(9)系统可写作： 引理2假定假设1成立，图G包含一棵有 =-i (11) 向生成树当且仅当图G包含一棵有向生成树。 其中 文献[18]中针对切换有向拓扑给出了该引理 -aIm 0 i= -aA:a(Ai+A2) 的证明。针对固定拓扑，本文运用将图G的拓扑 -aA? -QA3 0 -aAs+aA3+aAs 性质转化为与其等价的代数性质的方法给出新的 易知L和L具有相同特征值。又L行和为 简单证明。 0.对角线元素全非负.非对角线元素全非正，故L 证明对进行初等变换： alm 0 0 i→ 0 Q(A1+A2)-qA -0A2 0 -aA3 -qAs+aA3+aA4 从而rank()=m+rank(L)。由引理1，与L对 证明在假设1成立的条件下，由引理3，式 应的图G有一棵有向生成树等价于立只有简单 (1)系统在式(2)协议作用下渐近实现二分一致性 零特征值，即有rank()=m+rank(L)=n+m-1,也 等价于式(11)系统能够渐近实现一致性。由引 即rank(L)=n-l。因此，仍由引理1可知结论成立。 理4，式(11)系统能够渐近实现一致性当且仅当 通过针对式(9)系统的规范变换，我们实现了 图G包含一棵有向生成树。进一步，结合引理 系统连接权重符号的改变，将具有敌对关系的式 2可知定理结论成立。 (9)系统转换为具有非负连接权重的式(11)系 3.2离散系统的一致性分析 统。根据系统渐近实现一致性的定义，容易得出 对离散式)系统，令xm(k)=[x(K),2(k),,xm(k), 下面的引理。 ym(K)=y1(k),y2(K),…,ym(k]T,xf(k)=[xm+1(k),xm+2(K),; 引理3式(1)系统在式(2)协议作用下渐近 x(k)]:将式(5)协议应用到式(3)系统中，可得： 实现二分一致性：当且仅当式(11)系统能够渐近 (x(k+1)=(1-aT)xm(k)+aTym(k) 实现一致性。 ym(k+1)=Imym(k)+aT[Axm(k)-Aiym(k)+ A2xr(k)-A2ym(k)] (12) 针对一般一致性问题，文献2]中有如下引理： x(k+1)=In-mx(k)+aT[Aax(k)-Aax(k)+ 引理4在固定拓扑下，连续时间多智能体 A3x(k)-A3x(k)] 系统无=∑，-x1e1,能够渐近实现一致性。 式中：A,和A4中的元素全都非负；A2和A3中的 =1 元素全都非正；A1、A2、A3、A4与式(10)中定义相 当且仅当图G包含一棵有向生成树。 同。同样地记A:=A,(i=1,4),A=-Aj=2,3),易 下面给出保证式(1)系统二分一致性成立的 知A,(i=1,2,3,4)中元素全非负。 一个定理。 令zk)=x,y(,xTk),将式(12)写成紧 定理1假定假设1成立。式(1)系统在式 凑形式得： (2)协议作用下渐近实现二分一致性的充要条件 z(k+1)=Uz(k) (13) 是图G包含一棵有向生成树。 其中 (1-aT)I 0 U= aTA Im-aT(A:+A2) -aTA: -gTA3 0 I-m+aT(As-A3-A4) 基于假设l,令D=diag{lm,Im,-ln-m,对z进 z(k+1)=U2(k) (14) 行如下规范变换：元=Dz,从而系统(13)可写为 其中 (1-aT)1m aTI 0 0= aTA In-aT(A:+A2) aTA aTA3 0 Im+aT(A-A3-A4) 对矩阵U进行初等变换： (1-aT)In 0 aTI 0 aTA3 I-m+aT(A-A3-A4) 0 aTA Im-aT(A:+A2)
A˜ 易见 i(i = 1,2,3,4) 中元素全非负。 1 D = diag{Im,Im,−In−m} ξ ξˆ = Dξ 根据假设 ，令 ，对 进行 如下规范变换： ，从而式 (9) 系统可写作： ˙ ξˆ = −Lˆ ξ,ˆ (11) 其中 Lˆ = αIm −αIm 0 −αA˜ 1 α(Λ1 +Λ2) −αA˜ 2 −αA˜ 3 0 −αA˜ 4 +αΛ3 +αΛ4 Lˆ L¯ Lˆ 0 Lˆ 易知 和 具有相同特征值。又 行和为 ，对角线元素全非负，非对角线元素全非正，故 n+m G ′ 可看作是具有 个节点的图 对应的 Laplacian 矩阵。 G ′ G 引理 2 假定假设 1 成立，图 包含一棵有 向生成树当且仅当图 包含一棵有向生成树。 G 文献 [18] 中针对切换有向拓扑给出了该引理 的证明。针对固定拓扑，本文运用将图 的拓扑 性质转化为与其等价的代数性质的方法给出新的 简单证明。 证明 对 Lˆ 进行初等变换： Lˆ → αIm 0 0 α(Λ1 +Λ2)−αA˜ 1 0 −αA˜ 3 0 −αA˜ 2 −αA˜ 4 +αΛ3 +αΛ4 ∆ = α [ Im 0 0 L ] rank(Lˆ) = m+rank(L) Lˆ G ′ Lˆ rank(Lˆ) = m+rank(L) = n+m−1 rank(L) = n−1 从而 。由引理 1，与 对 应的图 有一棵有向生成树等价于 只有简单 零特征值，即有 ，也 即 。因此，仍由引理 1 可知结论成立。 通过针对式 (9) 系统的规范变换，我们实现了 系统连接权重符号的改变，将具有敌对关系的式 (9) 系统转换为具有非负连接权重的式 (11) 系 统。根据系统渐近实现一致性的定义，容易得出 下面的引理。 引理 3 式 (1) 系统在式 (2) 协议作用下渐近 实现二分一致性；当且仅当式 (11) 系统能够渐近 实现一致性。 针对一般一致性问题，文献 [2] 中有如下引理： x˙i = ∑n j=1 ai j(xj − xi),i ∈ I G 引理 4 [2] 在固定拓扑下，连续时间多智能体 系统 ，能够渐近实现一致性， 当且仅当图 包含一棵有向生成树。 下面给出保证式 (1) 系统二分一致性成立的 一个定理。 G 定理 1 假定假设 1 成立。式 (1) 系统在式 (2) 协议作用下渐近实现二分一致性的充要条件 是图 包含一棵有向生成树。 G ′ 证明 在假设 1 成立的条件下，由引理 3，式 (1) 系统在式 (2) 协议作用下渐近实现二分一致性 等价于式 (11) 系统能够渐近实现一致性。由引 理 4，式 (11) 系统能够渐近实现一致性当且仅当 图 包含一棵有向生成树。进一步，结合引理 2 可知定理结论成立。 3.2 离散系统的一致性分析 xm(k)=[x1(k), x2(k),···, xm(k)]T ym(k) = [y1(k), y2(k),··· , ym(k)]T , xf(k) = [xm+1(k), xm+2(k),··· xn(k)]T 对离散式(3)系统，令 ， , ，将式 (5) 协议应用到式 (3) 系统中，可得： xm(k+1) = (1−αT)xm(k)+αT ym(k) ym(k+1) = Im ym(k)+αT[A1 xm(k)−Λ1 ym(k)+ A2 xf(k)−Λ2 ym(k)] xf(k+1) = In−m xf(k)+αT[A4 xf(k)−Λ4 xf(k)+ A3 xm(k)−Λ3 xf(k)] (12) A1 A4 A2 A3 Λ1 Λ2 Λ3 Λ4 A˜ i = Ai(i = 1,4) A˜ j = −Aj(j = 2,3) A˜ i(i = 1,2,3,4) 式中： 和 中的元素全都非负； 和 中的 元素全都非正； 、 、 、 与式 (10) 中定义相 同。同样地记 ， ，易 知 中元素全非负。 z(k) [x T m (k) y T m (k) x T f (k)] 令 T = ， ， ，将式 (12) 写成紧 凑形式得： z(k+1) = Uz(k) (13) 其中 U = (1−αT)Im αT Im αT A˜ 1 Im −αT(Λ1 +Λ2) −αT A˜ 3 0 0 −αT A˜ 2 In−m +αT(A˜ 4 −Λ3 −Λ4) D = diag{Im,Im,−In−m} z z˜ = Dz 基于假设 1，令 ，对 进 行如下规范变换： ，从而系统 (13) 可写为 z˜(k+1) = U˜ z˜(k) (14) 其中 U˜ = (1−αT)Im αT Im αT A˜ 1 Im −αT(Λ1 +Λ2) αT A˜ 3 0 0 αT A˜ 2 In−m +αT(A˜ 4 −Λ3 −Λ4) 对矩阵 U˜ 进行初等变换： U˜ → (1−αT)Im 0 αT A˜ 3 In−m +αT(A˜ 4 −Λ3 −Λ4) αT A˜ 1 αT A˜ 2 αT Im 0 Im −αT(Λ1 +Λ2) ≜ Uˆ ·682· 智 能 系 统 学 报 第 15 卷
第4期 王晓宇，等：异质多智能体系统二分一致性的充要条件 ·683· 易知U、0、立具有相同特征值。从而可以把 特征值均在复平面上以原点为圆心的单位圆内即 式(14)系统写为 14,k1从而有14P=(1-aTRe(0)2+(-aTIm(0)2=1- k+1)=0k) (15) 2aTRe()+(aT)2(Re(2)2+(m(a)2=1-2aTRe()+ 式中：k兰[k),(k);()[(k,k]=x(k), (aT)|P<l,从而有0<aT<,min(2Re()/lP)。 -xk)严；kFyk)。 定理2假定假设1成立且图G包含一棵有向生 可将矩阵0写作0=Inm-aTV,其中 成树。式(3)系统在式（⑤）协议作用下渐近实现二分 0 -I -致性当且仅当aT满足0<aT<,min(2Re()/|, 2多1十加 -A4+A3+Λ4 其中，为矩阵V的非零特征值。 -A2 A1+A2 证明根据引理6，定理2等价于：式(3)系 显然地，V的行和为0，对角线元素全非负， 统在式（⑤）协议作用下渐近实现二分一致性当且 非对角线元素非正。V可以看成是具有n+m个 仅当矩阵0有简单特征值1且其余特征值均在复 节点的图G所对应的矩阵，其中G与G之间的 平面上以原点为圆心的单位圆内。 关系与之前G与G之间的关系相同。由引理2， 由于假设1成立且图G包含一棵有向生成 当图G包含一棵有向生成树时，图G也包含一棵 树，由引理2知，图G也包含一棵有向生成树，从 有向生成树。从而V有简单零特征值且其余非 而G对应的Laplacian矩阵V有简单零特征值。 零特征值均具有正实部。令Pn=(I,牙m,)F为 由引理6的证明可知，矩阵V有简单零特征值等 其对应的右特征向量，其中1m表示所有元素均为 价于矩阵0有简单特征值1。因此令J为矩阵0 1的m维列向量。 的Jordan标准型，则必存在可逆的矩阵PeRa+mxa+m 类似于引理3，通过针对式(13)系统的规范 使得0=PJP1,其中J= a,J为矩 1 变换，容易得出下面的引理。 阵0的非1特征值对应的Jordan块，0nm-1表示所 引理5式(3)系统在式(5)协议作用下渐近 有元素均为0的n+m-1维列向量。不失一般 实现二分一致性，当且仅当式(15)系统能够渐近 性，记 实现一致性。 引理6假定假设1成立且图G包含一棵有 P=[p1,p2,…,patm】∈R+mxa+m 向生成树。矩阵0有简单特征值1且其余特征值 Prl=[pi,gpb,…,ptnJ'eRa+matm网 均在复平面上以原点为圆心的单位圆内，当且仅 式中：pn∈R+m,i=1,2,…,n+m,为矩阵0的右特 当aT满足0<aT<,n(2Rea,)/川P,其中为 征向量以及广义右特征向量；p:∈R+m,i=1,2…, 矩阵V的非零特征值。 n+m为矩阵0的左特征向量以及广义左特征 证明充分性：由于，为矩阵V的特征值， 向量。 易见4：=1-aT是矩阵0的特征值。由于V有 充分性：因为矩阵0的非1特征值都在复平 简单零特征值，不妨令1=0，从而0有简单的特 面的单位圆内，且 征值l。由于0p1=(L+m-aTVp1=P1-aTVp1=P, )=02k-1)=02k-2)=…=00) 故P1是矩阵0对应于特征值1的右特征向量。 则 不妨令山=1，此外4，=(1-aTRe(a)-aTIm)i, i=2,3,…,n+m,其中是虚数单位。故4P=(1-aTRe 「.(k) m2)=m.内 =lim02(0)= 1np(0) (a)2+(-aTIm(0)2=aT0,PaT-2Re()》+1。由于 I(0) Re)>0,当0<aT<,min(2Re,)/1P)时，对 其中0)=[0)，(0]r为式(15)系统的初始值。 :≠1均有1<1，即|4K1。因此，矩阵0的 因此limm(k)=ar(imm(k)-limm(k)》=0m。式(I5) 其余特征值均在复平面上以原点为圆心的单位 系统满足lim(-元，(k)=0,ijeL,Iim|(k)=0,i∈ 圆内。 I,也即渐近实现了一致性。再由引理5可知，式(3) 必要性：记4为矩阵0的特征值且4：=1- 系统在式(5)协议作用下渐近实现了二分一 aT,1≤i≤n+m,其中：为矩阵V的特征值。因为 致性。 矩阵0有简单特征值1，不妨令山1=1，则有1=0 必要性：由引理5，式(3)系统渐近实现二 即矩阵V有简单零特征值。又因为矩阵0其余 分一致性等价于式(15)系统渐近实现一致性
易知 U、U˜ 、Uˆ 具有相同特征值。从而可以把 式 (14) 系统写为 zˆ(k+1) = Uˆ zˆ(k) (15) zˆ(k)≜[xˆ T n (k) yˆ T m (k)]T xˆn(k)≜[xˆ T m (k) xˆ T f (k)]T =[x T m (k) −x T f (k)]T yˆ T m (k) y T m (k) 式中： ， ； ， ， ； = 。 Uˆ Uˆ 可将矩阵 写作 =In+m −αTV ，其中 V = Im 0 −Im −A˜ 3 −A˜ 4 +Λ3 +Λ4 0 −A˜ 1 −A˜ 2 Λ1 +Λ2 V 0 V n+m G˜ G G˜ G G ′ 2 G G˜ V φr1 = (1 T m ,1 T n−m ,1 T m ) T 1m 1 m 显然地， 的行和为 ，对角线元素全非负， 非对角线元素非正。 可以看成是具有 个 节点的图 所对应的矩阵，其中 与 之间的 关系与之前 与 之间的关系相同。由引理 ， 当图 包含一棵有向生成树时，图 也包含一棵 有向生成树。从而 有简单零特征值且其余非 零特征值均具有正实部。令 为 其对应的右特征向量，其中 表示所有元素均为 的 维列向量。 类似于引理 3，通过针对式 (13) 系统的规范 变换，容易得出下面的引理。 引理 5 式 (3) 系统在式 (5) 协议作用下渐近 实现二分一致性，当且仅当式 (15) 系统能够渐近 实现一致性。 G Uˆ 1 αT 0 < αT < min 2⩽λi⩽n+m (2Re(λi)/ | λi | 2 ) λi V 引理 6 假定假设 1 成立且图 包含一棵有 向生成树。矩阵 有简单特征值 且其余特征值 均在复平面上以原点为圆心的单位圆内，当且仅 当 满足 ，其中 为 矩阵 的非零特征值。 λi V µi =1−αTλi Uˆ V λ1 = 0 Uˆ 1 Uˆ φr1 =(In+m −αTV)φr1 =φr1−αTVφr1= φr1 φr1 Uˆ µ1 = 1 µi = (1−αTRe(λi))−αTIm(λi)i i = 2,3,··· ,n+m i | µi | 2=(1−αTRe (λi))2 +(−αTIm(λi))2 = αT (| λi | 2αT −2Re(λi))+1 Re(λi) > 0 0 < αT < min 2⩽λi⩽n+m (2Re(λi)/ | λi | 2 ) ∀µi , 1 | µi | 2 < 1 | µi |< 1 Uˆ 证明 充分性：由于 为矩阵 的特征值， 易见 是矩阵 的特征值。由于 有 简单零特征值，不妨令 ，从而 有简单的特 征值 。由于 ， 故 是矩阵 对应于特征值 1 的右特征向量。 不妨令 ，此外 ， ，其中 是虚数单位。故 。由于 ， 当 时，对 均有 ，即 。因此，矩阵 的 其余特征值均在复平面上以原点为圆心的单位 圆内。 µi Uˆ µi = 1− αTλi ,1 ⩽ i ⩽ n+m λi Uˆ 1 µ1 = 1 λ1 = 0 V Uˆ 必要性：记 为矩阵 的特征值且 ，其中 为矩阵 V 的特征值。因为 矩阵 有简单特征值 ，不妨令 ，则有 即矩阵 有简单零特征值。又因为矩阵 其余 | µi |< 1 | µi | 2=(1−αTRe(λi))2 +(−αTIm(λi))2= 1− 2αTRe(λi)+(αT) 2 ((Re(λi))2 +(Im(λi))2 = 1−2αTRe(λi)+ (αT) 2 | λi | 2 < 1 0 < αT < min 2⩽λi⩽n+m (2Re(λi)/ | λi | 2 ) 特征值均在复平面上以原点为圆心的单位圆内即 ，从而有 ，从而有 。 0 < αT < min 2⩽λi⩽n+m (2Re(λi)/ | λi | 2 ) 定理 2 假定假设 1 成立且图 G 包含一棵有向生 成树。式 (3) 系统在式 (5) 协议作用下渐近实现二分 一致性当且仅当αT满足 ， 其中 λi 为矩阵 V 的非零特征值。 Uˆ 1 证明 根据引理 6，定理 2 等价于：式 (3) 系 统在式 (5) 协议作用下渐近实现二分一致性当且 仅当矩阵 有简单特征值 且其余特征值均在复 平面上以原点为圆心的单位圆内。 G G˜ G˜ Laplacian V V Uˆ 1 J Uˆ Jordan P ∈ R (n+m)×(n+m) Uˆ = PJ P−1 J = [ 1 0 T n+m−1 0n+m−1 J¯ ] ,J¯ Uˆ 1 Jordan 0n+m−1 0 n+m−1 由于假设 1 成立且图 包含一棵有向生成 树，由引理 2 知，图 也包含一棵有向生成树，从 而 对应的 矩阵 有简单零特征值。 由引理 6 的证明可知，矩阵 有简单零特征值等 价于矩阵 有简单特征值 。因此令 为矩阵 的 标准型，则必存在可逆的矩阵 使得 ，其中 为矩 阵 的非 特征值对应的 块， 表示所 有元素均为 的 维列向量。不失一般 性，记 P = [φr1,φr2,··· ,φr(n+m)] ∈ R (n+m)×(n+m) P −1 = [φ T l1 ,φ T l2 ,··· ,φ T l(n+m) ] T ∈ R (n+m)×(n+m) φri ∈ R (n+m) ,i = 1,2,··· ,n+m Uˆ φli ∈ R (n+m) i = 1,2,··· , Uˆ 式中： ，为矩阵 的右特 征向量以及广义右特征向量； ， n+m 为矩阵 的左特征向量以及广义左特征 向量。 Uˆ 充分性：因为矩阵 的非 1 特征值都在复平 面的单位圆内，且 zˆ(k) = Uˆzˆ(k−1) = Uˆ 2 zˆ(k−2) = ··· = Uˆ k zˆ(0) 则 lim k→∞ zˆ(k) = lim k→∞ xˆn(k) yˆm(k) = lim k→∞ Uˆ k zˆ(0) = 1nφ T l1 zˆ(0) 1mφ T l1 zˆ(0) zˆ(0) [xˆ T n (0), yˆ T m (0)]T lim k→∞ vˆm(k) = α(lim k→∞ yˆm(k)−lim k→∞ xˆm(k)) = 0m lim k→∞ | xˆi(k)− xˆj(k) |= 0,i, j ∈ I,lim k→∞ | vˆi(k) |= 0,i ∈ I1 其中 = 为式 (15) 系统的初始值。 因此 。式 (15) 系统满足 ，也即渐近实现了一致性。再由引理 5 可知，式 (3) 系统在 式 ( 5 ) 协议作用下渐近实现了二分一 致性。 必要性：由引理 5，式 (3) 系统渐近实现二 分一致性等价于式 (15) 系统渐近实现一致性， 第 4 期 王晓宇，等：异质多智能体系统二分一致性的充要条件 ·683·