Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time
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. The dual guarantee on computational efficiency and solution optimality suggests our proposed general method is promising in significantly scaling up multi-robot applications for logistics, e.g., at large robotic warehouses. 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 includ