Robotics: Science and Systems XIV

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

Jingjin Yu

Abstract:

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

Download:

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} 
}