Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

Abstract

Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(w1) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor w1, that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(w1) and speed it up, at the cost of incurring a separate suboptimality factor w2, that is due to inflating the heuristic values. Thus, the combination has suboptimality factor w1w2 .In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(w1) for short, that has sub optimality factor w1 rather than w1w2 (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(w1). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(w1) within a given runtime limit.