提出FICO框架,让多智能体路径规划实时响应并适应动态变化。
FICO: Finite-Horizon Closed-Loop Factorization for Unified Multi-Agent Path Finding
- 基于滚动时域控制的分解算法,实现闭环协同规划
- 毫秒级启动,支持千级智能体,计算效率提升100倍
- 适用于动态延迟与突发到达场景,适合机器人调度应用
多智能体路径规划是机器人与人工智能中的基础问题,但现有方法普遍将规划与执行分离,且对各类变体处理方式零散。本文提出一个系统级框架,将路径规划建模为控制设计问题,统一处理经典与不确定性场景。核心是有限时域闭环分解(FICO)算法,受滚动时域控制启发,利用组合结构实现高效闭环运行。FICO可在毫秒内启动执行,支持数千智能体,并在执行中自适应不确定性。大量实验表明,相比开环基线,其计算时间减少达两个数量级,且在随机延迟和智能体突入条件下显著提升吞吐量。该工作为通过系统建模、分解与闭环设计推进多智能体路径规划提供了原则性基础。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。