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