M8-T4 — Multi-Robot Path Finding

Learning objectives

After this lesson, you should be able to:

• State the MAPF problem and its two kinds of conflict: vertex and edge (swap).
• Explain planning in space and time with a reservation table, including the robot that has stopped.
• Describe prioritized planning, why it is fast, and why it can fail even when a solution exists.
• Explain in outline what conflict-based search does, and what it guarantees.

The intuition

Two people in a narrow corridor can pass if one waits in a doorway. Two robots that plan independently cannot: each sees an empty corridor and drives into it. The missing ingredient is time. A cell is not simply free or blocked; it is free or blocked at a moment. If the plan for the first robot says “cell 4 at time 7 is mine”, the second robot’s plan can use cell 4 at time 6 or at time 9, but not at time 7.

Add time as a third coordinate and the problem becomes ordinary graph search again. The state is (cell, time); moves go to a neighbouring cell at the next time step, or stay in the same cell for one step, which is waiting. Waiting is what makes it possible to let somebody pass.

Planning robots one after another is the simplest scheme: the first robot plans as if alone, the second plans around the first, the third around both. It is quick. Its weakness is that the first robot has no idea it is going to block somebody. A robot that parks in a corridor can lock out every robot planned after it.

The mathematics

The problem

G = (V, E)

the map as a graph: vertices are free cells or waypoints, edges are allowed moves

k

number of robots, each with a start s_i and a goal g_i (distinct)

π_i(t)

vertex of robot i at time step t; at each step it waits or moves along an edge

Two robots i and j are in conflict if, for some time t:

A solution is a set of paths without conflicts in which every robot ends at its goal and stays there. Two objectives are common: makespan (the time at which the last robot arrives) and sum of costs (the sum of each robot’s arrival time). Finding the best solution is NP-hard on graphs (Yu and LaValle, 2013), which is the reason the practical methods below exist. Some models forbid more, for example a robot moving into the cell another leaves in the same step (following), which is allowed or not depending on the robots’ speed and spacing.

Why not plan jointly?

Treat all robots as one system and the state is a tuple of cells: |V|^k states, and 5^k joint moves per step on a grid. For the 17-cell lobby of lab M8-L4 and three robots that is 17³ = 4 913 states per time step and 125 joint moves, against 3 × 17 = 51 and 3 × 5 = 15 when planned one at a time. Ten robots would have 5¹⁰ = 9.8 million joint moves per step.

Space-time search with reservations

Planning one robot with a reservation table: vertex reservations (cell, t) and edge reservations (from, to, t) made by robots already planned.

1. The state is (cell, time). From (v, t) the robot may go to (v, t + 1) (wait) or (u, t + 1) for each neighbour u.
2. Reject a move to (u, t + 1) if that vertex is reserved, or if the edge (u → v) is reserved at time t.
3. Search (breadth-first when every step costs one, A* with the ordinary distance as heuristic otherwise) until the goal is reached at a time after which nothing reserves the goal.
4. Reserve the whole path, and the goal cell from arrival to the end of the horizon.

Prioritized planning

Fix an order of robots (Erdmann and Lozano-Perez, 1987); plan robot 1, reserve its path, plan robot 2 around it, and so on. Silver (2005) applied the idea with space-time A* and reservation tables to games, and a windowed version (WHCA*) plans only a short horizon ahead. The method costs k single-robot searches, and it is not complete: for a given order there may be no solution although another order, or no fixed order at all, has one.

Conflict-based search

Conflict-based search (CBS; Sharon and others, 2015) has two levels. At the low level each robot is planned alone, subject to a set of constraints (“robot i may not be in v at time t”). At the high level a tree is searched, best-first by cost:

1. The root has no constraints; every robot takes its own shortest path.
2. If the paths have no conflict, return them.
3. Otherwise take one conflict (robots i and j at v, t) and make two children: one forbids v at t to robot i, the other to robot j. Replan only the robot whose constraint changed.
4. Expand the node of least total cost.

CBS is complete and returns a solution of least sum of costs. It scales to dozens of robots on open maps and slows sharply in narrow, crowded ones. Bounded-suboptimal versions trade a small increase in cost for speed.

A worked example

A swap that is not a collision on paper. In the corridor of the diagram, robot A goes 0, 1, 2, 3, 4 and robot B goes 5, 4, 3, 2, 1, 0 (a cell per time step). At t = 2 A is in cell 2 and B in cell 3; at t = 3 A is in 3 and B in 2. No vertex is shared at any whole step: the gap between the robots is 5, 3, 1, 1, 3 and 4 cells at t = 0 to 5. A checker that tests only vertices passes this plan. The robots would meet on the edge between cells 2 and 3. Stage 1 of lab M8-L4 is this bug.

The 07:40 lobby. The lobby of the lab is a 3 × 3 square with a one-cell corridor leaving each side: 17 free cells, a horizon of 24 steps. In the practice instance robot 0 starts in the west corridor at (row 3, col 1) and wants the end of the east corridor, (3, 6); robot 1 starts in the lobby at (3, 2) and wants robot 0’s start cell (3, 1); robot 2 starts at the lobby centre (3, 3) and wants the dead-end cell (3, 0) at the far end of the west corridor. A single-robot space-time graph has 17 × 25 = 425 nodes. All six priority orders give:

With order 0, 1, 2, robot 1 is planned before robot 2 and parks at (3, 1), the only cell through which robot 2’s goal (3, 0) can be reached. Nothing can pass a parked robot in a one-cell corridor, so robot 2 has no path. Only 0, 2, 1 works: robot 2 has to go into the dead end first, and robot 1 waits. The three rotations of the order (0, 1, 2; 1, 2, 0; 2, 0, 1) all fail, which is why the starter of stage 3, which tries only rotations, gives up.

The lesson is not that 0, 2, 1 is a magic order. It is that the order is a choice, that some orders are fatal, and that a planner has to be ready to try another.

Engineering implications and limitations

Plans meet reality

MAPF assumes every robot executes its plan step by step. Real robots slow down, stop for a person or lose a few seconds. A delay that breaks the timing of a plan can create the very conflicts the plan avoided. Two practical remedies are to execute with a policy that preserves the order in which robots pass each cell instead of absolute times, and to replan on a rolling horizon (module 7 and lesson M8-T5).

Reserve with margin

Plans on cells assume robots are points or at most one cell. Real robots have footprints and braking distances. Reserve with the footprint, add a time margin to every reservation, and keep a minimum gap between robots in a lane so that a following robot can stop. Large robots are modelled with several cells per robot or with swept areas on a roadmap graph.

Plan on the roadmap

For a hospital, planning on a lane graph (lesson M2-T5) is usually better than on a grid: nodes are places where a robot can wait, edges are lanes, and reservations on edges and nodes are cheap to store and to communicate. Provide places to wait (bays, niches, junctions wide enough to pass) so that “wait” is always an option for somebody.

Priorities need a rule

If priorities are fixed by robot number, a robot with an urgent delivery can end up last. Choose them by urgency, battery, distance to go or the number of alternative routes, and re-choose when plans fail. When a plan fails, try another order, plan the robots with the fewest options first, or hand the case to a complete method such as CBS for the small group involved.

Lifelong operation

Fleets do not plan once: goals keep arriving. The usual design replans each robot when it gets a new goal, against the reservations of the others, and keeps a short horizon of committed steps. Measure it as throughput and waiting time (lesson M8-T6), not only as path length.

Common misconceptions

Engineering takeaways

1. MAPF plans all robots together in space and time; conflicts are two robots at one vertex, or two robots swapping along an edge.
2. Reservation tables turn multi-robot planning into one search per robot, over (cell, time) states where waiting is a move.
3. Prioritized planning is fast and incomplete; a parked robot must stay reserved, and some priority orders are fatal.
4. Conflict-based search resolves one conflict at a time with constraints on a single robot, and returns a solution of least sum of costs.
5. Real fleets add footprints, delays and rolling horizons on top, and design the map with places to wait.

References and further reading

The prioritized-planning and conflict-based-search papers, the intractability result and a survey of definitions and variants.

• M. Erdmann and T. Lozano-Pérez, “On multiple moving objects”, Algorithmica 2(1–4), 1987.
• D. Silver, “Cooperative pathfinding”, AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2005.
• G. Sharon, R. Stern, A. Felner and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding”, Artificial Intelligence 219, 2015.
• J. Yu and S. M. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs”, AAAI Conference on Artificial Intelligence, 2013.
• R. Stern and others, “Multi-agent pathfinding: definitions, variants, and benchmarks”, Symposium on Combinatorial Search (SoCS), 2019.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: the same problem as a property of the building and the rules: deadlock, livelock and traffic management.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T3: Frontier Exploration

  Pick the next frontier to explore with a utility that balances distance and information.

• Lab
  M8-L4: Break the Deadlock

  Three robots meet at the elevator lobby at 07:40 and none will move: plan so that all of them get through.