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

Let G = (V, E) be an m1 × ldots × mk grid. Assuming that each v ∈ 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(ksumi mi) 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|^frac1k), the running time of iSAG approaches a linear O(|V|). Define dg(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 PartitionAndFlow (PAF) algorithm that computes O(dg(p)) makespan solutions for arbitrary fixed k ≥ 2, 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).