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.
@cite_4 introduced the CORDA or Asynchronous (ASYNC) scheduling model for weak robots. @cite_0 have introduced the ATOM or Semi-synchronous (SSYNC) model. In @cite_7 , impossibility of gathering for @math without assumptions on local coordinate system agreement for and is proved. Also, for @math it is impossible to solve gathering without assumptions on either coordinate system agreement or multiplicity detection @cite_5 . Cohen and Peleg @cite_1 have proposed a center of gravity algorithm for convergence of two robots in ASYNC and any number of robots in SSYNC.
@cite_4 @cite_7 @cite_1 @cite_0 @cite_5
1961973183 2044484214 1483270512 2119517221
In this paper we aim at an understanding of the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We study a hard task for a set of weak robots. The task is for the robots in the plane to form any arbitrary pattern that is given in advance. The robots are weak in several aspects. They are anonymous; they cannot explicitly communicate with each other, but only observe the positions of the others; they cannot remember the past; they operate in a very strong form of asynchronicity. We show that the tasks that such a system of robots can perform depend strongly on their common knowledge about their environment, i.e., the readings of their environment sensors. 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. Consider a group of N robots aiming to converge towards a single point. The robots cannot communicate, and their only input is obtained by visual sensors. A natural algorithm for the problem is based on requiring each robot to move towards the robots’ center of gravity. The paper proves the correctness of the center-of-gravity algorithm in the semi-synchronous model for any number of robots, and its correctness in the fully asynchronous model for two robots. Given a set of n autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position on the plane not fixed in advance (Gathering Problem). The main research question we address in this paper is: Under which conditions can this task be accomplished by the robots? The studied robots are quite simple: they are anonymous, totally asynchronous, they do not have any memory of past computations, they cannot explicitly communicate between each other. We show that this simple task cannot be in general accomplished by the considered system of robots.