Flocking and Distributed Consensus

"Nobody told me which way to fly. I just kept turning until my neighbors and I were all turning the same way, and somehow that counted as a plan."

A Boid That Never Met Its Flock's Center

Collective motion is the most studied behavior in swarm intelligence because it is visible, ubiquitous, and stubbornly leaderless. Starlings wheel in murmurations of thousands; fish schools turn as a sheet; locust bands march in a shared direction across kilometers. In none of these systems is there a commander broadcasting a heading. Each individual senses only a handful of close neighbors and reacts to them. The earlier sections of this chapter built coordination out of stigmergy and optimization over a search space; here the coordinated object is the group's own motion, and the coupling between agents is direct: each one watches what its neighbors are doing and adjusts. The surprise, made precise below, is that purely local adjustment is enough to reach a global agreement on where to go.

1. Reynolds' Three Rules Beginner

In 1987 Craig Reynolds modeled flocking with simulated agents he called boids. Each boid carries a position and a velocity and senses other boids within a fixed radius, its local neighborhood. On every time step it computes a steering adjustment from three rules, each a function only of those neighbors. Separation steers away from neighbors that are too close, so the flock does not collapse into a point. Alignment steers toward the average heading of neighbors, so members travel in a common direction. Cohesion steers toward the average position of neighbors, so the flock stays together. There is no leader, no shared map, and no global broadcast; the only inputs are the relative positions and velocities of nearby agents. Figure 31.5.1 names the three rules and shows the geometry of each.

Each rule produces a small steering vector; the boid adds a weighted combination of the three to its velocity, caps the speed, and moves. That is the entire algorithm. The realism of the resulting motion, flocks that split around obstacles and rejoin, that turn coherently, that never need a choreographer, is what made boids a landmark in both computer graphics and the study of self-organization. We give the most consequential of the three rules, alignment, a precise distributed-systems reading next.

2. Alignment Is Average Consensus Intermediate

Strip flocking down to the alignment rule alone and write each agent's state as a heading or velocity vector $v_i$. The alignment update replaces $v_i$ with a step toward the average heading of the neighbors $\mathcal{N}_i$ that agent $i$ currently senses,

which, stacking all agents and writing $L$ for the graph Laplacian of the interaction graph, is precisely the discrete-time average-consensus protocol

This is the same iteration analyzed in Chapter 29: if the interaction graph is connected and $\varepsilon$ is small enough, every agent's heading converges to the common average $\bar v = \frac{1}{N}\sum_i v_i(0)$, and the speed of that convergence is governed by the second-smallest eigenvalue of $L$, the algebraic connectivity or spectral gap $\lambda_2$. A well-knit flock (a graph with a large spectral gap) aligns fast; a stringy, weakly connected flock aligns slowly or, if the graph disconnects, splits into sub-flocks that each agree internally but not with one another. The very same eigenvalue sets the rate at which gossip averaging spreads a value across a decentralized network in Chapter 14; flocking and decentralized learning are running the same protocol on different state.

The last sentence is worth unpacking, because it shows the same machinery covering several coordination tasks. In rendezvous, agents must agree on a single meeting point; that is consensus on position, $p_i \leftarrow p_i + \varepsilon(\text{avg neighbor position} - p_i)$, which is exactly the cohesion rule run to convergence and drives all agents to their common centroid. In formation control, each agent $i$ wants to sit at a fixed offset $\delta_i$ relative to the group; running consensus on the shifted variable $p_i - \delta_i$ makes the differences $p_i - p_j$ converge to the desired $\delta_i - \delta_j$, so the group settles into the target shape (a line, a wedge, a grid) with no agent ever knowing the global frame. Heading consensus, rendezvous, and formation control are three boundary conditions on one protocol.

3. Why Local Rules Give Global Motion Intermediate

Nothing in a boid's update references the global state, yet a global property (a single shared heading) appears. The mechanism is exactly the consensus argument: local averaging is contractive toward agreement, and connectivity propagates each agent's influence to every other agent over a few rounds even though no agent ever talks to a distant one directly. Influence travels along edges of the interaction graph the way a value diffuses through a gossip network. This is why the single most important precondition for a coherent flock is the same as the precondition for consensus convergence: the interaction graph must stay connected. If cohesion is too weak relative to the agents' speed, neighbors drift out of sensing range, the graph fragments, and the flock breaks into pieces that no longer share a heading. Cohesion is not decoration; it is what preserves the connectivity that alignment needs.

The demonstration below makes the emergence visible and measurable. It implements boids in pure NumPy with the three rules over a fixed sensing radius and tracks the order parameter, the magnitude of the mean unit-velocity vector,

which is $0$ when headings point every which way and $1$ when the flock is perfectly aligned. We start from random positions and random headings (a disordered cloud) and watch $\phi$ climb as local averaging takes hold.

import numpy as np

rng = np.random.default_rng(7)
N, STEPS = 150, 200
R = 0.12            # neighbor sensing radius (local sensing only)
R_SEP = 0.03        # separation radius (avoid crowding)
SPEED = 0.012       # constant cruising speed
W_SEP, W_COH = 0.6, 0.25     # separation / cohesion nudge strengths

pos = rng.random((N, 2))                       # random positions in the unit square
ang = rng.uniform(0, 2 * np.pi, N)             # random initial headings (disordered)

def order_parameter(a):
    # |mean unit velocity|: 0 = disordered, 1 = perfectly aligned flock
    return np.hypot(np.mean(np.cos(a)), np.mean(np.sin(a)))

print("step   alignment(order parameter)")
for t in range(STEPS + 1):
    d = (pos[:, None, :] - pos[None, :, :] + 0.5) % 1.0 - 0.5   # toroidal offsets
    dist = np.hypot(d[:, :, 0], d[:, :, 1])
    nbr = dist < R                                             # neighbor graph (incl self)

    new_ang = ang.copy()
    for i in range(N):
        js = np.where(nbr[i])[0]
        # Alignment = heading consensus: average the neighbors' heading vectors.
        ax, ay = np.cos(ang[js]).sum(), np.sin(ang[js]).sum()
        # Cohesion: a pull toward the local center of mass of neighbors.
        coh = -d[i, js].sum(axis=0)
        ax += W_COH * coh[0]; ay += W_COH * coh[1]
        # Separation: push away from neighbors that are too close.
        close = js[(dist[i, js] < R_SEP) & (js != i)]
        if close.size:
            sep = d[i, close].sum(axis=0)        # offsets point from neighbor to self
            ax += W_SEP * sep[0]; ay += W_SEP * sep[1]
        new_ang[i] = np.arctan2(ay, ax)

    ang = new_ang
    pos = (pos + SPEED * np.c_[np.cos(ang), np.sin(ang)]) % 1.0   # advance, wrap

    if t % 40 == 0:
        print(f"{t:4d}   {order_parameter(ang):.3f}")

print("final alignment      :", f"{order_parameter(ang):.3f}")

step   alignment(order parameter)
   0   0.118
  40   0.968
  80   0.998
 120   0.999
 160   0.999
 200   1.000
final alignment      :   1.000

The order parameter rising from $0.12$ to $1.0$ is the emergence claim turned into a number: each agent averaged only with neighbors inside radius $R$, never computed a global heading, and yet the whole group converged to one. The first forty steps do almost all the work, which is the spectral-gap story from Section 2 made visible: once the interaction graph is well connected, consensus is fast. Slow the agents' cohesion or shrink $R$ until the graph fragments, and you would instead see $\phi$ stall below $1$, with the cloud settling into several internally-aligned but mutually-disagreeing flocks.

4. From Boids to Drone Swarms Advanced

The reason flocking matters for distributed AI, and not only for animation, is that a drone swarm or a fleet of ground robots faces exactly the boids constraints: each unit has local sensing (cameras, lidar, short-range radio), local communication with whoever is in range, no reliable global controller, and a hard need to move coherently without colliding. Decentralized motion coordination under those constraints is consensus-based flocking with real dynamics bolted on. Separation becomes a safety-critical collision-avoidance term, alignment becomes velocity consensus over the communication graph, and cohesion becomes the rule that keeps the swarm in radio range. The connectivity requirement stops being a curiosity and becomes a mission constraint: a swarm whose communication graph partitions is a swarm that can no longer agree on a maneuver. We develop the full robotics treatment, with sensing noise, latency, and partial failures, in the multi-agent robotics and drone-swarm case study of Chapter 39.

import numpy as np
# A: row-normalized adjacency of the interaction graph (who senses whom).
# One alignment / consensus step = one averaging against neighbors.
def consensus_step(v, A, eps=1.0):
    return v + eps * (A @ v - v)        # v <- (I - eps L) v, the boid alignment rule

for _ in range(50):                     # repeat; converges if the graph is connected
    v = consensus_step(v, A)