IEEE Proceedings Paper on Concensus and Cooperative Control

Consensus and Cooperation in Multi-Agent Networked Systems

The availability of low cost, high bandwidth, wireless communications between independent computing systems has enabled new approaches to cooperation between multi-agent systems performing a common task. In situations where the tasks involve motion control or other non-trivial process dynamics, the overall stability and performance of the cooperative system is dependent on the interaction between the topology of the information flow between the agents (who talks to who) as well as the individual dynamics of the agents. In this paper we explore two representative problems---consensus and formation control---and their applications in control of networked, multi-vehicle systems performing cooperative tasks.

Consensus refers to the problem of a set of distributed computers agreeing on some common quantity. The simplest version of this problem, which we call average consensus, requires the agents to agree on the average value of a set of quantities that are known to each individual agent. In vehicle applications, this often must be done in the presence of varying information topology, for example when a collection of robots are trying to agree on the position of a sensed object while moving and changing the topology of their wireless network connections. We present a framework for studying the concensus problems that models the information flow using the graph Laplacian and gives a provably correct consensus protocol in the presence of switching topology and delays.

Using the same graph theoretic methods, we also consider the the problem of cooperation among a collection of vehicles performing a shared task using intervehicle communication to coordinate their actions. We provide a Nyquist-like criterion that uses the eigenvalues of the graph Laplacian matrix to determine the effect of the graph on formation stability. We also demonstrate how to use concensus to improve the performance of the system, by supplying each vehicle with a common reference to be used for cooperative motion. A separation principle that states that formation stability is achieved if the information flow is stable for the given graph and if the local controller stabilizes the vehicle. The information flow can be rendered highly robust to changes in the graph, thus enabling tight formation control despite limitations in intervehicle communication capability.

I. Introduction and Motivation

II. Basic Tools

III. Consensus

IV. Cooperation

V. Future Directions

--

Topics

1. Nyquist/Laplacian ] Fiedeler vectors -> decomposition 2. Consensus/balanced graphs ] of multi-agent groups 3. Switching (incl. Ali, Moreau) ] 4. Performance (lambda_2, feedfwd, etc) 5. Distributed information processing 6. Tools: graph theory, stochastic matrices, Lyapunov 7. Asynchronous consensus (Mesbahi) 8. Alignment in flocking (proximity graphs, post-induced graphs)

Annotated Bibliography

The references below represent a collection of papers that have been important in the development of results in consensus and cooperation combining ideas from dynamical systems, graph theory, and control. We focus on work that explicitly addresses the interaction between the dynamcis of the agents and the topological structure of the information flow.

The references are broken up roughly by different groups and represented in rough chronilogical order. We have grouped collections of conference and journal papers on the same subject together.

Vicsek et al, Flocking

• Vicsek, T. and Cziro\'{o}k, A. and Ben-Jacob, E. and Cohen, I. Shochet, O.

 Novel type of phase transition in a system of self-deriven particles,
 Physical Review Letters, 75(6):1226--1229, 1995.

This is widely cited in many areas. It only provides numerical simulations with no analytical results. However, it did start a great interest in understanding flocking behavior. A nonlinear alignment rule is simulated. The reasons behind the phase transition has to do with connectivity of Erdos-Renyi random graphs. Unfortunately, the authors miss this point and provide a different explaination for a phase transition pheonamenon that is later disputed by other physicists including Toner and Tu (1998). We do not need to state Vicsek's explanation for the phase transition phenomenon. We can only explain their protocol and model properly and briefly mention its connection with random networks.

Tabuada

• P. Tabuada, G. J. Pappas, and P. Lima.

 Feasible formations of multi-agent systems. In Proceedings of the American 
 Control Conference, pages 56Ð61, 2001.

Fax et al, Information Flow

• IFAC conference papers

• Fax, J. A. and Murray, R. M.

 Information flow and cooperative control of vehicle formations, The 
 IEEE Transactions on Automatic Control, 49(9):1465--1476, 2004.

Basic idea of Laplacian feedback, associated performance issues with Nyquist plot and eigenvalue placement based on spectral properties of Laplacian. Explicit modeling of information states and communication in feedback.

Olfati-Saber, Consensus

• Olfati-Saber, R. and Murray, R. M.

 Consensus protocols for networks of dynamic agents, Proc. of the 
 American Control Conference, 2003.

• Olfati-Saber, R. and Murray, R. M.

 Consensus problems in networks of agents with switching topology and 
 time-delays}", IEEE Transactions on Automatic Control, 49(9):1520--1533, 2004. 

Laplacian feedback for average consensus, notion of balanced graph; performance on unstructured graph quantified by lambda2 and robustness to time-delay and switching discussed. Use of distributed feedback for a computational purpose.

The 2003 ACC is the first paper that formally defines consensus problems for networked dynamic systems and poses a more general $\chi$-consensus problem. All nodes of the network reach an agreement regarding the value of $\chi(x_1,x_2,\ldots,x_n)$. This also the first paper to analyze both linear and nonlinear consensus algorithms that solve avergare-consensus problems. The consensus problems with time-delays are discusses without a need to use a Nyquist criterion. The spectrum of Laplacian has sufficient information regarding the speed of converegence and toleraance to time-delays. All analysis is for a \emph{fixed topology}.

The journal paper brings up the importance of sufficient and necessary condition for solvability of average-consensus problems. The network necessarily has to be a \emph{balanced graph}. This also allows extension of the role of $\lambda_2$ to digraphs. Performance issues for networks with switching topologies are covered in this paper. This amounts to macro-scale switching of $\Gamma_k$'s in \cite{Jadbabaie_Lin_Morse:2003}.

• R. Olfati-Saber

 Ultrafast Consensus on Small-World Networks, American Control Conference, 2005.

"Phase-transition" behavior in lambda2 under random re-wiring of network (a la steve strogatz).

This paper demonstrates that small-world networks that are quasi-random have incredibly high $\lambda_2$'s. For example, a Watts-Strogatz model with link random rewiring probability of $p=0.9$ and $n=1000$ nodes has a $lambda_2$ that is 1500 larger than a ring lattice with 1000 nodes and node degree $10$ (total of 5000 links in both). This is a new development in design of ultrafast networks.

Jadbabaie

• Jadbabaie, A. and Lin, J. and Morse, A. S.

 Coordination of groups of mobile agents using nearest neighbor rules, 
 IEEE Trans. on Automatic Control, 48(6):988--1001, 2003.

Convergence/alignment in mobile agents; essentially a special case of a consensus problem with topology induced by positions.

Paper \cite{Jadbabaie_Lin_Morse:2003} (read): This is the first paper that analyzes the case of alignment under switching topology with the property that connectivity of aggregate graphs $\Gamma_k$ (union of graphs) on intervals of length $T \gg \delta$ ($\delta$ is the integration step-size) is sufficient to guarantee convergence to some common value. No performance analysis is provided. The main tool is the use of Wolfovitz's lemma that is quite well-known in Ergodicity Theory. [Olfati]

Remark: The authors misrepresent the work of Viscek perhaps unknowingly. Viscek's paper implements a nonlinear consensus algorithm, whereas the entire analysis of Jadbabaie et al. is on switched linear systems. Furthermore, in Viscek's model the position of the agents plays an important role. In \cite{Jadbabaie_Lin_Morse:2003}, the agents only have a heading angle and no position. We need to find a politically correct way to clarify such issues without direct reference to inconsistencies. The best way is to explain Viscek's model properly as it is rather than point out the inconsistencies.

Moreau

• Moreau, Luc

 Leaderless coordination via bidirectional and unidirectional
 time-dependent communication.  IEEE Conference on Decision and Control, 
 2003

