多智能体协同是实现智能系统合作的关键手段, 在各个领域都有着广泛的应用^[1−3]. 通过通信与信息共享组成多智能体网络, 对实现组织与个体之间的高效协同完成某项工作起着关键作用^[4−8]. 多智能体拓扑变化对整个网络系统的功能有重要影响^[9−11]. 因此, 及时准确发现网络系统的拓扑变化, 是实现多智能体系统平稳正常运行的必要条件.

近年来, 网络系统拓扑变化的检测越来越受到人们的关注, 许多学者对此进行了深入研究, 提出多种检查网络拓扑变化的算法. Rahimian等^[12]考虑了多输入多输出(Multiple input multiple output, MIMO)线性时不变(Linear time-invariant, LTI)系统的有向和加权网络, 基于对输出导数的跳变不连续的观测, 提出一种检测和隔离链路故障的方法. Materassi等^[13]利用维纳滤波器重构动态网络拓扑, 讨论了不同场景下网络拓扑检测算法的有效性. Dhal等^[14]考虑通过测量单个网络组件的噪声来检测网络同步过程中的链路故障. Shahrampour等^[15]提出几种通过确定网络响应的功率谱密度来区分有向和未知加权网络拓扑变化的算法, 并给出一种低成本的专用算法以检测两种特殊网络的拓扑变化.

上述研究主要致力于开发检测拓扑变化的算法. 然而, 网络拓扑变化能否被检测, 是开发检测拓扑变化的算法的前提条件, 也是智能体网络拓扑系统应用更为关键的问题^[16]. 因此, 可辨识性的概念和判断标准引起了部分学者的关注^[17−23]. Rahimian等^[17]研究了多智能体系统中链路故障是否可以检测的问题. Pandey等^[18]提出一种可以应用于链路故障检测的算法. Battistelli等^[19]考虑在已知部分网络节点动力学时, 在线实时检测问题, 给出一些实时检测网络系统节点或链路断开的充分必要条件. Patil等^[20]从控制论的角度推导了特征向量条件, 从而可以检查微分代数方程网络中是否存在无法检测到的拓扑变化, 然而该方法仅适用于无向网络. 此后出现了适用于有向网络的方法^[21−23], 这些方法可以验证有向网络拓扑变化的可辨识性. Zhang等^[21]从图论的角度给出拓扑故障可检测性的充要条件. Hao等^[22−23]阐明了网络系统的特征值和特征向量与各节点系统的特征值和特征向量之间的关系, 其中文献[22]给出通过观测网络状态来验证网络拓扑变化是否可辨识的低维条件, 文献[23]给出通过检测网络系统输出轨迹来验证网络拓扑变化可辨识性的低维充分必要条件.

上述研究假设网络系统中的每个智能体节点具有相同的动力学特性^[16−23], 这样的网络可以称为同构网络. 然而, 同构网络是一种理想的假设, 在实际网络中很难得到满足. 在大多数真实系统中, 不同智能体通常具有不同的动态特性^[24−25]. 这样的网络可以称为异构网络. 智能体异构性使得判断拓扑变化的可辨别性变得更加困难, 因为在考虑网络结构复杂性的同时, 还必须考虑异构智能体动态的复杂性. 在实际网络系统中, 不仅智能体动力学特性是异构的, 而且智能体之间的连接关系(用内耦合矩阵表示)相同也只是一个理想的假设, 而真实系统的内耦合矩阵一般是不同的. 例如, 在由发电机、变压器和电力设备组成的电力网络, 如果将发电机、变压器和电力设备视为网络节点, 则将其物理参数视为节点状态, 不同设备间的连接关系可能是不同的. 因此, 可以将这种电力网络系统视为具有不同内耦合矩阵的异构网络系统. 在这种情况下, 从同构和相同耦合关系网络获得的结果通常是无效的. 所以, 有必要针对异构网络且具有不相同的内耦合关系开发新的方法和判断条件来验证网络中拓扑变化的可辨识性.

基于上述讨论, 本文考虑异构智能体具有不同内耦合矩阵动态网络系统拓扑变化的可辨识性. 主要工作和贡献如下:

1) 揭示了智能体异构性以及内耦合矩阵的不相同会影响多智能体网络的可辨识性.

2) 针对内耦合矩阵不相同的一般网络结构, 给出通过检测系统状态和系统输出轨迹验证网络拓扑可辨识性的充分性条件, 以及网络子系统可观测是整个网络系统拓扑变化可辨识的必要条件.

3) 针对内耦合矩阵不相同的有向链状网络、有向星型网络以及有向环状网络等三种典型的网络结构, 分别给出网络拓扑变化可辨识的充分或必要条件.

1.   预备知识

1.1   符号表示

