Gathering Non-Oblivious Mobile Robots | |
Authors: | Mark Cieliebak |
Reference: | In "Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004)". Buenos Aires, Argentina, May 2004. Springer, LNCS 2976, pp. 577-588, 2004. |
Download: | Postscript (.ps) or PDF (.pdf) |
Abstract: |
We study the Gathering Problem, where we want to gather
a set of n autonomous mobile robots at a point in the plane.
This point is not fixed in advance. The robots are very weak, in the sense
that they have no common coordinate system, no identities, no central
coordination, no means of direct communication, and no synchronization.
Each robot can only sense the positions of the other robots, perform a
deterministic algorithm, and then move towards a destination point. It
is known that these simple robots cannot gather if they have no additional
capabilities. In this paper, we show that the Gathering Problem can be
solved if the robots are non-oblivious, i.e., if they are equipped with
memory.
|
Remarks: |