提出可处理异步动作的多智能体路径规划方法，显著提升大规模场景下的可扩展性。
Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions
- 结合搜索与规则引擎，实现异步动作下高效路径规划
- 1000智能体场景下比基线多处理一个数量级，平均完成时间长25%
- 适合需快速响应的大规模多智能体系统
多智能体路径寻找（MAPF）旨在为多个智能体从各自起点到目标点规划无碰撞路径，并最小化路径成本。尽管已有大量算法能处理数千个智能体，但通常假设每个动作耗时一个时间单位，且所有智能体的动作在离散时间步同步开始，这限制了其实际应用。仅少数算法处理异步动作，但均集中在求最优解，可扩展性有限。本文提出新规划器，位于谱的另一端，以牺牲解质量换取可扩展性，可为大量智能体生成无界次优解。方法结合基于搜索的（LSS）和基于规则的（PIBT）规划，分析其特性并在多种地图上测试，最多支持1000智能体。在运行时间限制下，相较基线可处理多一个数量级的智能体，平均使完成时间（makespan）增加约25%。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step, which may limit their use in practice. Only a few algorithms were developed to address asynchronous actions, and they all lie on one end of the spectrum, focusing on finding optimal solutions with limited scalability. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability, by finding an unbounded sub-optimal solution for many agents. Our method leverages both search methods (LSS) in handling asynchronous actions and rule-based planning methods (PIBT) for MAPF. We analyze the properties of our method and test it against several baselines with up to 1000 agents in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the baselines with about 25% longer makespan.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。