R (C)表示实数域(复数域), $ {\bf{R}^n\ (\bf{C}^n}) $表示n元有序实数组(复数组)构成的n维实向量空间(复向量空间), $ {\bf{R}}^{n\times m} \: ({\bf{C}}^{n\times m}) $表示$ n\times m $维实矩阵(复矩阵)的集合. ${{e}}_{i}$是除了$[{{e}}_i]_i=1$外其他元素均为0的列向量, $ {\boldsymbol{0}}_{n} $是元素均为0的列向量, $ {\boldsymbol{0}}_{n\times m} $是元素均为0的$ n\times m $维矩阵. $ \otimes $表示矩阵的克罗内克积运算. $ \sigma({A}) $表示矩阵A特征值的集合. $ {{I}}_{n\times n} $表示一个$ n\times n $维的单位矩阵. $ { \rm{diag}}\{a_1,\;a_2,\;\cdots,\;a_n\} $表示对角元分别为$ a_1,\;a_2,\;\cdots,\;a_n $的对角矩阵, $ { \rm{diag}}\{{A}_1, {A}_2,\;\cdots,\;{A}_n\} $表示对角块矩阵分别为$ {A}_{1},\;{A}_{2},\;\cdots, {A}_{n} $的矩阵. 没有指明矩阵规模时, 则认为矩阵之间的代数运算是相容的.

一个加权有向图$ G=(V,\;E,\;W) $由节点集$ V= \{1,\;2,\;\cdots,\;N\} $, 边集$ E=\{(j,\;i)\} $以及加权邻接矩阵${W}=[w_{ij}]\in \bf{R}^{N\times N}$构成, 若存在一条从节点j到节点i的有向边, 那么$ w_{ij}\neq0 $, 否则$ w_{ij}=0 $. 对于节点$ i\in V $, 邻居节点集$ N(i)=\{j\in V\mid j\neq i, \;(i, j)\in E\} $.

1.2   线性系统基础

考虑一个线性时不变系统:

其中x和y分别为n维状态向量和m维输出向量, A和C分别为$ n\times n $, $ m\times n $维状态和输出矩阵.

定义1^[26]. 如果对于任意给定的输入u和输出$ y(t_{f}) $, 状态$ x(t_{o}) $在有限时刻$[t_o,\;t_f] $内可以唯一确定, 则称该线性系统是可观测的.

引理1^[26]. 对于LTI系统(1)如下条件是等价的:

1) 系统(1)是可观测的;

2) 系统(1)的可观性矩阵 $ {{Q}} = [{{C}}^{ {\rm{T}}},\; {{A}}^{ {\rm{T}}}{{C}}^{ {\rm{T}}} $, $ \cdots,\; ({{A}}^{n-1})^{ {\rm{T}}}{{C}}^{ {\rm{T}}}]^{ {\rm{T}}} $列满秩, 即$ \text{rank}{{Q}}=n $;

3) $ \text{rank}[{{C}}^ {\rm{T}},\;s{{I}}_n-{{A}}^ {\rm{T}}]^ {\rm{T}}=n $, $ \forall s\in {{C}} $;

4) 对A的任一特征值$ \lambda $, 不存在A的非零特征向量$ \alpha $满足$ {{C}}\alpha =0 $.

LTI系统(1)可以用矩阵对($ {{A}},\; {{C}}$)表示. 系统(1)可观用($ {{A}},\; {{C}}$)可观表示.

2.   网络模型和问题描述

2.1   模型描述

考虑一个具有N个智能体的异构网络系统:

其中$ {{{{x}}}_{i}}\in{{\bf{R}}^{n}} $表示智能体i的状态向量; $ {{{{A}}}_{i}}\in{{\bf{R}}^{n\times n}} $表示智能体i的状态矩阵; $ {{{{H}}}_{i}}\in{{\bf{R}}^{n\times n}} $表示内耦合矩阵, 描述了$ {{{{x}}}_{i}} $和$ {{{{x}}}_{j}} $各分量之间的连接关系. $ {{w}_{ij}}\in \bf{R} $表示智能体i和智能体j之间的耦合强度, 通常假设$ {{w}_{ii}}=0 $. 若存在从智能体j指向智能体i的链路, 那么$ {{w}_{ij}}\ne 0 $, 反之$ {{{w}_{ij}}}=0 $, $ i,\;j=1,\;\cdots ,\;N $. 为避免特殊情况, 通常假设$ N\ge 2 $.

值得注意的是, 系统(2)中各个智能体的动力学是不同的, 故称为异构网络. 而当智能体的自身动力学相同时, 表示同构网络模型, 如文献[16−23]研究的都是同构网络的可辨识性. 另外, 本文不仅考虑了智能体之间的异构性, 还考虑了智能体之间的内耦合矩阵也是异构的网络拓扑变化的可辨识性.

令$ {{W}}=[{{w}_{ij}}]\in {{\bf{R}}^{N\times N}} $表示整个网络系统(2)的拓扑. 令$ {{X}}=[{{x}}_{1}^{ {\rm{T}}},\;\cdots,\;{{x}}_{N}^{ {\rm{T}}}]^{ {\rm{T}}} $表示网络系统(2)的状态, 那么系统(2)具有以下等价等式:

其中,

2.2   问题描述

网络拓扑发生变化时(连接边的增加、减少或边的权重改变), 不会影响单个智能体的动力学特性. 网络拓扑变化会导致拓扑矩阵变为$ \bar{W} $, 同时会产生一个新的系统, 新系统具有以下形式:

其中,

定义2 (不可辨识的初始状态)^[20]. 考虑网络系统(3), 当且仅当(3)的所有解和(5)的所有解满足下列等式时, 称初始状态${{{{X}}}_{0}}\in {{\bf{R}}^{Nn}}$关于拓扑变化$ W\to \bar{W} $是不可辨识的:

