近几年来学术界对多智能体系统已经有了广泛的研究和关注^[1-14]，并且已经应用在多个领域中，如无人机的编队控制、机器人的编队控制，甚至在军事上也有广泛的应用^[15-17]。多智能体系统的核心问题是关于可控性的问题，可控性能够使每个智能体的状态达到人们所期望的结果，并且使多智能体系统发挥最大的作用。所以，多智能体系统的可控性研究具有重要的意义。

在多智能体系统中，对具有领导者—跟随者结构的图可控性研究大都是基于单信号输入下或者是更为简单的模型下^{[13, 18]}，在多智能体中，模型的建立对系统的可控性有着重要的影响。在所建立的模型下，充分认识系统与可控性的关系，并理解系统对可控性的影响，这些无疑对解决多智能体系统的可控性问题提供了很好的方法和帮助。所以研究特定模型下系统的可控性成为一个热点。

Tanner是最早通过系统中各节点之间的联系来研究可控性的^[19]。他通过邻居信息，提出了其中一个节点为领导者时系统可控的充分必要条件，并得到了无向图下的能控性定理。这对后续有关可控性的研究给予了很大的帮助。早在Aguilar的文章中^[18]，Aguilar就整个图的可控性进行分类，根据图选取不同的领导者时图是否可控，来定义了3种图可控性，并就3种分类进行了详细的分析，但是Aguilar的文章内容是在单信号输入的特殊模型下进行研究的，即每个领导者节点受到同一个信号的输入，而本文是在更一般的多信号输入模型下进行研究，每个领导者节点可能受到不同的多个信号的输入，这种多信号输入的模型更能准确地表现多智能体系统的一般性，而且本文纠正了Aguilar文章^[18]中关于齐次向量的条件可控图问题。

一些研究者^[19-22]近几年对基于拉普拉斯矩阵下的可控性作了很多的研究，本文也是在拉普拉斯矩阵下，结合矩阵论的知识^[23-25]，对系统的可控性与拉普拉斯矩阵的关系进行了研究，特别是在拉普拉斯矩阵的特征值和特征向量等对系统可控性的影响方面进行了深入的研究，另外，本文主要在多输入信号情况下，对多智能体系统中的图可控性进行分类，具体分为多信号输入下本质可控图，多信号输入下完全不可控图以及多信号输入下条件可控图，并就这3 种分类的特殊性进行了描述，而且对它们的性质进行了相应的阐述。

1 预备知识

在多智能体系统中，图的节点代表智能体，图中的边线代表智能体之间的通信链接。本文中考虑的是简单图，即没有封闭环形或重边的无权重无向图。图G表示为G=[V E]，其中n个点的点集表示为V=[1 2 … n]，边集为E={(i, j)∈V×V}，输入节点集合表示为S=[i₁ i₂ … i_q]，并且满足i₁ ＜i₂＜… ＜i_q，输入节点称为领导者节点，剩下的跟随者节点集合即为V＼S。图G的邻接矩阵为A∈R^n×n，它的全部元素满足当(i, j)∈E时，a_ij=1；否则a_ij=0。如果(i, j)∈E，那么节点i和节点j是相邻点，节点i的相邻点集合为N_i={ka_ik=1}，一个节点i的度d_i为它的相邻点的数量。图G的度矩阵为D∈R^n×n，它是对角矩阵，第i个对角元素为d_i。 图的拉普拉斯矩阵表示为L=D－A。

在图G中，对于点集合的两个节点i和节点j，定义节点i和节点j之间的距离为d_G(i, j)，表示为节点i和节点j之间最短的通道。当图中任意一对节点之间存在一条通道时，我们说图G是连通的。拉普拉斯矩阵是半正定且实对称的，因此L的特征值可以给定顺序为λ₁≤λ₂≤…≤λ_n，其中特征值λ₁=0对应的特征向量为[1 1 … 1]^T。如果图G是连通的，则λ₁=0是L的非重特征根，此时有λ₂>0，本文中图G的特征值或特征向量即为图拉普拉斯矩阵L的特征值或特征向量。

