We consider the Embedded Pattern Formation (epf) problem introduced in [Fujinaga et al., SIAM J. on Comput., 44(3), 2015]. Given a set F of distinct points in the Euclidean plane (called here fixedpoints) and a set R of robots such that |R| = |F|, the problem asks for a distributed algorithm that moves robots so as to occupy all points in F. Initially, each robot occupies a distinct position. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of the robots’ positions and the fixed-points (Look) according to its own coordinate system, decides whether to move (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are oblivious, anonymous and execute the same algorithm. In the mentioned paper, the problem has been investigated by assuming chirality, that is robots share a common left-right orientation. The obtained solution has been used as a sub-procedure to solve the Pattern Formation problem, without fixed-points but still with chirality. Here we investigate the other branch, that is, we are interested in solving epf without chirality. We fully characterize when the epf problem can be accomplished and we design a deterministic distributed algorithm that solves the problem for all configurations but those identified as unsolvable. Our approach is also characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness.

Asynchronous embedded pattern formation without orientation

CICERONE, SERAFINO;DI STEFANO, GABRIELE;
2016

Abstract

We consider the Embedded Pattern Formation (epf) problem introduced in [Fujinaga et al., SIAM J. on Comput., 44(3), 2015]. Given a set F of distinct points in the Euclidean plane (called here fixedpoints) and a set R of robots such that |R| = |F|, the problem asks for a distributed algorithm that moves robots so as to occupy all points in F. Initially, each robot occupies a distinct position. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of the robots’ positions and the fixed-points (Look) according to its own coordinate system, decides whether to move (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are oblivious, anonymous and execute the same algorithm. In the mentioned paper, the problem has been investigated by assuming chirality, that is robots share a common left-right orientation. The obtained solution has been used as a sub-procedure to solve the Pattern Formation problem, without fixed-points but still with chirality. Here we investigate the other branch, that is, we are interested in solving epf without chirality. We fully characterize when the epf problem can be accomplished and we design a deterministic distributed algorithm that solves the problem for all configurations but those identified as unsolvable. Our approach is also characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness.
9783662534250
File in questo prodotto:
File Dimensione Formato  
2016_disc.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Documento in Pre-print
Licenza: Dominio pubblico
Dimensione 591.88 kB
Formato Adobe PDF
591.88 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11697/111899
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact