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

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