Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility
<|reference_start|>Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility: 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).<|reference_end|>
@article{gerlach2024symmetry,
    title={Symmetry Preservation in Swarms of Oblivious Robots with Limited
  Visibility},
    author={Raphael Gerlach and S"oren von der Gracht and Christopher Hahn and
  Jonas Harbig and Peter Kling},
    journal={arXiv preprint arXiv:2409.19277},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.19277},
    primaryClass={cs.RO cs.DS}
}