Robotics: Science and Systems XIV
Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids
Jingjin YuAbstract:
Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot 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 \Omega(|V|^2).
Bibtex:
@INPROCEEDINGS{Yu-RSS-18, AUTHOR = {Jingjin Yu}, TITLE = {Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2018}, ADDRESS = {Pittsburgh, Pennsylvania}, MONTH = {June}, DOI = {10.15607/RSS.2018.XIV.013} }