给定域k上的向量空间P，Q是P的有限子集，则Q的生成空间为Q中元素的所有有限线性组合组成的集合。如果Q=[p₁ p₂ … p_r]，则生成空间span(Q)=span(p₁, p₂，…, p_r)={λ₁p₁+λ₂p₂…+λ_rp_r|λ₁，λ₂, …, λ_r∈k}。令〈L;B〉表示包含B的最小L-不变子空间，即〈L;B〉=spanL^kBk∈N₀，并且，当dim(〈L;B〉)=k+1时，{B, LB, …, L^kB}是〈L;B〉的一个基。其中dim(〈L;B〉)表示矩阵(〈L;B〉)的空间维数。如果dim(〈L;B〉)=n，则系统(L, B)是可控的。

本文主要分析G=(V, E)上的可控性问题，其中x_i(t)∈R 代表了节点i∈V在时刻t时的状态，节点间的相互关系由边集E来表示。在时刻t时，一个外部控制向量通过一状态向量b_m∈R^q施加在节点i上。单个节点的状态方程可以表示为

另外，在时刻t，输出方程y(t)∈R^p由输出矩阵C∈R^n×p表示。所以对于连通图G=(V, E)，整个系统方程表示为

式中B=[b₁ b₂ … b_n]^T∈R^n×q。

定义1 如果所有领导者节点都受到同一个信号的输入，那称这样的系统为单信号输入系统。当系统受到多个信号输入时，称这样的系统为多信号输入系统。

在单信号输入系统下，对于具有n个点的图中，定义输入节点集合S={i₁, i₂, …, i_q}，并且满足i₁ ＜i₂＜…＜i_q，每个输入节点都受到同一个信号的输入时，相应的输入矩阵B可以改成输入向量b=[b₁ b₂ … b_n]^T∈{0, 1}ⁿ，即b_i∈{0, 1}，定义V_b={i∈Vb_i=1}为领导者节点集合，V＼V_b为跟随者节点集合，控制单信号为u(t)。系统(1) 可以改写为

在多信号输入系统下，系统可以分为2种，对于系统(1) ，一种情况是在n个点的图中，定义输入节点集合S每个点只收到一个信号的输入时(每个点收到的信号不一定相同)，相应的输入矩阵B=[e_i1 e_i2 … e_iq]∈R^n×q，e_ix表示第i_x个元素为1，其他元素为零的列向量，x{1, 2, …, q}, U(t)是有q个控制器的向量，即U(t)=u₁(t) u₂(t) … u_q(t)^T。

另一种情况是在n个点的图中，定义输入节点集合S，每个点可能收到多个信号的输入，相应的输入矩阵为

式中：b_ij∈0, 1，1≤i≤n，1≤j≤q。

2 主要结论

首先讨论单信号输入下系统可控性与多信号输入下系统可控性的区别和联系。

多信号输入下系统可控性与单信号输入下系统可控性是有很大区别的，在选取的领导者下，有些图在单信号输入系统下是不可控的，但在多信号输入系统下却不一定不可控。

图 1为具有4个节点的情形，选取节点2和节点4为领导者，当这2个节点受到单信号输入时，b=0 1 0 1^T，根据秩判据rankb Lb L²b L³b＜4，此时在选取的领导者下，系统不可控。当2个节点受到不同信号输入时，即多信号输入系统下，令B=[e₂ e₄]，根据秩判据rankB LB L²B L³B=4，此时系统可控。

当任意选取领导者节点时，有些图在单信号输入系统下是完全不可控的，但在多信号输入系统下并非完全不可控的。

图 2中任选节点为领导者，该图在单信号输入系统下是完全不可控的，即任选b∈{0, 1}ⁿ，根据秩判据rankb Lb … L⁵b＜6，系统(L, b)不可控。当选取节点1和节点5为领导者且2个节点受到不同信号输入时，即在多信号输入系统下，令B=[e₁ e₅]，根据秩判据rankB LB … L⁵B=6，此时系统(L, B)可控。

通过上文，可以看出多信号输入下可控性与单信号输入下可控性有很大的区别，那么就有必要讨论基于拉普拉斯矩阵下的多信号输入系统与系统可控性的关系，本文通过下面的定理给出。

定理 1 假定可对角化矩阵L无重特征值，矩阵U是由L的线性无关的单位特征向量构成的矩阵，那么〈L;B〉的维数等于W=U^－1B中非零列向量的个数。特别地，系统(L, B)是可控的充要条件是W矩阵中无零列向量。当L有重特征值，且w_i≠0_q时，系统(L, B)是不可控的，当且仅当重特征值λ_i所对应的向量组w_i中，存在线性相关的向量，其中i=1, 2，…, n。

证明 令D为对角矩阵，其对角元素为L的特征值，则有L=UDU^－1, 令W=U^－1B=w₁, w₂, …, w_n^T，W∈ R^n×q。其中w_i为列向量，i∈{1, 2, …, n}。

由于U是非奇异矩阵，所以它不影响式(3) 右边矩阵的秩，右边的矩阵展开后即为

对上式进行列变换得

当特征值不同时，式(4) 后面的矩阵是满秩的，只需考虑式(4) 前面1×q矩阵，其中每个元素为n×n的对角矩阵，则此矩阵实际上是具有n行，n×q列的矩阵:

根据此矩阵的特点，取第i行，当w_ij=0时，此矩阵的维数小于n，其j∈{1, 2, …, q}。所以〈L;B〉的维数取决于向量w_i^T，即L无重特征值时，〈L;B〉的维数等于W=U^－1B中非零列向量的个数，而且当且仅当W 矩阵中无零列向量时，dim(〈L;B〉)=n，即此时系统可控。

当L有重特征值情况时，根据无重特征值的情况，证明如下：

设λ_i=λ_j，若w_i=kw_j，其中k∈R，i, j∈1, 2, …, n且i≠j，则rankB LB … L^n－1B ＜n，此时，系统(L, B)不可控，而且当且仅当重特征值λ_i所对应的向量组w_i中，存在线性相关的向量时，系统(L, B)是不可控的。证毕。

通过下面情况的论述都能够验证定理1中无重特征值时的情况。对于具有个n个节点的图，节点2和节点4为领导者节点时，此时W=U^－1B=w₁ … w_n^T∈R^n×2，其中w_i=w_i2 w_i4^T，i∈{1, 2, …, n}。根据定理1得

在L无重特征值下，仅当存在w_i2=w_i4=0时，〈L;B〉的维数小于n，〈L;B〉的维数等于w_i中非零向量的个数。而且当且仅当w_i≠0时，dim(〈L;B〉)=n，即此时系统可控。

对于具有2个节点的图，节点1和节点2为领导者节点时，此时W=U^－1B=w₁ w₂^T∈R^2×2，其中w_i=w_i1w_i2^Τ，i∈{1, 2}。根据定理1得

由于U是非奇异矩阵，所以它不影响式(5) 右边矩阵的秩，对式(5) 右边矩阵进行列变换得

在λ₁≠λ₂下，上式后面的矩阵是满秩的，根据前面的矩阵，只有当w₁₁=w₁₂=0或w₂₁=w₂₂=0时，〈L;B〉的维数小于2，而且当且仅当w_i≠0时，dim(〈L;B〉)=2，即此时系统可控。

令E_n为n×q维的矩阵，并且矩阵中的每个元素为1;0_n为n×q维的矩阵，并且矩阵中的每个元素为0;1_n为n维列向量，且每个元素都为1;0_q为q维列向量，且每个元素都为0。下面推论由定理1的证明可得。

