2018/11/02 by Bose, Kaustav, Adhikary, Ranendu, Kundu, Manash Kumar +1 · 1 citation
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1811.00834
The Arbitrary Pattern Formation problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not agree on any common global coordinate system or chirality. We have shown that a set of robots can form any arbitrary pattern, if their starting configuration is asymmetric.