Outdoor cooperative flight using decentralized consensus algorithm and a guaranteed real-time communication protocol

This paper describes the implementation of a decentralized consensus law with theoretically provable convergence properties on a multi-agent testbed comprising of quadrotors. It is shown that for small roll and pitch angles and well-tuned control loops, the quadrotor dynamics can be approximated as a pair of double integrators. Several experiments are carried out in an outdoor environment for validation of the consensus law which is based on double integrator dynamics. For any arbitrary initial positions of the quadrotors, the consensus law is able to drive them to an autonomously decided common point, given that the communication graph is connected at each instant of time. The resulting experimental trajectories and the consensus point matches with theoretical predictions. For guaranteeing real-time reliability required for such coordinated motion, a novel synchronized, time-slotted, scalable and fully airborne communication protocol is proposed. The protocol avoids data collisions and ensures real-time, reliable communication between agents. It can also address changing communication graph topologies, temporary link-breaks and additions. Using this underlying protocol, the quadrotors attain consensus for static and dynamic communication graphs. Experiments to observe the effect of communication rate on consensus performance are also conducted.     

dBCube: a new class of hierarchical multiprocessor interconnectionnetworks with area efficient layout

Introduces a class of hierarchical networks that is suitable for implementation of large multi-computers in VLSI with wafer scale integration (VLSI/WSI) technology. These networks, which are termed dBCube, employ the hypercube topology as a basic cluster, connect many of these clusters using a de Bruijn graph, and maintain the node connectivity to be the same for all nodes product graph. The size of this class of regular networks can be easily extended by increments of a cluster size. Local communication, to be satisfied by the hypercube topology, allows easy embedding of existing parallel algorithms, while the de Bruijn graph, which was chosen for JPL's 8096-node multiprocessor, provides the shortest distance between clusters running different parts of an application. A scheme for obtaining WSI layout is introduced and used to estimate the number of tracks needed and the required area of the wafer. The exact number of tracks in the hypercube and an approximation for the de Bruijn graph are also obtained. Tradeoffs of area versus static parameters and the size of the hypercube versus that of the de Bruijn graph are also discussed     

Fault-tolerant de Bruijn and shuffle-exchange networks

This paper addresses the problem of creating a fault-tolerant interconnection network for a parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m de Bruijn graph, and the shuffle-exchange, are studied. For each topology an N+k node fault-tolerant graph is defined. These fault-tolerant graphs have the property that given any set of k node faults, the remaining N nodes contain the desired topology as a subgraph. All of the constructions given are the best known in terms of the degree of the fault-tolerant graph. We also investigate the use of buses to reduce the degrees of the fault-tolerant graphs still further     

Consensus seeking over directed networks with limited information communication

Existing works that deal with the problem of distributed average consensus with quantized information communication assume that the update matrices are doubly stochastic, which amounts to agents evolving on balanced directed networks with digital channels. This paper is concerned with the problem of seeking consensus via quantized information communication over a general unbalanced directed digital network. It is established that, by designing a protocol with a finite-level uniform quantization scheme, merely one bit quantized information transmitted along each connected digital channel suffices for achieving weighted average consensus with an exponential convergence rate, as long as the directed unbalanced network is strongly connected. An explicit characterization of the convergence rate of consensus is also given. By avoiding the double stochasticity assumption on the update matrix, the proposed quantized protocol is particularly suitable for the scenarios where no bidirectional and/or balanced information communication among agents is available.     

Self-emergence of a common lexicon by evolution in teams of autonomous agents

In multi-agent systems, the study of language and communication is an active field of research. In this paper we present the application of evolutionary strategies to the self-emergence of a common lexicon in a population of agents. By modeling the vocabulary or lexicon of each agent as an association matrix or look-up table that maps the meanings (i.e. the objects encountered by the agents or the states of the environment itself) into symbols or signals we check whether it is possible for the population to converge in an autonomous, decentralized way to a common lexicon, so that the communication efficiency of the entire population is optimal. We have conducted several experiments aimed at testing whether it is possible to converge with evolutionary strategies to an optimal Saussurean communication system. We have organized our experiments alongside two main lines: first, we have investigated the effect of the population size on the convergence results. Second, and foremost, we have also investigated the effect of the lexicon size on the convergence results. To analyze the convergence of the population of agents we have defined the population's consensus when all the agents (i.e. 100% of the population) share the same association matrix or lexicon. As a general conclusion we have shown that evolutionary strategies are powerful enough optimizers to guarantee the convergence to lexicon consensus in a population of autonomous agents.     

Cooperative tracking control for general linear multiagent systems with directed intermittent communications: An artificial delay approach

This paper investigates the consensus tracking problem for general linear multiagent systems on directed graph containing a spanning tree. For the considered linear systems, the consensus tracking aim cannot be achieved by using only memoryless static relative output feedbacks. Of particular interest is that both current and delayed relative output information of agents are required to achieve consensus. For the case of continuous communication among agents, an artificial delay output feedback control method is proposed. By utilizing the Taylor representation for the delayed signal with the remainder in the integral form, a delay‐dependent sufficient condition is presented to guarantee the exponential convergence of the global tracking error systems. For the intermittent case, the consensus tracking performance can still be guaranteed based on a multiple graph‐dependent Lyapunov functionals method. It is theoretically revealed that the time delay plays a key role in the exponential convergence of the closed‐loop systems, and the definite relationships among the time delay, network structure, communication rate, and consensus convergence rate are also provided. The effectiveness of the proposed control scheme is confirmed by numerical simulations.     

Stationary average consensus protocol for a class of heterogeneous high-order multi-agent systems with application for aircraft

This paper investigates the stationary average consensus problem for a class of heterogeneous-order multi-agent systems. The goal is to bring the positions of agents to the average of their initial positions while letting the other states converge to zero. To this end, three different consensus protocols are proposed. First, based on the auxiliary variables information among the agents under switching directed networks and state-feedback control, a protocol is proposed whereby all the agents achieve stationary average consensus. In the second and third protocols, by resorting to only measurements of relative positions of neighbouring agents under fixed balanced directed networks, two control frameworks are presented with two strategies based on state-feedback and output-feedback control. Finally, simulation results are given to illustrate the effectiveness of the proposed protocols.     

组合连通拓扑下基于事件触发的多智能体快速一致性算法

针对组合连通拓扑下多智能体系统控制过程中存在通信和计算资源损耗大以及系统收敛速度慢等问题,提出一种新的具有状态预测器的事件触发一致性控制协议,通过设计状态预测器使每个智能体都能对其邻居智能体的未来状态作出预测;同时,对于智能个体给出了基于状态信息的事件触发条件,当状态误差满足该条件才触发事件.在该控制策略下多智能体系统可在节约通信和计算资源的同时具有更快的收敛速度.利用Lyapunov稳定性理论和代数图论,证明了所提事件触发控制策略能够有效实现组合连通拓扑结构下的平均一致性,且不存在Zeno行为.仿真实例进一步验证了理论结果的有效性.     

Consensus strategy for a class of multi‐agents with discrete second‐order dynamics

This paper investigates consensus strategies for a group of agents with discrete second‐order dynamics under directed communication topology. Consensus analysis for both the fixed topology and time‐varying topology cases is systematically performed by employing a novel graph theoretic methodology as well as the classical nonnegative matrix theory. Furthermore, it is shown that the necessary and sufficient condition for the agents under fixed communication topology to reach consensus is that the communication topology has a spanning tree; and sufficient conditions for the agents to reach consensus when allowing for the dynamically changing communication topologies are also given. Finally, an illustrative example is provided to demonstrate the effectiveness of the proposed results. Copyright © 2011 John Wiley & Sons, Ltd.     

Distributed consensus of discrete‐time multi‐agent systems with multiplicative noises

In this paper, we consider the consensus problem of discrete‐time multi‐agent systems with multiplicative communication noises. Each agent can only receive information corrupted by noises from its neighbors and/or a reference node. The intensities of these noises are dependent on the relative states of agents. Under some mild assumptions of the noises and the structure of network, consensus is analyzed under a fixed topology, dynamically switching topologies and randomly switching topologies, respectively. By combining algebraic graph theory and martingale convergence theorem, sufficient conditions for mean square and almost sure consensus are given. Further, when the consensus is achieved without a reference, it is shown that the consensus point is a random variable with its expectation being the average of the initial states of the agents and its variance being bounded. If the multi‐agent system has access to the state of the reference, the state of each agent can asymptotically converge to the reference. Numerical examples are given to illustrate the effectiveness of our results. Copyright © 2014 John Wiley & Sons, Ltd.     

