Graph-theoretic characterisations of structural controllability for multi-agent system with switching topology

This article considers the controllability problem for multi-agent systems. In particular, the structural controllability of multi-agent systems under switching topologies is investigated. The structural controllability of multi-agent systems is a generalisation of the traditional controllability concept for dynamical systems, and purely based on the communication topologies among agents. The main contributions of this article are graph-theoretic characterisations of the structural controllability for multi-agent systems. It turns out that the multi-agent system with switching topology is structurally controllable if and only if the union graph 𝒢 of the underlying communication topologies is connected (single leader) or leader–follower connected (multi-leader). Finally, this article concludes with several illustrative examples and discussions of the results and future work.     

Controllability improvement for multi-agent systems: leader selection and weight adjustment

For an uncontrollable system, adding leaders and adjusting edge weights are two methods to improve controllability. In this paper, the controllability of multi-agent systems under directed topologies is studied, especially on the leader selection problem and the weight adjustment problem. For a multi-agent system, necessary and sufficient algebraic conditions for controllability with fewest leaders are proposed. To improve controllability by adjusting edge weights, the system is supposed to be structurally controllable, which holds if and only if the communication topology contains a spanning tree. It is also proved that the number of the fewest edges needed to be assigned on new weights equals the rank deficiency of controllability matrix. In addition, a leader selection algorithm and a weight adjustment algorithm are presented. Simulation examples are provided to illustrate the theoretical results.     

多智能体系统可控性的图论刻画

研究领航者-跟随者结构多智能体系统的可控性问题.利用松弛的等价分化刻画了系统可控性与信息拓扑结构之间的关系,为系统可控性提供了基于图论的判别方法.基于置换群理论将对称的概念推广到多领航者系统,并证明了3种图论工具（对称性、等价分化和松弛的等价分化）之间的包含关系.仿真结果验证了所提出方法的有效性.     

Consensus problem of heterogeneous multi-agent systems with time delay under fixed and switching topologies

Consensus problem is investigated for heterogeneous multi-agent systems composed of first-order agents and second-order agents in this paper. Leader-following consensus protocol is adopted to solve consensus problem of heterogeneous multi-agent systems with time-varying communication and input delays. By constructing Lyapunov-Krasovkii functional, sufficient consensus conditions in linear matrix inequality(LMI) form are obtained for the system under fixed interconnection topology. Moreover, consensus conditions are also obtained for the heterogeneous systems under switching topologies with time delays. Simulation examples are given to illustrate effectiveness of the results.     

多智能体网络系统的能控性代数条件

能控性是多智能体系统研究的核心问题,主要包括结构可控性和精准可控性。对多智能体系统的模型和能控性代数条件进行了总结。在相对协议和绝对协议条件下,运用图论和矩阵论的知识系统分析了多智能体系统能控性的代数条件。按照同质多智能体到异质多智能体的顺序,对现有的多智能体系统模型和代数条件进行了梳理,并在已有结论的基础上对多智能体系统能控性的代数条件进行了改善,进一步提出了新的代数条件。多智能体能控性代数条件的改进大大简化了能控性的计算量。     

Controllability of switching networks of multi‐agent systems

This paper addresses the controllability of a switching network of multi‐agent systems with a leader obeying nearest‐neighbor communication rules. The leader is a particular agent acting as an external input to control other member agents. Some computationally efficient sufficient conditions for such multi‐agent systems to be controllable are derived. The results show that a multi‐agent system can be controllable even if each of its subsystem is not controllable, by appropriately selecting one of the agents as the leader and suitably designing the neighbor‐interaction rules via a switching topology. The fixed topology case is analyzed and new controllability conditions and formula of inputs for the desired formation of the network are presented. The controllability of a switching network of multi‐agent systems in the presence of communication delay is also investigated. Examples with numerical simulations are given to illustrate the theoretical results. Copyright © 2011 John Wiley & Sons, Ltd.     

Controllability of multi-agent systems based on agreement protocols

This paper investigates the controllability of multi-agent systems based on agreement protocols. First, for a group of single-integrator agents, the controllability is studied in a unified framework for both networks with leader-following structure and networks with undirected graph. Some new necessary/sufficient conditions for the controllability of networks of single-integrator agents are established. Second, we prove that, under the same topology and same prescribed leaders, a network of high-order dynamic agents is completely controllable if and only if so is a network of single-integrator agents. Third, how the selection of leaders and the coupling weights of graphs affect the controllability is analyzed. Finally, some numerical simulations are presented to demonstrate the effectiveness of the theoretical results.     

