«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2020, Vol. 15 Issue (2): 264-270  DOI: 10.11992/tis.201901006
0

引用本文  

陈万金, 纪志坚. 基于拓扑结构和个体动态层面的多智能体系统可控性分析[J]. 智能系统学报, 2020, 15(2): 264-270. DOI: 10.11992/tis.201901006.
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. DOI: 10.11992/tis.201901006.

基金项目

国家自然科学基金项目(61873136,61603288,61374062)

通信作者

纪志坚. E-mail:jizhijian@pku.org.cn

作者简介

陈万金,硕士研究生,主要研究方向为多智能体系统;
纪志坚,博士,教授,博士生导师,主要研究方向为群体系统动力学与协调控制、复杂网络、切换动力系统的分析与控制、系统生物以及基于网络的控制系统等。主持国家自然科学基金项目4项。发表学术论文110余篇

文章历史

收稿日期:2019-01-07
网络出版日期:2019-04-11
基于拓扑结构和个体动态层面的多智能体系统可控性分析
陈万金 , 纪志坚     
青岛大学 自动化学院,山东 青岛 266071
摘要:针对一般线性多智能体系统中网络拓扑及个体动态这两个层面的可控性对系统整体可控性的关系进行了研究,提出了一种新的描述一般线性多智能体系统的模型。利用PBH(Popov-Belevitch-Hautus)判据,得到并证明了在此模型下多智能体系统可控性在网络拓扑结构与个体动态层面的充要条件。结合具体的例子解释了系统矩阵中出现重复特征值时对定理2充分性的影响,并且提供了一种避免重复特征值出现的方法。特别地,推导出了此模型下系统矩阵为实对称矩阵这一特殊情况时可以判定该系统不可控的两种判定条件,即比较系统矩阵中最大的特征值代数重数与控制矩阵中1元素的个数,满足条件即判定系统不可控。
关键词多智能体系统    可控性    线性定常系统    拓扑    邻居信息交互    特征值    特征向量    控制理论    
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.
Key words: multi-agent system    controllability    linear time-invariant systems    topology    local interaction    eigenvalue    eigenvector    control theory    

近二三十年,随着工业技术的发展迭代,得益于计算机、传感器、机器人等技术的发展,多智能体系统(multi-agent system,MAS)也越来越常见。不止控制领域,众多领域开始对其进行了研究[1-5]。多智能体系统实质上是多个个体组成的一个集合,这些个体每个都具有一定的接受与处理信息并且执行相应命令的能力。与传统的单个个体为一个系统相比,多智能体系统具有非常显著的优势,并且相关技术已经在智能交通系统[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]考察了完全图的能控性,文献[1429]研究了无向树图的可控性。但是多智能体系统具有“个体动态+通信拓扑”的特点[30],所以两者都对系统整体可控性有很大影响。文献[26]研究了扩散耦合多智能体系统的可控性的充要条件,网络拓扑结构与个体动态同时可控时整个系统便是可控的。文献[30]提出文献[26]结论的不足之处,说明此方面的结论并不完美,不能精确地描述网络拓扑结构与个体动态的可控性对系统整体可控性的影响,这是本文着力要解决的问题之一。

本文将研究一般线性多智能体系统的可控性与网络拓扑结构和个体动态可控性的关系,得到了相对完整的结论。另外,从特征值的角度出发,找到了系统矩阵中重复特征值数量与系统不可控之间的关系,并进一步整理了系统矩阵不含重复特征值的条件,给出了一类根据系统矩阵中重复特征值的重数判定系统不可控的判定条件。

1 预备知识

本节将定义本文中要用的数学符号与图论中基本概念。 ${{{e}}_i}$ 表示第 $i\left(i \in {\rm{N}}\right)$ 个元素为1,其余元素为0的列向量。如 ${{{e}}_1} = {\left[ {\begin{array}{*{20}{c}} 1&0& \cdots &0 \end{array}} \right]^{\rm{T}}}$ ${{\bf{R}}^n}$ 表示n维实向量空间, ${{\bf{R}}^{m \times n}}$ 表示实 $m \times n$ 阶矩阵的集合。对于一个集合S ${\rm{|}}S{\rm{|}}$ 表示集合的元素个数。 $ * $ 表示任意实数。图论概念: $G(V,E)$ 表示一个n节点的拓扑图。其中这个图的点集和边集分别用 $V = \{ {v_1},{v_2} \cdots {v_n}\} $ $E = \{ ({v_i},{v_j})|{v_i},{v_j} \in V,i \ne j\} $ 表示,不考虑自环的情况,即 $({v_i},{v_j}) \in E$ 。拓扑图分为有向图和无向图,两者的主要区别在于边的定义。对有向图来说, $({v_i},{v_j})$ 表示有一条点i指向点j的有向边,表示节点j收到来自i的信息,即边 $({v_i},{v_j}) \ne $ $ ({v_j},{v_i})$ 。对于无向图则有 $({v_i},{v_j}) = ({v_j},{v_i})$ ,即vi vj之间有边的连接,两个点则会相互接收到对方信息。如果点vj接受到点vi的信息,则称点vivj的邻居(neighbor)。点vi的邻居集表示为 ${N_{(i)}}$ 。对无向图来说,若 $({v_i},{v_j}) \in E$ ,则点vi是点vj的邻居,同时点vj也是点vi的邻居。 ${d_i} = {\rm{ }}|{N_{(i)}}|$ 表示点vi 的度(degree)。无向图G的度矩阵(degree matrix)用 $D(G) = {\rm diag}({d_1},{d_2}, \cdots ,{d_n})$ 表示。A(G)表示图G的邻接矩阵(adjacency matrix),在有向加权图中, ${{A}} = {({a_{ij}})_{n \times n}}$ 定义为

${a_{ij}} = \left\{ {\begin{array}{*{20}{l}} {{\rm{ }}{w_{ij}}},&{(j,i) \in E(G)} \\ 0,&{{\text{其他}}} \end{array}} \right.$

式中:wij表示边的权重,即点j对点i的影响程度。本文权重皆取 ${w_{ij}} = 1$ 。在无向图中,边 $({v_i},{v_j})$ 必然会有相同权重的边 $({v_j},{v_i})$ 与之对应,所以邻接矩阵A(G)为对称矩阵。拉普拉斯矩阵(Laplacian matrix)是相较于度矩阵的另一种表达图中顶点关系的一种矩阵,也是多智能体系统的研究中最常用的矩阵, ${{L}}(G) = {{D}}(G) - {{A}}(G)$ 。另外拉普拉斯矩阵可以定义如下:

${l_{ij}} = \left\{ {\begin{array}{*{20}{l}} {\displaystyle\sum\limits_{j = 1,j \ne i}^n {{a_{ij}}} },&{i = j} \\ { - {a_{ij}}},&{i \ne j} \end{array}} \right.$

由以上定义可知,在无向图中,矩阵L(G)的对角线元素是相应行其余元素和的相反数,即L(G)的每行元素之和为零,并且是实对称矩阵,即L(G)是可对角化的。

文中判别可控性主要用到如下引理。

引理1 秩判据[31],对于线性定常连续系统 $\dot {{x}} = {{Ax}} + {{Bu}}$ ,令AB分别为系统的状态矩阵和控制输入矩阵。当且仅当可控性判别矩阵C的秩满足等式:

${\rm rank}({{C}}) = \left[ {\begin{array}{*{20}{c}} {{B}}&{{{AB}}}& \cdots &{{{{A}}^{n - 1}}} \end{array}{{B}}} \right] = n$

系统是完全可控的。

PBH判据[11],对于系统 $\dot {{x}} = {{Ax}} + {{Bu}}$ ,当且仅当不存在非零向量v,满足以下等式:

$\left\{ {\begin{array}{*{20}{c}} {{{{B}}^{\rm{T}}}{{v}} = 0} \\ {{{Av}} = {\textit{λ}} {{v}}} \end{array}} \right.$

该系统是可控的。

在本文中,没有特殊说明的情况下,讨论的均是无向非加权固定拓扑下的系统。

2 一般性模型的建立

考虑一个由n个完全相同的智能体构成的智能体系统,用集合 $V = \{ 1,2, \cdots ,n\} $ 表示其包含的智能体集,并用 $1,2, \cdots n$ 依次将所含的智能体标注。将智能体按照是否接受外部控制输入分为领导者与跟随者,假设有m个领导者,则领导者集合表示为 ${V_L} = \{ {v_1},{v_2}, \cdots ,{v_m}\} $ ( $1 \leqslant m \leqslant n$ ), ${V_F} = V\backslash {V_L}$ 表示其跟随者集合。每一个跟随者 ${v_i} \in {V_F}$ ,线性动力学方程描述为

${{{\dot x}}_i} = {{A}}{{{x}}_i} + {{B}}{{{u}}_i}$ (1)

对于每一个领导者 ${v_i} \in {V_L}$ ,线性动力学方程描述为

${{{\dot x}}_i} = {{A}}{{{x}}_i} + {{B}}{{{u}}_i} + {{C}}{{{z}}_l}$ (2)

式中: ${{A}} \in {{{R}}^{m \times m}}$ ${{B}} \in {{{R}}^{m \times p}}$ ${{C}} \in {{{R}}^{m \times q}}$ 分别表示智能体vi的状态; ${{{u}}_i} \in {{{R}}^q}$ 表示该系统中单个智能体接受其余智能体信息的影响; ${{z}}_l$ 表示对单个智能体的外部输入控制。对于每一个智能体,基于该系统的邻居关系的耦合规则 ${{u}}_i$ 如下:

${{{u}}_i} = - {{{K}}_1}{{{x}}_i} + \sum\limits_{{v_j} \in {N_{(i)}}} {{a_{ij}}} {{{K}}_2}({{{x}}_j} - {{{x}}_i})$ (3)

式中: ${{{K}}_1}$ ${{{K}}_2} \in {{{R}}^{p \times m}}$ 为可以设计的反馈增益;aij表示智能体之间信息传递的强度。定义 ${{x}} = {\rm col} $ $({{{x}}_1},{{{x}}_2}, \cdots ,{{{x}}_n})$ ${{z}} = {\rm col}({{{z}}_1},{{{z}}_2}, \cdots ,{{{z}}_l})$ ,信息传递强度都相同且令 ${a_{ij}} = 1$ $i \ne j$ ,则上面的多智能体系统表达式可以整合为如下形式:

${{\dot x}} = [{{{I}}_n} \otimes ({{A}} - {{B}}{{{K}}_1}) - {{L}} \otimes {{B}}{{{K}}_2}]{{x}} + ({{M}} \otimes {{C}}){{z}}$ (4)

$ \otimes $ 表示克罗内克积(Kronecker product)[32]L为图G的拉普拉斯矩阵,M表示领导者与跟随者的身份,定义如下,vl表示领导者:

${{{M}}_{il}} = \left\{ {\begin{array}{*{20}{c}} 1&{{\rm{if\; }}i = l} \\ 0&{\text{其他}} \end{array}} \right.$

式(4)可以简化为

$\dot {{x}} = {\overset{\smile} {{L}}} {{x}} + {\overset{\smile} {{M}}} {{z}}$ (5)

文献[23]中所讨论的模型可以视为模型(4)(式(4))中K1为零矩阵的一种特殊情况。在第3节我们将讨论在模型(4)下一般线性多智能体系统的可控性问题。

3 主要结论

一般线性多智能体系统的可控性,根据系统的结构特点,可以细化成两个方面。一个是该系统的拓扑结构的可控性,另一个是系统中智能体个体动态的可控性。本节将研究这两个层面的可控性与多智能体系统整体可控性的关系。以下用矩阵对 $({{L}},{{M}})$ $({{A}} - {{B}}{{{K}}_1} -{\textit{λ}}{{B}}{{{K}}_2},{{C}})$ ,( ${\textit{λ}} $ 为矩阵 ${{L}}$ 的特征值),分别表示多智能体系统中网络拓扑结构可控和个体动态可控。

3.1 一般线性多智能体系统可控的必要性与充分性条件

定理1 在一般线性多智能体系统(5)中,如果该系统整体可控即 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 可控,则该系统的网络拓扑结构可控即 $({{L}},{{M}})$ 可控,同时每个智能体的动态可控,即对于每一个拉普拉斯矩阵L的特征值 ${\textit{λ}}$ $({{A}} - {{B}}{{{K}}_1} - {\textit{λ}} {{B}}{{{K}}_2},{{C}})$ 是可控的。

证明 这里只证明 $({{L}},{{M}})$ 是可控的, $({{A}} - {{B}}{{{K}}_1} -$ $ \lambda {{B}}{{{K}}_2},{{C}})$ 的可控性可以用同样的方法证明。

假设 $({{L}},{{M}})$ 不可控,根据PBH判据,则必然存在非零向量 ${{x}} \in {{{R}}^n}$ 满足 ${{{x}}^{\rm{T}}}{{L}} = {\textit{λ}}{{{x}}^{\rm{T}}},{{{x}}^{\rm{T}}}{{M}} = 0$ 。令 ${\rm{\theta}} ,{{y}}$ 分别为矩阵 ${{A}} - {{B}}{{{K}}_1} -{\textit{λ}}{{B}}{{{K}}_2}$ 的一个特征值与相应的左特征向量。那么有

$\begin{split} {\rm{ }}{({{x}} \otimes {{y}})^{\rm{T}}}& \;{{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over L} }} ={({{x}} \otimes {{y}})^{\rm{T}}}({{{I}}_n} \otimes ({{A}} - {{B}}{{{K}}_1} - {{L}} \otimes {{B}}{{{K}}_2})) = \\ & \quad {({{x}} \otimes {{y}})^{\rm{T}}} \otimes ({{{I}}_n} \otimes ({{A}} - {{B}}{{{K}}_1})) - \\ & \qquad {({{x}} \otimes {{y}})^{\rm{T}}} \otimes ({{L}} \otimes {{B}}{{{K}}_2}) = \\ & \;{{{x}}^{\rm{T}}} \otimes {{{y}}^{\rm{T}}}({{A}} - {{B}}{{{K}}_1}) - {{{x}}^{\rm{T}}}{{L}} \otimes {{{y}}^{\rm{T}}}{{B}}{{{K}}_2} = \\ & \quad {{{x}}^{\rm{T}}} \otimes ({{{y}}^{\rm{T}}}({{A}} - {{B}}{{{K}}_1} - {\textit{λ}} {{B}}{{{K}}_2}) = \\ & \qquad {{{x}}^{\rm{T}}} \otimes ({{{y}}^{\rm{T}}}{\rm{\theta }}) = {({{x}} \otimes {{y}})^{\rm{T}}}{\rm{\theta }} \end{split}$

${\rm{\theta}} $ ${\overset{\smile} {{L}}}$ 的一个特征值并且 ${({{x}} \otimes {{y}})^{\rm{T}}}$ 是相应的左特征向量。有 ${({{x}} \otimes {{y}})^{\rm{T}}}{\overset{\smile} {{M}}} = ({{{x}}^{\rm{T}}}{{M}}) \otimes ({{{y}}^{\rm{T}}}{{C}})$ ,根据PBH判据,即 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 不可控,这与已知其可控矛盾,因此 $({{L}},{{M}})$ 可控,证毕。

我们得到了模型(5)下的多智能体系统能控的必要性条件。通常来说,我们更希望能得到充要条件,并且通过充分条件来推断该系统是否可控。接下来讨论一般线性多智能体系统可控的充分条件。

定理2 在一般线性多智能体系统(5)中,如果网络拓扑结构可控即 $({{L}},{{M}})$ 可控,并且每个智能体的动态可控即对于L的每一个特征值 ${\lambda _s}$ $(0 < s \leqslant n,s \in $ N),有矩阵对 $({{A}} - {{B}}{{{K}}_1} - {\textit{λ}}{{B}}{{{K}}_2},{{C}})$ 可控,并且矩阵 ${{A}} - {{B}}{{{K}}_1} - {{\textit{λ}}_s}{{B}}{{{K}}_2}$ 之间不含有重复特征值,那么该系统整体可控即 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 可控。

证明 假设 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 不可控。L是对称矩阵,有 ${{{U}}^{\rm T}}{{LU}} = {\rm diag}({{\textit{λ}}_1}, \cdots ,{\lambda _n})$ ,总能找到一个正交矩阵U使得上式成立,其中 ${{\textit{λ}}_i}$ L的特征值。引入两个矩阵 ${{\tilde L}}{\text{、}}{{\tilde M}}$ ,由 ${\overset{\smile} {{L}}}{\text{、}}{\overset{\smile} {{M}}}$ 通过相似变换得到

$\begin{split} {{\tilde L}} = ({{{U}}^{\rm{T}}} \otimes {{{I}}_p})& {\overset{\smile} {{L}}}({{U}} \otimes {{{I}}_p}) = {\rm blockding}({{A}} - {{B}}{{{K}}_1} - {\lambda _s}{{B}}{{{K}}_2}) \\ & {{\tilde M}} = ({{{U}}^{\rm{T}}} \otimes {{{I}}_p}){\overset{\smile} {{M}}} = {{{U}}^T}{{M}} \otimes {{C}} \end{split} $

$s = \left( {1,2, \cdots ,n} \right)$ 。因为 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 不可控且 ${{{U}}^{\rm{T}}} \otimes {{{I}}_p}$ 非奇异,所以 $({{\tilde L}},{{\tilde M}})$ 不可控。又因为 ${{\tilde L}}$ 是一个对角块矩阵,并且矩阵块中无重复特征值导致 $({{\tilde L}},{{\tilde M}})$ 不可控的偶然性情况,则存在一个相应的矩阵对 $({{A}} - {{B}}{{{K}}_1} - {\lambda _s}{{B}}{{{K}}_2},{({{{U}}^{\rm{T}}}{{M}})_s} \otimes {{C}})$ 不可控,这里用Ms表示矩阵M的第s行。这表明 $({{L}},{{M}})$ 在的 ${({{{U}}^{\rm{T}}}{{M}})_s} = 0$ 情况下不可控或在 ${({{{U}}^{\rm{T}}}{{M}})_s} \ne 0$ 的情况下 $({{A}} - {{B}}{{{K}}_1} - \lambda {{B}}{{{K}}_2},{{C}})$ 不可控,出现矛盾,所以 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 可控,证毕。

定理2可以极大地减少判断系统可控性计算的复杂程度,用计算维数较低的 $({{L}},{{M}})$ $({{A}} - {{B}}{{{K}}_1} - {\textit{λ}} {{B}}{{{K}}_2},{{C}})$ 代替计算维度较高的 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 。定理2限定了矩阵块中不出现重复特征值的情况。如果去掉这一限制,那么当 $({{\tilde L}},{{\tilde M}})$ 不可控时,并不能说明 ${{\tilde L}}$ 所含的矩阵块 ${{A}} - {{B}}{{{K}}_1} - {{\textit{λ}} _s}{{B}}{{{K}}_2}$ ${{\tilde M}}$ 中矩阵块 ${({{{U}}^{\rm{T}}}{{M}})_s} \otimes {{C}}$ 组成的矩阵对一定含有不可控的情况,可能所含矩阵对全部可控,但矩阵对 $({{\tilde L}},{{\tilde M}})$ 不可控,进而系统整体矩阵对 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 不可控,此时充分性并不成立。因此,此定理只适用于系统矩阵不含有重复特征值的情况。由于系统矩阵的复杂程度,其特征值是否重复很难去控制,因此解决这个问题具有很高的难度并且条件比较苛刻,需要研究构成系统矩阵所需要的状态矩阵、内部耦合矩阵等,并且还要特定的拓扑结构。如果想要达到系统矩阵不含有重复特征值这一条件,其中一条可行的方法如下:对于模型(5)(式(5))下的一般线性多智能体系统,矩阵参数同时满足以下条件,则系统矩阵 ${\overset{\smile} {{L}}}$ 中不含有重复特征值。

1) 智能体状态矩阵 ${{A}} - {{B}}{{{K}}_1}$ 与系统拉普拉斯矩阵L各自不含有重复特征值且两者无任一特征值相同。

2) 内部耦合矩阵 ${{B}}{{{K}}_2} $ 的元素与智能体的状态矩阵 ${{A}} - {{B}}{{{K}}_1} $ 的元素互为相反数。

3) 智能体状态矩阵 ${{A}} - {{B}}{{{K}}_1}$ 的任意两个特征值之间的倍数不等于拉普拉斯矩阵L的任意一个特征值+1。

3.2 重复特征值导致不充分性的原因

以下给出一个实例,说明系统矩阵中存在重复特征值对定理2充分性的影响以及原因。

例1

$ \begin{aligned} & {{A}} = \left[\!\!\! {\begin{array}{*{20}{c}} {0.5}&1\\ 1&{0.5} \end{array}}\!\!\! \right],{{{K}}_1} = \left[\!\!\! {\begin{array}{*{20}{c}} 2&{1.5}\\ {1.5}&2 \end{array}}\!\!\! \right],{{C}} = \left[\!\!\! {\begin{array}{*{20}{c}} {\rm{1}}\\ {\rm{0}} \end{array}}\!\!\! \right]\\ {{B}} = {{{I}}_2},&{{{K}}_2} = \left[\!\!\! {\begin{array}{*{20}{c}} {1.5}&{0.5}\\ {0.5}&{1.5} \end{array}}\!\!\! \right],{{L}} = \left[\!\!\! {\begin{array}{*{20}{r}} 1&{ - 1}&0\\ { - 1}&2&{ - 1}\\ 0&{ - 1}&1 \end{array}}\!\!\! \right], {{M}} = \left[\!\!\! {\begin{array}{*{20}{c}} 1\\ 0\\ 0 \end{array}}\!\!\! \right] \end{aligned}$

以上为模型(5)中各矩阵参数,此时该系统拓扑结构矩阵对 $({{L}},{{M}})$ 以及每个智能体的状态矩阵对 $({{A}} - {{B}}{{{K}}_1} - {\textit{λ}} {{B}}{{{K}}_2},{{C}})$ 是可控的,然而系统整体矩阵对 $({\overset{\smile} {{L}}},{\overset{\smile} {{M}}})$ 不可控。

以下对这种状况进行进一步说明。在本例中3个矩阵块的特征值为−1、−2、−2、−4、−4、−8。以特征值−2为例,其特征向量分别为 ${[\!\!\! \begin{array}{*{20}{c}} 1&{ - 1}&0&0&0&0 \end{array}\!\!\! ]^{\rm{T}}}$ ${[\!\!\! \begin{array}{*{20}{c}} 0&0&1&{ - 1}&0&0 \end{array}\!\!\! ]^{\rm{T}}}$ ,令 ${{u}}_{ - 2}^{\rm{T}} = a[\!\!\! \begin{array}{*{20}{c}} 1&{ - 1}\!&\!0\!&\!0\!&\!0\!&\!0 \end{array}\!\!\! ] + $ $b[\!\!\! \begin{array}{*{20}{c}} 0\!&\!0\!&\!1\!&\!{ - 1}\!&\!0\!&\!0 \end{array}\!\!\! ] $ = $ [\!\!\! \begin{array}{*{20}{c}} a&{ - a}&b&{ - b}&0&0 \end{array}\!\!\! ]$ ,显然存在一组不全为0的实数a,b使得 ${{u}}_{ - 2}^{\rm{T}}{{\tilde M}} = 0$ 。所以根据PBH判据, $({{\tilde L}},{{\tilde M}})$ 不可控,进而系统整体不可控。

以上仅仅讨论的是单领导者情况下,当取多领导者时,矩阵块若出现重复特征值,系统不一定不可控。

例2 取与上例相同的矩阵参数,取1、3节点为领导者,则有

${{M}} = {\left[ {\begin{array}{*{20}{c}} 1&0&0 \\ 0&0&1 \end{array}} \right]^{\rm{T}}}$

此时系统拓扑结构与个体状态均能控,并且该系统矩阵 ${\overset{\smile} {{L}}}$ 有重复特征值(同上例),但是系统可控性判别矩阵秩为6,系统整体可控。

图1表示在该例系统参数下实现3个智能体由任意初始位置组成三角形,表示该系统可控。 ${x_{i1}}{\text{、}}{x_{i2}}$ 分别表示单个智能体的两个状态。本例说明在多领导者的情形下,当 ${{\tilde L}}$ 中的矩阵块出现重复特征值时,多智能体系统可控性不确定。因此,不能单单依靠 ${{\tilde L}}$ 是否出现相同的特征值就直接判定系统整体可控性,这样会使得构建可控系统的选择性大大减少。

Download:
图 1 3节点可控性 Fig. 1 Controllability diagram with 3 nodes
3.3 利用特征值重数对系统不可控的判定条件

受到文献[15]的启发,事实上,当遇到系统矩阵含有重复特征值的情况时,根据系统矩阵特征值的重数也能判断一类多智能体系统整体不可控。

定理 3 对于多智能系统(5),当 ${\overset{\smile} {{L}}}$ 为实对称矩阵,若出现以下任意一种情况,系统不可控。

1) ${\overset{\smile} {{M}}}$ 中只有单个1元素,此时 ${\overset{\smile} {{L}}}$ 出现重复特征值,系统整体不可控。

