第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 systems, 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 problem 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; controllability; 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
第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·485· ZFS与CM之间具有等价关系。基于NEP概念人 输入控制信号的个体称为领航顶点，其余顶点则 们给出了网络可控的必要条件，同时也证明了网 称为跟随顶点。本文考虑有n个无人机个体的线 络可控当且仅当它的每个连通分支可控。 性时不变系统，个体的动力学方程描述为 Ji等u6-1切则是通过Laplace矩阵的特征向量 (x:-x), x为跟随顶点 研究无向网络的可控性，其中文献[16)给出了无向 VI.VJEE(G) (1) 网络可控的充要条件，文献[I7]则给出DCD、TCD x为领航顶点 等破坏网络可控性的顶点集图特征。文献[18-19] （,eE(G 证明了高阶时不变系统的可控性等价于一阶（线 式中：：为第i个无人机的状态信息；山为外界输 性)时不变系统的可控性，通过Laplace矩阵的特 入控制信息。如图l,由Kalman秩条件知，取 征向量给出了无向网络可控的充要条件，同时指 或作为领航顶点，则系统可控：若取2作为领 出了使网络可控的2个方法：增加领航顶点和修 航顶点，则系统不可控。 改网络权值。 这些研究关注重点在于从理论上给出领航集 的代数特征或图论特征，所举算例规模较小。对于 仅具有单特征值的无向网络系统，可以从代数角 度给出领航集。理论研究表明，当网络中个体数 图1领航集的选取对系统可控性影响 量趋向无穷时，网络Laplace矩阵仅具有单特征值 Fig.1 Influence of leader's selection on the control- 的概率趋向1。但是，对于无人机集群系统，个体数 lability of the systems 量大多在几十至几百之间，这类系统的Laplace矩 1.2预备理论 阵具有多重特征值的可能性很大。现有的研究很 设x=[x…xJ,则式(I)为x=-Lx,其中 少涉及求解这种规模无向网络领航集的算法。 L=D-A为通信网络拓扑结构图G的Laplace 复杂网络的相关研究值得借鉴。Hamdan 矩阵，D为度对角矩阵，A为邻接矩阵。不防设 等如采用启发式算法求复杂网络的领航集，之所 F={,2,…,ym}为跟随集，F的补集F={ym+1 以采用启发式算法求领航集是因为这一问题是NP vm+2,…,vn}为领航集。记Ls-r为L中由顶点集S 难问题。在无向复杂网络的可控性研究中，多采 对应行与顶点集T对应列所组成的子矩阵。 用携带更多信息的可控性Gramian矩阵22)。 研究结果表明，无向网络可控性与Laplace矩 Katherine等P网研究了平均可控性以及可控性与鲁 阵L的特征值和特征向量有关。 棒性的关系，并给出使树图可控的领航集选取方 性质1618图设F为跟随集，则无向网络线性 法。2020年，基于顶点分类文献[25]提出大规模 时不变系统式(1)可控，当且仅当L与LF没有 动态系统的最小领航顶点选取问题的算法。 共同特征值。 本文针对具有几十个个体的无向领航跟随模 性质2设F为领航集，y为Laplace矩阵L 式无人机集群领航顶点选取问题，研究领航顶点 的任意特征向量，则无向网络线性时不变系统 的图特征，解决具有何种图特征的顶点必须成为领 式(1)可控当且仅当y≠0，即y中领航顶点对应 航顶点，以及如何求出最小领航集这2个问题；给 的分量不全为0，其中yF表示y中对应于领航集 出求领航集的算法并用数值仿真实验验证算法的 F分量构成的向量21刀。 有效性，分析无人机集群领航集的数值特征。 性质2给出领航集的代数特征。值得注意的 1 基本理论 是，性质2中的特征向量y是Laplace矩阵L的任 意一个特征向量，因此，当L有多重特征值时，并 1.1无人机集群通信网络的图论模型 不能仅通过考察它的所有线性无关的特征向量得 无人机个体间的通信关系可用图表示。设图 到领航集，而应进一步验证全部具有零分量的特 G=(VE),其中顶点集V={y,2,…,yn},y表示第 征向量。从数值计算角度而言，这种验证计算量 i个无人机个体，边，yeE当且仅当第i个无人 大，难以实现。本文将从领航顶，点的图特征出发， 机与第j个无人机间可通信，G称为通信网络拓 给出确保系统可控的领航集求解算法。 扑结构图。若无人机个体间的通信关系是单向 2关键集和完美关键集 的，则G为有向图；若无人机个体间是双向通信 的，则G为无向网络。 由性质2可知，对于非空顶点集T,若通信网 对于领航跟随模式的无人机集群，接收外界 络拓扑结构图G的Laplace矩阵L有一个特征向
ZFS 与 CM 之间具有等价关系。基于 NEP 概念人 们给出了网络可控的必要条件，同时也证明了网 络可控当且仅当它的每个连通分支可控。 Ji 等 [16-17] 则是通过 Laplace 矩阵的特征向量 研究无向网络的可控性，其中文献 [16] 给出了无向 网络可控的充要条件，文献 [17] 则给出 DCD、TCD 等破坏网络可控性的顶点集图特征。文献 [18-19] 证明了高阶时不变系统的可控性等价于一阶 (线 性) 时不变系统的可控性，通过 Laplace 矩阵的特 征向量给出了无向网络可控的充要条件，同时指 出了使网络可控的 2 个方法：增加领航顶点和修 改网络权值。 这些研究关注重点在于从理论上给出领航集 的代数特征或图论特征，所举算例规模较小。对于 仅具有单特征值的无向网络系统，可以从代数角 度给出领航集。理论研究表明，当网络中个体数 量趋向无穷时，网络 Laplace 矩阵仅具有单特征值 的概率趋向 1。但是，对于无人机集群系统，个体数 量大多在几十至几百之间，这类系统的 Laplace 矩 阵具有多重特征值的可能性很大。现有的研究很 少涉及求解这种规模无向网络领航集的算法。 复杂网络的相关研究值得借鉴。Hamdan 等 [20-21] 采用启发式算法求复杂网络的领航集，之所 以采用启发式算法求领航集是因为这一问题是 NP 难问题。在无向复杂网络的可控性研究中，多采 用携带更多信息的可控性 Gramian 矩阵[ 2 2 - 2 3 ]。 Katherine 等 [24] 研究了平均可控性以及可控性与鲁 棒性的关系，并给出使树图可控的领航集选取方 法。2020 年，基于顶点分类文献 [25] 提出大规模 动态系统的最小领航顶点选取问题的算法。 本文针对具有几十个个体的无向领航跟随模 式无人机集群领航顶点选取问题，研究领航顶点 的图特征，解决具有何种图特征的顶点必须成为领 航顶点，以及如何求出最小领航集这 2 个问题；给 出求领航集的算法并用数值仿真实验验证算法的 有效性，分析无人机集群领航集的数值特征。 1 基本理论 1.1 无人机集群通信网络的图论模型 G = (V,E) V = {v1, v2,··· , vn} vi vi , vj ∈ E 无人机个体间的通信关系可用图表示。设图 ，其中顶点集 ， 表示第 i 个无人机个体，边 当且仅当第 i 个无人 机与第 j 个无人机间可通信，G 称为通信网络拓 扑结构图。若无人机个体间的通信关系是单向 的，则 G 为有向图；若无人机个体间是双向通信 的，则 G 为无向网络。 对于领航跟随模式的无人机集群，接收外界 输入控制信号的个体称为领航顶点，其余顶点则 称为跟随顶点。本文考虑有 n 个无人机个体的线 性时不变系统，个体的动力学方程描述为 xi ′ = ∑ vi,vj∈E(G) (xj − xi), xi为跟随顶点 ∑ vi,vj∈E(G) (xj − xi)+ui , xi为领航顶点 (1) xi i ui v1 v3 v2 式中： 为第 个无人机的状态信息； 为外界输 入控制信息。如图 1，由 Kalman 秩条件[5] 知，取 或 作为领航顶点，则系统可控；若取 作为领 航顶点，则系统不可控。 v1 v2 v3 图 1 领航集的选取对系统可控性影响 Fig. 1 Influence of leader’s selection on the controllability of the systems 1.2 预备理论 x = [x1 x2 ··· xn] T x ′ = −Lx L = D− A G D A F = {v1, v2,··· , vm} F F¯ = {vm+1, vm+2,··· , vn} LS→T L S T 设 ，则式 (1) 为 ，其中 为通信网络拓扑结构图 的 Laplace 矩阵， 为度对角矩阵， 为邻接矩阵。不防设 为跟随集， 的补集 为领航集。记 为 中由顶点集 对应行与顶点集 对应列所组成的子矩阵。 L 研究结果表明，无向网络可控性与 Laplace 矩 阵 的特征值和特征向量有关。 L LF→F 性质 1 [16-18] 设 F 为跟随集，则无向网络线性 时不变系统式 (1) 可控，当且仅当 与 没有 共同特征值。 F y L yF¯ , 0 y yF¯ y F 性质 2 设 为领航集， 为 Laplace 矩阵 的任意特征向量，则无向网络线性时不变系统 式 (1) 可控当且仅当 ，即 中领航顶点对应 的分量不全为 0，其中 表示 中对应于领航集 分量构成的向量[12, 17]。 y L L 性质 2 给出领航集的代数特征。值得注意的 是，性质 2 中的特征向量 是 Laplace 矩阵 的任 意一个特征向量，因此，当 有多重特征值时，并 不能仅通过考察它的所有线性无关的特征向量得 到领航集，而应进一步验证全部具有零分量的特 征向量。从数值计算角度而言，这种验证计算量 大，难以实现。本文将从领航顶点的图特征出发， 给出确保系统可控的领航集求解算法。 2 关键集和完美关键集 T L 由性质 2 可知，对于非空顶点集 ，若通信网 络拓扑结构图 G 的 Laplace 矩阵 有一个特征向 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·485·
·486· 智能系统学报 第16卷 量y使得y=0,则该顶点集T不能作为领航集， 邻。首先断言：矩阵Ls-s有特征值A(d≠m)。事 也就是说，此时为使无人机集群可控，必须将T 实上，由于S中有m个顶点与S中所有顶点都相邻 的补集中某些顶点加入到领航集。基于此，本文 且其余顶点都不与S中顶点相邻，所以Ls→s-m山s 提出关键集的概念。 为顶点导出子图GS]的Laplace矩阵（其中Is,为 2.1关键集 1SI阶单位矩阵)，故Ls-s-mls有特征值0。 定义1关键集。设非空顶点集ScV,L为 情况1若矩阵Ls-s-mls只有零特征值。 通信网络拓扑结构图G的Laplace矩阵，若存在L 此时必有Ls-s-mls1=0ss1。注意到v∈S, 的一个特征向量y使得y=0,则称顶点集S为关 若v与S中顶点都相邻，则其在矩阵Ls-s中对应 键集(critical set,CS)。若lSI=k,则称S为k关键 的行向量L,s分量全为1；若v与S中顶点都不 集(kcritical set)。 相邻，则其对应的行向量L-s分量全为0。因 定义2完美关键集。设S为关键集，若存在 此，构造n阶列向量y=[1-S11…10…0],则易 L的一个特征向量y使得y,≠0v∈S),则称S为 见y为Laplace矩阵L的特征向量。 完美关键集(perfect critical set,.PCS)。若SI=k,则 情况2若矩阵Ls-s-mls,有非零特征值。 称S为k完美关键集(k perfect critical set). 此时取Lss-mls的特征值'≠0，令 定义3最小完美关键集。设S为关键集，若 =+m,则A为Lss的特征值且A≠m。 它的任何真子集都不再是关键集，则称S为最小 设ys为矩阵Lss相应于特征值A(d≠m)的 完美关键集(minimal perfect critical set,.MPCS)o 特征向量，构造n阶列向量y=ys0,则有 若S=k,则称S为k最小完美关键集(k minimal Ays (3) perfect critical set). & 若通信网络拓扑结构图为非连通图，则考虑 由Ls-sys=ys知 它的连通分支，故不失一般性，本节讨论的通信 Ii Ls-sys =mlisys =AIspys 网络拓扑结构图均为连通图。连通图的 再由A≠m知15ys=0,从而Ls-sys=0。于是 Laplace矩阵的零特征值是单重特征值，且其特征 由式(3)知Ly=y,即向量y为L的一个特征向量。 向量为1，(1.表示分量均为1的n维列向量)，该 由定理2可知图1中的顶点集{1，}是关键 特征向量不能导出关键集，因此，若无特别声明， 集，所以？不能作为领航顶点。 本节中出现的特征值入都不为0。 在一定条件下，运用定理2判断一个顶点子 由k关键集的定义可知，k为正整数且k<n, 集S是否为关键集时，可以不考虑5中那些与 定理1表明k≥2。 S中顶点都相邻或者都不相邻的顶点。 定理1n阶连通无向网络不存在1关键集。 设特征向量y是与k完美关键集S对应的特 证明设y为图G的Laplace矩阵L的一个特 征向量，即y5=0且y的非零分量恰有k个，于是 征向量，设其相应的特征值为入，则有Ly=y。于 有引理1。设[w,S]表示一个端点为v另一个端 是有1Ly=1y。由L=D-A知1L=0xm,从而： 点属于S的边集。 =∑o 引理1设S为k完美关键顶点集，则 (2) w∈，有I{,S]引≠1且I,S]≠k-1。 若S为1关键集，不防设S={,则由y:=0及 证明设S={,2,…,}为k完美关键集， 式(2)可知ys=0,于是y=0与y为特征向量矛盾。 存在y=y2…y%0…0jr为Laplace矩阵L 由性质2及定理1知推论1、2成立。 的特征向量。由S为k完美关键集知片≠0i=1, 推论1设G为n阶连通无向网络，ScV且 2…,k)。 S1=n-1,若取S为领航集，则系统可控。 v∈S,若v,S]I=1,不妨设vw1∈E,则L-y= 推论2设n阶无向网络G为非连通图，则 y=0,矛盾。 G有1关键集的充要条件是G中有孤立顶点。 we5,若w,S]I=k-1,不防设v与1,2，…， 由定理1可知，对于n阶连通无向网络的 -1都相邻，则 k关键集，必有2≤k≤n-1。 Li-vy 定理2设顶点集ScV且S|≥2，若w∈S, v要么与S中所有顶点都相邻，要么与S中所有顶 再由式(2)知=0，矛盾。 点都不相邻，则S为关键集。 2.22关键集和3关键集的图特性 证明设S中有m个顶点与S中所有顶点都相 由定理1知，2关键集是2完美关键集，也是
y yT = 0 T T 量 使得 ，则该顶点集 不能作为领航集， 也就是说，此时为使无人机集群可控，必须将 的补集中某些顶点加入到领航集。基于此，本文 提出关键集的概念。 2.1 关键集 S ⊂ V L L y yS¯ = 0 |S | = k 定义 1 关键集。设非空顶点集 ， 为 通信网络拓扑结构图 G 的 Laplace 矩阵，若存在 的一个特征向量 使得 ，则称顶点集 S 为关 键集 (critical set, CS)。若 ，则称 S 为 k 关键 集 (k critical set)。 L y yv , 0(∀v ∈ S ) |S | = k 定义 2 完美关键集。设 S 为关键集，若存在 的一个特征向量 使得 ，则称 S 为 完美关键集 (perfect critical set, PCS)。若 ，则 称 S 为 k 完美关键集 (k perfect critical set)。 |S | = k 定义 3 最小完美关键集。设 S 为关键集，若 它的任何真子集都不再是关键集，则称 S 为最小 完美关键集 (minimal perfect critical set, MPCS)。 若 ，则称 S 为 k 最小完美关键集 (k minimal perfect critical set)。 1 T n 1n λ 若通信网络拓扑结构图为非连通图，则考虑 它的连通分支，故不失一般性，本节讨论的通信 网络拓扑结构图均为连通图。连通图 的 Laplace 矩阵的零特征值是单重特征值，且其特征 向量为 , ( 表示分量均为 1 的 n 维列向量)，该 特征向量不能导出关键集，因此，若无特别声明， 本节中出现的特征值 都不为 0。 k < n k ⩾ 2 由 k 关键集的定义可知，k 为正整数且 ， 定理 1 表明 。 定理 1 n 阶连通无向网络不存在 1 关键集。 y L λ Ly = λy 1 T n Ly = λ1 T n y L = D− A 1 T n L = 01×n 证明 设 为图 G 的 Laplace 矩阵 的一个特 征向量，设其相应的特征值为 ，则有 。于 是有 。由 知 ，从而： 1 T n y = ∑n i=1 yi = 0 (2) S = {v1} ys¯ = 0 yS = 0 y = 0 y 若 S 为 1 关键集，不防设 ，则由 及 式 (2) 可知 ，于是 与 为特征向量矛盾。 由性质 2 及定理 1 知推论 1、2 成立。 S ⊂ V |S | = n−1 推论 1 设 G 为 n 阶连通无向网络， 且 ，若取 S 为领航集，则系统可控。 G 推论 2 设 n 阶无向网络 G 为非连通图，则 G 有 1 关键集的充要条件是 中有孤立顶点。 2 ⩽ k ⩽ n−1 由定理 1 可知，对于 n 阶连通无向网络的 k 关键集，必有 。 定理 2 设顶点集 S ⊂ V 且 |S | ⩾ 2 ，若 ∀v ∈ S¯， v 要么与 S 中所有顶点都相邻，要么与 S 中所有顶 点都不相邻，则 S 为关键集。 证明 设 S¯ 中有 m 个顶点与 S 中所有顶点都相 LS→S λ(λ , m) S¯ LS→S −mI|S | G[S ] I|S | |S | LS→S −mI|S | 邻。首先断言：矩阵 有特征值 。 事 实上，由于 中有 m 个顶点与 S 中所有顶点都相邻 且其余顶点都不与 S 中顶点相邻，所以 为顶点导出子图 的 Laplace 矩阵 (其中 为 阶单位矩阵)，故 有特征值 0。 情况 1 若矩阵 LS→S −mI|S | 只有零特征值。 LS→S −mI|S | = 0|S |×|S | ∀v ∈ S¯ LS¯→S Lv→S Lv→S y = [1− |S | 1 ··· 1 0 ··· 0] y L 此时必有 。注意到 ， 若 v 与 S 中顶点都相邻，则其在矩阵 中对应 的行向量 分量全为 1；若 v 与 S 中顶点都不 相邻，则其对应的行向量 分量全为 0。 因 此，构造 n 阶列向量 ，则易 见 为 Laplace 矩阵 的特征向量。 情况 2 若矩阵 LS→S −mI|S | 有非零特征值。 LS→S −mI|S | λ ′ , 0 λ = λ ′ +m λ LS→S λ , m 此时取 的特征值 ， 令 ，则 为 的特征值且 。 yS LS→S λ(λ , m) y = [yS 0] 设 为矩阵 相应于特征值 的 特征向量，构造 n 阶列向量 ，则有 Ly = [ LS→S LS→S¯ LS¯→S LS¯→S¯ ] [ yS 0 ] = [ λyS LS¯→S yS ] (3) 由 LS→S yS = λyS 知 1 T |S |LS→S yS = m1 T |S | yS = λ1 T |S | yS λ , m 1 T |S | yS = 0 LS¯→S yS = 0 Ly = λy y L 再由 知 ，从而 。于是 由式 (3) 知 ，即向量 为 的一个特征向量。 {v1, v3} v2 由定理 2 可知图 1 中的顶点集 是关键 集，所以 不能作为领航顶点。 S¯ 在一定条件下，运用定理 2 判断一个顶点子 集 S 是否为关键集时，可以不考虑 中那些与 S 中顶点都相邻或者都不相邻的顶点。 y yS¯ = 0 y [{v},S ] 设特征向量 是与 k 完美关键集 S 对应的特 征向量，即 且 的非零分量恰有 k 个，于是 有引理 1。设 表示一个端点为 v 另一个端 点属于 S 的边集。 ∀v ∈ S¯ |[{v},S ]| , 1 |[{v},S ]| , k−1 引 理 1 设 S 为 k 完美关键顶点集，则 ，有 且 。 S = {v1, v2,··· , vk} y = [y1 y2 ··· yk 0 ··· 0]T L yi , 0(i = 1, 2,··· , k) 证明 设 为 k 完美关键集， 存在 为 Laplace 矩阵 的特征向量。由 S 为 k 完美关键集知 。 ∀v ∈ S¯ |[{v},S ]| = 1 vv1 ∈ E L{v}→V y = y1 = 0, ，若 ，不妨设 ，则 矛盾。 ∀v ∈ S¯ |[{v},S ]| = k−1 v1, v2,··· , vk−1 ，若 ，不防设 v 与 都相邻，则 L{v}→V y = ∑k−1 i=1 yi 再由式 (2) 知 yk = 0, 矛盾。 2.2 2 关键集和 3 关键集的图特性 由定理 1 知，2 关键集是 2 完美关键集，也是 ·486· 智 能 系 统 学 报 第 16 卷
第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·487· 2最小完美关键集。 Lta-vy dc(vi)y:=Ayi,i=1.2.....k 定理3设ScV且S=2,则S为2关键集 即dc()=dc(2)=…=dc()=。亦即当S为独立 当且仅当对y∈5，v要么与S中所有顶点都相 集时，完美关键集S中顶点度均相等。基于此，定 邻，要么与S中所有顶点都不相邻。 理5给出了独立集成为关键集的一个充分条件。 证明由定理2知充分性成立。只须证明必 定理5设S为独立集，Gs为关于顶点集 要性。 S的简化图。若S中所有顶点在图G中的度相 设S为2关键集，由引理1知[{v以，S]≠1v∈S), 等，且Sc中所有顶点在Gs中的度均为偶数，则 因此，vv以，S]I=2或v,S]I=0,即要么v与S中 S为关键集。 所有顶点都相邻，要么ⅴ与S中所有顶点都不相邻。 证明不防设S={y,2,…,}且S中所有顶 定理4设ScV且S1=3,则S为3关键集 点在图G中的度均为d。若简化图Gs为空图，则 当且仅当v∈S,v要么与S中所有顶点都相邻， 由定理2知结论成立，下设Gs非空图。 要么与S中所有顶点都不相邻。 v∈Sc,由v在图Gs中的度为偶数知行向量 证明由定理2知充分性成立。只须证明必 L-s的所有分量求和为零（模2），于是子矩阵 要性。 Ls。,一s的列向量组线性相关，所以齐次线性方程 设S为3关键集，由引理1知[w以，S]‖≠1且 组L5,-sx=0有非零解x=[x…。 I[wh,S]1≠2y∈S),因此，要么v以，S]=3,要么 [v以，S]1=0,即要么v与S中所有顶点都相邻，要 我们断言∑x=0,事实上，由S中所有顶点 么v与S中所有顶点都不相邻。 在图G中的度均为d及简化图G的构造过程可 由定理3可知，2关键集实际上就是文献26] 知顶点(i=1,2,…,k)在简化图Gs中的度也相 给出的twins顶点对，由此可见，2关键集是 等，设为≠0（因Gs非空图），于是 twins顶点对的推广。但与文献[17刀中所提出的 DCD顶点对不同，DCD顶点对考虑的是在跟随 1abs=Wd…dr=d=0 集中的2个顶点，而2关键集考虑的对象则是所 有顶点。 即有克5=0。 另外，定理3和定理4表明顶点集S能否成 取y=[x2…x0…0,A=d,则有 为2关键集或3关键集与S中的顶点是否相邻无关。 但是，当S中顶点数更多时，该结论不一定成立。 Ls-vy=[Ls-s Ls-s10 =Ls-sx= 如图2中4个深色顶点构成的顶点集S,当S [dxdx2…dx]T=x 中顶点的相邻关系如图(a)时，它是4关键集；但 对∈5，若v与S中顶点都相邻，则由 当S中顶点的相邻关系如图⑥)时，它不再是4关键集。 方与=0知L=0:若与S中顶点都不相邻。 则有L-y=0;若w∈G,则有 (a)S是4关键集 (b)S不是4关键集 L-y=-Lm-s]=0 图24关键集与GS的关系 综上可知Ly=dy,即向量y为Laplace矩阵的 Fig.2 Relationship between four critical set an GS] 特征向量，由于ys=0,故由定义1知S为关键集。 2.3独立关键集的图特征 例如，图3中的独立集S,考虑其简化图Gs, 对于顶点集S,按照定理2，删除5中与S顶 在5c中的所有顶点的度都为偶数2，由定理5知 点都相邻或都不相邻的顶点，同时也删除顶点导 S为4关键集。 出子图G⑤中所有边，称这样得到的图为关于顶 点集S的简化图，记作Gs。当S是独立集时，Gs 是二部图。记Sc,为S在简化图Gs中的补集。 若S={y,y2,…,}为独立集且为k完美关键 集，则Laplace矩阵L有一个特征向量： G Gs y=y12…g0…0]T (a)原图 (b)简化图 》≠0，i=1,2,…,k 图3简化图及其关键集 由S为独立集知v:∈S有： Fig.3 Simplification of graph G and its CS
2 最小完美关键集。 S ⊂ V |S | = 2 ∀v ∈ S¯ 定理 3 设 且 ，则 S 为 2 关键集 当且仅当对 ，v 要么与 S 中所有顶点都相 邻，要么与 S 中所有顶点都不相邻。 证明 由定理 2 知充分性成立。只须证明必 要性。 |[{v},S ]| , 1(∀v ∈ S¯) |[{v},S ]| = 2 |[{v},S ]| = 0 设 S 为 2 关键集，由引理 1 知 ， 因此，v 或 ，即要么 v 与 S 中 所有顶点都相邻，要么 v 与 S 中所有顶点都不相邻。 S ⊂ V |S | = 3 ∀v ∈ S¯ 定理 4 设 且 ，则 S 为 3 关键集 当且仅当 ，v 要么与 S 中所有顶点都相邻， 要么与 S 中所有顶点都不相邻。 证明 由定理 2 知充分性成立。只须证明必 要性。 |[{v},S ]| , 1 |[{v},S ]| , 2(∀v ∈ S¯) |[{v},S ]| = 3 |[{v},S ]| = 0 设 S 为 3 关键集，由引理 1 知 且 ，因此，要么 ，要么 ，即要么 v 与 S 中所有顶点都相邻，要 么 v 与 S 中所有顶点都不相邻。 由定理 3 可知，2 关键集实际上就是文献 [26] 给 出 的 twin s 顶点对，由此可见， 2 关键集 是 twins 顶点对的推广。但与文献 [17] 中所提出的 DCD 顶点对不同，DCD 顶点对考虑的是在跟随 集中的 2 个顶点，而 2 关键集考虑的对象则是所 有顶点。 另外，定理 3 和定理 4 表明顶点集 S 能否成 为 2 关键集或 3 关键集与 S 中的顶点是否相邻无关。 但是，当 S 中顶点数更多时，该结论不一定成立。 如 图 2 中 4 个深色顶点构成的顶点 集 S， 当 S 中顶点的相邻关系如图 (a) 时，它是 4 关键集；但 当S中顶点的相邻关系如图(b)时，它不再是4关键集。 S S (a) S 是 4 关键集 (b) S 不是 4 关键集 图 2 4 关键集与 G[S] 的关系 Fig. 2 Relationship between four critical set an G[S] 2.3 独立关键集的图特征 S¯ G [ S¯ ] GS GS S¯ GS GS 对于顶点集 S，按照定理 2，删除 中与 S 顶 点都相邻或都不相邻的顶点，同时也删除顶点导 出子图 中所有边，称这样得到的图为关于顶 点集 S 的简化图，记作 。当 S 是独立集时， 是二部图。记 为 S 在简化图 中的补集。 S = {v1, v2,··· , vk} L 若 为独立集且为 k 完美关键 集，则 Laplace 矩阵 有一个特征向量： y = [y1 y2 ··· yk 0 ··· 0]T yi , 0, i = 1,2,··· , k 由 S 为独立集知 ∀vi ∈ S 有： L{vi}→V y = dG(vi)yi = λyi , i = 1,2,··· , k 即 dG(v1) = dG(v2) = ··· = dG(vk) = λ 。亦即当 S 为独立 集时，完美关键集 S 中顶点度均相等。基于此，定 理 5 给出了独立集成为关键集的一个充分条件。 GS S¯ GS GS 定理 5 设 S 为独立集， 为关于顶点集 S 的简化图。若 S 中所有顶点在图 G 中的度相 等，且 中所有顶点在 中的度均为偶数，则 S 为关键集。 S = {v1, v2,··· , vk} GS GS 证明 不防设 且 S 中所有顶 点在图 G 中的度均为 d。若简化图 为空图，则 由定理 2 知结论成立，下设 非空图。 ∀v ∈ S¯ GS GS Lv→S LS GS →S LS¯ Gs →S x = 0 x = [x1 x2 ··· xk] T ，由 v 在图 中的度为偶数知行向量 的所有分量求和为零 (模 2)，于是子矩阵 的列向量组线性相关，所以齐次线性方程 组 有非零解 。 ∑k i=1 xi = 0 GS vi(i = 1,2,··· , k) GS d ′ , 0 GS 我们断言 ，事实上，由 S 中所有顶点 在图 G 中的度均为 d 及简化图 的构造过程可 知顶点 在简化图 中的度也相 等，设为 (因 非空图)，于是 1 T 1×|S¯ Gs |LS¯ GS →S x = [d ′ d ′ ··· d ′ ]x = d ′∑k i=1 xi = 0 ∑k i=1 即有 xi = 0。 y = [x1 x2 ··· xk 0 ··· 0]T 取 ，λ = d ，则有 LS→V y = [LS→S LS→S¯ ] [ x 0 ] = LS→S x = [dx1 dx2 ··· dxk] T = λx ∀v ∈ S¯ ∑k i=1 xi = 0 L{v}→V y = 0 L{v}→V y = 0 ∀v ∈ S¯ Gs 对 ， 若 v 与 S 中顶点都相邻，则由 知 ；若 v 与 S 中顶点都不相邻， 则有 ；若 ，则有 L{v}→V y = [L{v}→S L{v}→S¯ ] [ x 0 ] = L{v}→S x = 0 Ly = λy y yS¯ = 0 综上可知 ，即向量 为 Laplace 矩阵的 特征向量，由于 ，故由定义 1 知 S 为关键集。 GS S¯ GS 2 例如，图 3 中的独立集 S，考虑其简化图 ， 在 中的所有顶点的度都为偶数 ，由定理 5 知 S 为 4 关键集。 简化图 S G S S GS S (a) 原图 (b) 简化图 GS 图 3 简化图及其关键集 Fig. 3 Simplification of graph G and its CS 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·487·
·488· 智能系统学报 第16卷 3 最小领航集 于是可构造二部图H=(U,V;E)如图5所 示。从该二部图中可以看出每个顶点”：只能覆盖 基于关键集的概念，本节讨论如何求出无人 一个4，于是从每个4的相邻顶点任取一个组成 机集群最小领航集的算法。 的集合就是图G的最小领航集，比如可取T= 3.1算法理论基础 ,2,4,}为最小领航集。 由性质2及关键集的定义知定理6成立。 定理6设F为跟随集，F为领航集，则双向 ● 通信无人机集群线性时不变系统（见式(1）)可控 当且仅当F中不包含关键集。 V1 V2 V3 V4 V's V5 V7 V's V9 V1o 证明由性质2知系统（见式(1）)可控当且 仅当y≠0，其中y是任意一个特征向量。由定 图5二部图 Fig.5 Bipartite graph 义1知，yF≠0当且仅当F不是关键集且不包含 任何关键集。 本算例说明如何运用关键集求出无人机集群 通信网络拓扑结构图的最小领航集。 设S1,S2,…,Sm是无人机集群通信网络拓扑 结构图的所有关键集，构造二部图H=(U,V:E), 3.3CSA算法复杂性分析 顶点集U={W,,…,4m},其中与S:对应； 般地，CSA算法的1)和3)都不是多项式时 间的算法。但是，基于本文给出的定理，求出相 V=V(G)={,2,…,}为无人机集群通信网络拓 扑结构图G的顶点集，v叫∈E(H)当且仅当∈Sj。 应特殊的关键集及领航集则是多项式时间算法， 若∈E(H则称顶点M覆盖关键集Sj。由定 具体的算法流程如图6所示。 理6可知求最小领航集等价于求覆盖所有关键集 (开始 的最小顶点集T(Ts)。 3.2最小领航集算法 输人Laplace矩阵L,n,T:=O 基于定理6，本节给出求领航集的算法(critic 找所有2关键集S al set algorithm,CSA): 谷 1)求出无人机集群通信网络拓扑结构图 任取y,∈S,T=TU{v G的所有k关键集S(i=1,2,…,m): 找所有3 2)构造二部图H=(UV;E): 领航T可控 关键集S 3)求最小顶点集T(T二V)使T中的顶点覆盖 所有关键集，则T即为最小领航集。 N 例如，图4中G来自文献[15]，由定理3知 已找3关键集 它有2关键集S1={M,%}、S2=2,、S3={v4,s、 Y S4={,;由定理4知该图没有3关键集；由于 T=0 2个悬挂点4、都与%相邻，故由引理1知% 不属于任何完美关键集；同理，考虑”1和%这 输出T 2个顶点可知0也不属于任何关键集。从而，容 易知道图4中不存在5完美关键集：对于4完美 结束 关键集只能是上述4个S:位=1,2,3,4)中每个集合 图6CSA算法流程 各取一个构成的集合，容易验证它们都不是关键 Fig.6 Flow chart of CSA 集。即上述4个S:(i=1,2,3,4)是该网络的全部最 由定理3知，在CSA算法流程图中找出所有2 小完美关键集。 关键集的算法复杂性为On)。由定理4知，找所 有3关键集的算法复杂性为0n),因此，图6所 示的CSA算法复杂性为Om)。 3.4数值实验及分析 在实验中，设无人机集群的初始位置随机，经 图4图G及其关键集 过一段时间后形成稳定的通信网络拓扑结构图， Fig.4 Graph G it's critical set 并在后续保持通信关系不变。在具体的数值实验
3 最小领航集 基于关键集的概念，本节讨论如何求出无人 机集群最小领航集的算法。 3.1 算法理论基础 由性质 2 及关键集的定义知定理 6 成立。 定理 6 设 F 为跟随集， F 为领航集，则双向 通信无人机集群线性时不变系统 (见式 (1)) 可控 当且仅当 F 中不包含关键集。 yF¯ , 0 y yF¯ , 0 证明 由性质 2 知系统 (见式 (1)) 可控当且 仅当 ，其中 是任意一个特征向量。由定 义 1 知， 当且仅当 F 不是关键集且不包含 任何关键集。 S 1,S 2,··· ,S m H = (U,V;E) U = {u1,u2,··· ,um} ui S i V = V(G) = {v1, v2,··· , vn} viuj ∈ E(H) vi ∈ S j viuj ∈ E (H) vi S j T(T ⊆ V) 设 是无人机集群通信网络拓扑 结构图的所有关键集，构造二部图 ， 顶点集 ，其中 与 对应； 为无人机集群通信网络拓 扑结构图 G 的顶点集， 当且仅当 。 若 则称顶点 覆盖关键集 。由定 理 6 可知求最小领航集等价于求覆盖所有关键集 的最小顶点集 。 3.2 最小领航集算法 基于定理 6，本节给出求领航集的算法 (critical set algorithm, CSA)： S i(i = 1,2,··· ,m) 1 ) 求出无人机集群通信网络拓扑结构 图 G 的所有 k 关键集 ； 2) 构造二部图 H = (U,V;E) ； 3) 求最小顶点集 T(T ⊆ V) 使 T 中的顶点覆盖 所有关键集，则 T 即为最小领航集。 S 1 = {v1, v6} S 2 = {v2, v3} S 3 = {v4, v5} S 4 = {v7, v8} v4 v5 v9 v9 v1 v6 v10 S i(i = 1,2,3,4) S i(i = 1,2,3,4) 例如，图 4 中 G 来自文献 [15]，由定理 3 知 它有 2 关键集 、 、 、 ；由定理 4 知该图没有 3 关键集；由于 2 个悬挂点 、 都与 相邻，故由引理 1 知 不属于任何完美关键集；同理，考虑 和 这 2 个顶点可知 也不属于任何关键集。从而，容 易知道图 4 中不存在 5 完美关键集；对于 4 完美 关键集只能是上述 4 个 中每个集合 各取一个构成的集合，容易验证它们都不是关键 集。即上述 4 个 是该网络的全部最 小完美关键集。 v1 v6 v10 v9 v4 v5 v2 v3 v8 v7 图 4 图 G 及其关键集 Fig. 4 Graph G it’s critical set H = (U,V;E) vi uj uj T = {v1, v2, v4, v7} 于是可构造二部图 如 图 5 所 示。从该二部图中可以看出每个顶点 只能覆盖 一个 ，于是从每个 的相邻顶点任取一个组成 的集合就是图 G 的最小领航集，比如可取 为最小领航集。 u1 u2 u3 u4 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 图 5 二部图 Fig. 5 Bipartite graph 本算例说明如何运用关键集求出无人机集群 通信网络拓扑结构图的最小领航集。 3.3 CSA 算法复杂性分析 一般地，CSA 算法的 1) 和 3) 都不是多项式时 间的算法。但是，基于本文给出的定理，求出相 应特殊的关键集及领航集则是多项式时间算法， 具体的算法流程如图 6 所示。 开始 结束 Y N Y N 输入 Laplace 矩阵 L, n, T:=Ø 任取 vi∈Si ,T:=T∪{vi } 找所有 3 领航 关键集 Si T 可控 已找 3 关键集 T:=Ø 输出 T 找所有 2 关键集 Si 图 6 CSA 算法流程 Fig. 6 Flow chart of CSA O(n 3 ) O(n 4 ) O(n 4 ) 由定理 3 知，在 CSA 算法流程图中找出所有 2 关键集的算法复杂性为 。由定理 4 知，找所 有 3 关键集的算法复杂性为 ，因此，图 6 所 示的 CSA 算法复杂性为 。 3.4 数值实验及分析 在实验中，设无人机集群的初始位置随机，经 过一段时间后形成稳定的通信网络拓扑结构图， 并在后续保持通信关系不变。在具体的数值实验 ·488· 智 能 系 统 学 报 第 16 卷
第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·489· 中，程序将在10×10平面区域内随机生成n个顶 取1个顶点放入领航顶点集；其次，对于多重特征 点，代表n个无人机个体的初始位置，设无人机个 值，设它的重数为m(m≥2)，由于这种特征值对应 体的通信半径为参数d。图7是实验中随机生成 的特征向量可能具有不同的非零分量集合，因 的3个通信网络拓扑结构图G。 此，这种特征值可能对应多个不同的MPCS,程序 对具有相同非零分量的特征向量进行识别并重新 认定该特征值的重数m1m1≤m)。在特征向量的 非零分量中任取m个对应顶点放入领航顶点集。 在图论方法中，程序基于本文给出的定理2~ 4 3 5,求出2关键集、3关键集和孤立关键集等一些 2 特殊的关键集。然后，在每个关键集中任取一个 顶点放入领航顶点集。 2 3 456789 x/m CSA算法则是将代数方法和图论方法相结合 (a)e10,d=5 求关键集。对于单重特征值，程序用代数方法求 它的关键集；对于多重特征值，则用图论方法求 出2关键集、3关键集。实验结果如图8所示。 1.0 0.9 0.8 0 . 0.5 345678910 0.4 Algebra x/m MPCS 0.3 (b)n=10,d左7 -◆-CSA 0.2 0.1 6g 102030405060708090100 个 (a)d=1 1.0 0.91 3 3 0.8 解0.7 童0.6 2345678910 -Algebra 0.5 MPCS x/m .4 CSA (c)=70,d1.5 03 02030405060708090100 图7无人机集群的通信网络拓扑结构 /个 Fig.7 Topology of communication network for UAVs (b)d=3 其中，图7(a)是通信半径为5时随机生成的 图8对比实验 具有10个无人机个体的通信网络拓扑结构图， Fig.8 Comparison of experimental results CSA算法求出的领航集为(1,2,3；图7(b)是通信 从图8中可以看出，通过引入图论理论求关 半径为7时随机生成的具有10个无人机个体的 键集，使得求解效率得到大幅度提高，特别是当 通信网络拓扑结构图，CSA算法求出的领航集为 通信半径d=1时，单纯的代数方法或图论方法都 {1,2,3,4,5:图7(c)是70个无人机个体通信半径为 难以搜索到领航集，但将两者相结合的CSA算法 1.5时生成的通信网络拓扑结构图，CSA算法求 仍然使得求解效率在80%以上。实验表明，代数 出的领航集为1,2，…，8}。 方法能找到一部分领航顶点，而图论方法则可以 实验1代数方法、图论方法及CSA算法的 找出另一部分领航顶点，CSA正是借助关键集概 对比实验。 念，将代数方法和图论方法统一用于构建最小领 在代数方法中，首先对于单重特征值，先求它 航顶点集。 的1个特征向量，若该特征向量的非零分量对应 实验2CSA算法的求解效率与无人机个体 的顶点集不是顶点集V,由定义1知，这些非零分 通信半径间关系。 量对应的顶点集是1个关键集，在该关键集中任 在本实验中，针对不同的无人机个体数目，测
中，程序将在 10×10 平面区域内随机生成 n 个顶 点，代表 n 个无人机个体的初始位置，设无人机个 体的通信半径为参数 d。图 7 是实验中随机生成 的 3 个通信网络拓扑结构图 G。 (a) n=10, d=5 (c) n=70, d=1.5 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 3 2 x/m x/m (b) n=10, d=7 x/m 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 6 3 7 8 5 2 4 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 1 2 3 4 5 y/m y/m y/m 图 7 无人机集群的通信网络拓扑结构 Fig. 7 Topology of communication network for UAVs {1,2,3} {1,2,3,4,5} {1,2,··· ,8} 其中，图 7(a) 是通信半径为 5 时随机生成的 具有 10 个无人机个体的通信网络拓扑结构图， CSA 算法求出的领航集为 ；图 7(b) 是通信 半径为 7 时随机生成的具有 10 个无人机个体的 通信网络拓扑结构图，CSA 算法求出的领航集为 ；图 7(c) 是 70 个无人机个体通信半径为 1.5 时生成的通信网络拓扑结构图，CSA 算法求 出的领航集为 。 实验 1 代数方法、图论方法及 CSA 算法的 对比实验。 在代数方法中，首先对于单重特征值，先求它 的 1 个特征向量，若该特征向量的非零分量对应 的顶点集不是顶点集 V，由定义 1 知，这些非零分 量对应的顶点集是 1 个关键集，在该关键集中任 m(m ⩾ 2) m1(m1 ⩽ m) m1 取 1 个顶点放入领航顶点集；其次，对于多重特征 值，设它的重数为 ，由于这种特征值对应 的特征向量可能具有不同的非零分量集合，因 此，这种特征值可能对应多个不同的 MPCS，程序 对具有相同非零分量的特征向量进行识别并重新 认定该特征值的重数 。在特征向量的 非零分量中任取 个对应顶点放入领航顶点集。 在图论方法中，程序基于本文给出的定理 2~ 5，求出 2 关键集、3 关键集和孤立关键集等一些 特殊的关键集。然后，在每个关键集中任取一个 顶点放入领航顶点集。 CSA 算法则是将代数方法和图论方法相结合 求关键集。对于单重特征值，程序用代数方法求 它的关键集；对于多重特征值，则用图论方法求 出 2 关键集、3 关键集。实验结果如图 8 所示。 10 20 30 40 50 60 70 80 90 100 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 概率 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 概率 Algebra MPCS CSA Algebra MPCS CSA n/个 10 20 30 40 50 60 70 80 90 100 n/个 (a) d=1 (b) d=3 图 8 对比实验 Fig. 8 Comparison of experimental results d = 1 从图 8 中可以看出，通过引入图论理论求关 键集，使得求解效率得到大幅度提高，特别是当 通信半径 时，单纯的代数方法或图论方法都 难以搜索到领航集，但将两者相结合的 CSA 算法 仍然使得求解效率在 80% 以上。实验表明，代数 方法能找到一部分领航顶点，而图论方法则可以 找出另一部分领航顶点，CSA 正是借助关键集概 念，将代数方法和图论方法统一用于构建最小领 航顶点集。 实验 2 CSA 算法的求解效率与无人机个体 通信半径间关系。 在本实验中，针对不同的无人机个体数目，测 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·489·
·490· 智能系统学报 第16卷 试CSA算法在不同通信半径条件下的求解效率， 人机个体数量n”与“边数/总边数（即完全图中的 实验结果如图9所示。 边数n(n-1)/2)”间的关系。 实验结果如图11所示。从图11中可以看 1.0 0.9 出，随着边数占比趋于1，领航顶点占比趋于 0.8 (n-1)/;随着边数占比趋于0，领航顶点占比趋 能0.7 ￥0.6 8odes 于1；特别是，领航顶点占比达最小。从图11 0.5 50 nodes -。-70 nodes 中可以看出，当无人机个体数量为10时，领航顶 0.4 0.3 点占比达最小的情况出现在边数占比为 0 4 6 810 通信半径dm 0.6~0.7;当无人机个体的数量为30时，领航顶点 占比达最小的情况出现在边数占比为0.4~0.6： 图9CSA算法求解效率与通信半径的关系 当无人机个体的数量为50(70)时，领航顶点占比 Fig.9 Relationship between the efficiency of CSA and communication radius of UAV 达最小的情况出现在边数占比为01~0.3。也就 从图9中可以看出，尽管CSA算法在求解过 是说，从整体上看，所有“领航顶点占比与边数占 程有一定程度的抖动，但当顶点个数小于30时， 比”曲线都是下凸曲线，无人机个体数越多，曲线 求解效率在95%上。一个有趣的现象是，当顶点 越向下凸且极小值点越向“左”偏。这一现象说 个数大于30时，若其通信半径介于3~9，则 明，若用较少个数的无人机个体控制整个无人机 CSA算法几乎100%可以找到领航集；若通信半 集群，则通信网络拓扑结构图中的边数应取值于 径小于3或大于9，则CSA算法都出现了不同程 适当范围，实验3从统计意义上给出了这个范围。 度的抖动，特别是当通信半径介于0.5~3时，算法 1.04 求解效率较差。出现这一现象的原因在于，此时 0.8 50nodes 图中单重特征值减少而多重特征值增加，这使得 出 同一特征值对应的关键集增加，而基于本文给出 的定理2~5，CSA算法只求出2关键集、3关键集 0.4 和孤立关键集等一些特殊的关键集，从而使得算 0.2 法难以找到领航集。例如，见图10，该无向网络 的特征值中，除单重特征值外，还有1个3重特征 0.2 0.40.6 0.8 1.0 值、1个4重特征值和1个5重特征值，CSA算法 边占比 难以找到它的领航集。这说明，当顶点个数多且 图11领航顶点个数与边数的关系 通信半径较小时，图中的关键集情况较复杂，需 Fig.11 Relationship between the number of leaders and edges 要进一步从理论上研究k关键集的图特征。 10 4结束语 本文以几十架无人机构成的无人机集群为应 用背景，利用Laplace矩阵的特征向量提出关键集 概念，指出领航集所必须具备的图特征，即领航 集需覆盖所有关键集。给出了2关键集和3关键 集的图特征，从图论角度给出独立集成为关键集 的一个充分条件。数值实验表明，基于关键集， 4 CSA算法在大多数情况下能以90%以上的概率 x/m 搜索到领航集。 图10复杂特征值情况的网络结构 如何刻画k(k≥4)关键集的图特征是需进一 Fig.10 Description of networks with multiple eigenvalues 步研究的内容。这是十分难以解决的问题，比如 实验3领航顶点个数与边数关系。 由图2知4关键集与这4个顶点的相邻关系有 随着无人机个体和边数的变化，领航顶点的 关，全体4阶互不同构的简单图有11个，其中边 个数也会相应地变化，因此，本实验不考虑领航 数为0、1、2、3、4、5、6的图的个数分别为1、1、 顶点个数的绝对值，而是考虑“领航顶点个数/无 2、3、2、1、1。而全体5阶互不同构的简单图有
试 CSA 算法在不同通信半径条件下的求解效率， 实验结果如图 9 所示。 0 2 4 6 8 10 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 概率 10 nodes 30 nodes 50 nodes 70 nodes 通信半径 d/m 图 9 CSA 算法求解效率与通信半径的关系 Fig. 9 Relationship between the efficiency of CSA and communication radius of UAV k 从图 9 中可以看出，尽管 CSA 算法在求解过 程有一定程度的抖动，但当顶点个数小于 30 时， 求解效率在 95% 上。一个有趣的现象是，当顶点 个数大 于 30 时，若其通信半径介 于 3～ 9， 则 CSA 算法几乎 100% 可以找到领航集；若通信半 径小于 3 或大于 9，则 CSA 算法都出现了不同程 度的抖动，特别是当通信半径介于 0.5~3 时，算法 求解效率较差。出现这一现象的原因在于，此时 图中单重特征值减少而多重特征值增加，这使得 同一特征值对应的关键集增加，而基于本文给出 的定理 2~5，CSA 算法只求出 2 关键集、3 关键集 和孤立关键集等一些特殊的关键集，从而使得算 法难以找到领航集。例如，见图 10，该无向网络 的特征值中，除单重特征值外，还有 1 个 3 重特征 值、1 个 4 重特征值和 1 个 5 重特征值，CSA 算法 难以找到它的领航集。这说明，当顶点个数多且 通信半径较小时，图中的关键集情况较复杂，需 要进一步从理论上研究 关键集的图特征。 0 2 4 6 8 10 1 2 3 4 5 6 7 8 9 10 x/m y/m 图 10 复杂特征值情况的网络结构 Fig. 10 Description of networks with multiple eigenvalues 实验 3 领航顶点个数与边数关系。 随着无人机个体和边数的变化，领航顶点的 个数也会相应地变化，因此，本实验不考虑领航 顶点个数的绝对值，而是考虑“领航顶点个数/无 n n(n−1)/2 人机个体数量 ”与“边数/总边数 (即完全图中的 边数 )”间的关系。 (n−1)/n 0.6 ∼ 0.7 0.4 ∼ 0.6 0.1 ∼ 0.3 实验结果如图 11 所示。从图 11 中可以看 出，随着边数占比趋于 1，领航顶点占比趋于 ；随着边数占比趋于 0，领航顶点占比趋 于 1；特别是，领航顶点占比达最小。从图 11 中可以看出，当无人机个体数量为 10 时，领航顶 点占比达最小的情况出现在边数占比为 ；当无人机个体的数量为 30 时，领航顶点 占比达最小的情况出现在边数占比为 ； 当无人机个体的数量为 50(70) 时，领航顶点占比 达最小的情况出现在边数占比为 。也就 是说，从整体上看，所有“领航顶点占比与边数占 比”曲线都是下凸曲线，无人机个体数越多，曲线 越向下凸且极小值点越向“左”偏。这一现象说 明，若用较少个数的无人机个体控制整个无人机 集群，则通信网络拓扑结构图中的边数应取值于 适当范围，实验 3 从统计意义上给出了这个范围。 0.2 0.4 0.6 0.8 1.0 边占比 0 0.2 0.4 0.6 0.8 1.0 领航顶点占比 10nodes 30nodes 50nodes 70nodes 图 11 领航顶点个数与边数的关系 Fig. 11 Relationship between the number of leaders and edges 4 结束语 本文以几十架无人机构成的无人机集群为应 用背景，利用 Laplace 矩阵的特征向量提出关键集 概念，指出领航集所必须具备的图特征，即领航 集需覆盖所有关键集。给出了 2 关键集和 3 关键 集的图特征，从图论角度给出独立集成为关键集 的一个充分条件。数值实验表明，基于关键集， CSA 算法在大多数情况下能以 90% 以上的概率 搜索到领航集。 如何刻画 k(k ⩾ 4) 关键集的图特征是需进一 步研究的内容。这是十分难以解决的问题，比如 由图 2 知 4 关键集与这 4 个顶点的相邻关系有 关，全体 4 阶互不同构的简单图有 11 个，其中边 数为 0、1、2、3、4、5、6 的图的个数分别为 1、1、 2、3、2、1、1。而全体 5 阶互不同构的简单图有 ·490· 智 能 系 统 学 报 第 16 卷
第3期 戴丽：双向通信无人机集群领航顶点选取方法 ·491· 34个。随着k的增加，k(k≥4)关键集的情况异常 [11]OLESKY DD,TSATSOMEROS M,VAN DEN 复杂。但是，这又是一个十分有意义的问题。比 DRIESSCHE P.Qualitative controllability and uncontrol- 如，从数值实验可以看出，仅依据本文给出的定 lability by a single entry[J].Linear algebra and its applic- 理2~5求出有限特殊的关键集，CSA算法就能在 ations.1993.187:183-194. 大多数情况下以90%以上的概率搜索到领航集。 [12]JI Meng,EGERSTEDT M.A graph-theoretic characteriz- 另外，从图论角度给出领航集的充要条件，最 ation of controllability for multi-agent systems[Cl//Pro- ceedings of 2007 American Control Conference.New 小领航顶点数的上、下界等也都是值得进一步研 York.NY,USA.2007:4588-4593. 究的问题。 [13]RAHMANI A,JI Meng,MESBAHI M,et al.Controllab- 参考文献： ility of multi-agent systems from a graph-theoretic per- spective[J].SIAM journal on control and optimization, [1]DORRI A,KANHERE SS,JURDAK R.Multi-agent sys- 2009,48(1y162-186 tems:a survey[J].IEEE access,2018,6:28573-28593. [14]MARTINI S,EGERSTEDT M,BICCHI A.Controllabil- [2]肖延东，老松杨，侯绿林，等.基于节点负荷失效的网络 ity analysis of multi-agent systems using relaxed equit- 可控性研究.物理学报，2013,62(18：180201 able partitions[J].International journal of systems,con- XIAO Yandong,LAO Songyang,HOU Lulin,et al.Net- trol and communications,2010,2(1/2/3):100-121. work controllability based on node overloaded failure[J]. [15]AGUILAR C O,GHARESIFARD B.Almost equitable Acta Physica Sinica,2013,62(18):180201. partitions and new necessary conditions for network con- [3]LIU Yangyu,SLOTINE J J,BARABASI A L.Controllab- trollability [J].Automatica,2017,80:25-31. ility of complex networks[J].Nature,2011,473(7346): [16]JI Zhijian,WANG Zidong,LIN Hai,et al.Interconnec- 167-173. tion topologies for multi-agent coordination under leader- [4]KUMAR Y,SHARA M,PRASANNA C.Minimizing in- follower framework[J].Automatica,2009,45(12): puts for strong structural controllability[Cl//Proceedings of 2857-2863 2019 American Control Conference.Philadelphia,PA. [17]JI Zhijian,YU Haisheng.A new perspective to graphical USA.2019:2048-2053 characterization of multiagent controllability[J].IEEE [5]TANNER H G.On the controllability of nearest neighbor transactions on cybernetics,2017,47(6):1471-1483. interconnections[C]/Proceedings of the 43rd IEEE Confer- [18]WANG Long,JIANG Fangcui,XIE Guangming,et al. ence on Decision and Control (CDC)(IEEE Cat.No. Controllability of multi-agent systems based on agree- 04CH37601).Nassau,Bahamas,2004:2467-2472. ment protocols[J].Science in China series F:information [6]MONSHIZADEH N.ZHANG Shou.CAMLIBEL M K. sciences,2009,52(11:2074-2088. Zero forcing sets and controllability of dynamical systems [19]JIANG Fangcui,WANG Long,XIE Guangming,et al.On defined on graphs[J].IEEE transactions on automatic con- the controllability of multiple dynamic agents with fixed trol,2014.59(9):2562-2567. topology[C]//Proceedings of the 2009 Conference on [7]MOUSAVI SS.CHAPMAN A.HAERI M.et al.Null American Control Conference.St.Louis,Missouri,USA, space strong structural controllability via skew zero for- 2009:5665-5670 cing sets[C]/Proceedings of 2018 European Control Con- [20]HAMDAN A M A,NAYFEH A H.Measures of modal ference.Limassol,Cyprus,2018:1845-1850 controllability and observability for first-and second-or- [8]MOUSAVI SS.HAERI M.MESBAHI M.On the struc- der linear systems[J.Journal of guidance,control,and tural and strong structural controllability of undirected net- dynamics..1989,12(3:421-428. works[J].IEEE transactions on automatic control,2018, [21]OLSHEVSKY A.Minimal controllability problems[J]. 63(7):2234-2241 IEEE transactions on control of network systems,2014, [9]CHAPMAN A,MESBAHI M.On strong structural con- 31):249-258. trollability of networked systems:a constrained matching [22]PASQUALETTI F,ZAMPIERI S,BULLO F.Controllab- approach[C]//Proceedings of 2013 American Control Con- ility metrics,limitations and algorithms for complex net- ference.Washington,DC,USA,2013:6126-6131 works[J].IEEE transactions on control of network sys- [10]TREFOIS M,DELVENNE J C.Zero forcing number, tems,2014,1(1):40-52 constrained matchings and strong structural controllabil- [23]SUMMERS T H,CORTESI FL,LYGEROS J.On sub- ity[J].Linear algebra and its applications,2015,484: modularity and controllability in complex dynamical net- 199-218 works[J].IEEE transactions on control of network sys-
34 个。随着 k 的增加， k(k ⩾ 4) 关键集的情况异常 复杂。但是，这又是一个十分有意义的问题。比 如，从数值实验可以看出，仅依据本文给出的定 理 2~5 求出有限特殊的关键集，CSA 算法就能在 大多数情况下以 90% 以上的概率搜索到领航集。 另外，从图论角度给出领航集的充要条件，最 小领航顶点数的上、下界等也都是值得进一步研 究的问题。 参考文献： DORRI A, KANHERE S S, JURDAK R. Multi-agent systems: a survey[J]. IEEE access, 2018, 6: 28573–28593. [1] 肖延东, 老松杨, 侯绿林, 等. 基于节点负荷失效的网络 可控性研究 [J]. 物理学报, 2013, 62(18): 180201. XIAO Yandong, LAO Songyang, HOU Lülin, et al. Network controllability based on node overloaded failure[J]. Acta Physica Sinica, 2013, 62(18): 180201. [2] LIU Yangyu, SLOTINE J J, BARABÁSI A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167–173. [3] KUMAR Y, SHARA M, PRASANNA C. Minimizing inputs for strong structural controllability[C]//Proceedings of 2019 American Control Conference. Philadelphia, PA, USA, 2019: 2048−2053. [4] TANNER H G. On the controllability of nearest neighbor interconnections[C]//Proceedings of the 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601). Nassau, Bahamas, 2004: 2467−2472. [5] MONSHIZADEH N, ZHANG Shou, CAMLIBEL M K. Zero forcing sets and controllability of dynamical systems defined on graphs[J]. IEEE transactions on automatic control, 2014, 59(9): 2562–2567. [6] MOUSAVI S S, CHAPMAN A, HAERI M, et al. Null space strong structural controllability via skew zero forcing sets[C]//Proceedings of 2018 European Control Conference. Limassol, Cyprus, 2018: 1845−1850. [7] MOUSAVI S S, HAERI M, MESBAHI M. On the structural and strong structural controllability of undirected networks[J]. IEEE transactions on automatic control, 2018, 63(7): 2234–2241. [8] CHAPMAN A, MESBAHI M. On strong structural controllability of networked systems: a constrained matching approach[C]//Proceedings of 2013 American Control Conference. Washington, DC, USA, 2013: 6126−6131. [9] TREFOIS M, DELVENNE J C. Zero forcing number, constrained matchings and strong structural controllability[J]. Linear algebra and its applications, 2015, 484: 199–218. [10] OLESKY D D, TSATSOMEROS M, VAN DEN DRIESSCHE P. Qualitative controllability and uncontrollability by a single entry[J]. Linear algebra and its applications, 1993, 187: 183–194. [11] JI Meng, EGERSTEDT M. A graph-theoretic characterization of controllability for multi-agent systems[C]//Proceedings of 2007 American Control Conference. New York, NY, USA, 2007: 4588−4593. [12] RAHMANI A, JI Meng, MESBAHI M, et al. Controllability of multi-agent systems from a graph-theoretic perspective[J]. SIAM journal on control and optimization, 2009, 48(1): 162–186. [13] MARTINI S, EGERSTEDT M, BICCHI A. Controllability analysis of multi-agent systems using relaxed equitable partitions[J]. International journal of systems, control and communications, 2010, 2(1/2/3): 100–121. [14] AGUILAR C O, GHARESIFARD B. Almost equitable partitions and new necessary conditions for network controllability[J]. Automatica, 2017, 80: 25–31. [15] JI Zhijian, WANG Zidong, LIN Hai, et al. Interconnection topologies for multi-agent coordination under leaderfollower framework[J]. Automatica, 2009, 45(12): 2857–2863. [16] JI Zhijian, YU Haisheng. A new perspective to graphical characterization of multiagent controllability[J]. IEEE transactions on cybernetics, 2017, 47(6): 1471–1483. [17] WANG Long, JIANG Fangcui, XIE Guangming, et al. Controllability of multi-agent systems based on agreement protocols[J]. Science in China series F: information sciences, 2009, 52(11): 2074–2088. [18] JIANG Fangcui, WANG Long, XIE Guangming, et al. On the controllability of multiple dynamic agents with fixed topology[C]//Proceedings of the 2009 Conference on American Control Conference. St. Louis, Missouri, USA, 2009: 5665−5670. [19] HAMDAN A M A, NAYFEH A H. Measures of modal controllability and observability for first-and second-order linear systems[J]. Journal of guidance, control, and dynamics, 1989, 12(3): 421–428. [20] OLSHEVSKY A. Minimal controllability problems[J]. IEEE transactions on control of network systems, 2014, 3(1): 249–258. [21] PASQUALETTI F, ZAMPIERI S, BULLO F. Controllability metrics, limitations and algorithms for complex networks[J]. IEEE transactions on control of network systems, 2014, 1(1): 40–52. [22] SUMMERS T H, CORTESI F L, LYGEROS J. On submodularity and controllability in complex dynamical networks[J]. IEEE transactions on control of network sys- [23] 第 3 期 戴丽：双向通信无人机集群领航顶点选取方法 ·491·
·492· 智能系统学报 第16卷 tems,2016,31:91-101 eigenvectors of graphs:perron-frobenius and faber-krahn [24]FITCH K,LEONARD N E.Optimal leader selection for type theorems[M].New York:Springer,2007. controllability and robustness in multi-agent networks[Cl// 作者简介： Proceedings of 2016 European Control Conference.Aal- 戴丽，副教授，博士，主要研究方 borg,Denmark,2016:1550-1555. 向为图论、博弈论和网络优化算法 [25]MOHAMMADREZA D.Minimal driver nodes for struc- 等。主持校预研项目1项，参与国家 tural controllability of large-scale dynamical systems: 自然科学基金2项。发表学术论文 node classification[].IEEE systems journal,2020,14(3) 10余篇。 4209-4216. [26]BIYIKOGU T,LEYDOLD J,STADLER P F.Laplacian 第四届模式识别与计算机视觉大会 The 4th Chinese Conference on Pattern Recognition and Computer Vision 第四届中国模式识别与计算机视觉大会将于2021年10月29日至11月1日在北京举行。会议由中国 图象图形学学会(CSIG)、中国人工智能学会(CAAI)、中国计算机学会(CCF)和中国自动化学会(CAA)联 合主办：由北京科技大学、北京交通大学和北京邮电大学共同承办，中山大学和清华大学协办，是国内顶级 的模式识别和计算机视觉领域学术盛会。本届会议将主要汇聚国内国外模式识别和计算机视觉理论与应用 研究的广大科研工作者及工业界同行，共同分享我国模式识别与计算机视觉领域的最新理论和技术成果 提供精彩的学术盛宴。现向广大科技工作者公开征集高质量、原创性的优秀英文学术论文。大会录用的稿 件将在会上展示，会议论文集将由Springer出版社出版，并被EI和ISTP检索；优秀的论文将推荐到国内外高 质量期刊发表。 1.征文范围（包括但不局限于） 模式分类与聚类分析、结构模式识别、机器学习、神经网络与深度学习、特征提取与特征选择、计算机视 觉基础理论、底层视觉理解、图像处理、三维视觉与重构、文档分析与识别、字符识别、人脸识别与姿态识 别、目标检测、跟踪与识别、行为识别、多媒体分析与推理、医学图像处理与分析、生物特征识别、遥感影像 解译优化及学习方法、多模态信息处理、性能评测和基准数据库、视频分析与理解、视觉应用与系统、机器 人、自动驾驶中的视觉问题。 2.重要日期 投稿截止日期：2021年4月30日 录用通知日期：2021年6月30日 终稿提交日期：2021年8月15日 会议举办日期：2021年10月29日至2021年11月1日 3.会议投稿 https://cmt3.research.microsoft.com/PRCV2021/
tems, 2016, 3(1): 91–101. FITCH K, LEONARD N E. Optimal leader selection for controllability and robustness in multi-agent networks[C]// Proceedings of 2016 European Control Conference. Aalborg, Denmark, 2016: 1550−1555. [24] MOHAMMADREZA D. Minimal driver nodes for structural controllability of large-scale dynamical systems: node classification[J]. IEEE systems journal, 2020, 14(3): 4209–4216. [25] [26] BIYIKOĞU T, LEYDOLD J, STADLER P F. Laplacian eigenvectors of graphs: perron-frobenius and faber-krahn type theorems[M]. New York: Springer, 2007. 作者简介： 戴丽，副教授，博士，主要研究方 向为图论、博弈论和网络优化算法 等。主持校预研项目 1 项，参与国家 自然科学基金 2 项。发表学术论文 10 余篇。 第四届模式识别与计算机视觉大会 The 4th Chinese Conference on Pattern Recognition and Computer Vision 第四届中国模式识别与计算机视觉大会将于 2021 年 10 月 29 日至 11 月 1 日在北京举行。会议由中国 图象图形学学会（CSIG）、中国人工智能学会（CAAI）、中国计算机学会（CCF）和中国自动化学会（CAA）联 合主办；由北京科技大学、北京交通大学和北京邮电大学共同承办，中山大学和清华大学协办，是国内顶级 的模式识别和计算机视觉领域学术盛会。本届会议将主要汇聚国内国外模式识别和计算机视觉理论与应用 研究的广大科研工作者及工业界同行，共同分享我国模式识别与计算机视觉领域的最新理论和技术成果， 提供精彩的学术盛宴。现向广大科技工作者公开征集高质量、原创性的优秀英文学术论文。大会录用的稿 件将在会上展示，会议论文集将由 Springer 出版社出版，并被 EI 和 ISTP 检索；优秀的论文将推荐到国内外高 质量期刊发表。 1. 征文范围（包括但不局限于） 模式分类与聚类分析、结构模式识别、机器学习、神经网络与深度学习、特征提取与特征选择、计算机视 觉基础理论、底层视觉理解、图像处理、三维视觉与重构、文档分析与识别、字符识别、人脸识别与姿态识 别、目标检测、跟踪与识别、行为识别、多媒体分析与推理、医学图像处理与分析、生物特征识别、遥感影像 解译优化及学习方法、多模态信息处理、性能评测和基准数据库、视频分析与理解、视觉应用与系统、机器 人、自动驾驶中的视觉问题。 2. 重要日期 投稿截止日期：2021 年 4 月 30 日 录用通知日期：2021 年 6 月 30 日 终稿提交日期：2021 年 8 月 15 日 会议举办日期：2021 年 10 月 29 日至 2021 年 11 月 1 日 3.会议投稿 https://cmt3.research.microsoft.com/PRCV2021/ ·492· 智 能 系 统 学 报 第 16 卷