paper

Average Case Constant Factor Time and Distance Optimal Multi-Robot Path Planning in Well-Connected Environments

arXiv:1706.07255

Abstract

Fast algorithms for optimal multi-robot path planning are sought after in real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and good (e.g., polynomial) running time. In this work, we develop a first low-polynomial running time algorithm, called SplitAngGroup (SaG), that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor makespan optimal solutions on average over all problem instances. That is, SaG is an average case O(1)-approximation algorithm and computes solutions with sub-linear makespan. SaG 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. SaG attains its desirable properties through a careful combination of a novel divide-and-conquer technique, which we denote as global decoupling, and network flow based methods for routing the robots. Solutions from SaG, in a weaker sense, are also a constant factor approximation on total distance optimality.

arXiv comment11 pages, 15 figures, expanded version of MRS 2017 paper, submitted to Autonomous Robots

References in corpus (3)

Cited by in corpus (1)