2) ${\overset{\smile} {{M}}}$ 中有l个1元素,此时 ${\overset{\smile} {{L}}}$ 出现某一特征值代数重数( $ \geqslant $ 3),系统整体不可控。

证明 以下对定理中包含的情况一一证明。

1)取单领导者,且外部输入控制信号只影响领导者的一种状态。对于一个具有n个个体的多智能体系统,用 $1,2, \cdots n$ 将它们标注。令 ${{A}} - {{B}}{{{K}}_1}$ 为每个智能体的s阶状态矩阵。令第一个智能体为领导者,那么 ${{M}} = {{{e}}_1}$ 。令外部输入控制矩阵 ${{C}} = {{{e}}_i},1 \leqslant i \leqslant s$ ,此时 ${\overset{\smile} {{M}}}$ 共有 $n \times s$ 个元素并且有如下形式:

${{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over M} }} = [\begin{array}{*{20}{c}} {\underbrace {0 \cdots 1 \cdots 0}_s}&{\underbrace {0 \cdots 0}_{(n - 1)s}} \end{array}]$

${\overset{\smile} {{L}}}$ 的特征值为 $({{\textit{λ}} _1},{{\textit{λ}} _2}, \cdots ,{{\textit{λ}} _i},\cdots ,{{\textit{λ}} _j},\cdots ,{{\textit{λ}} _{ns}})$ 并且互不相同,其中 ${{\textit{λ}}_j}(1 \leqslant i, j \leqslant ns,i \ne j)$ 的代数重数为2。此时有两个对应于 ${{\textit{λ}}_j}$ 的线性无关的特征向量 ${{{u}}_{j1}}{\text{、}}{{{u}}_{j2}}$ 。对这两个特征向量进行线性组合,得到对应于 ${{\textit{λ}}_j}$ 的一个新的特征向量 ${{{u}}_j}$ ${ u_j} = a{{{u}}_{j1}} + b{{{u}}_{j2}}$ $a,b \in {\rm{R}}$ 并且ab不同时为0。我们总能找到这样一组ab使得 ${{{u}}_j}$ 某一个位置的元素为0,这个位置对应于 ${\overset{\smile} {{M}}}$ 中元素为1的位置。即 ${{{u}}_j}$ 有如下形式:

