2026-07-25T02:21:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19891 2024-05-31T08:33:44Z ddc:004 open_access

Computational Power of Opaque Robots Feletti, Caterina Mambretti, Lucia Mereghetti, Carlo Palano, Beatrice Mobile robots Look-Compute-Move Computational complexity Opaque robots Distributed computing Obstructed visibility Collision intolerance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Caterina Feletti and Lucia Mambretti and Carlo Mereghetti and Beatrice Palano 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.13 urn:nbn:de:0030-drops-198913 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode