第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992tis.201901006 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190409.1042.020html 基于拓扑结构和个体动态层面的 多智能体系统可控性分析 陈万金，纪志坚 (青岛大学自动化学院，山东青岛266071) 摘要：针对一般线性多智能体系统中网络拓扑及个体动态这两个层面的可控性对系统整体可控性的关系进 行了研究，提出了一种新的描述一般线性多智能体系统的模型。利用PBH(Popov-Belevitch-Hautus)判据，得到 并证明了在此模型下多智能体系统可控性在网络拓扑结构与个体动态层面的充要条件。结合具体的例子解释 了系统矩阵中出现重复特征值时对定理2充分性的影响，并且提供了一种避免重复特征值出现的方法。特别 地，推导出了此模型下系统矩阵为实对称矩阵这一特殊情况时可以判定该系统不可控的两种判定条件，即比较 系统矩阵中最大的特征值代数重数与控制矩阵中1元素的个数，满足条件即判定系统不可控。 关键词：多智能体系统；可控性；线性定常系统；拓扑；邻居信息交互；特征值；特征向量：控制理论 中图分类号：TP273文献标志码：A 文章编号：1673-4785(2020)02-0264-07 中文引用格式：陈万金，纪志坚.基于拓扑结构和个体动态层面的多智能体系统可控性分析J.智能系统学报，2020,15(2)： 264-270. 英文引用格式：CHEN Wanjin,JI Zhijian.Controllability analysis of multi-agent systems based on topological structure and indi-- vidual dynamic level[Jl.CAAI transactions on intelligent systems,2020,15(2):264-270. Controllability analysis of multi-agent systems based on topological structure and individual dynamic level CHEN Wanjin,JI Zhijian (School of Automation Engineering,Qingdao University,Qingdao 266071,China) Abstract:The relationship between the controllability of network topology and individual dynamics in the overall con- trollability of the system is studied,and a new model describing the general linear multi-agent system is proposed.Us- ing the Popov-Belevitch-Hautus(PBH)criterion,the necessary and sufficient conditions for the controllability of a multi-agent system in the network topology and individual dynamic level are obtained and proved,and the effect of re- peated eigenvalues in the system matrix on the sufficiency of Theorem 2 is explained with a concrete example.We provide a way to avoid the occurrence of repeated eigenvalues.In particular,the two conditions for judging the uncon- trollable system can be determined when the system matrix is a real symmetric matrix under this model;that is,com- pare the largest eigenvalue algebraic multiplicity in the system matrix with the number of 1 elements in the control mat- rix.If this condition is satisfied,the system is uncontrollable. Keywords:multi-agent system;controllability;linear time-invariant systems;topology;local interaction;eigenvalue;ei- genvector,control theory 近二三十年，随着工业技术的发展迭代，得益 于计算机、传感器、机器人等技术的发展，多智能 体系统(multi-agent system,MAS)也越来越常见。 收稿日期：2019-01-07.网络出版日期：2019-04-11. 基金项目：国家自然科学基金项目(61873136,61603288,61374062) 不止控制领域，众多领域开始对其进行了研究。 通信作者：纪志坚.E-mail:jizhijian(@pku.org.cn 多智能体系统实质上是多个个体组成的一个集
DOI: 10.11992/tis.201901006 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190409.1042.020.html 基于拓扑结构和个体动态层面的 多智能体系统可控性分析 陈万金，纪志坚 （青岛大学 自动化学院，山东 青岛 266071） 摘 要：针对一般线性多智能体系统中网络拓扑及个体动态这两个层面的可控性对系统整体可控性的关系进 行了研究，提出了一种新的描述一般线性多智能体系统的模型。利用 PBH(Popov-Belevitch-Hautus) 判据，得到 并证明了在此模型下多智能体系统可控性在网络拓扑结构与个体动态层面的充要条件。结合具体的例子解释 了系统矩阵中出现重复特征值时对定理 2 充分性的影响，并且提供了一种避免重复特征值出现的方法。特别 地，推导出了此模型下系统矩阵为实对称矩阵这一特殊情况时可以判定该系统不可控的两种判定条件，即比较 系统矩阵中最大的特征值代数重数与控制矩阵中 1 元素的个数，满足条件即判定系统不可控。 关键词：多智能体系统；可控性；线性定常系统；拓扑；邻居信息交互；特征值；特征向量；控制理论 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2020)02−0264−07 中文引用格式：陈万金, 纪志坚. 基于拓扑结构和个体动态层面的多智能体系统可控性分析 [J]. 智能系统学报, 2020, 15(2): 264–270. 英文引用格式：CHEN Wanjin, JI Zhijian. Controllability analysis of multi-agent systems based on topological structure and individual dynamic level[J]. CAAI transactions on intelligent systems, 2020, 15(2): 264–270. Controllability analysis of multi-agent systems based on topological structure and individual dynamic level CHEN Wanjin，JI Zhijian (School of Automation Engineering, Qingdao University, Qingdao 266071, China) Abstract: The relationship between the controllability of network topology and individual dynamics in the overall controllability of the system is studied, and a new model describing the general linear multi-agent system is proposed. Using the Popov-Belevitch-Hautus (PBH) criterion, the necessary and sufficient conditions for the controllability of a multi-agent system in the network topology and individual dynamic level are obtained and proved, and the effect of repeated eigenvalues in the system matrix on the sufficiency of Theorem 2 is explained with a concrete example. We provide a way to avoid the occurrence of repeated eigenvalues. In particular, the two conditions for judging the uncontrollable system can be determined when the system matrix is a real symmetric matrix under this model; that is, compare the largest eigenvalue algebraic multiplicity in the system matrix with the number of 1 elements in the control matrix. If this condition is satisfied, the system is uncontrollable. Keywords: multi-agent system; controllability; linear time-invariant systems; topology; local interaction; eigenvalue; eigenvector; control theory 近二三十年，随着工业技术的发展迭代，得益 于计算机、传感器、机器人等技术的发展，多智能 体系统 (multi-agent system,MAS) 也越来越常见。 不止控制领域，众多领域开始对其进行了研究[1-5]。 多智能体系统实质上是多个个体组成的一个集 收稿日期：2019−01−07. 网络出版日期：2019−04−11. 基金项目：国家自然科学基金项目 (61873136, 61603288, 61374062). 通信作者：纪志坚. E-mail：jizhijian@pku.org.cn. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
第2期 陈万金，等：基于拓扑结构和个体动态层面的多智能体系统可控性分析 ·265· 合，这些个体每个都具有一定的接受与处理信息 重复特征值的条件，给出了一类根据系统矩阵中 并且执行相应命令的能力。与传统的单个个体为 重复特征值的重数判定系统不可控的判定条件。 一个系统相比，多智能体系统具有非常显著的优 势，并且相关技术已经在智能交通系统、机器人 1预备知识 编队6刀、人造卫星簇姿态控制图等实际工程应用 本节将定义本文中要用的数学符号与图论中 中得到应用。 基本概念。e:表示第iie)个元素为l,其余元 本文研究的是一般线性多智能体的能控性。 素为0的列向量。如e1=10…0。R表 在20世纪60年代，卡尔曼(R.E.Kalman)等首次 示n维实向量空间，Rm表示实m×n阶矩阵的集 提出能控性的概念o。Tanner在2004年最早提 合。对于一个集合S,SI表示集合的元素个数。* 出了多智能体的能控性山，是指通过对多智能体 表示任意实数。图论概念：G(V,E)表示一个n节 内部的某个或者是某几个领导者(leader)智能体 点的拓扑图。其中这个图的点集和边集分别用 施加外部控制输入，系统内部各智能体之间通过 V={W,M2vl,E={(y,y∈V,i≠》表示，不考 相互合作和自组织，使得跟随者(follower)智能体 虑自环的情况，即(，v)∈E。拓扑图分为有向图 由任意给定的初始状态到达期望的最终状态。 和无向图，两者的主要区别在于边的定义。对有 智能体能控性的研究得到了国内外学者的广泛关 向图来说，(，v)表示有一条点i指向点j的有向 注1n,并且近些年时效网络能控性问题、目标 边，表示节点j收到来自i的信息，即边(，)≠ 能控性问题叨、事件触发能控性问题等取得了 (y)。对于无向图则有(，v)=(y,,即，y之 很大进展。在现实生活中，具有多智能体系统性 间有边的连接，两个点则会相互接收到对方信 质的系统处处可见，并且有非常有意思的现象。 息。如果点y接受到点，的信息，则称点，为 比如一个蚁群中如果有某只或者某几只蚂蚁找到 y的邻居(neighbor)。点，的邻居集表示为Nao 食物，便会通过自身释放的化学物质引导大量蚁 对无向图来说，若(，)∈E,则点y,是点y的邻 群聚集2四：社会的舆论焦点往往是通过少数几个 居，同时点y也是点y,的邻居。d=Wal表示点y 人开始引爆；以及每个人的人际关系圈会随着其 的度(degree)。无向图G的度矩阵(degree matrix) 中的某个人或者是某几个人的行为而出现变化。 用D(G)=diag(d,d,…,dn)表示。A(G)表示图 所以，研究多智能体系统的能控性在研究自然现 G的邻接矩阵(adjacency matrix),在有向加权图 象、社会学现象，以及为发展新技术提供了重要 中，A=(a)mxm定义为 的思想方法。 Wij,(j,i)EE(G) 目前对多智能体系统能控性的研究大多都从 a={0,其他 网络拓扑方面入手，借助图论及代数工具进行研 式中：w,表示边的权重，即点j对点i的影响程 究27，如文献[28]讨论了路图和环图的能控性 度。本文权重皆取w=1。在无向图中，边(，y) 问题，文献[11]考察了完全图的能控性，文献 必然会有相同权重的边(v)与之对应，所以邻 [14,29]研究了无向树图的可控性。但是多智能 接矩阵A(G)为对称矩阵。拉普拉斯矩阵(Lapla- 体系统具有“个体动态+通信拓扑”的特点0，所以 cian matrix)是相较于度矩阵的另一种表达图中顶 两者都对系统整体可控性有很大影响。文献[26] 点关系的一种矩阵，也是多智能体系统的研究中 研究了扩散耦合多智能体系统的可控性的充要条 最常用的矩阵，L(G)=D(G)-A(G)。另外拉普拉 件，网络拓扑结构与个体动态同时可控时整个系 斯矩阵可以定义如下： 统便是可控的。文献[30]提出文献[26]结论的不 i=j 足之处，说明此方面的结论并不完美，不能精确 地描述网络拓扑结构与个体动态的可控性对系统 一0ij i≠j 整体可控性的影响，这是本文着力要解决的问题 由以上定义可知，在无向图中，矩阵L(G的 之一。 对角线元素是相应行其余元素和的相反数，即 本文将研究一般线性多智能体系统的可控性 L(G)的每行元素之和为零，并且是实对称矩阵， 与网络拓扑结构和个体动态可控性的关系，得到 即L(G)是可对角化的。 了相对完整的结论。另外，从特征值的角度出 文中判别可控性主要用到如下引理。 发，找到了系统矩阵中重复特征值数量与系统不 引理1秩判据”，对于线性定常连续系统 可控之间的关系，并进一步整理了系统矩阵不含 亡=Ar+B,令A,B分别为系统的状态矩阵和控
合，这些个体每个都具有一定的接受与处理信息 并且执行相应命令的能力。与传统的单个个体为 一个系统相比，多智能体系统具有非常显著的优 势，并且相关技术已经在智能交通系统[5] 、机器人 编队[6-7] 、人造卫星簇姿态控制[8] 等实际工程应用 中得到应用。 本文研究的是一般线性多智能体的能控性。 在 20 世纪 60 年代，卡尔曼 (R.E. Kalman) 等首次 提出能控性的概念[9-10]。Tanner 在 2004 年最早提 出了多智能体的能控性[11] ，是指通过对多智能体 内部的某个或者是某几个领导者 (leader) 智能体 施加外部控制输入，系统内部各智能体之间通过 相互合作和自组织，使得跟随者 (follower) 智能体 由任意给定的初始状态到达期望的最终状态[12]。 智能体能控性的研究得到了国内外学者的广泛关 注 [13-17] ,并且近些年时效网络能控性问题[18] 、目标 能控性问题[19] 、事件触发能控性问题[20] 等取得了 很大进展。在现实生活中，具有多智能体系统性 质的系统处处可见，并且有非常有意思的现象。 比如一个蚁群中如果有某只或者某几只蚂蚁找到 食物，便会通过自身释放的化学物质引导大量蚁 群聚集[21] ；社会的舆论焦点往往是通过少数几个 人开始引爆；以及每个人的人际关系圈会随着其 中的某个人或者是某几个人的行为而出现变化。 所以，研究多智能体系统的能控性在研究自然现 象、社会学现象，以及为发展新技术提供了重要 的思想方法。 目前对多智能体系统能控性的研究大多都从 网络拓扑方面入手，借助图论及代数工具进行研 究 [21-27] ，如文献 [28] 讨论了路图和环图的能控性 问题，文献 [11] 考察了完全图的能控性，文献 [14，29] 研究了无向树图的可控性。但是多智能 体系统具有“个体动态+通信拓扑”的特点[30] ，所以 两者都对系统整体可控性有很大影响。文献 [26] 研究了扩散耦合多智能体系统的可控性的充要条 件，网络拓扑结构与个体动态同时可控时整个系 统便是可控的。文献 [30] 提出文献 [26] 结论的不 足之处，说明此方面的结论并不完美，不能精确 地描述网络拓扑结构与个体动态的可控性对系统 整体可控性的影响，这是本文着力要解决的问题 之一。 本文将研究一般线性多智能体系统的可控性 与网络拓扑结构和个体动态可控性的关系，得到 了相对完整的结论。另外，从特征值的角度出 发，找到了系统矩阵中重复特征值数量与系统不 可控之间的关系，并进一步整理了系统矩阵不含 重复特征值的条件，给出了一类根据系统矩阵中 重复特征值的重数判定系统不可控的判定条件。 1 预备知识 ei i(i ∈ N) e1 = [ 1 0 ··· 0 ]T R n R m×n m×n |S | ∗ G(V,E) V = {v1, v2 ··· vn} E = {(vi , vj)|vi , vj ∈ V,i , j} (vi , vj) ∈ E (vi , vj) (vi , vj) , (vj , vi) (vi , vj) = (vj , vi) N(i) (vi , vj) ∈ E di = |N(i) | D(G) = diag(d1,d2,··· ,dn) A = (ai j)n×n 本节将定义本文中要用的数学符号与图论中 基本概念。 表示第 个元素为 1，其余元 素为 0 的列向量。如 。 表 示 n 维实向量空间， 表示实 阶矩阵的集 合。对于一个集合 S， 表示集合的元素个数。 表示任意实数。图论概念： 表示一个 n 节 点的拓扑图。其中这个图的点集和边集分别用 ， 表示，不考 虑自环的情况，即 。拓扑图分为有向图 和无向图，两者的主要区别在于边的定义。对有 向图来说， 表示有一条点 i 指向点 j 的有向 边，表示节点 j 收到来自 i 的信息，即边 。对于无向图则有 ，即 vi ，vj 之 间有边的连接，两个点则会相互接收到对方信 息。如果点 vj 接受到点 vi 的信息，则称点 vi 为 vj 的邻居 (neighbor)。点 vi 的邻居集表示为 。 对无向图来说，若 ，则点 vi 是点 vj 的邻 居，同时点 vj 也是点 vi 的邻居。 表示点 vi 的度 (degree)。无向图 G 的度矩阵 (degree matrix) 用 表示。 A( G ) 表 示 图 G 的邻接矩阵 (adjacency matrix)，在有向加权图 中， 定义为 ai j = { wi j, (j,i) ∈ E(G) 0, 其他 wi j = 1 (vi , vj) (vj , vi) L(G) = D(G)− A(G) 式中：wij 表示边的权重，即点 j 对点 i 的影响程 度。本文权重皆取 。在无向图中，边 必然会有相同权重的边 与之对应，所以邻 接矩阵 A(G) 为对称矩阵。拉普拉斯矩阵 (Laplacian matrix) 是相较于度矩阵的另一种表达图中顶 点关系的一种矩阵，也是多智能体系统的研究中 最常用的矩阵， 。另外拉普拉 斯矩阵可以定义如下： li j = ∑n j=1, j,i ai j, i = j −ai j, i , j 由以上定义可知，在无向图中，矩阵 L(G) 的 对角线元素是相应行其余元素和的相反数，即 L(G) 的每行元素之和为零，并且是实对称矩阵， 即 L(G) 是可对角化的。 文中判别可控性主要用到如下引理。 x˙ = Ax+ Bu 引理 1 秩判据[31] ，对于线性定常连续系统 ，令 A，B 分别为系统的状态矩阵和控 第 2 期 陈万金，等：基于拓扑结构和个体动态层面的多智能体系统可控性分析 ·265·
·266· 智能系统学报 第15卷 制输入矩阵。当且仅当可控性判别矩阵C的秩 3节我们将讨论在模型(4)下一般线性多智能体 满足等式： 系统的可控性问题。 rank(C)=[BAB…A-lB=n 3主要结论 系统是完全可控的。 PBH判据，对于系统=Ax+Bu,当且仅当 一般线性多智能体系统的可控性，根据系统 不存在非零向量”，满足以下等式： 的结构特点，可以细化成两个方面。一个是该系 Bv=0 统的拓扑结构的可控性，另一个是系统中智能体 Av=Av 个体动态的可控性。本节将研究这两个层面的可 该系统是可控的。 控性与多智能体系统整体可控性的关系。以下用 在本文中，没有特殊说明的情况下，讨论的均 矩阵对(L,M0,(A-BK1-BK2,C),(为矩阵L的 是无向非加权固定拓扑下的系统。 特征值)，分别表示多智能体系统中网络拓扑结构 可控和个体动态可控。 2一般性模型的建立 3.1一般线性多智能体系统可控的必要性与充 考虑一个由n个完全相同的智能体构成的智 分性条件 定理1在一般线性多智能体系统（⑤）中，如 能体系统，用集合V={1,2,…,}表示其包含的智 果该系统整体可控即(L,可控，则该系统的网 能体集，并用1,2，…n依次将所含的智能体标注。 络拓扑结构可控即(L,M)可控，同时每个智能体 将智能体按照是否接受外部控制输入分为领导者 的动态可控，即对于每一个拉普拉斯矩阵L的特 与跟随者，假设有m个领导者，则领导者集合表 征值1，(A-BK,-BK2,C)是可控的。 示为VL={w,2,…,Vm}(I≤m≤n),V=八Vz表示 证明这里只证明(L,M0是可控的，(A-BK1- 其跟随者集合。每一个跟随者y∈V,线性动力 BK2,C)的可控性可以用同样的方法证明。 学方程描述为 假设(L,M)不可控，根据PBH判据，则必然 xi=Axi+Bu (1) 存在非零向量xeRm满足xL=x,xM=0。令 对于每一个领导者∈V,线性动力学方程描述为 0,y分别为矩阵A-BK1-BK2的一个特征值与相 =Ax;+Bu;+Cz (2) 应的左特征向量。那么有 式中：A∈Rmxm、B∈RmP、C∈Rmxg分别表示智能 体v:的状态；：∈R表示该系统中单个智能体接 (x⑧y)Ti=(x⑧y)TLn⑧(A-BK1-L⑧BK2)》= 受其余智能体信息的影响；表示对单个智能体 (x⑧y)T⑧(In⑧(A-BK1)- (x⑧y)⑧(L⑧BK,)= 的外部输入控制。对于每一个智能体，基于该系 xT⑧y(A-BK1)-xTL⑧yBK2= 统的邻居关系的耦合规则4：如下： xT⑧y(A-BK1-BK2)= u=-Kx+∑a,Kg,-x) (3) x⑧yT)=(x®y)'0 V)ENi 即0是L的一个特征值并且(x⑧y)'是相应的左 式中：Ki,K2eRm为可以设计的反馈增益；ag表 特征向量。有(x⑧y)FM=(rrM)⑧yC),根据PBH 示智能体之间信息传递的强度。定义x=col 判据，即(L,0不可控，这与已知其可控矛盾，因 (r1,2,…,x),z=Col(z1,2,…,z),信息传递强度都 此(L,M)可控，证毕。 相同且令a=1,i≠j,则上面的多智能体系统表 我们得到了模型(5)下的多智能体系统能控 达式可以整合为如下形式： 的必要性条件。通常来说，我们更希望能得到充 =[In⑧(A-BK1)-L⑧BK2]x+(M⑧C)z(4) 要条件，并且通过充分条件来推断该系统是否可 ⑧表示克罗内克积(Kronecker product)B。 控。接下来讨论一般线性多智能体系统可控的充 L为图G的拉普拉斯矩阵，M表示领导者与跟随 分条件。 者的身份，定义如下，y,表示领导者： 定理2在一般线性多智能体系统（⑤）中，如 M={0其型 果网络拓扑结构可控即(L0可控，并且每个智 能体的动态可控即对于L的每一个特征值， 式(4)可以简化为 (0<s≤n,sEN),有矩阵对(A-BK1-BK2,C)可 文=Lx+Mz (5) 控，并且矩阵A-BK1-BK2之间不含有重复特 文献[23]中所讨论的模型可以视为模型(4) 征值，那么该系统整体可控即(L,M)可控。 (式(4))中K为零矩阵的一种特殊情况。在第 证明假设(L,M)不可控。L是对称矩阵
制输入矩阵。当且仅当可控性判别矩阵 C 的秩 满足等式： rank(C) = [ B AB ··· A n−1 B ] = n 系统是完全可控的。 PBH 判据 x˙ = Ax+ Bu [11] ，对于系统 ，当且仅当 不存在非零向量 v，满足以下等式： { B T v = 0 Av = λv 该系统是可控的。 在本文中，没有特殊说明的情况下，讨论的均 是无向非加权固定拓扑下的系统。 2 一般性模型的建立 V = {1,2,··· ,n} 1,2,···n VL = {v1, v2,··· , vm} 1 ⩽ m ⩽ n VF = V\VL vi ∈ VF 考虑一个由 n 个完全相同的智能体构成的智 能体系统，用集合 表示其包含的智 能体集，并用 依次将所含的智能体标注。 将智能体按照是否接受外部控制输入分为领导者 与跟随者，假设有 m 个领导者，则领导者集合表 示为 ( )， 表示 其跟随者集合。每一个跟随者 ，线性动力 学方程描述为 x˙i = Axi + Bui (1) 对于每一个领导者 vi ∈ VL，线性动力学方程描述为 x˙i = Axi + Bui +Czl (2) A ∈ R m×m B ∈ R m×p C ∈ R m×q ui ∈ R q zl ui 式中： 、 、 分别表示智能 体 vi 的状态； 表示该系统中单个智能体接 受其余智能体信息的影响； 表示对单个智能体 的外部输入控制。对于每一个智能体，基于该系 统的邻居关系的耦合规则 如下： ui = −K1 xi + ∑ vj∈N(i) ai jK2(xj − xi) (3) K1 K2 ∈ R p×m x = col (x1, x2,··· , xn) z = col(z1,z2,··· ,zl) ai j = 1 i , j 式中： ， 为可以设计的反馈增益；aij 表 示智能体之间信息传递的强度。定义 ， ，信息传递强度都 相同且令 ， ，则上面的多智能体系统表 达式可以整合为如下形式： x˙ = [In ⊗(A− BK1)− L⊗ BK2]x+(M ⊗C)z (4) ⊗ 表示克罗内克积 (Kronecker product)[32]。 L 为图 G 的拉普拉斯矩阵，M 表示领导者与跟随 者的身份，定义如下，vl 表示领导者： Mil = { 1 if i = l 0 其他 式 (4) 可以简化为 x˙ = ⌣ Lx+ ⌣ M z (5) 文献 [23] 中所讨论的模型可以视为模型（4） （式（4））中 K1 为零矩阵的一种特殊情况。在第 3 节我们将讨论在模型 (4) 下一般线性多智能体 系统的可控性问题。 3 主要结论 (L, M) (A− BK1 −λBK2,C) λ L 一般线性多智能体系统的可控性，根据系统 的结构特点，可以细化成两个方面。一个是该系 统的拓扑结构的可控性，另一个是系统中智能体 个体动态的可控性。本节将研究这两个层面的可 控性与多智能体系统整体可控性的关系。以下用 矩阵对 ， ，( 为矩阵 的 特征值)，分别表示多智能体系统中网络拓扑结构 可控和个体动态可控。 3.1 一般线性多智能体系统可控的必要性与充 分性条件 ( ⌣ L, ⌣ M) (L, M) λ (A− BK1 −λBK2,C) 定理 1 在一般线性多智能体系统 (5) 中，如 果该系统整体可控即 可控，则该系统的网 络拓扑结构可控即 可控，同时每个智能体 的动态可控，即对于每一个拉普拉斯矩阵 L 的特 征值 ， 是可控的。 (L, M) (A− BK1− λBK2,C) 证明 这里只证明 是可控的， 的可控性可以用同样的方法证明。 (L, M) x ∈ R n x T L = λx T , x TM = 0 θ, y A− BK1 −λBK2 假设 不可控，根据 PBH 判据，则必然 存在非零向量 满足 。令 分别为矩阵 的一个特征值与相 应的左特征向量。那么有 (x⊗ y) T ⌣ L = (x⊗ y) T (In ⊗(A− BK1 − L⊗ BK2)) = (x⊗ y) T ⊗(In ⊗(A− BK1))− (x⊗ y) T ⊗(L⊗ BK2) = x T ⊗ y T (A− BK1)− x T L⊗ y TBK2 = x T ⊗(y T (A− BK1 −λBK2) = x T ⊗(y T θ) = (x⊗ y) T θ θ ⌣ L (x⊗ y) T (x⊗ y) T ⌣ M = (x TM)⊗(y TC) ( ⌣ L, ⌣ M) (L, M) 即 是 的一个特征值并且 是相应的左 特征向量。有 ，根据 PBH 判据，即 不可控，这与已知其可控矛盾，因 此 可控，证毕。 我们得到了模型 (5) 下的多智能体系统能控 的必要性条件。通常来说，我们更希望能得到充 要条件，并且通过充分条件来推断该系统是否可 控。接下来讨论一般线性多智能体系统可控的充 分条件。 (L, M) λs (0 < s ⩽ n,s ∈ (A− BK1 −λBK2,C) A− BK1 −λsBK2 ( ⌣ L, ⌣ M) 定理 2 在一般线性多智能体系统 (5) 中，如 果网络拓扑结构可控即 可控，并且每个智 能体的动态可控即对于 L 的每一个特征值 ， N)，有矩阵对 可 控，并且矩阵 之间不含有重复特 征值，那么该系统整体可控即 可控。 ( ⌣ L, ⌣ 证明 假设 M) 不可控。L 是对称矩阵， ·266· 智 能 系 统 学 报 第 15 卷
第2期 陈万金，等：基于拓扑结构和个体动态层面的多智能体系统可控性分析 ·267· 有ULU=diag(a1,…,dn),总能找到一个正交矩阵 例1 U使得上式成立，其中：为L的特征值。引入两 个矩阵L、M,由L、M通过相似变换得到 i=(U⑧lp)L(U⑧p)=blockding(A-BK1-,BKz) M=(Ur⑧I)M=U酽M⑧C s=(1,2,…,m)。因为(L,0不可控且Ur⑧12 以上为模型（⑤）中各矩阵参数，此时该系统拓 非奇异，所以（亿，0不可控。又因为立是一个对 扑结构矩阵对(L,)以及每个智能体的状态矩阵 角块矩阵，并且矩阵块中无重复特征值导致 对(A-BK1-BK2,C)是可控的，然而系统整体矩 (亿，)不可控的偶然性情况，则存在一个相应的 阵对(L,M0不可控。 矩阵对(A-BK1-入BK2,(UTM0,⑧C)不可控，这里 以下对这种状况进行进一步说明。在本例 用M,表示矩阵M的第s行。这表明(L,M)在的 中3个矩阵块的特征值为-1、-2、-2、-4、-4、 (UM),=0情况下不可控或在(U严M,≠0的情况 一8。以特征值-2为例，其特征向量分别为 [1-10000F、[001-100F,令 下(A-BK1-ABK2,C不可控，出现矛盾，所以 2=a1-10000]+b[001-100]= (L.0可控，证毕。 [a-ab-b00],显然存在一组不全为0的 定理2可以极大地减少判断系统可控性计 实数a,b使得，M=0。所以根据PBH判据， 算的复杂程度，用计算维数较低的(L,M), (亿，不可控，进而系统整体不可控。 (A-BK1-BK2,C)代替计算维度较高的（亿，M0。 以上仅仅讨论的是单领导者情况下，当取多 定理2限定了矩阵块中不出现重复特征值的情 领导者时，矩阵块若出现重复特征值，系统不一 况。如果去掉这一限制，那么当（立，0不可控 定不可控。 时，并不能说明立所含的矩阵块A-BK1-1,BK2 例2取与上例相同的矩阵参数，取1、3节 与M中矩阵块(U严M),⑧C组成的矩阵对一定含 点为领导者，则有 有不可控的情况，可能所含矩阵对全部可控，但 M=100 矩阵对（亿，不可控，进而系统整体矩阵对 001 (亿，)不可控，此时充分性并不成立。因此，此定 此时系统拓扑结构与个体状态均能控，并且 该系统矩阵L有重复特征值（同上例），但是系统 理只适用于系统矩阵不含有重复特征值的情况。 可控性判别矩阵秩为6，系统整体可控。 由于系统矩阵的复杂程度，其特征值是否重复很 图1表示在该例系统参数下实现3个智能体 难去控制，因此解决这个问题具有很高的难度并 由任意初始位置组成三角形，表示该系统可控。 且条件比较苛刻，需要研究构成系统矩阵所需要 x、x2分别表示单个智能体的两个状态。本例说 的状态矩阵、内部耦合矩阵等，并且还要特定的 明在多领导者的情形下，当立中的矩阵块出现重 拓扑结构。如果想要达到系统矩阵不含有重复特 复特征值时，多智能体系统可控性不确定。因 征值这一条件，其中一条可行的方法如下：对于 此，不能单单依靠立是否出现相同的特征值就直 模型(5)（式(5）)下的一般线性多智能体系统，矩 接判定系统整体可控性，这样会使得构建可控系 阵参数同时满足以下条件，则系统矩阵工中不含 统的选择性大大减少。 有重复特征值。 1.8 1)智能体状态矩阵A-BK1与系统拉普拉斯 1.6 矩阵L各自不含有重复特征值且两者无任一特征 1.4 值相同。 1.2 2)内部耦合矩阵BK2的元素与智能体的状态 81.0 矩阵A-BK的元素互为相反数。 0.8 3)智能体状态矩阵A-BK:的任意两个特征 0.6 一X1 值之间的倍数不等于拉普拉斯矩阵L的任意一个 0.4 特征值+1。 0.2 0 0.5 1.01.52.02.53.03.54.0 3.2重复特征值导致不充分性的原因 以下给出一个实例，说明系统矩阵中存在重 图13节点可控性 复特征值对定理2充分性的影响以及原因。 Fig.1 Controllability diagram with 3 nodes
U T LU = diag(λ1,··· , λn) λi L˜、M˜ ⌣ L、 ⌣ M 有 ，总能找到一个正交矩阵 U 使得上式成立，其中 为 L 的特征值。引入两 个矩阵 ，由 通过相似变换得到 L˜ = (U T ⊗ Ip) ⌣ L(U ⊗ Ip) = blockding(A− BK1 −λsBK2) M˜ = (U T ⊗ Ip) ⌣ M = U T M ⊗C s = (1,2,··· ,n) ( ⌣ L, ⌣ M) U T ⊗ Ip (L˜, M˜ ) L˜ (L˜, M˜ ) (A− BK1 −λsBK2,(U TM)s ⊗C) (L, M) (U TM)s = 0 (U TM)s , 0 (A− BK1 −λBK2,C) ( ⌣ L, ⌣ M) 。因为 不可控且 非奇异，所以 不可控。又因为 是一个对 角块矩阵，并且矩阵块中无重复特征值导致 不可控的偶然性情况，则存在一个相应的 矩阵对 不可控，这里 用 Ms 表示矩阵 M 的第 s 行。这表明 在的 情况下不可控或在 的情况 下 不可控，出现矛盾，所以 可控，证毕。 (L, M) (A− BK1 −λBK2,C) ( ⌣ L, ⌣ M) (L˜, M˜ ) L˜ A− BK1 −λsBK2 M˜ (U TM)s ⊗C (L˜, M˜ ) ( ⌣ L, ⌣ M) ⌣ L 定理 2 可以极大地减少判断系统可控性计 算的复杂程度，用计算维数较低的 ， 代替计算维度较高的 。 定理 2 限定了矩阵块中不出现重复特征值的情 况。如果去掉这一限制，那么当 不可控 时，并不能说明 所含的矩阵块 与 中矩阵块 组成的矩阵对一定含 有不可控的情况，可能所含矩阵对全部可控，但 矩阵对 不可控，进而系统整体矩阵对 不可控，此时充分性并不成立。因此，此定 理只适用于系统矩阵不含有重复特征值的情况。 由于系统矩阵的复杂程度，其特征值是否重复很 难去控制，因此解决这个问题具有很高的难度并 且条件比较苛刻，需要研究构成系统矩阵所需要 的状态矩阵、内部耦合矩阵等，并且还要特定的 拓扑结构。如果想要达到系统矩阵不含有重复特 征值这一条件，其中一条可行的方法如下：对于 模型 (5)（式 (5)）下的一般线性多智能体系统，矩 阵参数同时满足以下条件，则系统矩阵 中不含 有重复特征值。 1) 智能体状态矩阵 A− BK1 与系统拉普拉斯 矩阵 L 各自不含有重复特征值且两者无任一特征 值相同。 BK2 A− BK1 2) 内部耦合矩阵 的元素与智能体的状态 矩阵 的元素互为相反数。 3) 智能体状态矩阵 A− BK1 的任意两个特征 值之间的倍数不等于拉普拉斯矩阵 L 的任意一个 特征值+1。 3.2 重复特征值导致不充分性的原因 以下给出一个实例，说明系统矩阵中存在重 复特征值对定理 2 充分性的影响以及原因。 例 1 A = [ 0.5 1 1 0.5 ] ,K1 = [ 2 1.5 1.5 2 ] ,C = [ 1 0 ] B = I2,K2 = [ 1.5 0.5 0.5 1.5 ] , L = 1 −1 0 −1 2 −1 0 −1 1 , M = 1 0 0 (L, M) (A− BK1 −λBK2,C) ( ⌣ L, ⌣ M) 以上为模型 (5) 中各矩阵参数，此时该系统拓 扑结构矩阵对 以及每个智能体的状态矩阵 对 是可控的，然而系统整体矩 阵对 不可控。 [ 1 −1 0 0 0 0 ] T [ 0 0 1 −1 0 0 ] T u T −2 = a[ 1 −1 0 0 0 0 ]+b[ 0 0 1 −1 0 0 ] [ a −a b −b 0 0 ] u T −2M˜ = 0 (L˜, M˜ ) 以下对这种状况进行进一步说明。在本例 中 3 个矩阵块的特征值为−1、−2、−2、−4、−4、 − 8 。以特征值 − 2 为例，其特征向量分别为 、 ， 令 = ，显然存在一组不全为 0 的 实数 a,b 使得 。所以根据 PBH 判据， 不可控，进而系统整体不可控。 以上仅仅讨论的是单领导者情况下，当取多 领导者时，矩阵块若出现重复特征值，系统不一 定不可控。 例 2 取与上例相同的矩阵参数，取 1、3 节 点为领导者，则有 M = [ 1 0 0 0 0 1 ]T ⌣ L 此时系统拓扑结构与个体状态均能控，并且 该系统矩阵 有重复特征值 (同上例)，但是系统 可控性判别矩阵秩为 6，系统整体可控。 xi1、xi2 L˜ L˜ 图 1 表示在该例系统参数下实现 3 个智能体 由任意初始位置组成三角形，表示该系统可控。 分别表示单个智能体的两个状态。本例说 明在多领导者的情形下，当 中的矩阵块出现重 复特征值时，多智能体系统可控性不确定。因 此，不能单单依靠 是否出现相同的特征值就直 接判定系统整体可控性，这样会使得构建可控系 统的选择性大大减少。 0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 x1 x2 x3 xi1 xi2 图 1 3 节点可控性 Fig. 1 Controllability diagram with 3 nodes 第 2 期 陈万金，等：基于拓扑结构和个体动态层面的多智能体系统可控性分析 ·267·
·268· 智能系统学报 第15卷 3.3利用特征值重数对系统不可控的判定条件 线性无关的特征向量“1、u2、“序。对u1、42进 受到文献[15]的启发，事实上，当遇到系统 行线性组合，得到新的特征向量42=au1+bu2, 矩阵含有重复特征值的情况时，根据系统矩阵特 选取合适的一组不全为0的数a,b,a,beR,使得 征值的重数也能判断一类多智能体系统整体不 u2的第一个元素为0。同样地，分别对“、“月 可控。 和42、“B进行线性组合，得到“、423，它们的 定理3对于多智能系统（⑤），当L为实对称 第一个元素均为0。至此，得到了3个新的对应 矩阵，若出现以下任意一种情况，系统不可控。 于的特征向量，并且它们的第1个元素均为 1)M中只有单个1元素，此时L出现重复特 0。现在考虑特征向量的第2个元素。与找第一 征值，系统整体不可控。 个元素的方法相同，对这3个特征向量中的任意 2)M中有1个1元素，此时L出现某一特征 两个进行线性组合，然后得到另外3个第1和第 值代数重数（≥3），系统整体不可控。 2个元素都为0的特征向量。重复以上步骤，直 证明以下对定理中包含的情况一一证明。 到得到一个前m个元素都为0的特征向量，将它 1)取单领导者，且外部输入控制信号只影响 记为aed,它有如下形式： 领导者的一种状态。对于一个具有n个个体的多 以=[00j H5一闭 智能体系统，用1,2，n将它们标注。令A-BK 根据PBH判据，aM=O,此时系统不可控。 为每个智能体的s阶状态矩阵。令第一个智能体 ②多领导者系统。对于具有1个领导者的多 为领导者，那么M=e1。令外部输入控制矩阵 智能体系统，假设前1个智能体为领导者，分别标 C=e,1≤i≤s,此时M共有n×s个元素并且有如 注为m1,2,…,m。那么M具有如下形式： 下形式： M=[e1e2…e,】 M=【0-l0001 其中e:的维度为n。假设外部输入控制矩阵C有 令L的特征值为（亿1,2，…，，……，n)并且互 m(2≤m≤s)个元素为1，且为前m个元素，那么M 不相同，其中，(1≤i,j≤ns,i≠)的代数重数为 具有如下形式： 2。此时有两个对应于入的线性无关的特征向量 M=[m1m2…m] “1、u2。对这两个特征向量进行线性组合，得到 m=[l00Q0 对应于，的一个新的特征向量4j,4=aun+b2, m%=[00 10000 加 a,beR并且a,b不同时为0。我们总能找到这样 (n-2)s 一组a,b使得u,某一个位置的元素为0，这个位 置对应于M中元素为1的位置。即w有如下形式： m=[00l001 (n-1)s 率…0…水*…米 假设中存在一个代数重数为3的特征值 ,(1≤j≤ns-2),其余特征值互不相同，那么入相 此时uM=0O,根据PBH判据，此多智能体系统不 应有3个线性无关的特征向量u1、u2、“3,对这 可控。 3个特征向量两两线性组合，得到3个新的特征 2)M中有1个1元素，此时有两种情况。 向量，并且它们第一个元素均为0。再对这3个 ①取单领导者系统，外部输入控制信号影响 新的特征向量两两线性组合，对这一过程重复进 领导者的多种状态。即外部输入控制矩阵有 行，直至得到一个新的特征向量，它相应于M元 m个元素为1(2≤m≤s),可以是C中任意m个元 素为1的位置上的元素都为O。根据PBH判据， 素的位置，假设前m个元素为1，则C具有如下 此特征向量在M的零空间中，因此系统不可控， 形式： 证毕。 C=[1001 以下给出两个实例，验证定理3中2种情况。 例3 1201 那么M具有如下形式： =-1 .K M=[J0000] 0 3 1 0 (n-1s 0 令L的特征值为01，…，-2)并且互不相同，其中 (1≤j≤s-2)的代数重数为3，对应于，有3个 1-2 w-8
3.3 利用特征值重数对系统不可控的判定条件 受到文献 [15] 的启发，事实上，当遇到系统 矩阵含有重复特征值的情况时，根据系统矩阵特 征值的重数也能判断一类多智能体系统整体不 可控。 ⌣ 定理 3 对于多智能系统 (5)，当 L 为实对称 矩阵，若出现以下任意一种情况，系统不可控。 ⌣ M ⌣ 1） 中只有单个 1 元素，此时 L 出现重复特 征值，系统整体不可控。 ⌣ M ⌣ L ⩾ 2) 中有 l 个 1 元素，此时 出现某一特征 值代数重数（ 3），系统整体不可控。 证明 以下对定理中包含的情况一一证明。 1,2,···n A− BK1 M = e1 C = ei ,1 ⩽ i ⩽ s ⌣ M n× s 1）取单领导者，且外部输入控制信号只影响 领导者的一种状态。对于一个具有 n 个个体的多 智能体系统，用 将它们标注。令 为每个智能体的 s 阶状态矩阵。令第一个智能体 为领导者，那么 。令外部输入控制矩阵 ，此时 共有 个元素并且有如 下形式： ⌣ M = [ 0···1···0 | {z } s 0···0 |{z} (n−1)s ] ⌣ L (λ1, λ2,··· , λi ,··· , λj ,··· , λns) λj(1 ⩽ i, j ⩽ ns,i , j) λj uj1、uj2 λj uj uj = auj1 +buj2 a,b ∈ R uj ⌣ M uj 令 的特征值为 并且互 不相同，其中 的代数重数 为 2。此时有两个对应于 的线性无关的特征向量 。对这两个特征向量进行线性组合，得到 对应于 的一个新的特征向量 ， ， 并且 a，b 不同时为 0。我们总能找到这样 一组 a，b 使得 某一个位置的元素为 0，这个位 置对应于 中元素为 1 的位置。即 有如下形式： uj = [ ∗···0 i ···∗ | {z } s ∗···∗ |{z} (n−1)s ] u T j ⌣ 此时 M = 0 ，根据 PBH 判据，此多智能体系统不 可控。 ⌣ 2) M 中有 l 个 1 元素，此时有两种情况。 (2 ⩽ m ⩽ s) ① 取单领导者系统，外部输入控制信号影响 领导者的多种状态。即外部输入控制矩阵有 m 个元素为 1 ，可以是 C 中任意 m 个元 素的位置，假设前 m 个元素为 1，则 C 具有如下 形式： C = [ 1···1 |{z} m 0···0 | {z } s ] ⌣ 那么 M 具有如下形式： ⌣ M = [ 1···1 |{z} m 0···0 |{z} s−m 0···0 |{z} (n−1)s ] ⌣ L (λ1,··· , λns−2) λj(1 ⩽ j ⩽ ns−2) λj 令 的特征值为 并且互不相同，其中 的代数重数为 3，对应于 有 3 个 uj1、uj2、uj3 uj1、uj2 uj12 = auj1 +buj2 a,b ∈ R uj12 uj1、uj3 uj2、uj3 uj13、uj23 λj uneed 线性无关的特征向量 。对 进 行线性组合，得到新的特征向量 ， 选取合适的一组不全为 0 的数 a,b， ，使得 的第一个元素为 0。同样地，分别对 和 进行线性组合，得到 ，它们的 第一个元素均为 0。至此，得到了 3 个新的对应 于 的特征向量，并且它们的第 1 个元素均为 0。现在考虑特征向量的第 2 个元素。与找第一 个元素的方法相同，对这 3 个特征向量中的任意 两个进行线性组合，然后得到另外 3 个第 1 和第 2 个元素都为 0 的特征向量。重复以上步骤，直 到得到一个前 m 个元素都为 0 的特征向量，将它 记为 ，它有如下形式： u T need = [ 0···0 |{z} m ∗···∗ |{z} ns−m ] u T need ⌣ 根据 PBH 判据， M = 0 ，此时系统不可控。 n1,n2,··· ,nl M ② 多领导者系统。对于具有 l 个领导者的多 智能体系统，假设前 l 个智能体为领导者，分别标 注为 。那么 具有如下形式： M = [ e1 e2 ··· el ] ei m(2 ⩽ m ⩽ s) ⌣ M 其中 的维度为 n。假设外部输入控制矩阵 C 有 个元素为 1，且为前 m 个元素，那么 具有如下形式： ⌣ M = [ m1 m2 ··· ml ] mT 1 = [ 1···1 |{z} m 0···0 |{z} s−m 0···0 |{z} (n−1)s ] mT 2 = [ 0···0 |{z} s 1···1 |{z} m 0···0 |{z} s−m 0···0 |{z} (n−2)s ] . . . mT l = [ 0···0 |{z} (n−1)s 1···1 |{z} m 0···0 |{z} s−m ] ⌣ L λj(1 ⩽ j ⩽ ns−2) λj uj1、uj2、uj3 ⌣ M ⌣ M 假设 中存在一个代数重数为 3 的特征值 ，其余特征值互不相同，那么 相 应有 3 个线性无关的特征向量 ，对这 3 个特征向量两两线性组合，得到 3 个新的特征 向量，并且它们第一个元素均为 0。再对这 3 个 新的特征向量两两线性组合，对这一过程重复进 行，直至得到一个新的特征向量，它相应于 元 素为 1 的位置上的元素都为 0。根据 PBH 判据， 此特征向量在 的零空间中，因此系统不可控， 证毕。 以下给出两个实例，验证定理 3 中 2 种情况。 例 3 A = 1 2 0 −1 1 2 0 3 1 ,K1 = −1 3 0 1 −2 3 0 4 −1 ,C = 1 1 0 ,B = I3 K2 = −2 1 0 1 −3 1 0 1 −2 , L = 1 −1 0 −1 2 −1 0 −1 1 , M = 1 0 0 ·268· 智 能 系 统 学 报 第 15 卷