DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2024.13

Computational Power of Opaque Robots

Authors: Caterina Feletti, Lucia Mambretti, Carlo Mereghetti, and Beatrice Palano

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

In the field of distributed computing by robot swarms, the research comprehends manifold models where robots operate in the Euclidean plane through a sequence of look-compute-move cycles. Models under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, and (iii) the synchronization mode. By varying features (i,ii), we obtain the noted four base models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Combining each base model with the three main synchronization modes (fully synchronous, semi-synchronous, and asynchronous), we obtain the well-known 12 models. Extensive research has studied their computational power, proving the hierarchical relations between different models. However, only transparent robots have been considered. In this work, we study the taxonomy of the 12 models considering collision-intolerant opaque robots. We present six witness problems that prove the majority of the computational relations between the 12 models. In particular, the last witness problem depicts a peculiar issue occurring in the case of obstructed visibility and asynchrony.

Cite as

Caterina Feletti, Lucia Mambretti, Carlo Mereghetti, and Beatrice Palano. Computational Power of Opaque Robots. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.SAND.2024.13,
  author =	{Feletti, Caterina and Mambretti, Lucia and Mereghetti, Carlo and Palano, Beatrice},
  title =	{{Computational Power of Opaque Robots}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.13},
  URN =		{urn:nbn:de:0030-drops-198913},
  doi =		{10.4230/LIPIcs.SAND.2024.13},
  annote =	{Keywords: Mobile robots, Look-Compute-Move, Computational complexity, Opaque robots, Distributed computing, Obstructed visibility, Collision intolerance}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.5

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots

Authors: Caterina Feletti, Carlo Mereghetti, and Beatrice Palano

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated. In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and 𝒪(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses 𝒪(log n) epochs still maintaining a constant amount of colors.

Cite as

Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. 𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.OPODIS.2023.5,
  author =	{Feletti, Caterina and Mereghetti, Carlo and Palano, Beatrice},
  title =	{{𝒪(log\{n\})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.5},
  URN =		{urn:nbn:de:0030-drops-194956},
  doi =		{10.4230/LIPIcs.OPODIS.2023.5},
  annote =	{Keywords: Autonomous mobile robots, Opaque robots, Luminous robots, Pattern formation}
}

Search Results

Documents authored by Mereghetti, Carlo

Computational Power of Opaque Robots

Abstract

Cite as

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots

Abstract

Cite as

Thanks for your feedback!

Could not send message