Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids

Abstract

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 ).