推论 对于系统(1) ，假设L没有重特征值，则系统(L, B)是可控的，当且仅当L的任意一个特征向量的转置与矩阵B的乘积为非零向量，即u_i^TB=w_i^T≠0_q^T。

注释 单信号输入系统下，对应的拉普拉斯矩阵如果存在重特征值，则系统不可控；但是在多信号输入系统下，并不能单纯依靠存在重特征值来判断系统的不可控性。

推论2 对于系统(1) ，无论L有无重特征值时，若B=0_n，即W=U^－1B=w₁ … w_n^T=0_n，则系统(L, B)不可控。

证明同理定理1证明为

则rank B LB … L^n－1B ＜n，即系统(L, B)不可控。

令‖b_j‖=∑_i=1ⁿb_ij表示列向量b_j中非零元素之和。令B=E_n－B表示B的补集。

定理2 让n≥2，对于系统(1) ，系统(L, B)是可控的, 当且仅当系统(L, B-)是可控的。而且B∉{E_{n, 0n}}时，dim(〈L;B〉)=dim〈L;B〉成立。

证明 U为L标准正交基组成的矩阵，其中U的第一列特征向量为中元素为正实数。令W=U^－1B=w₁ … w_n^T，并且W-=U^－1B=w₁ … w_n^T, 其中W和W-∈R^n×q。*表示任意实数，但它们满足U^T的第2行到第n行向量都与1_n正交。那么，

即

从(6) 中可以看出对所有的i=2, …, n，有w_i^T=－w_i^T，另外

因为B∉{E_n,O_n}，所以w₁≠O_q，w_i≠O_q。这样可以证明在B∉{E_n,O_n}下W-和W有相同数目的非零向量。而且因为对于所有的i=2, 3，…, n，有w_i^T=－w_i^T，无论L有无重特征值，〈L;B〉的维数都等于〈L;B〉，即dim(〈L;B〉)=dim〈L;B〉。而且它们的维数相同时，可控性也相同。

通过上文的阐述，可以给出多信号输入下图可控性分类的定义。

定义2 在连通图G中，对于系统(1)

1) 如果除去图中每个点都是输入节点以及每个点都不是输入节点的2种情况后，任意选取图中的点为输入节点时，系统(L, B)是可控的，则图关于B是多信号输入下本质可控图；

2) 如果在图中选取任意点为输入节点时，系统(L, B)都是不可控的，则图关于B是多信号输入下完全不可控图；

3) 如果图关于B即不是多信号输入下本质可控图也不是多信号输入下完全不可控图，则图关于B是多信号输入下条件可控图。

下面是分情况讨论3种情况下的图性质。

2.1 多信号输入下本质可控图

在本节中，主要给出2个多输入下本质可控图的必要条件，通过下面的命题论证。

命题1 多输入下本质可控图是不对称的。

证明 设G是多输入下本质可控图，则L必须有不同的特征值。在这用反证法，假设多输入下本质可控图是对称的，则G有一个非平凡自同构群，设J是置换矩阵代表G的一个非恒等自同构，那么存在2个不同的标准正交基e_i和e_j，使得Je_i=e_j和Je_j=e_i。则有J[e_i 0_n …]=[e_j 0_n …]和J[0_n e_j …] = [0_n e_i …]。并且有JL(G)=L(G)J，令B=[e_i 0_n …]+[0_n e_j …]。可以得到JB=B。设λ为矩阵L的特征值，其对应的特征向量为v，满足Lv=λv。两边同乘以J，有JLv=Jλv，因为JL(G)=L(G)J，则有L(Jv)=λ(Jv)，即Jv也是对应于特征值λ的特征向量。因为L有一系列正交特征向量，v－Jv也是L的特征向量。而且JB=J^TB=B，则有(v－Jv)^TB=v^TB－v^TJ^TB=v^TB－v^TB=0即B正交于L的特征向量。因此系统(L, B)是不可控的。这与G是多输入下本质可控图相矛盾。所以多输入下本质可控图是不对称的。结论得证。

