Characterizing geometric patterns formable by oblivious anonymous mobile robots

In a system in which anonymous mobile robots repeatedly execute a “Look–Compute–Move” cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. This paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. Therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. Related results on the pattern convergence problem are also presented.