第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0L:10.11992tis.202006010 双向通信无人机集群领航顶点选取方法 戴丽 (国防科技大学文理学院，湖南长沙410073) 摘要：领航顶点选取是关系到领航-跟随模式无人机集群等多智能体系统可控性的重要问题。以具有几十架 个体的无人机集群为研究对象，针对领航顶点选取问题，基于Laplac心矩阵的特征向量，提出关键集概念。从理 论上证明2关键集、3关键集以及独立关键集的图特征。在此基础上，给出求无向网络最小关键集的CSA算 法，通过数值仿真实验获得了不同规模、不同通信半径条件下无人机集群最小领航集的数值特征。 关键词：领航顶点选取：领航跟随模式：无向图：Laplace矩阵：可控性：关键集：最小领航集；算法 中图分类号：TP273 文献标志码：A文章编号：1673-4785(2021)03-0484-09 中文引用格式：戴丽.双向通信无人机集群领航顶点选取方法.智能系统学报，2021,16(3)：484-492 英文引用格式：DAI Li.Leaders'selection for UAV swarm with two-way communicationJ.CAAI transactions on intelligent sys- tems,2021,16(3:484-492. Leaders'selection for UAV swarm with two-way communication DAILi (College of Liberal Arts and Sciences,National University of Defense Technology,Changsha 410073,China) Abstract:Leaders'selection plays a vital role in the controllability of multiagent systems,such as the leader-follower framework of UAVs.Using the UAV swarm with dozens of individuals as the research object and aiming at the prob- lem of leaders'selection,this paper proposes a critical set based on the eigenvector of a Laplace matrix.Theoretically, the graphical characteristics of two,three,and isolated critical sets are proved.Based on this,an algorithm named CSA for finding the minimum critical set of undirected communication networks is presented.Finally,numerical simulation is used to obtain the numerical features of the minimum leaders of UAVs of various sizes and communication radii Keywords:leader's selection:leader-follower framework:undirected network:Laplacian matrix:controllab- ility;critical vertex set;minimum leader set;algorithm 多智能体系统控制技术是人工智能时代的研 与这2个问题密切相关。 究热点之一山，其成果可用于多个领域，如智能交 对于通信网络拓扑结构图为有向图的领航跟 通、机器人编队，甚至是军事用途，如无人机蜂 随网络系统，文献[3]通过引进匹配概念，使有向 (狼)群作战等。无人机集群作为一种特殊的多智 网络的可控性问题已得到较好解决。但是，对于 能体系统，个体无需全局通信，仅通过对其周围 无向领航跟随网络系统控制而言，正如Kumar 一定范围内个体间的通信、合作和协调等就可以 等)于2019年所指出的那样：如何选取领航顶 表达集群整体结构和功能。它在自组织能力、推 点、如何选取最少个数的领航顶点都是尚待解决 理能力，以及对未知环境的适应性等方面有很多 的难题。 潜在应用。 目前，无向网络控制技术已经引起人们的广 无论是地面起飞式无人机集群，还是空投式 泛关注。文献[5]是一篇较早关注无向网络可控 无人机集群，其控制技术的难点都在于队形控 性的文章，该文通过Kalman秩条件给出了无向网 制，核心在于解决可行性和有效性两个问题四：可 络可控的充要条件。研究无向网络领航集常用的 行性是研究无人机集群能不能全局可控，使之形 成所有预定队形；有效性则回答了最少需要输人 图结构有：强制零点集(zero forcing set,,ZFS)H,6- 多少信号，才能达到全局可控。最小领航集选取 约束匹配(constraint matching,.CM)-"和非平凡等 价划分(nontrivial equitable partition,NEPy2-l等。 收稿日期：2020-06-08. 基金项目：国家自然科学基金项目(11872371)， 已有的研究成果表明无向网络可控当且仅当领航 通信作者：戴丽.E-mail:daili@nudt.edu.cn. 集是推广的ZFS,且Shima等8,1o发现了网络中DOI: 10.11992/tis.202006010 双向通信无人机集群领航顶点选取方法 戴丽 （国防科技大学 文理学院，湖南 长沙 410073） 摘 要：领航顶点选取是关系到领航−跟随模式无人机集群等多智能体系统可控性的重要问题。以具有几十架 个体的无人机集群为研究对象，针对领航顶点选取问题，基于 Laplace 矩阵的特征向量，提出关键集概念。从理 论上证明 2 关键集、3 关键集以及独立关键集的图特征。在此基础上，给出求无向网络最小关键集的 CSA 算 法，通过数值仿真实验获得了不同规模、不同通信半径条件下无人机集群最小领航集的数值特征。 关键词：领航顶点选取；领航跟随模式；无向图；Laplace 矩阵；可控性；关键集；最小领航集；算法 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2021)03−0484−09 中文引用格式：戴丽. 双向通信无人机集群领航顶点选取方法 [J]. 智能系统学报, 2021, 16(3): 484–492. 英文引用格式：DAI Li. Leaders’ selection for UAV swarm with two-way communication[J]. CAAI transactions on intelligent sys￾tems, 2021, 16(3): 484–492. Leaders’ selection for UAV swarm with two-way communication DAI Li (College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China) Abstract: Leaders’ selection plays a vital role in the controllability of multiagent systems, such as the leader-follower framework of UAVs. Using the UAV swarm with dozens of individuals as the research object and aiming at the prob￾lem of leaders’ selection, this paper proposes a critical set based on the eigenvector of a Laplace matrix. Theoretically, the graphical characteristics of two, three, and isolated critical sets are proved. Based on this, an algorithm named CSA for finding the minimum critical set of undirected communication networks is presented. Finally, numerical simulation is used to obtain the numerical features of the minimum leaders of UAVs of various sizes and communication radii. Keywords: leader’s selection; leader-follower framework; undirected network; Laplacian matrix; controllab￾ility; critical vertex set; minimum leader set; algorithm 多智能体系统控制技术是人工智能时代的研 究热点之一[1] ，其成果可用于多个领域，如智能交 通、机器人编队，甚至是军事用途，如无人机蜂 (狼) 群作战等。无人机集群作为一种特殊的多智 能体系统，个体无需全局通信，仅通过对其周围 一定范围内个体间的通信、合作和协调等就可以 表达集群整体结构和功能。它在自组织能力、推 理能力，以及对未知环境的适应性等方面有很多 潜在应用。 无论是地面起飞式无人机集群，还是空投式 无人机集群，其控制技术的难点都在于队形控 制，核心在于解决可行性和有效性两个问题[2] ：可 行性是研究无人机集群能不能全局可控，使之形 成所有预定队形；有效性则回答了最少需要输入 多少信号，才能达到全局可控。最小领航集选取 与这 2 个问题密切相关。 对于通信网络拓扑结构图为有向图的领航跟 随网络系统，文献 [3] 通过引进匹配概念，使有向 网络的可控性问题已得到较好解决。但是，对于 无向领航跟随网络系统控制而言，正如 Kumar 等 [4] 于 2019 年所指出的那样：如何选取领航顶 点、如何选取最少个数的领航顶点都是尚待解决 的难题。 目前，无向网络控制技术已经引起人们的广 泛关注。文献 [5] 是一篇较早关注无向网络可控 性的文章，该文通过 Kalman 秩条件给出了无向网 络可控的充要条件。研究无向网络领航集常用的 图结构有：强制零点集 (zero forcing set, ZFS)[4, 6-8] 、 约束匹配 (constraint matching, CM)[8-11]和非平凡等 价划分 (nontrivial equitable partition，NEP)[12-15] 等。 已有的研究成果表明无向网络可控当且仅当领航 集是推广的 ZFS，且 Shima 等 [8, 10] 发现了网络中 收稿日期：2020−06−08. 基金项目：国家自然科学基金项目 (11872371). 通信作者：戴丽. E-mail：daili@nudt.edu.cn. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021