Bulk Search For Optimally Solving Two Variants Of Anonymous Multi-agent Pathfinding

Abstract

We consider the Anonymous Multi-Agent Path-Finding (AMAPF) problem where the agents are confined to a graph, a set of goal vertices is given, and each of these vertices has to be reached by some agent. The problem is to find an assignment of the goals to the agents as well as the collision-free paths, and we seek solutions that minimize either the sum of costs of all paths (SOC) or the maximum path cost (makespan). Two assumptions are usually used for the agents’ behavior after reaching the goals. The first assumption is that agents stay at the goals after reaching them and wait for the other agents to reach their goals, while the second assumption is that agents disappear upon arrival at goal vertices. We refer to the AMAPF problem under the first assumption and to the problem under the second assumption as AMAPF and AMAPFD, respectively. AMAPF can be solved in polynomial time with respect to the makespan objective (although existing approaches have a critical bottleneck in one part of the solving process). For the SOC objective, the known optimal approaches have worst-case exponential complexity. For AMAPFD with the SOC objective, to the best of our knowledge, no dedicated optimal solver has been reported. To this end, in this paper, we enhance the existing solution of the AMAPF-makespan problem and introduce a novel solution to AMAPFD-SOC. Specifically, for the AMAPF-makespan problem, the polynomial approach to solving this problem is to reduce it to a special type of a graph search problem, i.e., to the problem of finding a Maximum Flow on an auxiliary graph induced by the input one. The size of the former graph may be very large and the search on it may become a bottleneck for the standard Maximum Flow solvers. We suggest a specific search algorithm (called Bulk Search) that leverages the idea of exploring the search space not through considering separate search states but rather bulks of them simultaneously. That is, we implicitly compress, store, and expand bulks of the search states as single states, reducing the runtime and memory consumption. Empirically, the resulting AMAPF solver outperforms the competing approach based on the standard MF solver, and solves all publicly available MAPF instances from the MovingAI benchmark in less than 30 seconds. For the AMAPFD-SOC problem, we suggest a method to reduce the problem to a Minimum-Cost Maximum-Flow (MCMF) problem on a similar auxiliary graph used in the AMAPF problem but now with non-zero edge costs. After that, we propose a modified version of Bulk Search, called Generalized Bulk Search to help solve the MCMF problem efficiently. As a result, the AMAPFD-SOC problem is solved by an efficient solver that could solve 98.5% of all MovingAI benchmark instances in less than 30 seconds.