Gathering Autonomous Mobile Robots | |
Authors: | Mark Cieliebak and Giuseppe Prencipe |
Reference: | In "Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002)", Andros, Greece, June 2002. Proceedings in Informatics 13, Carleton Scientific, pp. 57-72, 2002 |
Download: | Postscript (.ps) or PDF (.pdf) |
Abstract: |
We study the problem of coordinating a set of autonomous
mobile robots that can freely move in a two-dimensional plane; in particular,
we want them to gather at a point not fixed in advance (Gathering Problem).
We introduce a model of weak robots (decentralized, asynchronous, no common
knowledge, no identities, no central coordination, no direct communication,
oblivious) which can observe the set of all points in the plane which
are occupied by other robots. Based on this observation, a robot uses
a deterministic algorithm to compute a destination, and moves there. We
prove that these robots are too weak to gather at a point in finite time.
Therefore, we strengthen them with the ability to detect whether more
than one robot is at a point (multiplicity). We analyze the Gathering
Problem for these stronger robots. We show that the problem is still unsolvable
if there are only two robots in the system. For 3 and 4 robots, we give
algorithms that solve the Gathering Problem. For more than 4 robots, we
present an algorithm that gathers the robots in finite time if they are
not in a specific symmetric configuration at the beginning (biangular
configuration). We show how to solve such initial configurations
separately. However, the general solution of the Gathering Problem remains
an open problem.
|
Remarks: |