부산대학교 도서관

Among fundamental problems in the context of distributed computing by mobile robots, the Pattern Formation (PF) is certainly the most representative. Given a multi-set $F$ of points in the Euclidean plane and a set $R$ of robots such that $|R|=|F|$ , PF asks for a distributed algorithm that moves robots so as to reach a configuration similar to $F$ . Similarity means that robots must be disposed as $F$ regardless of translations, rotations, reflections, uniform scalings. In the literature, PF has been approached by assuming asynchronous robots endowed with chirality, i.e. a common handedness. The proposed algorithm along with its correctness proof turned out to be flawed. In this paper, we propose a new algorithm on the basis of a recent methodology studied for approaching problems in the context of distributed computing by mobile robots. According to this methodology, the correctness proof results to be well-structured and less prone to faulty arguments. We then ultimately characterize PF when chirality is assumed.