Optimal and competitive runtime bounds for continuous, local gathering of mobile robots

Abstract

We consider a scenario in which n mobile robots with a limited viewing range are distributed arbitrarily in the plane, such that the visibility graph of the robots is connected. The goal is to gather the robots in one (not predefined) point. Each robot may base its decision where to move only on the current relative positions of the robots which are in its viewing range. That is, besides having a limited viewing range, the robots are oblivious (they do not use information from the past), they do not have IDs, and they do not have a common sense of direction. On the other hand side, we assume that they are points, i.e., have no extent.