Solving the Pattern Formation by Mobile Robots With Chirality

Abstract

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.

Keywords

• Distributed algorithms
• mobile robots
• asynchrony
• pattern formation