We study two recent consensus problems in multi-agent coordination with linear dynamics. In Saber and Murray an agreement problem was studied with linear continuous-time state equations and a sufficient condition was given for the given protocol to solve the agreement problem; namely that the underlying graph is strongly connected.We give sufficient and necessary conditions which include graphs that are not strongly connected. In addition, Saber and Murray show that the protocol solves the average consensus problem if and only if the graph is strongly connected and balanced. We show how multi-rate integrators can solve the average consensus problem even if the graph is not balanced. We give lower bounds on the rate of convergence of these systems which are related to the coupling topology. Saber and Murray also considered the case where the coupling topology changes with time but remain a balanced graph at all times. We relate this case of switching topology to synchronization of nonlinear dynamical systems with time-varying coupling and give conditions for solving the consensus problem even when the graphs are not balanced.
Jadbabaie et al. study a model of leaderless and follow-the-leader coordination of autonomous agents using a discrete-time model with time-varying linear dynamics and show coordination if the underlying undirected graph is connected across intervals. Mureau extended this to directed graphs which are strongly connected across intervals. We prove that coordination is possible even if the graph is not strongly connected by utilizing recent results on the weak ergodicity of inhomogeneous Markov chains.
By: Chai Wah Wu
Published in: RC23582 in 2005
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .