Gathering of robots on meeting-points: feasibility and optimal resolution algorithms

The paper considers variants of the gathering problem of oblivious and asynchronous robots moving in the plane. When robots are free to gather anywhere in the plane, the problem has been solved in Cieliebak et al. (SIAM J Comput 41(4):829-879, 2012). We propose a new natural and challenging model that requires robots to gather only at some predetermined points in the plane, referred to as meeting-points. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of robots' positions and meeting-points (Look) according to its own coordinate system, 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 and deterministic algorithm. In the new proposed model, we fully characterize when gathering can be accomplished. We design an algorithm that solves the problem for all configurations with robots but those identified as ungatherable. After that, we consider the classical notion of optimization algorithms and extend it to the context of robot-based computing systems. With this new notion, we re-consider the gathering on meeting-points problem but with respect to two objective functions. In particular, we first solve the gathering by minimizing the overall traveled distance performed by all robots and then we address the minimization of the maximum traveled distance performed by a single robot. For the former objective function, we fully characterize when optimal gathering can be achieved by providing a distributed algorithm along with the proof of correctness. For the latter objective function, we design another gathering algorithm that ensures optimal gathering almost for all the cases where it is possible, and discuss some insights on the remaining cases.