由于初始状态$ X_0=\boldsymbol{0}_{Nn} $不受拓扑变化的影响始终满足上式, 所以$ X_0=\mathbf{0}_{Nn} $始终是不可辨识的初始状态. 称$ {{{{X}}}_{0}}={{{{{\boldsymbol{0}}}}}_{Nn}} $为平凡不可辨识的初始状态. 除$ {{{{X}}}_{0}}={{{{{\boldsymbol{0}}}}}_{Nn}} $外其他不可辨识的初始状态称为非平凡不可辨识的初始状态. 根据非平凡不可辨识初始状态的存在性, 拓扑变化可分为以下两种类型:

定义3 (拓扑变化的可辨识性)^[20]. 考虑网络系统(3), 若系统不存在(非平凡)不可辨识的初始状态, 则称拓扑变化$ W\to \bar{W} $是一直−可辨识的; 若存在非平凡不可辨识初始状态, 则称拓扑变化是可能−不可辨识的.

可以发现, 拓扑变化的可辨识性取决于初始状态. 如果拓扑变化是一直−可辨识的, 那么它对于所有初始状态都是可辨识的. 如果拓扑变化是可能−不可辨识的, 则它对于某些初始状态可能是可辨识的, 但对于其他初始状态也可能是不可辨识的. 为了简明地描述可辨识性, 我们将“一直−可辨识”称为“可辨识”, 将“可能−不可辨识”称为“不可辨识”.

引理2^[19]. 考虑网络系统(3), 当且仅当系统$ \left\{ \begin{matrix} \dot{X}=\Delta X \\ Y=\Gamma X \end{matrix} \right. $可观测时, 系统(3)的拓扑变化$ W\to \bar{W} $是可辨识的, 其中$ \Delta ={\mathrm{diag}}\{\Phi ,\;\bar{\Phi }\} $, $ \Gamma =[\begin{matrix} I & -I \end{matrix}] $.

3.   网络拓扑变化的可辨识性

3.1   一般网络结构的拓扑变化可辨识性

本节通过举例说明内耦合矩阵不同时对网络拓扑变化可辨识性的影响, 并给出对于一般网络结构验证网络拓扑变化的可辨识性条件.

例1. 考虑一个具有$ {n=2} $个智能体组成的网络系统, 如图 1所示. 当智能体网络系统增加一条由智能体2指向智能体1的连边时, 网络拓扑矩阵由$ W=\left[ \begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix} \right] $变为$ \bar{W}=\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] $. 智能体1和智能体2的状态矩阵分别为$ {{A}_{1}}=\left[ \begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix} \right] $, $ {{A}_{2}}=\left[ \begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix} \right] $. 假设两个智能体具有相同的内耦合矩阵, 即$ {{H}_{1}}={{H}_{2}}= \left[ \begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix} \right] $. 由引理2, ${{ \rm{rank}}}[\Gamma^ {\rm{T}},\;\Delta^ {\rm{T}}\Gamma^ {\rm{T}},\;\cdots,\;(\Delta^7)^ {\rm{T}}\Gamma^ {\rm{T}}]^ {\rm{T}}= 6<8 $, 所以拓扑变化$ W\to\bar{W} $是不可辨识的.

图 1  增加一条连边的有向网络

Fig. 1  A directed network with an edge added

下载: 全尺寸图片 幻灯片

当两个智能体的内耦合矩阵不同时, $ {{H}_{1}}= \left[ \begin{matrix} 1 & 2 \\ 2 & 3 \end{matrix} \right] $, $ {{H}_{2}}=\left[ \begin{matrix} 2 & 1 \\ 3 & 2 \end{matrix} \right] $. 由引理2, $ { \rm{rank}}[\Gamma^ {\rm{T}},\;\Delta^ {\rm{T}}\Gamma^ {\rm{T}}, \cdots, \;(\Delta^7)^ {\rm{T}}\Gamma^ {\rm{T}}]^ {\rm{T}}=8 $, 所以拓扑变化$ W\to \bar{W} $是可辨识的.

例2. 考虑一个具有n = 2个智能体组成的网络系统, 如图 2所示. 当智能体网络系统删除一条由智能体1指向智能体2的连边时, 网络拓扑矩阵由$ W=\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] $变为$ \bar{W}=\left[ \begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix} \right] $. 智能体1和智能体2的状态矩阵分别为$ {{A}_{1}}=\left[ \begin{matrix} 0 & 0 \\ 2 & 0 \end{matrix} \right] $, $ {{A}_{2}}=\left[ \begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix} \right] $. 假设两个智能体具有相同的内耦合矩阵, 即$ {{H}_{1}}={{H}_{2}}= \left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right] $. 由引理2, $ { \rm{rank}}[\Gamma^ {\rm{T}},\;\Delta^ {\rm{T}}\Gamma^ {\rm{T}},\;\cdots, \; (\Delta^7)^ {\rm{T}}\Gamma^ {\rm{T}}]^ {\rm{T}}= 8 $, 所以拓扑变化$ W\to \bar{W} $是可辨识的.

当两个智能体的内耦合矩阵不同时, $ {{H}_{1}}= $ $\left[ \begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix} \right] $, $ {{H}_{2}}=\left[ \begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix} \right] $. 由引理2, $ { \rm{rank}}[\Gamma^ {\rm{T}},\;\Delta^ {\rm{T}}\Gamma^ {\rm{T}}, \cdots,\; (\Delta^7)^ {\rm{T}}\Gamma^ {\rm{T}}]^ {\rm{T}}=7<8 $, 所以拓扑变化$ W\to \bar{W} $是不可辨识的.

