Abstract : We propose a novel method for multi-agent systems via super-nodes cooperation, in order to improve the convergence rate of multi-agent systems to achieve consensus. The new algorithm establishes a graph signal model for the multi-agent system, and selects super-nodes to cooperate in the graph, improve the speed of consensus. First, we select some super-nodes and divide local sets by single-hop sampling algorithm, and cooperate the nodes in the local set. Then the coarsened graph is obtained by edge connection between super-nodes, and the coefficients of the graph filter are designed by the eigenvalues of the Laplacian matrix. Finally, the signal of super-nodes are averaged by iteration of the graph filter, and transmitted to their neighbor nodes, all nodes achieved average consensus. The simulation results show that the algorithm achieves the average consensus at the end, which can significantly improve the convergence speed and reduce the calculation amount compared with the existing methods. Keywords : multi-agent system average consensus graph signal super-node coarsened graph

多智能体系统(multi-agent systems)是指一组具备一定通信、传感、计算能力的智能体通过某种通信方式构成的复杂网络化系统，具有自主性和分布式的特点 ^{[ 1 ]} .单个智能体的设计相对简单，只能与其相邻的智能体进行信息交互而不能获得全局的信息，整个系统可以利用个体之间的相互合作来完成复杂任务和智能行为 ^{[ 2 ]} .多智能体技术已被广泛应用在编队控制 ^{[ 3 ]} 、交通控制 ^{[ 4 ]} 、传感器网络 ^{[ 5 ]} 等诸多领域.近年来，多智能体的协同控制成为控制领域新的研究热点 ^{[ 6 ]} ，其中一致性问题是协同控制领域中的经典问题.

一致性(consensus)是指在一致性协议或算法的控制下，智能体之间通过局部的通信，仅依赖于邻居的信息更新自己的状态，最终使得所有智能体的状态达到一致.一致性协议或算法指每个智能体在与它相邻智能体之间进行信息交换的过程中所遵循的交互规则 ^{[ 7 ]} .在众多一致性算法中，以节点初始值的均值为收敛目标的平均一致性算法是一类重要的算法，其应用最为广泛.如自组织网络(Ad Hoc networks)中，节点间需要协作完成一定的任务，而协作依赖于相同的参考时间 ^{[ 8 ]} .由于每个节点拥有的本地时钟是各不相同的，为确保合理利用通信资源，需要设计相应的一致性算法对各节点的时钟进行校正，使网络实现时钟同步.

在数学、控制科学、计算学科等领域已经有很多关于一致性问题的研究.传统的一致性研究大都根据矩阵不等式方法和李亚普诺夫稳定性理论来进行一致性协议的设计与性能分析.这些方法没有关注系统一致演化的本质物理解释，并且给出的一致性协议在收敛速度上还有待提升.随着图信号处理理论的发展，很多学者对多智能体系统的一致性问题和图信号处理之间的关系进行研究.文[ 9 ]与文[ 10 ]提出把多智能体系统建模成无向图，从图信号处理的角度看待多智能体一致性的问题，可以将智能体的初始状态视为初始的图信号值，多智能体系统的每一次协同的过程对应于图信号经过一次低通滤波.每个智能体的局部控制器可以视为图滤波器 ^{[ 11 - 12 ]} ，通过对图滤波器的设计，可以给出收敛速度较快的一致性控制协议.文[ 9 ]算法中，图滤波器的系数是选取图的拉普拉斯矩阵的最大特征值的倒数，这种算法实现了渐近时间平均一致性；文[ 10 ]算法中，图滤波器的系数是选取图的拉普拉斯矩阵的所有不同非0特征值的倒数，这种算法实现了有限时间平均一致性.

在一致性问题当中，系统的收敛速度是评价一致性协议的核心指标，更快的收敛速度意味着更高的工程应用价值.本文基于多智能体系统的平均一致性与图信号滤波的关系，提出超节点协同算法，有效提高一致性的收敛速度.首先利用单跳采样算法对图进行超节点的选取和局部集的划分，具有扩展性，能够用于大规模系统.然后在算法的每一步迭代中，只需超节点进行协同，超节点数量相对较少，降低了计算复杂度；普通节点只与超节点进行通信，降低了通信量.实验仿真表明，与文[ 9 - 10 ]相比，本文的方法显著加快收敛速度和降低计算量.

