FICO: Finite-Horizon Closed-Loop Factorization for Unified Multi-Agent Path Finding
Multi-Agent Path Finding is a fundamental problem in robotics and AI, yet most existing formulations treat planning and execution separately and address variants of the problem in an ad hoc manner. This paper presents a system-level framework for MAPF that integrates planning and execution, generalizes across variants, and explicitly models uncertainties. At its core is the MAPF system, a formal model that casts MAPF as a control design problem encompassing classical and uncertainty-aware formulations. To solve it, we introduce Finite-Horizon Closed-Loop Factorization (FICO), a factorization-based algorithm inspired by receding-horizon control that exploits compositional structure for efficient closed-loop operation. FICO enables real-time responses -- commencing execution within milliseconds -- while scaling to thousands of agents and adapting seamlessly to execution-time uncertainties. Extensive case studies demonstrate that it reduces computation time by up to two orders of magnitude compared with open-loop baselines, while delivering significantly higher throughput under stochastic delays and agent arrivals. These results establish a principled foundation for analyzing and advancing MAPF through system-level modeling, factorization, and closed-loop design.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization
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 re…
Data-Driven Controller Design via Finite-Horizon Dissipativity
Given one open-loop measured trajectory of a single-input single-output discrete-time linear time-invariant system, we present a framework for data-driven controller design for closed-loop finite-horizon dissipativity. F…
Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding
Multi-Agent Path Finding (MAPF) is a core coordination problem for large robot fleets in automated warehouses and logistics. Existing approaches are typically either open-loop planners, which must compute complete trajec…
Computational EfficiencyLinear-Quadratic Dynamic Games as Receding-Horizon Variational Inequalities
We consider dynamic games with linear dynamics and quadratic objective functions. We observe that the unconstrained open-loop Nash equilibrium coincides with the LQR in an augmented space, thus deriving an explicit expre…
Finite-Sample Closed-Loop Stability of Model Predictive Path Integral Control for Linear Time-Invariant Systems
We establish finite-sample closed-loop stability guarantees for Model Predictive Path Integral (MPPI) control applied to discrete-time Linear Time-Invariant (LTI) systems with additive Gaussian process disturbances. The …