# Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights
## 1 Introduction  
The last decade has seen a major increase in the development and dissemination of distributed environments for mobile entities, e.g., sensor networks, multi-robot systems, and drone swarms, having a great impact in several different contexts. Along with the application studies in the robotics and electronics fields [1, 2, 3, 4, 5], computer science research has attempted to design theoretical models [6, 7, 8, 9, 10] which best formalize and simulate generic distributed systems, and to study efficient algorithms for some primitive tasks. Such an analytical investigation aims at providing a rigorous and universal methodology to study the collaborative strategies for mobile multi-agent systems [11, 12, 10, 13], model peculiar real-world scenarios [14, 15, 16], prove and analyze the correctness of algorithmic solutions [17, 18], and investigate their computational complexity [19, 20, 21, 22, 23]. Several theoretical models have been introduced for these purposes: agents, also called _robots_, act under several assumptions about their capabilities and about a particular scenario. Models of great importance are the ones where robots are autonomous, i.e., they work without central control, and operate through a sequence of _look-compute-move_ cycles in which each robot _(i)_ takes the snapshot of the system _(look)_, _(ii)_ executes a deterministic algorithm (_compute_), and _(iii)_ travels to the computed destination (_move_) [9, 22, 23, 24]. Different model assumptions are considered, affecting the computational power of robots [19; 21; 22; 23]. Generally, robots are assumed to be point-like, anonymous (without any distinct identifiers yielding the ability to distinguish one robot from another), and oblivious (without any persistent memory). In order to consider more powerful and realistic models, the _luminous_ robot [11; 20; 22; 25; 26; 27] has been introduced: robots equipped with a persistent light assuming different colors. Since such a light color is preserved from one look-compute-move cycle to the next one, it can be used as a persistent constant memory and a means of communication as well. Another step towards realistic models is to work, not with point-like (punctiform model) robots, but _fat robots_[13; 28; 29], where all robots are supposed to be solid discs with a certain radius. Moreover, robots can be _transparent_[13; 19; 30], enabling complete visibility of the system, or _opaque_[11; 26; 31]. Depending on the nature of the problem, robots can move either on the Euclidean plane, or on a graph [22; 23] which can either be known in advance or not. Concerning robot activation policy, three modes are proposed in the literature: _fully synchronous_ (fsynch), where all robots execute their cycle synchronously, _semi-synchronous_ (ssynch), where robots in a subset execute their cycle synchronously whereas the others remain idle, and _asynchronous_ (asynch), where each robot acts asynchronously. Several research efforts focus on very basic classes of geometric pattern formation problems to be solved within such distributed environments [10; 11; 32; 33]. In the Gathering problem, robots are required to meet in a certain location. Solutions to this problem are provided in [34] for asynch robots with limited visibility, in [29] for a few fat asynch robots, and in [28] for fat fsynch robots with limited visibility. In [14; 15], Gathering is tackled for robots that move on a ring, coping with two fault models: with a mobile malicious agent [15] and with a stationary faulty node (_black hole_) [14]. The Circle Formation problem requires robots to displace upon a common circle. In [13], this problem is solved for asynchronous fat transparent robots moving freely on the plane, while in [31] asynchronous opaque robots moving on an infinite grid are considered.