Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

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(\(w_1\)) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor \(w_1\), that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(\(w_1\)) and speed it up, at the cost of incurring a separate suboptimality factor \(w_2\), that is due to inflating the heuristic values. Thus, the combination has suboptimality factor \(w_1 w_2\). In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(\(w_1\)) for short, that has suboptimality factor \(w_1\) rather than \(w_1 w_2\) (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(\(w_1\)). 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(\(w_1\)) within a given runtime limit.