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 the 25th International Joint Conference on Artificial Intelligence (IJCAI), 3067–3074. 2016. URL: http://www.ijcai.org/Abstract/16/435.
[BibTeX] [full text]

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

## BibTeX

@inproceedings{cohen2016,
author = "Cohen, Liron and Uras, Tansel and Kumar, T. K. Satish and Xu, Hong and Ayanian, Nora and Koenig, Sven",
year = "2016",
pages = "3067--3074",
url = "http://www.ijcai.org/Abstract/16/435",
booktitle = "the 25th International Joint Conference on Artificial Intelligence ({IJCAI})",
title = "Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding"
}