# Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

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" }

[download]

## Full Text

[download]