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 $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

Consider a system composed of mobile robots (mobile sensors) that move on the plane, each of which independently executing its own instance of an algorithm. Given a desired geometric pattern, the flocking problem consists in ensuring that the robots form this pattern and maintain it while moving together on the plane. In this paper, we look at the flocking problem in the presence of faulty robots, where the desired pattern is a regular polygon. We propose a distributed algorithm assuming a semi-synchronous model with a k-bounded scheduler, in the sense that no robot is activated more than k times between any two consecutive activations of any other robot. The algorithm is composed of three parts: failure detector, ranking assignment and flocking algorithm. The rank assignment part is to provide a persistent ranking for the robots in the system. Then, the failure detector can select the set of correct robots from all the robots. Finally, the flocking algorithm handles the movement and reconfiguration of the flock, while maintaining the desired shape. The difficulty of the problem comes from the combination of the three parts together with the necessity to prevent collision and allow the rotation of the flock. Different from the existed work, our algorithm can make the formation rotate freely and has good maneuverability.

Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity. In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.