Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time

Teng Guo, Jingjin Yu (Rutgers University)
	Paper #057

Abstract

It is well-known that graph-based multi-robot path planning (MRPP) is NP-hard to optimally solve. In this work, we propose the first low polynomial-time algorithm for MRPP achieving 1–1.5 asymptotic optimality guarantees on solution makespan (i.e., the time it takes to complete a reconfiguration of the robots) for random instances under very high robot density, with high probability. Specifically, on an m1×m2 gird, m1 ≥m2, our RTH (Rubik Table with Highways) algorithm computes solutions for routing up to m1m2/3 robots with uniformly randomly distributed start and goal configurations with a makespan of m1 +2m2 +o(m1), with high probability. Because the minimum makespan for such instances is m1 +m2 −o(m1), also with high probability, RTH guarantees m1+2m2 m1+m2 optimality as m1 → ∞ for random instances with up to 1/3 robot density, with high probability (m1+2m2)/(m1+m2) ∈(1,1.5]. Alongside the above-mentioned key result, we also establish: (1) for completely filled grids, i.e., m1m2 robots, any MRPP instance may be solved in polynomial time under a makespan of 7m1 + 14m2, (2) for m1m2/3 robots, RTH solves arbitrary MRPP instances with makespan of 3m1 + 4m2 + o(m1), (3) for m1m2/2 robots, a variation of RTH solves a random MRPP instance with the same 1-1.5 optimality guarantee, and (4) the same (m1+2m2)/(m1+m2) optimality guarantee holds for regularly distributed obstacles at 1/9 density together with 2m1m2/9 randomly distributed robots; such settings directly map to real-world parcel sorting scenarios. Moreover, we have developed effective, principled heuristics that further improve the computed optimality of RTH algorithms. In extensive numerical evaluations, RTH and its variants demonstrate exceptional scalability as compared with methods including ECBS and DDM, scaling to over 450 ×300 grids with 45,000 robots, and consistently achieves makespan around 1.5 optimal or better, as predicted by our theoretical analysis