Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    ECBS with flex distribution for bounded-suboptimal Multi-Agent Path Finding


    Beteiligte:

    Erscheinungsdatum :

    2021-01-01


    Anmerkungen:

    Chan , S H , Li , J , Gange , G , Harabor , D , Stuckey , P J & Koenig , S 2021 , ECBS with flex distribution for bounded-suboptimal Multi-Agent Path Finding . in H Ma & I Serina (eds) , Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021) . 14th International Symposium on Combinatorial Search, SoCS 2021 , vol. 1 , Association for the Advancement of Artificial Intelligence (AAAI) , Palo Alto CA USA , pp. 159-161 , International Symposium on Combinatorial Search 2021 , Guangzhou , China , 26/07/21 . < https://ojs.aaai.org/index.php/SOCS/article/view/18569 >


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Flex distribution for bounded-suboptimal Multi-Agent Path Finding

    Chan, Shao-Hung / Li, Jiaoyang / Gange, Graeme et al. | BASE | 2022

    Freier Zugriff

    Bounded suboptimal path planning with Compressed Path Databases

    Zhao, Shizhe / Chiari, Mattia / Botea, Adi et al. | BASE | 2020

    Freier Zugriff

    Fuzzy Control of Automobile ECBS on Varying Pavement

    Sun, Ren Yun ;Wang, Bo ;Zhan, Yong Fu | Trans Tech Publications | 2011