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.