A Tight Runtime Bound for Synchronous Gathering of Autonomous Robots with Limited Visibility

摘要

The problem of gathering n autonomous robots in the Euclidean plane at one (not predefined) point is well-studied under various restrictions on the capabilities of the robots and in several time models. However, only very few runtime bounds are known. We consider the scenario of local algorithms in which the robots can only observe their environment within a fixed viewing range and have to base their decision where to move in the next step solely on the relative positions of the robots within their viewing range. Such local algorithms have to guarantee that the (initially connected) unit disk graph defined by the viewing range of the robots stays connected at all times. In this paper, we focus on the synchronous setting in which all robots are activated concurrently. Ando et al. [2] presented an algorithm where a robot essentially moves to the center of the smallest enclosing circle of the robots in its viewing range and showed that this strategy performs gathering of the robots in finite time. However, no bounds on the number of rounds needed by the algorithm are known. We present a lower bound of Ω(n2) for the number of rounds as well as a matching upper bound of O(n2) and thereby obtain a tight runtime analysis of the algorithm of Θ(n2).