2024/04/03 by Hahn, Christopher, Harbig, Jonas, Kling, Peter
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotics (cs.RO)
paper · doi:10.48550/arxiv.2404.02771
In the arbitrary pattern formation problem, n autonomous, mobile robots must form an arbitrary pattern P ⊆ ℝ2. 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 [22] or if robots have a limited viewing range but memory [25]. 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.