Forming sequences of geometric patterns with oblivious mobile robots

We study the computational power of distributed systems consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception, allowing them to see each other, but they do not have any means of explicit communication with each other. Further the robots are oblivious, meaning that they always act based on their current perception of the environment, and they have no memory of the past. Such system of simple robots have been studied extensively with the objective of achieving coordinated tasks e.g. arranging the robots in a line or a circle. In fact it has been shown that obliviousness is not a limiting factor to form a single geometric pattern, however arbitrary. This paper aims to understand the computational limits imposed by the obliviousness of the robots by studying the formation of a series of geometric patterns instead of a single pattern. If such a series of patterns could be formed this would create some form of memory in an otherwise memory-less system. We show that, under particular conditions, oblivious robot systems can indeed form a given series of geometric patterns starting from any arbitrary configuration. More precisely, we characterize the series of patterns that can be formed by oblivious robot systems under various additional restrictions such as anonymity, asynchrony and lack of common orientation. These results provide strong indications that oblivious solutions may be obtained also for tasks that intuitively seem to require memory.