Multi-Agent Path Finding (MAPF)

In MAPF, each agent operates as an independent entity with its own start and goal configuration, but all agents move within a shared spatial environment, typically represented as a graph or grid. This creates the core tension: agents' paths must be planned interdependently to avoid conflicts, but each agent's objective is distinct. The environment is often static for the planning horizon, meaning obstacles are known and fixed, though the agents themselves are dynamic obstacles to each other.

A valid MAPF solution must produce collision-free paths. Collisions are strictly defined to enable algorithmic reasoning:

• Vertex Conflict: Two agents occupy the same location (vertex) at the same timestep.
• Edge Conflict: Two agents traverse the same edge in opposite directions simultaneously.
• Following Conflict: An agent moves into a vertex currently occupied by another agent (often treated as a vertex conflict at the next timestep). Some formulations also consider k-robust plans, where agents maintain a temporal buffer of k timesteps between uses of the same vertex, adding robustness to execution timing errors.

MAPF algorithms optimize for a global objective function. The most common are:

• Sum of Costs (SoC): Minimizes the total number of timesteps all agents take to reach their goals (including wait actions). This is the standard makespan for the fleet.
• Makespan: Minimizes the time until the last agent reaches its goal. This focuses on overall completion time.
• Flowtime: Similar to SoC, but often refers to minimizing the sum of individual path lengths excluding waits. The choice of objective significantly influences algorithm design and solution quality, with SoC being the most prevalent in literature.

MAPF problems are categorized by their underlying assumptions, which dictate algorithmic approaches:

• Classic MAPF: Agents occupy single vertices, move synchronously in discrete timesteps (wait, move to adjacent vertex), and actions are deterministic.
• Lifelong MAPF: Agents are assigned continuous streams of tasks; planning focuses on efficient throughput rather than one-time goals.
• Anonymous MAPF: Agents are interchangeable; any agent can fulfill any goal.
• Kinodynamic MAPF: Incorporates kinematic (e.g., non-holonomic) and dynamic (e.g., acceleration) constraints, requiring continuous state-space planning.
• Online MAPF: The environment or task set changes dynamically during execution, requiring real-time replanning.

MAPF is provably computationally hard. Finding optimal (minimum sum-of-costs) paths for multiple agents on a graph is NP-hard, even for simple grid worlds. This means solution time can grow exponentially with the number of agents, making optimal solvers impractical for large fleets. Consequently, the field is divided between:

• Optimal Solvers: Like Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), which guarantee optimality but scale to dozens of agents.
• Suboptimal/Bounded Solvers: Like Priority-Based Search and Windowed Hierarchical Cooperative A*, which sacrifice guaranteed optimality for polynomial-time scaling to hundreds of agents.

A fundamental architectural split in MAPF solutions:

• Centralized Planning: A single planner has complete global knowledge of all agent states, tasks, and the environment. It computes all paths simultaneously, enabling global optimality (e.g., CBS, MILP formulations). This is computationally intensive but guarantees conflict-free solutions.
• Decentralized Planning: Each agent plans its own path, typically using local sensing or communication (e.g., Optimal Reciprocal Collision Avoidance (ORCA)). This scales well and is robust to dynamic changes but can lead to local deadlocks (e.g., the symmetric dilemma) and does not guarantee global optimality. Hybrid approaches, like decentralized planning with periodic centralized resolution, are common in practice.

MAPF algorithms coordinate fleets of Autonomous Mobile Robots (AMRs) and Automated Guided Vehicles (AGVs) to transport goods from storage to packing stations. This system optimizes pick-and-place operations by:

• Calculating parallel, non-conflicting routes for hundreds of robots.
• Dynamically rerouting around human workers, fallen items, or disabled agents.
• Minimizing the makespan (total time to complete all retrieval tasks). Major logistics providers use MAPF to achieve sub-5-minute order turnaround times, directly increasing throughput.

In automated parking structures and container ports, MAPF schedules the movement of driverless vehicles within confined, highly structured grids. The system must solve a dense routing problem where:

• Each vehicle must navigate to a precise parking stall or loading bay.
• Reversing maneuvers and tight turns are constrained.
• The goal is to maximize space utilization while ensuring all vehicles can eventually exit. This application reduces human labor and minimizes damage by eliminating tight, error-prone manual driving.

Teams of drones or ground robots use decentralized MAPF variants to collaboratively explore unknown or hazardous environments. Key challenges include:

• Planning under partial observability where the map is discovered in real-time.
• Balancing coverage versus coordination to avoid redundant search paths.
• Incorporating communication constraints that may limit real-time coordination. In search and rescue, this allows robots to systematically clear a collapsed structure, sharing location data to pinpoint survivors faster than a single agent could.

MAPF principles underpin next-generation air traffic management for Urban Air Mobility (UAM) and drone delivery swarms. The problem scales to 3D space with strict separation assurance requirements. Algorithms must:

• Plan conflict-free 4D trajectories (including time) in a continuous airspace.
• Handle dynamic airspace constraints like temporary flight restrictions or weather.
• Optimize for fuel efficiency and minimal delays. This ensures safe, scalable operations for hundreds of aircraft in shared low-altitude corridors.

Within hospitals, MAPF coordinates a heterogeneous fleet delivering meals, linens, lab samples, and medications. This environment introduces unique constraints:

• Static and dynamic priorities: An emergency medication delivery must preempt routine laundry transport.
• Sterile zone management: Certain corridors near operating rooms have restricted access.
• Shared infrastructure: Robots must coordinate with elevators and automated doors. Successful deployment reduces staff burden on non-clinical tasks and improves delivery reliability.

In chip manufacturing, an Automated Material Handling System (AMHS) uses MAPF to transport wafer cassettes between hundreds of process tools. This is a high-stakes application where:

• Cleanroom contamination and vibration avoidance are critical constraints.
• Tool starvation (a tool waiting for a wafer) costs millions in lost throughput.
• The system must be deadlock-free and guarantee delivery within strict time windows. Optimal MAPF here directly increases fab yield and capital tool utilization.

Space-Time A* is a search algorithm that extends the classic A* algorithm by treating time as an explicit dimension. Instead of searching a 2D or 3D grid, it searches a 3D or 4D space-time grid. This allows the planner to account for the future positions of dynamic obstacles (including other agents with known trajectories). A state is defined as (x, y, t). This method is crucial for planning with dynamic constraints and is often used as the low-level planner in hierarchical MAPF frameworks like CBS. It guarantees a collision-free path if one exists within the searched horizon.

Model Predictive Control is an advanced receding horizon control strategy used for real-time trajectory optimization. At each control cycle, MPC solves a finite-time optimal control problem over a short prediction horizon, using a dynamic model of the agent (and often other agents) to predict future states. It optimizes a cost function (e.g., path deviation, control effort) subject to constraints (e.g., collision avoidance, dynamics). Only the first control action of the optimized sequence is executed before the horizon shifts forward and the process repeats. This makes MPC exceptionally robust for handling disturbances and model inaccuracies in dynamic MAPF scenarios.

Kinodynamic planning is the problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic constraints like a car's turning radius) and dynamic constraints (e.g., acceleration, torque, and velocity limits). Standard MAPF often assumes simple point-mass agents or discrete moves. Kinodynamic planning addresses the reality of physical robots, requiring smooth, dynamically feasible trajectories. Algorithms like state lattice planners or optimization-based methods (e.g., Timed Elastic Bands) are used. This is critical for heterogeneous fleet orchestration, where different vehicle types (forklifts, AMRs, AGVs) have unique motion models that must be respected in shared space.