Tight Analysis of a Collisionless Robot Gathering Algorithm

摘要

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane that have a physical extent and hence cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem with minimum time objective has applications in many real-world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011) gave a local greedy algorithm in a fully synchronous setting and proved that, for the discrete version of the problem where robots’ movements are restricted to the positions on an integral grid, their algorithm solves this problem in O ( nR ) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this article, we improve significantly the round complexity of their algorithm to R + 2 · ( n - 1) rounds. This round complexity is obtained in the following modified model: (1) the viewing range of the robots is increased to three hops and (2) robots can additionally move to the diagonally opposite corner to a grid cell in one step—that is, they can traverse the two corresponding grid edges in one time step. We also prove that there are initial configurations of n robots in this problem where at least R +(n-1)/2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + ( n - 1) rounds for the algorithm of Cord-Landwehr et al. These results altogether provide a tight runtime analysis of their algorithm.