Fast and Scalable Rule-Based Search for Deadline-Constrained Anonymous Multi-Agent Path Finding

Abstract

Anonymous Multi-Agent Path Finding (AMAPF) requires coordinating a set of interchangeable agents to reach a set of target locations. In the variant with Individual Deadlines (AMAPFwID), each target must be reached before a specified time limit. Although AMAPFwID is solvable in polynomial time, state-of-the-art approaches rely on max-flow computations over time-expanded networks, whose size grows quadratically with the workspace. This makes them computationally impractical for large-scale instances involving thousands of agents. We introduce DART (Deadline-Aware Rapid Target-swapping), a highly scalable rule-based framework for AMAPFwID. The method decomposes the problem into two integrated phases: (1) a Task Assignment Phase, using either Bottleneck Assignment with Cost Refinement (BACR) or Deadline-Aware Assignment with Conflict Refinement (DACR) to produce initial pairings; and (2) a Reactive Search Phase, which employs seven deterministic motion rules to resolve local spatio-temporal conflicts. A key component of the approach is an Excess Time heuristic that prioritizes agents based on their temporal slack, guiding the search toward deadline-feasible configurations. We provide a theoretical analysis of correctness and test DART on standard MAPF benchmarks. The results show that DART scales to maps with thousands of agents, reducing runtime by several orders of magnitude compared to the optimal solver while maintaining near-optimal solution quality (around 1.01 times the optimal sum-of-moves).