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

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

## Full Text

[download]