图 2  删除一条连边的有向网络

Fig. 2  A directed network with an edge deleted

下载: 全尺寸图片 幻灯片

注1. 从以上两个例子可以看出, 内耦合矩阵不同的网络的可辨识性与内耦合矩阵相同的网络的可辨识性是具有很大区别的. 拓扑变化在内耦合矩阵相同的网络中是不可辨识的, 然而, 在智能体动力学特性不变的情况下, 当内耦合矩阵互异时, 拓扑变化可能变成可辨识的. 类似地, 在具有相同内耦合矩阵的网络中的拓扑变化是可辨识的, 当内耦合矩阵不同后拓扑变为不可辨识. 这说明原拓扑辨识性判别方法, 对于具有不同的内耦合矩阵的完全异构智能体网络已不适用. 因此需要开发新的适用于内耦合矩阵不同网络的可辨识性条件.

定理1. 考虑系统(3), 拓扑变化$ W\to \bar{W} $是可辨识的, 当且仅当:

有唯一解$ {{\alpha }_{i}}=0 $, $ i=1,\;\cdots ,\;N $.

证明. 由引理2, 对于系统(3), 其拓扑变化$ W\to \bar{W} $是可辨识的等价于系统$ (\Delta ,\;\Gamma ) $是可观测的, 其中$ \Delta ={ \rm{diag}}\{\Phi ,\;\bar{\Phi }\} $, $ \Gamma =[\begin{matrix} I & -I \end{matrix}] $. 由于$ (\Delta ,\;\Gamma ) $可观测, 根据引理1可知, 满足方程$ (s{{I}_{2Nn}}-\Delta ,\;\Gamma )\alpha = 0 $的$ \alpha $只有零向量.

由$ (s{{I}_{2Nn}}-\Delta )\alpha =0 $, 展开可得式(8). 由$ \Gamma \alpha =0 $, 展开可得式(9). 由式(9)可得, $ {{\alpha }_{N+1}}={{\alpha }_{1}},\;\cdots ,\; $$ {{\alpha }_{2N}}={{\alpha }_{N}} $, 进而式(8)可写成式(10).

即对于$ i=1,\;\cdots,\;N $,

可以得到$ {{H}_{i}} \sum\nolimits_{j=1,\;j\ne i}^{N}{{{w}_{ij}}{{\alpha }_{j}}} = {{H}_{i}} \sum\nolimits_{j=1,\;j\ne i}^{N} {{{\bar{w}}}_{ij}} {{\alpha }_{j}} $有唯一解$ {{\alpha }_{i}}=0 $, $ i=1,\;\cdots ,\;N $时, 系统的拓扑变化$ W\to \bar{W} $是可辨识的. □

注2. 定理1证明通过定义新的系统$ (\Delta ,\;\Gamma ) $, 其中$ \Delta ={ \rm{diag}}\{\Phi ,\;\bar{\Phi }\} $, $ \Gamma =[\begin{matrix} I & -I \end{matrix}] $, 可将异构多智能体系统网络拓扑变化的可辨识性与可观测性建立起联系, 从而可以通过系统可观性理论推导可辨识性条件. 不难看出, 定理1中仅涉及$ n\times n $维矩阵以及n维向量, 这在计算时的矩阵规模与通过引理2验证网络拓扑变化的可辨识性时涉及$ 2Nn\times 2Nn $维矩阵以及2Nn维向量相比是相当小的.

接下来给出一个通过异构多智能体系统网络拓扑变化可辨识性推断子系统可观测性的条件.

定理2. 考虑系统(3), 若系统$ (\Phi ,\;\Psi ) $的拓扑变化$ W\to \bar{W} $是可辨识的, 那么$ ({{A}_{i}},\;{{H}_{j}}) $是可观测的, 其中$ i=1,\;\cdots ,\;N $, $ 1\le j\le N $且$ j\ne i $.

证明. 由于网络化系统$ (\Phi ,\;\Psi ) $的拓扑变化$ W\to \bar{W} $是可辨识的, 根据引理2, 进一步可以得到系统$ (\Delta ,\;\Gamma ) $是可观的. 根据引理1, 进一步可以得到$ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right] = 2Nn $, 从而可知矩阵对$ \left[ \begin{matrix} s{{I}_{n}}-{{A}_{1}} \\ {{H}_{j}} \end{matrix} \right] $, $ 2\le j\le N $满秩, $ \cdots $, 矩阵对$ \left[ \begin{matrix} s{{I}_{n}}-{{A}_{N}} \\ {{H}_{j}} \end{matrix} \right] $, $ 1\le j\le N- 1 $满秩. 即, $ ({{A}_{i}},\;{{H}_{j}}) $是可观测的, 其中$ i=1,\;\cdots , N $, $ 1\le j\le N $且$ j\ne i $. □

注3. 通过定义新的系统$ (\Delta ,\;\Gamma ) $, 其中$ \Delta = { \rm{diag}}\{\Phi , \bar{\Phi }\} $, $ \Gamma =[\begin{matrix} I & -I \end{matrix}] $, 由系统$ (\Phi ,\;\Psi ) $拓扑变化可辨识得出新系统$ (\Delta ,\;\Gamma ) $可观测, 再根据可观测性判据进而得出满秩, 从而得到$ ({{A}_{i}},\;{{H}_{j}}) $可观测, 将网络化系统拓扑变化的可辨识性与可观测性建立起联系. 由系统的可辨识性可以直接得出$ ({{A}_{i}},\;{{H}_{j}}) $的可观测性, 即, $ ({{A}_{i}},\;{{H}_{j}}) $是可观测的, 是整个网络系统(3)可辨识的必要条件.

