From Multi-Agent Pathfinding to 3D Pipe Routing

Gleb Belov, Wenbo Du, Maria Garcia de la Banda, Daniel Harabor, Sven Koenig, Xinrui Wei

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

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 locations 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 for automated warehouses (such as those operated
by Amazon) and other important 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 collisionfree 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.
Original languageEnglish
Title of host publicationProceedings of the Twelfth International Symposium on Combinatorial Search
EditorsDaniel Harabor, Mauro Vallati
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages11-19
Number of pages9
ISBN (Electronic)9781577358220
Publication statusPublished - 2020
EventInternational Symposium on Combinatorial Search 2020 - Vienna, Austria
Duration: 26 May 202028 May 2020
Conference number: 13th
https://aaai.org/ocs/index.php/SOCS/SOCS20/schedConf/presentations

Conference

ConferenceInternational Symposium on Combinatorial Search 2020
Abbreviated titleSoCS 2020
CountryAustria
CityVienna
Period26/05/2028/05/20
Internet address

Cite this

Belov, G., Du, W., Garcia de la Banda, M., Harabor, D., Koenig, S., & Wei, X. (2020). From Multi-Agent Pathfinding to 3D Pipe Routing. In D. Harabor, & M. Vallati (Eds.), Proceedings of the Twelfth International Symposium on Combinatorial Search (pp. 11-19). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ocs/index.php/SOCS/SOCS20/paper/view/18513