Robots with lights is a model of autonomous mobile computational entties operating in the plane in Look-Compute-Move cycles: each agent has an externally visible light which can assume colors from a fixed set; the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The investigation of computability in this model is under way, and several results have been recently established. In these investigations, however, an agent is assumed to be capable to see through another agent. In this paper we start the study of computing when visibility is obstructable, and investigate the most basic problem for this setting, Complete Visibility: The agents must reach within finite time a configuration where they can all see each other and terminate. We do not make any assumption on a-priori knowledge of the number of agents, on rigidity of movements nor on chirality. The local coordinate system of an agent may change at each activation. Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that Complete Visibility is always solvable, even in the asynchronous setting, without collisions and using a small constant number of colors. The proof is constructive. We also show how to extend our protocol for Complete Visibility so that, with the same number of colors, the agents solve the (non-uniform) Circle Formation problem with obstructed visibility.

Robots with Lights: Overcoming Obstructed Visibility Without Colliding / DI LUNA, GIUSEPPE ANTONIO; Flocchini, Paola; Gan Chaudhuri, Sruti; Santoro, Nicola; Viglietta, Giovanni. - 8756:(2014), pp. 150-164. (Intervento presentato al convegno 16th International Symposium, SSS 2014 tenutosi a Paderborn; Gemanry) [10.1007/978-3-319-11764-5_11].

Robots with Lights: Overcoming Obstructed Visibility Without Colliding

Giuseppe Antonio Di Luna
;
2014

Abstract

Robots with lights is a model of autonomous mobile computational entties operating in the plane in Look-Compute-Move cycles: each agent has an externally visible light which can assume colors from a fixed set; the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The investigation of computability in this model is under way, and several results have been recently established. In these investigations, however, an agent is assumed to be capable to see through another agent. In this paper we start the study of computing when visibility is obstructable, and investigate the most basic problem for this setting, Complete Visibility: The agents must reach within finite time a configuration where they can all see each other and terminate. We do not make any assumption on a-priori knowledge of the number of agents, on rigidity of movements nor on chirality. The local coordinate system of an agent may change at each activation. Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that Complete Visibility is always solvable, even in the asynchronous setting, without collisions and using a small constant number of colors. The proof is constructive. We also show how to extend our protocol for Complete Visibility so that, with the same number of colors, the agents solve the (non-uniform) Circle Formation problem with obstructed visibility.
2014
16th International Symposium, SSS 2014
robot; complexity; algorithms; lights;
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Robots with Lights: Overcoming Obstructed Visibility Without Colliding / DI LUNA, GIUSEPPE ANTONIO; Flocchini, Paola; Gan Chaudhuri, Sruti; Santoro, Nicola; Viglietta, Giovanni. - 8756:(2014), pp. 150-164. (Intervento presentato al convegno 16th International Symposium, SSS 2014 tenutosi a Paderborn; Gemanry) [10.1007/978-3-319-11764-5_11].
File allegati a questo prodotto
File Dimensione Formato  
DiLuna_Robots-with-Lights_2014.pdf

solo gestori archivio

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

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 383.78 kB
Formato Adobe PDF
383.78 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/763138
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 21
social impact