# Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights
## 1 Introduction
In the Uniform Circle Formation (UCF) problem [26; 30; 35; 36; 37], robots are required to move to the vertices of a common regular polygon whose number of vertices--which can or cannot be known in advance--is exactly the number of robots in the system. This problem has received a lot of attention (see, e.g., [36] for a survey) for both theoretical and practical reasons. From a practical point of view, a regular layout may present several advantages for a distributed system. E.g., in a network of mobile agents, it may be convenient to regularly displace them to facilitate communications, visibility and computations. Every agent is equidistant from its neighbors and has the same view of the system: this guarantees a fair communication, where there are no evident differences in the energy spent in sending messages. Moreover, this uniform pattern allows to implement distributed algorithms which guarantee a fair load balancing among agents. So far, swarms of transparent robots have been mainly considered in the UCF investigation. However, such a _full visibility_ feature might not turn out to be realistic. Accordingly, _obstructed visibility_ can represent a constraint making the model more interesting and realistic, although more difficult to manage. In such an _opaque model_, if three robots are collinear, the middle robot obstructs the vision of the other two. So, whenever collinearities occur, some robots may have a wrong perception of the actual global number of agents in the system and, more generally, of the configuration of the whole system itself. In this realm, the first natural problem to be tackled is Complete Visibility, where robots are required to displace on the plane so that each robot is visible to all others. Since robot opaqueness turns out to be a critical issue, some additional capabilities for robots might be considered. In particular, solutions in the literature are proposed for luminous robots. Such a well-studied functionality turns out to be a natural minimal enhancement to solve several tasks (see, e.g., [19; 20; 21; 22; 23; 25]). In [38], a \(\mathcal{O}(\log N)\) time algorithm is given, solving Complete Visibility by using \(\mathcal{O}(1)\) colors in the asynch mode. Moreover, the problem is solved with a constant amount of time and colors both for the ssynch mode [39] and for the asynch one [40]. In [16], a fault-tolerant algorithm for Complete Visibility is exhibited. Overall, a strategy for reaching a configuration where every robot can see the entire swarm can be used as a sub-routine in all those problems where robots need to count themselves (as in UCF, [26]). Related Works and Main ContributionsThis paper investigates the UCF problem for a swarm of opaque and luminous robots. Such a problem has been investigated and solved under different combinations of system assumptions in order to point out the minimal sets of features for its solution. In [35; 37], the problem is solved for fat robots, but (partially) oriented. Specifically, the authors of [37] cope with transparent and fat robots, which agree on one axis of their coordinate systems, operating in the ssynch mode. The algorithm in [35] solves the UCF problem for a swarm of fat, opaque, but oriented (they share a common coordinate system) robots in the asynch mode. In [30], the authors provide a solution for transparent, disoriented, and non-rigid robots, in the asynch mode. The work in [26] exhibits an algorithm solving the UCF problem for swarms of opaque luminous robots only in the fsynch mode, featuring six cycles and a constant number of colors. In all the above-cited works, robots solve the problem without colliding. The current paper considers robots sharing the same features as [26], and aims to improve and complete its algorithmic investigation. Specifically, all three synchronization modes are examined here; as a matter of fact, this paper provides three algorithmic solutions to solve the UCF problem by opaque luminous robots in the fsynch, ssynch, and asynch modes.