We consider the Mutual Visibility problem for anonymous dimensionless robots with obstructed visibility moving in a plane: starting from distinct locations, the robots must reach, without colliding, a configuration where no three of them are collinear. We study this problem in the luminous robots model, in which each robot has a visible light that can assume colors from a fixed set. Among other results, we prove that Mutual Visibility can be solved in SSynch with 2 colors and in ASynch with 3 colors. If an adversary can interrupt and stop a robot moving to its computed destination, Mutual Visibility is still solvable in SSynch with 3 colors and, if the robots agree on the direction of one axis, also in ASynch. As a byproduct, we provide the first obstructed-visibility solutions to two classical problems for oblivious robots: collision-less convergence to a point (also known as near-gathering) and circle formation.

Mutual visibility by luminous robots without collisions / Di Luna, G; Flocchini, P; Gan Chaudhuri, S; Poloni, F; Santoro, N; Viglietta, G. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 254:(2017), pp. 392-418. [10.1016/j.ic.2016.09.005]

Mutual visibility by luminous robots without collisions

Di Luna G
;
2017

Abstract

We consider the Mutual Visibility problem for anonymous dimensionless robots with obstructed visibility moving in a plane: starting from distinct locations, the robots must reach, without colliding, a configuration where no three of them are collinear. We study this problem in the luminous robots model, in which each robot has a visible light that can assume colors from a fixed set. Among other results, we prove that Mutual Visibility can be solved in SSynch with 2 colors and in ASynch with 3 colors. If an adversary can interrupt and stop a robot moving to its computed destination, Mutual Visibility is still solvable in SSynch with 3 colors and, if the robots agree on the direction of one axis, also in ASynch. As a byproduct, we provide the first obstructed-visibility solutions to two classical problems for oblivious robots: collision-less convergence to a point (also known as near-gathering) and circle formation.
2017
Robots; Mobile robots; Deterministic algorithm
01 Pubblicazione su rivista::01a Articolo in rivista
Mutual visibility by luminous robots without collisions / Di Luna, G; Flocchini, P; Gan Chaudhuri, S; Poloni, F; Santoro, N; Viglietta, G. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 254:(2017), pp. 392-418. [10.1016/j.ic.2016.09.005]
File allegati a questo prodotto
File Dimensione Formato  
DiLuna_Mutual-visibility_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 839.28 kB
Formato Adobe PDF
839.28 kB Adobe PDF   Contatta l'autore

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/11573/1328071
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 63
  • ???jsp.display-item.citation.isi??? 36
social impact