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

• URL: http://arxiv.org/abs/2603.28968v1
• Date: Mon, 30 Mar 2026 20:12:26 GMT
• Title: Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints
• Abstract summary: Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans.<n>We develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair.<n>Experiments show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions.
• Score: 3.7347677698423536
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows [72.9051182568928]
  We present ReASearch, a unified framework for reasoning-driven optimization.<n>With a shared agent loop and domain-specific tools, ReASearch instantiates the exact same scaffold to optimize prompts, programs, and ML.<n>We observe that complex search behaviors emerge naturally from the agent's reasoning process.
  arXiv  Detail & Related papers  (2026-08-07T02:15:39Z)
• Alternating Target-Path Planning for Scalable Multi-Agent Coordination [11.193867567895353]
  concurrent target assignment and pathfinding problem extends multi-agent pathfinding.<n>We propose an iterative refinement framework that decouples target assignment from pathfinding.<n>This represents a solid step toward practical, large scale TAPF suitable for real-world setups.
  arXiv  Detail & Related papers  (2026-05-08T13:50:51Z)
• CoSearch: Joint Training of Reasoning and Document Ranking via Reinforcement Learning for Agentic Search [51.911048955965136]
  CoSearch is a framework that jointly trains a multi-step reasoning agent and a generative document ranking model.<n>Our results show that joint training of the reasoning agent and retrieval system is both feasible and strongly performant.
  arXiv  Detail & Related papers  (2026-04-19T17:48:17Z)
• Beyond Monolithic Architectures: A Multi-Agent Search and Knowledge Optimization Framework for Agentic Search [56.78490647843876]
  Agentic search has emerged as a promising paradigm for complex information seeking by enabling Large Language Models (LLMs) to interleave reasoning with tool use.<n>We propose bfM-ASK, a framework that explicitly decouples agentic search into two complementary roles: Search Behavior Agents, which plan and execute search actions, and Knowledge Management Agents, which aggregate, filter, and maintain a compact internal context.
  arXiv  Detail & Related papers  (2026-01-08T08:13:27Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution [9.839983977902671]
  Switchable-Edge Search (SES) is an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations.
  arXiv  Detail & Related papers  (2024-03-26T23:10:41Z)
• Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints [5.265273282482319]
  This paper examines the Task Assignment and Path Finding with Precedence and Temporal Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to simultaneously generate task assignments and collision-free paths that adhere to precedence and temporal constraints. Experimentally, we demonstrate that our algorithm, CBS-TA-PTC, can solve highly challenging bomb-defusing tasks with precedence and temporal constraints efficiently.
  arXiv  Detail & Related papers  (2024-02-13T20:07:58Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF) We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
  arXiv  Detail & Related papers  (2022-02-08T07:26:45Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.