1 图信号处理相关知识

图信号处理(graph signal processing，GSP)是研究非规则域信号的有利工具 ^{[ 13 ]} ，在生物医学 ^{[ 14 ]} 、机器学习 ^{[ 15 ]} 、传感器网络 ^{[ 16 ]} 和图像处理 ^{[ 17 ]} 等方面有重要应用.本文针对多智能体系统建立图信号模型，每个智能体看作是图中的一个节点，节点处的信号值表示智能体的数据，边表示智能体之间的相互通信.

在本文中，考虑一个由 N 个智能体组成的系统，其图信号模型为 G =( V ， E ， W )，其中 V ={1，2，…， N }是节点的集合，且任意两个节点之间都存在路径可以连通； E ={ e _ij }是边的集合， e _ij =( i ， j )表示节点 i 和节点 j 之间有边相连接；邻接矩阵 W =( w _ij )∈R ^{N × N} ，在本文算法中当节点 i 与 j 之间存在边相连时， w _ij = w _ji =1.不考虑自环，对于所有节点 i 都有 w _ii =0.图模型的度矩阵 D =diag( d _i )，其中 ， i =1，2，…， N .图的拉普拉斯矩阵为 L = D - W ，可以分解为 L = UΛU ^T ，其中特征向量矩阵 U =[ u ₁ ， u ₂ ，…， u _N ]，特征值矩阵 Λ =diag{ λ ₁ ， λ ₂ ，…， λ _N }.节点 i 处的信号值为 x _i ，所有节点的信号值集合为一个列向量 x =[ x ₁ ， x ₂ ，…， x _N ] ^T .在图信号处理中，图傅里叶变换定义为 ，相应的图傅里叶逆变换为 ^{[ 18 ]} .

为了下一步研究，本文给出引理1.

引理1 ^{[ 19 ]} 若图 G =( V ， E ， W )是无向图，则图 G 的拉普拉斯矩阵 L 是一个对称矩阵，有 N 个实特征值，对它们进行排列：

对每个超节点而言，局部集内其它节点都是其一阶邻居节点，可以直接交互得到这些节点的信息.本文对同一局部集内的超节点与邻居节点进行一次协同，来更新超节点的信号值.协同方法为：

初始图 G ₁ 的节点数记为 N ，初始时刻第 i 个节点的信号值为 x _i (0)， i =1，2，…， N ；采样后构成粗化图 G ₂ 的超节点个数记为 M (即划分的局部集有 M 个)，第 j 个局部集内所有节点的信号值之和为 f _j (0)， j =1，2，…， M .第 j 个超节点的信号取值 F _j (0)= f _j (0)× d . d 为权值，对其进行求解：

初始图 G ₁ 的信号平均值为 ，粗化图 G ₂ 的信号平均值为 ，在采样前后图的信号平均值相同，有 y ₁ = y ₂ ，即：

完成局部集内节点协同后，超节点更新信号值，再进行下一步.

3.2 超节点之间协同

通过上一步得到粗化图 G ₂ 后，可以取粗化图的拉普拉斯矩阵最大特征值的倒数或所有不同非0特征值的倒数来设计图滤波器的系数，超节点通过图滤波器的迭代达到平均值.相较于文[ 9 - 10 ]用初始图的拉普拉斯矩阵特征值设计图滤波器的系数，本文方法的计算复杂度显著降低，分析如下：对于初始图 G ₁ ，节点个数记为 N ，其拉普拉斯矩阵 L ₁ 的规模大小为 N × N ，不同的非零特征值个数记为 N ₁ ( N ₁ ≤ N -1)；对于粗化图 G ₂ ，节点个数记为 M ，其拉普拉斯矩阵 L ₂ 的规模大小为 M × M ，不同的非零特征值个数记为 M ₁ ( M ₁ ≤ M -1).进行单跳采样后图的节点数远小于采样前，即 M < N ， M ₁ < N ₁ .因此，对于拉普拉斯矩阵特征值的求解和每次迭代过程中使用到拉普拉斯矩阵，使用粗化图的计算量是远小于初始图的.

最后，超节点的信号值达到平均值后传输给其局部集内的邻居节点，使所有节点达到平均一致.

4 实验仿真结果及分析

这一节对本文算法进行仿真实验，并与已有算法进行对比.其中，仿真实验1是通过具体示例来验证超节点协同算法的过程，仿真实验2是展示在各种规模大小的多智能体系统下，本文算法与文[ 9 - 10 ]算法收敛速度及收敛时间的比较.

4.1 仿真实验1

建立一个节点编号为1-9，信号初始值 x (0)=[-9, 8, -3, 6, -5, 7, -2, 4, -6] ^T 的图模型如 图 1 所示. 图 1 中节点3的度最大，作为第一个超节点，编号为 A ，将它的邻居节点1，2，4，5及它们之间的边整体划为一个局部集；然后去掉节点4与节点6、节点5与节点6、节点5与节点7之间的边，剩下图的部分中确定节点7为第2个超节点(当有节点的度大小相同时，依据编号顺序选取)，编号为 B ，与节点6、8及它们之间的边构成第2个局部集；最后节点9作为第3个超节点单独构成第3个局部集，第3个超节点的编号为 C .对超节点之间进行边的连接，完成后的粗化图如 图 2 所示.初始图节点数为9，粗化图节点数为3，则 .对每个局部集内的节点进行协同，计算超节点的信号取值：

4.2 仿真实验2

以下仿真实验均使用处理器为Intel Core i7-7700，运行内存(RAM)为8 GB的计算机，在Matlab 2016a软件平台上进行.图使用GSPBOX ^{[ 23 ]} 生成，图上节点的初始信号值在[-1, 1]间随机取值.在图的节点数为100到5 000的范围内选取不同节点数做100次实验，记录迭代次数、迭代时间的平均值.

1) 给出文[ 9 ]和本文算法的对比.文[ 9 ]迭代公式为 x ( t +1)=( I - ε _t L ) x ( t )，其中 ， λ _max 为初始图拉普拉斯矩阵的最大特征值.本文方法：基于超节点协同算法，迭代公式为 x ( t +1)=( I - ε _t L ) x ( t )，其中 ， λ′ _max 为粗化图拉普拉斯矩阵的最大特征值.迭代终止条件均为每个节点的信号值与上一次迭代后的信号值之差小于10 ^-4 .对迭代时间进行对比，结果如 表 1 所示.对迭代次数进行对比，结果如 图 5 所示.与文[ 9 ]相比，本文算法的迭代次数平均降低了72.71%，在节点数大于1 000的情况下本文算法比文[ 9 ]算法的迭代时间平均减少了77.43%.

表 1 对比文[ 9 ]与本文算法的运行时间 Tab.1 Run time of literature [ 9 ] and my method

2) 给出文[ 10 ]和本文算法进行比较.文[ 10 ]算法迭代公式为 x ( t +1)=( I - ε _t L ) x ( t )， ， p 为初始图的拉普拉斯矩阵不同非0特征值的个数(0= λ ₁ < λ ₂ … < λ _{p +1} ).本文方法：基于超节点协同算法，迭代公式为 x ( t +1)=( I - ε _t L ) x ( t )，其中 ， m 为粗化图的拉普拉斯矩阵不同非0特征值的个数(0= λ ₁ < λ ₂ … < λ _{m +1} ).对迭代时间进行对比，结果如 表 2 所示.对迭代次数进行对比，结果如 图 6 所示.与文[ 10 ]相比，本文算法的迭代次数平均降低了78.75%，在节点数大于1 000的情况下，本文算法比文[ 10 ]算法的迭代时间平均减少了74.07%.

表 2 对比文[ 10 ]与本文算法的运行时间 Tab.2 Run time of literature [ 10 ] and my method

综上所述，可以看出本文算法的迭代次数降低了4/5左右，原因是随机生成初始图的度大多为5，进行单跳采样后粗化图的节点个数大约变为初始图的1/5.在节点数大于1 000的情况下，本文方法的迭代时间也更少，原因是对图进行单跳采样会占用一定时间，但随着图的规模增大，采样所用时间是远小于迭代时间的.

