Self-stabilizing algorithm for circle formation by disoriented oblivious mobile robots

Abstract

This paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle. The difficulty of the problem results from the fact that robots are anonymous, oblivious, unable to communicate directly, and also disoriented, i.e, share no knowledge of a common coordinate system. More precisely, the proposed algorithm ensures that the robots deterministically form a circle in a finite number ofsteps and converges to a situation in which all robots are located evenly on the boundary of the circle. In addition, thanks to the nature of the assumed model (i.e., oblivious robots), the algorithm is also self-stabilizing.