SCIENCE@home

Constant Factor Optimal Multi-Robot Path Planning in Well-Connected Environments

Jingjin Yu

Published 2017 in arXiv.org

ABSTRACT

Fast algorithms for optimal multi-robot path planning are sought after in many real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and fast run time (e.g., polynomial). In this work, we develop a low-polynomial running time algorithm, called SplitAndGroup, that solves the multi-robot path planning problem on grids and grid-like environments and produces constant factor time- and distance-optimal solutions, in expectation. In particular, SplitAndGroup computes solutions with sub-linear makespan. SplitAndGroup is capable of handling cases when the density of robot is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied by robots. SplitAndGroup attains its desirable properties through a careful combination of divide-and-conquer technique and network flow based methods for routing the robots.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    arXiv.org

  • Publication date

    2017-06-22

  • Fields of study

    Computer Science, Engineering

  • Identifiers
    arXiv 1706.07255
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-64 of 64 references · Page 1 of 1

CITED BY

Showing 1-7 of 7 citing papers · Page 1 of 1