Birds, fish, and many other animals move in groups without a leader: each one only reacts to the neighbors around it. The Vicsek model captures this with simple particles that turn toward the average heading of everyone within a radius, plus some noise. My bachelor thesis asked two questions: does a swarm still form when each particle reads only k randomly drawn neighbors, and can the rule be learned with multi-agent reinforcement learning instead of written by hand?

Sample your neighbors

A fixed number of neighbors is what real flocks seem to track, and it is what a neural network needs as input. But the purely topological rule, the k nearest agents, fails here: in dense spots the nearest agents are all very close, so the interaction becomes short-ranged and the swarm falls apart into tiny packets.

The rule I introduced keeps the radius, then draws k neighbors at random from everyone inside it, anew for every agent at every step. The sampled mean of the headings’ sine and cosine is an unbiased Monte Carlo estimate of the mean over the whole neighborhood, with k as the sample size.

  • ScopeThe uniformly subsampled Cartesian alignment mean is a Monte Carlo estimator of the full Vicsek alignment vector; the final normalized angular update is not claimed to be unbiased. Estimator statement applies to the Cartesian mean only.
The same neighborhood under three rules: the metric rule links everyone inside the radius, the topological rule spends its four links on one tight cluster, and the metric-topological rule draws four at random from inside the radius

Why random draws work

Seen from one agent, its neighborhood is a histogram of headings. With room for only k inputs, a sensible compression splits it into k regions that hold equally many agents and averages each one. Computing those regions at every step is expensive; random draws get the same effect statistically, because over many steps they hit every region equally often.

A radial histogram of the headings one agent sees, and the same histogram split into eight regions that each hold the same number of agents
Conceptual, on synthetic data.

Streams instead of fragments

Under the topological rule the swarm stays scattered in small packets. Under the sampled rule, although every agent reads only k neighbors per step, the swarm forms large, stream-like structures that resemble the metric Vicsek reference.

One difference remains: for small k, the sharp, vortex-like turns of the Vicsek model are smoothed out, because an agent cannot take in every direction in a single step.

Snapshots of the three rules at three noise levels: the topological rows break into small packets, while the sampled rule forms large streams like the metric Vicsek reference
N = 400 agents at density 4, after a few simulation steps; k applies to the upper two rows.

Converging to the Vicsek model

With every candidate kept, the rule is exactly the Vicsek model, so it has to converge as k grows; the Monte Carlo view predicts that it does so fast. The order parameter, a measure of how aligned the whole swarm is, confirms it: the deviation from the Vicsek reference shrinks quickly with k and is barely visible at k = 6.

Order parameter versus noise for k = 1 to 6 and four system sizes; the shaded deviation from the Vicsek reference shrinks as k grows and is barely visible at k = 6

How fast

The mean squared deviation condenses each curve into one number per system size. Larger systems converge a little more slowly at the same density.

  • ResultFrom k = 1 to k = 6, the mean squared deviation of the order parameter from the metric Vicsek reference falls by more than an order of magnitude, roughly as a power law in k (fitted log-log slopes between −1.55 and −1.93); at k = 6 the two models are practically indistinguishable in this observable. The alignment order parameter as a function of noise, at density 4, for system sizes up to N = 1600. No claim of general equivalence.
Mean squared deviation from the Vicsek reference versus k for four system sizes, falling steeply, and the same data on log-log axes with a linear fit per system size
Right: log-log fits (“Steigung” is German for slope).

Learning the rule instead

The second part turned the question around: instead of writing a local rule, define a global goal and let the agents learn how to reach it. The order parameter is a natural reward, and the fixed k of the sampled rule gives every agent an observation of constant size.

The C++ simulation became a learning environment: each agent observes the headings of its k sampled neighbors, acts by choosing a new heading, and is rewarded by the change in the order parameter.

Diagram of the multi-agent reinforcement-learning setup, labelled in German: agents take actions in an environment, and observations and rewards flow back to actor and critic networks
As drawn for the thesis, in German: Agenten are the agents, Aktionen their actions, Umgebung the environment, Beobachtungen observations, Belohnung the reward.

Choosing an algorithm

A heading is a continuous action, which narrows the choice to methods such as DDPG, TD3, PPO, or SAC. The thesis used DDPG, an actor–critic method, with TF-Agents: an actor proposes the action, and a critic estimates how good it is.

Venn diagram of reinforcement-learning algorithm families, labelled in German: value-based methods (DQN, C51), policy-based and policy-gradient methods (REINFORCE), and the actor-critic methods DDPG, PPO, TD3 and SAC where they overlap
From the thesis, in German: value-based methods on the left, policy-based on the right, actor-critic where they overlap.

The networks

The actor was kept minimal, a single dense layer, because the target behavior, the Vicsek average, is itself a simple function of the neighbors’ headings. The critic, shown here, takes the observation and the action and returns one value. A second attempt used one agent per particle with a shared policy in RLlib.

The critic network: the observation and the action each pass through dense layers, merge, and end in a single Q-value

What came out of it

The pipeline ran end to end and training proceeded, but no interpretable policy came out of it. The main suspect is the angle: a heading wraps around at 2π, and as a plain number it jumps there, a discontinuity the small networks did not overcome in the time available. The RLlib attempt failed earlier, at training launch.

The natural next experiment: encode the heading as its sine and cosine, and test whether a single-layer network can learn the averaging rule.

  • Negative resultThe actor–critic multi-agent RL pipeline ran end to end, but training a policy that reproduces flocking remained unsuccessful.

Context

Primary references

  1. Vicsek et al. (1995): Novel type of phase transition in a system of self-driven particles
  2. Ballerini et al. (2008): Interaction ruling animal collective behavior depends on topological rather than metric distance
  3. Chaté et al. (2008): Collective motion of self-propelled particles interacting without cohesion
  4. Lowe et al. (2017): Multi-agent actor–critic for mixed cooperative-competitive environments

Novelty scope: The contribution is the random-sampling neighbor rule and the finding that a small random sample reproduces the alignment behavior of the full rule. Vicsek alignment itself is established, and the precise statement about the estimator is registered with its scope. The reinforcement-learning extension is reported exactly as it ended: an unsuccessful training attempt.