${{{u}}_j} = [\begin{array}{*{20}{c}} {\underbrace { * \cdots \mathop 0\limits_i \cdots * }_s}&{\underbrace { * \cdots * }_{(n - 1)s}} \end{array}]$

此时 ${{u}}_{_j}^{\rm{T}}{\overset{\smile} {{M}}} = 0$ ,根据PBH判据,此多智能体系统不可控。

2) ${\overset{\smile} {{M}}}$ 中有l个1元素,此时有两种情况。

① 取单领导者系统,外部输入控制信号影响领导者的多种状态。即外部输入控制矩阵有m个元素为1 $(2 \leqslant m \leqslant s)$ ,可以是C中任意m个元素的位置,假设前m个元素为1,则C具有如下形式:

${{C}} = [\underbrace {\begin{array}{*{20}{c}} {\underbrace {1 \cdots 1}_m}&{0 \cdots 0} \end{array}}_s]$

那么 ${\overset{\smile} {{M}}}$ 具有如下形式:

${\overset{\smile} {{M}}} = [\begin{array}{*{20}{c}} {\underbrace {1 \cdots 1}_m}&{\underbrace {0 \cdots 0}_{s - m}}&{\underbrace {0 \cdots 0}_{(n - 1)s}} \end{array}]$

${\overset{\smile} {{L}}}$ 的特征值为 $({{\textit{λ}} _1}, \cdots ,{{\textit{λ}} _{ns - {\rm{2}}}})$ 并且互不相同,其中 ${{\textit{λ}}_j}(1 \leqslant j \leqslant ns - 2)$ 的代数重数为3,对应于 ${{\textit{λ}}_j}$ 有3 个线性无关的特征向量 ${{{u}}_{j1}}{\text{、}}{{{u}}_{j2}}{\text{、}}{{{u}}_{j3}}$ 。对 ${{{u}}_{j1}}{\text{、}}{{{u}}_{j2}}$ 进行线性组合,得到新的特征向量 ${{{u}}_{j12}} = a{{{u}}_{j1}} + b{{{u}}_{j2}}$ ,选取合适的一组不全为0的数a,b, ${\rm{a}}, {\rm{b}} \in {\rm{R}}$ ,使得 ${{{u}}_{j12}}$ 的第一个元素为0。同样地,分别对 ${{{u}}_{j1}}{\text{、}}{{{u}}_{j{\rm{3}}}}$ ${{{u}}_{j{\rm{2}}}}{\text{、}}{{{u}}_{j{\rm{3}}}}$ 进行线性组合,得到 ${{{u}}_{j{\rm{13}}}}{\text{、}}{{{u}}_{j2{\rm{3}}}}$ ,它们的第一个元素均为0。至此,得到了3个新的对应于 ${\lambda _j}$ 的特征向量,并且它们的第1个元素均为0。现在考虑特征向量的第2个元素。与找第一个元素的方法相同,对这3个特征向量中的任意两个进行线性组合,然后得到另外3个第1和第2个元素都为0的特征向量。重复以上步骤,直到得到一个前m个元素都为0的特征向量,将它记为 ${{{u}}_{\rm need}}$ ,它有如下形式:

