Motivation
In this post, we will explore simple mathematical models that explain how collective motion can emerge in groups of self-propelled agents. It is remarkable that schools of fish, flocks of birds, and even human crowds or bacterial colonies are able to move in a coordinated way without any central control. Similar large-scale patterns also appear in non-biological systems, such as vehicular traffic and turbulent flows. What these systems have in common is that they are fundamentally out of equilibrium: each individual continuously consumes energy to move, and the group never settles into a static equilibrium state as in traditional thermodynamic systems. Yet, despite the noise, variability, and lack of centralized communication, coherent collective motion still emerges. A major breakthrough in understanding this phenomenon came from Vicsek et al. (1995), who introduced a minimal model showing that simple, local alignment rules are sufficient to produce global order. Their work sparked an entire field of research into active matter and collective behavior.
Overview of Vicsek Method
The Vicsek model proposes the simulation of N particles in a square arena with side length L. The particles are represented by points that continously are moving on the screen. There are three simple initial conditions that are employed:
- At time t = 0, N particles are randomly distributed in the arena
- The particles all have the same absolute velocity, v
- The particles all have randomly distributed orientation
At each time step, the velocities of the particles are determined (the magnitude is always the same but orientation is recalculated). The position of particle i is updated according to: ____ where the velocity of a particle ___ has a magnitude given by absolute value v and direction given by ____. To compute the average direction, a radius around each particle i is chosen and the average direction of all particles in the radius (including the particle i) is taken using ___. Finally, to measure the global order of the system, the absolute value of the average normalized velocity is computed at every time step. The closer to 0 the value is, the more disorderly the system, and the closer to 1 the value is, the greater the presence of a global order and indicates that the group is exhibiting a collective motion in a similar direction.
Computational Efficiency
Given that at every timestep, we need to compute the nearest neighbors for each particle to see if they are within the radius, this problem scales as an O( N^2) problem. We can look to the field of molecular dynamics as this is a problem that is often encountered there for which there is a solution in the cell lists or neighbor lists algorithm. With this algorithm, we discretize the arena into individual cells and go through the particles once and bin them into the appropriate cells. Then, when looking for nearest neighbors to our particle i, we can simply look at the 8 adjacent cells in 2D to check for the presence of neighbor particles whom to include for the average orientation calculation. This reduces the complexity of the algorithm to O(N). In order to avoid reimplementing this algorithm from scratch, I have used the implementation given by https://github.com/jaantollander/cell_lists. The below supplied image is also provided from the same page and gives a good illustration of the discretization of the arena into smaller cells and the incorporation of a cutoff radius to include nearest neighbors.
