Real-time planning for a combined problem of target assignment and path planning for multiple agents, also known as the unlabeled version of Multi-Agent Path Finding (MAPF), is crucial for high-level coordination in multi-agent systems, e.g., pattern formation by robot swarms. This paper studies two aspects of unlabeled-MAPF: (1) offline scenario: solving large instances by centralized approaches with small computation time, and (2) online scenario: executing unlabeled-MAPF despite timing uncertainties of real robots. For this purpose, we propose TSWAP, a novel complete algorithm consisting of target assignment with lazy evaluation and path planning with target swapping. TSWAP can adapt to both offline and online scenarios. We empirically demonstrate that Offline TSWAP is highly scalable; providing near-optimal solutions while reducing runtime by orders of magnitude compared to existing approaches. In addition, we present the benefits of Online TSWAP, such as delay tolerance, through real-robot demos.
翻译:对于多个代理商的目标分配和路径规划的综合问题(又称无标签的多代理商路径发现(MAPF)),实时规划对多试剂系统的高级别协调至关重要,例如机器人群形成模式。本文研究了未标记的MAPF的两个方面:(1) 脱线方案:通过集权方法解决大型案例,使用小计算时间,(2) 在线方案:执行无标签的MAPF,尽管实际机器人的时间不确定。为此目的,我们提议TSWAP,这是一套新颖的完整算法,包括懒惰的评价和与目标转换的路径规划。 TSWAP可以适应离线和在线两种情况。我们从经验上证明,离线 TSWAP 提供接近最佳的解决方案,同时按数量顺序减少运行时间。此外,我们介绍了在线 TSWAP 的好处,例如延缓度,通过实时机器人演示。