Title: Average Case Constant Factor Time and Distance Optimal Multi-Robot Path Planning in Well-Connected Environments,
Abstract: Fast algorithms for optimal multi-robot path planning are sought after in
many real-world applications. Known methods, however, generally do not
simultaneously guarantee good solution optimality and fast run time (e.g.,
polynomial). In this work, we develop a low-polynomial running time algorithm,
called SplitAndGroup (SAG),that solves the multi-robot path planning problem on
grids and grid-like environments and produces constant factor makespan-optimal
solutions in the average case. That is, SAG is an average case
O(1)-approximation algorithm. SAG computes solutions with sub-linear makespan
and is capable of handling cases when the density of robots is extremely high -
in a graph-theoretic setting, the algorithm supports cases where all vertices
of the underlying graph are occupied by robots. SAG attains its desirable
properties through a careful combination of divide-and-conquer technique and
network flow based methods for routing the robots. Solutions from SAG, in a
weaker sense, is also a constant factor approximation on total distance
optimality.