Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time
share
Let G = (V, E) be an m_1 ×...× m_k 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(k∑_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, , 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|^1/k), the running time of 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 , we develop the () algorithm that computes O(d_g(p)) makespan solutions for k = 2, 3 using mostly o(|V|^2) running time. provides worst case O(1)-approximation regarding solution time optimality. We note that the worst case running time for the problem is Ω(|V|^2).
READ FULL TEXT