Controllability and observability of multi-agent systems with heterogeneous and switching topologies

ABSTRACT

This paper focuses on controllability and observability of multi-agent systems with heterogeneous and switching topologies, where the first- and the second-order information interaction topologies are different and switching. First, based on the controllable state set, a controllability criterion is obtained in terms of the controllability matrix corresponding to the switching sequence. Next, by virtue of the subspace sequence, two necessary and sufficient algebraic conditions are established for controllability in terms of the system matrices corresponding to all the possible topologies. Furthermore, controllability is considered from the graphic perspective. It is proved that the system is controllable if the union graph of all the possible topologies is controllable. With respect to observability, two sufficient and necessary conditions are derived by taking advantage of the system matrices and the corresponding invariant subspace, respectively. Finally, some simulation examples are worked out to illustrate the theoretical results.     

Distributed consensus of heterogeneous multi-agent systems with fixed and switching topologies

In this article, we study distributed consensus of heterogeneous multi-agent systems with fixed and switching topologies. The analysis is based on graph theory and nonnegative matrix theory. We propose two kinds of consensus protocols based on the consensus protocol of first-order and second-order multi-agent systems. Some necessary and sufficient conditions that the heterogeneous multi-agent system solves the consensus problems under different consensus protocols are presented with fixed topology. We also give some sufficient conditions for consensus of the heterogeneous multi-agent system with switching topology. Simulation examples are provided to demonstrate the effectiveness of the theoretical results.     

有向符号网络的边能控性研究

符号网络是一类具有正负符号特征的网络.在多智能体系统中,符号网络能够描述智能体之间的合作与对抗交互关系,因此受到学者的广泛关注.本文主要研究有向符号网络的边能控性.首先,对具有符号网络的多智能体系统边动力学进行建模,得到边能控性模型.其次,从网络拓扑结构角度对边能控子空间进行定量刻画,利用有向符号网络的距离和等价划分得到能控子空间的上下界估计.进一步,讨论了符号网络边能控性与顶点能控性的关系.所得结果表明:当顶点符号图为结构非平衡时,符号网络的边能控性与顶点能控性等价.最后,通过仿真结果验证所得理论的有效性.     

Controllability of discrete-time multi-agent systems with directed topology and input delay

This paper investigates the controllability of first-order and second-order discrete-time multi-agent systems with directed topology and input delay. The problem is studied in the leader–follower framework where a number of agents are selected to be leaders and serve as control inputs to all other agents. Sufficient and necessary conditions are derived for the controllability of first-order discrete-time multi-agent systems. With sampling period and feedback gain satisfying certain conditions, it is proved under three different protocols that the controllability of second-order discrete-time multi-agent systems is equivalent to that of a pair of submatrices of Laplacian matrix. In addition, the controllability of both first-order and second-order discrete-time multi-agent systems with input delay is shown, through some transformations, to be equivalent to that of the transformed non-delayed systems. Finally, some simulation examples are given to illustrate the theoretical results.     

Controllability of multi-agent systems with time-delay in state and switching topology

In this article, the controllability issue is addressed for an interconnected system of multiple agents. The network associated with the system is of the leader–follower structure with some agents taking leader role and others being followers interconnected via the neighbour-based rule. Sufficient conditions are derived for the controllability of multi-agent systems with time-delay in state, as well as a graph-based uncontrollability topology structure is revealed. Both single and double integrator dynamics are considered. For switching topology, two algebraic necessary and sufficient conditions are derived for the controllability of multi-agent systems. Several examples are also presented to illustrate how to control the system to shape into the desired configurations.     

异构变时延多智能体系统编队控制分析

实际工程应用中,异构多智能体的编队控制问题研究具有十分重要的意义。考虑现实环境影响,编队系统个体之间的通信变时延难以忽略。系统收敛速率是评价系统性能的重要依据,然而现有编队控制问题研究很少能给出相应的量化指标。针对上述情形,对包含一、二阶智能体的异构变时延系统的编队控制问题进行分析研究。首先,考虑固定有向通信拓扑情况,对领航跟随者模式下异构变时延多智能体系统提出线性一致性控制协议。然后,构建误差系统模型,利用图论与矩阵论分析方法,并结合Routh-Hurwitz定理与牛顿-莱布尼兹公式,获得系统实现编队控制的充要条件,同时得到估算系统收敛速率的不等式关系。最后,仿真算例中随机给定一种系统节点0全局可达的通信拓扑,并对不同时延情况的编队控制效果进行分析,验证一致性控制协议的正确性和有效性。     

Controllability of discrete‐time multiagent systems with switching topology

