Paper deep dive

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

Viraj Parimi, Brian C. Williams

Year: 2026Venue: arXiv preprintArea: cs.ROType: PreprintEmbeddings: 61

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%

Last extracted: 4/1/2026, 1:14:09 AM

Summary

The paper introduces a Large Neighborhood Search (LNS) framework for the Multi-Agent Task Assignment and Path Finding with Precedence Constraints (TAPF-PC) problem. By treating TAPF-PC as a lifted version of MAPF-PC, the authors propose a two-level architecture: an outer search that explores task reassignments and local orderings, and an inner repair mechanism that uses MAPF-PC solvers to ensure collision-free paths and precedence satisfaction. Experimental results demonstrate that this approach improves 89.1% of instances compared to fixed-assignment seed solutions.

Entities (5)

MAPF-PC · problem-formulation · 100%TAPF-PC · problem-formulation · 100%Viraj Parimi · researcher · 100%Large Neighborhood Search · algorithm · 98%SIPPS · algorithm · 95%

Relation Signals (3)

TAPF-PC → extends → MAPF-PC

confidence 100% · TAPF-PC, which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost.

Large Neighborhood Search → solves → TAPF-PC

confidence 95% · we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it

SIPPS → optimizes → MAPF-PC

confidence 90% · we instantiate neighborhood MAPF-PC repair with Safe Interval Path Planning with Soft constraints (SIPPS)

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

60,946 characters extracted from source content.

Expand or collapse full text

Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints Viraj Parimi 1 , Brian Williams 1 1 Massachusetts Institute of Technology vparimi@mit.edu, williams@csail.mit.edu Abstract Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream op- erations can proceed at the right time. Multi-agent path find- ing with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy or- dering 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 assign- ment and path finding with precedence constraints (TAPF- PC), which extends MAPF-PC by jointly optimizing assign- ment, 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 fea- sible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibil- ity within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of in- stances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints. 1 Introduction Multi-agent path finding (MAPF) is a widely studied model for coordinating multiple agents in shared environments. In its classical form, MAPF focuses on computing collision- free paths for agents whose destinations are fixed in ad- vance (Stern et al. 2019). This formulation is commonly applied in domains such as warehouse automation and fac- tory logistics, where teams of robots must move efficiently through shared spaces (Wurman, D’Andrea, and Mountz 2008; Li et al. 2021). In many practical settings, however, deciding which agent should perform which task is itself a key part of the planning problem, and solution quality de- pends as much on task allocation as on routing. This coupling becomes even more important when tasks are not independent. In many applications, one task or stage cannot begin until another has been completed. Such prece- dence relations arise naturally in pickup-and-delivery (Ma et al. 2017; Liu et al. 2019), warehouse operations (Wurman, Copyright © 2026, Association for the Advancement of Artificial Intelligence (w.aaai.org). All rights reserved. D’Andrea, and Mountz 2008; Zhang et al. 2022), and man- ufacturing settings such as robotic assembly (Brown et al. 2020). For example, a robot may need to deliver a package before another robot can collect it, or complete multiple sub- assemblies before they can be combined (Ma et al. 2017; Brown et al. 2020). Once such dependencies are present, task assignment, temporal ordering, and collision-free rout- ing become tightly coupled, since changing the assignment affects who goes where, when downstream tasks become available, and how agents interact in shared space (Zhang et al. 2022; Brown et al. 2020). Prior work has explored several ways of integrating as- signment and routing in multi-agent systems, sometimes in- cluding local task ordering, but most do not treat prece- dence relations as explicit global constraints. In one line of work, agents are jointly assigned to targets while collision- free paths are planned simultaneously, as in TAPF (Ma and Koenig 2016) and Conflict-Based Search with Task Assign- ment (CBS-TA) (H ̈ onig et al. 2018). Other formulations en- rich the task model by introducing additional temporal or structural requirements. Multi-Goal TAPF (MG-TAPF) ex- tends this to multi-goal tasks with prescribed within-task goal sequences (Zhong et al. 2022), while Multi-Agent Pickup-and-Delivery (MAPD) addresses a lifelong regime in which pickup-and-delivery tasks arrive online and must be assigned and routed over time (Ma et al. 2017; Liu et al. 2019). Together, these formulations show that assignment and motion often need to be optimized jointly, but none of them combines explicit cross-task precedence constraints with flexible assignment. This gap becomes sharper when precedence relations are themselves explicit planning constraints. MAPF-PC is an es- tablished framework for multi-agent planning with prece- dence constraints in the fixed-assignment setting, where each agent is given a goal sequence and the planner must compute collision-free paths that satisfy precedence rela- tions among the goals (Zhang et al. 2022). Related formula- tions that combine flexible assignment with precedence con- straints have been explored in robotic assembly and manu- facturing (Brown et al. 2020; Liu et al. 2024), but these ap- proaches rely on exact search or sequential greedy insertion and have not been demonstrated at the scale of hundreds of agents and thousands of tasks. In this paper, we study task assignment and path finding with precedence constraints arXiv:2603.28968v1 [cs.RO] 30 Mar 2026 (TAPF-PC), treating it as a lifted counterpart of MAPF-PC. While MAPF-PC addresses routing and precedence satis- faction for a given assignment, TAPF-PC must additionally reason over assignment choices. Figure 1 illustrates this dis- tinction with a simple counterexample, showing that fixed- assignment optimality does not resolve TAPF-PC once reas- signment is allowed. Accordingly, we view TAPF-PC as a search problem above MAPF-PC, in which the outer search explores reassignments while MAPF-PC methods repair the induced fixed-assignment neighborhoods. The resulting search space couples assignment, prece- dence satisfaction, and collision avoidance, making direct optimization challenging. Exact joint methods are available for several related assignment-and-routing formulations (Ma and Koenig 2016; H ̈ onig et al. 2018; Zhong et al. 2022; Brown et al. 2020), but the scale of the lifted TAPF-PC search space motivates scalable suboptimal search. To this end, we develop a large neighborhood search (LNS) frame- work for TAPF-PC that starts from a feasible MAPF-PC seed and explores alternative assignments around it. At each iteration, the method selects a precedence-aware task neighborhood for reconsideration, keeps the exterior solu- tion fixed, and repairs the affected region under the tim- ing and routing constraints induced across the neighborhood boundary. In this way, fixed-assignment MAPF-PC meth- ods (Zhang et al. 2022) are embedded as repair engines within a higher-level search over assignment and routing. Our contributions are twofold. First, we develop a large neighborhood search framework for TAPF-PC that de- composes the problem into an outer reassignment search with precedence-aware neighborhood destruction and inner MAPF-PC repair subproblems. Second, through systematic experiments across multiple benchmark families and scal- ing regimes, we show that flexible reassignment improves 89.1% of instances and characterize the repair and neigh- borhood design choices that drive these results. 2 Problem Formulation We model the environment as an undirected graph G = (V,E), where V is the set of vertices and E is the set of edges. Let A = a 1 ,...,a k denote a set of k agents, with each agent a i starting at a distinct vertex s i ∈ V . Time is dis- crete, and at each timestep an agent may move to an adjacent vertex or wait at its current vertex. As in standard MAPF, vertex conflicts and edge conflicts are forbidden, meaning that two agents may not occupy the same vertex at the same timestep or traverse the same edge in opposite directions si- multaneously (Stern et al. 2019). Let Θ = θ 1 ,...,θ m denote the set of m tasks, where each task θ ∈ Θ is associated with a goal vertex g(θ) ∈ V . A precedence constraint is an ordered pair (θ u ,θ v ) indicat- ing that task θ v may be completed only after task θ u has been completed. Let P ⊆ Θ× Θ denote the set of prece- dence constraints, and assume that P is acyclic. A task θ is completed when an agent reaches g(θ) and all predeces- sor constraints are satisfied. We now formally state the two problem formulations relevant to this work, namely MAPF- PC, in which the task assignment is fixed, and TAPF-PC, in which it is part of the solution. Precedence constraints g 1 g 2 g 3 g 4 (a) Fixed Assignment (MAPF-PC) a 1 a 2 g 1 g 2 g 3 g 4 a 1 :(g 1 , g 4 ) a 2 :(g 3 , g 2 )J 0 =15 (b) Flexible Assignment (TAPF-PC) a 1 a 2 g 1 g 2 g 3 g 4 a 1 :(g 1 , g 2 ) a 2 :(g 3 , g 4 )J 1 =9 Start g GoalPrec.Wall Figure 1: Fixed vs. flexible goal assignment under prece- dence constraints (g 1 ≺ g 2 , g 3 ≺ 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) Flex- ible Assignment (TAPF-PC): J 1 = 9, showing that fixed- assignment optimality does not imply TAPF-PC optimality. 2.1 MAPF-PC In MAPF-PC, each agent a i is given a fixed ordered task sequence c i = ⟨θ i,1 ,θ i,2 ,...,θ i,m i ⟩ of m i = |c i | tasks as part of the input. Let C =c 1 ,...,c k denote the collection of all agent task sequences. Some sequences may be empty, in which case the corresponding agent is assigned no tasks. These sequences form a partition of Θ, so that each task is assigned to exactly one agent in advance and P k i=1 m i = m. For a task θ, let τ (θ) denote its completion time. A feasi- ble MAPF-PC solution consists of a collision-free path for each agent such that all tasks in its assigned sequence are completed. In addition, the prescribed local order must be respected, so τ (θ i,j ) < τ (θ i,j+1 ) for all consecutive tasks in c i , and every global precedence constraint (θ u ,θ v ) ∈ P must satisfy τ (θ u ) < τ (θ v ). MAPF-PC therefore extends classical MAPF by allowing each agent to execute a pre- scribed sequence of tasks under additional global prece- dence constraints (Stern et al. 2019; Zhang et al. 2022). 2.2 TAPF-PC TAPF-PC lifts MAPF-PC by making the task sequences C = c 1 ,...,c k part of the solution rather than part of the input (Brown et al. 2020; Liu et al. 2024). A feasible TAPF-PC solution must therefore determine a partition of Θ into per-agent task sequences, the order of tasks within each sequence, and collision-free paths that realize those choices while satisfying all precedence constraints. Equivalently, a TAPF-PC solution induces a collection of ordered per-agent task sequences C = c 1 ,...,c k , but unlike MAPF-PC, these sequences are not specified in ad- vance. In this paper, we study TAPF-PC in the offline setting, where all tasks and precedence constraints are known at the beginning of planning. Unless stated otherwise, we seek a feasible TAPF-PC solution of minimum sum of costs, where the cost of an agent is the timestep at which it completes its final assigned task. This objective is standard in MAPF and in joint assignment-and-routing formulations such as CBS- TA (H ̈ onig et al. 2018), although TAPF has also been studied under makespan objectives (Ma and Koenig 2016). 3 Overall Framework We solve TAPF-PC using a large neighborhood search (LNS) framework that operates on complete feasible solu- tions. At iteration t, the incumbent feasible solution consists of ordered per-agent task sequences C t = c t 1 ,...,c t k to- gether with collision-free paths that realize those sequences. The search is initialized from a feasible fixed-assignment MAPF-PC solution (Section 4.1), obtained using an exist- ing MAPF-PC solver (Zhang et al. 2022). Starting from this seed, the framework repeatedly destroys (Section 4.2) and repairs precedence-aware neighborhoods (Section 4.3) to explore reassignment opportunities. Unlike LNS for standard MAPF, our neighborhoods are defined over tasks rather than over agents or paths (Huang et al. 2022; Li et al. 2022). This distinction is essential in TAPF-PC because removing one task may force depen- dent successor tasks to be reconsidered, while repairing a task may require restoring missing predecessor tasks in the precedence graph to preserve feasibility. Accordingly, each iteration selects a task neighborhood, derives boundary con- ditions from the frozen exterior, constructs a reassignment- and-order proposal, solves the induced MAPF-PC repair in- stance, and stitches the result into the incumbent. This organization yields a two-level architecture. At the outer level, LNS searches over reassignment and local or- dering decisions for TAPF-PC. At the inner level, the in- duced repair instance is solved as a constrained MAPF-PC subproblem embedded in the current global solution. Algo- rithm 1 summarizes the overall control flow of the proposed framework, from seed generation through neighborhood de- struction, repair, acceptance, and post-refinement. Here S denotes the current search state, S ⋆ denotes the best feasible solution found so far, and e S denotes the candidate produced by the current repair step. 4 Large Neighborhood Search for TAPF-PC 4.1 Seed Solution The search begins from a complete fixed-assignment seed that specifies, for each task, an assigned agent, a within- agent execution order, and explicit paths that realize those Algorithm 1: Large Neighborhood Search for TAPF-PC. Require: Graph G, agents A, tasks Θ, Precedence P Ensure: Best feasible TAPF-PC solution found 1: Construct a fixed-assignment MAPF-PC seed S ⋆ 2: S ← S ⋆ 3: while search budget remains do 4:Select and expand destroy seed into Θ − t 5:Construct a reassignment-and-order proposal for Θ − t 6:Solve the induced local MAPF-PC repair subproblem 7:Stitch repaired paths into exterior as candidate e S 8:Validate e S and update S via the acceptance rule 9:if e S improves the best feasible solution then 10: S ⋆ ← e S 11:end if 12: end while 13: Apply post-refinement to S ⋆ 14: return S ⋆ choices. To obtain this seed, we first construct a fixed- assignment MAPF-PC instance using a precedence-aware greedy assignment-and-order heuristic. The initializer main- tains the set of precedence-ready tasks, whose predecessor tasks in P have already been assigned, and repeatedly as- signs one such task to the agent whose current partial se- quence has the smallest estimated completion time. Once the per-agent task sequences are formed, the resulting assign- ment and within-agent order define a fully specified fixed- assignment MAPF-PC instance, which is then solved with a MAPF-PC method, such as Priority-Based Search (PBS-PC) or Conflict-Based Search (CBS-PC), to obtain collision-free paths for all agents (Zhang et al. 2022). 4.2 Neighborhood Destruction Each LNS iteration begins by selecting a task neighborhood to destroy. The destroy phase selects a seed set of tasks b Θ − t and transforms it into the final destroyed neighborhood Θ − t as described below. The neighborhood-size parameter con- trols the seed size, but the actual destroyed set may be larger after precedence closure. Destroy Operator Families The destroy operators used in our framework fall into three broad families. The first family consists of task-seeded operators that adapt standard destroy strategies from prior LNS work, including random removal, cost-based removal, conflict-driven removal, and Shaw-style relatedness removal (Shaw 1997; Lutz 2014). The second family consists of the precedence-aware op- erators introduced in this work. The PRECEDENCE-WAIT operator targets tasks whose execution is delayed by un- met precedence requirements. For an assigned task θ, let w prec (θ) denote the realized precedence wait, the gap be- tween the agent’s arrival at g(θ) and the earliest time θ can begin given its predecessors’ completion times. The opera- tor ranks tasks by decreasing w prec (θ) and seeds destruction from those with the largest wait, expanding to their immedi- ate precedence neighbors. While PRECEDENCE-WAIT targets individual tasks, the LOW-SLACK operator targets precedence edges directly. For a precedence edge (θ u ,θ v ) ∈ P , let σ(θ u ,θ v ) denote the temporal slack between the completion of θ u and the re- alized start of θ v in the current incumbent solution. Small slack indicates a tight precedence handoff, leaving little room to absorb changes in completion time without affect- ing downstream execution. The LOW-SLACK operator ranks edges by increasing slack and uses the tasks at both ends of the tightest edges as the destroy seed. Together, these opera- tors steer the search toward precedence bottlenecks that are not visible to cost- or collision-based destroy rules. The third family is agent-seeded, motivated by localized repair ideas from MAPF-LNS2 (Li et al. 2022). The AGENT- CONFLICT operator seeds destruction from tasks owned by agents involved in recent conflicts, while the FAILURE- RECOVERY operator targets tasks owned by agents whose most recent repair attempt failed. Although seeded from agents, the resulting neighborhood is still task-based. Across all three families, the destroy policy may be fixed or selected adaptively using an adaptive large neighborhood search (ALNS) portfolio (Ropke and Pisinger 2006). Precedence Closure and Neighborhood Preparation Starting from the seed b Θ − t , the algorithm takes the transi- tive successor closure in the precedence graph, adding every descendant of the seed tasks to the removed set to form the destroyed neighborhood Θ − t . This closure is essential be- cause once a task is removed, every downstream task that depends on it can no longer be treated as fixed. Predecessor tasks, by contrast, may remain in the exterior solution and later induce boundary conditions for repair. After successor closure, tasks in Θ − t are excised from the current assignment and their path segments are removed. If a removed task is followed by a surviving task on the same agent, that immediate successor becomes a boundary task. Such a task remains assigned, but its incoming path segment from a now-destroyed predecessor has been invalidated and must therefore be recomputed before full repair. Boundary tasks are replanned to account for the missing predecessor, and later surviving tasks are retimed to reflect updated pre- decessor completion times. In our framework, these updates are computed with Multi-Label A* (MLA*) (Grenouilleau, van Hoeve, and Hooker 2019). Outside this affected bound- ary, assignment and path structure remain fixed, and the de- stroyed set Θ − t with the patched exterior context C fix t , com- prising the frozen assignment, paths, and incumbent comple- tion times of all tasks outside the destroyed neighborhood, is passed to the repair stage. 4.3 Repair Mechanisms Given the destroyed task neighborhood Θ − t and the fixed ex- terior context C fix t , the repair mechanisms described below operate on the per-agent task sequences after removing tasks in Θ − t . Let c t i denote the resulting sequence of agent a i . Regret-Based Repair Regret repair rebuilds the destroyed portion of the solution by greedily reinserting destroyed tasks one at a time into the current per-agent task sequences. For a destroyed task θ ∈ Θ − t , a feasible insertion spot is defined by a candidate owner a i together with an insertion position in c t i such that the resulting local order remains con- sistent with the precedence constraints and the frozen ex- terior context. Among all feasible insertion spots for θ, let ∆ 1 (θ) ≤ ∆ 2 (θ) ≤ ... denote the corresponding insertion costs in increasing order, so that ∆ 1 (θ) is the cost of the best feasible insertion of θ into the current partial repair. The re- gret score of task θ is defined as ρ(θ) = ∆ 2 (θ)− ∆ 1 (θ), the difference between the best and second-best feasible in- sertion costs (Lutz 2014; Xu et al. 2022). A large regret in- dicates that failing to place θ at its best current spot would incur a substantial loss relative to the remaining options. Repair proceeds greedily, guided by these regret scores. At each step, the algorithm selects the destroyed task with highest regret, inserts it at its best feasible spot, updates the partial solution, and then recomputes the relevant inser- tion costs for the remaining destroyed tasks. This compute- intensive process continues until all tasks in Θ − t have been reinserted or no feasible insertion remains, in which case the repair attempt is abandoned. Notably, regret-based repair de- termines reassignment and local ordering entirely through greedy insertion scores, so path feasibility enters the repair only through these local insertion evaluations. MAPF-PC Neighborhood Repair Let A mut t ⊆ A denote the set of agents whose task sequences may change during repair. Before proposal construction begins, the framework computes an initial release bound for each destroyed task θ ∈ Θ − t from cross-boundary precedence edges. Specifi- cally, fixed predecessors ofθ induce an earliest feasible com- pletion bound τ (θ) = 1 +max (φ,θ)∈P, φ/∈Θ − t τ inc (φ), where τ inc denotes the incumbent completion time from the frozen exterior context C fix t . As each destroyed task is in- serted during proposal construction, its approximate com- pletion time becomes available, and the release bounds of any remaining destroyed successors are tightened. Repair then constructs a local assignment-and-order pro- posal for the tasks in Θ − t . The destroyed tasks are pro- cessed in a precedence-respecting topological order over the destroyed subset. Among currently ready destroyed tasks, the proposal builder prioritizes tasks with smaller release bounds. This ordering is computed once before the inser- tion loop and remains fixed throughout proposal construc- tion. For the current task θ ∈ Θ − t , the algorithm considers candidate owners a i ∈ A mut t together with feasible insertion positions in c t i . In local mode, the candidate owner set is re- stricted to a bounded mutable-agent neighborhood around the current owners of the destroyed tasks, whereas in global mode any agent may be considered as in regret repair. A candidate insertion of θ at position p in agent a i ’s sequence is admissible if it respects the local same-agent ordering, satisfies the release bound τ (θ), remains reach- able under the current approximate completion-time esti- mate, and does not conflict with the frozen exterior occu- pancy reservations. Among admissible positions, the pro- posal selects the one minimizing a static insertion-detour score based on shortest-path distances d(·,·), ignoring dy- namic agent interactions. Exact collision avoidance is de- ferred to the MAPF-PC repair solve that follows later. Each insertion is committed immediately, after which approxi- mate completion times and release bounds are updated. Re- peating this over all tasks in Θ − t in topological order yields the proposed mutable task sequences b C mut t . Once b C mut t has been fixed, we solve a local MAPF-PC subproblem whose task sequences are given by b C mut t and whose exterior con- text is inherited from C fix t (Zhang et al. 2022). 4.4 SIPPS Integration The effectiveness of neighborhood repair depends not only on the quality of the local reassignment proposal, but also on the speed with which that proposal can be realized as collision-free paths. Because the outer LNS loop invokes repair repeatedly, a slow low-level planner directly reduces the number of neighborhoods that can be explored within a fixed runtime budget. For this reason, we instantiate neigh- borhood MAPF-PC repair with Safe Interval Path Planning with Soft constraints (SIPPS) (Li et al. 2022) as the low-level path planner rather than the default MLA* planner used by the MAPF-PC solver. This preserves the MAPF-PC repair structure while reducing per-iteration cost. Recall from Sec- tion 4.3 that the low-level planner must compute paths for each mutable agent that visit its repaired goal sequence, re- spect the frozen exterior occupancy reservations, and satisfy the precedence-derived release bounds. WeadaptSIPPStotheprecedence-constrained neighborhood-repair setting, following the same stage- indexed approach by which MAPF-PC adapts its low-level planner to ordered goal sequences (Zhang et al. 2022). After the proposal fixes the local assignment and order, the resulting temporal constraints are exported to the MAPF-PC repair solver, which derives stage-level lower and upper tim- ing bounds for SIPPS. SIPPS enforces these bounds directly during low-level search. Arrivals before the lower bound are deferred by waiting when possible, whereas arrivals after the upper bound are infeasible. In addition, SIPPS prunes branches whose optimistic completion estimates already violate downstream timing bounds, avoiding search effort on provably infeasible paths. A further consequence of using SIPPS is that the repaired neighborhood need not be realized only against hard obsta- cles. SIPPS also supports soft obstacles, in which collisions with the frozen exterior are penalized rather than strictly pro- hibited. This allows the low-level planner to return a neigh- borhood solution that remains in limited soft conflict with the frozen exterior solution. These soft conflicts arise only at the boundary between the repaired neighborhood and the fixed world outside it. They do not alter the assignment-and- order proposal itself. This distinction gives rise to two re- pair modes. In the hard mode, only fully conflict-free neigh- borhood realizations are retained. In the relaxed mode, soft- conflict realizations may also be returned, leaving the outer search to resolve the remaining interface conflicts later. 4.5 Acceptance, Update, and Post-Refinement After neighborhood repair produces a candidate solution, the repaired paths are stitched back into the fixed exterior con- text and validated against the global precedence constraints and path-conflict conditions before any update is made. The framework supports multiple acceptance rules for updating the search state. In the main configuration studied in this paper, only fully conflict-free repair solutions are retained, and valid candidates are accepted or rejected using thresh- old acceptance (Dueck and Scheuer 1990). A relaxed vari- ant permits solutions with soft conflicts at the neighborhood boundary, accepting candidates only if their conflict counts does not worsen. After the LNS loop terminates, a post-refinement phase is applied to the best solution found. During the main LNS loop, all MAPF-PC solves operate on local neighborhoods, so the final paths are composed of independently repaired subproblems rather than a globally planned routing. Post- refinement addresses this by treating the assignment and within-agent order discovered by LNS as fixed and invok- ing a full MAPF-PC solve over the complete instance. The result is accepted only when it yields a valid solution that strictly improves the current best incumbent. 5 Experimental Setup Our experiments address the following questions: Q1. How do different repair strategies and reassignment scopes compare for TAPF-PC? Q2. How does search behavior evolve over time? Q3. How does performance vary with team size and prece- dence density? Q4. Are the SoC gains driven primarily by reductions in precedence-induced waiting? 5.1 Benchmarks and Instance Generation We evaluate the proposed TAPF-PC methods on a benchmark suite built from four map families, namely empty-16-16, empty-32-32, random-32-32-20, and warehouse-10-20-10-2-1. These correspond to grid maps of size 16× 16, 32× 32, 32× 32, and 161× 63, respectively. Instances are parameterized by the number of agents k, tasks m, and precedence constraints|P|. The benchmark suite is organized into three tiers, de- noted small, medium, and large. The small tier contains 1,350 instances, the medium tier contains 1,650 instances, and the large tier contains 368 instances. The small tier fo- cuses primarily on 100-task instances with moderate prece- dence density across empty, random, and warehouse maps. The medium tier expands to larger 200-task instances with broader sweeps in both agent count and precedence den- sity, together with several larger warehouse-only settings. The large tier is warehouse-only and contains the hardest instances in the benchmark suite, reaching up to 500 agents and 1,000 tasks (full configurations in Supplement A). Within each map family and tier, the benchmark suite con- tains multiple independently generated instances for each realized (k,m,|P|) configuration. All comparisons use the CBS (n= 1253)PBS (n= 1347) Seed Solver 0 10 20 30 40 50 60 Relative SoC reduction (%) By Benchmark Size Small CBS (n= 809)PBS (n= 1641) Seed Solver 0 10 20 30 40 50 60 Medium PBS (n= 324) Seed Solver 0 2 4 6 8 10 12 14 Large (warehouse only) CBS (n= 596)PBS (n= 600) Seed Solver 0 10 20 30 40 50 Relative SoC reduction (%) By Map Family Empty CBS (n= 761)PBS (n= 1238) Seed Solver 0 10 20 30 40 50 60 Random CBS (n= 705)PBS (n= 1474) Seed Solver 0 10 20 30 40 50 60 Warehouse RegretLocal–PBSGlobal–PBSGlobal–CBS 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. common subset of instances for which every displayed method has a corresponding seeded result. All compared methods use the same fixed-assignment seed for a given in- stance and seed solver, so differences between methods are not confounded by different initialization quality. 5.2 Protocol and Configuration The primary comparison set consists of four methods, namely Regret, Local–PBS, Global–PBS, and Global–CBS. Regret uses regret-based repair, while the remaining three use neighborhood MAPF-PC repair, with Local/Global de- noting reassignment scope and PBS/CBS identifying the solver type. The solver type refers to the MAPF-PC solver used during repair, not the solver used to generate the initial seed. These four methods are chosen to isolate two key de- sign axes. Regret against Local–PBS tests whether MAPF- PC neighborhood repair improves over greedy reinsertion, Local–PBS against Global–PBS tests the effect of reassign- ment scope, and Global–PBS against Global–CBS compares the underlying MAPF-PC solver under global reassignment. All four use hard repair only, retaining only conflict-free candidates, with relaxed variants in Supplement C. Across the reported LNS runs, the shared configuration uses destroy seed size 2, adaptive destroy selection through ALNS (Ropke and Pisinger 2006), and threshold accep- tance (Dueck and Scheuer 1990). ALNS uses a reaction factor of 0.35 with standard reward-based weight updates. Threshold acceptance uses a cooling coefficient of 0.99975 with initial temperature set to 5% of the initial sum of costs. We also evaluated alternative acceptance rules, including simulated annealing (van Laarhoven and Aarts 1987), great deluge (Dueck 1993), and old bachelor acceptance (Hu, Kahng, and Tsao 1995), but threshold acceptance consis- tently performed best across our benchmark suite. MLA* is used for local patching during neighborhood destruction (Section 4.2), while SIPPS serves as the low-level planner inside MAPF-PC neighborhood repair. Large-tier results are PBS-seeded only, since CBS-PC seeds were not available at that scale. Our primary objective is sum of costs (SoC). We report absolute SoC reduction ∆J = J seed − J final , relative SoC reduction 100· ∆J/J seed , and improvement frequency (fraction of instances with ∆J > 0). To address Q4, we additionally track the reduction in total precedence wait. We distinguish explicitly between seed generation, the main LNS loop, and post-refinement. The total reported run- time includes all three components. All compared LNS runs use tier-specific wall-clock budgets of 60 s for the small tier, 180 s for the medium tier, and 300 s for the large tier. The wall-clock budget governs only the main LNS loop. Seed generation and post-refinement run outside this budget, and their costs are reported separately. The framework is imple- mented in C++ and tested on an Intel Core i9-14900K run- ning Ubuntu 24.04. 1 1 The code and the problem instances will be released. Small CBSSmall PBSMedium CBSMedium PBSLarge PBS 0 20 40 60 80 100 Instances improved (%) 47 37 32 24 90 92 84 87 66 92 93 85 89 75 92 92 85 82 52 (n=1253)(n=1347)(n=809)(n=1641)(n=324) Improvement Frequency Small CBSSmall PBSMedium CBSMedium PBSLarge PBS 0 200 400 600 800 1000 1200 Absolute SoC reduction (n=1253)(n=1347)(n=809)(n=1641)(n=324) Improvement Magnitude RegretLocal – PBSGlobal – PBSGlobal – CBS 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. 6 Results 6.1 Comparison of Repair Strategies To answer Q1, we compare Regret, Local–PBS, Global– PBS, and Global–CBS. Figure 2 reports relative sum of costs reduction over the fixed-assignment seed. Across both PBS- and CBS-seeded settings, all neighborhood-repair methods substantially outperform the regret baseline. For example, Global–PBS achieves a median relative reduction of 12.2% overall, whereas Regret achieves a median reduction of 0.0%, indicating that it fails to improve the majority of in- stances. Among the MAPF-PC repair variants, Global–PBS is the strongest overall. It achieves the largest median rel- ative reduction in most small and medium settings and re- mains the only method with nontrivial gains on the large PBS-seeded warehouse tier, where it attains a median rel- ative reduction of 1.5% and improves 75.0% of instances. Local–PBS is consistently competitive and often close be- hind, while Global–CBS is competitive in some easier set- tings but achieves smaller median reductions than Global– PBS on the harder medium-tier settings. Figure 3 shows that this advantage is not driven by a few isolated wins. In the left panel, Global–PBS improves a large fraction of instances and leads in most benchmark subsets. In the right panel, the distribution of absolute SoC reduction is generally higher for Global–PBS, and its me- dian reduction is the largest in each subset shown. This is especially clear on the large PBS-seeded warehouse tier, where Global–PBS improves 75.0% of instances while the regret baseline remains nearly flat. These results indicate that Global–PBS generally finds better solutions more often and by larger margins than the other configurations. 6.2 Search Behavior Over Time To address Q2, Figure 4 provides a complementary tempo- ral view of these trends. The regret baseline remains close to zero over time, whereas the MAPF-PC repair methods im- prove rapidly once the search begins. For Global–PBS, on small instances, the median curve reaches 50% of its final 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=1347) By Benchmark Size Small 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=1641) Medium 0200400 Wall-clock time (s) 0 1 2 3 4 5 (n=324) Large (warehouse only) 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=600) By Map Family Empty 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=1238) Random 0200400 Wall-clock time (s) 0 5 10 15 20 25 (n=1474) Warehouse RegretLocal – PBSGlobal – PBSGlobal – CBS 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. gain by about 8 s and 80% by about 24 s. On the medium and pooled warehouse panel, it reaches 50% by about 67–69 s and 80% by about 138–160 s. This shows that neighborhood repair quickly identifies productive reassignment opportuni- ties. At the same time, the stronger methods continue to im- prove rather than plateauing immediately, which indicates that the gains are not confined to a single early repair. A useful nuance emerges when comparing Local–PBS and Global–PBS. In some easier settings, especially on smaller instances, Local–PBS improves very quickly at the start of the run. However, given more runtime and in harder settings, Global–PBS typically catches up and then over- takes it. This is most visible in the PBS-seeded medium and warehouse subsets, where the best-so-far curve of Global– PBS ultimately dominates. Localized repair can be attrac- tive for rapid early progress, but globally flexible reassign- ment yields the strongest overall search behavior given suf- 20406080100 Agents 0 5 10 15 20 Relative SoC reduction (%) Random (n=1,996) Varying Agents (PC = 120) 100150200250 Precedence Constraints 0 8 16 24 32 (n=1,164) Varying Precedence Constraints (A = 60) 406080100 Agents 0 5 10 15 20 25 Relative SoC reduction (%) Warehouse (n=1,600) 100150200250 Precedence Constraints 0 8 16 24 32 40 (n=1,200) RegretLocal – PBSGlobal – PBSGlobal – CBS Figure 5: Scalability on PBS-seeded runs. Curves show me- dian relative SoC reduction, and shaded bands show in- terquartile 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. ficient runtime. CBS-seeded search behavior and iteration- level curves are provided in Supplement B. 6.3 Scalability and High-Precedence Regimes Turning to Q3, the scalability results further clarify when global flexibility is most valuable. Figure 5 shows that when the number of agents increases while the numbers of tasks (m = 200) and precedence constraints (|P| = 120) are held fixed, Global–PBS remains the strongest method across a broad range of settings. This indicates that broader reassign- ment flexibility remains beneficial as team size grows. The same pattern appears across random and warehouse environ- ments, which suggests that the advantage of global repair is not tied to a single map family. At low to moderate numbers of precedence constraints with k = 60 agents and m = 200 tasks, Global–PBS con- tinues to perform strongly. However, in the high-precedence regime, its advantage erodes and Local–PBS performs bet- ter. Supplement D provides further analysis of this crossover. As precedence density increases, the number of accepted re- pairs per run drops sharply for Global–PBS, while Local– PBS retains a more stable repair rate. This suggests that dense precedence structure makes globally flexible repair harder to realize productively, as larger neighborhoods en- counter more cross-boundary precedence constraints and are more likely to produce failed or uncompetitive repairs. The more constrained local mode avoids this by keeping neigh- borhoods small enough to remain tractable. 6.4 Precedence-Induced Wait Reduction Finally, Q4 asks whether the sum of costs improvements are primarily driven by reductions in precedence-induced waiting. If so, the methods that reduce precedence wait the most should also achieve the largest SoC gains. Figure 6 tracks the reduction in realized precedence wait over time. 0816243240 Wall-clock time (s) 0 20 40 60 80 100 Precedence-wait reduction (%) (n=1,347) Small 0306090120150 Wall-clock time (s) 0 20 40 60 80 100 (n=1,641) Medium 050100150200250 Wall-clock time (s) 0 3 6 9 12 15 (n=324) Large (warehouse only) RegretLocal – PBSGlobal – PBSGlobal – CBS 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. On PBS-seeded small instances, Local–PBS reduces prece- dence wait especially quickly, with Global–PBS close be- hind. On medium instances, the two PBS-based methods remain close, while Global–CBS is weaker. On the large PBS-seeded subset, only Global–PBS produces a notice- able reduction. These curves confirm that the precedence- aware aspects of the neighborhood design are doing mean- ingful work. However, on small instances Local–PBS re- duces precedence wait faster yet does not achieve a better fi- nal SoC than Global–PBS, and on the large tier Global–PBS leads in both metrics. This suggests that relieving prece- dence bottlenecks is an important but incomplete explana- tion of the overall gains, since globally flexible reassignment can also improve routing efficiency by placing tasks with agents that reach them at lower path cost. Additional analyses, including operator-contributions, re- laxed soft-conflict variants, and a runtime decomposition by tier and method, are provided in the Supplement. 7 Conclusion We studied TAPF-PC, a lifted setting in which assign- ment, ordering, and collision-free routing must be decided jointly under precedence constraints. We argued that fixed- assignment MAPF-PC does not resolve this larger problem, because allowing reassignment enlarges the solution space and creates improvement opportunities that are inaccessible once task ownership is fixed. To address this, we developed a LNS framework that separates the problem into an outer re- assignment search and inner MAPF-PC repair subproblems, with SIPPS integrated as an efficient low-level planner. Our experiments show that this approach improves 89.1% of instances over fixed-assignment seeds, with the threshold- accepting Global–PBS variant performing best overall. More broadly, the results suggest that MAPF-PC methods are especially effective for TAPF-PC when used as repair en- gines inside a higher-level search over flexible assignment. At the same time, the approach is heuristic, and the high- precedence regime reveals a limitation of globally flexible repair, as Local–PBS can become more effective when dense precedence structure makes global repair harder to exploit. Despite these encouraging results, several directions re- main for future work. One is to design stronger repair poli- cies for denser-precedence regimes. Another is to extend the framework to lifelong settings where tasks arrive online and precedence relations evolve over time. Acknowledgments We gratefully acknowledge support from the Boeing Com- pany. We thank Siddhant Tandon for help with the experi- mental setup. The views and conclusions contained in this document are those of the authors and should not be inter- preted as representing the official policies, either expressed or implied, of the sponsoring organizations or agencies. A Benchmark Configurations Table 1 lists the full set of realized benchmark configura- tions by tier. Each configuration contains 50 independently generated instances. B Additional Search Behavior The main text reports search behavior over wall-clock time for PBS-seeded runs. This section provides complementary views. B.1 CBS-Seeded Search Behavior Figure 7 shows search behavior over wall-clock time for CBS-seeded runs. The overall trends are broadly consis- tent with the PBS-seeded results. On small and medium in- stances, the MAPF-PC repair methods outperform the regret baseline, and Global–PBS again emerges as the strongest configuration. One notable difference is that Regret achieves non-negligible gains on CBS-seeded empty maps, suggest- ing that higher-quality seeds provide a more favorable start- ing point for greedy reinsertion. No CBS-seeded data is available for the large tier, as CBS-PC did not scale to that tier. B.2 Iteration-Level Search Behavior Figures 8 and 9 show search behavior as a function of LNS iteration count rather than wall-clock time, for PBS-seeded and CBS-seeded runs respectively. This view shows how much each method improves per iteration, independent of how long each iteration takes. On the PBS-seeded medium and large tiers, Global–PBS achieves larger per-iteration gains than Local–PBS, confirming that its wall-clock advan- tage stems from higher-quality repairs. The CBS-seeded it- eration curves show a similar pattern on small and medium instances. C Relaxed Soft-Conflict Variants The primary results use hard repair, in which only fully conflict-free neighborhood realizations are retained. This section compares hard and relaxed variants for both local and global PBS-based repair. Figure 10 shows that the effect of relaxed repair is limited. On small and medium instances, the hard and relaxed vari- ants perform similarly for both local and global modes. On the large tier, hard Global–PBS retains a higher median re- duction than its relaxed counterpart, indicating that the over- head of resolving accumulated soft conflicts can outweigh the benefit of accepting more candidates on the hardest in- stances. For Local–PBS, the hard and relaxed variants per- form similarly throughout, with neither consistently domi- 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=1253) By Benchmark Size Small 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=809) Medium 0100200300 Wall-clock time (s) 0 1 2 No data Large (warehouse only) 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=596) By Map Family Empty 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=761) Random 0100200300 Wall-clock time (s) 0 5 10 15 20 25 30 (n=705) Warehouse RegretLocal – PBSGlobal – PBSGlobal – CBS 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. nating. Figure 11 provides a temporal view of the same com- parison. The local variants track each other closely across all tiers. The global variants also remain close on small and medium instances, but on the large tier hard Global–PBS maintains a clear lead throughout. These results justify the choice of hard Global–PBS as the primary configuration. While relaxed repair performs com- parably on small and medium instances, it does not improve performance on the hardest instances. D High-Precedence Diagnostic Figure 12 provides a detailed view of the crossover be- tween Global–PBS and Local–PBS in the high-precedence regime, as discussed in Section 6.3 of the main text. As precedence density increases, the number of accepted re- pairs per run drops sharply for Global–PBS, while Local– PBS retains a more stable level of accepted repairs. This indicates that globally flexible repair becomes harder to re- alize productively when precedence structure is extremely dense, as larger destroyed neighborhoods encounter more cross-boundary precedence constraints and are more likely to produce failed or uncompetitive repair candidates. The more constrained local mode avoids this by keeping neigh- borhoods small enough to remain tractable. Overall, Global– PBS remains the strongest method across most regimes. However, very high precedence density presents a genuine challenge where local repair can become the better choice. E Runtime Decomposition Figure 13 shows the runtime decomposition on the large PBS-seeded warehouse tier. The majority of the wall-clock budget is spent inside the embedded MAPF-PC repair solve, with the reassignment-and-order proposal stage, initializa- tion, and neighborhood generation accounting for smaller fractions. This allocation reflects the design of the frame- work, as the quality gains come from solving full MAPF-PC subproblems rather than from greedy insertion, so dedicat- ing most of the budget to the repair solve is where the in- Table 1: Benchmark configurations by tier. Each tuple (k,m,|P|) denotes the number of agents, tasks, and precedence con- straints. Each configuration contains 50 independently generated instances. TierMap families#Realized (k, m,|P|) configurations Smallempty-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) Largewarehouse † 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) † warehouse-10-20-10-2-1 vestment pays off. Final MAPF-PC polish is non-negligible but still secondary. Notably, the search-behavior curves in the main text show substantial improvement well before the end of the allotted runtime, confirming that the central gains arise from the neighborhood-search process itself and that post-refinement serves as a polishing step rather than the main source of improvement. The same general pattern holds on the medium tier, though the relative share of the embedded solve is smaller. On the small tier, the breakdown is more balanced across components. F Operator Contributions Figures 14 and 15 report the incumbent-improvement rate of each destroy operator across the four methods, broken down by benchmark tier for PBS-seeded and CBS-seeded runs re- spectively. The FAILURE-RECOVERY operator consistently achieves the highest improvement rate across all methods and tiers, reflecting the value of redirecting the search after unsuccess- ful repair attempts. Among the task-based operators, Worst and Shaw tend to produce slightly higher improvement rates than Random and Task Conflict, though all four contribute throughout. The precedence-aware operators show a split. LOW-SLACK achieves moderate improvement rates compa- rable to the task-based family, while PRECEDENCE-WAIT has among the lowest rates across all non-Regret methods. This does not mean PRECEDENCE-WAIT is unproductive, as it may steer the search toward neighborhoods that enable later improvements through other operators, but its direct contribution to incumbent updates is smaller. These results support the use of a mixed ALNS portfolio. No single operator family dominates, and the combination of task-based, precedence-aware, and agent-based operators provides complementary signals for neighborhood selection. References Brown, K.; Peltzer, O.; Sehr, M. A.; Schwager, M.; and Kochenderfer, M. J. 2020. Optimal Sequential Task As- signment and Path Finding for Multi-Agent Robotic Assem- bly Planning. In 2020 IEEE International Conference on Robotics and Automation (ICRA), 441–447. Dueck, G. 1993. New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel. Jour- nal of Computational Physics, 104(1): 86–92. Dueck, G.; and Scheuer, T. 1990. Threshold Accepting: A General Purpose Optimization Algorithm Appearing Su- perior to Simulated Annealing. Journal of Computational Physics, 90(1): 161–175. Grenouilleau, F.; van Hoeve, W.-J.; and Hooker, J. N. 2019. A Multi-Label A* Algorithm for Multi-Agent Pathfinding. In Proceedings of the 29th International Conference on Au- tomated Planning and Scheduling (ICAPS), 181–185. H ̈ onig, W.; Kiesel, S.; Tinka, A.; Durham, J. W.; and Aya- nian, N. 2018. Conflict-Based Search with Optimal Task Assignment. In Proceedings of the International Joint Con- ference on Autonomous Agents and Multiagent Systems (A- MAS), 757–765. Hu, T. C.; Kahng, A. B.; and Tsao, C.-W. A. 1995. Old Bachelor Acceptance: A New Class of Non-Monotone Threshold Accepting Methods. ORSA Journal on Comput- ing, 7(4): 417–425. Huang, T.; Li, J.; Koenig, S.; and Dilkina, B. 2022. Anytime Multi-Agent Path Finding via Machine Learning-Guided Large Neighborhood Search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 9368– 9376. Li, J.; Chen, Z.; Harabor, D.; Stuckey, P. J.; and Koenig, S. 2022. MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 10256–10265. Li, J.; Tinka, A.; Kiesel, S.; Durham, J. W.; Kumar, T. K. S.; and Koenig, S. 2021. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Con- ference on Artificial Intelligence (AAAI), 11272–11281. 050100 LNS iteration 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=1347) By Benchmark Size Small 0100200 LNS iteration 0 4 8 12 16 20 (n=1641) Medium 0204060 LNS iteration 0 1 2 3 4 5 (n=324) Large (warehouse only) 050100 LNS iteration 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=600) By Map Family Empty 0100200 LNS iteration 0 4 8 12 16 20 (n=1238) Random 0100200 LNS iteration 0 5 10 15 20 25 (n=1474) Warehouse RegretLocal – PBSGlobal – PBSGlobal – CBS 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. Liu, M.; Ma, H.; Li, J.; and Koenig, S. 2019. Task and Path Planning for Multi-Agent Pickup and Delivery.In Proceedings of the 18th International Conference on Au- tonomous Agents and MultiAgent Systems, AAMAS ’19, 1152–1160. Richland, SC: International Foundation for Au- tonomous Agents and Multiagent Systems. Liu, S.; Feng, B.; Bi, Y.; and Yu, D. 2024. An Integrated Approach to Precedence-Constrained Multi-Agent Task As- signment and Path Finding for Mobile Robots in Smart Man- ufacturing. Applied Sciences, 14(7): 3094. Lutz, R. 2014. Adaptive Large Neighborhood Search: A Heuristic for the Rich Pickup and Delivery Problem with Time Windows. Bachelor’s thesis, Ulm University. Ma, H.; and Koenig, S. 2016. Optimal Target Assignment and Path Finding for Teams of Agents. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1144–1152. Ma, H.; Li, J.; Kumar, T. K. S.; and Koenig, S. 2017. Life- long Multi-Agent Path Finding for Online Pickup and De- livery Tasks. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’17, 837–845. Richland, SC: International Foundation for Au- tonomous Agents and Multiagent Systems. Ropke, S.; and Pisinger, D. 2006. An Adaptive Large Neigh- borhood Search Heuristic for the Pickup and Delivery Prob- lem with Time Windows. Transportation Science, 40(4): 455–472. Shaw, P. 1997. A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. Tech- nical report, Department of Computer Science, University of Strathclyde, Glasgow, Scotland, UK. Stern, R.; Sturtevant, N.; Felner, A.; Koenig, S.; Ma, H.; Walker, T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. K. S.; Boyarski, E.; and Bart ́ ak, R. 2019. Multi-Agent Pathfind- ing: Definitions, Variants, and Benchmarks. In Proceedings of the International Symposium on Combinatorial Search, volume 10, 151–159. van Laarhoven, P. J. M.; and Aarts, E. H. L. 1987. Simulated Annealing: Theory and Applications. Springer. Wurman, P. R.; D’Andrea, R.; and Mountz, M. 2008. Coor- dinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses. AI Magazine, 29(1). Xu, Q.; Li, J.; Koenig, S.; and Ma, H. 2022. Multi-Goal Multi-Agent Pickup and Delivery. In 2022 IEEE/RSJ In- ternational Conference on Intelligent Robots and Systems (IROS), 9964–9971. Zhang, H.; Chen, J.; Li, J.; Williams, B. C.; and Koenig, S. 2022.Multi-Agent Path Finding for Precedence- Constrained Goal Sequences. In Proceedings of the 21st In- ternational Conference on Autonomous Agents and Multia- 050100 LNS iteration 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=1253) By Benchmark Size Small 0100200 LNS iteration 0 4 8 12 16 20 (n=809) Medium 0204060 LNS iteration 0 1 2 No data Large (warehouse only) 050100 LNS iteration 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=596) By Map Family Empty 0100200 LNS iteration 0 4 8 12 16 20 (n=761) Random 0100200 LNS iteration 0 5 10 15 20 25 30 (n=705) Warehouse RegretLocal – PBSGlobal – PBSGlobal – CBS 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. gent Systems, 1464–1472. Richland, SC: International Foun- dation for Autonomous Agents and Multiagent Systems. ISBN 9781450392136. Zhong, X.; Li, J.; Koenig, S.; and Ma, H. 2022. Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding. In IEEE International Conference on Robotics and Automation (ICRA), 10731–10737. CBS (n= 1253)PBS (n= 1347) Seed Solver 0 10 20 30 40 50 60 Relative SoC reduction (%) By Benchmark Size Small CBS (n= 809)PBS (n= 1641) Seed Solver 0 10 20 30 40 50 60 Medium PBS (n= 324) Seed Solver 0 2 4 6 8 10 12 14 Large (warehouse only) CBS (n= 596)PBS (n= 600) Seed Solver 0 10 20 30 40 50 Relative SoC reduction (%) By Map Family Empty CBS (n= 761)PBS (n= 1238) Seed Solver 0 10 20 30 40 50 60 Random CBS (n= 705)PBS (n= 1474) Seed Solver 0 10 20 30 40 50 60 Warehouse Local–PBSRelaxed Local–PBSGlobal–PBSRelaxed Global–PBS 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. 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=1347) By Benchmark Size Small 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=1641) Medium 0200400 Wall-clock time (s) 0 1 2 3 4 5 (n=316) Large (warehouse only) 0204060 Wall-clock time (s) 0 5 10 15 20 25 30 Relative SoC reduction (%) (n=600) By Map Family Empty 0100200 Wall-clock time (s) 0 4 8 12 16 20 (n=1238) Random 0200400 Wall-clock time (s) 0 5 10 15 20 25 (n=1466) Warehouse Local – PBSRelaxed Local – PBSGlobal – PBSRelaxed Global – PBS 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. 100150200250 0 8 16 24 32 Relative SoC reduction (%) Random Relative SoC Reduction 100150200250 0 15 30 45 60 75 Accepted repairs per run Accepted Repairs per Run 100150200250 Number of precedence constraints 0 8 16 24 32 40 Relative SoC reduction (%) Warehouse 100150200250 Number of precedence constraints 0 6 12 18 24 30 Accepted repairs per run Local – PBSGlobal – PBS 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 cor- responds to random maps, and the bottom row corresponds to warehouse maps. All instances use k = 60 agents and m = 200 tasks. RegretLocal – PBSGlobal – CBSGlobal – PBS 0 100 200 300 400 500 Mean Runtime (s) 83.7s83.7s83.7s83.7s 34.8s 29.4s 30.3s 298.1s 269.3s 275.4s 274.4s 73.4s 98.1s 98.2s 94.2s 457.2s 486.1s 486.9s 482.9s InitializationNeighborhood generationEmbedded MAPF-PC solve Repair bookkeepingFinal MAPF-PC polish Figure 13: Runtime decomposition on the large PBS-seeded warehouse tier. The embedded MAPF-PC solve dominates the total runtime, while neighborhood generation, book- keeping, and final polishing remain secondary. Random Shaw Task Conflict Worst Prec. Wait Low Slack Agent Conflict Failure Recovery 0 2 5 8 10 12 Incumbent-improving proposals (%) Small Task-BasedPrecedence-awareAgent-Based n=5,388 Random Shaw Task Conflict Worst Prec. Wait Low Slack Agent Conflict Failure Recovery 0 4 8 12 16 20 Incumbent-improving proposals (%) Medium Task-BasedPrecedence-awareAgent-Based n=6,564 Random Shaw Task Conflict Worst Prec. Wait Low Slack Agent Conflict Failure Recovery 0 3 6 9 12 15 Incumbent-improving proposals (%) Large (warehouse only) Task-BasedPrecedence-awareAgent-Based n=1,272 RegretLocal – PBSGlobal – PBSGlobal – CBS 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. Random Shaw Task Conflict Worst Prec. Wait Low Slack Agent Conflict Failure Recovery 0 2 4 6 8 10 Incumbent-improving proposals (%) Small Task-BasedPrecedence-awareAgent-Based n=5,012 Random Shaw Task Conflict Worst Prec. Wait Low Slack Agent Conflict Failure Recovery 0 5 10 15 20 25 Incumbent-improving proposals (%) Medium Task-BasedPrecedence-awareAgent-Based n=3,235 RegretLocal – PBSGlobal – PBSGlobal – CBS 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.

Instant research discovery