在实际中, 智能体系统的状态可能是不可观测的, 因此考虑通过系统输出轨迹Y来验证拓扑变化的可辨识性. 下面给出了通过检测网络系统的输出轨迹进而验证网络拓扑变化的可辨识性的充分性条件.

首先定义几个符号.

定义向量集合$ {{\Gamma }^{1}}(s)\;=\;\{\alpha \in {{{\bf{C}}}^{n}}|{{C}_{i}}\alpha \;=\;0\} $, $ {{\Gamma }^{2}}(s) = \{\alpha \in {{{\bf{C}}}^{n}}|(s{{I}_{n}}-{{A}_{i}})\alpha =0 $, $ \alpha \in {{\Gamma }^{1}}(s)\} $, 并定义矩阵集$ \Gamma(s)=\{[v_{1},\;\cdots,\;v_{N},\;v_{N+1},\;\cdots,\;v_{2N}]^{ {\rm{T}}}|v_{i} \in \Gamma^{2}(s)\} $.

令$ \eta=[(\eta^1)^ {\rm{T}},\;(\eta^2)^ {\rm{T}}]^ {\rm{T}} $表示$ \Xi ={ \rm{diag}}\{\Phi ,\;\bar{\Phi }\} $的特征向量, 其中$ (\eta^1)^ {\rm{T}}=[(\eta_1^1)^ {\rm{T}},\;\cdots,\;(\eta_N^1)^ {\rm{T}}]^ {\rm{T}} $, $ (\eta^2)^ {\rm{T}}= [(\eta_1^2)^ {\rm{T}},\;\cdots,\;(\eta_N^2)^ {\rm{T}}]^ {\rm{T}} $.

定理3. 假设$ \sigma ({{A}_{1}})=\cdots =\sigma ({{A}_{N}}) $, $ \eta _{i}^{1}\in {{\Gamma }^{1}}(s) $, $ \eta _{i}^{2}\in {{\Gamma }^{1}}(s) $, $ i=1,\;\cdots ,\;N $. 以下条件同时成立时, 网络拓扑变化$ W\to \bar{W} $是$ \Psi $ -可辨识的:

1) $ ({{A}_{i}},\;{{H}_{i}}) $是可控的, $ i=1,\;\cdots ,\;N $;

2) 任意$ s\in \sigma ({{A}_{i}}) $, 若$ {W}'\rho =0 $, 那么$ \rho =0 $. 其中$ \rho \in \Gamma (s) $, $ {W}'={ \rm{diag}}\{W,\;\bar{W}\} $;

3) 任意$ s\notin \sigma ({{A}_{i}}) $, $ { \rm{rank}}({{I}_{2Nn}}-({W}'\;\otimes \;{{I}_{n}}){\gamma }', (\Delta'\; \otimes \;{{I}_{n}}){\phi }')\;=\;2Nn $. 其中$ {\gamma }'\;=\;{ \rm{diag}}\{\gamma ,\;\gamma \} $, $ \gamma \;= { \rm{diag}}\{{{\gamma }_{1}},\;\cdots ,\;{{\gamma }_{N}}\} $, $ {{\gamma }_{i}}\;=\;{{(s{{I}_{n}}\;-\;{{A}_{i}})}^{-1}}{{H}_{j}} $, $ \Delta \;= { \rm{diag}}\{{{I}_{N}}, \;-{{I}_{N}}\} $, $ {\phi }'={ \rm{diag}}\{\phi ,\;\phi \} $, $ \phi ={ \rm{diag}}\{{{\phi }_{1}},\; \cdots , {{\phi }_{N}}\} $, $ {{\phi }_{i}}={{C}_{i}}{{(s{{I}_{n}}-{{A}_{i}})}^{-1}}{{H}_{j}} $, $ i=1,\;\cdots ,\;N $.

证明. 由引理2可知, 网络系统$ (\Phi ,\;\Psi ) $的拓扑变化$ W\to \bar{W} $是$ \Psi $ -可辨识的与系统$ (\Xi ,\;\Sigma ) $是可观测的是相等价的. 进而, 由引理1可知, 系统$ (\Xi ,\;\Sigma ) $是可观测的等价于$ (s{{I}_{2Nn}}-\Xi )\eta =0 $以及$ \Sigma \eta =0 $有唯一解$ \eta =0 $. 将$ (s{{I}_{2Nn}}-\Xi )\eta =0 $具体展开, 可以得到式(12). 将$ \Sigma \eta =0 $具体展开, 可以得到式(13).

由式(12) ~ (13), 可以进一步得到$ (s{{I}_{n}}-{{A}_{i}})\eta _{i}^{1}- $ $ \sum\nolimits_{j=1,\;j\ne i}^{N}{{{w}_{ij}}{{H}_{i}}\eta _{j}^{1}}\;=\;0 $, $ (s{{I}_{n}} - {{A}_{i}})\eta _{i}^{2} - \sum\nolimits_{j=1,\,j\ne i}^{N} {{{\bar{w}}}_{ij}} \times {{H}_{i}}\eta _{j}^{2}=0 $以及$ {{C}_{i}}(\eta _{i}^{1}-\eta _{i}^{2})=0 $, 其中$ i=1,\;\cdots ,\;N $.

若$ s\in \sigma ({{A}_{i}}) $, $ i=1,\;\cdots ,\;N $, 那么$\sum\nolimits_{j=1,\;j\ne i}^{N}{{w}_{ij}}\times \eta _{i}^{1} = 0$; 若$ \sum\nolimits_{j=1,\;j\ne i}^{N}{{{w}_{ij}}\eta _{i}^{1}}\ne 0 $, 那么H的列向量可由$ s{{I}_{n}}- {{A}_{i}} $的列向量线性表示, 从而可以得到$ { \rm{rank}}(s{{I}_{n}}- {{A}_{i}}, \, {{H}_{i}})={ \rm{rank}}(s{{I}_{n}}-{{A}_{i}})<n $, 即$ ({{A}_{i}}, \,{{H}_{i}}) $不是能控的, 这与定理3中条件1) 矛盾. 因此, 可以得到$ (s{{I}_{n}}- {{A}_{i}})\eta _{i}^{1}=0 $.

同理, 对于$ i=1,\,\cdots ,\,N $, 可以得到$ (s{{I}_{n}} - {{A}_{i}})\eta _{i}^{2}= 0 $. 由于$ \eta _{i}^{1}\in {{\Gamma }^{1}}(s) $, $ \eta _{i}^{2}\in {{\Gamma }^{1}}(s) $, 那么$ {{C}_{i}}\eta _{i}^{1}=0 $, $ {{C}_{i}}\eta _{i}^{2}= 0 $, 即$ \eta _{i}^{1}\in {{\Gamma }^{2}}(s) $, $ \eta _{i}^{2}\in {{\Gamma }^{2}}(s) $. 取$ \rho=[\eta_{1}^{1},\;\cdots,\;\eta_{N}^{1}, \;\eta_{1}^{2}, \cdots, \;\eta_{N}^{2}]^{ {\rm{T}}}\in\Gamma(s) $, 进而得到式(14). 由定理3中的条件2)可知, 当$ {W}'\rho =0 $时, 进而可以得到$ \rho =0 $, 这等价于$ \eta =0 $.

