Swarms and distributed control

Lesson 9 treated multi-robot teams in which tasks are explicitly allocated, often by a planner or an auction. Swarm robotics takes a different approach: large numbers of relatively simple robots, each using only local sensing and communication, follow simple rules from which useful collective behaviour emerges. No robot knows the whole plan, and no single robot is essential. This lesson covers the principles of swarm robotics, the mathematics of consensus on communication graphs, flocking and formation control, coverage control, stigmergy and threshold-based task allocation, and the difficult questions of designing, verifying and supervising emergent behaviour. It also distinguishes true swarms from centrally choreographed groups, such as most drone light shows.

Principles of swarm robotics

Swarm robotics draws inspiration from social insects, bird flocks and fish schools. An ant colony finds short paths to food, a termite mound regulates its temperature and a flock of starlings turns as one, without any individual directing the group. Researchers identify several properties that swarm systems aim for. Robustness: the loss of some robots degrades performance gradually rather than causing failure. Scalability: the same rules work for ten robots or a thousand, because each robot interacts only with neighbours. Flexibility: the swarm adapts to changes in the environment or task. Simplicity of individuals: each robot can be cheap, with limited sensing, computation and communication.

These properties come with costs. Emergent behaviour can be hard to predict and to design: choosing local rules that produce a desired global outcome is an inverse problem with no general solution. Performance may be lower than with an optimized centralized plan. Verifying that a swarm will never do something unsafe is difficult because the space of possible interactions is enormous. And supervising hundreds of robots requires new forms of human interface. Field applications have so far been more limited than research suggests, but swarm methods are increasingly used for parts of larger systems: distributed sensing, area coverage, formation keeping and resilient communication.

Consensus on communication graphs

Many distributed algorithms reduce to agreement: robots must agree on a heading, a meeting point, a time, or an estimate of a quantity such as average temperature, using only communication with neighbours. Model the robots as nodes of a graph, with an edge between two robots that can communicate. In the simplest consensus protocol, each robot repeatedly moves its value toward the values of its neighbours:

Here \( L = D - A \) is the graph Laplacian, with \( D \) the diagonal matrix of node degrees and \( A \) the adjacency matrix. If the graph is connected and undirected, all values converge to the average of the initial values. The speed of convergence is governed by the second-smallest eigenvalue of \( L \), called the algebraic connectivity \( \lambda_2 \): disagreement decays roughly as \( e^{-\lambda_2 t} \). Well-connected graphs have large \( \lambda_2 \) and agree quickly; long chains and rings of robots, common when robots are strung out along a pipeline or tunnel, have small \( \lambda_2 \) and agree slowly. In discrete time with step size \( \varepsilon \), the update \( x_i \gets x_i + \varepsilon \sum_j (x_j - x_i) \) converges if \( \varepsilon \) is less than one over the maximum degree.

# Discrete-time average consensus on three communication graphs
import numpy as np
rng = np.random.default_rng(10)
n = 20
def laplacian(A):
    return np.diag(A.sum(1)) - A
def chain(n):
    A = np.zeros((n, n))
    for i in range(n - 1): A[i, i + 1] = A[i + 1, i] = 1
    return A
def ring(n):
    A = chain(n); A[0, -1] = A[-1, 0] = 1; return A
def geometric(n, radius):
    while True:
        p = rng.uniform(0, 1, (n, 2))
        A = ((np.linalg.norm(p[:, None] - p[None], axis=2) < radius) & ~np.eye(n, dtype=bool)).astype(float)
        if np.linalg.eigvalsh(laplacian(A))[1] > 1e-9: return A     # keep only connected graphs
x0 = rng.uniform(0, 100, n)          # e.g. each robot's local temperature estimate
for name, A in [("chain", chain(n)), ("ring", ring(n)), ("random geometric", geometric(n, 0.4))]:
    L = laplacian(A); lam2 = np.linalg.eigvalsh(L)[1]
    eps = 0.9 / A.sum(1).max()
    x, k = x0.copy(), 0
    while np.ptp(x) > 0.01 * np.ptp(x0):
        x = x - eps * L @ x; k += 1
    print(f"{name:17s} lambda2 = {lam2:6.3f}  steps to 1 % disagreement: {k:5d}  average kept: {x.mean():.3f} vs {x0.mean():.3f}")

chain             lambda2 =  0.025  steps to 1 % disagreement:   220  average kept: 59.465 vs 59.465
ring              lambda2 =  0.098  steps to 1 % disagreement:    72  average kept: 59.465 vs 59.465
random geometric  lambda2 =  0.935  steps to 1 % disagreement:    27  average kept: 59.465 vs 59.465

The chain of twenty robots needs about eight times as many iterations to agree as the well-connected random network, and closing the chain into a ring with one extra link makes agreement about three times faster. In every case the average is preserved, which is what makes consensus useful for distributed estimation: robots can compute the average of their measurements without sending them all to one place. Practical versions must handle changing graphs as robots move, communication delays, packet loss and robots that fail or report faulty values; resilient consensus algorithms discard extreme values from neighbours so that a few faulty or malicious robots cannot pull the group arbitrarily.

Flocking and formations

In 1987 Craig Reynolds showed that realistic animated flocks, which he called boids, emerge when each agent follows three local rules: separation (steer away from neighbours that are too close), alignment (steer toward the average heading of neighbours) and cohesion (steer toward the average position of neighbours). Later work, notably by Olfati-Saber, gave flocking algorithms with proofs of collision avoidance and velocity matching for robots, using potential functions for spacing and consensus for alignment. Flocking is used for groups of drones or surface vessels moving together without fixed positions.

# A minimal boids simulation: does the group align and stay together?
import numpy as np
rng = np.random.default_rng(3)
N, R, dt, vmax = 40, 15.0, 0.1, 5.0
pos = rng.uniform(0, 60, (N, 2)); vel = rng.normal(0, 2, (N, 2))
def step(pos, vel, w_sep=1.5, w_ali=1.0, w_coh=0.4):
    d = pos[:, None, :] - pos[None, :, :]
    dist = np.linalg.norm(d, axis=2) + np.eye(N) * 1e9
    nb = dist < R
    acc = np.zeros_like(vel)
    for i in range(N):
        if nb[i].any():
            close = dist[i] < 4.0
            acc[i] += w_sep * (d[i][close] / dist[i][close, None] ** 2).sum(0) if close.any() else 0
            acc[i] += w_ali * (vel[nb[i]].mean(0) - vel[i])
            acc[i] += w_coh * (pos[nb[i]].mean(0) - pos[i]) * 0.1
    vel = vel + acc * dt
    speed = np.linalg.norm(vel, axis=1, keepdims=True)
    vel = np.where(speed > vmax, vel / speed * vmax, vel)
    return pos + vel * dt, vel
def order(vel):                        # 1.0 means all agents move in the same direction
    u = vel / np.linalg.norm(vel, axis=1, keepdims=True)
    return np.linalg.norm(u.mean(0))
for t in range(0, 601):
    if t % 150 == 0:
        dmin = (np.linalg.norm(pos[:, None] - pos[None], axis=2) + np.eye(N) * 1e9).min()
        print(f"step {t:3d}: alignment order {order(vel):.2f}, closest pair {dmin:5.2f} m, group spread {pos.std(0).mean():5.1f} m")
    pos, vel = step(pos, vel)

step   0: alignment order 0.02, closest pair  0.14 m, group spread  16.9 m
step 150: alignment order 0.18, closest pair  3.44 m, group spread  11.9 m
step 300: alignment order 0.27, closest pair  2.82 m, group spread   7.8 m
step 450: alignment order 0.61, closest pair  2.19 m, group spread   6.6 m
step 600: alignment order 0.95, closest pair  2.07 m, group spread   6.3 m

The order parameter rises as the agents align, and separation keeps them from colliding, without any agent knowing the group's overall direction. Changing the weights changes the behaviour: too little cohesion and the flock splits; too much and it collapses into a tight cluster. Tuning such parameters for robust behaviour across many conditions is a central challenge of swarm design, and automatic design methods such as evolutionary algorithms and reinforcement learning are often used to search for good local rules.

Formation control asks robots to hold a specific geometric shape, such as a line of AUVs spaced 200 m apart to survey with side-scan sonar, or a triangle of drones for stereo imaging. Displacement-based formation control applies consensus to the differences between actual and desired relative positions, so the formation can translate while keeping its shape; distance-based methods use only measured distances, which avoids the need for a shared coordinate frame but needs rigid graph structures to define a unique shape. Leader-follower schemes are simpler but depend on the leader.

Coverage, stigmergy and division of labour

Coverage control distributes robots over an area to monitor it well. In the method of Cortés and colleagues, each robot is responsible for its Voronoi cell, the set of points closer to it than to any other robot, and moves toward the centroid of its cell weighted by a density function describing where coverage matters most. Repeating this, a form of Lloyd's algorithm, converges to a centroidal Voronoi configuration that locally optimizes coverage, using only information about neighbours. The approach suits sensor networks of drones or surface vessels monitoring an oil spill, an algal bloom or a wildfire perimeter, and the density function can be updated as new measurements arrive.

Stigmergy is coordination through changes in the environment: ants lay pheromone trails that others follow, reinforcing short paths. Robots can use virtual pheromones in a shared map, marks such as RFID tags or simply the state of the work itself, for example a weeding robot avoiding rows that look recently treated. Division of labour in insect colonies is often explained by response thresholds: each individual takes up a task when a stimulus, such as the amount of unfinished work, exceeds its personal threshold, and thresholds vary across individuals. Robots using randomized thresholds can divide work among tasks in proportion to demand without explicit negotiation, adapting as demand changes and as robots fail.

Swarms in practice

Research swarms demonstrate scale. Harvard's Kilobot project showed in 2014 that 1,024 small, inexpensive robots could self-assemble into shapes using only local infrared communication. Drone light shows with thousands of drones are visually swarm-like, but they are usually choreographed: each drone follows a pre-computed trajectory using RTK positioning and synchronized timing, with a central ground station; they show the value of precise positioning and fleet management rather than emergent behaviour. Field uses of swarm ideas include distributed ocean sensing with many floats and gliders, cooperative search with drones, and formations of surface vessels for survey. Militaries in several countries are investing heavily in drone swarms and in countering them; ROB-450 lesson 11 discussed the ethical and legal debate about autonomy in the use of force, which applies with particular force to swarms because human control over each robot's actions may be weak.

Human-swarm interaction is an active research area. Operators of large swarms work best with high-level commands such as setting the area to cover, the density of robots, or the behaviour to adopt, and with displays that summarize the swarm's state rather than showing every robot. The same principles apply to supervising fleets of field robots, as lesson 11 develops.