Skip to content
LumenaryAcademy
Systems 70 min

Multi-robot systems

Many robots, one job. Who decides, who does which task, how a group agrees and moves together, how swarms emerge from simple rules, how robots share corridors without collisions, and what warehouses with thousands of robots have learned.

Code tested · 5AI-draftedAwaiting review by a roboticist

Your guides: Chloe · The Builder, Margaret · The Experimenter, Gideon · The Safety Engineer

MotivationH

Why many robots, and why it is hard

Some jobs are too big, too spread out or too risky for one robot. A fulfilment centre has hundreds of thousands of items to bring to packers each day; a farm has hectares to weed; a search after an earthquake covers a whole district; a mine's tunnels must be mapped faster than one robot can drive them. Several robots working together can do more at once, cover more ground, carry on when one breaks, and combine different abilities: a drone that sees from above guiding a ground robot that can lift. On Mars, NASA's Ingenuity helicopter flew ahead of the Perseverance rover from 2021, scouting routes.

But more robots is not automatically better. They get in each other's way, they must agree on who does what, and they must talk over radios that drop messages and have limited range. A fleet of a hundred robots in which each waits for permission from every other is slower than one robot. The central questions of this lesson are therefore organisational: who decides (architectures), who does what (task allocation), how robots agree and move together (consensus, formations, swarms), and how they share space (multi-agent path finding), all under limited communication.

IntuitionH

Who decides: coordination architectures

centraliseddecentralisedhierarchical
Three ways to organise a team. Centralised: one planner hears every robot and commands every robot. Decentralised: each robot decides for itself, talking only to the neighbours it can reach. Hierarchical: a fleet manager assigns work and reserves space, while robots handle local motion and safety themselves.

A centralised system has one planner that knows every robot's state and decides everything. It can find the best plan, and it is simple to reason about, but its computation grows quickly with the number of robots, it needs reliable communication with all of them, and it is a single point of failure. A decentralised (or distributed) system lets each robot decide for itself using only what it senses and what its neighbours tell it. It scales, survives losing robots and links, and works when no central computer is in range, but its decisions are usually worse than a central planner's, and proving that the group as a whole behaves well is harder. Real systems are mostly hierarchical: a fleet manager assigns tasks and reserves routes, while each robot plans its own motion, avoids obstacles and keeps itself safe.

A useful middle ground is the market: robots bid for tasks with their own cost estimates, and an auction (run by an auctioneer, or by the robots among themselves) allocates them. Each robot computes its bids locally, using what it alone knows (where it is, how much battery it has left), and the auction needs only short messages.

ComputationC

Who does what: task allocation by auction

Definition— Multi-robot task allocation

