From Multi-Agent Pathfinding to 3D Pipe Routing
From Multi-Agent Pathfinding to 3D Pipe Routing
复制标题
DOI：
10.1609/socs.v11i1.18530
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
G. Belov;Wenbo Du;M. G. D. L. Banda;Daniel Damir Harabor;Sven Koenig;Xinrui Wei
中科院分区：
文献类型：
--
作者：
G. Belov;Wenbo Du;M. G. D. L. Banda;Daniel Damir Harabor;Sven Koenig;Xinrui Wei
二维多智能体路径寻找（MAPF）问题的目标是在已知的二维环境中，从一组起始位置到一组目标位置，为许多智能体找到无碰撞的路径。由于MAPF对机器人导航的重要性，它已经在理论计算机科学、机器人技术和人工智能领域进行了几十年的研究。由于它与自动化仓储（如亚马逊运营的仓储）和其他当代应用领域的相关性，它目前正在经历重大的科学进展。在本文中，我们证明了一些最近开发的MAPF算法比MAPF研究界目前认为的应用范围更广泛。特别是，我们描述了3D管道路由（PR）问题，其目的是在已知的3D环境中，将无碰撞的管道从给定的起始位置放置到给定的目标位置。MAPF和PR问题是相似的：MAPF实例的解决方案是x-y-t空间中的一组阻塞单元，而相应PR实例的解决方案是x-y-z空间中的一组阻塞单元。我们将展示如何使用这种相似性将最近开发的几种MAPF算法应用于PR问题，并讨论它们在实际PR实例上的性能。这为MAPF研究社区开辟了一个与工业相关的新方向。
The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community.