[2605.07744] Alternating Target-Path Planning for Scalable Multi-Agent Coordination

Computer Science > Artificial Intelligence arXiv:2605.07744 (cs) [Submitted on 8 May 2026] Title:Alternating Target-Path Planning for Scalable Multi-Agent Coordination Authors:Yu Kumagai, Keisuke Okumura View a PDF of the paper titled Alternating Target-Path Planning for Scalable Multi-Agent Coordination, by Yu Kumagai and 1 other authors View PDF HTML (experimental) Abstract: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. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.07744 ...