Multi-Agent Path Finding (MAPF)

MAPF solvers are categorized by their planning architecture. Decoupled planners compute paths for each agent independently and then resolve conflicts, which is fast but often suboptimal. Coupled planners treat the entire fleet as a single, high-dimensional system, guaranteeing completeness and optimality at the cost of exponential state-space explosion. Modern approaches often use prioritized planning, where agents plan sequentially, treating previously planned agents as dynamic obstacles.

The objective function fundamentally shapes the resulting fleet behavior. Makespan minimizes the time until the last agent reaches its goal, optimizing for overall task completion. Sum-of-costs minimizes the total number of timesteps taken by all agents, which is equivalent to minimizing total energy consumption. A third common objective is minimizing service time, the sum of each agent's individual completion time.

MAPF defines specific collision types that must be resolved:

• Vertex Conflict: Two agents occupy the same node at the same timestep.
• Edge Conflict: Two agents traverse the same edge in opposite directions at the same timestep.
• Following Conflict: One agent moves into a node just vacated by another, which is safe in vertex/edge models but not when agents have a physical volume.
• Cycle Deadlock: A set of agents wait for each other in a cyclic dependency, requiring global coordination to resolve.

CBS is a seminal optimal MAPF algorithm that operates on two levels. The high-level search builds a constraint tree where each node imposes a constraint on a single agent (e.g., 'Agent A cannot be at location X at time T'). The low-level search computes a shortest path for each agent respecting its constraints. When a conflict is found between two paths, the node is split into two children, each adding a new constraint to resolve the conflict.

Classic MAPF operates on a discrete graph where agents move one edge per timestep. Real-world robots require kinodynamic MAPF, which incorporates velocity and acceleration limits. This is often handled by a post-processing step where a discrete path is converted into a smooth, executable trajectory using splines, or by planning directly in a state lattice that encodes kinematic constraints into the graph edges.

Standard MAPF assumes a one-shot problem where agents start, reach goals, and stop. Lifelong MAPF addresses the realistic scenario where agents are continuously assigned new goals. As soon as an agent reaches its destination, it receives a new task. This requires algorithms that can interleave execution with replanning, often using windowed approaches that plan for a finite horizon and use a rule-based policy to handle the infinite tail.

The mathematical foundation of all motion planning. C-Space transforms a robot with volume and orientation into a single point in a high-dimensional space, where each axis represents a degree of freedom. Obstacles are mapped into this space as C-obstacles, reducing the path planning problem to finding a continuous curve for a point through free space. For MAPF, the joint C-Space of all agents becomes exponentially large, motivating decoupled approaches.

The algorithmic guarantee that planned motions will not intersect with static obstacles or other dynamic agents. Techniques range from geometric collision detection (using algorithms like GJK for convex shapes) to velocity obstacle methods that predict future intersections. In MAPF, collision avoidance extends to agent-agent conflicts—including vertex conflicts (occupying the same cell) and edge conflicts (swapping positions simultaneously).

Motion planning that respects both kinematic constraints (e.g., joint limits) and differential dynamics (velocity, acceleration, force bounds). Unlike purely geometric path planning, kinodynamic planners generate dynamically feasible trajectories that a real robot's actuators can execute. In MAPF contexts, ignoring kinodynamics leads to plans that cause robots to overshoot turns or collide when stopping distances are underestimated.

A real-time control strategy that solves a finite-horizon optimization problem at each timestep, applying only the first control input before re-planning. MPC inherently handles multi-variable constraints and previews future states, making it ideal for dynamic obstacle avoidance. In MAPF, decentralized MPC allows each agent to continuously replan while treating other agents' predicted trajectories as moving constraints.

An integrated paradigm that bridges symbolic task reasoning with continuous motion planning. A TAMP solver determines not just how to move, but what actions to take and in what sequence—e.g., picking an object, opening a door, then placing the object. In multi-agent systems, TAMP coordinates heterogeneous robots performing interdependent subtasks, resolving deadlocks where one agent's action is a prerequisite for another's.

An asymptotically optimal sampling-based planner that accelerates convergence by restricting sampling to an ellipsoidal subset of the configuration space once an initial solution is found. This informed set contains all configurations that could improve the current path cost. For MAPF, sampling-based methods like RRT* can be extended to multi-agent scenarios by growing trees in the composite state space, though computational cost grows rapidly with agent count.