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) |
Abstract: |
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.
|
Remarks: |