"No one told me where the formation's center was. I just kept matching the speed of the two robots I could see, and somehow we all arrived holding the shape."
A Formation, Holding Its Shape Without a Conductor
A team of robots coordinates its motion and behavior not because one machine commands the rest, but because each robot runs the same simple rule over the small set of neighbors it can sense or hear, and the global pattern (a formation, a flock, a meeting point, a covered area) emerges from those local interactions. The previous section described the robots themselves and the perception that gives each one a local picture of its world. This section is about what happens when many such robots must act as one body. We take the two most relevant ideas from Part VI, the multi-agent system that frames each robot as an autonomous agent with goals and a communication graph (Chapter 29) and the swarm-intelligence principle that complex collective behavior arises from simple local rules (Chapter 31), and ground them in the concrete problem of getting physical robots to move together. The mathematical heart of the section is one primitive, distributed consensus, the same agreement-through-local-averaging idea introduced for distributed-systems coordination in Chapter 2 and used for sensor fusion at the edge in Section 34.5. Here it becomes the engine that lets robots agree on a heading, a meeting point, or a shared estimate without ever routing everything through a center.
A single robot executes a plan. A team of robots must first agree on what the plan is, and then keep agreeing as the world moves underneath them. That agreement is the whole problem of coordination, and it is harder than it sounds, because no robot sees the full team, communication links come and go as robots move in and out of range, and there is rarely time to gather everyone's state at one place and broadcast a decision back. The discipline of multi-robot coordination answers a single question in many forms: how does a group of robots, each acting on local information and local communication, produce coherent collective behavior? The answer that scales, the one this section develops, is that coordination is computed the same way the rest of this book computes distributed results, by local interaction and a combine step, not by a central controller that becomes the bottleneck and the single point of failure the moment the team grows.
1. Three Ways to Coordinate, and Why Only One Scales Beginner
Coordination architectures fall on a spectrum, and naming the three points on it fixes the vocabulary for the rest of the section. A centralized scheme elects one node, a ground station or a designated lead robot, that collects the state of the whole team, computes the joint plan, and sends each robot its part. It is the easiest to reason about and the easiest to break: the center is a single point of failure, its inbound link saturates as the team grows, and a robot that loses contact with it is left with no instruction at all. A decentralized scheme removes the center but still allows rich structure, typically a hierarchy or clusters with local leaders, so that most decisions are made locally and only summaries travel far. A distributed scheme is the limiting case: there is no privileged node, every robot runs an identical rule, and the only information any robot uses is what it can obtain from its immediate neighbors in the communication graph. The global behavior is then an emergent property of those local interactions rather than the output of any one machine.
This is the same architectural choice the book has made repeatedly, and for the same reason. A parameter server (Chapter 11) centralizes the gradient combine and pays for it with a bandwidth bottleneck; all-reduce distributes the combine and scales to thousands of workers because no node is special. Multi-robot coordination repeats the lesson in physical space: a central planner is fine for three robots in a lab and impossible for three hundred drones over a field, where links are intermittent and latency to a ground station is fatal to a tight formation. The distributed paradigm is the one that scales out, because its communication is local and its cost per robot does not grow with the size of the team. The rest of this section is about how to compute genuinely collective behavior under that constraint.
Distributed training combines per-worker gradients into one shared update through neighbor communication and averaging. Distributed robot coordination combines per-robot estimates (heading, position, a target location) into one shared agreement through neighbor communication and averaging. The mathematics is the same primitive, consensus, and the reason to prefer it is the same: a combine that uses only local links has no central bottleneck and no single point of failure, so it scales to many agents and survives the loss of any one of them. When you see a flock, a formation, or a swarm meeting at a point, you are watching an all-reduce being computed by robots instead of GPUs.
2. Flocking: Three Local Rules That Make a Swarm Beginner
The clearest demonstration that global motion can come from local rules is Reynolds' model of flocking, the foundation of the swarm-behavior treatment in Chapter 31. Each simulated agent, a "boid," looks only at the flockmates within a fixed sensing radius and steers by combining three rules. Separation steers away from neighbors that are too close, preventing collisions. Cohesion steers toward the average position of nearby flockmates, keeping the group together. Alignment steers toward the average velocity of nearby flockmates, so the group moves as one. Writing $\mathcal{N}_i$ for the set of neighbors robot $i$ currently senses, $p_j$ and $v_j$ for the position and velocity of robot $j$, and $p_j - p_i$ for the relative position, the three steering accelerations are
$$a_i^{\text{sep}} = -\!\!\sum_{j \in \mathcal{N}_i} \frac{p_j - p_i}{\lVert p_j - p_i \rVert^2}, \qquad a_i^{\text{coh}} = \frac{1}{|\mathcal{N}_i|}\!\!\sum_{j \in \mathcal{N}_i} (p_j - p_i), \qquad a_i^{\text{ali}} = \frac{1}{|\mathcal{N}_i|}\!\!\sum_{j \in \mathcal{N}_i} (v_j - v_i),$$and the robot follows their weighted sum $a_i = w_s\, a_i^{\text{sep}} + w_c\, a_i^{\text{coh}} + w_a\, a_i^{\text{ali}}$. No term refers to a global quantity; each is an average or a sum over the neighbor set alone. The famous result, and the reason flocking is the canonical example of swarm intelligence, is that a few hundred agents running this rule with no leader produce the coherent, fluid, obstacle-avoiding motion of a bird flock or a fish school. The collective pattern is real and useful, yet it lives nowhere in any single agent's program; it is a property of the interaction.
The alignment term is worth isolating, because it is exactly the consensus update of the next section applied to velocity. Stripped of separation and cohesion, alignment says each robot moves its velocity a little toward the average velocity of its neighbors. Iterated, that is precisely the process in Figure 39.2.1: scattered headings collapse to a common heading. Flocking, then, is consensus on velocity wrapped in two extra rules that manage spacing. This is the bridge from the intuitive swarm picture to the precise primitive we can analyze and prove convergent.
Reynolds built boids in 1986 to animate bat swarms for film, not to control robots, and the unsettling thing he found is that no boid ever "knows" it is in a flock. Each one is selfishly matching its three nearest neighbors and avoiding a crash. The murmuration, the rolling dark cloud of a thousand starlings turning as one over a winter field, is something only an outside observer perceives. The birds, like the robots, are just doing local arithmetic. Distributed intelligence has a way of being invisible to its own participants.
3. The Consensus Primitive: Agreement by Local Averaging Intermediate
Underneath formation control, flocking alignment, rendezvous, and distributed estimation sits one primitive. Each robot $i$ holds a value $x_i$, a heading, a coordinate, a sensor estimate, and the team must agree on a single shared value computed from all of them, using only neighbor communication. The distributed consensus update is
$$x_i(t+1) = x_i(t) + \sum_{j \in \mathcal{N}_i} w_{ij}\,\big(x_j(t) - x_i(t)\big),$$which reads operationally as: each robot moves its value a fraction of the way toward each neighbor's value, summed over its neighbors. The weights $w_{ij}$ are nonnegative, vanish for non-neighbors, and are small enough that no robot overshoots. Collecting the values into a vector $x(t)$, the whole team's update is the linear map $x(t+1) = W\,x(t)$ for a weight matrix $W$ whose off-diagonal entry $(i,j)$ is $w_{ij}$ and whose rows sum to one. If $W$ is symmetric, doubly stochastic, and the communication graph is connected, a classical result guarantees that every robot's value converges to the exact average of the initial values,
$$\lim_{t \to \infty} x_i(t) = \bar{x} = \frac{1}{n}\sum_{k=1}^{n} x_k(0) \quad \text{for every } i,$$at a geometric rate governed by the second-largest eigenvalue magnitude of $W$. The team computes a global mean using only local links, exactly the all-reduce of Chapter 2 and the data-parallel gradient average of Chapter 15, now run over a physical robot network instead of a datacenter fabric. Section 39.6 develops the decentralized-control machinery (proofs, time-varying graphs, robustness to link loss) in full; here we use the result and watch it work.
The one design subtlety is choosing $W$ so that convergence to the true mean is guaranteed using only local information. A robot cannot know the global graph, but it can know its own degree and ask each neighbor for that neighbor's degree. The Metropolis-Hastings weights, $w_{ij} = 1 / (1 + \max(\deg_i, \deg_j))$ for each edge with the diagonal set so each row sums to one, are computable from exactly that local exchange and make $W$ symmetric and doubly stochastic. The demonstration below builds these weights on a small robot communication graph and runs the consensus update of Section 3 to agreement.
import numpy as np
# A small communication graph: 6 robots, each links only to a few neighbors.
# Edge (i, j) means robots i and j can hear each other and exchange a scalar.
edges = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,0),(0,3)] # a ring plus one chord
n = 6
# Build the symmetric adjacency and degree from the undirected edges.
A = np.zeros((n, n))
for i, j in edges:
A[i, j] = 1.0
A[j, i] = 1.0
deg = A.sum(axis=1)
# Metropolis-Hastings weights: every robot uses only LOCAL info (its own degree
# and each neighbor's degree). These weights guarantee convergence to the mean.
W = np.zeros((n, n))
for i in range(n):
for j in range(n):
if A[i, j] > 0:
W[i, j] = 1.0 / (1.0 + max(deg[i], deg[j]))
W[i, i] = 1.0 - W[i].sum()
# Each robot starts with its own noisy heading estimate (degrees).
rng = np.random.default_rng(7)
x = rng.uniform(0.0, 120.0, size=n)
global_mean = x.mean()
print(f"global mean (the target) : {global_mean:.4f}")
print(f"initial spread (max - min) : {x.max() - x.min():.4f}")
print()
print("round disagreement (max-min) est. of robot 0")
print("----- ---------------------- ----------------")
for t in range(0, 21):
if t in (0, 1, 2, 4, 8, 16, 20):
print(f"{t:5d} {x.max() - x.min():21.6f} {x[0]:14.6f}")
x = W @ x # one synchronous round: each robot averages with neighbors
print()
print(f"final disagreement : {x.max() - x.min():.2e}")
print(f"final estimate (robot 0) : {x[0]:.6f}")
print(f"error vs global mean : {abs(x[0] - global_mean):.2e}")
global mean (the target) : 73.9384
initial spread (max - min) : 80.6408
round disagreement (max-min) est. of robot 0
----- ---------------------- ----------------
0 80.640793 75.011456
1 37.934314 78.632097
2 23.348450 76.373726
4 10.495563 74.467821
8 3.023710 73.953750
16 0.300200 73.938447
20 0.094981 73.938438
final disagreement : 7.12e-02
final estimate (robot 0) : 73.938438
error vs global mean : 9.82e-08
The disagreement, the gap between the most and least optimistic robot, shrinks geometrically: roughly a factor of three every two rounds, fixed by the second eigenvalue of $W$. This is the same convergence-by-averaging that produces the aligned headings of Figure 39.2.1, the same combine that data parallelism uses to agree on a gradient, now agreeing on a heading instead. A team with no leader and no global view computed a global quantity from local conversations alone.
The averaging combine that opened this book as the exact gradient identity of data parallelism (Chapter 1) and reappeared as gradient all-reduce in distributed training (Chapter 15) has now crossed out of the datacenter. In Code 39.2.1 the workers are robots, the network is a mesh of radio links that move as the robots move, and the value being reduced is a heading rather than a gradient, yet the operation is identical: combine one value per node into a shared mean using only local communication, with no central node and no single point of failure. Scale-out's signature primitive is not a datacenter technique that happens to suit robots; it is the way distributed agreement is computed wherever agents must agree without a center.
4. Formation, Rendezvous, and Coverage from One Primitive Intermediate
Consensus is not only how robots agree on a number; with a small twist it is how they take up a spatial pattern. In rendezvous, every robot must meet at a single point not fixed in advance. Running the consensus update on each robot's position vector drives every position toward the average of the initial positions, so the team gathers at its own centroid, a meeting point that emerged from the group rather than being assigned. Formation control generalizes this by giving robot $i$ a desired offset $\delta_i$ from the formation center and running consensus on the shifted quantity $p_i - \delta_i$; the values agree, which means $p_i - p_j \to \delta_i - \delta_j$, so the robots settle into the exact relative geometry of a wedge, line, or grid while the center of that geometry is again whatever the group converges to. The pattern is held by every robot tracking its neighbors' offsets, with no robot needing to know where the formation's center is, which is precisely the situation the epigraph describes.
Two organizational choices cut across all of these. A leader-follower formation designates one robot whose motion is exogenous (it follows a mission path or a human pilot) while the rest reach consensus relative to it; the team inherits a direction cheaply, at the cost of a distinguished robot whose loss the followers must detect and recover from. A leaderless formation gives no robot special status, so the shape is robust to the loss of any member but the group's overall trajectory must be injected some other way, for instance by giving several robots a weak bias toward a goal. The same consensus core serves both; the choice is about where the mission's intent enters the team. Coverage control applies the identical local-interaction logic to area rather than shape: each robot is responsible for the region closer to it than to any other robot (its Voronoi cell) and moves toward that cell's centroid, computable from neighbor positions alone. The team spreads to tile an area evenly, the natural distributed solution to surveillance, mapping, and search, and a direct application of the distributed-sensing-and-fusion view of Section 34.5.
Who: A robotics engineer deploying a team of twelve drones to inspect a wind farm spread over several kilometers.
Situation: The first design routed every drone's position and camera trigger through a single ground station that computed the formation and sent each drone its waypoint.
Problem: At the far end of the farm, link latency to the ground station spiked and occasionally dropped; drones that lost contact froze in place, and the centralized formation buckled whenever the station's uplink saturated.
Dilemma: Keep the centralized planner and invest in a stronger, costlier radio backbone to every drone, or move to a distributed formation where drones coordinate with the few neighbors in radio range and the ground station only sets the mission goal.
Decision: They went distributed, running consensus-based formation control on each drone's offset from the formation center, with three drones given a weak bias toward the next inspection target to inject the mission direction.
How: Each drone broadcast its position and offset to neighbors within range, computed Metropolis-style weights from local degree exchange, and updated its target with the consensus rule of Code 39.2.1 generalized to two-dimensional positions.
Result: The formation held its wedge across the whole farm despite intermittent links; a drone that briefly lost all neighbors simply held position and rejoined when a link returned, and the loss of the ground station mid-mission degraded nothing but the ability to retask, exactly the single-point-of-failure removal that Section 1 promised.
Lesson: When links are intermittent and the team is spread over distance, distributing the coordination is not an optimization, it is what makes the team survive at all.
5. Communication, Asynchrony, and the Limits of Local Rules Advanced
The clean convergence of Code 39.2.1 rests on assumptions a real robot team strains. The update was synchronous, every robot stepping in lockstep, whereas robots sense and message at different times, so practical consensus runs asynchronously and the convergence guarantee must be re-established for updates that interleave and use stale neighbor values, the same synchronous-versus-asynchronous tension that runs from coordination in Chapter 2 through asynchronous SGD in Chapter 10. The graph was fixed and connected, whereas a moving team's links appear and vanish; the theory extends to time-varying graphs provided the union of links over any bounded window stays connected, a condition called joint connectedness that formation controllers must actively preserve by keeping robots within range of enough neighbors. And the rate of agreement is set by the graph's connectivity: a long thin chain of robots reaches consensus slowly because information crawls hop by hop, while a denser mesh agrees fast, which is why coverage and formation designs care about the algebraic connectivity of the team, not merely about staying linked.
There is also a ceiling on what purely local, value-averaging rules can achieve. Consensus agrees on an average, which is the right answer for a heading or a meeting point but the wrong tool for a task that needs a discrete joint decision: which robot inspects which turbine, who yields at a narrow passage, how to break the symmetry when averaging would freeze every robot at the centroid. Those problems are distributed task allocation and negotiation, and they draw on the auction and game-theoretic mechanisms of Chapter 29 rather than on averaging. The practical lesson is to match the coordination primitive to the structure of the agreement: continuous quantities that should blend, use consensus; discrete assignments that should be partitioned, use a distributed allocation protocol. A complete robot team uses both, consensus to hold the formation and an allocation layer to decide what the formation is for.
Code 39.2.1 builds the weight matrix and the update loop by hand to expose the primitive. In a real robot stack you describe the communication graph and let a library run the dynamics. With NetworkX, a doubly stochastic consensus matrix for any graph is a single call, and the update is one matrix-vector product per round:
import networkx as nx, numpy as np
G = nx.cycle_graph(6); G.add_edge(0, 3) # the same robot mesh
# Lazy Metropolis-Hastings weights straight from the graph (one call):
W = np.eye(6) - 0.5 * nx.laplacian_matrix(G, weight=None).toarray() / 6
x = np.array([10., 90., 30., 70., 50., 80.])
for _ in range(50):
x = W @ x # neighbor averaging, vectorized
print("agreed value:", round(float(x.mean()), 4), "| spread:", f"{x.max()-x.min():.2e}")
Two threads are reshaping multi-robot coordination beyond hand-tuned rules. The first replaces fixed weights with learned coordination policies: graph neural networks whose message-passing layers mirror the neighbor structure of the team are trained so that each robot's policy generalizes to team sizes never seen in training, a line developed in decentralized GNN controllers for flocking and coverage (Tolstaya et al. and successors), and pushed further by multi-agent reinforcement learning that learns the local rule directly, connecting this case study back to distributed MARL training (Chapter 30) and the distributed RL infrastructure of Chapter 20. The second thread is safety with guarantees: control-barrier-function methods give each robot a local filter that provably preserves collision avoidance and connectivity while it runs whatever consensus or learned policy drives the mission, so the emergent behavior of a large swarm carries a formal safety certificate rather than only empirical good behavior. Both directions keep the distributed, local-communication structure that makes the team scale, while replacing the fixed averaging rule with something learned or certified. Section 39.6 takes up the decentralized-control theory these methods build on.
We now have the spine of multi-robot coordination: three architectures of which only the distributed one scales, flocking as the intuitive face of local rules, and consensus as the precise primitive that delivers formation, rendezvous, and coverage from neighbor communication alone. The next section moves from getting the robots to move together to giving the team a shared picture of its environment, where the same local-combine logic returns as distributed estimation and mapping. That tour begins in Section 39.3.
For each scenario, state whether a centralized, decentralized, or distributed coordination scheme fits best, and name the specific failure or bottleneck that rules out the others: (a) three warehouse robots sharing one charging dock under a single facility controller; (b) a hundred-drone light show choreographed to a fixed soundtrack with a reliable broadcast uplink; (c) a fifty-robot search team spread across a disaster site with no infrastructure and intermittent peer-to-peer radio. Then explain, for case (c), which quantities the team should reach by consensus and which require a distributed task-allocation protocol instead.
Extend Code 39.2.1 from scalar headings to two-dimensional positions, then turn rendezvous into formation control. First run the consensus update on each robot's $(x, y)$ position and confirm all robots converge to the centroid (rendezvous). Next give robot $i$ a desired offset $\delta_i$ (for example, the vertices of a regular hexagon) and run consensus on $p_i - \delta_i$; verify that the final relative positions satisfy $p_i - p_j \approx \delta_i - \delta_j$, so the team forms the hexagon. Report the residual formation error and the round at which it falls below $10^{-3}$, and explain why the formation's absolute center is not something you controlled.
The convergence rate of consensus is governed by the second-largest eigenvalue magnitude of the weight matrix $W$. For three six-robot graphs, a path (a chain), a ring, and a complete graph (every robot hears every other), build the Metropolis-Hastings weight matrix, compute that eigenvalue, and predict the number of rounds each needs to shrink the disagreement by a factor of $1000$. Confirm the prediction by running the update of Code 39.2.1 on each graph. Explain, in terms of how information travels through the graph, why the chain is slowest and the complete graph is fastest, and what this implies for how spread out a real robot team can afford to be while still holding a tight formation.