Gathering a swarm of Robots is one of the basic tasks in distributed computing. Varying of the Robots’ capabilities as well as on the environments where Robots move lead to very different approaches. In general, the problem requires the design of a distributed algorithm that brings all Robots to meet at some common location, not known in advance. We consider asynchronous Robots subject to the well-established Look-Compute-Move model. Each time a robot wakes up, it perceives the current configuration in terms of Robots’ positions (Look), it decides whether and where to move (Compute), and makes the computed move (Move), if any. Starting from the case of Robots moving in the Euclidean plane, we highlight pros and cons for Robots moving along the edges of a graph. We survey on the most recent results about Robots moving in general graphs and in specific topologies like trees, rings, grids, and cliques. Further, we show how the design of an algorithm for general graphs naturally leads to optimization issues. In particular, we survey on optimal gathering algorithms in terms of total number of edges traversed by Robots in order to accomplish the gathering task. Also in this case, results concern general graphs and specific topologies. In doing so, we highlight how the problem and the resolution algorithms change when optimal constraints are included.

Asynchronous Robots on graphs: Gathering

Cicerone, Serafino;Di Stefano, Gabriele;Navarra, Alfredo
2019-01-01

Abstract

Gathering a swarm of Robots is one of the basic tasks in distributed computing. Varying of the Robots’ capabilities as well as on the environments where Robots move lead to very different approaches. In general, the problem requires the design of a distributed algorithm that brings all Robots to meet at some common location, not known in advance. We consider asynchronous Robots subject to the well-established Look-Compute-Move model. Each time a robot wakes up, it perceives the current configuration in terms of Robots’ positions (Look), it decides whether and where to move (Compute), and makes the computed move (Move), if any. Starting from the case of Robots moving in the Euclidean plane, we highlight pros and cons for Robots moving along the edges of a graph. We survey on the most recent results about Robots moving in general graphs and in specific topologies like trees, rings, grids, and cliques. Further, we show how the design of an algorithm for general graphs naturally leads to optimization issues. In particular, we survey on optimal gathering algorithms in terms of total number of edges traversed by Robots in order to accomplish the gathering task. Also in this case, results concern general graphs and specific topologies. In doing so, we highlight how the problem and the resolution algorithms change when optimal constraints are included.
2019
978-3-030-11071-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/132089
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? ND
social impact