Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules

2 min read

Jadbabaie, Lin and Morse prove why the Vicsek flocking model works. In that model every agent moves at the same speed and, at each step, sets its heading to the average of its own heading and those of the agents within a fixed radius. Simulations had shown the group ends up moving in one direction even though neighbourhoods change all the time. The paper drops the geometry and treats the neighbour graph as an arbitrary switching signal, so each step multiplies the heading vector by a stochastic matrix, and uses Wolfowitz’s theorem on infinite products of ergodic matrices to prove convergence. The model is also a switched linear system that is stable although no common quadratic Lyapunov function exists.

Findings

  • Theorem 1: if the neighbour graph is connected at every step, all headings converge to a common value.
  • Theorem 2 (the main result): the graph need not ever be connected. It is enough that there is an infinite sequence of contiguous, bounded time intervals across each of which the union of the graphs is connected (“jointly connected”).
  • The same holds for a leader-follower version: if followers are linked to a leader with a fixed heading often enough, all follower headings converge to the leader’s.
  • An alternative update written with graph Laplacians, and a continuous-time leader-follower model, are also analysed.

Limits

  • The analysis ignores how the switching depends on positions; the authors say a full account of flocking needs the coupled motion and graph dynamics. With small sensing radius and spread-out agents they expect the group to split into subgroups with different headings.
  • Noise, which is part of the original Vicsek model, is ignored, as are collision avoidance, sensing errors and vehicle models.
  • They wanted the result for non-contiguous intervals and leave it open.
  • Every agent follows the rule honestly. One agent that reports a fixed false heading acts exactly like the leader in their leader-follower result and drags everyone to its value.

Relevance

Plain averaging gives agreement under intermittent connectivity, with no defence at all. The last limit is where resilient consensus (W-MSR and robust graphs) takes over, and the mean’s breakdown point of zero is a problem for multi-robot systems and aerial swarms. Related to the topic of the buoy formation paper.