In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi- synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i.e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane

Navarra, Alfredo
Writing – Original Draft Preparation
2018

Abstract

In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi- synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i.e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.
2018
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11391/1439921
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 18
social impact