Minimum-Traveled-Distance Gathering of Oblivious Robots over given Meeting Points

The paper considers a new variant of the gathering problem of oblivious and asynchronous robots moving on the plane. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of robots disposal (Look), decides whether to move toward some direction (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are anonymous and execute the same distributed algorithm that must guarantee to move all robots to meet at some point among a predetermined set. During the Look phase, in fact, robots perceives not only the relative positions of the other robots, but also the relative positions of a set of points referred to as fixed points where gathering must be finalized. We are interested in designing a gathering algorithm that solves the problem by also minimizing the total distances covered by all robots. We characterize when this gathering problem can be optimally solved, and we provide a new distributed algorithm along with its correctness.