There has been a wide interest in designing distributed algorithms for tiny robots. In particular, it has been shown that the robots can complete certain tasks even in the presence of faulty robots. In this paper, we focus on gathering of all non-faulty robots at a single point in presence of faulty robots. We propose a wait-free algorithm (i.e., no robot waits for other robot and algorithm instructs each robot to move in every step, unless it is already at the gathering location), that gathers all non-faulty robots in semi-synchronous model without any agreement in the coordinate system and with weak multiplicity detection (i.e., a robot can only detect that either there is one or more robot at a location) in the presence of at most @math faulty robots for @math . We show that the required capability for gathering robots is minimal in the above model, since relaxing it further makes gathering impossible to solve. Also, we introduce an intermediate scheduling model between the asynchronous ( i.e., no instantaneous movement or computation) and the semi-synchronous (i.e., both instantaneous movement and computation) as the asynchronous model with instantaneous computation. Then we propose another algorithm in model for gathering all non-faulty robots with weak multiplicity detection without any agreement on the coordinate system in the presence of at most @math faulty robots for @math .
Some of the common problems for these multi-robot systems include, : all robots agree on a leader among themselves @cite_12 @cite_3 @cite_15 , : all robots gather at a single point @cite_16 , : the robots come very close to each other @cite_6 and : the robots imitate a given pattern on the plane @cite_16 . The gathering problem has been studied for different models, including fully synchronous (), semi-synchronous () and asynchronous (). In model, the gathering problem has been solved without making any additional assumptions to the basic model @cite_5 . In @cite_16 , 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_14 . In @cite_8 , have studied gathering with multiplicity detection. A practical implementation of non-transparent fat robots with omnidirectional cameras opened up several new algorithmic issues @cite_11 . @cite_12 have proposed a deterministic algorithm for leader election and gathering for transparent fat robots without common sense of direction or chirality. Common chirality is basically the common clockwise order.
@cite_14 @cite_8 @cite_3 @cite_6 @cite_5 @cite_15 @cite_16 @cite_12 @cite_11
2963730940 1569673105 1780011259 2049232787
Consider a set of n finite set of simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular n-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant. This paper considers a system of asynchronous autonomous mobile robots that can move freely in a two-dimensional plane with no agreement on a common coordinate system. Starting from any initial configuration, the robots are required to eventually gather at a single point, not fixed in advance (gathering problem). Prior work has shown that gathering oblivious (i.e., stateless) robots cannot be achieved deterministically without additional assumptions. In particular, if robots can detect multiplicity (i.e., count robots that share the same location) gathering is possible for three or more robots. Similarly, gathering of any number of robots is possible if they share a common direction, as given by compasses, with no errors. Our work is motivated by the pragmatic standpoint that (1) compasses are error-prone devices in reality, and (2) multiplicity detection, while being easy to achieve, allows for gathering in situations with more than two robots. Consequently, this paper focusses on gathering two asynchronous mobile robots equipped with inaccurate compasses. In particular, we provide a self-stabilizing algorithm to gather, in a finite time, two oblivious robots equipped with compasses that can differ by as much as π 4. This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems. Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation @math that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the @math -axis of a compass and the reference direction of the global coordinate system: @math for semi-synchronous and asynchronous robots with static compasses, @math for semi-synchronous robots with dynamic compasses, and @math for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.