The Multi-Agent Path Finding (MAPF) problem aims to find collision-free paths for multiple agents while optimizing objectives such as the sum of costs or makespan. MAPF has wide applications in domains like automated warehouses, manufacturing systems, and airport logistics. However, most MAPF formulations assume a simplified robot model for planning, which overlooks execution-time factors such as kinodynamic constraints, communication latency, and controller variability. This gap between planning and execution is problematic for time-sensitive applications. To bridge this gap, we propose REMAP, an execution-informed MAPF planning framework that can be combined with leading search-based MAPF planners with minor changes. Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths. We demonstrate our method for solving MAPF with Real-world Deadlines (MAPF-RD) problem, where agents must reach their goals before a predefined wall-clock time. We integrate our framework with two popular MAPF methods, MAPF-LNS and CBS. Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods (e.g., constant execution speed estimators) on benchmark maps with up to 300 agents.

翻译：多智能体路径规划（MAPF）问题旨在为多个智能体寻找无碰撞路径，同时优化总成本或完工时间等目标。MAPF在自动化仓库、制造系统和机场物流等领域具有广泛应用。然而，大多数MAPF公式采用简化的机器人模型进行规划，忽略了执行时的动态约束、通信延迟和控制器可变性等因素。这种规划与执行之间的差距对时间敏感的应用场景尤为不利。为弥合这一差距，我们提出了REMAP——一种执行感知的MAPF规划框架，该框架可通过微小改动与主流基于搜索的MAPF规划器结合。本框架集成了提出的ExecTimeNet模型，能够基于规划路径精确预估执行时间。我们展示了该方法用于解决具有现实世界截止时间（MAPF-RD）的MAPF问题，其中智能体必须在预设的物理时间前抵达目标位置。我们将该框架与两种主流MAPF方法（MAPF-LNS和CBS）集成。实验表明，在包含多达300个智能体的基准地图上，REMAP相较于基线方法（如恒定执行速度估计器）在解质量上实现了最高20%的提升。