Planning motions for multiple robots at once is expensive — the joint state space grows exponentially with each robot added. This work combines two things: a sampling-based planner that grows a motion tree in the full joint space (respecting each robot’s dynamics), and a multi-agent search over a simpler roadmap that ignores dynamics. The roadmap gives cheap hints about which routes are worth trying; the motion planner does the hard work of making them physically feasible. When a robot gets stuck, the search replans around it — and together, robots coordinate to reach their goals without deadlocking each other.
The Core Problem
A centralized planner operating in the combined state space of all robots quickly becomes infeasible. Even for 3–4 robots with dynamics, exhaustive joint search is too slow for practical use.
Coordinated Expansion
Instead of expanding a motion tree jointly across all robots at once, this approach processes robots sequentially:
Expand robot i’s motion tree to follow route σᵢ, while avoiding static obstacles and the already-planned trajectories of robots 1, …, i−1.
This converts an exponential joint problem into a series of single-robot planning problems, each with a slightly larger obstacle set. The key insight is that earlier robots’ trajectories are treated as dynamic obstacles for later robots, preserving feasibility without central coordination.
Guidance via Multi-Agent Search
A discrete multi-agent search algorithm provides route assignments (σ₁, …, σₙ) before motion planning begins. This high-level plan guides the sampling-based expansion, preventing wasted computation on routes that are globally infeasible.
Results
Demonstrated on multi-robot location exchange tasks — robots must swap positions through constrained passages. The approach successfully coordinates robots in scenarios where unguided joint planning fails.
Videos
Multi-robot planning to exchange locations via a narrow tunnel