Given robots R1,…,RmR_1, \ldots, R_m, tasks T1,…,TnT_1, \ldots, T_n and a cost for each robot to do each set of tasks, task allocation chooses which robot does which tasks (and, if a robot does several, in what order) to minimise a team objective, typically the total cost (sum of all robots' travel) or the makespan (the time the last robot finishes).

If each robot does exactly one task and costs simply add, this is the assignment problem, solved exactly in polynomial time by the Hungarian algorithm (Kuhn, 1955). When robots do several tasks each, the cost of a set of tasks depends on the route through them, and the problem contains the travelling-salesperson problem: NP-hard, so large instances are solved approximately (see Hard problems).

A sequential single-item auction is a simple and surprisingly good approximation. In each round, every robot computes, for every unassigned task, its marginal cost: how much longer its route would become if it inserted that task at the best place. It sends its bids to the auctioneer; the single lowest bid in the whole team wins, that task is added to that robot's route, and the next round begins. The program runs it for three robots and seven pick-ups in a 20 m hall, compares it with simply sending each task to the nearest robot, and finds the true optimum by brute force.

python
import itertools
import numpy as np

robots = np.array([[0.0, 0.0], [20.0, 0.0], [10.0, 15.0]])            # start positions (m)
R = len(robots)

def setup(tasks):
    """Distances between all places: robots' starts are 0..R-1, tasks are R..R+n-1."""
    pts = np.vstack([robots, tasks])
    return np.linalg.norm(pts[:, None, :] - pts[None, :, :], axis=2).tolist()

def route_cost(D, i, route):
    """Robot i drives from its start through the tasks in order (no return)."""
    places = [i] + [R + j for j in route]
    return sum(D[a][b] for a, b in zip(places, places[1:]))

def auction(D, n):
    """Sequential single-item auction. Each round every robot bids, for every unassigned task, the
    extra distance it would add by inserting it at the cheapest place in its route; the lowest bid wins."""
    routes, unassigned = [[] for _ in range(R)], set(range(n))
    while unassigned:
        bids = []
        for i in range(R):
            base = route_cost(D, i, routes[i])
            for j in sorted(unassigned):
                for k in range(len(routes[i]) + 1):
                    r = routes[i][:k] + [j] + routes[i][k:]
                    bids.append((route_cost(D, i, r) - base, i, j, r))
        _, i, j, r = min(bids, key=lambda b: b[:3])
        routes[i] = r
        unassigned.remove(j)
    return sum(route_cost(D, i, r) for i, r in enumerate(routes)), routes

def best_costs(D, n):
    """best[i][mask]: shortest route for robot i through exactly the tasks in mask (dynamic programming)."""
    best = []
    for i in range(R):
        dp = {(1 << j, j): D[i][R + j] for j in range(n)}             # (tasks visited, last task) -> length
        for mask in range(1, 1 << n):
            for last in range(n):
                if (mask, last) not in dp:
                    continue
                for nxt in range(n):
                    if not mask & (1 << nxt):
                        key, c = (mask | 1 << nxt, nxt), dp[(mask, last)] + D[R + last][R + nxt]
                        if c < dp.get(key, float("inf")):
                            dp[key] = c
        row = [0.0] + [float("inf")] * ((1 << n) - 1)
        for (mask, last), c in dp.items():
            row[mask] = min(row[mask], c)
        best.append(row)
    return best

def optimum(best, n):
    """Try every assignment of the n tasks to the robots (R^n of them)."""
    out = float("inf")
    for a in itertools.product(range(R), repeat=n):
        masks = [0] * R
        for j, i in enumerate(a):
            masks[i] |= 1 << j
        out = min(out, sum(best[i][m] for i, m in enumerate(masks)))
    return out

def nearest_robot(D, best, n):
    masks = [0] * R
    for j in range(n):
        masks[min(range(R), key=lambda i: D[i][R + j])] |= 1 << j
    return sum(best[i][m] for i, m in enumerate(masks))

rng = np.random.default_rng(11)
n = 7
tasks = np.round(rng.uniform(0, 20, size=(n, 2)), 1)                    # 7 pick-ups in a 20 m x 20 m hall
D = setup(tasks)
best = best_costs(D, n)
cost, routes = auction(D, n)
print("auction routes (task numbers in visiting order):", routes)
print(f"auction {cost:.1f} m; nearest robot {nearest_robot(D, best, n):.1f} m; optimum {optimum(best, n):.1f} m"
      f" (from {R ** n} possible assignments)")

gaps_a, gaps_n = [], []
for trial in range(50):                                                 # 50 more random halls
    tasks = np.round(rng.uniform(0, 20, size=(n, 2)), 1)
    D = setup(tasks)
    best = best_costs(D, n)
    opt = optimum(best, n)
    gaps_a.append(100 * (auction(D, n)[0] / opt - 1))
    gaps_n.append(100 * (nearest_robot(D, best, n) / opt - 1))
print("\nover 50 random halls, extra distance compared with the optimum:")
for name, gaps in [("auction", gaps_a), ("nearest robot", gaps_n)]:
    print(f"  {name:14} mean {np.mean(gaps):4.1f}%   worst {np.max(gaps):5.1f}%   optimal in {sum(g < 1e-9 for g in gaps)} of 50")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

In the first hall the auction finds the optimal plan, 43.9 m of driving against 49.1 m for nearest-robot assignment. Over fifty random halls it is optimal in 30, 2.7% worse than optimal on average and 17% in the worst case, while nearest-robot assignment averages 11.6% and reaches 51.5%. The auction wins because marginal costs account for what each robot is already doing: a task near the end of a robot's route is cheap for that robot even if another robot starts closer to it. Each round costs one message per robot, seven rounds in all here; the brute-force optimum had to examine 37=21873^7 = 2187 assignments, and at 20 tasks it would be about 3.5 billion.

ComputationC

Agreeing and gathering: consensus and rendezvous

Many team behaviours start with agreement: on a meeting point, a common heading, an estimate of where a target is, or the time. The simplest rule is to move towards your neighbours. If robot ii at position xix_i can hear the set of neighbours NiN_i, the consensus protocol is

xi←xi+ε∑j∈Ni(xj−xi),or, for all robots at once,x←x−ε L x,x_i \leftarrow x_i + \varepsilon \sum_{j \in N_i} (x_j - x_i), \qquad\text{or, for all robots at once,}\qquad x \leftarrow x - \varepsilon\, L\, x,

where L=D−AL = D - A is the graph Laplacian of the communication graph: AA its adjacency matrix and DD the diagonal matrix of each robot's number of neighbours (the graph theory of Graph theory).

Theorem— Average consensus

Let the communication graph be undirected and connected, with Laplacian eigenvalues 0=λ1<λ2≤⋯≤λn0 = \lambda_1 < \lambda_2 \le \cdots \le \lambda_n, and let 0<ε<2/λn0 < \varepsilon < 2/\lambda_n (for instance ε<1/dmax⁡\varepsilon < 1/d_{\max}, where dmax⁡d_{\max} is the largest degree). Then the protocol x←x−εLxx \leftarrow x - \varepsilon L x preserves the average xˉ\bar x of the robots' values, and every robot's value converges to xˉ\bar x. The disagreement shrinks at least by the factor max⁡(∣1−ελ2∣,∣1−ελn∣)\max(|1 - \varepsilon\lambda_2|, |1 - \varepsilon\lambda_n|) per step.

Proof

LL is symmetric and every row sums to zero, so 1⊤L=0\mathbf 1^\top L = 0 and 1⊤x\mathbf 1^\top x is unchanged by each step: the average is preserved. Write x=xˉ1+ex = \bar x\mathbf 1 + e with 1⊤e=0\mathbf 1^\top e = 0. Since L1=0L\mathbf 1 = 0, each step maps ee to (I−εL)e(I - \varepsilon L)e. A connected graph's Laplacian has a one-dimensional null space spanned by 1\mathbf 1, so ee lies in the span of eigenvectors with eigenvalues λ2,…,λn\lambda_2, \ldots, \lambda_n, on which I−εLI - \varepsilon L multiplies by 1−ελk1 - \varepsilon\lambda_k. Under the condition on ε\varepsilon each of these factors has magnitude below 1, so e→0e \to 0 geometrically at the stated rate.

∎

Applied to positions, consensus is rendezvous: robots meet at the centroid of where they started, without anyone computing it. The second eigenvalue λ2\lambda_2, the algebraic connectivity, measures how well connected the graph is, and sets the speed. The program gathers six robots scattered over a 50 m field under three communication graphs, then with lost messages, then with the group split in two.

python
import numpy as np

rng = np.random.default_rng(3)
n = 6
x0 = rng.uniform(0, 50, size=(n, 2))                 # six robots scattered over a 50 m x 50 m field
eps = 0.15                                            # step size, kept below 1 / (largest number of neighbours)

def laplacian(edges):
    A = np.zeros((n, n))
    for i, j in edges:
        A[i, j] = A[j, i] = 1.0                        # undirected links: i hears j and j hears i
    return np.diag(A.sum(axis=1)) - A

def spread(x):
    """Largest distance of any robot from the group's centroid (m)."""
    return np.max(np.linalg.norm(x - x.mean(axis=0), axis=1))

def rendezvous(edges, steps=400, loss=0.0):
    """Each step, every robot moves eps times the sum of the offsets to the neighbours it hears."""
    x = x0.copy()
    for k in range(steps):
        if spread(x) < 0.01:
            return k, x
        up = [e for e in edges if rng.random() >= loss]     # links that worked this step
        x = x - eps * laplacian(up) @ x
    return None, x

graphs = {
    "everyone hears everyone": [(i, j) for i in range(n) for j in range(i + 1, n)],
    "ring": [(i, (i + 1) % n) for i in range(n)],
    "line (ring with one link cut)": [(i, i + 1) for i in range(n - 1)],
}
print(f"start: spread {spread(x0):.1f} m, centroid {np.round(x0.mean(axis=0), 2)}")
print("graph                            lambda2   predicted shrink   steps to 1 cm   final centroid")
for name, edges in graphs.items():
    lam2 = np.sort(np.linalg.eigvalsh(laplacian(edges)))[1]
    k, x = rendezvous(edges)
    print(f"{name:31}  {lam2:6.3f}     {1 - eps * lam2:6.3f}          {k:6d}        {np.round(x.mean(axis=0), 2)}")

k, x = rendezvous(graphs["ring"], loss=0.3)
print(f"{'ring, 30% of messages lost':31}     -          -              {k:6d}        {np.round(x.mean(axis=0), 2)}")
k, x = rendezvous([(0, 1), (1, 2), (3, 4), (4, 5)])
print(f"two separate groups of three: never meet (steps = {k}); they gather at "
      f"{np.round(x[0], 1)} and {np.round(x[5], 1)}")

# Formation control: agree on a common reference point, each robot keeping its own offset from it.
offsets = 8 * np.c_[np.cos(np.arange(n) * np.pi / 3), np.sin(np.arange(n) * np.pi / 3)]   # a hexagon, radius 8 m
L = laplacian(graphs["ring"])
x = x0.copy()
for k in range(300):
    x = x - eps * L @ (x - offsets)
err = np.linalg.norm((x - x.mean(axis=0)) - (offsets - offsets.mean(axis=0)), axis=1)
print(f"\nhexagon formation after 300 steps: worst corner error {err.max():.1e} m, "
      f"sides {np.round(np.linalg.norm(x - np.roll(x, -1, axis=0), axis=1), 3)} m, centre {np.round(x.mean(axis=0), 2)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

All three connected graphs bring the robots together at exactly the starting centroid, (21.55, 17.02), but at very different speeds: 4 steps when everyone hears everyone (λ2=6\lambda_2 = 6), 42 on a ring (λ2=1\lambda_2 = 1), 156 on a line (λ2=0.268\lambda_2 = 0.268). Cutting a single link of the ring nearly quadruples the time. Losing 30% of messages at random slows the ring from 42 to 64 steps but does not stop it. Splitting the group into two parts that cannot hear each other is different in kind: each half gathers at its own centroid, 12.8 m apart, and they never meet. Connectivity is the condition; λ2\lambda_2 is the speed.

ExplanationH

Formations and swarms

The last part of the program turned consensus into formation control. Each robot ii is given an offset did_i, its slot in the formation, and runs consensus on xi−dix_i - d_i instead of xix_i. The robots agree on a common reference point, and each sits at its offset from it: after 300 steps the six robots form a regular hexagon with 8 m sides around their starting centroid, correct to 10−1410^{-14} m. Adding a common velocity makes the whole formation move. Other formation schemes use a leader that others follow at fixed offsets (simple, but the leader is a single point of failure), a virtual structure moved as a rigid body, or constraints only on inter-robot distances, which need no common coordinate frame and suit robots without GNSS.

A swarm takes decentralisation to its limit: many simple, usually identical robots, each following local rules based on what it senses nearby, with no robot knowing the global plan. The group's behaviour emerges from the interactions. Craig Reynolds' 1987 "boids" showed that three rules (keep apart from neighbours, match their heading, move towards their centre) produce convincing flocks. In 2014 Rubenstein, Cornejo and Nagpal at Harvard had a thousand coin-sized Kilobots assemble themselves into shapes using only local infrared messages with their neighbours, slowly but without central control. In 2022 a team at Zhejiang University flew a swarm of ten palm-sized drones through a bamboo forest, each planning its own path from its own sensors and sharing trajectories with the others.

Swarms are attractive because they scale and tolerate failures: lose ten robots out of a thousand and the rest carry on. They are hard to design because nobody can program the global behaviour directly; it must be coaxed from local rules, and checked by simulation and analysis. The drone light shows seen in many cities are, despite the name, not swarms in this sense: each drone flies a trajectory planned in advance by a central computer and follows it by RTK GNSS.

ComputationC

Sharing space: multi-agent path finding

When many robots move in a shared space, each robot's shortest path is not enough: two robots may want the same cell at the same moment, or need to pass in a corridor only one wide.

Definition— Multi-agent path finding (MAPF)

On a graph (often a grid) with time in discrete steps, each of kk robots has a start and a goal vertex, and at each step it either waits or moves to a neighbouring vertex. A solution is a path for every robot with no vertex conflict (two robots at the same vertex at the same time) and no swap conflict (two robots exchanging vertices along the same edge in one step). Typical objectives are the sum of costs (total steps of all robots) and the makespan (the time the last robot arrives).

Finding an optimal solution is NP-hard in general, and three families of methods dominate. Coupled search plans all robots together in their joint state space: complete and optimal, but the joint space grows exponentially with the number of robots. Prioritised planning plans the robots one at a time in some priority order, each treating the paths of those before it as moving obstacles (a reservation table in space and time): fast and often good, but incomplete: it can fail on problems that have solutions. Conflict-based search (CBS) sits between them. The program shows why, on two robots that must swap ends of a one-lane corridor with a single passing bay.

ABA's goalB's goalpassing bay
Two robots must swap the ends of a one-lane corridor that has a single passing bay below its middle. Their shortest paths collide in the middle. One robot must wait in the bay while the other passes, and only a planner that considers both robots together, or revisits the first robot's plan, finds that.
python
from collections import deque

grid = ["#########",
        "#.......#",          # a one-lane corridor ...
        "####.####",          # ... with a single passing bay below its middle
        "#########"]
free = {(r, c) for r, row in enumerate(grid) for c, ch in enumerate(row) if ch == "."}
MOVES = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]              # wait, or step to a neighbouring cell
start = {"A": (1, 1), "B": (1, 7)}
goal = {"A": (1, 7), "B": (1, 1)}                               # the two robots must swap ends

def neighbours(p):
    return [(p[0] + dr, p[1] + dc) for dr, dc in MOVES if (p[0] + dr, p[1] + dc) in free]

def at(path, t):
    return path[min(t, len(path) - 1)]                          # a robot that has arrived waits at its goal

def first_conflict(pa, pb):
    for t in range(max(len(pa), len(pb))):
        if at(pa, t) == at(pb, t):
            return ("vertex", at(pa, t), t)
        if t > 0 and at(pa, t) == at(pb, t - 1) and at(pb, t) == at(pa, t - 1):
            return ("swap", (at(pa, t - 1), at(pa, t)), t)
    return None

def plan(s, g, reserved=None, horizon=40):
    """Breadth-first search in space-time, avoiding another robot's reserved path (if any)."""
    def blocked(p, q, t):                                       # moving p -> q, arriving at time t
        return bool(reserved) and (q == at(reserved, t) or (q == at(reserved, t - 1) and p == at(reserved, t)))
    queue, parent = deque([(s, 0)]), {(s, 0): None}
    while queue:
        p, t = queue.popleft()
        if p == g and all(at(reserved, u) != g for u in range(t, horizon) if reserved):   # can stay there for good
            path, node = [], (p, t)
            while node:
                path.append(node[0])
                node = parent[node]
            return path[::-1]
        if t == horizon:
            continue
        for q in neighbours(p):
            if (q, t + 1) not in parent and not blocked(p, q, t + 1):
                parent[(q, t + 1)] = (p, t)
                queue.append((q, t + 1))
    return None

def joint_plan():
    """Breadth-first search over both robots together: complete and optimal, but exponential in robots."""
    s = (start["A"], start["B"])
    queue, parent = deque([s]), {s: None}
    while queue:
        a, b = queue.popleft()
        if (a, b) == (goal["A"], goal["B"]):
            path, node = [], (a, b)
            while node:
                path.append(node)
                node = parent[node]
            return [p[0] for p in path[::-1]], [p[1] for p in path[::-1]]
        for qa in neighbours(a):
            for qb in neighbours(b):
                if qa == qb or (qa == b and qb == a) or (qa, qb) in parent:
                    continue
                parent[(qa, qb)] = (a, b)
                queue.append((qa, qb))
    return None

pa, pb = plan(start["A"], goal["A"]), plan(start["B"], goal["B"])
print("independent shortest paths:", len(pa) - 1, "and", len(pb) - 1, "steps; first conflict:", first_conflict(pa, pb))
for first, second in [("A", "B"), ("B", "A")]:
    p1 = plan(start[first], goal[first])
    p2 = plan(start[second], goal[second], reserved=p1)
    print(f"prioritised, {first} plans first: {second} " + ("finds a path" if p2 else "finds NO path"))
ja, jb = joint_plan()
print("joint search finds a plan with", len(ja) - 1, "steps; conflicts:", first_conflict(ja, jb))
for t in range(len(ja)):
    rows = [list(row) for row in grid]
    rows[ja[t][0]][ja[t][1]] = "A"
    rows[jb[t][0]][jb[t][1]] = "B"
    print(f"t={t}: " + "".join(rows[1]) + "   bay: " + rows[2][4])
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Planned independently, each robot takes 6 steps and they collide in the middle cell at t=3t = 3. Prioritised planning fails whichever robot goes first: the first robot plans its shortest path without a thought for the other, and that path leaves the second no way out, since it cannot reach the bay before the first robot passes it. A solution exists, though: the joint search finds one in 8 steps, in which A waits one step at its start, B ducks into the bay at t=4t = 4, and both then carry on.

Conflict-based search, introduced by Sharon, Stern, Felner and Sturtevant in 2015, finds such solutions without searching the joint space. It plans each robot alone, then looks for the first conflict between their paths, here A and B both at the middle cell at t=3t = 3. It resolves the conflict by branching into two subproblems: in one, A is forbidden from that cell at that time; in the other, B is. In each branch only the constrained robot replans, still alone but now obeying its constraints, and the search continues, best first by total cost, until a branch has no conflicts. The result is optimal, and because conflicts in real maps are usually few, it explores far less than joint search. Its descendants, with bounded suboptimality and better heuristics, solve problems with hundreds of robots, and lifelong MAPF, where robots receive new goals as they finish old ones, is the version that warehouses need.

ExplanationH

Warehouse fleets and communication limits

The largest multi-robot systems in daily use are in warehouses. Kiva Systems, founded in the United States in 2003, built robots that drive under shelving pods and carry them to people who pick items; Amazon bought the company in 2012, and in 2025 said it had deployed more than a million robots across its operations. Other designs put robots on top of a grid of stacked crates, digging out the crate they need, as in Ocado's systems in the United Kingdom and AutoStore's from Norway; others carry totes or cases, as from Geek+ and Hai Robotics in China and from GreyOrange and Addverb, both founded in India. All of them solve the problems of this lesson continuously, at scale: allocating orders to robots and stations, lifelong path finding on a grid or a road map with reservations, charging schedules, and traffic management to prevent deadlocks.

These fleets are hierarchical. A central fleet manager assigns tasks and reserves space and time on the map, because the warehouse is a controlled environment with good wireless coverage and the central plan is far better than local negotiation; each robot follows its reservations, measures its own position (often from floor markers) and stops for anything unexpected. Standards let different vendors' robots share a site: VDA 5050, from the German automotive and engineering associations, defines messages between vehicles and a master controller, and the open-source Open-RMF, developed with support from Singapore, lets fleets from different makers share corridors, doors and lifts. When coordination fails, the consequences are physical: Ocado reported that a fire at its Erith warehouse in 2021 began after three robots collided on the grid.

Communication limits shape every design. Bandwidth limits what robots can share (summaries and maps, not raw sensor streams), latency limits how tightly they can coordinate, range limits who can talk to whom, and messages are lost. Outdoors and underground, communication is the main constraint. In DARPA's Subterranean Challenge (2018–2021), teams sent mixed fleets of legged, wheeled and flying robots into tunnels, caves and an urban underground, dropping radio relays as they went and letting robots explore alone out of contact, returning to share maps when they could; the winning team, CERBERUS, an international consortium including ETH Zurich and NTNU, combined ANYmal quadrupeds with flying robots. Designing for intermittent communication (robots that keep working safely when alone and merge their knowledge when they meet) is one of the field's central challenges, from search and rescue to planetary exploration.

Note

Trying it safely. Multi-robot ideas are ideal for simulation: the programs above, ROS 2 with several simulated robots in Gazebo, or a MAPF benchmark from the Stern et al. paper. With real hardware, start with a few small, slow, battery-powered robots on a table or floor marked out for them, each with its own stop button, and test that every robot stops safely when it loses contact with the others. Industrial fleets are segregated from people or certified to work near them, for good reason.

Common misconceptionsH

Common misconceptions

Misconception

"Twice the robots, twice the work." Interference grows with density: robots wait for each other in aisles and at stations, and planners slow down. Warehouses tune the number of robots per area, and past a point adding robots reduces throughput.

Misconception

"Decentralised is always more robust than centralised." A decentralised system has no single point of failure, but it can still fail as a whole: a disconnected communication graph never reaches consensus, as the program showed, and local rules can produce deadlocks or oscillations that no individual robot notices.

Misconception

"If every robot follows its own shortest path and avoids collisions locally, the team will be fine." In tight spaces, purely local collision avoidance produces deadlocks: two robots facing each other in a corridor each wait for the other forever. That is why warehouses plan in space and time, and why MAPF exists.

Misconception

"Prioritised planning finds a solution whenever one exists." It is incomplete: the corridor example has a solution, and prioritised planning fails in both orders because the first robot's plan ignores the second. Complete methods must be willing to change any robot's plan.

Exercises

Exercises

1. Multi-robot systems

Warm-upHuman

Two robots on a straight track: R1R_1 starts at position 0 m and R2R_2 at 10 m. Three tasks are at 2 m, 5 m and 9 m. Run a sequential single-item auction: in each round, every robot bids, for each unassigned task, the extra distance it would add to its route by inserting the task at the best place (robots do not return to their starts); the single lowest bid wins. After all three tasks are assigned, what is the total distance the two robots travel, in metres?

2. Multi-robot systems

CoreHuman

Four robots communicate in a ring (each hears exactly two others) and run the consensus protocol x←x−εLxx \leftarrow x - \varepsilon L x with ε=0.25\varepsilon = 0.25. The Laplacian of a 4-ring has eigenvalues 0,2,2,40, 2, 2, 4. What is the smallest number of steps that is guaranteed to shrink the robots' disagreement (the distance of xx from the average) by a factor of at least 1000, whatever the starting values?

3. Multi-robot systems

Warm-upHuman

Six robots run the rendezvous protocol, but robots 1–3 can hear only each other and robots 4–6 can hear only each other. What happens?

Choose one

4. Multi-robot systems

CoreHuman

In the lesson's corridor, prioritised planning failed in both orders although a solution exists. What is the underlying reason?

Choose one

5. Multi-robot systems

CoreHuman

Which statements about coordination architectures are correct? Select all that apply.

Choose all that apply

6. Multi-robot systems

CoreComputational

Write consensus_step(x, edges, eps). x is a NumPy array with one row (or one number) per robot, and edges is a list of undirected links (i, j). Return the new values after one step of the consensus protocol, in which every robot moves towards each neighbour it hears:

xi←xi+ε∑j∈Ni(xj−xi).x_i \leftarrow x_i + \varepsilon\sum_{j \in N_i}(x_j - x_i).

All robots update simultaneously, using the old values.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Multi-robot systems

CoreComputational

Conflict-based search starts by finding the first conflict between paths. Write first_conflict(path_a, path_b). Each path is a list of grid cells, one per time step, starting at t=0t = 0; a robot that has reached the end of its path waits at its last cell for ever. Return ("vertex", t) if both robots are in the same cell at time tt, ("swap", t) if they exchange cells between t−1t - 1 and tt, for the earliest such tt (vertex first if both happen at the same tt), or None if the paths never conflict. A robot moving into the cell the other has just left is not a conflict.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources