Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
复制标题
DOI：
10.1609/icaps.v32i1.19810
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Keisuke Okumura;Xavier D'efago
中科院分区：
文献类型：
--
作者：
Keisuke Okumura;Xavier D'efago
针对多个代理的目标分配和路径计划的组合问题的实时计划，也称为多代理路径查找的未标记版本（MAPF），对于多代理系统中的高级协调至关重要机器人群的编队。本文研究了未标记的MAPF的两个方面：（1）脱机场景：通过以较小的计算时间进行集中式方法解决大型实例，以及（2）在线场景：尽管有真实的机器人的时间不确定性，执行了未标记的MAPF。为此，我们提出了一种新型的亚次级完整算法TSWAP，该算法采用任意的初始目标分配，然后通过目标交换重复一台式路径计划。 TSWAP可以适应离线和在线方案。我们从经验上证明，离线TSWAP是高度可扩展的。与现有方法相比，在减少数量级的运行时提供近乎最佳的解决方案。此外，我们通过实体演示介绍了在线TSWAP的好处，例如延迟公差。
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 sub-optimal complete algorithm, which takes an arbitrary initial target assignment then repeats one-timestep 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.