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)
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.

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