2026-07-26T16:44:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19892 2024-05-31T08:33:44Z ddc:004 open_access

Forming Large Patterns with Local Robots in the OBLOT Model Hahn, Christopher Harbig, Jonas Kling, Peter Swarm Algorithm Swarm Robots Distributed Algorithm Pattern Formation Limited Visibility Oblivious In the arbitrary pattern formation problem, n autonomous, mobile robots must form an arbitrary pattern P ⊆ R². The (deterministic) robots are typically assumed to be indistinguishable, disoriented, and unable to communicate. An important distinction is whether robots have memory and/or a limited viewing range. Previous work managed to form P under a natural symmetry condition if robots have no memory but an unlimited viewing range [Masafumi Yamashita and Ichiro Suzuki, 2010] or if robots have a limited viewing range but memory [Yukiko Yamauchi and Masafumi Yamashita, 2013]. In the latter case, P is only formed in a shrunk version that has constant diameter. Without memory and with limited viewing range, forming arbitrary patterns remains an open problem. We provide a partial solution by showing that P can be formed under the same symmetry condition if the robots' initial diameter is ≤ 1. Our protocol partitions P into rotation-symmetric components and exploits the initial mutual visibility to form one cluster per component. Using a careful placement of the clusters and their robots, we show that a cluster can move in a coordinated way through its component while "drawing" P by dropping one robot per pattern coordinate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christopher Hahn and Jonas Harbig and Peter Kling 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.14 urn:nbn:de:0030-drops-198924 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode