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