Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

• URL: http://arxiv.org/abs/2608.06702v1
• Date: Fri, 07 Aug 2026 01:56:19 GMT
• Title: Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF
• Abstract summary: Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints.<n>We propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second.
• Score: 5.199189722211842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Reactive frameworks such as PIBT and Enhanced PIBT (EPIBT) scale effortlessly to thousands of agents through rule-based, step-by-step coordination but suffer from severe temporal myopia, making them ineffective in scenarios where long-horizon reasoning is essential. RHCR plans windowed paths over multi-step horizons but incurs substantial planning overheads that hinder scalability. TP tackles both challenges by planning only subsets of agents at each timestep, yet its applicability is restricted to highly structured maps. To achieve long-horizon planning at scale across general maps, we propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second while planning over multi-step horizons. PUSH combines the key advantages of PIBT, RHCR, and TP. Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. Unlike TP, however, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. To maintain high throughput in congested environments, PUSH further integrates EPIBT-inspired priority inheritance, backtracking, and anytime improvements into its windowed planning. Empirical evaluations across two realistic MAPF scenarios requiring long-horizon reasoning show that PUSH scales to the same massive agent loads as EPIBT (e.g., 10k agents) while achieving significantly higher system throughput than all baselines.

Related papers

• HIPIF: Hierarchical Planning and Information Folding for Long-Horizon LLM Agent Learning [51.95194664412812]
  Large Language Models (LLMs) have demonstrated strong capabilities as autonomous agents across a wide range of tasks.<n>We propose Hierarchical Planning and Information Folding (HIPIF) for long-horizon LLM agent learning.<n>HIPIF trains the agent end-to-end to organize long-horizon execution around explicit subgoals while folding completed subgoal histories to reduce long-context interference.
  arXiv  Detail & Related papers  (2026-06-09T07:35:14Z)
• Planning over MAPF Agent Dependencies via Multi-Dependency PIBT [26.73382486796029]
  Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second.<n>PIBT is a popular algorithm capable of effectively planning in such situations.<n>We propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies.
  arXiv  Detail & Related papers  (2026-03-24T16:38:12Z)
• HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel [17.262462566213244]
  We propose HiMAP-Travel, a hierarchical multi-agent framework that splits planning into strategic coordination and parallel day-level execution.<n>On TravelPlanner, HiMAP-Travel with Qwen3-8B achieves 52.78% validation and 52.65% test Final Pass Rate (FPR)
  arXiv  Detail & Related papers  (2026-03-05T02:55:53Z)
• Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
  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.
  arXiv  Detail & Related papers  (2025-11-26T20:08:52Z)
• 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)
• Wide-Horizon Thinking and Simulation-Based Evaluation for Real-World LLM Planning with Multifaceted Constraints [39.01715254437105]
  This paper introduces the Multiple Aspects of Planning (MAoP) to solve planning problems with multifaceted constraints.<n>Instead of direct planning, MAoP leverages the strategist to conduct pre-planning from various aspects and provide the planning blueprint for planners.
  arXiv  Detail & Related papers  (2025-06-14T09:37:59Z)
• HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking [109.09735490692202]
  We propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning.<n> Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6 times performance improvement over o1-preview.
  arXiv  Detail & Related papers  (2025-05-05T02:38:58Z)
• Extendable Long-Horizon Planning via Hierarchical Multiscale Diffusion [62.91968752955649]
  This paper tackles a novel problem, extendable long-horizon planning-enabling agents to plan trajectories longer than those in training data without compounding errors.<n>We propose an augmentation method that iteratively generates longer trajectories by stitching shorter ones.<n>HM-Diffuser trains on these extended trajectories using a hierarchical structure, efficiently handling tasks across multiple temporal scales.
  arXiv  Detail & Related papers  (2025-03-25T22:52:46Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
  We introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG) which allows switching orders during execution to avoid unnecessary waiting time. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.
  arXiv  Detail & Related papers  (2023-12-30T20:23:27Z)
• LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning [65.86754998249224]
  We develop a novel hybrid planner that leverages a conventional rule-based planner in conjunction with an LLM-based planner. Our approach navigates complex scenarios which existing planners struggle with, produces well-reasoned outputs while also remaining grounded through working alongside the rule-based approach.
  arXiv  Detail & Related papers  (2023-12-30T02:53:45Z)
• Differentiable Spatial Planning using Transformers [87.90709874369192]
  We propose Spatial Planning Transformers (SPT), which given an obstacle map learns to generate actions by planning over long-range spatial dependencies. In the setting where the ground truth map is not known to the agent, we leverage pre-trained SPTs in an end-to-end framework. SPTs outperform prior state-of-the-art differentiable planners across all the setups for both manipulation and navigation tasks.
  arXiv  Detail & Related papers  (2021-12-02T06:48:16Z)

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.