• Moreau, Luc (Sidmar)

 Stability of continuous-time distributed consensus
 algorithms IEEE Conference on Decision and Control, 2004

• Moreau, Luc

 Stability of multiagent systems with time-dependent
 communication links, IEEE Transactions on Automatic Control,
 50(2):169--182, 2005.

Convergence with time-delay under unidirectional interconnection with possibly asymmetric time-delays.

This paper provides a powerful tool for converegence analysis of linear \& nonlinear consensus protocols in presence of microscale switching and time-delays. The results are far more general than the ones in \cite{Jadbabaie_Lin_Morse:2003}. This analysis can also be used for convergence of asynchronuous consensus algorithms.

Olfati-Saber, Flocking

• Olfati-Saber, R.

 Flocking for Multi-Agent Dynamic Systems: Theory and
 Algorithms, IEEE TAC (accepted), 2005.
       

Paper \cite{Olfati:CDSTR04-005} (read): This paper provides flocking algorithms that heavily rely on velocity consensus algorithms for design of a dissipative particle systems that performs flocking behavior with analytical guarantees. The networks all are spatially induced and have a switching topology.

Mesbahi

• Y. Hatano and M. Mesbahi

 Agreement over random networks IEEE Conference
 on Decision and Control (CDC), 2004

• M. Mesbahi

 On state-dependent dynamic graphs and their controllability
 properties. IEEE Conference on Decision and Control (CDC), 2004

Consensus with stochastic topology switching, not necessarily all connected graphs in transient.

Xiao/Boyd

• L Xiao and S. Boyd

 Fast linear iterations for distributed averaging,
 Systems \& Control Letters, 52:65--78, 2004.

Optimizes lambda2 using SDP... recent results (infocom 05) allow this to be done in a distributed way using Kempe's algorithm for calculation of the Fiedler vector.

This paper uses the average-consensus framework in \cite{Olfati_Murray:ACC03a} combined by an LMI framework that solves the problem of optimization of weights of a network with a fixed set of links to maximize $\lambda_2$. This is a central algorithm that is not useful for networks but is good for designing Markov chain with slighter higher mixing rates. The gain in increase of $\lambda_2$ is moderate (2 or so).

Ren and Beard et al

• Wei Ren, Randal W. Beard

 "Consensus Seeking in Multi-agent Systems Using
 Dynamically Changing Interaction Topologies," IEEE Transactions on
 Automatic Control, (to appear)

• Wei Ren, Randal W. Beard, Timothy W. McLain

 "Coordination Variables and
 Consensus Building in Multiple Vehicle Systems, Block Island Workshop on
 Cooperative Control, Editors Vijay Kumar, Naomi Leonard, A. Stephen Morse,
 Lecture Notes in Control and Information Systems, vol. 309,
 Springer-Verlag, p. 171--188, 2004.

Leonard

Cooperative control based on distributed gradient computations.

Spanos

Consensus tracking with network reconfiguration, split/rejoin and robustness to arbitrary time-delay w/ small gain thm. (note: all bidirectional)

Spanos, Olfati-Saber, Murray IPSN '05 (read): This paper provides a promising direction for application of consensus algorithms in distributed Kalman filtering and sensor fusion. This is what I meant by collaborative information processing.

Tsitsiklis et al.

Application of parallel/distributed computing techniques to analyze convergence in general asynchronous setting (no specification of computing a particular quantity, e.g. average).

Actions

1. Assemble bibliography

 * Send papers to Richard by Mon, 5 pm
 * Post to wiki (Demetri)

2. Pick subset to cover ] Meet in ~2 weeks 3. Common notation/language ] 18 Apr 4. Common problems ]

5. List tools ] Meet in ~2 weeks 6. Diversions/open problems ] 6 May 7. Outline ]

8. Write ] Finish by 6/15/05

Compelling benchmark problem

 * perhaps something that might be mobile sensor network