Target assignment and pathfinding (TAPF) is an appealing extension of classical multi-agent pathfinding (MAPF): each agent has a set of targets, and the planner must both assign a target to each agent and plan collision-free paths for them. A trivial approach is to compute an assignment that minimizes the total single-agent shortest-path distance over agent--target pairs, and then solve the resulting MAPF instance. However, this approach falls short because the shortest-path distance remains a proxy that ignores interference among agents. Assigning targets based on the costs agents actually pay, which depend on how every other agent is assigned and routed, would yield a better final outcome. To this end, we propose an iterative TAPF method that improves target assignments by calibrating travel cost estimates from fast, suboptimal MAPF feedback. Experiments show that our method produces solutions close to optimal on small instances and outperforms existing planners in solution quality on larger ones.
Figures & tables
Figure 1: TAPF solution quality of an interference-agnostic assignment and a calibrated cost assignment in the HOTSPOT scenario, where the targets are densely clustered in small regions of the map. Targets are assigned by a linear sum assignment on each, and paths are planned by LaCAM3 ( Okumura 2024 ) , a fast suboptimal MAPF solver.
Figure 2: Overview of TACT. (i) The cost matrix is initialized with shortest-path distances, (ii, iii) Random noise varies the target assignment. Then, (iv) MAPF plans paths for it, and (v) the observed travel losses are fed back, gradually calibrating the estimates. (ii–iv) can be executed in parallel, so each iteration feeds back several observations.
Algorithm 1 TACT
Figure 3: Evolution of the cost matrix on a 10 × 10 grid with 10 agents. Each agent is given 10 candidate targets, all at the same shortest-path distance. Each column shows one iteration: the map (top) draws the paths at that iteration, with circles as agents and squares as their assigned targets. Red paths contain delays over the shortest-path distance (waits and detours), while blue paths do not . The arrow marks agent 8, discussed in the main text. The cost matrix (bottom) shows the estimated interference cost ( C[i][v]−dist(si,v) ), with rows as agents and columns as candidate targets. Black frames mark the targets assigned at that iteration. Unobserved entries remain gray.
Figure 4: Comparison with solvers on random-32-32-10 in EQ-DIST (left) and HOTSPOT (right), evaluated over 10 instances. Instances that ITA-ECBS fails to solve within the time limit are plotted in the gray band labeled “fail.”
Figure 5: Solution quality on eight maps in EQ-DIST (top) and HOTSPOT (bottom) scenarios. Lines show the mean scores, with the semi-transparent regions indicating a standard deviation.
n
Solver
Imprv
Path
Total
Assign
LaCAM
Iter.
(%)
(%)
(%)
[ms]
[ms]
200
TACT-L3
14.7
2.4
16.7
0.21
9.7
628
D-H-L3
7.9
1.2
9.0
0.01
6.7
892
400
TACT-L3
12.2
4.3
16.0
0.36
17.1
358
D-H-L3
4.1
2.2
6.1
0.02
11.9
503
600
TACT-L3
9.4
6.9
15.6
0.52
25.5
238
Table 1: Detailed comparison of TACT-LaCAM3 (TACT-L3) and D-H-LaCAM3 (D-H-L3) on random-64-64-20 HOTSPOT . Imprv and Path denote the mean flowtime improvement (%) over the initial solution and by the final path optimization, respectively. Assign and LaCAM denote the mean runtime per iteration of the assignment step and of the LaCAM evaluation, respectively. Iter. is the mean number of iterations for target reassignment.
Figure 6: Anytime behavior of TACT, TACT with sequential evaluation (seq-TACT), and DBS-Hungarian (D-H) for a 30s budget in HOTSPOT .
Figure 7: Scalability on warehouse-20-40-10-2-2 in HOTSPOT with n=2,000 to 10,000 under a fixed 5min budget, and runtime of TACT, broken down into the target assignment and the LaCAM (log scale).
Figure 8: Effect of the feedback rate α , with the remaining parameters fixed to σ=5 and P=8 .
Figure 9: Effect of the noise scale σ (left column) and the number of parallel candidates P (right column), with feedback rate α=0.2 . The left column shows the best flowtime over the lower bound against runtime with P=8 fixed. The right column shows it against iterations with σ=5 fixed.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 10: Comparison with ITA-ECBS ( w=1.10 ) in the shared-target setting of ITA-ECBS ( Tang, Koenig, and Li 2024 ) on random-32-32-10 with K=5 . Each panel reports the flowtime over the lower bound against the percentage of shared targets, as mean over 10 instances with a time limit of 10s per solver. Shaded regions indicate the min–max range.
Figure 11: Comparison on fully random scenario.
Figure 12: Annealing of the noise scale from σ0∈{5,10,20,40} down to 1 , against the constant σ=5 , in HOTSPOT .
Figure 13: One-shot target assignment on the final calibrated cost matrix versus the best solution found during the iterations, in HOTSPOT .
Figure 14: Comparison of calibrating with the travel time and the travel loss on HOTSPOT .
map
d
maze-32-32-4
40
random-64-64-20
43
warehouse-10-20-10-2-1
76
ost003d
143
warehouse-20-40-10-2-1
154
lak303d
173
Appendix
Table 2: Distance d of EQ-DIST per map.
map
hotspot radius r
n=50
100
150
200
maze-32-32-4
8
14
18
22
n=200
400
600
800
random-64-64-20
20
35
45
55
warehouse-10-20-10-2-1
16
26
36
45
ost003d
20
30
45
60
Appendix
Table 3: Hotspot radius r of HOTSPOT per map and number of agents n .
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
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.
Yimin Tang, Han Zhang, Shao-Hung Chan +4
Thomas Lord Department of Computer Science, University of Southern California · Symbotic · Department of Computer Science, University of California Irvine
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.