Pattern Formation by Autonomous Robots Without Chirality

摘要

Consider a set of anonymous mobile robots, and the patterns they can collectively form in the plane. If each robot has a compass needle that indicates North but there is no agreement on East and West (i.e., no chirality), it is known that every arbitrary pattern given in input can be formed if and only if the number of robots is odd. In this paper we study what patterns can be formed by an even number of such robots, and provide a complete characterization. We identify the class of patterns which cannot be formed by an even number of anonymous robots without chirality, regardless of additional capabilities. We then construct a set of rules (distributed algorithm) which leads the robots to form any of the other patterns in finite time. The algorithm is collision-free, completely oblivious and fully asynchronous.