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.OPODIS.2022.15
URN: urn:nbn:de:0030-drops-176350
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17635/
Castenow, Jannik ;
Harbig, Jonas ;
Jung, Daniel ;
Kling, Peter ;
Knollmann, Till ;
Meyer auf der Heide, Friedhelm
A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility
Abstract
We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related NearGathering task, they must reach distinct positions in close proximity such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in ?(n + Δ²) synchronous rounds both in two and three dimensions, where Δ denotes the initial maximal distance of two robots [Hideki Ando et al., 1999; Michael Braun et al., 2020; Bastian Degener et al., 2011].
In this work, we formalize a key property of efficient Gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in ?(Δ²) synchronous rounds, for d ≥ 2. For d = 1, any λ-contracting protocol gathers in optimal time ?(Δ). Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside the local convex hulls of their neighborhoods - λ-contracting protocols have this property - requires Ω(Δ²) rounds to gather all robots (d > 1). Among others, we prove that the d-dimensional generalization of the GTC-protocol [Hideki Ando et al., 1999] is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d.
We also introduce an approach to make any λ-contracting protocol collision-free (robots never occupy the same position) to solve NearGathering. The resulting protocols maintain the runtime of Θ (Δ²) and work even in the semi-synchronous model. This yields the first NearGathering protocols for disoriented robots and the first proven runtime bound. In particular, combined with results from [Paola Flocchini et al., 2017] for robots with global visibility, we obtain the first protocol to solve Uniform Circle Formation (arrange the robots on the vertices of a regular n-gon) for oblivious, disoriented robots with limited visibility.
BibTeX - Entry
@InProceedings{castenow_et_al:LIPIcs.OPODIS.2022.15,
author = {Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm},
title = {{A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {15:1--15:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17635},
URN = {urn:nbn:de:0030-drops-176350},
doi = {10.4230/LIPIcs.OPODIS.2022.15},
annote = {Keywords: mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering}
}
|
Keywords: |
|
mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering |
|
Collection: |
|
26th International Conference on Principles of Distributed Systems (OPODIS 2022) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
15.02.2023 |
