KZYJC
控制与决策
Control and Decision
1001-0920
控制与决策编辑部
中国沈阳
kzyjc-36-6-1442
10.13195/j.kzyjc.2019.1106
TP273
A
论文与报告
Papers and Reports
基于影响度介数中心性的多智能体牵制控制算法
Multi-agent pinning control algorithm based on betweenness centrality with influence degree
何
明
HE
Ming
何明(1978-), 男, 教授, 博士生导师, 从事智联网、无人指控等研究, E-mail: paper_review@126.com
paper_review@126.com
马
子玉
MA
Zi-yu
马子玉(1996-), 男, 硕士生, 从事无人机指控的研究, E-mail: paper_review@126.com
paper_review@126.com
*
刘
锦涛
LIU
Jin-tao
刘锦涛(1981-), 男, 讲师, 博士, 从事多智能体协同控制的研究, E-mail: top1944@163.com
top1944@163.com
郑
旭东
ZHENG
Xu-dong
郑旭东(1963-), 男, 教授, 博士生导师, 从事无人机指控等研究, E-mail: 2528996681@163.com
2528996681@163.com
周
波
ZHOU
Bo
周波(1982-), 男, 讲师, 博士, 从事复杂网络建模的研究, E-mail: zhoubo1982@163.com
zhoubo1982@163.com
解放军陆军工程大学 指挥控制工程学院,南京 210007
Command And Control Engineering College, Army Engineering University of PLA, Nanjing 210007
马子玉, E-mail: paper_review@126.com
6
2021
36
6
1442
1448
1
8
2019
16
1
2020
版权所有©《控制与决策》编辑部2021
Copyright ©2021 Control and Decision.
2021
针对多智能体系统在牵制控制过程中最终收敛时系统稳定性较差的问题, 设计一种影响度矩阵, 重新构建介数中心性算法来完成牵制控制节点选择工作.首先, 根据子网的度分布计算影响度矩阵; 其次, 由影响度矩阵计算子网的介数中心性分布矩阵; 最后, 根据介数中心性选择牵制控制节点, 既保留个体本身的重要性, 也引入邻居个体重要性对其影响程度.经过对比实验验证了影响度介数中心性算法可有效增强多智能体系统的鲁棒性并提高系统的收敛速度.
Aiming at the poor stability of the final convergence of multi-agent systems in the process of pinning control, we design an influence degree matrix and reconstruct an intermediate centrality algorithm to complete the selection of pinning control nodes. Firstly, an influence degree matrix is calculated according to degree distribution of subnets. Then, the influence degree matrix is used to calculate the intermediate centrality distribution matrix of the subnet. Finally, traction control nodes are selected according to the distribution of betweenness centrality. We not only preserve the importance of the individual in the system, but also introduce the influence of the importance of the individual in the neighborhood. Comparative experiments show that the betweenness centrality algorithm can greatly enhance the robustness of multi-agent systems and improve the convergence speed of the system.
多智能体
牵制控制
一致性
影响度
介数中心性
multi-agent
pinning control
consensus
influence
betweenness centrality
国家重点研发计划项目
2018YFC0806900
中国博士后科学基金项目
2018M633757
江苏省重点研发计划项目
BE2016904
江苏省重点研发计划项目
BE2017616
江苏省重点研发计划项目
BE2018754
江苏省重点研发计划项目
BE2019762
国家重点研发计划项目(2018YFC0806900);中国博士后科学基金项目(2018M633757);江苏省重点研发计划项目(BE2016904, BE2017616, BE2018754, BE2019762)
0
引言
在自然界中群体行为是物种常见的生存方式, 如协同狩猎的狼群、“人”字迁徙的雁群、结队觅食的鱼群、分工协作的蜂群等. 学者经过多年对这些群落的深入研究, 提出多智能体概念. 其特征是从简单的局部规则进化到协调的全局行为, 具有自适应性、鲁棒性、分散性和自组织性等特点[1 ] .
早期的研究集中在建模和仿真上. Vicsek等[2 ] 提出的Vicsek模型凭借其直观算法和对状态的清晰描述, 得到学者的广泛关注. 但该模型仅实现群集整体上的有序运动, 而忽略了智能体间的碰撞问题. Reynolds[3 ] 在大量观察生物群体行为的基础上提出Boids模型, 对群体智能行为提出3种规则: 碰撞避免、聚集和速度匹配[4 ] . 人工多智能体集群为实现整体有序统一运动, 需要在每个智能体上都安装全局控制器. 这对于大型集群而言显然是不可行的, 因而蜂拥控制[5 -7 ] 由此提出: 仅需将控制信息发送到网络中部分节点, 通过局部信息交互使所有智能体的运动状态渐近一致并且彼此间距离都趋于相同. Olfati[8 ] 基于Boids模型提出两种可在自由空间中收敛和一种实现躲避障碍的蜂拥控制算法, 但该算法要求集群内所有智能体都可接收到控制信号. Su等[9 ] 在此基础上提出牵制控制算法, 证明仅需若干个关键节点获得控制信息, 整个集群凭借局部信息交互使系统最终收敛. 随后文献[10 ]发现驱动节点的最少数目随着网络互连密度的增高而降低, 但网络可控性却在不断增大. Zhao等[11 ] 提出对单节点采用非独立控制策略以降低系统总能量上界, 从而实现控制. 针对大型非线性动力学复杂网络, DeLellis等[12 ] 给出寻找控制节点的次优解, 并设置部分控制网络所需的最小耦合和控制增益的界, 将理论分析转化为整数线性规划(ILP).
多智能体在聚集过程中会发生拓扑变化, 因而学者将复杂网络的研究成果应用于多智能体集群控制中. 文献[13 ]和文献[14 ]分别提出在网络中安排一个领导节点, 该节点不接收其他节点信息, 而是在网路中持续广播自身的运动信息. 针对复杂网络无标度特性, 文献[5 ]提出基于局部线性反馈的控制方式, 相较于随机控制方式, 连通性越高的节点需要的控制器越少. 文献[15 ]提出一种基于李亚普诺夫稳定性的控制方法, 该方法将系统稳定性问题转化为对一个描述网络拓扑结构的简单矩阵的负确定性度量, 采用包含增加边权重和删除节点两种操作的归一化方法对动态复杂网络进行分析.
在基于复杂网络的蜂拥控制中, 如何在有限资源的条件下优化网络性能(如提高收敛速度、降低能耗等)是研究的重点. 关键节点的选择可帮助我们理解信息传播方式. 网络节点的影响力是复杂网络研究中一个关键问题, 重要节点对网络功能起主导作用. 为确定节点在复杂网络中的重要程度, 研究人员提出度中心性、介数中心性、特征向量中心性等度量方法. 文献[16 ]提出度中心性算法寻找控制节点, 但文章并未考虑到度相同的情况下如何选择牵制控制节点, 依靠该算法寻找到的控制节点随机性大, 易造成系统不稳定. 文献[17 ]中提出利用\begin{document}$ k $\end{document} -shell算法寻找控制节点, 并引入控制节点与领导者的距离来解决两个节点\begin{document}$ k_{s} $\end{document} 相同时的问题. 但\begin{document}$ k $\end{document} -shell是一种粗粒化节点分类方法, 节点与领导者的距离将极大影响控制节点的选择. 文献[18 ]证明了在拓扑结构不断变化的动态网络中, 接受控制信息的节点介数中心性越高, 整个系统获得信息的时间也就越短. 本文在考虑邻居节点重要性的前提下, 设计一种影响度矩阵, 重新构建影响度介数中心性算法(betweenness centrality with influence degree, BCID)来寻找牵制控制节点, 并证明系统最终达到收敛, 形成整体上的有序运动. 通过对比实验验证了基于所提出算法的多智能体系统有着较强的鲁棒性, 极大提高了系统收敛速度.
1
理论基础
假设由\begin{document}$ n $\end{document} 个独立个体组成的多智能体系统, 个体\begin{document}$ i $\end{document} 的控制方程为
1 \begin{document}$ \begin{align} &\begin{cases} {{\dot {{{\mathit{\boldsymbol{q}}}}}}_i} = {{{{\mathit{\boldsymbol{p}}}}}_{i}}, \\ {{\dot {{{\mathit{\boldsymbol{p}}}}}}_i} = {{{{\mathit{\boldsymbol{u}}}}}_{i}}. \end{cases} \end{align} $\end{document}
其中\begin{document}$ {{{{\mathit{\boldsymbol{q}}}}}_{i}}, {{{{\mathit{\boldsymbol{p}}}}}_{i}}, {{{{\mathit{\boldsymbol{u}}}}}_{i}}\in{{{{\mathit{\boldsymbol{R}}}}}^{m}}(i = 1, 2, \ldots, n, m = 2, 3) $\end{document} , 分别表示个体\begin{document}$ i $\end{document} 的位置矢量、速度矢量和控制输入[8 ] . 若感知半径\begin{document}$ {r>0} $\end{document} , 则个体\begin{document}$ i $\end{document} 的邻域可表示为
2 \begin{document}$ \begin{align} {{{N}}_i} = \{ j\in {{N: }}\|{{{{\mathit{\boldsymbol{q}}}}}_i}-{{{{\mathit{\boldsymbol{q}}}}}_j}\|\leqslant{{r, i}} \ne {{j\} }}, \end{align} $\end{document}
\begin{document}$ {\|Z\|} $\end{document} 为欧氏距离. 将互为邻居的智能体间用直线连接, 系统的拓扑结构可用图论知识表示: 图\begin{document}$ G(V, E, A) $\end{document} , 点集合\begin{document}$ V $\end{document} 代表个体\begin{document}$ {\{1, 2, \ldots, n\}} $\end{document} , 边集合\begin{document}$ E = \{ (i, j) \!\in\! V \!\times\! V, j \!\in\! {N_i}\} $\end{document} 代表智能体间存在通信. \begin{document}$ {A} = [{{a}_{ij}}]\!\in\! {{{{\mathit{\boldsymbol{R}}}}}^{n}}\!\times\! {{{{\mathit{\boldsymbol{R}}}}}^{n}} $\end{document} 为邻接矩阵.
\begin{document}$ a_{ij} = \begin{cases} 1, \, (i, j) \in E;\\ 0, \, {\rm otherwise}. \end{cases} $\end{document}
其中一个节点的度被定义为其可到达网络中点的数目, 即\begin{document}$ {d_i} = \sum\limits_{j = 1}^n {{a_{ij}}} $\end{document} . 图的度矩阵则是对角线为各节点度的对角矩阵, 即\begin{document}$ D = {\rm diag}[{d_1}, \ldots, {d_n}] $\end{document} .
Laplacian矩阵被定义为
3 \begin{document}$ \begin{align} L = D - A, \end{align} $\end{document}
其谱含有关于图结构特性的信息, 最小非零特征值直接反映了图连通的鲁棒性, 满足
4 \begin{document}$ \begin{align} {{{\mathit{\boldsymbol{z}}}}}^{\rm T}( {{{{\mathit{\boldsymbol{L}}}}} \otimes {{{{\mathit{\boldsymbol{I}}}}}_m}}){{{\mathit{\boldsymbol{z}}}}} = \frac{1}{2} \sum\limits_{j \in {{\cal N}_i}} {{a_{ij}}{{( {{{{{\mathit{\boldsymbol{z}}}}}_j} - {{{{\mathit{\boldsymbol{z}}}}}_i}})}^2}} . \end{align} $\end{document}
为避免个体间发生碰撞, 规定多智能体系统的最终状态为
5 \begin{document}$ \begin{align} \ \|{{{{\mathit{\boldsymbol{q}}}}}_i} - {{{{\mathit{\boldsymbol{q}}}}}_j}|| = d, \; (i, j) \in E, d < r, \end{align} $\end{document}
并将式(5)命名为\begin{document}$ \alpha $\end{document} -lattices系统[8 ] . 但因个体存在自主行动的能力, 导致\begin{document}$ \alpha $\end{document} -lattices系统十分不稳定, 最终演变为
6 \begin{document}$ \begin{align} -\delta+d\leqslant\|{{{{\mathit{\boldsymbol{q}}}}}_i}-{{{{\mathit{\boldsymbol{q}}}}}_j}\|\leqslant\delta + d, \; (i, j) \in E. \end{align} $\end{document}
式(6)被称为类\begin{document}$ \alpha \rm{-} {\rm lattices} $\end{document} 系统, 两种系统如图 1 所示.
1
两种系统
2
控制一致性证明
考虑到一个由\begin{document}$ n $\end{document} 个智能体构成的控制复杂网络, 其控制输入为
7 \begin{document}$ \begin{align} {u_i} = f_i^g + f_i^d + {h_i}f_i^\gamma. \end{align} $\end{document}
其中: \begin{document}$ {f_i^g} $\end{document} 为势函数梯度项, 促使集群的形成; \begin{document}$ {f_i^d} $\end{document} 为速度一致项, 使所有智能体速度渐近一致; \begin{document}$ {f_i^\gamma} $\end{document} 为导航反馈项, 包含领导者的运动信息; \begin{document}$ {h_i} $\end{document} 为牵制控制节点选择项.
\begin{document}$ {h_i} = \begin{cases} 1, \; i\rm{为牵引控制节点};\\ 0, \; {\rm otherwise}. \end{cases} $\end{document}
8 \begin{document}$ \begin{align} &f_i^g = \sum\limits_{j \in {N_i}} {{\phi_\alpha }} (\|{{{{\mathit{\boldsymbol{q}}}}}_j} - {{{{\mathit{\boldsymbol{q}}}}}_i}\|{_\sigma }){n_{ij}}, \\ &{n_{ij}} = \frac{{{{{\mathit{\boldsymbol{q}}}}}_j} - {{{{\mathit{\boldsymbol{q}}}}}_i}}{\sqrt {1 + \varepsilon\|{{{{\mathit{\boldsymbol{q}}}}}_j} - {{{{\mathit{\boldsymbol{q}}}}}_i}\|{^2}}}. \end{align} $\end{document}
9 \begin{document}$ \begin{align} &f_i^d = \sum\limits_{j \in {N_i}} {{a_{ij}}(t)({{{{\mathit{\boldsymbol{p}}}}}_j} - {{{{\mathit{\boldsymbol{p}}}}}_i})}. \end{align} $\end{document}
10 \begin{document}$ \begin{align} &f_i^\gamma = - {c_1}({{{{\mathit{\boldsymbol{q}}}}}_i} - {{{{\mathit{\boldsymbol{q}}}}}_\gamma }) - {c_2}({{{{\mathit{\boldsymbol{p}}}}}_i} - {{{{\mathit{\boldsymbol{p}}}}}_\gamma }), \; {c_1}, {c_2} > 0. \end{align} $\end{document}
其中: \begin{document}$ {{{{\mathit{\boldsymbol{q}}}}}_\gamma } $\end{document} 和\begin{document}$ {{{{\mathit{\boldsymbol{p}}}}}_\gamma} $\end{document} 分别代表虚拟领导者的位置和速度矢量. 记\begin{document}$ {\tilde{{{\mathit{\boldsymbol{q}}}}}_i} = {{{{\mathit{\boldsymbol{q}}}}}_i} - {{{{\mathit{\boldsymbol{q}}}}}_\gamma}, {\tilde{{{\mathit{\boldsymbol{p}}}}}_i} = {{{{\mathit{\boldsymbol{p}}}}}_i} - {{{{\mathit{\boldsymbol{p}}}}}_\gamma } $\end{document} , 则
11 \begin{document}$ \begin{align} \left\{ \begin{array}{l} {{\dot{\tilde{{{\mathit{\boldsymbol{q}}}}}}}_i} = {{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i}, \\ {{\dot{\tilde{{{\mathit{\boldsymbol{p}}}}}}}_i} = {{\tilde{{{\mathit{\boldsymbol{u}}}}}}_i}, \end{array} \right. i = 1, 2, \ldots, n. \end{align} $\end{document}
令\begin{document}$ {{{{\mathit{\boldsymbol{q}}}}}_{ij}} = {{{{\mathit{\boldsymbol{q}}}}}_i} - {{{{\mathit{\boldsymbol{q}}}}}_j}, {{\tilde{{{\mathit{\boldsymbol{q}}}}}}_{ij}} = {{\tilde{{{\mathit{\boldsymbol{q}}}}}}_{i}}-{{\tilde{{{\mathit{\boldsymbol{q}}}}}}_{j}} $\end{document} , 显然\begin{document}$ {{\tilde{{{\mathit{\boldsymbol{q}}}}}}_{ij}} = {{{{\mathit{\boldsymbol{q}}}}}_{ij}} $\end{document} . 记\begin{document}$ {\tilde{{{\mathit{\boldsymbol{q}}}}}} = {\rm col}({{\tilde{{{\mathit{\boldsymbol{q}}}}}}_1}\ldots {{\tilde{{{\mathit{\boldsymbol{q}}}}}}_n}), {\tilde{{{\mathit{\boldsymbol{p}}}}}} = {\rm col}({{\tilde{{{\mathit{\boldsymbol{p}}}}}}_1}\ldots {{\tilde{{{\mathit{\boldsymbol{p}}}}}}_n}) $\end{document} , 系统的总能量由总势能和相对动能构成, 即
12 \begin{document}$ \begin{align} &Q({\tilde{{{\mathit{\boldsymbol{q}}}}}}, {\tilde{{{\mathit{\boldsymbol{p}}}}}}) = \frac{1}{2} \sum\limits_{i = 1}^n {({U_i}({\tilde{{{\mathit{\boldsymbol{q}}}}}}) + {{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i}^{\rm T}{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i)}, \end{align} $\end{document}
13 \begin{document}$ \begin{align} &{U_i}({\tilde{{{\mathit{\boldsymbol{q}}}}}}) = \sum\limits_{j = 1, j \ne i}^n {{\phi_\alpha }} (\|{{\tilde{{{\mathit{\boldsymbol{q}}}}}}_{ij}}\|{_\sigma })+{h_i}{c_1}{{\tilde{{{\mathit{\boldsymbol{q}}}}}}_i}^{\rm T}{{\tilde{{{\mathit{\boldsymbol{q}}}}}}_i}. \end{align} $\end{document}
若集群内个体运动方程为式(1), 控制输入为式(7), 初始能量\begin{document}$ {Q_0} $\end{document} 为有限值, 则有如下定理成立.
定理1 网络内存在的边将不会发生断裂, 系统逐渐收敛.
定理2 所有智能体的最终速度将与虚拟领导者保持一致.
定理3 假设系统初始能量\begin{document}$ {Q_0} $\end{document} 满足\begin{document}$ {Q_0} < (k + 1) {\psi _\alpha }(0), {\psi _\alpha }(z) = \int\nolimits_{{d_\alpha }}^z {{\phi _\alpha }(s){{\rm d}s}} $\end{document} 为相对势能, 则系统内至多有\begin{document}$ k $\end{document} 对智能体可能发生碰撞(当\begin{document}$ k = 0 $\end{document} 时, 系统将不会发生碰撞).
2.1
网络连通性证明
假设1 无向图初始状态\begin{document}$ {G_0} $\end{document} 是连通的(注: 若系统初始状态不是连通的, 分为\begin{document}$ m $\end{document} 个子网, 则每个子网至少有一个牵制点, 可得到相同的结论).
能量函数\begin{document}$ Q(t) $\end{document} 在\begin{document}$ t $\end{document} 时刻的导数为
14 \begin{document}$ \begin{align} \dot Q = \;&\frac{1}{2}\sum\limits_{i = 1}^n {{{\dot U}_i}} + \sum\limits_{i = 1}^n{{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i}^{\rm T}{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i = \\ &-{{\tilde{{{\mathit{\boldsymbol{p}}}}}}^{\rm T}}[(L(t) + {c_2}H(t)) \otimes {I_n}]{\tilde{{{\mathit{\boldsymbol{p}}}}}}, \end{align} $\end{document}
其中\begin{document}$ H(t) = {\rm diag}[{h_1}\ldots{h_n}] $\end{document} . 因为矩阵\begin{document}$ L $\end{document} 和\begin{document}$ H $\end{document} 都为半正定矩阵[8 ] , 所以在\begin{document}$ t $\end{document} 时刻\begin{document}$ \dot Q(t)\leqslant0 $\end{document} , 系统总能量
15 \begin{document}$ \begin{align} Q(t)\leqslant{Q_0}\leqslant{Q_{\max }}. \end{align} $\end{document}
由人工势能函数的定义可知: \begin{document}$ {\psi _\alpha }(z)\leqslant{Q_0}\leqslant{Q_{\max }} $\end{document} , 因为系统初始状态是连通的, 所有个体的距离都不超过\begin{document}$ r $\end{document} , 这表明此时网络中已存在的边不会发生断裂. 假设经过\begin{document}$ \Delta t $\end{document} 时间后, 网络中新添入\begin{document}$ m $\end{document} 条边, 新增加的边的势能都是有限的, 所以
16 \begin{document}$ \begin{align} Q(t + \Delta t) \leqslant{Q_0} + m{\psi _\alpha }(\|d\|{_\sigma })\leqslant{Q_{\max }}. \end{align} $\end{document}
由此类推, 在时间段\begin{document}$ [{t_k}, {t_k} + \Delta t) $\end{document} 中能量\begin{document}$ {Q_t} $\end{document} 对时间的导数为
17 \begin{document}$ \begin{align} \dot Q(t) = - {{\tilde{{{\mathit{\boldsymbol{p}}}}}}^{\rm T}}[(L(t) + {c_2}H(t)) \otimes {I_n}]{\tilde{{{\mathit{\boldsymbol{p}}}}}}\leqslant0. \end{align} $\end{document}
这表明随着时间推移, 系统中已存在的边将无断开的可能性, 而初始网络\begin{document}$ {G(0)} $\end{document} 是连通的, 所以系统将始终保持着连通.
2.2
速度一致性证明
由式(12)和(15)可得到\begin{document}$ {{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i}^{\rm T}{\tilde{{{\mathit{\boldsymbol{p}}}}}}_i\leqslant2{Q_0} $\end{document} , 所以多智能体系统中个体\begin{document}$ i $\end{document} 与虚拟领导者的速度差异不超过\begin{document}$ \sqrt {2{Q_0}} $\end{document} .定义集合
18 \begin{document}$ \begin{align} \varOmega = \{{{[{{\tilde{{\mathit{\boldsymbol{q}}}}}}^{\rm T}, {{\tilde{{\mathit{\boldsymbol{p}}}}}^{\rm T}}]}^{\rm T}}\in {{{{\mathit{\boldsymbol{R}}}}}^{2Nn}}|Q\leqslant{{Q}_{\max }}\} \end{align} $\end{document}
为正不变集, 依据LaSalle不变性原理[19 ] , 最终集合会趋向最大不变集
19 \begin{document}$ \begin{align} S = \{{{[{{\tilde{{\mathit{\boldsymbol{q}}}}}^{\rm T}}, {{\tilde{{\mathit{\boldsymbol{p}}}}}^{\rm T}}]}^{\rm T}}\in {{{{\mathit{\boldsymbol{R}}}}}^{2Nn}}|\dot{Q} = 0\}. \end{align} $\end{document}
由方程(14), 可得出
20 \begin{document}$ \begin{align} &\dot Q = - {{\tilde{{\mathit{\boldsymbol{p}}}}}^{\rm T}}[(L(t) + {c_2}H(t)) \otimes {I_n}]{\tilde{{\mathit{\boldsymbol{p}}}}} = \\ &- {{\tilde{{\mathit{\boldsymbol{p}}}}}^{\rm T}}[L(t) \otimes {I_n}]{\tilde{{\mathit{\boldsymbol{p}}}}}-{{{c}}_2}{{\tilde{{\mathit{\boldsymbol{p}}}}}^{\rm T}}[H(t) \otimes {I_n}]{\tilde{{\mathit{\boldsymbol{p}}}}} = 0. \end{align} $\end{document}
因而
21 \begin{document}$ \begin{align} &-{{{\tilde{{\mathit{\boldsymbol{p}}}}}}^{\rm T}}[L(t) \otimes {I_n}]{\tilde{{\mathit{\boldsymbol{p}}}}} = 0, \\ &\; {{{c}}_2}{{{\tilde{{\mathit{\boldsymbol{p}}}}}}^{\rm T}}[H(t) \otimes {I_n}]{\tilde{{\mathit{\boldsymbol{p}}}}} = 0, \end{align} $\end{document}
当且仅当\begin{document}$ {{\tilde{{\mathit{\boldsymbol{p}}}}}_1} = \ldots = {{\tilde{{\mathit{\boldsymbol{p}}}}}_N} = 0 $\end{document} , 即\begin{document}$ {{\mathit{\boldsymbol{p}}}_1} = \ldots = {{{p}}_N} = {{{p}}_\gamma } $\end{document} 时, 等式成立. 所以系统最终达到收敛, 每个智能体速度等于虚拟领导者速度.
2.3
碰撞避免
已知系统初始能量\begin{document}$ Q_0 $\end{document} 为有限值, 满足\begin{document}$ {Q_0} < (k + 1){\psi_\alpha}(0) $\end{document} . 同时假设在\begin{document}$ {t^ * } > 0 $\end{document} 时刻系统内超过\begin{document}$ k $\end{document} 对不同智能体发生碰撞, 则在\begin{document}$ {t^ * } $\end{document} 时刻系统内至少有\begin{document}$ k+1 $\end{document} 对不同智能体发生碰撞. 此刻系统能量至少为\begin{document}$ (k + 1){\psi _\alpha }(0) $\end{document} , 有
22 \begin{document}$ \begin{align} {Q_0}\geqslant Q({t^ * })\geqslant(k + 1){\psi _\alpha }(0). \end{align} $\end{document}
与原有假设\begin{document}$ {Q_0}\leqslant(k + 1){\psi _\alpha }(0) $\end{document} 相冲突, 这意味着在\begin{document}$ t > 0 $\end{document} 的任何时刻系统内至多有\begin{document}$ k $\end{document} 对不同智能体发生碰撞. 因此当\begin{document}$ k = 0 $\end{document} 时, 系统将不会发生碰撞.
3
影响度介数中心性
3.1
介数中心性
介数中心性是图论中描述节点重要性的经典概念. 它认为, 当信息沿最短路径传播时, 节点的重要性与节点控制信息传输的能力相关, 即与通过节点的最短路径数目有关. 具体地, 节点\begin{document}$ i $\end{document} 的介数中心性定义为
23 \begin{document}$ \begin{align} {\nu _i} = \sum\limits_{s \ne t \ne i}{\frac{{n_{{{ts}}}^i}}{{{g_{ts}}}}}. \end{align} $\end{document}
其中: \begin{document}$ {{{g}}_{{{ts}}}} $\end{document} 代表节点\begin{document}$ t $\end{document} 与\begin{document}$ s $\end{document} 间存在的最短路径数目, \begin{document}$ {{n}}_{ts}^i $\end{document} 代表节点\begin{document}$ t $\end{document} 与\begin{document}$ s $\end{document} 的最短路径穿过节点\begin{document}$ i $\end{document} 的路径数目.
在多智能体系统中, 控制节点承担着引导集体宏观运动的任务, 若介数中心性高的个体失去联系, 则整个系统很可能会分裂成若干孤立的小团体. 不仅如此, 牵制控制节点的重要程度也应该与其相邻节点的重要性有关.本文引入影响度矩阵, 用以表征某一节点的邻居节点对其影响程度.
3.2
影响度矩阵
设节点\begin{document}$ i $\end{document} 与节点\begin{document}$ j $\end{document} 的邻域分别为\begin{document}$ {N_i} $\end{document} 和\begin{document}$ {N_j} $\end{document} , 则节点\begin{document}$ j $\end{document} 对节点\begin{document}$ i $\end{document} 的影响程度[20 ] 定义为
24 \begin{document}$ \begin{align} {\omega _{ij}} = \frac{{|{N_i} \bigcap {N_j}{{|}}}}{{|{N_i} \bigcup {N_j}{{|}}}}, \; i \ne j. \end{align} $\end{document}
其中: \begin{document}$ {N_i} \bigcap {N_j} $\end{document} 代表节点\begin{document}$ i $\end{document} 的邻域与节点\begin{document}$ j $\end{document} 的邻域的交集, \begin{document}$ {N_i} \bigcup {N_j} $\end{document} 代表节点\begin{document}$ i $\end{document} 的邻域与节点\begin{document}$ j $\end{document} 的邻域的并集, 分别为
25 \begin{document}$ \begin{align} \left\{ \begin{array}{l} |{N_i} \bigcap {N_j}| = \sum\limits_{k = 1}^n {{a_{ik}} \bigwedge {a_{jk}}}, \\[10pt] |{N_i} \bigcup {N_j}| = \sum\limits_{k = 1}^n {{a_{ik}} \bigvee {a_{jk}}}, \end{array} \right. i \ne j. \end{align} $\end{document}
符号\begin{document}$ “ \bigwedge” $\end{document} 和\begin{document}$ “ \bigvee” $\end{document} 分别代表逻辑与运算和逻辑或运算. 这表明节点\begin{document}$ i $\end{document} 和节点\begin{document}$ j $\end{document} 共同邻接点越多, 彼此间影响力越大.
若某节点对恰好是两个子群间沟通的桥梁, 如图 2 所示, 个体\begin{document}$ A $\end{document} 、\begin{document}$ B $\end{document} 介数中心性很高, 但没有共同的邻居节点, 其\begin{document}$ {\omega _{ AB}} = 0 $\end{document} , 彼此间影响力为零. 为解决此类问题, 在网络中设置一个虚拟节点\begin{document}$ S $\end{document} , 如图 3 所示, 网络中每个节点都与之相连, 确保任何节点对至少有一个公共邻居节点. 但原不相邻的节点间将对彼此产生影响, 所以设立虚拟节点的方法仍存在不足.
2
多智能体系统系统
3
引入虚拟节点的网络
又如图 4 , 在图 4 的网络关系网中, 若按式(24)计算, 图 (4a) 中节点3对节点7的影响度\begin{document}$ \omega_{73}^a = {3}/{7} $\end{document} , 图 (4b) 中节点3对节点7的影响度\begin{document}$ \omega _{73}^b = {3}/{9} $\end{document} . 但在实际情况中, 因为图 (4b) 节点3与节点7间存在连边, 应比图 (4a) 产生更大的影响力.
4
网络关系网
结合图 3 中引入虚拟节点的思想, 将虚拟节点\begin{document}$ S $\end{document} 与网络中所有节点重合, 即节点\begin{document}$ i(i = 1, 2, \ldots, N) $\end{document} 与自身相连接, 其领域集合中将包含\begin{document}$ i $\end{document} . 这样既可以确保任意两个相邻节点之间至少有两个相同的邻居节点, 也可避免两不相邻的节点间仍产生影响的问题.
定义拓展邻接矩阵\begin{document}$ \tilde A = [{\tilde a_{ij}}], \tilde A = A + {I_n} $\end{document} . 节点\begin{document}$ i $\end{document} 与节点\begin{document}$ j $\end{document} 邻域的交集与并集重写为
26 \begin{document}$ \begin{align} \begin{cases} |{{\tilde N}_i} \bigcap {{\tilde N}_j}| = \sum\limits_{k = 1}^n {{{\tilde a}_{ik}} \bigwedge {{\tilde a}_{jk}}}, \\[8pt] |{{\tilde N}_i} \bigcup {{\tilde N}_j}| = \sum\limits_{k = 1}^n {{{\tilde a}_{ik}} \bigvee {{\tilde a}_{jk}}}. \end{cases} \end{align} $\end{document}
重新计算图 4 中节点3对节点7的影响性, 可得到影响度\begin{document}$ \omega _{73}^a = {3}/{9} $\end{document} 和\begin{document}$ \omega _{73}^b = {5}/{9} $\end{document} .
两节点间对彼此的影响力还应与本身重要程度相关. 例如在社交网络, \begin{document}$ C $\end{document} 和\begin{document}$ D $\end{document} 两人互为朋友, 但\begin{document}$ C $\end{document} 的朋友圈比\begin{document}$ D $\end{document} 的朋友圈更大, 则\begin{document}$ C $\end{document} 对\begin{document}$ D $\end{document} 的影响力要比\begin{document}$ D $\end{document} 对\begin{document}$ C $\end{document} 的影响力大, 即\begin{document}$ {\omega _{ DC}} > {\omega _{ CD}} $\end{document} . 所以, 重新设计影响度函数
27 \begin{document}$ \begin{align} {\tilde \omega _{ij}} = \frac{{|{{\tilde N}_i} \bigcap {{\tilde N}_j}{{|}}}}{{|{{\tilde N}_i} \bigcup {{\tilde N}_j}{{|}}}}\frac{{{d_j}}}{{{d_i}}}, \end{align} $\end{document}
其中\begin{document}$ {d_{i, j}} $\end{document} 代表节点\begin{document}$ i, j $\end{document} 的度. 可得到影响度矩阵
28 \begin{document}$ \begin{align} \tilde W = \begin{bmatrix} 1&{{{\tilde \omega }_{12}}}& \cdots &{{{\tilde \omega }_{1n}}}\\ {{{\tilde \omega }_{21}}}&1& \cdots &{{{\tilde \omega }_{2n}}}\\ \vdots & \vdots & \ddots & \vdots \\ {{{\tilde \omega }_{n1}}}&{{{\tilde \omega }_{n2}}}& \cdots &1 \end{bmatrix}. \end{align} $\end{document}
由影响度矩阵\begin{document}$ \tilde W $\end{document} , 重新计算节点的介数中心性
29 \begin{document}$ \begin{align} \tilde V = \tilde WV, \end{align} $\end{document}
其中\begin{document}$ V = {[ {{v_1}\ldots{v_N}}]^{\rm T}} $\end{document} .
基于影响度介数中心性\begin{document}$ \tilde V $\end{document} 分布选择控制节点步骤如下.
step 1: 遍历整个网络, 获得子网\begin{document}$ s $\end{document} 的邻接矩阵\begin{document}$ {{{A}}_{{s}}} $\end{document} 和拓展邻接矩阵\begin{document}$ {{\tilde{A}}_{{s}}} $\end{document} ;
step 2: 根据介数中心性算法获得子网\begin{document}$ s $\end{document} 的介数中心性分布矩阵\begin{document}$ V $\end{document} ;
step 3: 计算子网\begin{document}$ s $\end{document} 影响度矩阵\begin{document}$ {\tilde W_s} $\end{document} , 按式(29)获得影响度介数中心性分布矩阵\begin{document}$ \tilde V $\end{document} ;
step 4: 根据矩阵\begin{document}$ \tilde V $\end{document} , 搜寻出子网\begin{document}$ s $\end{document} 中介数中心度最大的节点, 并标识为牵制控制节点.
4
实验仿真
实验1 本实验基于Reynolds模型, 运用影响度介数中心性寻找牵制控制算法中关键牵制节点.设多智能体系统个体数量\begin{document}$ n = 100 $\end{document} , 所有个体的初始状态随机产生, 如图 5 所示. 设智能体感知半径\begin{document}$ r = 6 $\end{document} , 目标\begin{document}$ \alpha $\end{document} -lattices结构半径\begin{document}$ d = 5 $\end{document} .
5
多智能体系统初始状态分布
在文献[17 ]中, 通过控制变量法, 实验得出\begin{document}$ {c_1} $\end{document} 对系统收敛速度几乎不产生影响, 而\begin{document}$ {c_2} $\end{document} 越大, 集群的收敛速度也就越快, 但收敛速度受到集群数量影响而存在上界. 因而设\begin{document}$ {c_1} = 0.5, {c_2} = 2 $\end{document} .
图 6 为多智能体系统在不同时间下的状态分布, 由图 6(a) 和图 6(b) 对比可看出: 智能体会跟随着牵制控制节点逐渐向虚拟领导者靠拢, 系统最终收敛为全连通网络.
6
多智能体系统状态演化
实验2 为对比分析不同方法选择牵制控制节点对系统收敛快慢和稳定性的影响, 分别采用影响度介数中心性(BCID)、介数中心性(BC)、度中心性(DC)、特征向量中心性(EC)和\begin{document}$ k $\end{document} -shell五种度量方法. 设多智能体系统个体数量\begin{document}$ n = 100 $\end{document} , 本实验随机获得15组多智能体系统不同初始状态, 控制输入参数与实验1相同.
定义速度差异函数
30 \begin{document}$ \begin{align} {\vartheta _i} = \arctan\Big(\frac{{q_\gamma ^y}}{{q_\gamma ^x}}\Big) - \arctan \Big(\frac{{q_i^y}}{{q_i^x}}\Big). \end{align} $\end{document}
记个体\begin{document}$ i $\end{document} 与虚拟领导者同步条件
31 \begin{document}$ \begin{align} {\vartheta_i} = 1, \; |{\vartheta _i}| < 0.01. \end{align} $\end{document}
系统最终保持同步条件\begin{document}$ \sum\limits_{i = 1}^n {{\varpi _i}} = n $\end{document} , 实验结果如图 7 所示. 可以看出, 本文提出的BCID算法相较于传统介数中心性算法大大缩减了系统收敛时间, 且比其他几种中心性算法有着更快的收敛时间和更强鲁棒性, 终止时间较为稳定.
7
收敛时间折线
以样本8为例, 度中心性算法虽比IDBC算法收敛时间更短, 但在\begin{document}$ \alpha $\end{document} -lattices系统中单个智能体最多有6个邻居, 这导致存在大量度相同的节点, 造成基于度中心性算法选择的控制节点随机性大, 易牵连多数节点与既定运动方向发生偏离, 使得系统不稳定. 而基于BCID算法选择的控制节点一方面凭借影响度矩阵, 通过与周围重要性较高的节点通信来间接影响更多的节点, 提高系统稳定性; 另一方面, 控制节点的介数中心性越高通知到网络全部节点的所需时间也就越短. 定义多智能体系统收敛程度
32 \begin{document}$ \begin{align} P = \frac{{ \sum\limits_{i = 1}^n {\varpi_i} }}{n}. \end{align} $\end{document}
收敛度变化如图 8 所示, BCID算法相较于度中心性算法可使系统长时间达到完全收敛, 而度中心性算法极易发散.
8
收敛度变化
实验3 在实验2的基础上, 设计实验验证BCID对系统稳定性的影响. 当系统达到稳定时, 如果此时更改目标运动状态(即虚拟领导者的运动信息), 会导致系统的速度一致性崩溃, 但集群无分裂的可能(已证明网络中存在的边不会断开), 恢复速度一致性所需时间是系统稳定性的一种体现. 设集群内智能体数量\begin{document}$ n = 30 $\end{document} , 在系统达到一致后更改虚拟领导者的运动信息. 实验结果如图 9 所示, 其中样本\begin{document}$ 1\sim $\end{document} 样本\begin{document}$ 5 $\end{document} 是在相同初始状态下跟随不同的虚拟领导者, 样本\begin{document}$ 6\sim $\end{document} 样本\begin{document}$ 10 $\end{document} 则是在不同的初始状态下跟随同一虚拟领导者.
9
回归一致性所需时间折线
由图 9 可看出, BCID算法在不同情况下都可快速响应系统, 引导整个集群向目标运动状态转变, 可快速恢复系统的速度一致性, 保证系统的稳定性. 虽然某些情况下恢复时间可能超过其他算法(如样本8), 但BCID算法更为稳定, 在多数情况下都优于其他几种控制算法.
5
结论
本文在牵制控制节点的选择上考虑到邻居节点的重要性影响, 设计一种影响度矩阵. 通过仿真实验验证该算法可有效增强系统的鲁棒性和提高收敛速度. 但由于介数中心性本身的局限性, 可直接影响到的节点数较少, 因而系统初始收敛程度依线性增长, 且实验是假设虚拟领导者匀速运动. 下一步将研究虚拟领导者以既定路线飞行时的牵制控制节点选择问题和为实现集群可跟随虚拟领导者运动重新构建控制输入问题.}
责任编委:程龙.
References
[
]1
Beard
R W
McLain
T W
Nelson
D B
Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs
Proceedings of the IEEE
2006
94
7
1306
1324
10.1109/JPROC.2006.876930 Beard R W, McLain T W, Nelson D B, et al. Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs[J]. Proceedings of the IEEE, 2006, 94(7): 1306-1324.
[
]2
Vicsek
T
Czirk
A
Ben-Jacob
E
Novel type of phase transition in a system of self-driven particles
Physical Review Letters
1995
75
6
1226
10.1103/PhysRevLett.75.1226 Vicsek T, Czirk A, Ben-Jacob E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical Review Letters, 1995, 75(6): 1226.
[
]3
Reynolds
C W
Flocks, herds and schools: A distributed behavioral model
ACM SIGGRAPH Computer Graphics
1987
21
4
25
34
10.1145/37402.37406 Reynolds C W. Flocks, herds and schools: A distributed behavioral model[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 25–34.
[
]4
Su H S, Wang X F, Lin Z L. Flocking of multi-agents with a virtual leader, part Ⅱ: With a virtual leader of varying velocity[C]. Proceedings of the IEEE Conference on Decision and Control, 2018, 54(2): 1429-1434.
[
]5
Wang
X F
Chen
G P
Pinning control of scale-free dynamical networks
Physica A: Statistical Mechanics and its Applications
2002
310
3/4
521
531
Wang X F, Chen G P. Pinning control of scale-free dynamical networks[J]. Physica A: Statistical Mechanics and its Applications, 2002, 310(3/4): 521-531.
[
]6
Huang
M
Manton
J H
Coordination and consensus of networked agents with noisy measurements: Stochastic algorithms and asymptotic behavior
SIAM Journal on Control and Optimization
2009
48
1
134
161
10.1137/06067359X Huang M, Manton J H. Coordination and consensus of networked agents with noisy measurements: Stochastic algorithms and asymptotic behavior[J]. SIAM Journal on Control and Optimization, 2009, 48(1): 134-161.
[
]7
Li
K Z
Sun
W
Small
M
Practical synchronization on complex dynamical networks via optimal pinning control
Physical Review E: Statistical, Nonlinear, and Soft Matter Physics
2015
92
1
1
5
Li K Z, Sun W, Small M, et al. Practical synchronization on complex dynamical networks via optimal pinning control[J]. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2015, 92(1): 1-5.
[
]8
Olfati-Saber
R
Flocking for multi-agent dynamic systems: Algorithms and theory
IEEE Transactions on Automatic Control
2006
51
3
401
420
10.1109/TAC.2005.864190 Olfati-Saber R. Flocking for multi-agent dynamic systems: Algorithms and theory[J]. IEEE Transactions on Automatic Control, 2006, 51(3): 401-420.
[
]9
Su
H S
Wang
X F
Lin
Z L
Flocking of multi-agents with a virtual leader
IEEE Transactions on Automatic Control
2009
54
2
293
307
10.1109/TAC.2008.2010897 Su H S, Wang X F, Lin Z L. Flocking of multi-agents with a virtual leader[J]. IEEE Transactions on Automatic Control, 2009, 54(2): 293-307.
[
]10
Nie
S
Wang
X W
Wang
B H
Effect of degree correlation on exact controllability of multiplex networks
Physica A: Statistical Mechanics and its Applications
2015
436
98
102
10.1016/j.physa.2015.05.038 Nie S, Wang X W, Wang B H. Effect of degree correlation on exact controllability of multiplex networks[J]. Physica A: Statistical Mechanics and its Applications, 2015, 436: 98-102.
[
]11
Zhao
J M
Lu
Q
Peng
Y
Research on minimum control energy of complex networks by the non-independent control strategy of single control input
Physica A: Statistical Mechanics and its Applications
2019
532
121810
10.1016/j.physa.2019.121810 Zhao J M, Lu Q, Peng Y, et al. Research on minimum control energy of complex networks by the non-independent control strategy of single control input[J]. Physica A: Statistical Mechanics and its Applications, 2019, 532: 121810.
[
]12
DeLellis
P
Garofalo
F
Lo
Iudice F
The partial pinning control strategy for large complex networks
Automatica
2018
89
111
116
10.1016/j.automatica.2017.11.025 DeLellis P, Garofalo F, Lo Iudice F. The partial pinning control strategy for large complex networks[J]. Automatica, 2018, 89: 111-116.
[
]13
Moore K L, Lucarelli D. Forced and constrained consensus among cooperating agents[C]. Proceedings of IEEE Conference on Networking, Sensing and Control. Tucson: IEEE, 2005: 449-454.
[
]14
Tanner
H G
On the controllability of nearest neighbor interconnections
Proceedings of the IEEE Conference on Decision and Control
2004
3
5
2467
2472
Tanner H G. On the controllability of nearest neighbor interconnections[J]. Proceedings of the IEEE Conference on Decision and Control, 2004, 3(5): 2467-2472.
[
]15
Xiang
J
Chen
G R
On the $ V $-stability of complex dynamical networks
Automatica
2007
43
6
1049
1057
10.1016/j.automatica.2006.11.014 Xiang J, Chen G R. On the $ V $-stability of complex dynamical networks[J]. Automatica, 2007, 43(6): 1049-1057.
[
]16
Gao
J Y
Xu
X
Ding
N
Flocking motion of multi-agent system by dynamic pinning control
IET Control Theory & Applications
2017
11
5
714
722
Gao J Y, Xu X, Ding N, et al. Flocking motion of multi-agent system by dynamic pinning control[J]. IET Control Theory & Applications, 2017, 11(5): 714-722.
[
]17
何
明
许
元云
刘
景涛
基于$k$-shell分解的多智能体牵制控制算法
控制与决策
2020
35
10
2556
2560
何明, 许元云, 刘景涛, 等. 基于$k$-shell分解的多智能体牵制控制算法[J]. 控制与决策, 2020, 35(10): 2556-2560.
He
M
Xu
Y Y
Liu
J T
Multi-agent pinning control algorithm based on $k$-shell decomposition
Contral and Decision
2020
35
10
2556
2560
He M, Xu Y Y, Liu J T, et al. Multi-agent pinning control algorithm based on $k$-shell decomposition[J]. Contral and Decision, 2020, 35(10): 2556-2560.
[
]18
Tsalouchidou
I
Baeza-Yates
R
Bonchi
F
Temporal betweenness centrality in dynamic graphs
International Journal of Data Science and Analytics
2020
9
3
257
272
10.1007/s41060-019-00189-x Tsalouchidou I, Baeza-Yates R, Bonchi F, et al. Temporal betweenness centrality in dynamic graphs[J]. International Journal of Data Science and Analytics, 2020: 9(3): 257-272.
[
]19
Khalil
H K
Nonlinear systems
Upper Saddle River
Prentice Hall
2002
311
319
Khalil H K. Nonlinear systems[M]. Upper Saddle River: Prentice Hall, 2002: 311-319.
[
]20
顾
亦然
王
兵
孟
繁荣
一种基于$k$-shell的复杂网络重要节点发现算法
计算机技术与发展
2015
25
9
70
74
顾亦然, 王兵, 孟繁荣, 等. 一种基于$k$-shell的复杂网络重要节点发现算法[J]. 计算机技术与发展, 2015, 25(9): 70-74.
Gu
Y R
Wang
B
Meng
F R
An algorithm of important nodes finding for complex network based on $k$-shecl
Computer Technology and Development
2015
25
9
70
74
Gu Y R, Wang B, Meng F R, et al. An algorithm of important nodes finding for complex network based on $k$-shecl[J]. Computer Technology and Development, 2015, 25(9): 70-74.