License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.9
URN: urn:nbn:de:0030-drops-154423
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15442/
Go to the corresponding LIPIcs Volume Portal

Fekete, Sándor P. ; Keldenich, Phillip ; Kosfeld, Ramin ; Rieck, Christian ; Scheffer, Christian

Connected Coordinated Motion Planning with Bounded Stretch

pdf-format:
LIPIcs-ISAAC-2021-9.pdf (12 MB)

Abstract

We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.
On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is ?(d), which is optimal up to constant factors.

BibTeX - Entry

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2021.9,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Kosfeld, Ramin and Rieck, Christian and Scheffer, Christian},
  title =	{{Connected Coordinated Motion Planning with Bounded Stretch}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15442},
  URN =		{urn:nbn:de:0030-drops-154423},
  doi =		{10.4230/LIPIcs.ISAAC.2021.9},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}

Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

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