基于符号有向图的多智能体系统的结构能控性与镇定性

Structural Controllability and Stabilizability of Multi-Agent Systems Based on Signed Directed Graphs

摘要: 本文在一般协议的背景下研究了基于符号有向图的多智能体系统的结构能控性与镇定性。首先，我们给出消除系统中不可达节点的方法，接着给出了一类扩张的新定义“非零入度扩张”。通过增加节点和增加边，只要不产生零入度扩张，则系统仍结构能控的特点研究了系统的结构能控性。最后，给出系统可镇定的两个定理并通过仿真实例证明了结论。

Abstract: In this paper, the structural controllability and stabilizability of multi-agent systems which are based on the signed directed graphs is investigated in the context of general protocols. First, we present a method for eliminating nonaccessible nodes with-in the multi-agent systems. Then, a new definition of dilations “non-zero indegree dilation” is given. We studied the structural controllability of the system by the characteristic that the system can still be structurally controlled as long as zero indegree dilation is not generated by adding nodes and edges. Finally, two theorems for the stabilizability of multi-agent systems are given. A simulation is given to illustrate the theoretical results.

1. 引言

在过去的十年里，复杂网络的能控性得到了充足的发展[1]-[3]。由于复杂网络的众多成就和计算机技术的快速发展，近年来多智能体系统的研究受到了各个领域的关注。系统的能控性是一个基本问题，它在分布式控制、编队控制和协同控制中起着重要作用[4] [5]。在文献[6]中首次提出了基于最近邻居协议的多智能体系统的能控性概念。此后，学者们对这一问题的研究不断深化。文献[7]通过研究高阶网络扩展了文献[6]的结论，结果表明能控性与智能体的动态方程无关只与智能体的拓扑结构有关。文献[8]研究了基于符号有向加权图的多智能体系统的能控性，通过几乎等价划分将能控性问题转化为图问题并给出了一个系统能控的必要条件。文献[9]进一步研究了基于矩阵加权符号有向图的多智能体系统的能控性，通过几乎等价划分给出了系统能控的一个必要条件。然而，由于权重、动态模型、一致性协议等因素对多智能体之间关系的约束和影响，多智能体系统的能控性研究充满了困难和挑战。

权重在能控性中起着重要作用。但在实际应用中往往得不到精确的数值，结构能控性的概念应运而生。1974年，Lin在文献[10]中首次提出了基于复杂网络的结构能控性概念，并发展了结构能控性的代数和图论等价条件，这为能控性开辟了一个新的视角。之后，学者们对基于有向图的复杂网络的结构能控性理论进行了研究并得到了诸多结果[11]-[13]。文献[14]在有向图的基础上，给出了多智能体系统结构能控性的一个充要条件，即一个多智能体系统是结构能控的当且仅当对应的拓扑图是连通的。文献[15]在文献[14]的基础上讨论了高阶多智能体系统的结构能控性，得到了与一阶系统结构能控相同的结论，即拓扑图是连通的。文献[16]讨论了基于加权有向图的多智能体系统的结构能控性，通过距离划分和权重平衡划分给出了系统结构能控的两个充要条件。在现实中，智能体之间可能存在竞争与合作。文献[17]讨论了基于绝对协议的符号有向图的多智能体系统的结构能控性问题，得到了结构能控的图论充要条件，即系统是领航者跟随者连通的。

多智能体系统的结构能控性不取决于图的权重而只取决于结构，镇定性与之相似。文献[18]研究了在有向图下的多智能体系统的镇定性。结果表明，独立的强连通分支是多智能体系统可镇定的关键。文献[19]研究了基于绝对协议的符号有向图的多智能体系统的镇定性。为了解决符号图的可镇定性，提出了符号图结构平衡独立强连通分量的概念，并在此基础上导出了符号有向图可镇定的一个充要条件。文献[20]从商图的角度研究了大规模网络的拓扑结构对镇定性的影响并提出了在镇定性分析中发挥重要作用的NSi划分的概念。

对于符号有向图的研究大都基于绝对协议，而对一般协议却少有研究。一般协议下每个智能体根据自身和邻居的信息做出决策，这有助于构建模块化和可扩展的系统，没有中心节点对所有智能体进行集中控制，这增强了系统的鲁棒性，即使部分智能体失效，整个系统仍能继续运作。现实世界中的交互往往是基于局部信息和相对变化的，一般协议能够更好地模拟这种交互方式，使其在诸如无人机编队、机器人协作等应用中更为实用。本文基于一般协议的符号有向图研究多智能体系的结构能控性与镇定性。本文的主要成果分为两个部分。第一，给出了消除多智能体系统中不可达节点的方法并提出了扩张的新定义。进一步通过增加节点和边的方法证明了这种扩张对多智能体系统的结构能控性没有影响。第二，基于NSi划分得到多智能体系统自反馈可镇定的充分条件。

本文的组织结构如下。在第二节中，我们介绍了本文中使用的图论、系统模型。第三节介绍了本文的主要成果。最后，在第四节中给出结论。

2. 预备知识

2.1. 图论知识

一个符号有向图可由$\mathcal{G}=\left\{\mathcal{V},ℰ,A\right\}$ 表示，其中$\mathcal{V}=\left\{1,\cdots ,n\right\}$ 是节点集合，$ℰ\subseteq \mathcal{V}\times \mathcal{V}$ 是边集合。矩阵$A=\left[a_{ij}\right]\in R^{n\times n}$ 是$\mathcal{G}$ 的邻接矩阵，$a_{ij}$ 表示边的权重。$a_{ij}\ne 0$ 表示节点i与节点j间存在边且该边由节点j指向节点i。假设不存在自环即$a_{ii}=0$ 。有向路径是由如下序列$i_1,i_2,\cdots ,i_k$ 定义，其中节点$i_s$ 和节点$i_{s+1}$ 是两个不同节点并且$\left(i_s,i_{s+1}\right)\in ℰ$ 。弱有向路径也是由不同顶点的序列定义，但只要$\left(i_s,i_{s+1}\right)\in ℰ$ 或者$\left(i_{s+1},i_s\right)\in ℰ$ 。图$\mathcal{G}$ 被称为强连通的当且仅当任意两个不同节点间都存在一条有向路径，被称为弱连通的当且仅当任意两不同节点间都存在一条弱有向路径。节点i的邻接集合定义为$N_i=\left\{j\in \mathcal{V}:\left(j,i\right)\in ℰ,j\ne i\right\}$ 。图$\mathcal{G}$ 的入度矩阵$D=diag\left(d_1,\cdots ,d_n\right)$ 其中$d_i={\displaystyle \sum _{j\in N_i}{a}_{ij}}$ 。图$\mathcal{G}$ 的拉普拉斯矩阵为$L=D-A$ ，其中的元素可以表示为：

$l_{ij}=\{\begin{array}{l}{d}_i,i=j,\hfill \\ -a_{ij},i\ne j.\hfill \end{array}$ (1)

2.2. 系统模型

基于符号有向图我们考虑一个具有n个节点的多智能体系统。为了简单起见，只考虑一维情况。每个节点都可以与其邻居通信，每个节点的动态可以表示为：

${\dot{x}}_i=u_i$ (2)

这里$x_i\in ℛ$ 是节点i的状态，$u_i\in ℛ$ 是系统控制输入。假设有$l\left(l\le n\right)$ 个节点被选为领航者，不失一般性我们选择前$1,\cdots ,l$ 个节点作为领航者。定义领航者集合${\mathcal{V}}_l=\left\{1,\cdots ,l\right\}$ ，则跟随者集合为${\mathcal{V}}_f=\mathcal{V}\backslash {\mathcal{V}}_l$ 。领航者集合${\mathcal{V}}_l$ 中每个节点都有额外的控制输入，因此所有节点的动态遵循以下一般协议：

$\{\begin{array}{l}{u}_i=-{\displaystyle \sum _{j\in N_i}{a}_{ij}}\left(x_i-x_j\right)+{\tilde{u}}_i,i\in {\mathcal{V}}_l\hfill \\ u_i=-{\displaystyle \sum _{j\in N_i}{a}_{ij}}\left(x_i-x_j\right),i\in {\mathcal{V}}_f\hfill \end{array}$ (3)

由于我们考虑的是符号有向图，所以$a_{ij}$ 可取正值或负值。设$x={\left(x_1,\cdots ,x_n\right)}^{\text{T}}$ 是所有节点状态的叠加向量，那么系统的动态可以写为：

$\dot{x}\left(t\right)=-Lx\left(t\right)+Bu\left(t\right)$ (4)

这里L是拉普拉斯矩阵并且$B=\left[e_{i_1},\cdots ,e_{i_l}\right]$ 是控制输入矩阵。

基于上述内容我们定义多智能体系统${\pi }_{\Lambda }$ ，其系统动态为：

$\dot{x}\left(t\right)=-L_{\Lambda }x\left(t\right)+B_{\Lambda }u\left(t\right)$ (5)

其中$L_{\Lambda }$ 是拉普拉斯矩阵，$B_{\Lambda }$ 是控制输入矩阵。矩阵$L_{\Lambda }$ 和$B_{\Lambda }$ 中的元素有两种情况，要么是固定的零元要么是非零的自由参数。对于矩阵$L_{\Lambda }$ 中的非零的自由参数，它们的权重可以变化但是符号不会改变。

3. 主要成果

3.1. 结构能控性

在得到本章节的主要结论前，我们首先给出必要的定义。

定义1：(不可达节点) 节点i被称为不可达的当且仅当从任何领航者都不存在一条有向路指向该节点。

定义2：(扩张) 图$\mathcal{G}$ 含有扩张当且仅当存在一个子集${\mathcal{V}}_k\subset \mathcal{V}$ 使得$\left|N\left({\mathcal{V}}_k\right)\right|<\left|{\mathcal{V}}_k\right|$ ，其中$N\left({\mathcal{V}}_k\right)$ 是邻居集。

我们从不可达节点和扩张两个方面考虑由(5)定义的多智能体系统${\pi }_{\Lambda }$ 。首先找到系统${\pi }_{\Lambda }$ 中所有独立强连通分支和强连通分支。强连通分支间有一个自然的排列顺序，强连通分支$C_i$ 和$C_j$ 之间有如$C_i<C_j$ 的排列顺序当节点$v_i\in C_i$ 和节点$v_j\in C_j$ 间存在一条边$\left(v_i,v_j\right)$ 。在这种排列顺序下的初始强连通分支是独立强连通分支。

定理1：系统${\pi }_{\Lambda }$ 中不含有不可达节点当且仅当从每个独立强连通分支中选择一个节点作为领航者。

证明：充分性：对于系统的所有独立强连通分支，我们从每个分支中选择一个节点为领航者。独立强连通分支中任意两节点间都存在有向路，选择其中一个节点作为领航者则该领航者与分支中其他节点都存在一条有向路，这保证了该独立强连通分支中所有节点都不为不可达节点。由于所有领航者自身构成一个强连通分支，因此对系统的所有强连通分支存在一个自然顺序排列$\left(C_i<C_j\right)$ 。这保证了对任意节点i都存在一条由领航者到该节点的有向路，这就确保了系统中不含有不可达节点。

必要性：我们采用反证法，假设存在一个独立强连通分支$C_k$ 中不包含领航者。由独立强连通分支的定义可知不存在其他节点到该独立强连通分支的入边，因此对于该分支中的节点不存在一条由领航者到其的有向路。这与系统不含有不可达节点相矛盾，因此对每个独立强连通分支至少存在一个节点为领航者。

接下来考虑扩张对多智能体系统结构能控性的影响。对于线性复杂网络，图1中包含扩张则系统是结构不能控的但对多智能体系统却不同。我们先通过下面例子简单介绍这种差异。

Figure 1. A signed directed graph of three nodes

图1. 三个节点的符号有向图

例1：首先考虑基于图1的线性复杂网络，系统动态可以表示为：

$\left[\begin{array}{c}{\dot{x}}_1\left(t\right)\\ {\dot{x}}_2\left(t\right)\\ {\dot{x}}_3\left(t\right)\end{array}\right]=\left[\begin{array}{ccc}0& 0& 0\\ a_{21}& 0& 0\\ a_{31}& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\left(t\right)\\ x_2\left(t\right)\\ x_3\left(t\right)\end{array}\right]+\left[\begin{array}{c}{b}_1\\ 0\\ 0\end{array}\right]u\left(t\right)$ (6)

能控性判别矩阵为：

$Q_A=\left[B,AB,A^{2}B\right]=b_1\left[\begin{array}{ccc}1& 0& 0\\ 0& a_{21}& 0\\ 0& a_{31}& 0\end{array}\right]$ (7)

由于$rank\left(Q_A\right)=2<3$ 系统是不可控的。我们注意到能控性判别矩阵的秩与$b_1,a_{21},a_{31}$ 无关，因此无论如何改变自由变量的值系统都是不能控的。

接着我们考虑基于图1的多智能体系统，系统动态可以表示为：

$\left[\begin{array}{c}{\dot{x}}_1\left(t\right)\\ {\dot{x}}_2\left(t\right)\\ {\dot{x}}_3\left(t\right)\end{array}\right]=\left[\begin{array}{ccc}0& 0& 0\\ -a_{21}& a_{21}& 0\\ -a_{31}& 0& a_{31}\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\left(t\right)\\ x_2\left(t\right)\\ x_3\left(t\right)\end{array}\right]+\left[\begin{array}{c}{b}_1\\ 0\\ 0\end{array}\right]u\left(t\right)$ (8)

能控性判别矩阵为：

$Q_L=\left[B,LB,L^{2}B\right]=b_1\left[\begin{array}{ccc}1& 0& 0\\ 0& -a_{21}& -a_{21}^2\\ 0& -a_{31}& -a_{31}^2\end{array}\right]$ (9)

可以看出我们能够通过调整$b_1,a_{21},a_{31}$ 的值使得系统结构能控。

对同一个符号有向图，扩张对线性复杂网络和多智能体系统的影响截然不同。不可达节点与扩张是两种概念但二者也有交叉，如图1中的节点1既是不可达节点也是扩张，为了消除这种情况我们将扩张分为如下两种情况。

定义3：(非零入度扩张) 对于图$\mathcal{G}$ 的一个扩张k，${\mathcal{V}}_k$ 是它的节点集合。若至少存在一条边$\left(i,j\right)\in ℰ$ ，其中$i\in \mathcal{V}\backslash {\mathcal{V}}_k$ ，$j\in {\mathcal{V}}_k$ 那么我们称扩张k为非零入度扩张。

定义4：(零入度扩张) 对于图$\mathcal{G}$ 的一个扩张k，${\mathcal{V}}_k$ 是它的节点集合。若不存在边$\left(i,j\right)\in ℰ$ ，其中$i\in \mathcal{V}\backslash {\mathcal{V}}_k$ ，$j\in {\mathcal{V}}_k$ 那么我们称扩张k为零入度扩张。

由于零入度扩张我们可以通过在其中选择节点作为领航者的方法消除其对结构能控性的影响，因此接下来主要研究非零入度扩张。考虑一个基于符号有向图的多智能体系统${\pi }_p$ ，假设它含有k个节点，$L_p$ 和$B_p$ 分别为对应拉普拉斯矩阵和控制输入矩阵。我们首先考虑如图2的情况，选择${\pi }_p$ 中一个节点j，在该节点处增加$n-k$ 个节点和边来创造一个非零入度扩张。假设新的系统为${\pi }_t$ 则它包含n个节点。

Figure 2. Single-node multi-branched type

图2. 单节点多分枝型

命题1：如果上述系统${\pi }_p$ 是结构能控的则新系统${\pi }_t$ 也是结构能控。

证明：系统${\pi }_t$ 的拉普拉斯矩阵和控制输入矩阵可以表示为：

$L_t=\left[\begin{array}{cc}{L}_p& 0\\ A& L_a\end{array}\right],B_t=\left[\begin{array}{c}{B}_p\\ 0\end{array}\right]$ (10)

其中$L_a$ 是拉普拉斯矩阵中与增加的节点相关的部分，它是一个对角矩阵。矩阵A揭示了增加的节点与节点j的连接关系，它只有第j列是自由的参数其他元素都是固定的零元。

$L_a=\left[\begin{array}{cccc}{a}_{k+1j}& 0& \cdots & 0\\ 0& a_{k+2j}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nj}\end{array}\right],A=\left[\begin{array}{ccccc}0& \cdots & -a_{k+1j}& \cdots & 0\\ 0& \cdots & -a_{k+2j}& \cdots & 0\\ ⋮& \ddots & ⋮& \ddots & ⋮\\ 0& \cdots & -a_{nj}& \cdots & 0\end{array}\right]$ (11)

通过矩阵$L_t$ 的形式可以看出其特征值为矩阵$L_p$ 和$L_a$ 特征值的并。假设${\lambda }_i,i=1,2,\cdots ,k$ 是矩阵$L_p$ 的特征值，${\lambda }_i,i=k+1,k+2,\cdots ,n$ 是矩阵$L_a$ 的特征值。由于系统${\pi }_p$ 是结构能控的，则根据PBH判据可知$r\left[{\lambda }_{i}I-L_p,B_p\right]=k,i=1,2,\cdots ,k$ 。对系统${\pi }_t$ 考虑$\left[{\lambda }_{i}I-L_t,B_t\right]$ ，具体形式为：

$\left[\begin{array}{ccc}{\lambda }_i{I}_k-L_p& 0& B_p\\ -A& {\lambda }_i{I}_{n-k}-L_a& 0\end{array}\right]$ (12)

对那些属于$L_p$ 的特征值只需验证上述分块矩阵中${\lambda }_i{I}_{n-k}-L_a$ 是满秩的就可以保证$r\left[{\lambda }_{i}I-L_t,B_t\right]=n$ 。由$L_a$ 的构成形式，我们只需选择不同于$L_p$ 特征值的数值作为$L_a$ 的对角元素就可保证${\lambda }_i{I}_{n-k}-L_a$ 是满秩的。对那些属于$L_a$ 的特征值由于矩阵A的存在也可保证$r\left[{\lambda }_{i}I-L_t,B_t\right]=n$ 。综上所述对$L_t$ 的所有特征值都有$r\left[{\lambda }_{i}I-L_t,B_t\right]=n$ ，由PBH判据可知${\pi }_t$ 结构能控。

图2的构造方式只考虑了一种情况即每个分支只有一个节点，下面考虑如图3的另一种情况即一个分支上增加多个节点。

Figure 3. Multi-node single-branched type

图3. 多节点单分枝型

命题2：如果系统${\pi }_p$ 是结构能控的，则通过图3增加节点的方式产生的新系统${\pi }_t$ 也是结构能控。

证明：我们首先给出矩阵$L_a$ 和A的具体形式：

$L_a=\left[\begin{array}{ccccc}{a}_{k+1j}& 0& \cdots & 0& 0\\ -a_{k+2k+1}& a_{k+2k+1}& \cdots & 0& 0\\ ⋮& \ddots & \ddots & ⋮& ⋮\\ 0& \cdots & -a_{n-1n-2}& a_{n-1n-2}& 0\\ 0& 0& \cdots & -a_{nn-1}& a_{nn-1}\end{array}\right],A=\left[\begin{array}{ccccc}0& \cdots & -a_{k+1j}& \cdots & 0\\ 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0\end{array}\right]$ (13)

可以看出矩阵$L_a$ 是一个下三角矩阵，其特征值只与对角线元素有关。因此我们仍然可以通过利用命题1的证明方法证明$r\left[{\lambda }_{i}I-L_t,B_t\right]=n$ ，这里不再赘述。

注1：命题2只考虑了一个分支的情况，多个分支的情况类似只需合理的对节点编号得到的矩阵$L_a$ 都会是一个下三角矩阵。

上述讨论只考虑了增加的节点间只有入边的情况而忽略了增加的节点间的出边，下面我们将所有情况都考虑进去来研究非零入度扩张。

定理2：非零入度扩张不会影响多智能体系统的结构能控性。

证明：我们假设系统${\pi }_n$ 是结构能控的，通过之前的两个方法增加节点得到新系统${\pi }_m$ 。如果增加的节点没有出边则由命题1和命题2可知系统${\pi }_m$ 是结构能控的。如果增加的节点有出边，那么新的系统的拉普拉斯矩阵$L_m$ 和控制输入矩阵$B_m$ 可以表示为：

$L_m=\left[\begin{array}{cc}\stackrel{\sim }{L_1}& B\\ A_{21}& \stackrel{\sim }{L_2}\end{array}\right],B_m=\left[\begin{array}{c}{B}_1\\ 0\end{array}\right]$ (14)

由拉普拉斯矩阵的形式采用分步验证的方法。首先考虑只有入边的情况，由上述内容可知系统是结构能控的。进一步只需研究不增加节点只增加边是否会影响系统的结构能控性。而在系统中只增加边不会增加不可达节点和扩张的个数，从而只增加边不会改变系统的结构能控性。系统${\pi }_m$ 是结构能控的，因此非零入度扩张不会影响多智能体系统的结构能控性。

3.2. 镇定性

在本章节我们主要研究基于一般协议下的符号有向图的多智能体系统(4)的自反馈镇定问题，文献[19]研究了在绝对协议下符号有向图的镇定问题并提出了结构平衡的独立强连通分支的概念，得到了只需从每个结构平衡的独立强连通分支中选择至少一个节点给予自反馈控制输入就可使得系统镇定的结论。然而这个结论并不能直接推广到一般协议下的符号有向图，一般协议下符号有向图的情况更加复杂。文献[20]首次提出了NSi划分的概念并用于系统的镇定性分析中。本文利用NSi划分来对一般协议下的符号有向图进行镇定性分析，下面介绍NSi划分及所需引理。

定义5：(独立强连通分支(iSCC)) 图$\mathcal{G}$ 的一个独立强连通分支是$\mathcal{G}$ 的一个最大强连通诱导子图${\mathcal{G}}^i=\left({\mathcal{V}}^i,{ℰ}^i,A^i\right)$ ，并且对于任意$v_j\in \mathcal{V}\backslash {\mathcal{V}}^i,v_i\in {\mathcal{V}}^i$ 都有$\left(v_i,v_j\right)\cancel{\in }ℰ$ 。

在独立强连通划分下系统的拉普拉斯矩阵可以表示为：

$L=\left[\begin{array}{ccccc}{L}_{1,1}^i& 0& \cdots & 0& 0\\ 0& L_{2,2}^i& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & L_{c,c}^i& 0\\ L_{c+1,1}& L_{c+1,2}& \cdots & L_{c+1,c}& L_{c+1,c+1}\end{array}\right]$ (15)

这里$L_{jj}^i,j=1,\cdots ,c$ 为对应第j个独立强连通分支的拉普拉斯矩阵。

定义6：(非独立强连通分支(NiSCC)) 图$\mathcal{G}$ 的一个非独立强连通分支是$\mathcal{G}$ 的一个最大强连通诱导子图${\mathcal{G}}^N=\left({\mathcal{V}}^N,{ℰ}^N,A^N\right)$ 满足：

1) 对任意$v_i\in {\mathcal{V}}^N,v_j\in \mathcal{V}\backslash {\mathcal{V}}^N$ 都有$\left(v_j,v_i\right)\cancel{\in }ℰ$ ；

2) 至少存在一个节点$v_q\in {\mathcal{V}}^N,v_p\in \mathcal{V}\backslash {\mathcal{V}}^N$ 满足$\left(v_q,v_p\right)\in ℰ$ 。

在非独立强连通划分下系统的拉普拉斯矩阵可以表示为：

$L=\left[\begin{array}{ccccc}{L}_{1,1}^N& 0& \cdots & 0& L_{1,0}\\ 0& L_{2,2}^N& \cdots & 0& L_{2,0}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & L_{c,c}^N& L_{c,0}\\ 0& 0& \cdots & 0& L_{0,0}\end{array}\right]$ (16)

这里$L_{jj}^N,j=1,\cdots ,c$ 为对应第j个非独立强连通分支的拉普拉斯矩阵。

定义7：(半独立连通分支(SiCC) 图$\mathcal{G}$ 的半独立连通分支是$\mathcal{G}$ 的一个连通诱导子图${\mathcal{G}}^S=\left({\mathcal{V}}^S,{ℰ}^S,A^S\right)$ 满足：

1) 若连通诱导子图为强连通子图则

(i) 至少存在一个根节点$v_i\in {\mathcal{V}}^S,v_j\in {\mathcal{V}}^i$ 满足$\left(v_i,v_j\right)\in ℰ$ ；

(ii) 至少存在一个节点$v_q\in {\mathcal{V}}^N,v_k\in {\mathcal{V}}^S$ 满足$\left(v_k,v_q\right)\in ℰ$ 。

2) 若连通诱导子图为弱连通子图则

(i) 对任意$v_s\in {\mathcal{V}}^S$ 都是子节点和父节点；

(ii) 所有根节点$v_i\in {\mathcal{V}}^S$ 都有$\left(v_i,v_j\right)\in ℰ$ ，这里$v_j\in {\mathcal{V}}^i;$

(iii) 至少存在一个节点$v_q\in {\mathcal{V}}^N,v_k\in {\mathcal{V}}^N$ 满足$\left(v_k,v_q\right)\in ℰ$ 。

定义8：(NSi划分) 任何拓扑图$\mathcal{G}$ 的节点在iSCC，SiCC和NiSCC划分下总是属于三种情况中的一个。

注2：在NSi划分下任何拓扑图$\mathcal{G}$ 都可以由上述三种划分表示。不失一般性，我们假设前c个连通分支为非独立强连通分支。第$c+1$ 个连通分支为半独立连通分支，$c+2$ 到d为独立强连通分支。当拓扑图为连通图时，系统的拉普拉斯矩阵可以表示为下列的上三角矩阵：

$L=\left[\begin{array}{ccccccc}{L}_{1,1}^N& \cdots & 0& L_{1,c+1}& L_{1,C+2}& \cdots & L_{1,d}\\ ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& \cdots & L_{c,c}^N& L_{c,c+1}& L_{c,c+2}& \cdots & L_{c,d}\\ 0& \cdots & 0& L_{c+1,c+1}^S& L_{c+1,c+2}& \cdots & L_{c+1,d}\\ 0& \cdots & 0& 0& L_{c+2,c+2}^i& \cdots & 0\\ ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& \cdots & 0& 0& 0& \cdots & L_{d,d}^i\end{array}\right]$ (17)

引理1：对于一个弱对角占优的矩阵A如果对角元素都为正实数且矩阵为不可约矩阵，则矩阵的所有特征值都具有正实部。

引理2：对于一个严格对角占优的矩阵A如果对角元素都为正实数，则矩阵的所有特征值都具有正实部。

引理3：对于一个给定的多智能体系统(4)及状态反馈控制$\tilde{u}=-Kx$ ，若导出的状态反馈系统满足矩阵$-\left(L+BK\right)$ 的特征值均具有负实部则称系统实现了镇定。

在本章节中${\tilde{u}}_i$ 被设计为${\tilde{u}}_i=-k_i{x}_i$ 。控制${\tilde{u}}_i$ 是一个自反馈控制，它只与自身的状态有关。

定理3：若图$\mathcal{G}$ 的半独立连通分支为强连通分支，给予可使矩阵$L_{1,1}^N\cdots L_{c+1,c+1}^S\cdots L_{d,d}^i$ 满足弱对角占优且对角线元素为正的节点自反馈控制输入则系统可自反馈镇定。

证明：在NSi划分下系统的拉普拉斯矩阵如(17)所示的上三角矩阵，则L的特征值可以看作是$L_{1,1}^N\cdots L_{c+1,c+1}^S\cdots L_{d,d}^i$ 特征值的并。给予节点自反馈控制${\tilde{u}}_i=-k_i{x}_i$ ，由控制输入矩阵B的具体形式可以得到$L_{i,i}+B_{i,i}{K}_{i,i}=L_{i,i}+K_{i,i},i=1,\cdots ,d$ ，此时矩阵$L_{1,1}^N+K_{1,1}\cdots L_{c+1,c+1}^S+K_{c+1,c+1}\cdots L_{d,d}^i+K_{d,d}$ 满足弱对角占优且对角线元素为正，$K_{i,i}$ 代表每个连通分支对应的自反馈增益矩阵。由于所有连通诱导子图为强连通子图则每个强连通分支对应的拉普拉斯矩阵都是不可约的，下用反证法证明$L_{i,i}+K_{i,i}$ 也为不可约，假设$L_{i,i}+K_{i,i}$ 可约则可知存在置换矩阵P使得

$P\left(L_{i,i}+K_{i,i}\right)P^{\text{T}}=P{L}_{i,i}{P}^{\text{T}}+P{K}_{i,i}{P}^{\text{T}}=\left[\begin{array}{cc}X& O\\ Y& Z\end{array}\right]$ (18)

由于矩阵$K_{i,i}$ 是对角矩阵为对角矩阵则$P{K}_{i,i}{P}^{\text{T}}$ 分块矩阵右上方矩阵为零矩阵，这意味矩阵$L_{i,i}$ 可以表示为：

$P{L}_{i,i}{P}^{\text{T}}=\left[\begin{array}{cc}\tilde{X}& O\\ \tilde{Y}& \tilde{Z}\end{array}\right]$ (19)

这与矩阵$L_{i,i}$ 不可约相矛盾，因此矩阵$L_{i,i}+K_{i,i}$ 也不可约。矩阵$L_{i,i}+K_{i,i}$ 弱对角占优且主对角元素都为正。由引理1可知矩阵$L_{i,i}+K_{i,i}$ 的特征值都具有正实部，则由引理3可知系统在给予自反馈控制输入后可镇定。

定理4：若图$\mathcal{G}$ 的半独立连通分支为弱连通分支，给予可使矩阵$L_{1,1}^N\cdots L_{c,c}^N,L_{c+2,c+2}^i,\cdots ,L_{d,d}^i$ 满足弱对角占优且对角线元素为正，使矩阵$L_{c+1,c+1}^S$ 满足严格对角占优且对角线元素为正的节点自反馈控制输入则系统可自反馈镇定。

证明：对非独立连通分支与独立强连通分支与定理3证明相同这里不再赘述。下面考虑半连通分支，由于半连通分支是弱连通无法确定矩阵$L_{c+1,c+1}^S$ 是否可约，我们给予节点自反馈控制输入使得矩阵$L_{c+1,c+1}^S+K_{c+1,c+1}$ 满足严格对角占优，由引理2可知矩阵$L_{c+1,c+1}^S+K_{c+1,c+1}$ 的特征值都具有正实部，则由引理3可知系统在给予自反馈控制输入后可镇定。

下面给出一个例子来验证定理的正确性。

Figure 4. A signed directed graph of six nodes

图4. 六个节点的符号有向图

例2：考虑基于图4的多智能体系统，其中节点$\left\{1,2\right\}$ 构成非独立强连通分支，节点$\left\{3,4\right\}$ 为半独立弱连通分支，节点$\left\{5,6\right\}$ 为独立强连通分支。假设默认权重为1，我们给出系统的拉普拉斯矩阵：

$L=\left[\begin{array}{cccccc}0& -1& 1& 0& 0& 0\\ 1& -1& 0& 0& 0& 0\\ 0& 0& 1& -1& 0& 0\\ 0& 0& 0& 2& -1& -1\\ 0& 0& 0& 0& 1& -1\\ 0& 0& 0& 0& 1& -1\end{array}\right]$ (20)

根据NSi划分将拉普拉斯矩阵进行划分，其中

$L_{1,1}^N=\left[\begin{array}{cc}0& -1\\ 1& -1\end{array}\right],L_{2,2}^S=\left[\begin{array}{cc}1& -1\\ 0& 2\end{array}\right],L_{3,3}^i=\left[\begin{array}{cc}1& -1\\ 1& -1\end{array}\right]$ (21)

根据定理4选择节点1、2、3、6给予自反馈控制输入，不妨设

$K_{1,1}=\left[\begin{array}{cc}1& 0\\ 0& 2\end{array}\right],K_{2,2}=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right],K_{3,3}=\left[\begin{array}{cc}0& 0\\ 0& 2\end{array}\right]$ (22)

假设节点的初始状态为$x_0={\left[-2.3,-4.6,7.2,4.2,-6.5,1.2\right]}^{\text{T}}$ ，图5展示了节点的状态轨迹可以看出系统达到自反馈镇定。

Figure 5. State trajectory of nodes

图5. 节点的状态轨迹

4. 结论

本文主要研究了基于一般协议下符号有向图的结构能控性与镇定性。针对结构能控性，我们给出了消除系统中不可达节点的方法，提出了非零入度扩张的新定义并通过增加节点增加边的方式证明了其不影响多智能体系统的结构能控性。针对镇定性，我们通过NSi划分分析了一般协议下符号有向图的自反馈镇定问题，针对两种不同的拓扑结构给出了系统可自反馈镇定的充分条件。

NOTES

^*通讯作者。