含生成森林有向图的零特征值及在编队控制中的应用

Zero Eigenvalue of Directed GraphsWith Spanning ForestsWith Application to Formation Control

中文关键词  拉普拉斯矩阵  多智能体网络  有向图  生成森林  编队控制

英文关键词  Laplacian matrix, multi-agent networks, directed graphs, spanning forest, formation control

中文摘要

      本文研究了含有m-生成森林有向图拉普拉斯矩阵的零特征值重数，其中m≥1是一个整数。对于这个问 题，这个图一般不含有生成树。即使初始时具有生成树，受到隐秘的攻击或经过障碍物造成的智能体之间的通信 阻挡（如在分布式控制、分布式（在线）优化、多智能体算子等问题中）等因素后，这个图也可能不再含有生成树 。另外，作为一个研究方向，它本身亦是个有趣的科学问题。为了解决这个问题，本文证明了拉普拉斯矩阵的 零特征值重数等于这个图中的生成森林个数，这个结论可以看作是在带有生成树的有向图情形（即m=1时）的一 个推广。再者，结合分布式优化方法，所得结论被应用于单积分器多智能体系统下的编队控制，表明了达到的编 队队形处在通信图拉普拉斯矩阵的核空间中。最后给出了一个例子用以展示在编队控制中的应用。

英文摘要

      This paper investigates the multiplicity of zero eigenvalue of the Laplacian matrix for a directed graph, which has a spanning m-forest, where m≥1 is an integer. For this problem, the graph usually does not contain a spanning tree, and this scenario may occur due to insidious attacks or communication blocking by obstacles between two agents in distributed control, (online) optimization, multi-agent operators, and so on, even though it indeed has a spanning tree at the beginning. In addition, this problem is of interest as a research direction in its own right. To deal with this problem, it is shown that the multiplicity of the Laplacian’s zero eigenvalue amounts to the number of spanning forests in the studied graph, which can be seen as an extension of the directed graph case with a spanning tree, in which case it has m=1. Moreover, the obtained result is applied to formation control for single-integrator multi-agent systems along with distributed optimization methods, indicating that the achieved formation shape lies in the kernel space of the Laplacian matrix associated with the communication graph. Finally, an example is provided to demonstrate the applicability to formation control.