UIUC's AO-ARC algorithm speeds multi-robot planning with guaranteed optimality

Researchers James Motes, Marco Morales, and Nancy Amato from the University of Illinois at Urbana-Champaign have developed AO-ARC, a new algorithm for multi-robot motion planning (MRMP) that achieves both fast initial solutions and long-term optimality. The method treats MRMP as an anytime problem—where a feasible solution is needed quickly but can be improved over time. AO-ARC builds on the ARC (Adaptive Robot Compositions) method, which dynamically (de)couples robots during planning, and integrates it with the AO-x meta-algorithm for converting feasibility solvers into anytime algorithms. By iteratively calling ARC on bounded problem instances under a makespan cost metric, AO-ARC maintains consistent cost bounds across different robot groupings, enabling it to converge to near-optimal paths as computation time increases.

The team provides a theoretical proof that AO-ARC is almost-surely asymptotically optimal, meaning it converges to the optimal solution with probability 1 as runtime grows. Empirical tests in 2D environments with varying coordination complexity and a 3D manipulator scenario show that AO-ARC matches the speed of state-of-the-art feasibility solvers for initial solutions, then continues improving more reliably than existing anytime methods as the number of robots scales. This makes it particularly promising for warehouse logistics, autonomous vehicle fleets, and industrial robotics where many agents must navigate without collisions while meeting strict time constraints. The code is available on arXiv.