In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Robots are punctiform and memoryless, they operate in Rm, they have local reference systems independent of each other, and are activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3 m+ 3 k of these weak entities in Rm to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

TuringMobile: a turing machine of oblivious mobile robots with limited visibility and its applications / Di Luna, G. A.; Flocchini, P.; Santoro, N.; Viglietta, G.. - In: DISTRIBUTED COMPUTING. - ISSN 0178-2770. - 35:2(2022), pp. 105-122. [10.1007/s00446-021-00406-6]

TuringMobile: a turing machine of oblivious mobile robots with limited visibility and its applications

Di Luna G. A.
Primo
;
2022

Abstract

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Robots are punctiform and memoryless, they operate in Rm, they have local reference systems independent of each other, and are activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3 m+ 3 k of these weak entities in Rm to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.
2022
Mobile robots, turing machine
01 Pubblicazione su rivista::01a Articolo in rivista
TuringMobile: a turing machine of oblivious mobile robots with limited visibility and its applications / Di Luna, G. A.; Flocchini, P.; Santoro, N.; Viglietta, G.. - In: DISTRIBUTED COMPUTING. - ISSN 0178-2770. - 35:2(2022), pp. 105-122. [10.1007/s00446-021-00406-6]
File allegati a questo prodotto
File Dimensione Formato  
DiLuna_preprint_TuringMobile_2022.pdf.pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 462.98 kB
Formato Adobe PDF
462.98 kB Adobe PDF
DiLuna_TuringMobile_2022.pdf

solo gestori archivio

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