Gathering Autonomous Mobile Robots in Non Totally Symmetric Configurations
Authors: Mark Cieliebak and Giuseppe Prencipe
Reference: Technical Report 379, ETH Zurich, Department of Computer Science, October 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 that are occupied by other robots. Based on this observation, a robot uses a deterministic algorithm to compute a destination, and moves there. The problem is unsolvable if the robots have no additional abilities. Therefore, we introduce the ability to detect how many robots are at a specific point in the plane (multiplicity detection). For two robots, the problem remains unsolvable. 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 if they are not in a specific symmetric configuration at the beginning (totally symmetric 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.