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/
Fekete, Sándor P. ;
Keldenich, Phillip ;
Kosfeld, Ramin ;
Rieck, Christian ;
Scheffer, Christian
Connected Coordinated Motion Planning with Bounded Stretch
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 |