Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian, and Sven Koenig. Improved solvers for bounded-suboptimal multi-agent path finding. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 3067–3074. 2016. URL: http://www.ijcai.org/Abstract/16/435.
[full text] [slides] [BibTeX▼]

## 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($$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.