${{u}}_{\rm need}^{\rm{T}} = [\begin{array}{*{20}{c}} {\underbrace {0 \cdots 0}_m}&{\underbrace { * \cdots * }_{ns - m}} \end{array}]$

根据PBH判据, ${{u}}_{{\rm{need}}}^{\rm{T}}{\overset{\smile} {{M}}} = 0$ ,此时系统不可控。

② 多领导者系统。对于具有l个领导者的多智能体系统,假设前l个智能体为领导者,分别标注为 ${n_1},{n_2}, \cdots ,{n_l}$ 。那么 ${{M}}$ 具有如下形式:

${{M}} = [\begin{array}{*{20}{c}} {{{{e}}_1}}&{{{e}}_2}& \cdots &{{{{e}}_l}} \end{array}]$

其中 ${{{e}}_i}$ 的维度为n。假设外部输入控制矩阵C $m(2 \leqslant m \leqslant s)$ 个元素为1,且为前m个元素,那么 ${\overset{\smile} {{M}}}$ 具有如下形式:

$\begin{array}{l} {{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over M} }} = [\begin{array}{*{20}{c}} {{{{m}}_1}}&{{{{m}}_2}}& \cdots &{{{{m}}_l}} \end{array}]\\ {{m}}_{\rm{1}}^{\rm{T}} = [\begin{array}{*{20}{c}} {\underbrace {1 \cdots 1}_m}&{\underbrace {0 \cdots 0}_{s - m}}&{\underbrace {0 \cdots 0}_{(n - 1)s}} \end{array}]\\ {{m}}_2^{\rm{T}} = [\begin{array}{*{20}{c}} {\underbrace {0 \cdots 0}_s}&{\underbrace {1 \cdots 1}_m}&{\underbrace {0 \cdots 0}_{s - m}}&{\underbrace {0 \cdots 0}_{(n - 2)s}} \end{array}]\\ \vdots \\ {{m}}_l^{\rm{T}} = [\begin{array}{*{20}{c}} {\underbrace {0 \cdots 0}_{(n - 1)s}}&{\underbrace {1 \cdots 1}_m}&{\underbrace {0 \cdots 0}_{s - m}} \end{array}] \end{array}$

假设 ${\overset{\smile} {{L}}}$ 中存在一个代数重数为3的特征值 ${\lambda _j}(1 \leqslant j \leqslant ns - 2)$ ,其余特征值互不相同,那么 ${\lambda _j}$ 相应有3个线性无关的特征向量 ${{{u}}_{j1}}{\text{、}}{{{u}}_{j2}}{\text{、}}{{{u}}_{j3}}$ ,对这3个特征向量两两线性组合,得到3个新的特征向量,并且它们第一个元素均为0。再对这3个新的特征向量两两线性组合,对这一过程重复进行,直至得到一个新的特征向量,它相应于 ${\overset{\smile} {{M}}}$ 元素为1的位置上的元素都为0。根据PBH判据,此特征向量在 ${\overset{\smile} {{M}}}$ 的零空间中,因此系统不可控,证毕。

以下给出两个实例,验证定理3中2种情况。

例3

$\begin{gathered} {{A}} = \left[\!\!\! {\begin{array}{*{20}{r}} 1&2&0 \\ { - 1}&1&2 \\ 0&3&1 \end{array}} \!\!\!\right],{{{K}}_1} = \left[\!\!\! {\begin{array}{*{20}{r}} { - 1}&3&0 \\ 1&{ - 2}&3 \\ 0&4&{ - 1} \end{array}} \!\!\!\right],{{C}} = \left[\!\!\! {\begin{array}{*{20}{c}} 1 \\ 1 \\ 0 \end{array}}\!\!\! \right],{{B}} = {{{I}}_3} \\ {{{K}}_2} = \left[\!\!\! {\begin{array}{*{20}{r}} { - 2}&1&0 \\ 1&{ - 3}&1 \\ 0&1&{ - 2} \end{array}} \right],{{L}} = \left[ {\begin{array}{*{20}{r}} 1&{ - 1}&0 \\ { - 1}&2&{ - 1} \\ 0&{ - 1}&1 \end{array}} \!\!\!\right],{{M}} = \left[\!\!\! {\begin{array}{*{20}{c}} 1 \\ 0 \\ 0 \end{array}}\!\!\! \right] \\ \end{gathered} $

取矩阵参数如上,对应于情况2) 中②的, ${\overset{\smile} {{M}}}$ 中有2个元素为1。此时系统网络拓扑结构可控,并且个体动态能控,但系统整体不可控,可控性判别矩阵的秩为5<9。 ${\overset{\smile} {{L}}}$ 存在一个代数重数为3的特征值 ${\textit{λ}} = {\rm{4}}$

例4 取矩阵参数与例3相同,取1、3节点为领导者,对应于情况2) 中②的 ,

${{M}} = {\left[ {\begin{array}{*{20}{c}} 1&0&0 \\ 0&0&1 \end{array}} \right]^{\rm{T}}}$

${\overset{\smile} {{M}}}$ 中有4个元素为1。此时系统拓扑结构和单个智能体动态均是能控的,但是系统整体并不可控,可控性判别矩阵为8<9。

值得注意的是,例4中的系统矩阵 ${{\tilde L}} $ 的特征值为1、2、2、4、4、4、8、8、16, ${{\tilde L}} $ 的对角矩阵块 ${A}-{B}{{{K}}_{1}}-{{{{\textit{λ}}} }_{{s}}}{B}{{{K}}_{2}} $ 之间也出现了重复的特征值,但鉴于例2中 ${{\tilde L}} $ 的对角矩阵块 ${A}-{B}{{{K}}_{1}}-{{{{\textit{λ}}} }_{{s}}}{B}{{{K}}_{2}} $ 之间即使出现了重复特征值但系统整体仍然可控的情况,并不能断言矩阵块 ${A}-{B}{{{K}}_{1}}-{{{{\textit{λ}}} }_{{s}}}{B}{{{K}}_{2}} $ 之间有重复的特征值导致了系统整体不可控,而是 ${\overset{\smile} {{L}}}$ 中的3个重复的特征值导致该系统不可控。

4 结束语

本文构建了一个用于描述一般线性多智能体系统的模型(4),并且包含了现有模型。并且从系统拓扑结构和个体状态层面对系统整体可控性进行了研究,得到了系统整体可控的必要条件和一类充分性条件。构建了一类系统矩阵不含有重复特征值的系统并且可以利用以上充分条件判断该系统是否可控。关于系统矩阵中出现重复特征值的情况,借助具体的例子,探讨了系统矩阵中重复特征值在不同情况下对系统整体可控性的影响,并用简单的代数知识与例子对其进行了解释。最后,提出一种根据系统矩阵特征值重数个数判断系统是否整体可控的方法。本文对于一般线性多智能体可控性以及系统矩阵重复特征值对系统可控性影响的研究结果,为以后研究更加复杂的多智能体系统可控性提供了一种方法和基础。

