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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    From multi-agent pathfinding to 3D pipe routing



    Erscheinungsdatum :

    2020-01-01


    Anmerkungen:

    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 . Association for the Advancement of Artificial Intelligence (AAAI) , Palo Alto CA USA , pp. 11-19 , International Symposium on Combinatorial Search 2020 , Vienna , Austria , 26/05/20 . < https://aaai.org/ocs/index.php/SOCS/SOCS20/paper/view/18513 >


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Method for pipe routing using the expert system and the heuristic pathfinding algorithm in shipbuilding

    Jisang Ha / Myung-Il Roh / Ki-Su Kim et al. | DOAJ | 2023

    Freier Zugriff

    Pathfinding and Routing for Automated Driving in the Lanelet2 Map Framework

    Poggenhans, Fabian / Janosovits, Johannes | IEEE | 2020



    Building Digital Maps for Pathfinding

    Angwin, G. T. / Heideman, M. T. / Intelligent Vehicle Highway Society of America | British Library Conference Proceedings | 1993


    PATHFINDING SYSTEM, METHOD AND PROGRAM

    MUTSUGA KATSUHIKO / MOCHIZUKI ATSUSHI | Europäisches Patentamt | 2016

    Freier Zugriff