License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.74
URN: urn:nbn:de:0030-drops-87872
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8787/
Go to the corresponding LIPIcs Volume Portal

Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Konitzny, Matthias ; Lin, Lillian ; Scheffer, Christian

Coordinated Motion Planning: The Video (Multimedia Exposition)

pdf-format:
LIPIcs-SoCG-2018-74.pdf (7 MB)

Abstract

We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.

BibTeX - Entry

@InProceedings{becker_et_al:LIPIcs:2018:8787,
  author =	{Aaron T. Becker and S{\'a}ndor P. Fekete and Phillip Keldenich and Matthias Konitzny and Lillian Lin and Christian Scheffer},
  title =	{{Coordinated Motion Planning: The Video (Multimedia Exposition)}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{74:1--74:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8787},
  URN =		{urn:nbn:de:0030-drops-87872},
  doi =		{10.4230/LIPIcs.SoCG.2018.74},
  annote =	{Keywords: Motion planning, robot swarms, complexity, stretch, approximation}
}

Keywords: Motion planning, robot swarms, complexity, stretch, approximation
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI