Main /
PublicationS.H. Chan, J. Li, G. Gange, D. Harabor, P. Stuckey and S. Koenig. Flex Distribution for BoundedSuboptimal MultiAgent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2022. Abstract: MultiAgent Path Finding (MAPF) is the problem of finding collisionfree paths for multiple agents that minimize the sum of path costs. EECBS is a leading twolevel algorithm that solves MAPF boundedsuboptimally, that is, within some factor w of the minimum sum of path costs C*. It uses focal search to find boundedsuboptimal 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 boundedsuboptimally. 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 boundedsuboptimal 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 highlevel search with EECBS, and lowlevel focalA* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.
