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
Go to the corresponding LIPIcs Volume Portal

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

LIPIcs-OPODIS-2022-15.pdf (1 MB)


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

  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 =		{},
  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

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