2015/09/30 by Yamauchi, Yukiko, Uehara, Taichi, Yamashita, Masafumi
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1509.09207
We consider a swarm of autonomous mobile robots each of which is an anonymous point in the three-dimensional Euclidean space (3D-space) and synchronously executes a common distributed algorithm. We investigate the pattern formation problem that requires the robots to form a given target pattern from an initial configuration and characterize the problem by showing a necessary and sufficient condition for the robots to form a given target pattern. The pattern formation problem in the two dimensional Euclidean space (2D-space) has been investigated by Suzuki and Yamashita (SICOMP 1999, TCS 2010), and Fujinaga et al. (SICOMP 2015). The symmetricity ρ(P) of a configuration (i.e., the positions of robots) P is intuitively the order of the cyclic group that acts on P. It has been shown that fully-synchronous (FSYNC) robots can form a target pattern F from an initial configuration P if and only if ρ(P) divides ρ(F). We extend the notion of symmetricity to 3D-space by using the rotation groups each of which is defined by a set of rotation axes and their arrangement. We define the symmetricity \varrho(P) of configuration P in 3D-space as the set of rotation groups that acts on P and whose rotation axes do not contain any robot. We show the following necessary and sufficient condition for the pattern formation problem which is a natural extension of the existing results of the pattern formation problem in 2D-space: FSYNC robots in 3D-space can form a target pattern F from an initial configuration P if and only if \varrho(P) ⊆ \varrho(F). For solvable instances, we present a pattern formation algorithm for oblivious FSYNC robots. The insight of this paper is that symmetry of mobile robots in 3D-space is sometimes lower than the symmetry of their positions and the robots can show their symmetry by their movement.