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.SoCG.2022.12
URN: urn:nbn:de:0030-drops-160203
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16020/
Banyassady, Bahareh ;
de Berg, Mark ;
Bringmann, Karl ;
Buchin, Kevin ;
Fernau, Henning ;
Halperin, Dan ;
Kostitsyna, Irina ;
Okamoto, Yoshio ;
Slot, Stijn
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Abstract
We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end.
If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(n log n + mn + m²) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.
BibTeX - Entry
@InProceedings{banyassady_et_al:LIPIcs.SoCG.2022.12,
author = {Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn},
title = {{Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16020},
URN = {urn:nbn:de:0030-drops-160203},
doi = {10.4230/LIPIcs.SoCG.2022.12},
annote = {Keywords: motion planning, computational geometry, simple polygon}
}
|
Keywords: |
|
motion planning, computational geometry, simple polygon |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