若$ s\;\notin\; \sigma ({{A}_{i}}) $, 其中$ i\;=\;1,\;\cdots ,\;N $. 令$ \xi _{i}^{1}\;= \sum\nolimits_{j=1,\;j\ne i}^{N} {{{w}_{ij}} \eta _{j}^{1}} $, 那么$\eta _{i}^{1} = {{(s{{I}_{n}}-{{A}_{i}})}^{-1}} \sum\nolimits_{j=1,\;j\ne i}^{N} {{w}_{ij}} \times{{H}_{i}}\eta _{j}^{1}$; $ \eta _{i}^{2}={{(s{{I}_{n}}-{{A}_{i}})}^{-1}} $$ \sum\nolimits_{j=1,\;j\ne i}^{N}{{{{\bar{w}}}_{ij}}{{H}_{i}}\eta _{j}^{2}} $ 可以写成:

令$ \xi^{1}=[(\xi_{1}^{1})^{ {\rm{T}}},\;\cdots,\;(\xi_{N}^{1})^{ {\rm{T}}}]^{ {\rm{T}}} $, 可以得到$ ({{I}_{Nn}}\;- (W\otimes {{I}_{n}})\gamma ){{\xi }^{1}}=0 $.

根据式(15), 由于$ \eta _{i}^{1}\in {{\Gamma }^{1}}(s) $, $ i=1,\;\cdots ,\;N $, 可以得到$ {{I}_{Nn}}\phi {{\xi }^{1}}=0 $. 令$ \xi _{i}^{2}=\sum\nolimits_{j=1,\;j\ne i}^{N}{{{{\bar{w}}}_{ij}}\eta _{j}^{2}} $, 那么:

令$ \xi^{2}=[(\xi_{1}^{2})^{ {\rm{T}}},\;\cdots,\;(\xi_{N}^{2})^{ {\rm{T}}}]^{ {\rm{T}}} $, 可以得到$ ({{I}_{Nn}}\;- (\bar{W}\otimes {{I}_{n}})\gamma ){{\xi }^{2}}=0 $. 在式(17)的基础上, 由于$ \eta _{i}^{2}\in {{\Gamma }^{1}}(s) $, $ i=1,\;\cdots ,\;N $, 可以得到$ -{{I}_{Nn}}\phi {{\xi }^{2}}=0 $. 令$ \xi=[(\xi^1)^ {\rm{T}},\;(\xi^2)^ {\rm{T}}]^ {\rm{T}} $, 即$ ({{I}_{2Nn}}-({W}'\otimes {{I}_{n}}){\gamma }')\xi =0 $, $ (\Delta' \otimes {{I}_{n}}){\phi }'\xi =0 $. 由于$ { \rm{rank}}({{I}_{2Nn}}-({W}'\otimes {{I}_{n}}){\gamma }', \;(\Delta' \otimes {{I}_{n}}){\phi }')=2Nn $, 所以$ \xi =0 $, 即$ \eta =0 $. 由引理2, $ (\Xi ,\;\Sigma ) $是可观测的, 这等价于系统$ (\Phi ,\;\Psi ) $的拓扑变化是$ \Psi $ -可辨识的.□

注4. 定理3提供了通过观察输出轨迹辨识具有不同内耦合矩阵异构网络系统拓扑变化的充分条件. 该条件考虑了智能体动力学的异构性以及系统的可控性. 在智能体系统和网络拓扑上分别验证这一条件在大规模网络中是可行的. 通过检测系统输出轨迹来验证拓扑变化的可辨识性, 新条件适用范围更广. 这也说明子系统$ ({{A}_{i}},\;{{H}_{i}}) $的可控性与拓扑变化的可辨识性密切相关.

3.2   典型网络拓扑变化可辨识性

第3.1节是对于一般结构网络拓扑变化的可辨识性分析, 本节考虑几种典型结构的有向网络在拓扑变化时能否检测到的问题. 本节考虑有向链状网络(如图 3所示)、有向星型网络(如图 4所示)以及有向环状网络(如图 5所示)三种典型的网络结构, 这些典型基本的网络结构也是组成大规模网络的基本单元, 因此对典型网络结构分析是必要的.

图 3  一个有向链状网络

Fig. 3  A directed chain network

下载: 全尺寸图片 幻灯片

图 4  一个有向星型网络

Fig. 4  A directed star network

下载: 全尺寸图片 幻灯片

图 5  一个有向环状网络

Fig. 5  A directed circle network

下载: 全尺寸图片 幻灯片

首先, 考虑有向链状网络和有向星型网络的可辨识性.

定理4. 考虑如图 3所示的有向链状网络系统(3)和如图 4所示的有向星型网络系统(3). 若拓扑变化是由于删除某条连边导致, 那么该拓扑变化$ W\to \bar{W} $是不可辨识的.

证明. 在如系统(3)所示的有向链状网络中,

当s是$ {{A}_{N}} $的特征值时, $ { \rm{rank}}(s{{I}_{n}}-{{A}_{N}})<n $. 将$ \left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right] $的前Nn列依次加到后Nn列, 可以得到$ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right]<2Nn $, 即拓扑变化$ W\to \bar{W} $不可辨识.

在如系统(3)所示的有向星型网络中,

当s是$ {{A}_{i}} \,(i = 2,\,\cdots ,\,N) $的特征值时, $ { \rm{rank}}(s{{I}_{n}}- {{A}_{i}})<n $. 将$ \left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right] $的前Nn列依次加到后Nn列, 可以得到$ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right]<2Nn $, 即拓扑变化$ W\to \bar{W} $是不可辨识的.□

注5. 定理4揭示了网络拓扑变化的局限性. 该定理指出, 在链状网络和星型网络系统中, 如果拓扑变化仅由于删除某条连边引起, 那么这种变化是不可辨识的. 在某些实际情境下, 人们无法仅通过观察网络的行为或性能变化来准确判断哪条连边被删除. 这对于实际网络的运行维护、故障排查以及容错系统的设计具有指导作用.

最后, 给出适用于有向环状网络的可辨识性条件.

定理5. 考虑如图 5所示的有向环状网络系统(3). 若拓扑变化是由于边权重改变导致, 若$ ({{A}_{i}}, {{H}_{i+1}}) $, $ i=1,\;\cdots ,\;N-1 $与$ ({{A}_{N}},\;{{H}_{1}}) $均是可观测的, 那么该拓扑变化$ W\to \bar{W} $是可辨识的.

证明. 在如系统(3)所示的有向环状网络中,

显然, 当:

时, $ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right]=2Nn $, 从而多智能体网络系统的拓扑变化是可辨识的. 式(19)等价于$ ({{A}_{1}},\;{{H}_{2}}),\; \cdots $, $ ({{A}_{N-1}},\;{{H}_{N}}) $, $ ({{A}_{N}},\;{{H}_{1}}) $均是可观测的. 此时拓扑变化$ W\to \bar{W} $是可辨识的.□

注6. 定理5给出了有向环状网络系统通过智能体动力学和内耦合矩阵判断网络边权重变化的充分条件. 通过观测系统输出辨识边权重变化, 对于实时监控和诊断系统状态, 发现并解决潜在问题, 设计更为有效的控制策略, 提升系统的性能都具有重要作用.

关于几种典型多智能体网络的可辨识性条件已经给出. 接下来通过一个简单的例子来说明定理5的可行性.

例3. 考虑一个由两个智能体组成的有向环状网络系统, 如图 6所示. 网络拓扑矩阵为$ W= \left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] $. 智能体1的状态矩阵$ {{A}_{1}}=\left[ \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right] $, 内耦合矩阵为$ {{H}_{1}}=\left[ \begin{matrix} 0 & 1 \\ 3 & 0 \end{matrix} \right] $. 智能体2的状态矩阵$ {{A}_{2}}=\left[ \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right] $, 内耦合矩阵为$ {{H}_{2}}=\left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right] $. 网络中边权重发生变化后, 网络拓扑矩阵变为$ \bar{W}=\left[ \begin{matrix} 0 & 2 \\ 3 & 0 \end{matrix} \right] $.

图 6  一个由两个智能体组成的有向环状网络系统

Fig. 6  A directed circular network system consisting of two agents

下载: 全尺寸图片 幻灯片

