The optimal tolerance of uniform observation error for mobile robot convergence

We consider a convergence problem of autonomous mobile robots with inaccurate sensors which may return erroneous locations of other robots. In this paper, we newly introduce a uniform error model, which is a restricted variant of the original observation-error model proposed by Cohen and Peleg (2008) [1], . In Cohen and Peleg (2008) [1], they studied the convergence problem in the atomic-movement model(ATOM) where an observation of robots includes an observation error. The degree of an observation error is characterized by distance errors and angle errors. While the original model (non-uniform model) allows that two or more points can have different error degrees, the uniform error model assumes that the same amount of error degree is incurred to all observed points in a single observation. The main focus of our study is to reveal how much such uniformity expands the feasibility of the convergence. In the non-uniform error model, it has been shown that no algorithm can achieve convergence if the maximum error angle is more than or equal to π/3. This paper shows that in the ATOM model, the convergence problem is solvable under the uniform error model if the maximum error angle and distance are less than π/2 and one respectively. We also prove that the angle bound is tight in the sense that there is no convergence algorithm for the maximum error angle more than or equal to π/2 in the uniform error model.