Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids
Jingjin Yu · 2018
Let G = (V, E) be an m1 × . . .× m k grid for some arbitrary constant k.We establish that O( k i=1 mi) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multirobot path planning can be realized on G in O(|V | 2 ) running time, even when vertices of G are fully occupied by robots.When all dimensions are of equal sizes, the running time approaches O(|V |).Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V | 2 ) time for two and three dimensions.We note that the problem has a worst case running time lower bound of Ω(|V | 2 ).