Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines

• URL: http://arxiv.org/abs/2511.21886v1
• Date: Wed, 26 Nov 2025 20:08:52 GMT
• Title: Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines
• Authors: Jingtian Yan, Shuai Zhou, Stephen F. Smith, Jiaoyang Li,
• Abstract summary: We propose REMAP, an execution-informed MAPF planning framework for time-sensitive applications.<n>Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths.<n>Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods.
• Score: 9.228609005424348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multi-Agent Path Finding (MAPF) problem aims to find collision-free paths for multiple agents while optimizing objectives such as the sum of costs or makespan. MAPF has wide applications in domains like automated warehouses, manufacturing systems, and airport logistics. However, most MAPF formulations assume a simplified robot model for planning, which overlooks execution-time factors such as kinodynamic constraints, communication latency, and controller variability. This gap between planning and execution is problematic for time-sensitive applications. To bridge this gap, we propose REMAP, an execution-informed MAPF planning framework that can be combined with leading search-based MAPF planners with minor changes. Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths. We demonstrate our method for solving MAPF with Real-world Deadlines (MAPF-RD) problem, where agents must reach their goals before a predefined wall-clock time. We integrate our framework with two popular MAPF methods, MAPF-LNS and CBS. Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods (e.g., constant execution speed estimators) on benchmark maps with up to 300 agents.

Related papers

• Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems [28.133146953693814]
  We present Lifelong Scalable Multi-Agent Realistic Testbed (L), an open-source simulator to evaluate any Multi-Agent Path Finding (MAPF) in a Fleet Management System (FMS) with Automated Guided Vehicles (AGVs)<n>MAPF aims to move a group of agents from their corresponding starting locations to their goals. Lifelong MAPF (LMAPF) is a variant of MAPF that continuously assigns new goals for agents to reach.<n>LMAPF applications, such as autonomous warehouses, often require a centralized, lifelong system to coordinate the movement of a fleet of robots, typically AGVs.
  arXiv  Detail & Related papers  (2026-02-17T16:53:20Z)
• WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning [7.2069924323665235]
  Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications.<n>We propose kinodynamic Temporal Plan Graph Planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a kinodynamically feasible plan.<n>Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism.
  arXiv  Detail & Related papers  (2025-08-02T21:33:08Z)
• Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
  Real-Time MAPF embodies a realistic MAPF setup in which planning and execution are interleaved.<n>Existing solutions to RT-MAPF iteratively call windowed versions of MAPF algorithms in every planning period.<n>We explore different policies for allocating the planning budget in windowed versions of standard MAPF algorithms.
  arXiv  Detail & Related papers  (2025-07-22T08:32:55Z)
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a common abstraction of multi-robot trajectory planning problems.<n>We introduce MAPF-GPT-DDG, a decentralized suboptimal MAPF solvers that leverage machine learning.<n>Our experiments demonstrate that MAPF-GPT-DDG surpasses all existing learning-based MAPF solvers.
  arXiv  Detail & Related papers  (2025-06-30T12:34:31Z)
• Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
  The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target.<n>We propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target.<n>We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms.
  arXiv  Detail & Related papers  (2024-12-05T15:37:29Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment.<n>Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning.<n>We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents. We propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations.
  arXiv  Detail & Related papers  (2023-08-22T07:17:39Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)

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.