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

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 m₁ × m₂ gird, m₁ ≥ m₂, our RTH (Rubik Table with Highways) algorithm computes solutions for routing up to^m1m₂ robots with uniformly randomly distributed start 3 and goal configurations with a makespan of m₁ + 2m₂ + o(m₁), with high probability. Because the minimum makespan for such instances is m₁ + m₂ − o(m₁), also with high probability, RTH guarantees^m1+2m₂ m₁+m₂ optimality as m₁ → ∞ for random instances with up to¹ robot density, with high probability. 3 m₁+2m₂ m₁+m₂ ∈ (1, 1.5]. Alongside this key result, we also establish a series of related results supporting even higher robot densities and environments with regularly distributed obstacles, which directly map to real-world parcel sorting scenarios. Building on the baseline methods with provable guarantees, we have developed effective, principled heuristics that further improve the computed optimality of the 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.