Agreeing Asynchronously

Abstract

This paper formulates and solves a version of the widely studied Vicsek consensus problem in which each member of a group ofn> 1 agents independently updates its heading at times determined by its own clock. It is not assumed that the agents' clocks are synchronized or that the ldquoeventrdquo times between which any one agent updates its heading are evenly spaced. Nor is it assumed that heading updates must occur instantaneously. Using the concept of ldquoanalytic synchronizationrdquo together with several key results concerned with properties of ldquocompositionsrdquo of directed graphs, it is shown that the conditions under which a consensus is achieved are essentially the same as those applicable in the synchronous case provided the notion of an agent's neighbor between its event times is appropriately defined. However, in sharp contrast with the synchronous case where for analysis anndimensional state space model is adequate, for the asynchronous version of the problem a 2n-dimensional state space model is required. It is explained how to analyze this model despite the fact that, unlike the synchronous case, the stochastic matrices involved do not have all positive diagonal entries.