AO-ARC: Almost-Surely Asymptotically Optimal Multi-Robot Motion Planning with ARC
Provides a practical anytime MRMP method with optimality guarantees for robotics practitioners needing fast initial solutions and eventual optimality.
AO-ARC achieves initial solution times comparable to state-of-the-art feasibility solvers for multi-robot motion planning while converging faster and more reliably than existing anytime methods as robot count increases, with theoretical guarantees of asymptotic optimality.
We present AO-ARC, an anytime multi-robot motion planning (MRMP) method that achieves initial solution times on par with state-of-the-art MRMP feasibility solvers while converging faster and more reliably than existing anytime MRMP methods as the number of robots increases. AO-ARC adapts the AO-x meta-algorithm for converting feasibility solvers into anytime algorithms by iteratively calling the original ARC method on bounded MRMP instances under a makespan cost metric. This exploits the adaptive (de)coupling of ARC while maintaining the consistent cost bound across robot (de)compositions needed for AO-x. We provide theoretical analysis proving the asymptotic optimality properties of AO- ARC and conduct empirical evaluation on a set of 2D scenarios with different levels of coordination complexity and a 3D manipulator scenario representative of real-world applications.