Search
Close this search box.

Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons

Abstract

We consider the following motion-planning problem: we are given \(m\) unit discs in a simple polygon with n vertices, each at their own start position, and we want to move the discs to a given set of \(m\) target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in \(O(mn+m^2)\) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multi-robot motion planning problem for discs moving in a simple polygon, which is known to be strongly NP-hard.

Illustration of the technique described in the paper.
Illustration of the technique described in the paper. The free space is decomposed into regions and modeled as a graph. In order to solve the unlabeled problem we solve a special case of a pebble problem, which is a discrete version of the multi-robot problem. A solution to the pebble problem can be transformed into a set of collision free paths for the continuous unlabeled problem.

Links

  • Aviv Adler, Mark de Berg, Dan Halperin and Kiril Solovey (*alphabetical order)
    Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons
    Transactions on Automation Science and Engineering (T-ASE), 2015 [link][bibtex]
    Algorithmic Foundations of Robotics XI, Volume 107 of STAR, 2014 [link][bibtex]
    arXiv:1312.1038v3, 2013 [link][bibtex]

Contacts

Aviv Adler
Dan Halperin
Kiril Solovey
Mark de Berg 
@article{adhs-emrpu-13,
  author       = {Aviv Adler and Mark de Berg and Dan Halperin and Kiril Solovey},
  title        = {Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons},
  journal      = {CoRR},
  volume       = {abs/1312.1038},
  year         = {2013},
  url          = {http://arxiv.org/abs/1312.1038},
  eprinttype   = {arXiv},
  eprint       = {1312.1038},
  timestamp    = {Mon, 13 Aug 2018 16:47:10 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/AdlerBHS13.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{adhs-emrpu-15,
  author = {Aviv Adler and Mark de Berg and Dan Halperin and Kiril Solovey},
  editor = {H. Levent Akin and Nancy M. Amato and Volkan Isler and A. Frank van der Stappen},
  title = {Efficient Multi-robot Motion Planning for Unlabeled Discs in Simple Polygons},
  bookTitle = {Algorithmic Foundations of Robotics XI: Selected Contributions of the 11th International Workshop on the Algorithmic Foundations of Robotics ({WAFR})},
  series = {Springer Tracts in Advanced Robotics ({STAR})},
  volume = {107},
  year = {2015},
  publisher = {Springer},
  pages = {1--17},
  doi = {10.1007/978-3-319-16595-0_1}
}

@article{adhs-emrpu-15,
  author = {Aviv Adler and Mark de Berg and Dan Halperin and Kiril Solovey},
  journal = {IEEE Transactions on Automation Science and Engineering}, 
  title = {Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons}, 
  year = {2015},
  volume = {12},
  number = {4},
  pages = {1309-1317},
  doi = {10.1109/TASE.2015.2470096}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content