ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search
Authors: Yimin Tang, Han Zhang, Shao-Hung Chan, Junsoo Kim, Erdem Bıyık, Sven Koenig, Jingkai Chen
Organizations: Thomas Lord Department of Computer Science, University of Southern California · Symbotic · Department of Computer Science, University of California Irvine
Combined Target Assignment and Path Finding (TAPF) requires assigning targets for agents while simultaneously planning collision-free paths. We present ITA-LaCAM, a complete and scalable TAPF solver inspired by LaCAM and ITA-CBS. In ITA-LaCAM, each joint-configuration node carries an agent-to-target matching. When a successor is generated, ITA-LaCAM incrementally repairs the matching for the agents that moved and uses the targets to guide PIBT successor generation. This design enables adaptive reassignment without explicitly enumerating the combinatorial assignment space, while preserving LaCAM's completeness and scalability. Across 9,760 benchmark instances on eight maps with 5--200 agents, ITA-LaCAM solved 100% of the instances, compared with 95.6% for IR-TAPF configured with DBS-Hungarian. ITA-LaCAM found an initial solution faster in 84.0% of the comparisons and achieved a lower sum of costs in 65.0% of the instances solved by both methods.
Figures & tables
Figure 1: The eight benchmark maps used in our experiments.
Figure 2: Group Test success rates over 20 instances per point with a 10-second limit. ITA-LaCAM, IR-TAPF, and ITA-CBS solve 100%, 94.9%, and 15.9% of the 3,200 instances, respectively.
Algorithm 2 Procedure PIBT with Swap
Figure 3: Common Target Test success rates over 20 instances per point with a 10-second limit. ITA-LaCAM, IR-TAPF, and ITA-CBS solve 100%, 96.0%, and 67.8% of 6,560 instances; IR-TAPF’s rate drops to 84.6% when all additional targets are shared.
Figure 4: First-solution times on all 9,760 instances; IR-TAPF failures appear on the right boundary ( x=10 s). Points below the diagonal favor ITA-LaCAM, which is faster on 84.0% of instances, versus 15.2% for IR-TAPF and 0.8% ties.
Figure 5: Paired SOC on 9,335 instances (ITA-LaCAM lower: 65.0%; overall median ratio: 1.020). The curve shows the median ratio among instances with similar IR-TAPF SOC.
Figure 6: Paired SOC on 4,955 instances (ITA-CBS lower: 67.7%; overall median ratio: 1.016). The curve shows the median ratio among instances with similar ITA-CBS SOC.
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.
Yu Kumagai, Keisuke Okumura
1Hitotsubashi University, Japan · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
Multi-Agent Path Finding (MAPF) aims to compute collision-free paths for multiple agents and has a wide range of practical applications. LaCAM*, an anytime configuration-based solver, currently represents the state of the art. Recent work has explored the use of guidance paths to steer LaCAM* toward configurations that avoid traffic congestion, thereby improving solution quality. However, existing approaches rely on Frank-Wolfe-style optimization that repeatedly invokes single-agent search before executing LaCAM*, resulting in substantial computational overhead for large-scale problems. Moreover, the guidance path is static and primarily beneficial for finding the first solution in LaCAM*. To address these limitations, we propose a new approach that leverages LaCAM*'s ability to construct a dynamic, lightweight traffic map during its search. Experimental results demonstrate that our method achieves higher solution quality than state-of-the-art guidance-path approaches across two MAPF variants.
Bojie Shen, Yue Zhang, Zhe Chen +1
Monash University, Faculty of Information Technology
Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy ordering relations when task sequences are fixed in advance. In many applications, however, solution quality depends not only on how agents move, but also on which agent performs which task. This motivates the lifted problem of task assignment and path finding with precedence constraints (TAPF-PC), which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost. To address the resulting coupled TAPF-PC search space, we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibility within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints.