# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 2 Model and Preliminaries  
Robots  
Let \(\mathcal{Q}=\{r_{0},r_{1},\cdots,r_{N-1}\}\) be a set of \(N\) robots (agents) in a distributed system. Each robot is represented as a (dimensionless) point that moves in \(\mathbb{R}^{2}\), the infinite 2-dimensional real plane. In this paper, a point will denote a robot, as well as its position. A robot \(r_{i}\) can see, and be visible to, another robot \(r_{j}\) iff there is no third robot \(r_{k}\) in the line segment joining \(r_{i}\) and \(r_{j}\). Each robot has a light that can assume one color at a time; this color comes from a set with a constant number of colors. Look-Compute-Move  
At any given time, a robot \(r_{i}\) can be active or inactive. When robot \(r_{i}\) becomes active, it performs the \"Look-Compute-Move\" (LCM) cycle described below. * _Look:_ For each robot \(r_{j}\) that is visible to \(r_{i}\), robot \(r_{i}\) observes the position of \(r_{j}\) and the color of its light. It is assumed that \(r_{i}\) is visible to itself. Each robot observes position of other robots accurately, but within its own local frame of reference. That is, two different robots observing the position of the same point may produce different coordinates. * _Compute:_ After observing the position and light color of visible robots, robot \(r_{i}\) may perform an arbitrary computation using only the positions and colors observed during the \"look\" portion of the current LCM cycle. This computation includes determination of a (possibly) new position to move to and light color for robot \(r_{i}\) for the start of next cycle. * _Move:_ At the end of the LCM cycle, robot \(r_{i}\) changes its light to the new color (determined during the compute phase) and moves to its new position. Robot \(r_{i}\) maintains this new light color from the current LCM cycle until it is possibly changed in the move phase of the next LCM cycle. Robot Activation and Synchronization  
In the fully synchronous setting (\(\mathcal{FSYNC}\)), every robot is active in every LCM cycle. In the semi-synchronous setting (\(\mathcal{SSYNC}\)), at least one robot is active, and over an infinite number of LCM cycles, every robot is active infinitely often. In the asynchronous setting (\(\mathcal{ASYNC}\)), robots have no common notion of time. No limit exists on the number and frequency of LCM cycles in which a robot can be active except that every robot is active infinitely often. Complying with the \(\mathcal{ASYNC}\) setting, we assume that a robot \"wakes up\" and performs its _Look_ phase at an instant of time. An arbitrary amount of time may elapse between the Look and Compute phases and between the Compute and Move phases. We also assume that during the _Move_ phase it moves in a straight line at some (not necessarily constant) speed, but without stopping or changing direction. We will call such robot moves _monotonic_ movements. Runtime  
For the \(\mathcal{FSYNC}\) setting, time is measured in rounds. Since a robot in the \(\mathcal{SSYNC}\) and \(\mathcal{ASYNC}\) settings could stay inactive for an indeterminate number of rounds, we introduce the idea of an epoch to measure runtime. An _epoch_ is the smallest number of rounds within which each robot is active at least once [38]. Let \(t_{0}\) denote the start time of the algorithm. Epoch \(i\) (\(i\geq 1\)) is the time interval from \(t_{i-1}\) to \(t_{i}\) where \(t_{i}\) is the first time instance after \(t_{i-1}\) when each robot has completed at least one complete LCM cycle. Therefore, for the \(\mathcal{FSYNC}\) setting, a round is an epoch. We will use the term \"time\" generically to mean rounds for the \(\mathcal{FSYNC}\) setting and epochs for the \(\mathcal{SSYNC}\) and \(\mathcal{ASYNC}\) settings. For \(N\geq 3\), represent a _convex polygon_ as a sequence \(\mathbf{P}=(c_{0},c_{1},\cdots,c_{N-1})\) of _corner points_ in a plane that enumerates the polygon vertices in clockwise order. Figure 1 shows a 5-corner convex polygon \((c_{0},c_{1},c_{2},c_{3},c_{4})\).