In Vicsek model, all agents will eventually move in the same direction

You need to know: Basic geometry (distance in the plane, vector addition), limits, connected graph.

Background: Consider n autonomous agents (points) which are moving in the plane with the same speed but with different directions. Fix constant . The agents are called neighbours at time t if the distance between them is at most r. At discrete time moments each agent’s direction is updated and become the average of its own direction and the directions of its neighbours. At any time moment t, let be a graph with vertices being agents, in which neighbours connected by edges.

The Theorem: On 4th March 2002, Ali Jadbabaie, Jie Lin, and Stephen Moore submitted to IEEE Transactions on Automatic Control a paper in which they proved the following result. Assume that, in the model described above, there exists an infinite sequence of continuous, non-empty, bounded, non-intersecting time-intervals , , starting at , in which graph is connected. Then in the limit all agents will eventually move in the same direction.

Short context: Coordination of groups of mobile autonomous agents in an important topic which attracted a lot of attention in the literature. It has applications in physics (e.g. the study of active matter), machine learning, etc. In 1995, Vicsek, Czirok, Ben Jacob, Cohen, and Schochet suggested the model described above, and performed a number of numerical simulations demonstrating that, after some time, the agents start moving in the same direction, despite the absence of central coordination. The Theorem provides a theoretical explanation for this observation.

Links: The original paper is available here.

Go to the list of all theorems