Distinct Gathering Under Round Robin

Zusammenfassung

We resolve one of the longest-standing questions about autonomous mobile robots in a surprising way. Distinct Gathering is the fundamental cooperation task of letting robots, initially scattered across the plane in distinct locations, gather in an arbitrary single point. The scheduler \emph{Round Robin} cyclically activates the robots one by one in a fixed order. When activated, a robot perceives all robot locations and moves wherever it wants based only on this information. For n = 2 robots, the task is trivial. What happens for n >= 3 has remained an open problem for decades by now. The established conjecture declares the the task to be impossible in this case. We prove that it is indeed impossible for n = 3 but, to great surprise, ossible again for any n >= 4. We go beyond the the standard requirements by providing a very robust algorithm that does not require any consistency or self-consistency for the local Cartesian maps perceived by the robots and works even for non-rigid movement, that is, if robots may be unpredictably stopped and deactivated during a movement.