Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization

• URL: http://arxiv.org/abs/2604.00428v1
• Date: Wed, 01 Apr 2026 03:14:16 GMT
• Title: Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization
• Abstract summary: 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.
• Score: 9.832339001385828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent coordination in automated warehouses and logistics is commonly modeled as the Multi-Agent Path Finding (MAPF) problem. Closed-loop MAPF algorithms improve scalability by planning only the next movement and replanning online, but this finite-horizon viewpoint can be shortsighted and makes it difficult to preserve global guarantees and exploit compositional structure. This issue is especially visible in Anytime Closed-Loop Conflict-Based Search (ACCBS), which applies Conflict-Based Search (CBS) over dynamically extended finite horizons but, under finite computational budgets, may terminate with short active prefixes in dense instances. We introduce certificate trajectories and their associated fleet budget as a general mechanism for filtering closed-loop updates. A certificate provides a conflict-free fallback plan and a monotone upper bound on the remaining cost; accepting only certificate-improving updates yields completeness. The same budget information induces a budget-limited factorization that enables global, inheritable decomposition across timesteps. Instantiating the framework on ACCBS yields Certificate-Driven Conflict-Based Search (CDCBS). Experiments on benchmark maps show that CDCBS achieves more consistent solution quality than ACCBS, particularly in dense settings, while the proposed factorization reduces effective group size.

Related papers

• TAPO: Tool-Aware Policy Optimization via Credit Transfer for Multimodal Search Agents [54.08846865906602]
  We characterize credit misassignment as a systematic failure mode of GRPO in tool-augmented multimodal search agents.<n>We propose Tool-Aware Policy Optimization (TAPO), which exploits the parameter-determinism property of information-acquisition tools.
  arXiv  Detail & Related papers  (2026-06-04T07:15:43Z)
• AnchorMoE: Interpretable Time Series Classification via Anchor-Routed MoE [51.994752158953084]
  AnchorMoE is an interpretable-by-construction classification framework.<n>It encodes multi-view representations of local patches and routes them to specialized experts.<n>Experiments on real-world and synthetic benchmarks demonstrate that AnchorMoE achieves highly competitive classification performance.
  arXiv  Detail & Related papers  (2026-06-02T13:30:54Z)
• Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions [7.042035340772298]
  Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations.<n>Most existing MAPF algorithms rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit.<n>This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which can solve MAPF-AA with completeness and solution optimality guarantees.
  arXiv  Detail & Related papers  (2026-03-19T13:12:27Z)
• Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding [44.79409119345322]
  Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph.<n>We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution.
  arXiv  Detail & Related papers  (2026-03-11T11:04:54Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure [0.0]
  We propose the Coverage-Objective-Structure (CSO) framework, which decomposes nearly every PAC sample complexity result into three factors.<n> CSO is not a theorem but an interpretive template that identifies bottlenecks and makes cross-setting comparison immediate.<n>We provide practitioner tools: rate lookup tables indexed by CSO coordinates, Bellman residual diagnostics, coverage estimation with deployment gates, and per-episode policy certificates.
  arXiv  Detail & Related papers  (2026-03-01T22:33:16Z)
• Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding [10.628717510399046]
  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.
  arXiv  Detail & Related papers  (2026-02-12T14:55:16Z)
• CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction [49.09876340754804]
  conformsctextCoVeR is a model-free decoding strategy that balances search efficiency with the need for versatile trajectories.<n>We show that conformsctextCoVeR simultaneously maintains a compact search space and ensures high coverage probability over desirable trajectories.
  arXiv  Detail & Related papers  (2025-09-05T01:07:12Z)
• 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)
• Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
  We propose a non-orthogonal multiple access (NOMA) enabled HFL system under semi-synchronous cloud model aggregation. We show that the proposed scheme outperforms the considered benchmarks regarding HFL performance improvement and total cost reduction.
  arXiv  Detail & Related papers  (2023-11-03T13:34:44Z)
• Scalable Incomplete Multi-View Clustering with Structure Alignment [71.62781659121092]
  In this paper, we propose a novel incomplete anchor graph learning framework. We construct the view-specific anchor graph to capture the complementary information from different views. The time and space complexity of the proposed SIMVC-SA is proven to be linearly correlated with the number of samples.
  arXiv  Detail & Related papers  (2023-08-31T08:30:26Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Improving Continuous-time Conflict Based Search [19.36475688888736]
  Conflict-Based Search (CBS) is a powerful framework for optimally solving multi-agent path finding (MAPF) problems. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. We show how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-levelagents, to the continuous time setting of CCBS.
  arXiv  Detail & Related papers  (2021-01-24T14:34:25Z)
• 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.