Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2602.12024v1
• Date: Thu, 12 Feb 2026 14:55:16 GMT
• Title: Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding
• Abstract summary: MAPF is a core coordination problem for large robot fleets in automated warehouses and logistics.<n>Existing approaches are either open-loop planners, which generate fixed trajectories, or closed-loops without reliable performance guarantees.<n>This paper presents ACCBS, a closed-loop built on a finite-horizon variant of CBS with a horizon-changing mechanism.
• Score: 10.628717510399046
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: MAPF is a core coordination problem for large robot fleets in automated warehouses and logistics. Existing approaches are typically either open-loop planners, which generate fixed trajectories and struggle to handle disturbances, or closed-loop heuristics without reliable performance guarantees, limiting their use in safety-critical deployments. This paper presents ACCBS, a closed-loop algorithm built on a finite-horizon variant of CBS with a horizon-changing mechanism inspired by iterative deepening in MPC. ACCBS dynamically adjusts the planning horizon based on the available computational budget, and reuses a single constraint tree to enable seamless transitions between horizons. As a result, it produces high-quality feasible solutions quickly while being asymptotically optimal as the budget increases, exhibiting anytime behavior. Extensive case studies demonstrate that ACCBS combines flexibility to disturbances with strong performance guarantees, effectively bridging the gap between theoretical optimality and practical robustness for large-scale robot deployment.

Related papers

• Optimal Reward Shaping: Autonomous Car Parking Case Study [1.1458853556386799]
  We present a parameterized reward shaping framework featuring alignment feedback, drive-direction switch regularization, and an aligned episode termination mechanism evaluated on an autonomous parallel parking task.<n>By employing surrogate-based Bayesian optimization, our co-optimized Deep Q-Network (DQN) agent resolves characteristic control failure modes, significantly outperforming uncalibrated baselines across both success rate and trajectory smoothness.
  arXiv  Detail & Related papers  (2026-07-26T11:49:23Z)
• Distributed Motion Planning with Safety Guarantees for Self-Reconfiguring Robotic Boats [76.98547580312116]
  This paper proposes a hybrid framework that combines distributed Model Predictive Control (MPC) with Control Barrier Functions (CBFs)<n>To ensure safety in real time, distributed CBF-based filters are applied to enforce inter-agent avoidance.
  arXiv  Detail & Related papers  (2026-07-22T16:37:05Z)
• World Models as Adversaries: Multi-Agent Self-Play Fine-Tuning for Robust Motion Planning [60.88859946006306]
  Adversa World Modeling is a theoretically grounded multi-agent self-play fine-tuning framework.<n>In inner minimization, the planner's predictive world model is converted into a role-conditioned adversary that learns sparse, scene-adaptive attack coalitions.<n> Experiments on the nuPlan and InterPlan benchmarks demonstrate that our method generates transferable adversarial interactions.
  arXiv  Detail & Related papers  (2026-07-12T07:44:16Z)
• Occluding the Solution Space: Planner-Agnostic Adversarial Attacks on Tolerance-Aware Manipulation [57.9825059129472]
  We propose a planner-agnostic attack framework for tolerance-aware manipulation.<n>Our approach shifts the evaluation paradigm to task-level feasibility over goal regions.<n>Online, we formulate the attack as a budgeted maximum-coverage optimization.
  arXiv  Detail & Related papers  (2026-07-04T08:14:44Z)
• Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization [9.832339001385828]
  Closed-loop MAPF algorithms improve scalability by planning only the next movement and replanning online.<n>This issue is especially visible in Anytime Closed-Loop Conflict-Based Search (ACCBS)<n>We introduce certificate trajectories and their associated fleet budget as a general mechanism for filtering closed-loop updates.
  arXiv  Detail & Related papers  (2026-04-01T03:14:16Z)
• Accelerated Spline-Based Time-Optimal Motion Planning with Continuous Safety Guarantees for Non-Differentially Flat Systems [6.862015448582809]
  State-of-the-art approaches formulate spline-based motion planning as a single Control Problem (OCP)<n>By treating separation as an independent classification problem solvable via a linear system or quadratic program, the proposed method eliminates hyperplane parameters from the OCP variables.<n> Experimental validation demonstrates that this decoupled approach reduces trajectory times up to almost 60% compared to fully-rich environments.
  arXiv  Detail & Related papers  (2026-03-25T09:53:04Z)
• VORL-EXPLORE: A Hybrid Learning Planning Approach to Multi-Robot Exploration in Dynamic Environments [19.811711277536187]
  Multi-robot exploration commonly decouples frontier allocation from local navigation.<n>We propose VORL-EXPLORE, a hybrid learning and planning framework that addresses this limitation through execution fidelity.<n>It also drives a risk-aware adaptive arbitration mechanism between global A* guidance and a reactive reinforcement learning policy.
  arXiv  Detail & Related papers  (2026-03-09T05:20:33Z)
• BandPO: Bridging Trust Regions and Ratio Clipping via Probability-Aware Bounds for LLM Reinforcement Learning [49.25750348525603]
  BandPO replaces canonical clipping with Band, a unified theoretical operator that projects trust regions into dynamic, probability-aware clipping intervals.<n>We show that BandPO consistently outperforms canonical clipping and Clip-Higher, while robustly mitigating entropy collapse.
  arXiv  Detail & Related papers  (2026-03-05T08:03:05Z)
• Adaptive Linear Path Model-Based Diffusion [52.84663832658799]
  We introduce Linear Path Model-Based Diffusion (LP-MBD), which replaces the variance-preserving schedule with a flow-matching linear probability path.<n>We also propose Adaptive LP-MBD (ALP-MBD), which leverages reinforcement learning to adjust diffusion steps and noise levels according to task complexity and environmental conditions.
  arXiv  Detail & Related papers  (2026-02-02T21:33:03Z)
• QoS-Aware Hierarchical Reinforcement Learning for Joint Link Selection and Trajectory Optimization in SAGIN-Supported UAV Mobility Management [52.15690855486153]
  A space-air-ground integrated network (SAGIN) has emerged as an essential architecture for enabling ubiquitous UAV connectivity.<n>This paper formulates UAV mobility management in SAGIN as a constrained multiobjective joint optimization problem.
  arXiv  Detail & Related papers  (2025-12-17T06:22:46Z)
• Logic-informed reinforcement learning for cross-domain optimization of large-scale cyber-physical systems [7.352750348429755]
  We present logic-informed reinforcement learning (LIRL) for cyber-physical systems.<n>LIRL maps a low-dimensional latent action onto the admissible hybrid manifold defined on-the-fly by first-order logic.<n>It consistently maintains zero constraint violations and significantly surpasses state-of-the-art hybrid-action reinforcement learning baselines.
  arXiv  Detail & Related papers  (2025-11-02T05:02:17Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• Towards Robust Spacecraft Trajectory Optimization via Transformers [17.073280827888226]
  We develop an autonomous generative model to solve non- optimal control problems in real-time.<n>We extend the capabilities of ART to address robust chance-constrained optimal control problems.<n>This work marks an initial step toward the reliable deployment of AI-driven solutions in safety-critical autonomous systems such as spacecraft.
  arXiv  Detail & Related papers  (2024-10-08T00:58:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.