Distributed δ-consensus in directed delayed networks of multi-agent systems

In this article, we propose a distributed δ-consensus protocol in directed networks of dynamic agents having communication delays. The δ-consensus protocol is an average consensus protocol where agents exchange the information with their neighbours at some discontinuous moments. We provide convergence analysis for such consensus algorithm under stochastic switching communication graphs, and then present some generic criteria for solving the average consensus problem. We also show that directed delayed networks of dynamic agents can achieve average consensus even when each agent in the networks intermittently exchanges the information with its neighbours only at some discrete moments. Subsequently, a typical numerical example illustrates and visualises the effectiveness and feasibility of the theoretical results.     

Sufficient conditions for the convergence of a class of nonlinear distributed consensus algorithms

This paper is concerned with the convergence of a class of continuous-time nonlinear consensus algorithms for single integrator agents. In the consensus algorithms studied here, the control input of each agent is assumed to be a state-dependent combination of the relative positions of its neighbors in the information flow graph. Using a novel approach based on the smallest order of the nonzero derivative, it is shown that under some mild conditions the convex hull of the agents has a contracting property. A set-valued LaSalle-like approach is subsequently employed to show the convergence of the agents to a common point. The results are shown to be more general than the ones reported in the literature in some cases. An illustrative example demonstrates how the proposed convergence conditions can be verified.     

Finite-time consensus for multi-agent systems with globally bounded convergence time under directed communication graphs

In this paper, we study the finite-time consensus problems with globally bounded convergence time also known as fixed-time consensus problems for multi-agent systems subject to directed communication graphs. Two new distributed control strategies are proposed such that leaderless and leader-follower consensus are achieved with convergence time independent on the initial conditions of the agents. Fixed-time formation generation and formation tracking problems are also solved as the generalizations. Simulation examples are provided to demonstrate the performance of the new controllers.     

Design and Analysis of a Class of Highly Scalable Hierarchical Networks: PdBCube

A class of hierarchical networks called the dBCube, that provides cost-effective and high-performance communication in large multicomputer systems, has recently been introduced. Such a compound graph of a hypercube and a de Bruijn (dB) graph utilizes every node of the hypercube as a gateway for intercluster communication. This paper presents a partially connected dBCube subclass (PdBCube), wherein the use of fewer nodes as gateways makes the PdBCube highly scalable in terms of both the hypercube and the dB size. This enhancement in scalability can be achieved by two different approaches to assigning gateways. Performance degradation of the proposed PdBCube is illustrated in terms of diameter and average distance. Improvement in track efficiency and reduction in cost are observed to be directly related to a decrease in the number of remote links.     

多智能体沿多条给定路径编队运动的有向协同控制

研究了在有向通信连接下二阶积分器描述的多智能体沿多条给定路径编队运动的控制器设计及其稳定性分析问题. 智能体的动态和指定路径都是在固定直角坐标系下描述的. 通过引入路径函数来设计路径跟踪控制, 根据路径函数与弧长的关系来设计编队控制律, 使得多智能体沿期望路径的位置和速度在规定队形下达到一致. 利用图论证明, 当通信拓扑对应的有向图具有全局可达点时, 设计的编队控制系统是渐近稳定的. 本文设计的有向协同控制律可以应用于区域的信息优化采集.     

对抗网络下时滞非线性多智能体系统固定时间二分一致性

本文针对一类存在输入时延的非线性多智能体系统,研究了其在结构平衡的无向符号图下的固定时间二分一致性问题.首先,本文针对智能体间相互合作与相互竞争的关系,设计了一类存在输入时延的多智能体系统固定时间分布式一致性控制协议,使得系统状态在固定时间内收敛到数值相同但符号相反的两个值,且收敛时间上界与初始状态无关.随后,利用Lyapunov稳定性理论和代数图论给出了在存在输入时延的情况下多智能体系统实现固定时间二分一致性的充分条件和收敛时间的上界值,证明了控制算法的稳定性.最后,仿真实例验证了所提固定时间二分一致性算法和理论结果的有效性.     

Average Convergence for Directed & Undirected Graphs in Distributed Systems

Consensus control of multi-agent systems is an innovative paradigm for the development of intelligent distributed systems. This has fascinated numerous scientific groups for their promising applications as they have the freedom to achieve their local and global goals and make their own decisions. Network communication topologies based on graph and matrix theory are widely used in a various real-time applications ranging from software agents to robotics. Therefore, while sustaining the significance of both directed and undirected graphs, this research emphases on the demonstration of a distributed average consensus algorithm. It uses the harmonic mean in the domain of multi-agent systems with directed and undirected graphs under static topologies based on a control input scheme. The proposed agreement protocol focuses on achieving a constant consensus on directional and undirected graphs using the exchange of information between neighbors to update their status values and to be able to calculate the total number of agents that contribute to the communication network at the same time. The proposed method is implemented for the identical networks that are considered under the directional and non-directional communication links. Two different scenarios are simulated and it is concluded that the undirected approach has an advantage over directed graph communication in terms of processing time and the total number of iterations required to achieve convergence. The same network parameters are introduced for both orientations of the communication graphs. In addition, the results of the simulation and the calculation of various matrices are provided at the end to validate the effectiveness of the proposed algorithm to achieve consensus.     

Performance metrics in the average consensus problem: A tutorial

The average consensus algorithm is a distributed procedure which allows a network of agents to agree on the average of a set of initial values. The computation occurs through local exchange of information only, namely the information exchange takes place only between agents which are neighbors with respect to a graph representing the system communication architecture. Several performance metrics have been proposed for the evaluation of this algorithm. Particularly interesting and challenging is to relate them to the communication topology. Different performance metrics may yield different answers in comparing alternative communication topologies. In this paper, we present a few performance metrics and we show how these metrics are related to the communication topology. In particular, when available, we present bounds which permit to relate performance and topology for general graphs, for graphs with symmetries, called d-dimensional tori, and for geometric graphs.     

Stability and convergence analysis of multi-agent consensus with information reuse

In this article, we study multi-agent consensus algorithms with information reuse by intentionally introducing the outdated state information into the traditional consensus algorithms. In the continuous-time case, we first show that the outdated state information combined with the current state information does not necessarily jeopardise the stability of a single system, but may improve the convergence speed without increasing the maximal control effort. Then this idea is extended from the single-agent case to the multi-agent case. When the directed communication graph is fixed, the corresponding Laplacian matrix and the outdated state information satisfy certain conditions, we show that the consensus algorithm with both the current and outdated states can achieve a faster convergence speed than the standard one. We also consider the case of a switching directed communication graph and derive corresponding conditions. In the discrete-time case, we propose a discrete-time consensus algorithm with both the current and outdated states under an undirected fixed communication graph. We then derive conditions on the communication graph, the sampling period and the outdated state information such that the proposed algorithm can achieve a faster convergence speed than that using the standard one. In both the continuous-time and discrete-time settings, we show that the maximum control efforts for the proposed consensus algorithms are identical to those for the standard ones. Several simulation examples are presented as a proof of concept.     

Mean square average-consensus under measurement noises and fixed topologies: Necessary and sufficient conditions

In this paper, average-consensus control is considered for networks of continuous-time integrator agents under fixed and directed topologies. The control input of each agent can only use its local state and the states of its neighbors corrupted by white noises. To attenuate the measurement noises, time-varying consensus gains are introduced in the consensus protocol. By combining the tools of algebraic graph theory and stochastic analysis, the convergence of these kinds of protocols is analyzed. Firstly, for noise-free cases, necessary and sufficient conditions are given on the network topology and consensus gains to achieve average-consensus. Secondly, for the cases with measurement noises, necessary and sufficient conditions are given on the consensus gains to achieve asymptotic unbiased mean square average-consensus. It is shown that under the protocol designed, all agents’ states converge to a common Gaussian random variable, whose mathematical expectation is just the average of the initial states.