Gathering Oblivious Robots in the Plane

Zusammenfassung

The question what kind of tasks autonomous mobile robots can accomplish has been investigated for multiple decades by now. The robots are mobile because they can move in some metric space, by default the Euclidean plane. They are autonomous due to the lack of a central entity controlling all movements. Instead, the well-established model of Look-Compute-Move (LCM) cycles lets each robot, independently and repeatedly, first observe the surrounding robots, then use a shared algorithm to compute a target location, and then move there. The robots are by default assumed to be oblivious, which means that they lose all their memory whenever they finish an LCM cycle. The arguably most fundamental task for a group of mobile robots is to gather in a single point. Whether autonomous mobile robots, arbitrarily scattered in the plane, are able to achieve a gathering depends on the details of the model. In this survey, we introduce the standard LCM model for oblivious robots in the Euclidean plane and discuss important modeling details and variants. We then present known results about gathering for various variants of this model using proof sketches, briefly discussing them and extending their scope in some cases, and finally highlight some remaining open questions.