参考文献
[1] XIE Guangming, WANG Long. Consensus control for a class of networks of dynamic agent[J]. International journal of robust and nonlinear control, 2007, 17(10/11): 941-959. (0)
[2] XIAO Feng, WANG Long, CHEN Jie, et al. Finite- time formation control for multi-agent systems[J]. Automatica, 2009, 45(11): 2605-2611. DOI:10.1016/j.automatica.2009.07.012 (0)
[3] 王晓晓, 纪志坚. 广播信号下非一致多智能体系统的能控性[J]. 智能系统学报, 2014, 9(4): 401-406.
WANG Xiaoxiao, JI Zhijian. Controllability of non-identical multi-agent systems under a broadcasting control signal[J]. CAAI transactions on intelligent systems, 2014, 9(4): 401-406. (0)
[4] ZHENG Y, ZHU Y, WANG L. Consensus of heterogeneous multi-agent systems[J]. IET control theory and applications, 2011, 5(16): 1881-1888. (0)
[5] ADLER J L, SATAPATHY G, MANIKONDA V, et al. A multi-agent approach to cooperative traffic management and route guidance[J]. Transportation research part B: methodological, 2005, 39(4): 297-318. DOI:10.1016/j.trb.2004.03.005 (0)
[6] 单素素, 纪志坚, 翟海川. 采用Leader-follower和模糊反馈机制的机器鱼队形控制[J]. 智能系统学报, 2013, 8(3): 247-253.
SHAN Susu, JI Zhijian, ZHAI Haichuan. The formation control of multi-robot fish based on leader-follower and fuzzy feedback mechanism[J]. CAAI transactions on intelligent systems, 2013, 8(3): 247-253. (0)
[7] 王耀威, 纪志坚, 翟海川. 仿生机器鱼运动控制方法综述[J]. 智能系统学报, 2014, 9(3): 276-284.
WANG Yaowei, JI Zhijian, ZHAI Haichuan. A survey on motion control of the biomimetic robotic fish[J]. CAAI transactions on intelligent systems, 2014, 9(3): 276-284. DOI:10.3969/j.issn.1673-4785.2014.03.002 (0)
[8] DIMAROGONAS D V, TSIOTRAS P, KYRIAKOPOULOS K J. Leader-follower cooperative attitude control of multiple rigid bodies[J]. Systems and control letters, 2009, 58(6): 429-435. DOI:10.1016/j.sysconle.2009.02.002 (0)
[9] KALMAN R E. Contributions to the theory of optimal control[J]. Boletin de la sociedad matematica mexicana, 1960, 5: 102-119. (0)
[10] KALMAN R E, HO Y C, NARENDRA K S. Controllability of linear dynamical systems[J]. Contributions to differential equations, 1963, 1(2): 189-213. (0)
[11] TANNER H G. On the controllability of nearest neighbor interconnections[C]//Proceedings of the 43rd IEEE Conference on Decision and Control. Nassau, Bahamas, 2004: 2467−2472. (0)
[12] 关永强, 纪志坚, 张霖, 等. 多智能体系统能控性研究进展[J]. 控制理论与应用, 2015, 32(4): 421-431.
GUAN Yongqiang, JI Zhijain, ZHANG Lin, et al. Recent developments on controllability of multi-agent system[J]. Control theory and applications, 2015, 32(4): 421-431. DOI:10.7641/CTA.2014.40419 (0)
[13] 董洁, 纪志坚, 王晓晓. 多智能体网络系统的能控性代数条件[J]. 智能系统学报, 2015, 10(5): 747-754.
DONG Jie, JI Zhijian, WANG Xiaoxiao. Algebraic conditions for the controllability of multi-agent systems[J]. CAAI transactions on intelligent systems, 2015, 10(5): 747-754. (0)
[14] JI Zhijian, LIN Hai, YU Haisheng. Leaders in multi-agent controllability under consensus algorithm and tree topology[J]. Systems and control letters, 2012, 61(9): 918-925. DOI:10.1016/j.sysconle.2012.06.003 (0)
[15] JI Zhijian, LIN Hai, YU Haisheng. Protocols design and uncontrollable topologies construction for multi-agent networks[J]. IEEE transactions on automatic control, 2015, 60(3): 781-786. DOI:10.1109/TAC.2014.2335971 (0)
[16] JI Zhijian, WANG Zidong, LIN Hai, et al. Interconnection topologies for multi-agent coordination under leader-follower framework[J]. Automatica, 2009, 45(12): 2857-2863. DOI:10.1016/j.automatica.2009.09.002 (0)
[17] 晁永翠, 纪志坚, 王耀威, 等. 复杂网络在路形拓扑结构下可控的充要条件[J]. 智能系统学报, 2015, 10(4): 577-582.
CHAO Yongcui, JI Zhijian, WANG Yaowei, et al. Necessary and sufficient conditions for the controllability of complex networks with path topology[J]. CAAI transactions on intelligent systems, 2015, 10(4): 577-582. (0)
[18] SCHOLTES I, WIDER N, GARAS A. Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities[J]. The European physical journal B, 2016, 89(3): 61. DOI:10.1140/epjb/e2016-60663-0 (0)
[19] CZEIZLER E, WU K C, GRATIE C, et al. Structural target controllability of linear networks[J]. IEEE/ACM transactions on computational biology and bioinformatics, 2018, 15(4): 1217-1228. DOI:10.1109/TCBB.2018.2797271 (0)
[20] LIU Kaien, JI Zhijian. Consensus of multi-agent systems with time delay based on periodic sample and event hybrid control[J]. Neurocomputing, 2017, 270: 11-17. DOI:10.1016/j.neucom.2016.12.106 (0)
[21] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE transactions on evolutionary computation, 1997, 1(1): 53-66. DOI:10.1109/4235.585892 (0)
[22] JI Meng, EGERSTEDT M. A graph-theoretic characterization of controllability for multi-agent systems[C]//Proceedings of the 2007 American Control Conference. New York, USA, 2007: 4588-4593. (0)
[23] MARTINI S, EGERSTEDT M, BICCHI A. Controllability analysis of multi-agent systems using relaxed equitable partitions[J]. International journal of systems, control and communications, 2010, 2(1/2/3): 100-121. DOI:10.1504/IJSCC.2010.031160 (0)
[24] 张安慧, 张世杰, 陈健, 等. 多智能体系统可控性的图论刻画[J]. 控制与决策, 2011, 26(11): 1621-1626, 1631.
ZHANG Anhui, ZHANG Shijie, CHEN Jian, et al. Graph-theoretic characterization of controllability for multi-agent systems[J]. Control and decision, 2011, 26(11): 1621-1626, 1631. (0)
[25] AMLIBEL M K, ZHANG S, CAO M. Comments on ‘Controllability analysis of multi-agent systems using relaxed equitable partitions’[J]. International journal of systems, control and communications, 2012, 4(1/2): 72-75. DOI:10.1504/IJSCC.2012.045932 (0)
[26] ZHANG Shuo, CAO Ming, CAMLIBEL M K. Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents[J]. IEEE transactions on automatic control, 2014, 59(3): 745-750. DOI:10.1109/TAC.2013.2275666 (0)
[27] JI Zhijian, LIN Hai, LEE T H. A graph theory based characterization of controllability for multi-agent systems with fixed topology[C]//Proceedings of the 47th IEEE conference on Decision and control. Cancun, Mexico, 2008: 5262−5267. (0)
[28] LIU Xianzhu, JI Zhijian. Controllability of multiagent systems based on path and cycle graphs[J]. International journal of robust and nonlinear control, 2018, 28(1): 296-309. DOI:10.1002/rnc.v28.1 (0)
[29] 楚天广, 杨正东, 邓奎英, 等. 群体动力学与协调控制研究中的若干问题[J]. 控制理论与应用, 2010, 27(1): 86-93.
CHU Tianguang, YANG Zhengdong, DENG Kuiying, et al. Problems in swarm dynamics and coordinated control[J]. Control theory and applications, 2010, 27(1): 86-93. (0)
[30] XUE Mengran, ROY S. Comments on “Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents”[J]. IEEE transactions on automatic control, 2017, 63(7): 2306. (0)
[31] XIANG Linying, ZHU J J H, CHEN Fei, et al. Controllability of weighted and directed networks with nonidentical node dynamics[J]. Mathematical problems in engineering, 2013, 2013: 405034. (0)
[32] 徐仲, 张凯院, 陆全, 等. 矩阵论简明教程[M]. 第2版. 北京: 科学出版社, 2005: 155. (0)