本文研究了如何提高多智能体系统离散时间一致性的收敛速度的问题.基于图信号处理理论，对多智能体系统建模成初始图，在图中选取超节点得到粗化图，利用粗化图的拉普拉斯矩阵的特征值来设计控制增益.实验仿真验证了所提方法的有效性.后续工作是将本文方法拓展至二阶和高阶多智能体系统.

王祥科, 李迅, 郑志强. 多智能体系统编队控制相关问题研究综述[J]. 控制与决策, 2013, 28(11): 1601–1603.
Wang X K, Li X, Zheng Z Q. Survey of developments on multi-agent formation control related problems[J]. Control and Decision, 2013, 28(11): 1601–1603. 张静莲, 刘三阳, 张朝辉. 具有小世界现象的无线传感器网络构造方法[J]. 信号处理, 2017, 33(3): 417–421.
Zhang J L, Liu S Y, Zhang Z H. Approach to construct wireless sensor network with small world phenomenon[J]. Joumal of signal Processing, 2017, 33(3): 417–421. 闵海波, 刘源, 王仕成, 等. 多个体协调控制问题综述[J]. 自动化学报, 2012, 38(10): 1557–1570.
Min H B, Liu Y, Wang S C, et al. An overview on coordination control problem of multi-agent system[J]. Acta Auto Maticasinica, 2012, 38(10): 1557–1570. Olfati-Saber R, Fax J A, Murray R M. Consensus and cooperation in networked multi-agent systems[J]. Proceedings of the IEEE, 2007, 95(1): 215–233. DOI:10.1109/JPROC.2006.887293 Sandryhaila A, Moura J. Big data analysis with signal processing on graphs:Representation and processing of massive data sets with irregular structure[J]. IEEE Signal Processing Magazine, 2014, 31(5): 80–90. DOI:10.1109/MSP.2014.2329213 Kim W H, Adluru N, Chung M K, et al. Multi-resolution brain network filtering and analysis via wavelets on non-euclidean space[C]//Medical Image Computing and Computer-Assisted Intervention. Berlin, Germany: Springer, 2013: 643-651. Gadde A, Anis A, Ortega A. Active semi-supervised learning using sampling theory for graph signals[C]//20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014: 492-501. Wang W, Ramchandran K. Random multiresolution representations for arbitrary sensor network graphs[C]//IEEE International Conference on Acoustics Speech and Signal Processing. Piscataway, NJ, USA: IEEE, 2006: 161-164. Narang S K, Chao Y H, Ortega A. Graph-wavelet filterbanks for edge-aware image processing[C]//Statistical Signal Processing Workshop. Piscataway, NJ, USA: IEEE, 2012: 141-144. Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs:Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30(3): 83–98. DOI:10.1109/MSP.2012.2235192 Olfati-Saber R, Murray R. Consensus problems in networks of agents with switching topology and time-delays[J]. IEEE Transactions on Automatic Control, 2004, 49(9): 1520–1533. DOI:10.1109/TAC.2004.834113 陈南凯.多智能体系统的协同一致性及应用研究[D].长沙: 湖南大学, 2016.
Chen N K. The research on consistency and application of multi-agent systems cooperative[D]. Changsha: Hunan University, 2016. 刘鹏飞.图上信号的降维与重建方法[D].北京: 清华大学, 2015.
Liu P F. Dimensionality reduction and reconstruction for graph signals[D]. Beijing: Tsinghua University, 2015. 位鲁松, 蒋英春. 一种改进的加权图信号传播重构算法[J]. 桂林电子科技大学学报, 2017, 37(3): 192–196.
Wei L S, Jiang Y C. An improved propagation reconstruction algorithm for weighted graph signals[J]. Journal of Guilin University of Electronic Technology, 2017, 37(3): 192–196. DOI:10.3969/j.issn.1673-808X.2017.03.005 Perraudin N, Paratte J, Shuman D, et al. GSPBOX:Atoolbox for signal processing on graphs[J]. Arxiv, 2016, 61(7): 1644–1656. DOI:10.1109/TSP.2013.2238935

采用超节点协同的多智能体系统一致性算法

Novel Average Consensus Algorithm for Multi-agent Systems via Super-nodes Cooperation

信息与控制, 2019, 48(6): 694-699, 706.

Information and Control, 2019, 48(6): 694-699, 706.

http://dx.doi.org/10.13976/j.cnki.xk.2019.8653