The current theoretical investigation on the controllability of switched multiagent systems mainly focuses on fixed connected topology or union graph without nonaccessible nodes. However, for discrete‐time multiagent systems with switching topology, it is still unknown whether the existing results are valid or not under the condition of arbitrary topology. Based on graph distance partitions and Wonham's geometric approach, we provide the lower and upper bounds for the dimension of controllable subspaces of discrete‐time multiagent systems. Unlike the existing results of controllability with switching topology, the proposed results have the advantage of being applicable to multiagent systems with arbitrary graphic topologies, union graph (strongly connected or not), and coupling weights. We also provide 2 algorithms for computing the lower and upper bounds for the dimension of controllable subspaces, respectively. Furthermore, as a remarkable application, we present how the proposed lower bound can be utilized for achieving the targeted controllability if the dimension of the controllable subspace of the switched system satisfies certain conditions.     

异构多无人机网络化协同控制系统的可控性

研究具有Leader-Follower结构和分布式通信拓扑的异构多无人机网络化分布式协同控制系统的可控性问题. 基于同构网络的受控一致性思想建立了异构多飞行器网络控制系统的动态模型; 并针对该动态模型的不同形式, 基于代数图论和传统的控制理论, 分别得到了异构多无人机网络化协同控制系统的可控性条件, 尤其是可控性与该网络化系统中通信拓扑之间的关系; 然后分析且提出了改善系统可控性的可行性方法. 最后仿真结果验证了本文相关结论的正确性.     

Controllability and observability of switched multi-agent systems

This paper considers controllability and observability of switched multi-agent systems, which are composed of continuous-time and discrete-time subsystems. First, a controllability criterion is established in terms of the system matrices. Then, by virtue of the concepts of the invariant subspace and the controllable state set, a method is proposed to construct the switching sequence to ensure controllability of switched multi-agent systems, and a necessary and sufficient condition is obtained for controllability. Moreover, a necessary controllability condition is derived in terms of eigenvectors of the Laplican matrix. With respect to observability, two necessary and sufficient algebraic conditions are obtained. Finally, simulation examples are provided to illustrate the theoretical results.     

异构多智能体系统有限时间一致性分析

研究二阶智能体速度不可测情况下由一阶和二阶智能体构成的异构多智能体系统有限时间一致性问题。在固定拓扑结构下,给出了异构系统实现一致性的控制协议,通过LaSalle不变集原理和齐次控制方法得到了异构系统有限时间一致性的充分条件;在切换拓扑结构下,给出了异构系统一致性的控制协议,得到了异构系统有限时间一致性的充分条件。仿真结果验证了相关结果的有效性。     

带强连通分支的多智能体系统可控包含控制

研究有强连通子图拓扑结构的有向多智能体系统领导者选择及可控包含控制问题.根据网络拓扑结构,智能体被分为两类:单元智能体和一般智能体.首先设计强连通子图中个体组成的单元智能体的一致性协议实现各个单元的一致;后由单元智能体和一般智能体构成新的拓扑结构,结合复杂网络可控性理论与二分图最大匹配算法确定满足网络可控的最少领导者集合,并为所有智能个体设计相应的控制协议,驱使跟随者渐近收敛到多个领导者组成的动态凸包中,从而实现网络的可控包含控制.仿真结果验证了理论分析的正确性.     

Target controllability of multiagent systems under fixed and switching topologies

In this article, the target controllability of multiagent systems under fixed and switching topologies is investigated, respectively. In the fixed topology setting, some necessary and/or sufficient algebraic and graph‐theoretic conditions are proposed, and the target controllable subspace is quantitatively studied by virtue of almost equitable graph vertex partitions. In the switching topology setting, based on the concepts of the invariant subspace and the target controllable state set, some necessary and sufficient algebraic conditions are obtained. Moreover, the target controllability is studied from the union graph perspective. The results show that when the union graph of all the possible topologies is target controllable, the multiagent system would be target controllable even if each of its subsystems is not. Numerical simulations are provided finally to verify the effectiveness of the theoretical results.     

多智能体系统能控性研究进展

能控性问题是多智能体协调控制领域中一个基本又十分重要的研究课题.本文对多智能体系统能控性问题的研究现状进行综述.介绍了多智能体能控性领域的基本问题和特点,并结合智能体自身动力学与邻居交互协议,从拓扑结构角度对该领域当前的研究热点和前沿进行分析阐述.进一步,对结构能控性的研究成果进行归纳总结,并对能观测性、可镇定性和复杂网络能控性等相关问题进行阐述.最后给出了仍需解决的问题和可能的研究方向.