Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. EECBS is a leading two-level algorithm that solves MAPF bounded-suboptimally, that is, within some factor w of the minimum sum of path costs C*. It uses focal search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. EES keeps track of a lower bound LB on C* to find paths whose sum of path costs is at most w LB in order to solve MAPF bounded-suboptimally. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w C*. In this paper, we therefore propose Flexible EECBS (FEECBS), which uses a flex(ible) distribution of the path costs (that relaxes the requirement to find bounded-suboptimal paths on the low level) in order to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We address the drawbacks of flex distribution via techniques such as restrictions on the flex distribution, restarts of the high-level search with EECBS, and low-level focal-A* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Flex distribution for bounded-suboptimal Multi-Agent Path Finding



    Erscheinungsdatum :

    2022-01-01


    Anmerkungen:

    Chan , S-H , Li , J , Gange , G , Harabor , D , Stuckey , P J & Koenig , S 2022 , Flex distribution for bounded-suboptimal Multi-Agent Path Finding . in V Honavar & M Spaan (eds) , 36th AAAI Conference on Artificial Intelligence (AAAI-22) . 36th AAAI Conference on Artificial Intelligence (AAAI-22) , no. 9 , vol. 36 , Association for the Advancement of Artificial Intelligence (AAAI) , Palo Alto CA USA , pp. 9313-9322 , AAAI Conference on Artificial Intelligence 2022 , Online , United States of America , 22/02/22 . https://doi.org/10.1609/aaai.v36i9.21162



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



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

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

    Freier Zugriff

    Bounded suboptimal path planning with Compressed Path Databases

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

    Freier Zugriff

    Decentralized Multi-Agent Path Finding for UAV Traffic Management

    Ho, Florence / Geraldes, Ruben / Goncalves, Artur et al. | IEEE | 2022


    High Density Automated Valet Parking via Multi-agent Path Finding

    Okoso, Ayano / Otaki, Keisuke / Koide, Satoshi et al. | IEEE | 2022