Eventually consistent compasses for robust gathering of asynchronous mobile robots with limited visibility

摘要

Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize to eventually meet at some arbitrary location. That problem has the advantage that, while being very simple to express, it retains the inherent difficulty of agreement, namely the problem of breaking symmetry. In their fully asynchronous model with oblivious robots and limited visibility, Flocchini et al. [7] show that gathering is solvable, as long as the robots share the knowledge of some direction, as provided by a compass. It turns out that, in robotic systems, compasses are devices that are often subject to instabilities. In this paper, we thus define a model with unreliable compasses and, focusing on the gathering problem, show that the algorithm of Flocchini et al. is unable to tolerate unstable compasses. We then give a gathering algorithm that solves the problem in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually.