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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.