Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights

We study the Uniform Circle Formation (UCF) problem, which asks a swarm of mobile agents, arbitrarily positioned onto the plane, to arrange on the vertices of a regular polygon. Each agent, customarily called robot, runs a distributed algorithm by executing a sequence of look-compute-move cycles. The robot swarm may adhere to three synchronization modes: fully synchronous, semi-synchronous, and asynchronous. Our robots are assumed to be punctiform, anonymous, and indistinguishable by their appearance; they do not store past actions or system snapshots, and they have neither a coordinate system nor chirality in common. Moreover, we consider opaque robots, i.e. they may have obstructed visibility due to collinearities. To cope with these strong limitations, we consider luminous robots, that is, they are equipped with a persistent light assuming different colors. This latter peculiarity represents the only way robots have to communicate. For all three synchronization modes, we solve the UCF problem with a constant number of colors. Concerning the running time, our solutions use a constant number of cycles (epochs) for fully synchronous (semi-synchronous) robots, and linearly many epochs in the worst-case for asynchronous robots.