提出新算法解决异步多智能体路径规划，保证最优与完整。
Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions
- 基于冲突搜索框架，避开连续等待导致的状态无限问题
- 实测分支数减少最高达90%，显著提升求解效率
- 适合需异步动作的现实场景，如机器人调度、自动驾驶
多智能体路径规划（MAPF）旨在为多个智能体从起点到终点规划无碰撞路径，并最小化路径开销。现有大多数算法依赖同步动作假设，即所有智能体在同一时间开始行动且每步耗时一个单位时间，这限制了实际应用。为突破此限制，连续时间冲突搜索（CCBS）被提出用于处理异步动作下的MAPF（MAPF-AA），但其因连续等待时间导致不可数无限状态空间，已被证明不完全。本文提出冲突搜索异步动作（CBS-AA）方法，克服该理论缺陷，可保证求解的完整性与最优性。基于CBS-AA，我们还设计冲突消解技术以进一步提升可扩展性。实验表明，该方法最多可将分支数量减少90%。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs. 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, which may limit the use of MAPF planners in practice. To get rid of this assumption, Continuous-time Conflict-Based Search (CCBS) is a popular approach that can find optimal solutions for MAPF with asynchronous actions (MAPF-AA). However, CCBS has recently been identified to be incomplete due to an uncountably infinite state space created by continuous wait durations. This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue and can solve MAPF-AA with completeness and solution optimality guarantees. Based on CBS-AA, we also develop conflict resolution techniques to improve the scalability of CBS-AA further. Our test results show that our method can reduce the number of branches by up to 90%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。