SEAR: A Polynomial- Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee

Shuai D. Han, Edgar J. Rodriguez, Jingjin Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We study the labeled multi-robot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constant-factor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but non-polynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on the microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline.

Original languageEnglish (US)
Title of host publication2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages7967-7974
Number of pages8
ISBN (Electronic)9781538680940
DOIs
StatePublished - Dec 27 2018
Event2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018 - Madrid, Spain
Duration: Oct 1 2018Oct 5 2018

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866

Conference

Conference2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018
Country/TerritorySpain
CityMadrid
Period10/1/1810/5/18

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'SEAR: A Polynomial- Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee'. Together they form a unique fingerprint.

Cite this