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 的好处,例如延缓度,通过实时机器人演示。

0
下载
关闭预览

相关内容

专知会员服务
39+阅读 · 2020年9月6日
商业数据分析,39页ppt
专知会员服务
160+阅读 · 2020年6月2日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
已删除
将门创投
6+阅读 · 2018年12月3日
Arxiv
0+阅读 · 2021年10月31日
Arxiv
0+阅读 · 2021年10月30日
Arxiv
5+阅读 · 2021年2月8日
VIP会员
相关资讯
已删除
将门创投
6+阅读 · 2018年12月3日
Top
微信扫码咨询专知VIP会员