We consider a set of oblivious robots moving in the plane that have to gather at one point among a predetermined set of so called meeting points. Robots operate in asynchronous Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of relative positions of robots and meeting points (Look), decides whether to move toward some direction (Compute), then makes the computed move, eventually (Move). Robots are anonymous and execute the same distributed algorithm that must guarantee to gather all robots at a meeting point by minimizing the longest distance traveled by a single robot. This is a new metric for evaluating the quality of the gathering, and we start characterizing configurations where optimal gathering can be achieved. We then provide a distributed algorithm to optimally solve such configurations.

MinMax-Distance Gathering on given Meeting Points

CICERONE, SERAFINO;DI STEFANO, GABRIELE;
2015-01-01

Abstract

We consider a set of oblivious robots moving in the plane that have to gather at one point among a predetermined set of so called meeting points. Robots operate in asynchronous Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of relative positions of robots and meeting points (Look), decides whether to move toward some direction (Compute), then makes the computed move, eventually (Move). Robots are anonymous and execute the same distributed algorithm that must guarantee to gather all robots at a meeting point by minimizing the longest distance traveled by a single robot. This is a new metric for evaluating the quality of the gathering, and we start characterizing configurations where optimal gathering can be achieved. We then provide a distributed algorithm to optimally solve such configurations.
2015
978-3-319-18172-1
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/37312
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 9
social impact