Symmetry of Anonymous Robots

摘要

Symmetry of anonymous mobile robots imposes many impossibilities. We focus on the formation problem that requires the robots to form a target pattern. We consider the robots moving in the three-dimensional space and the two-dimensional space (3D and 2D space, respectively) and introduce the notion of symmetricity of a set of points that represents the set of rotation groups that the robots cannot resolve. However, the symmetricity does not always match the rotational symmetry of geometric positions of the robots. We demonstrate that the robots are capable of breaking symmetry by their movement in some cases. The goal of this chapter is to present the following characterization of formable patterns; anonymous synchronous mobile robots in 3D space or 2D space can form a target pattern from an initial configuration if and only if the symmetricity of an initial configuration is a subset of the symmetricity of the target pattern.