# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 1 Introduction  
The classical model of distributed computing by mobile robots models each robot as a point in the plane that is equipped with a local coordinate system and sensory capabilities to determine the positions of other robots [1]. The local coordinate system of a robot may not be consistent with that of other robots. The sensory capability of a robot, generally called _vision_, allows a robot to determine the positions of other robots in its own coordinate system. The robots are _autonomous_ (no external control), _anonymous_ (no unique identifiers), _indistinguishable_ (no external identifiers), and _disoriented_ (no agreement on local coordinate systems or units of distance measures). They execute the same algorithm. Typically, robots have _unobstructed_ visibility, that is, robots are transparent such that three collinear robots can see each other. Each robot proceeds in _Look-Compute-Move_ (LCM) cycles: When a robot becomes active, it first gets a snapshot of its surroundings (_Look_), then computes a destination based on the snapshot (_Compute_), and finally moves towards the destination (_Move_). Moreover, the robots are _oblivious_, i.e., in each cycle, each robot has no memory of its past LCM cycles [1]. Furthermore, the robots are _silent_ because they do not communicate directly, and only vision and mobility enable them to coordinate their actions. While silence has advantages, many other situations, e.g., hostile environments, assume direct communication. The _robots with lights_ model [1; 2; 3] incorporates direct communication, where each robot has an externally visible light that can assume colors from a constant-sized set; robots explicitly communicate with each other using these colors. The colors are _persistent_, i.e., the color is not erased at the end of a cycle. Except for the lights, the robots are oblivious as in the classical model. In addition, robots have _obstructed visibility_ such that robot \(b\) in line between robots \(a\) and \(c\) blocks the views of \(a\) from \(c\) and vice versa. The following fundamental problem, Complete Visibility on the robots with lights model is the main focus of this paper. Given an arbitrary initial configuration of \(N\) robots located at distinct points on a real plane, they autonomously arrange themselves in a configuration in which each robot is in a distinct position and from which it can see all other robots. In the initial configuration, some robots may be obstructed from the view of others and the robots themselves do not know the total number of robots, \(N\). Solving Complete Visibility enables solutions to many other robot problems under obstructed visibility, including gathering, pattern formation, and leader election. For example, we recently solved the problem of pattern formation in Reference [4], which uses the solution to Complete Visibility presented in this paper in the first step of its four-step algorithm. Indeed, after the robots reach a configuration of complete visibility, they know the value of \(N\) and each robot can see all the robots in the system as in robots model with unobstructed visibility, i.e., any solution to Complete Visibility recovers unobstructed visibility configuration starting from an obstructed visibility configuration. [PERSON] et al. [5] gave the first algorithm for robots with lights to solve Complete Visibility on a real plane. They arranged robots on the corners of a \(N\)-corner convex hull, which immediately solves Complete Visibility since each robot positioned on a corner of a convex hull sees all other \(N-1\) robots positioned on \(N-1\) other corners. In the real-world setting, the convex hull based Complete Visibility solution might also help to make a barrier around the site of interest so that the intruders entering the site from one point may be monitored and reported to all the points of interests (provided by robots). [PERSON] et al. [5] focused mostly on correctness proving that the problem can be solved in finite time.