The design of distributed gathering and convergence algorithms for tiny robots has recently received much attention. In particular, it has been shown that convergence problems can even be solved for very weak, robots: robots which cannot maintain state from one round to the next. The oblivious robot model is hence attractive from a self-stabilization perspective, where state is subject to adversarial manipulation. However, to the best of our knowledge, all existing robot convergence protocols rely on the assumption that robots, despite being "weak", can measure distances. We in this paper initiate the study of convergence protocols for even simpler robots, called : robots which cannot measure distances. In particular, we introduce two natural models which relax the assumptions on the robots' cognitive capabilities: (1) a Locality Detection ( @math ) model in which a robot can only detect whether another robot is closer than a given constant distance or not, (2) an Orthogonal Line Agreement ( @math ) model in which robots only agree on a pair of orthogonal lines (say North-South and West-East, but without knowing which is which). The problem turns out to be non-trivial, and simple median and angle bisection strategies can easily increase the distances among robots (e.g., the area of the enclosing convex hull) over time. Our main contribution are deterministic self-stabilizing convergence algorithms for these two models, together with a complexity analysis. We also show that in some sense, the assumptions made in our models are minimal: by relaxing the assumptions on the further, we run into impossibility results.
The problems of gathering @cite_7 , where all the robots gather at a single point, convergence @cite_2 , where robots come very close to each other and Pattern formation @cite_8 @cite_7 have been studied intensively in the literature.
@cite_8 @cite_7 @cite_2
2135835260 2044484214 2563454818
The distributed coordination and control of a set of autonomous mobile robots is a problem widely studied in a variety of fields, such as engineering, artificial intelligence, artificial life, robotics. Generally, in these areas the problem is studied mostly from an empirical point of view. In contrast, we aim to understand the fundamental limitations on what a set of autonomous mobile robots can achieve. We describe the current investigations on what autonomous mobile robots can and can not do with respect to some coordination problems. In this note we make a minor correction to a scheme for robots to broadcast their private information. All major results of the paper [I. Suzuki and M. Yamashita, SIAM J. Comput., 28 (1999), pp. 1347-1363] hold with this correction. The common theoretical model adopted in recent studies on algorithms for systems of autonomous mobile robots assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions, and replacing it with the more realistic assumption that the robot sensors, movement and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements and calculations to carry out the task of convergence. The paper presents several impossibility results, limiting the inaccuracy allowing convergence. The main positive result is an algorithm for convergence under bounded measurement, movement and calculation errors.