任何少于6个点的图都可以改为对称的图。如图 3(a)中，5个点的情况可以改为图 3(b)中对称的图形。由此启发可以得到下面的命题。

命题 2 多输入下本质可控图至少有6个点。

证明 根据命题1，并且由任何不对称的图形至少有6个点得证。

对于系统(1) ，不对称的图并不都是多输入下本质可控图。通过图 (4) 可以进行验证。

图 4是一个在给定点标记下的不对称图，它的拉普拉斯矩阵为

当输入矩阵B=[e₁ e₂]时，可以求出rank B LB … L⁵B＜6。此时系统(L, B)是不可控的。

2.2 多信号输入下完全不可控图

相对于多信号输入下本质可控图，图对称与否并不与多信号输入下完全不可控图有关联。对于系统(1) ，对称的图并不都是多输入下完全不可控图。如图 1为对称图，当B=[e₂ e₄]时，根据秩判据，此时系统可控。

给定图G，则可以写出图的拉普拉斯矩阵，也可以求出图的特征值，特征值所对应的特征向量也可以求出，由此启发，给出下面的命题。

命题 3 图G在有重特征值的情况下，对任意的B使得w_i线性相关，那么这样的图为多信号输入下完全不可控图。其中w_i^T=u_i^TB，u_i为重特征值所对应的特征向量，i=1, …, n。

证明 根据定理1，得证。

命题 4 在图G中，如果存在一个L的特征向量的转置与B 的乘积为0_q^T，则这样的图为多信号输入下完全不可控图。

证明 根据定理1，得证。

2.3 多信号输入下条件可控图

在本节中，主要提出文献^[18]中的错误，并举例进行阐述。

对于文献^[18]中的模型(2) 实际上是系统(1) 的特殊情况，即单信号输入系统，此时要在系统(2) 下进行分析与讨论文献^[18]中的问题。

定义 3^[18] 在图G=(V, E)中，r, s∈R，称b∈Rⁿ在图G中是一个(r, s)-齐次可控向量，如果对于每一个i∈V_b，有r=N_i∩V＼V_b，并且对每一个j∈V\V_b，有s=N_j∩V_b。即每一个领导节点i与r个跟随者相邻，并且每一个跟随者节点j与s个领导者相邻。

对于文献^[18]中推论4.2：G是一个含有n个点的连通图，并且n≥3时，如果G有一个(r, s)-齐次可控向量，则G是条件可控的。

如图 5，在系统(2) 下，令b=[0 0 1 1 0 0]^T，其中i∈V_b={3, 4}，若i=3，则N_i={1, 2}且j∈V＼V_b={1, 2, 5, 6}，得r=2，即领导节点3与2个跟随者邻接，若j=1，则N_j={3}，得s=1，即跟随者节点1与1个领导者邻接。由此称b=[0 0 1 1 0 0]^T在图G中是一个(2, 1) -齐次可控向量。则根据文献^[18]中推论4.2得图G是条件可控的。

图 5的拉普拉斯矩阵为L

可以求出它有一个两重的特征值为3。即图 5具有重特征值，根据注释，在单信号输入系统下可以得到图G是完全不可控的，显然是矛盾的，所以文献^[18]中推论4.2是错误的。在多信号输入系统下，更不能通过齐次向量来判断图的条件可控性。

3 结束语

本文就多信号输入系统下的可控性分类问题进行了详细的研究与分析，并对拉普拉斯矩阵下特征值和特征向量与可控性的关系进行了阐述和论证，论述了单信号输入系统与多信号输入系统的区别和联系，而且纠正了文献^[18]中关于齐次可控向量应用在条件可控图上的错误。本文对可控性分类的研究方法和结果，为以后研究更复杂的图可控性问题提供了方向和帮助。