Alternating Target-Path Planning for Scalable Multi-Agent Coordination
This work addresses the scalability bottleneck in multi-agent coordination for large-scale TAPF, offering a practical solution for real-world setups.
The paper tackles the concurrent target assignment and pathfinding (TAPF) problem, proposing an iterative refinement framework that decouples target assignment from pathfinding using fast suboptimal MAPF solvers. The framework scales beyond state-of-the-art CBS-based solvers while maintaining decent solution quality.
The concurrent target assignment and pathfinding (TAPF) problem extends multi-agent pathfinding (MAPF) by asking planners to allocate distinct targets and collision-free paths to agents. Prior work on TAPF has relied exclusively on Conflict-Based Search (CBS), which tightly couples target assignment and pathfinding, resulting in compute-intensive, non-scalable solutions. In contrast, we propose an iterative refinement framework that decouples target assignment from pathfinding. Our framework builds on modern, fast, suboptimal MAPF solvers, such as LaCAM. Specifically, within a given time budget, it repeatedly solves MAPF for the current target assignment, identifies bottleneck agents via MAPF feedback, and refines the assignment. Empirical results show that feedback-driven reassignment loop is effective, enabling our framework to scale well beyond the reach of the state-of-the-art CBS-based solver while maintaining decent solution quality. This represents a solid step toward practical, large scale TAPF suitable for real-world setups.