Coordination of groups of mobile autonomous agents using nearest neighbor rules

In a recent Physical Review Letters article, Vicsek and his colleagues propose a simple but compelling discrete-time model of n autonomous agents all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its neighbors. This paper provides a theoretical explanation for the behavior of the Vicsek model. Using tools from algebraic graph theory and the theory of non-homogeneous Markov chains, we show that all agents converge to a common heading as long as the union of the directed neighbor graphs across any contiguous, bounded time interval is jointly connected.