Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints

Viraj Parimi; Brian C. Williams

cs.ROMar 30, 2026

Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints

Authors: Viraj Parimi, Brian C. Williams

Organizations: Massachusetts Institute of Technology

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Fixed vs. flexible goal assignment under precedence constraints $(g_{1}\!\prec\!g_{2},\;g_{3}\!\prec\!g_{4})$ . $J$ denotes sum of path costs; assigned goal sequences are shown below each panel. (a) Fixed Assignment (MAPF-PC): $J_{0}\!=\!15$ . (b) Flexible Assignment (TAPF-PC): $J_{1}\!=\!9$ , showing that fixed-assignment optimality does not imply TAPF-PC optimality.

Figure 2: Main method comparison across seeded benchmark subsets. Each panel reports relative sum of costs reduction over the fixed-assignment seed (higher is better). Top row : By benchmark tier. Bottom row : By map family.

Figure 3: Improvement frequency and absolute sum of costs reduction. Left : Fraction of improved instances, Right : Boxplots of absolute SoC reduction across all instances. Larger values are better.

Figure 4: Search behavior on PBS-seeded runs. Curves show median best-so-far relative SoC reduction over wall-clock time, and shaded bands show the interquartile range. The x-axis shows wall-clock time including seed generation and post-refinement.

Figure 5: Scalability on PBS-seeded runs. Curves show median relative SoC reduction, and shaded bands show interquartile range. Left column : Varying agents with fixed tasks and precedence constraints. Right column : Varying precedence constraints with fixed agents and tasks. Top row : Random map. Bottom row : Warehouse map.

Figure 6: Reduction in realized precedence wait over time on PBS-seeded runs. Larger values indicate greater removal of precedence-induced waiting relative to the seed solution.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Tier	Map families	#	Realized $(k,m,\|P\|)$ configurations
Small	empty-16 empty-32 random-32 warehouse †	8	$(10,100,80)$ , $(10,100,100)$ , $(20,100,80)$ , $(20,100,100)$ , $(30,100,80)$ , $(30,100,100)$ , $(60,200,80)$ , $(100,200,100)$
Medium	random-32 warehouse †	21	$(10,200,120)$ , $(10,200,160)$ , $(10,200,280)$ , $(20,200,120)$ , $(20,200,160)$ , $(20,200,280)$ , $(30,200,120)$ , $(40,200,120)$ , $(50,200,120)$ , $(60,200,120)$ , $(60,200,160)$ , $(60,200,200)$ , $(60,200,240)$ , $(60,200,280)$ , $(70,200,120)$ , $(80,200,120)$ , $(90,200,120)$ , $(100,200,120)$ , $(150,300,150)$ , $(200,400,200)$ , $(250,500,250)$
Large	warehouse †	10	$(200,800,400)$ , $(200,1{,}000,500)$ , $(200,1{,}200,600)$ , $(200,1{,}400,700)$ , $(200,1{,}600,800)$ , $(300,600,300)$ , $(350,700,350)$ , $(400,800,400)$ , $(450,900,450)$ , $(500,1{,}000,500)$

Appendix

Table 1: Benchmark configurations by tier. Each tuple

(k,m,|P|)

denotes the number of agents, tasks, and precedence constraints. Each configuration contains 50 independently generated instances.

Figure 7: Search behavior on CBS-seeded runs. Curves show median best-so-far relative SoC reduction over wall-clock time, and shaded bands show the interquartile range. No CBS-seeded data is available for the large tier.

Figure 8: Search behavior by LNS iteration on PBS-seeded runs. Curves show median best-so-far relative SoC reduction over iteration count, and shaded bands show the interquartile range.

Figure 9: Search behavior by LNS iteration on CBS-seeded runs. Curves show median best-so-far relative SoC reduction over iteration count, and shaded bands show the interquartile range. No CBS-seeded data is available for the large tier.

Figure 10: Hard vs. relaxed repair comparison across benchmark subsets. Each panel reports relative sum-of-costs reduction over the fixed-assignment seed. Diamond markers indicate the median. Top row : By benchmark tier. Bottom row : By map family.

Figure 11: Search behavior for hard vs. relaxed PBS variants. Curves show median best-so-far relative SoC reduction over wall-clock time, and shaded bands show the interquartile range.

Figure 12: PBS-seeded high-precedence diagnostic. The left column shows median relative sum-of-costs reduction, and the right column shows median accepted repairs per run. Shaded bands show the interquartile range. The top row corresponds to random maps, and the bottom row corresponds to warehouse maps. All instances use

k=60

agents and

m=200

tasks.

Figure 13: Runtime decomposition on the large PBS-seeded warehouse tier. The embedded MAPF-PC solve dominates the total runtime, while neighborhood generation, bookkeeping, and final polishing remain secondary.

Figure 14: Destroy-operator contribution by benchmark tier on PBS-seeded runs. For each destroy operator, the colored bars show the mean incumbent-improving proposal rate (%) aggregated over the runs in that tier, and the vertical whiskers indicate the 25th–75th percentile range of the corresponding per-run rates. Operators are grouped by family. Note that

n

denotes the total number of method-runs contributing to the tier panel, summed across methods.

Figure 15: Destroy-operator contribution by benchmark tier on CBS-seeded runs. Format follows Figure 14 . No CBS-seeded data is available for the large tier.

Multi-Agent Path Finding

Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.

See all 92 papers

May 8, 2026

Alternating Target-Path Planning for Scalable Multi-Agent Coordination

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 Coordination Multi-Robot Task Allocation Iterative Refinement Multi-Agent Path Finding

Ask PDF

May 15, 2026

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Multi-robot systems are integral to modern logistics, but their capabilities are often limited to tasks executable by individual agents. This paper addresses a critical gap in existing frameworks like Multi-Agent Path Finding (MAPF) and Task Allocation and Path Finding (TAPF), which lack true cooperation for transporting large items that require multiple agents. To this end, we formalise the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem, which integrates team formation, task assignment, and collision-free pathfinding. We present an optimal solver, Cooperative Transportation Task Conflict-Based Search (CT-TCBS), which features a novel Incremental Expansion strategy to tackle the combinatorial explosion inherent in team formation. Recognising the computational cost of optimality, we also develop a family of sub-optimal solvers that employ a global, task-centric perspective, selecting the next task to assign based on a global difficulty metric (Best Task or Worst Task). Our comprehensive empirical evaluation demonstrates three key findings: (1) the incremental expansion strategy significantly outperforms the naive combinatorial approach by successfully pruning the dominant task-allocation search space; (2) we identify a task-conflict expansion dilemma, where sophisticated conflict resolvers effective for large-agent pathfinding subproblems can be detrimental in the integrated CT-TAPF setting; and (3) our proposed sub-optimal solvers establish a new, more efficient frontier on the solution quality-runtime spectrum compared to "nn-" agent-centric baselines. This work provides a foundational framework and a set of effective algorithms for a new, practical class of cooperative multi-agent problems.

Ning Zhou, Nikolai W. F. Bode, Edmund R. Hunt

University of Bristol

Multi-Agent System Optimization Multi-Robot Coordination Conflict-Based Search Multi-Robot Task Allocation Multi-Agent Path Finding Multi-Robot Cargo Transportation

Ask PDF

Sep 13, 2026

ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search

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

Multi-Agent Path Finding Multi-Robot Task Allocation

Ask PDF

Abstract

Multi-Agent Path Finding

Explore similar work

Alternating Target-Path Planning for Scalable Multi-Agent Coordination

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search