Solving the Robots Gathering Problem
Authors: Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro
Reference: In "Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)", Eindhoven, Netherlands, June 2003. Springer, LNCS 2719, pp. 1181-1196, 2003
Download: Postscript (.ps) or PDF (.pdf)
Consider a set of n > 2 simple autonomous mobile robots (decentralized, asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of gathering them at a point not fixed in advance (Gathering Problem). In the literature, most contributions are simulation-validated heuristics. The existing algorithmic contributions for such robots are limited to solutions for $n < 5$ or for restricted sets of initial configurations of the robots. In this paper, we present the first algorithm that solves the Gathering Problem for any initial configuration of the robots.

Note: electronic versions may not always correspond exactly to printed versions.