[{"title":"Symmetry Preservation in Swarms of Oblivious Robots with Limited  Visibility","date_created":"2024-10-01T13:29:43Z","publisher":"Schloss Dagstuhl -- Leibniz-Zentrum für Informatik","year":"2025","language":[{"iso":"eng"}],"keyword":["Swarm Algorithm","Swarm Robots","Distributed Algorithm","Pattern Formation","Limited Visibility","Oblivious"],"external_id":{"arxiv":["2409.19277"]},"abstract":[{"lang":"eng","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)."}],"publication":"28th International Conference on Principles of Distributed Systems (OPODIS 2024)","main_file_link":[{"url":"https://arxiv.org/abs/2409.19277","open_access":"1"}],"doi":"10.4230/LIPIcs.OPODIS.2024.13","conference":{"location":"Lucca, Italy","end_date":"2024-12-13","start_date":"2024-12-11","name":"28th International Conference on Principles of Distributed Systems (OPODIS 2024)"},"author":[{"orcid":"0009-0002-4750-2051","last_name":"Gerlach","id":"32655","full_name":"Gerlach, Raphael","first_name":"Raphael"},{"id":"97359","full_name":"von der Gracht, Sören","last_name":"von der Gracht","orcid":"0000-0002-8054-2058","first_name":"Sören"},{"full_name":"Hahn, Christopher","last_name":"Hahn","first_name":"Christopher"},{"id":"47213","full_name":"Harbig, Jonas","last_name":"Harbig","first_name":"Jonas"},{"first_name":"Peter","last_name":"Kling","full_name":"Kling, Peter"}],"volume":324,"date_updated":"2025-01-09T11:39:19Z","oa":"1","citation":{"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>","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>.","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>","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)} }"},"intvolume":"       324","publication_status":"published","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-360-7"]},"user_id":"97359","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","department":[{"_id":"101"}],"project":[{"name":"Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme","_id":"106","grant_number":"453112019"}],"_id":"56298","status":"public","editor":[{"last_name":"Bonomi","full_name":"Bonomi, Silvia","first_name":"Silvia"},{"first_name":"Letterio","full_name":"Galletta, Letterio","last_name":"Galletta"},{"first_name":" Etienne","full_name":"Rivière,  Etienne","last_name":"Rivière"},{"full_name":"Schiavoni,  Valerio","last_name":"Schiavoni","first_name":" Valerio"}],"type":"conference"}]