Multi-Agent Path Finding (MAPF)

MAPF algorithms are fundamentally categorized by their architectural approach to coordination.

• Centralized Planning: A single planner computes paths for all agents simultaneously in a joint state space. This approach, used by algorithms like Multi-Agent A (MAA)** and Conflict-Based Search (CBS), guarantees optimality and completeness but scales exponentially with the number of agents.
• Decoupled Planning: Agents plan paths independently, often with coordination rules. Methods like Priority Planning or Velocity Obstacle (VO)-based approaches are more scalable but may sacrifice solution quality or completeness guarantees.

The quality of a MAPF solution is measured against specific optimality criteria, which often present a trade-off.

• Makespan: The total time until the last agent reaches its goal. Minimizing makespan is critical for synchronized operations.
• Sum of Costs (SOC) / Flowtime: The sum of each agent's individual path cost (e.g., travel time). Minimizing SOC reduces total fleet effort and energy consumption.
• Bounded Suboptimal Search: Many practical algorithms sacrifice guaranteed optimality for speed, providing solutions within a known factor (e.g., 1.1x) of the optimal cost.

Collisions are formally defined by the type of spatio-temporal overlap between agent plans.

• Vertex Conflict: Two agents occupy the same location at the same timestep.
• Edge Conflict: Two agents traverse the same edge in opposite directions simultaneously.
• Cardinal Conflict: The most severe conflict type, where resolving it (e.g., by making one agent wait) inevitably increases the sum of costs for the involved agents. Identifying cardinal conflicts allows algorithms like CBS to prune the search space efficiently.

A core distinction in MAPF modeling is whether time is an explicit dimension.

• Space-Time Planning: Algorithms like Space-Time A* or those using a Time-Expanded Graph model time explicitly, planning which agent is where and when. This is necessary for environments with dynamic obstacles or strict scheduling.
• Pure Geometric Planning: Focuses only on spatial paths. Coordination is handled via speed assignment or reactive rules. This is simpler but less suitable for tightly synchronized operations.
• Safe Interval Path Planning (SIPP) offers a middle ground by compressing time into intervals where a location is continuously safe.

A fundamental tension in MAPF algorithm design.

• Completeness: An algorithm is complete if it guarantees to find a solution if one exists, or report failure otherwise. Optimal algorithms like MAA* and CBS are complete.
• Scalability: As the number of agents grows, the joint state space explodes. Subdimensional Expansion and Independence Detection (ID) are techniques to improve scalability by limiting joint search.
• Suboptimal Algorithms: Scalable algorithms like Windowed Hierarchical Cooperative A (WHCA)** sacrifice completeness and optimality to solve large-scale problems in real-time, making them essential for practical deployment.

MAPF problems vary based on when tasks are known and the planning horizon.

• Classical (Offline) MAPF: All agent start and goal positions are known upfront. Planning occurs once before execution.
• Online MAPF: New agents or tasks may appear during execution, requiring Real-Time Replanning Engines.
• Lifelong MAPF (LMAPF): Agents are continuously assigned new tasks as soon as they finish old ones, simulating persistent operation in a warehouse or factory. This requires integrating MAPF with Dynamic Task Allocation and robust Deadlock Detection and Recovery systems.

Makespan is the total time elapsed from the start of execution until the last agent in the fleet reaches its goal. It measures the overall completion time of the multi-agent plan.

• Primary Use: Evaluates throughput and system latency. Critical for time-sensitive operations like just-in-time manufacturing or emergency response.
• Calculation: Makespan = max(agent_finish_time) - start_time.
• Trade-off: Minimizing makespan often requires agents to move in parallel, which can increase the complexity of finding collision-free paths and may lead to higher computational costs.

Sum of Costs (SOC), also called Flowtime, is the sum of the path lengths (or travel times) for all individual agents from their start to their goal locations.

• Primary Use: Measures the total resource consumption or cumulative delay experienced by the fleet. It is the standard optimality criterion in classical MAPF literature.
• Calculation: SOC = Σ (path_length_i) for all agents i.
• Key Insight: Minimizing SOC often leads to more "selfish" agent behavior, as each agent seeks its shortest path, potentially creating more conflicts that the algorithm must resolve. It is distinct from makespan; a low SOC does not guarantee a low makespan.

CPU Time and Memory Usage are computational efficiency metrics that measure the resources required by the MAPF solver to find a solution.

• CPU Time: The actual computation time (in seconds or milliseconds) the algorithm takes to return a plan. This is critical for real-time applications where planning must occur within strict time windows.
• Memory Usage: The peak RAM consumption during the search process. Optimal algorithms like CBS and ICTS can have exponential memory requirements in the worst case, limiting scalability.
• Context: These metrics are typically reported alongside solution quality (makespan, SOC) to provide a full cost-benefit analysis of an algorithm. Suboptimal or windowed algorithms (e.g., WHCA*) often trade a small increase in solution cost for orders-of-magnitude reductions in CPU time.

Success Rate is the percentage of problem instances for which an algorithm finds a valid, collision-free solution within a given time or memory limit. Scalability refers to how the algorithm's performance degrades as the number of agents or environment complexity increases.

• Success Rate: A fundamental metric for completeness. An algorithm with a 100% success rate is "complete." In practice, optimal algorithms may time out on large instances, resulting in a lower success rate.
• Scalability: Evaluated by plotting solution cost and CPU time against increasing agent density (agents per square meter). Algorithms using decoupled or subdimensional approaches typically scale to hundreds or thousands of agents, while optimal coupled planners are often limited to tens of agents.
• Benchmarking: Standardized benchmarks like movingai.com or specific warehouse layouts are used to measure these metrics consistently across different algorithms.

k-Robustness is a robustness metric that enforces a temporal separation of at least k time steps between any two agents at any location. It provides a buffer against execution delays and timing uncertainties.

• Mechanism: A k-robust plan ensures that if an agent is delayed by up to k time steps, it will not collide with any other agent adhering to its planned schedule. This is stricter than standard collision avoidance.
• Trade-off: Increasing k (e.g., from 0 to 2) improves execution safety but typically increases the makespan and SOC, as agents must wait longer or take longer detours to maintain the separation buffer.
• Application: Essential for deploying MAPF solutions with physical robots that have imperfect control and localization, or in environments with dynamic, unpredicted obstacles.

Plan Execution Deviation measures the difference between the planned paths and the actual trajectories followed by physical agents, quantifying the real-world fidelity of the MAPF solution.

• Causes of Deviation: Control error, localization drift, unexpected delays (e.g., wheel slip), and the presence of dynamic obstacles not included in the planning model.
• Measurement: Often calculated as the average positional error over time or the rate of reactive collision avoidance interventions (e.g., emergency stops) required during execution.
• Implication: High deviation necessitates either more robust planning (see k-Robustness), tighter low-level control, or a real-time replanning layer to adjust plans based on observed state. This metric bridges the gap between discrete algorithmic planning and continuous physical execution.

A two-level, optimal search algorithm for MAPF. At the high level, a constraint tree is searched where each node contains a set of constraints imposed to resolve conflicts between agents. At the low level, a fast single-agent planner (like A*) finds paths for each agent that satisfy the current constraints. The algorithm systematically explores constraint combinations until a conflict-free solution is found.

• Core Mechanism: Resolves conflicts by imposing constraints (e.g., "Agent A cannot be at vertex V at time T") and replanning.
• Optimality: Guarantees finding a solution that minimizes the sum of costs (SOC) or makespan, if one exists.
• Scalability Challenge: The constraint tree can grow exponentially with the number of agents and conflicts.

A centralized, optimal algorithm that performs an A* search in the joint state space of all agents. Each state in this space is a tuple containing the location of every agent (e.g., (pos_agent1, pos_agent2, ..., pos_agent_k)). The search expands this massive state space to find a sequence of joint moves that leads all agents to their goals.

• State Space Complexity: The search space size is O(v^k), where v is the number of vertices and k is the number of agents, leading to extreme scalability limits.
• Optimality: Finds the optimal solution relative to the chosen heuristic.
• Foundation: Serves as the theoretical baseline for optimal MAPF; most advanced algorithms are designed to avoid searching this full joint space.

A pair of concepts for local, reactive collision avoidance, often used in continuous spaces or as a low-level safety layer. They are typically decoupled from global MAPF planning.

• Velocity Obstacle (VO): A geometric construct. For a given agent, the VO defines the set of all its possible velocities that would cause a collision with another moving object within a specified time window (τ). The agent simply chooses any velocity outside this set.
• Optimal Reciprocal Collision Avoidance (ORCA): An efficient, distributed algorithm based on VO. Each agent assumes reciprocal responsibility and selects the velocity closest to its preferred velocity from the set of mutually collision-free velocities. This enables smooth, oscillation-free navigation in dense crowds.

Key techniques for planning in dynamic environments where time is an explicit dimension.

• Space-Time A*: An extension of A* where each search node is a (location, time) pair. This allows the planner to find paths that avoid reservations made by other agents or dynamic obstacles at specific times.
• Time-Expanded Graph (TEG): A modeling method that converts a temporal planning problem into a static graph search. The original graph is replicated for each discrete time step (0, 1, 2,...T). A "wait" action is represented by an edge from node (v, t) to (v, t+1). A path in the TEG corresponds to a space-time trajectory.

Fundamental concepts for conflict classification and solution evaluation in MAPF.

• Cardinal Conflict: The most severe type of conflict between two agents. Resolving it (by making one agent wait or detour) unavoidably increases the sum of both agents' path costs. Detecting cardinal conflicts is crucial for algorithms like CBS, as they often require branching.
• Sum of Costs (SOC): The primary optimality metric for MAPF. It is calculated as the sum of the path lengths (or travel times) for all individual agents from their start to their goal. Minimizing SOC is the objective of most optimal MAPF algorithms. Flowtime is an equivalent metric.

A dynamic variant of MAPF where agents are continuously assigned new tasks upon completing their current ones, simulating persistent operation in warehouses or fulfillment centers. This requires online planning where new paths must be computed in real-time without disrupting the execution of existing plans.

• Key Challenge: Balancing optimality with replanning speed and stability (avoiding excessive changes to in-progress paths).
• Common Approach: Uses windowed planning (e.g., WHCA*), where paths are planned only for a short horizon and are periodically replanned as agents approach the end of their planned window.
• Distinction: Contrasts with one-shot MAPF, which solves for a single set of start-goal pairs.