容易验证$ ({{A}_{1}},\;{{H}_{2}}) $, $ ({{A}_{2}},\;{{H}_{1}}) $均是可观测的. 可以得到结论: 在这个网络中, 改变边权重的拓扑变化$ W\to \bar{W} $是可辨识的.

4.   实例分析

4.1   无人驾驶车辆系统实例

本节通过无人驾驶车辆系统, 验证第3.1节一般网络结构下给出结果的有效性和可应用性.

考虑一个由4辆无人驾驶车辆构成的交通网络系统, 在双车道交通中执行自适应巡航和跟随任务, 如图 7所示. 两辆巡航车辆1和2根据彼此的相对位置保持一致性, 后面的两辆车3和4根据前车的位置保持最小安全距离.

图 7  无人驾驶车辆系统

Fig. 7  Autonomous vehicle system

下载: 全尺寸图片 幻灯片

根据车辆1的运动轨迹, 车辆2、车辆3和车辆4受控, 该系统可描述为(3)、(4)的形式, 其中:

当车辆1和车辆3之间的链路断开时, 无人驾驶车辆系统的拓扑矩阵发生变化:

通过计算可以得到对任意的$ i=1,\;\cdots ,\;4 $; $ 1\le j\le 4 $ 且 $ j\ne i $, $ ({{A}_{i}},\;{{H}_{j}}) $不可观测, 可知矩阵对$ \left[ \begin{matrix} s{{I}_{n}}-{{A}_{1}} \\ {{H}_{j}} \end{matrix} \right] $, $ 2\le j\le 4 $不满秩, $ \cdots $, 矩阵对$ \left[ \begin{matrix} s{{I}_{n}}-{{A}_{4}} \\ {{H}_{j}} \end{matrix} \right] $, $ 1\le j\le 3 $不满秩, 进一步可以得到$ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right] <2Nn $, 即拓扑变化$ W\to \bar{W} $是不可辨识的.

根据定理2, 可以得出其逆否定理: 当$ ({{A}_{i}},\;{{H}_{j}}) $不可观测时, 那么多智能体网络的拓扑变化是不可辨识的. 根据对无人驾驶车辆系统的实例分析验证了定理2的逆否定理, 考虑到定理2与逆否定理的等价关系, 同样验证了定理2的可行性.

通过这个例子说明了本文提出的定理2对于某些实际网络运行系统具有一定指导作用.

4.2   无人机系统实例

本节通过无人机编队系统, 验证第3.2节典型网络结构给出结果的有效性和可应用性.

考虑一个由四架无人机组成的编队避障系统, 采用长机−僚机模式, 即指定一架无人机作为长机, 其他作为僚机, 如图 8所示. 当僚机因遭遇大范围障碍物而失去与长机的信号联系时, 分析系统是否能够检测到这种变化并重新组织队形.

图 8  编队避障无人机系统

Fig. 8  Formation obstacle avoidance UAV system

下载: 全尺寸图片 幻灯片

显然, 这个无人机网络化系统为具有有向星型的网络结构. 该系统可写成(3)、(4)的形式, 其中:

当僚机2与长机1之间的链路断开时, 多智能体的网络拓扑矩阵发生变化:

在如图 8所示的有向星型网络中,

当s是$ {{A}_{i}} $$ (i=2,\;3,\;4) $的特征值时, $ { \rm{rank}}(s{{I}_{n}}- {{A}_{i}})<n $. 经过计算可以得到$ { \rm{rank}}\left[ \begin{matrix} s{{I}_{2Nn}}-\Delta \\ \Gamma \end{matrix} \right]\;< 2Nn $, 即拓扑变化$ W\to \bar{W} $是不可辨识的. 其中$ \Delta = { \rm{diag}}\{\Phi ,\;\bar{\Phi }\} $, $ \Gamma = [\begin{matrix} I & -I \end{matrix}] $.

根据对无人机编队避障系统的实例分析验证了定理4, 当存在僚机与长机之间的链路断开时, 多智能体网络的拓扑变化是不可辨识的. 通过引理2同样可以验证该无人机系统发生链路断开的拓扑变化的可辨识性. 然而, 在计算时涉及24×24维和12×24维矩阵, 矩阵规模是非常大的, 这里省略了具体的计算过程.

通过这个例子说明了本文提出的定理4对于某些实际网络运行维护和故障排查以及设计容错系统具有一定指导作用.

5.   结束语

本文研究了异构智能体且具有不同内耦合矩阵的有向网络拓扑变化的可辨识性问题. 首先, 构建了具有不同内耦合矩阵的异构智能体网络模型, 并通过两个例子说明了异构耦合矩阵网络与同构耦合矩阵网络在网络拓扑可辨识性上存在本质区别. 其次, 针对一般网络结构, 分别给出了通过检测系统状态和系统输出轨迹验证网络拓扑可辨识性的充分性条件, 以及网络子系统可观测是整个网络系统拓扑变化可辨识的必要条件. 并针对典型的网络结构, 给出更简单实用的拓扑变化可辨识的判断条件. 最后, 通过实际例子说明了结论的可行性及有效性.

尽管本文对异构智能体网络拓扑变化可辨识给出了充分及必要条件, 但针对实际多智能体网络系统如何开发具体辨识算法以及如何通过网络系统输出辨识网络结构, 还需要考虑网络系统的可辨识性与可控性可观测性的关系, 也是需要进一步研究的问题.