[{"abstract":[{"text":"In the general pattern formation (GPF) problem, a swarm of simple autonomous,\r\ndisoriented robots must form a given pattern. The robots' simplicity imply a\r\nstrong limitation: When the initial configuration is rotationally symmetric,\r\nonly patterns with a similar symmetry can be formed [Yamashita, Suzyuki; TCS\r\n2010]. The only known algorithm to form large patterns with limited visibility\r\nand without memory requires the robots to start in a near-gathering (a swarm of\r\nconstant diameter) [Hahn et al.; SAND 2024]. However, not only do we not know\r\nany near-gathering algorithm guaranteed to preserve symmetry but most natural\r\ngathering strategies trivially increase symmetries [Castenow et al.; OPODIS\r\n2022].\r\n  Thus, we study near-gathering without changing the swarm's rotational\r\nsymmetry for disoriented, oblivious robots with limited visibility (the\r\nOBLOT-model, see [Flocchini et al.; 2019]). We introduce a technique based on\r\nthe theory of dynamical systems to analyze how a given algorithm affects\r\nsymmetry and provide sufficient conditions for symmetry preservation. Until\r\nnow, it was unknown whether the considered OBLOT-model allows for any\r\nnon-trivial algorithm that always preserves symmetry. Our first result shows\r\nthat a variant of Go-to-the-Average always preserves symmetry but may sometimes\r\nlead to multiple, unconnected near-gathering clusters. Our second result is a\r\nsymmetry-preserving near-gathering algorithm that works on swarms with a convex\r\nboundary (the outer boundary of the unit disc graph) and without holes (circles\r\nof diameter 1 inside the boundary without any robots).","lang":"eng"}],"publication":"28th International Conference on Principles of Distributed Systems (OPODIS 2024)","keyword":["Swarm Algorithm","Swarm Robots","Distributed Algorithm","Pattern Formation","Limited Visibility","Oblivious"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2409.19277"]},"year":"2025","title":"Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility","publisher":"Schloss Dagstuhl -- Leibniz-Zentrum für Informatik","date_created":"2024-10-01T13:29:43Z","editor":[{"full_name":"Bonomi, Silvia","last_name":"Bonomi","first_name":"Silvia"},{"last_name":"Galletta","full_name":"Galletta, Letterio","first_name":"Letterio"},{"first_name":" Etienne","last_name":"Rivière","full_name":"Rivière,  Etienne"},{"first_name":" Valerio","full_name":"Schiavoni,  Valerio","last_name":"Schiavoni"}],"status":"public","type":"conference","_id":"56298","project":[{"name":"Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme","_id":"106","grant_number":"453112019"}],"department":[{"_id":"101"}],"user_id":"97359","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","intvolume":"       324","citation":{"chicago":"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>.","ieee":"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>.","ama":"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>","mla":"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>.","short":"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.","bibtex":"@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)} }","apa":"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>"},"publication_identifier":{"isbn":["978-3-95977-360-7"],"issn":["1868-8969"]},"publication_status":"published","conference":{"name":"28th International Conference on Principles of Distributed Systems (OPODIS 2024)","start_date":"2024-12-11","end_date":"2024-12-13","location":"Lucca, Italy"},"doi":"10.4230/LIPIcs.OPODIS.2024.13","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2409.19277"}],"oa":"1","date_updated":"2025-01-09T11:39:19Z","volume":324,"author":[{"last_name":"Gerlach","orcid":"0009-0002-4750-2051","full_name":"Gerlach, Raphael","id":"32655","first_name":"Raphael"},{"first_name":"Sören","orcid":"0000-0002-8054-2058","last_name":"von der Gracht","full_name":"von der Gracht, Sören","id":"97359"},{"first_name":"Christopher","last_name":"Hahn","full_name":"Hahn, Christopher"},{"first_name":"Jonas","last_name":"Harbig","full_name":"Harbig, Jonas","id":"47213"},{"first_name":"Peter","full_name":"Kling, Peter","last_name":"Kling"}]}]