SEAR: A Polynomial-Time Expected Constant-Factor Optimal Algorithmic Framework for Multi-Robot Path Planning.

Abstract

This work studies the labeled multi-robot path and motion planning problem in continuous domains, in the absence of static obstacles. Given $n$ robots which may be arbitrarily close to each other and assuming random start and goal configurations for the robots, we derived an $O(n^3)$, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation. Furthermore, our algorithm only requires a small constant factor expansion of the initial and goal configuration footprints for solving the problem. In addition to strong theoretical guarantees, we present a thorough computational evaluation of the proposed solution. Beyond the baseline solution, adapting an effective (but non-polynomial time) robot routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline.