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.

Solving the Pattern Formation by Mobile Robots with Chirality

Cicerone S.;Di Stefano G.;Navarra A.
2021

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 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.
File in questo prodotto:
File Dimensione Formato  
2021_IEEE_Access_2.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Dominio pubblico
Dimensione 1.56 MB
Formato Adobe PDF
1.56 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/169592
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact