Reaching a consensus in a dynamically changing environment { a graphical approach

This paper uses recently established properties of compositions of directed graphs together with results from the theory of non-homogeneous Markov chains to derive worst case conver-gence rates for the headings of a group of mobile autonomous agents which arise in connection with the widely studied Vicsek consensus problem. The paper also uses graph theoretic con-structions to solve modi¯ed versions of the Vicsek problem in which there are measurement delays, asynchronous events, or a group leader. In all three cases the conditions under which consensus is achieved prove to be almost the same as the conditions under which consensus is achieved in the synchronous, delay-free, leaderless case.