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 Fujinaga et al. SIAM J. Comput., 2015, 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.
|Titolo:||Solving the Pattern Formation by Mobile Robots with Chirality|
|Data di pubblicazione:||2021|
|Appare nelle tipologie:||1.1 Articolo in rivista|