Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time

Let $G = (V, E)$ be an $m_1 \times \ldots \times m_k$ grid. Assuming that each $v \in V$ is occupied by a robot and a robot may move to a neighboring vertex in a step via synchronized rotations along cycles of $G$, we first establish that the arbitrary reconfiguration of labeled robots on $G$ can be performed in $O(k\sum_i m_i)$ makespan and requires $O(|V|^2)$ running time in the worst case and $o(|V|^2)$ when $G$ is non-degenerate (i.e., nearly one dimensional). The resulting algorithm, \isag, provides average case $O(1)$-approximate (i.e., constant factor) time optimality guarantee. In the case when all dimensions are of similar size $O(|V|^{\frac{1}{k}})$, the running time of \isag approaches a linear $O(|V|)$. Define $d_g(p)$ as the largest distance between individual initial and goal configurations over all robots for a given problem instance $p$, building on \isag, we develop the \pafalgo (\paf) algorithm that computes $O(d_g(p))$ makespan solutions for $k = 2, 3$ using mostly $o(|V|^2)$ running time. \paf provides worst case $O(1)$-approximation regarding solution time optimality. We note that the worst case running time for the problem is $\Omega(|V|^2)$.