conference paper published Raphael Gerlach author 326550009-0002-4750-2051 Sören von der Gracht author 973590000-0002-8054-2058 Christopher Hahn author Jonas Harbig author 47213 Peter Kling author SilviaBonomi editor LetterioGalletta editor EtienneRivière editor ValerioSchiavoni editor 101 department 28th International Conference on Principles of Distributed Systems (OPODIS 2024) Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme project 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 [Yamashita, Suzyuki; TCS 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) [Hahn et al.; SAND 2024]. However, not only do we not know any near-gathering algorithm guaranteed to preserve symmetry but most natural gathering strategies trivially increase symmetries [Castenow et al.; OPODIS 2022]. Thus, we study near-gathering without changing the swarm's rotational symmetry for disoriented, oblivious robots with limited visibility (the OBLOT-model, see [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 Informatik2025Lucca, Italy eng Swarm AlgorithmSwarm RobotsDistributed AlgorithmPattern FormationLimited VisibilityOblivious 1868-8969 978-3-95977-360-7 2409.1927710.4230/LIPIcs.OPODIS.2024.13 324 Gerlach, Raphael, et al. “Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility.” <i>28th International Conference on Principles of Distributed Systems (OPODIS 2024)</i>, edited by Silvia Bonomi et al., vol. 324, Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2025, doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">10.4230/LIPIcs.OPODIS.2024.13</a>. Gerlach R, von der Gracht S, Hahn C, Harbig J, Kling P. Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility. In: Bonomi S, Galletta L, Rivière Etienne, Schiavoni Valerio, eds. <i>28th International Conference on Principles of Distributed Systems (OPODIS 2024)</i>. Vol 324. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">10.4230/LIPIcs.OPODIS.2024.13</a> @inproceedings{Gerlach_von der Gracht_Hahn_Harbig_Kling_2025, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility}, volume={324}, DOI={<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">10.4230/LIPIcs.OPODIS.2024.13</a>}, booktitle={28th International Conference on Principles of Distributed Systems (OPODIS 2024)}, publisher={Schloss Dagstuhl -- Leibniz-Zentrum für Informatik}, author={Gerlach, Raphael and von der Gracht, Sören and Hahn, Christopher and Harbig, Jonas and Kling, Peter}, editor={Bonomi, Silvia and Galletta, Letterio and Rivière, Etienne and Schiavoni, Valerio}, year={2025}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} } Gerlach, R., von der Gracht, S., Hahn, C., Harbig, J., &#38; Kling, P. (2025). Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility. In S. Bonomi, L. Galletta, Etienne Rivière, &#38; Valerio Schiavoni (Eds.), <i>28th International Conference on Principles of Distributed Systems (OPODIS 2024)</i> (Vol. 324). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">https://doi.org/10.4230/LIPIcs.OPODIS.2024.13</a> R. Gerlach, S. von der Gracht, C. Hahn, J. Harbig, and P. Kling, “Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility,” in <i>28th International Conference on Principles of Distributed Systems (OPODIS 2024)</i>, Lucca, Italy, 2025, vol. 324, doi: <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">10.4230/LIPIcs.OPODIS.2024.13</a>. R. Gerlach, S. von der Gracht, C. Hahn, J. Harbig, P. Kling, in: S. Bonomi, L. Galletta, Etienne Rivière, Valerio Schiavoni (Eds.), 28th International Conference on Principles of Distributed Systems (OPODIS 2024), Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2025. Gerlach, Raphael, Sören von der Gracht, Christopher Hahn, Jonas Harbig, and Peter Kling. “Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility.” In <i>28th International Conference on Principles of Distributed Systems (OPODIS 2024)</i>, edited by Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, Vol. 324. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2024.13">https://doi.org/10.4230/LIPIcs.OPODIS.2024.13</a>. 562982024-10-01T13:29:43Z2025-01-09T11:39:19Z