Getting close without touching: near-gathering for autonomous mobile robots

We present the first (deterministic) algorithm for the Near-Gathering problem, to the best of our knowledge, which allows a set of autonomous mobile robots to nearly gather within finite time without ever colliding. Our algorithm assumes some reasonable conditions on the input configuration (the Near-Gathering problem is easily seen to be unsolvable in general). Further, all the robots are assumed to have a com- pass (hence they agree on the “North” direction), but they do not necessarily have the same handedness (hence they may disagree on the clockwise direction). We also show how the robots can detect termination, i.e., detect when the Near- Gathering problem has been solved. This is crucial when the robots have to perform a generic task after having nearly gathered. We show that termination detection can be obtained even if the total number of robots is unknown to the robots themselves (i.e., it is not a parameter of the algorithm), and robots have no way to explicitly communicate.