  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 makespan 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_1\times m_2$ gird, $m_1 \ge m_2$, our RTH (Rubik Table
with Highways) algorithm computes solutions for routing up to
$\frac{m_1m_2}{3}$ robots with uniformly randomly distributed start and goal
configurations with a makespan of $m_1 + 2m_2 + o(m_1)$, with high probability.
Because the minimum makespan for such instances is $m_1 + m_2 - o(m_1)$, also
with high probability, RTH guarantees $\frac{m_1+2m_2}{m_1+m_2}$ optimality as
$m_1 \to \infty$ for random instances with up to $\frac{1}{3}$ robot density,
with high probability. $\frac{m_1+2m_2}{m_1+m_2} \in (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 \times 300$ grids with $45,000$ robots, and
consistently achieves makespan around $1.5$ optimal or better, as predicted by
our theoretical analysis.
