Tight bound on the gathering of two oblivious mobile robots with inconsistent compasses
Masafumi Yamashita, Samia Souissi, Xavier Défago · Institutional Repositories DataBase (IRDB) · 2007
We consider a system of autonomous mobile robots that can move in the two dimensional space. These robots must gather, in finite time, at a single point in the plane, not predetermined (gathering problem). We consider that the robots are equipped with compasses, although these compasses can be inconsistent. In our previous work, we proposed an algorithm that gathers two oblivious mobile robots in finite time when the compasses diverge by at most 45°. In this paper, we extend this work by proving a tight bound on the degree of divergence of robots' compasses for solving the gathering problem. More specifically, we present a self-stabilizing algorithm to gather, in a finite time, two oblivious robots equipped with compasses that can differ by an angle strictly smaller than 180°, and we show that it is a tight bound.