2026-07-21T20:03:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22549 2025-10-02T11:05:54Z ddc:004 open_access

Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility Gerlach, Raphael von der Gracht, Sören Hahn, Christopher Harbig, Jonas Kling, Peter Swarm Algorithm Swarm Robots Distributed Algorithm Pattern Formation Limited Visibility Oblivious In the general pattern formation (GPF) problem, a swarm of simple autonomous, disoriented robots must form a given pattern. The robots' simplicity imply a strong limitation: When the initial configuration is rotationally symmetric, only patterns with a similar symmetry can be formed [Masafumi Yamashita and Ichiro Suzuki, 2010]. The only known algorithm to form large patterns with limited visibility and without memory requires the robots to start in a near-gathering (a swarm of constant diameter) [Christopher Hahn et al., 2024]. However, not only do we not know any near-gathering algorithm guaranteed to preserve symmetry but most natural gathering strategies trivially increase symmetries [Jannik Castenow et al., 2022]. Thus, we study near-gathering without changing the swarm’s rotational symmetry for disoriented, oblivious robots with limited visibility (the OBLOT-model, see [Paola Flocchini et al., 2019]). We introduce a technique based on the theory of dynamical systems to analyze how a given algorithm affects symmetry and provide sufficient conditions for symmetry preservation. Until now, it was unknown whether the considered OBLOT-model allows for any non-trivial algorithm that always preserves symmetry. Our first result shows that a variant of Go-To-The-Average always preserves symmetry but may sometimes lead to multiple, unconnected near-gathering clusters. Our second result is a symmetry-preserving near-gathering algorithm that works on swarms with a convex boundary (the outer boundary of the unit disc graph) and without "holes" (circles of diameter 1 inside the boundary without any robots). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raphael Gerlach and Sören von der Gracht and Christopher Hahn and Jonas Harbig and Peter Kling 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.13 urn:nbn:de:0030-drops-225490 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode