Understand
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 (in the current context, a grid is degenerate if it is nearly one dimensional).
- The resulting algorithm, iSAG, provides average case $O(1)$-approximate (i.e., constant-factor) time optimality guarantee.
- When all dimensions are of similar size $O(|V|^{\frac{1}{k}})$, the running time of iSAG approaches a linear $O(|V|)$.