Robots with Lights: Overcoming Obstructed Visibility Without Colliding  G. A. Di Luna 1 , P. Flocchini 2 , S. Gan Chaudhuri 3 , N. Santoro 4 , and G. Viglietta 2  1   Dipartimento di Ingegneria Informatica, Automatica e Gestionale Antonio Ruberti, Universit` a degli Studi di Roma “La Sapienza”, Rome, Italy,   diluna@dis.uniroma1.it  2   School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa ON, Canada,  flocchin@site.uottawa.ca,   viglietta@gmail.com  3   Department of Information Technology, Jadavpur University, Kolkata, India,   srutiganc@it.jusl.ac.in  4   School of Computer Science, Carleton University, Ottawa ON, Canada,   santoro@scs.carleton.ca  Abstract.   Robots with lights   is a model of autonomous mobile computational entties operating in the plane in Look-Compute-Move cycles: each agent has an externally visible light which can assume colors from a fixed set; the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The investigation of computability in this model, initially suggested by Peleg, is under way, and several results have been recently estab- lished. In these investigations, however, an agent is assumed to be capable to see through another agent. In this paper we start the study of computing when visibility is obstructable, and investigate the most basic problem for this setting,   Complete Visibility : The agents must reach within finite time a configuration where they can all see each other and terminate. We do not make any assumption on a-priori knowledge of the number of agents, on rigidity of movements nor on chirality. The local coordinate system of an agent may change at each activation. Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that C OMPLETE   V ISIBILITY   is always solvable, even in the   asynchronous   setting, without collisions and using a small constant number of colors. The proof is constructive. We also show how to ex- tend our protocol for C OMPLETE   V ISIBILITY   so that, with the same number of colors, the agents solve the (non-uniform) C IRCLE   F ORMATION   problem with obstructed visibility.  1   Introduction  1.1   Framework  In the traditional model of distributed computing by mobile entities in the plane, called  robots   or   agents , each entity is modelled as a point; it is provided with a local coordi- nate system (not necessarily consistent with that of the other agents); it has sensorial capabilities, called   vision , enabling it to determine the position (within its own coordi- nate system) of the other agents. The agents are anonymous, they are indistinguishable, and they execute the same code. Agents operates in   Look-Compute-Move   cycles: when becoming active, an agent uses its sensing capabilities to get a snapshot of its surroundings (Look), then this snap- shot is used to compute a destination point (Compute), and finally it moves towards  arXiv:1405.2430v1 [cs.DC] 10 May 2014
this destination (Move); after that, the agent becomes inactive. In the majority of in- vestigations, the agents are assumed to be oblivious: at the beginning of each cycle, an agent has no recollection of its past observations and computations [11]. Depending on the assumptions on the activation schedule and the duration of the cycles, three main settings are identified. In the   fully-synchronous   setting, all agents are activated simulta- neously, and each cycle is instantaneous. The   semi-synchronous   setting is like the fully synchronous one except that he set of agents to be activated is chosen by an adversary, subject only to a fairness restriction: each agent will be activated infinitely often. In the  asynchronous   setting, there is no common notion of time, and no assumption is made on timing of activation, other than fairness, nor on the duration of each computation and movement, other than it is finite. Vision and mobility provide the agents with   stigmergy , enabling the agents to com- municate and coordinate their actions by moving and sensing their relative positions. The agents are otherwise assumed to be   silent , without any means of explicit direct com- munication [11]. This restriction enables deployment in extremely harsh environments where communication is not possible, i.e an underwater deployment or a military sce- nario where wireless communication are impossible or can be jammed. Nevertheless, in many other situations it is possible to assume the availability of some sort of direct communication. The theoretical interest is obviously for weak communication capabil- ities. A model employing a weak explicit communication mechanism is that of   robots with lights : in this model, each agent is provided with a local externally visible   light , which can can assume colors from a fixed set; the agents explicitly communicate with each other using these lights [5, 6, 10, 12, 14, 16]. In this model, the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The classical model of silent entities and the more recent model of entities with visible lights share a common assumption, that   visibility is unobstructed . That is, three or more collinear agents are assumed to be mutually visible. It can be easily argued against such an assumption, and for the importance of investigating computability when visibility is obstructed by presence of the agents: given three collinear agents, the one in the middle blocks the visibility between the other two and they cannot see each other. Nothing is known on computing with   obstructed visibility   except for the investiga- tions on the so-called   fat agents   model, where agents are not points but unit discs, and collisions are allowed 5   and can be used as an explicit computational tool. (e.g., [1,2,4]); and for the study of uniformly spreading agents operating in a one dimensional space (i.e., on a line) [3]. In this paper we start to fill this void, and focus on agents with visible lights in presence of obstructed visibility. The problem we investigate is perhaps the most basic in a situation of obstructed visibility, and it is the one of the agents reaching a configuration of complete un- obstructeded visibility. More precisely, this problem, that we shall call C OMPLETE  V ISIBILITY , requires the agents, starting from an arbitrary initial configuration where  5   In pointilinear models, collisions create unbreakable symmetries; thus, unless this is the re- quired outcome of the problem, their avoidance is required by all solution protocols. In ad- dition, in real world implementations, collisions (e.g., of two quad copters) may have unpre- dictable outcomes that might be better avoided.
they are in distinct points but might be unable to see everybody and might not know the total number of agents 6 , to reach within finite time a configuration in which every agent is in a distinct location from which it can see all other agents, and no longer move. Among the configurations that achieve complete visibility, a special class is that where all agents are on the perimeter of a circle (not necessarily equally spaced). The problem of forming any such a configuration is called C IRCLE   F ORMATION   and it has been extensively studied both in the classical model of silent agents and in the ones with visible lights (e.g., [7–9, 13, 15]). Unfortunately, none of these investigations consider obstructed visibility, and their algorithms do not work in the setting considered here.  1.2   Our Contributions  In this paper we study solving C OMPLETE   V ISIBILITY   by robots with lights. That is, we consider autonomous and anonymous agents, each endowed with a visible light that can assume a constant number of persistent colors, that are otherwise oblivious, and whose visibility is obstructed by other agents in the line of sight; and we investigate under what conditions they can solve C OMPLETE   V ISIBILITY   and at what cost (i.e., how many colors). We do not make any assumptions on a-priori knowledge on the number of agents, nor on agreement on coordinate systems, unit of distance and chirality; actually, the lo- cal coordinate system of an agent may change at each activation. Neither we make any assumption on rigidity of movements; that is, a move may be stopped by an adversary before the agent reaches its destination; the only constraint is that, if interrupted before reaching its destination, the agent moves at least a minimum distance   δ >   0   (other- wise, no destination can ever be reached). Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that C OMPLETE   V ISIBILITY   is always solvable, even in the   asynchronous   setting, without collisions and using a small constant number of colors. The proof is constructive. We first design a protocol that achieves complete visibility with six colors under a semi-synchronous scheduler. We then show how to transform it into an asynchronous algorithm with only four additional colors. We also show how to extend the protocol so that, under the same weak conditions and without increasing the number of colors, the agents can position themselves on the perimeter of a circle. In other words, we also show how to solve the (non-uniform) C IRCLE   F ORMATION   problem with obstructed visibility. Due to lack of space, some of the proofs are sketched and some omitted.  2   Model and Definitions  Consider a set of mobile anonymous agents   A   :   { a 1 , a 2 , .., a n } . Each agent   a i   has a persistent state variable   s i , which may assume any value in a finite set of   colors   C .  6   The actual number of agents may be unknown for several reasons; e.g., if the deployment of agents has been done by an airplane, a subset of agents may be lost or destroyed during the landing process.
We denote by   x i ( t )   ∈   R 2   the position occupied by agent   a i   at time   t   expressed in some global coordinate system (used only for description purposes, and unknown to the agents); when no ambiguity arises, we omit the indication of time. A   configuration  C   is a set of   n   tuples in   C   ×   R 2   each defining the position and color of an agent; let   C t  denote the configuration at time   t . Each agent   a i   has its own system of coordinates centered in itself, which does not necessarily agree with those of the other agents, i.e. there is no common unit of measure and not common notion of clockwise orientation. Agents   a i   and   a j   are visible to each other at time   t   if and only if the segment   x i ( t ) x j   ( t )   does not contain any other agents. Let   C t [ a i ]   denote the set of the positions and colors of the agents visible to   a i   time   t . We shall call such a set   local view . A configuration   C   is said to be   obstruction-free   if  ∀ a i   ∈ A   we have   |C [ a i ] |   =   n ; that is, if all agents can see each other. Two agents   a i  and   a j   are said to   collide   at time   t   if   x i ( t ) =   x j   ( t ) . At any time, agents can be active or inactive. When activated, an agent   a i   performs a sequence of operations called   Look-Compute-Move : it activates the sensors to obtain a snapshot (called   local view   ) of the positions of the visible agents expressed in its own coordinate system ( Look ); it then executes an algorithm (the same for all agents) based on its local view, which returns a destination point   x   ∈   R 2   and a color   c   ∈   C  ( Compute ); it then sets its own state variable to   c   and moves towards   x   ( Move ). The movement may be stopped by an adversary before the agent reaches its destination; the only constraint on the adversary is that, if interrupted before reaching its destination, a robot moves at least a minimum distance   δ >   0   (otherwise, no destination can ever be reached). We consider two schedulers for the activation of the agents:   Semi-Synchronous  ( SSYNC ) and   Asynchronous   ( ASYNC ). In   SSYNC , the time is discrete; at each time in- stant   t   (called   round ) a subset of the agents is activated and performs its operational cycle instantaneously. The choice of the activation is done by an adversary, which how- ever activates each agent infinitely often. In   ASYNC , there is no common notion of time; each agent is activated independently, and each Compute and Move operation can take an unpredictable (but bounded) amount of time, unknown to the agent. At the beginning (time t=0), the agents start in an arbitrary configuration   C 0   occu- pying different positions, and they are   black   (the state variable of each one is set to a special symbol   ă   ). The goal is for the agents to reach, in finite time, an obstruction-free configuration without ever colliding. We call this problem C OMPLETE   V ISIBILITY . An algorithm is said to solve the problem if it always achieves complete visibility regard- less of the choices of the adversary, and from any initial configuration. Let   H t   be the convex hull defined by   C t , let   ∂ H t   =   V t   ∪ B t   denote the agents on the border of   H t , where   V t   :   { v 1 , . . . , v k } ⊆ A   is the set of agents (   corner-agents ) located at the corners of   H t   and   B r   :   { b 1 , . . . , b l }   is the set of those located on the edges of   H r   ( edge-agents ); let   I t   be the set of agents that are interior of   H t   (   interior- agents ). Let   n t   =   |V t |   be the number of corners in   H 0 . Given an agent   a i   ∈   A , we denote by   H t [ a i ]   the convex hull of its local view   C t [ a i ] . Let   C c t   indicate the set of agents in   C t   with color   c   at time   t , similarly we define   H c t   [ a i ]   as the convex hull, of  C c t   [ a i ] . Analogously defined are the extensions of   V t ,   B t ,   I t . Given a configuration   C , we indicate by   SEC ( C )   the smallest enclosing circle containing   C   (when no ambiguity
arises we just use the term   SEC ). Given two points   x, y   ∈   R 2   with   xy   we indicate the line that contains them, and we use the operator   ∩   to indicate the intersection of lines and segments. Let   d ( x, y )   indicate the Euclidean distance between two points (or a segment and a point); moreover, given   x, y, z   ∈   R 2   we use   ∠ xyz   to indicate the angle with vertex   y   and sides   xy, yz . In the following, with an abuse of notation, when no ambiguity arises, we use   a i   to denote both the agent and its position.  3   Complete Visibility in SSYNC  In this Section we provide an Algorithm that reaches Complete Visibility in the semi- synchronous setting. The algorithm is described assuming   |V 0 | ≥   3 ; we will then show how the agents can easily move to reach this condition starting from a configuration with   |V 0 |   = 2 . Our algorithm works in two phases: (1)   Interior Depletion   (ID) and (2)   Edge Deple- tion   (ED). The purpose of the Interior Depletion phase is to reach a configuration   C ID  in which there are no interior-agents. In this phase, the interior-agents move towards an edge they perceive as belonging to the border of the convex hull, and they position themselves between two corner-agents. At the end of this phase, all agents are on   ∂ H 0 . The goal of the Edge Depletion phase is to have all agents in   B ID   to move so to reach complete visibility.  3.1   Phase 1: Interior Depletion Phase  Initially all agents are   black . The objective of this phase is to have all agents on   ∂ H 0 , with the corner-agents colored   red   and the edge-agents colored   brown . Notice that corner (resp. edge) agents are able to recognize their condition in spite of possible obstructions. In fact, if a   black   agent   a i   is activated at some round   r , and it sees that   C r   [ a i ]   contains a region of plane that is free of agents and wider than   180 ◦ , then   a i   knows it is a corner and sets its variable   s i   to   red . A similar rule is applied to edge-agents; in this case, an edge-agent   a i   sets its variable   s i   to   brown   if   C r   [ a i ]  contains a region of plane free of agents and wide exactly   180 ◦   (see Coloring Case of Figure 1). In the ID phase, corner-agents color themselves   red , and no longer move, while edge-agents color themselves   brown . Each interior-agent   a   moves to position itself on one of its nearest visible edges of   ∂ H 0 ; note that an edge of   ∂ H 0   can be recognized in  a ’s local view once it is occupied only by   brown   and   red   agents. To prevent collisions, the interior-agent moves towards the chosen edge   e   perpendicularly if and only if it is one with minimum distance to   e   and its destination on   e   is empty; otherwise it does not move. An edge-agent on the destination of an interior one, slightly moves to make room for the interior-agent. The I NTERIOR   D EPLETION   algorithm is detailed in Figure 1. It is easy to see that at the end of this phase, all the agents will be positioned on a convex hull.  Lemma 1.   For any initial configuration   C 0   there exists a round   r   ∈   N +   such that in   C r  we have that   I r   =   ∅ ; furthermore, this occurs without collisions.
Algorithm I NTERIOR   D EPLETION   (for the generic agent   a i   activated at round   r )  –   Coloring Case: if ( s i   =   black ) then:  •   If ( a i   is a corner-agent in   H r   [ a i ]) ) then   a i   sets   s i   =   red  •   If ( a i   is an edge-agent in   H r   [ a i ]) ) then   a i   sets   s i   =   brown  –   Interior Case: if ( a i   is interior in   H r   [ a i ])   and   s i   =   black ) then:  •   a i   uses its local view   C r   [ a i ]   to determine the edges of   ∂ H r   [ a i ] .  •   If ( ∃ e   ∈   ∂ H r   [ a i ]   such that   ∀ a j   ∈ I r   [ a i ] , d ( a j   , e )   ≤   d ( a i , e ) ) then  ∗   a i   computes a point   x   of   e   such that   a i x   ⊥   e ; if   x   is empty, then   a i   moves toward   x  –   Obstructing Edge Case: if ( s i   =   brown   ) then:  •   Let   e   be the edge to which   a i   belongs; if ( ∃ a j   ∈ I r   [ a i ]   ∧   a j   a i   ⊥   e ), then   a i  moves toward the nearest point   x   ∈   e   such that   ∀ a k   ∈ I r   [ a i ] ,   a k   x   6   ⊥   e .  Fig. 1:   Algorithm for the Interior Depletion Phase  Theorem 1.   There is a round   r   ∈   N +   such that the agents occupy different positions on   H r   . Moreover, the corner-agents are   red , and the edge-agents are   brown .  3.2   Phase 2: Edge Depletion -ED  The purpose of the ED phase is to move the edge-agents out of the current convex hull to reach a final configuration whose convex hull includes   H 0   and all agents are on the corners, thus achieving complete visibility. The algorithm makes an edge-agent move from its edge   e   =   v 0 v 1   to a point out of the current convex hull, but within a   safe zone . Safe zones are calculated so to guarantee that   red   agents never cease to be located on corners of the current convex hull, in spite of the movement of the edge-agents. More precisely, the safe zone   S ( e )   of   e   consists of the portion of plane outside the current convex hull, such that   ∀ x   ∈   S ( e )   we have  ∠ xv 0 v 1   <   180 ◦   − ∠ v − 1   v 0 v 1  4   and   ∠ v 0 v 1 x <   180 ◦   − ∠ v 0   v 1 v 2  4   (see Figure 2a). Note that, due to the mutual obstructions that lead to different local views, edge- agents cannot always compute   S ( e )   exactly (see Figure 2b). In fact, only when there is a single edge-agent between the two   red   corner-agents on   e , the computation of   S ( e )  is exact; in any case, we can show that the safe area   S ′ ( e )   computed by an agent is  S ′ ( e )   ⊆   S ( e )   and thus still safe. The migration of edge-agents and their transformation into corner-agents occurs in steps: in fact, if the edge   e   contains more than one edge-agent, our algorithm makes them move in turns, starting from the two agents   b 1   and   b 0   that are immediate neigh- bors of the corners   v 1   and   v 0 , respectively. Only once they are out of the convex hull and they are corner of a new edge   e ′ , other agents on   e   will follow, always moving perpendicularly to   e ′ . Careful changes of colors are required to coordinate this process. In fact, once the first pair is in position, the two agents will become   blue   to signal the other   brown   agents on   e   that it is their turn to move out; they will set their color to   red
only when there is no interior-agent in the space delimited by   e ′   and   e . Once   red , their color will never change until completion. Due to the different estimations of   S , to semi-synchronicity, and to the unpredictable distance traversed by an agent (possibly stopped before destination), a variety of situa- tions could disrupt this ideal behaviour. In particular, it could happen that only one of the two agents, say   b 1 , moves while the other stays still, or that   b 1   moves further from  e   than   b 0 . In both cases this leads to a configuration in which   b 0   becomes a interior or edge-agent. This problem is however adjusted by   b 1   that, when noticing the situation, moves towards   v 1   until   b 0   becomes a corner in   H [ b 1 ] . A further complication is that   b 1  might wrongly perceive   b 0   as a corner and thus decide not to move; this occurs if   v 0 b 0  happens to be collinear with   b 1   obstructing visibility; such a case is however detected by   b 0   itself, which uses a different color ( orange ) to signal that   b 1   has to move further towards   v 1   to transform   b 0   into a corner (see Figure 2d). v    1  v   0   v   1  v   2  b   0  Safe Area  b   1  (a)   Safe Area of edge   v 0 v 1 : an agent moving inside the safe area cannot create collinearity with agents on the neighboring edges v    1  v   0   v   1  v   2  b   0   b   1  (b)   Approximation of the safe area computed by agent   b 1   using as reference the two lines   v 1 v 2   and   v − 1 b 0   . This approximation is entirely contained in the real safe area v    1  v   0   v   1  v   2  b   0   b   1  (c)   Creation of a new edge, due to non-rigid movements or to different approximations of the safe area, agent   b 1   could move making agent   b 0   interior, this condition is adjusted by letting   b 1  move towards   v 1 v    1  v   0   v   1  v   2  b   0  b   1  (d)   b 1   could move in such a way to become collinear to   v 0 b 0 ,   b 0  signals this condition by changing its color  Fig. 2: Edge Depletion Phase The detailed algorithm for the ED phase is reported in Figure 3.  3.3   The case of   |V 0 |   = 2  The strategy of the previous Section works for   |V 0 |   >   2 . It is however simple to have the agent move to reach such a condition from   |V 0 |   = 2 , as described below. When   |V 0 |   = 2   the agents are necessarily disposed forming a line and   |A| ≥   2 . First notice that an agent   a   can detect that the configuration is a line, and whether it is an extremity (i.e., it sees only one other agents   a ′ ), or an internal agent (i.e., it is
Algorithm E DGE   D EPLETION  For agent   a i   activated at round   r ; to be executed if and only if   @ ( black, a j   )   ∈ C r   [ a i ] . - Execute C OMPUTE   O RDER   and appropriate case from the list below.  –   B ROWN   E DGE   C ASE :   a i   belongs to an edge   e   of   C r   [ a i ]   and   s i   =   brown . If   a i   is the only agent on   e   then  •   a i   computes the angles   α   = 180 ◦   −   ∠ v − 1 v 0 a i ,   β   = 180 ◦   −   ∠ a i v 1 v 2 , and   γ   =  min (   α  4   ,   β  4   ) ; it then computes a point   x   such that   ∠ xv 1 a i   < γ   and   ∠ xv 0 a i   < γ .  •   a i   sets   s i   =   yellow .  •   a i   moves perpendicularly to   e   with destination   x . If   a i   is not the only non- red   agent on   e   and one of its neighbors on   e   is   red   (by routine C OMPUTE O RDER , this agent is   v 1 ) then: let   b   be its other neighbor;  •   a i   computes the two angles   α   = 180 ◦   −   ∠ a i v 1 v 2 ,   β   = 180 ◦   −   ∠ v − 1 ba i , and  γ   =   min (   α  4   ,   β  4   ) ; it then computes a point   x   such that   ∠ xv 1 a i   < γ   ∧   ∠ xba i   < γ .  •   a i   sets   s i   =   yellow .  •   a i   moves perpendicularly to   e   with destination   x .  –   Y ELLOW   C ASE :   s i   =   yellow .  •   if there is another   yellow   or   blue   agent   a j   with   e a i   =   e a j   then  ∗   if   a i v 1   ∩   a j   v 0   6   ∈   ( a i v 1   ∪   a j   v 0 )   then   a i   sets   s i   =   blue  ∗   if   a i v 1   ∩   a j   v 0   ∈   a i v 1   then   a i   moves towards   v 1   along   a i v 1   of   d ( a i ,v 1 ) 2  ∗   if   a j   ∈   a i v 1   then   a i   sets   s i   =   orange  •   else if   @ ( s j   , a j   )   ∈ C r   [ a i ]   with   a j   6   =   a i   and   e a i   =   e a j   and   @ ( s j   , a j   )   ∈ C r   [ a i ] ∩ e a i  then  ∗   a i   set   s i   =   red  –   O RANGE   C ASE :   s i   =   orange .  •   if there is another blue agent   a j   with   e a i   =   e a j   then  ∗   if   a j   6   ∈   a i v 1   then   a i   sets   s i   =   blue  –   B LUE   C ASE :   s i   =   blue   and   a i   ∈   e   with   e   edge of   C r   [ a i ] .  •   if there is another orange agent   a j   with   e a i   =   e a j   then  ∗   a i   moves along   a i v 1   in direction of   v 1   towards the point at distance   d ( a i ,v 1 ) 2  •   else if   @ ( brown, a j   )   ∈ C r   [ a i ]   such that   a j   could move to   e   then  ∗   a i   sets   s i   =   red  –   B ROWN   I NTERIOR   C ASE :   a i   is such that   s i   =   brown   and   a i   ∈ I r   [ a i ] .  •   if there exists and edge   e ′   =   a x a y   with   s x   =   s y   =   blue   and   a i   could move perpendicularly towards   e ′   without crossing any segment delimited by two   red  agents, then   a i   moves towards   e ′ .  •   if   a i   ∈   e   =   a 0 a 1   with   e   ∈   ∂ H { red,brown }  r   [ a i ]   and   ∃ x   ∈   R 2   such that   a 0 a i   ⊥   xa i  and   @ a j   ∈   ∠ a 0 a i x   or   @ a j   ∈   ∠ a 1 a i x   then   a i   executes the second subcase of the B ROWN   E DGE   C ASE .  –   C ORNER   C ASE :   a i   is a corner of   C r   [ a i ]   and   s i   =   red .  •   a i   can check local termination and the global termination  ∗   a i   locally terminates when   s i   =   red  ∗   a i   detects the global termination of ED phase when   @ ( s j   , a j   )   ∈ C r   [ a i ]   with  s j   6   =   red  Fig. 3:   Edge Depletion Phase algorithm
Procedure C OMPUTE   O RDER  –   if   a i   belongs to an edge   e   of   H r   [ a i ]   and   s i   =   brown , it orders the   red   agents in its local view in a circular order, starting from the closest,   ( v 1 , v 2 , . . . , v 0 ) .  –   if   s i   ∈ { orange, blue, yellow } , then   a i   determines which of its current neighbors was  v 1   in its previous computation and the edge   e a i   =   v 1 v 0   to which it belonged:  •   a i   computes the nearest edge   e   =   { u, v } ∈ H red r   [ a i ]  •   a i   computes the point   x   ∈   R 2   such that is   uv   ⊥   a i x  •   a i   sets   v 1   =   u, v 0   =   v   if   @ a j   ∈   ∠ uxa i   otherwise it sets   v 1   =   v, v 0   =   u .  •   a i   sets   e a i   =   v 1 v 0  Color   Meaning   Transition to:  Black   initial color of all agents   { Red, Brown }  Brown   agents on edges or having to move to a new edge of   H   Y ellow Y ellow   agents moving out of   H   to form a new edge   { Blue, Orange, Red }  Orange   agents needing to be transformed into corners   Blue Blue   corner-agent now forming a new edge   e , waiting for other agents to move to   e Red Red   a stable corner-agent   −  Fig. 4:   Colors used in the C OMPLETE   V ISIBILITY   algorithm.  between two collinear agents). If   a   is internal, it does not move; if it is an extreme,  a   sets its color to   red   and moves perpendicular to the segment   a ′ a . This means that, as soon as at least one of the extremes is activated, it will move (or they will move) creating a configuration with   |V|   >   2 . At that point, the algorithm previously described is applied.  Correctness of the ED phase.   With the following lemma we show that the global absence of interior-agents with respect to the initial convex hull, can be locally detected by each agent.  Lemma 2.   Given an agent   a i   ∈ A   with   s i   ∈ { red, brown }   and a round   r   ∈   N + , if  @ ( black, a j   )   ∈ C r   [ a i ]   then   C r   does not contain interior-agents with respect to   H 0 .  Proof.   By contradiction, assume that   @ ( black, a j   )   ∈ C r   [ a i ]   but there exists at least an interior-agent   a   with respect to   H 0 . By the rules of the ID phase, agent   a   cannot change its color from   black   to another because it can detect it is neither a corner nor a border. Thus,   a   is not in   C r   [ a i ]   because   C r   [ a i ] , by assumption, does not contain   black   agents. Thus, it must exist an agent   a k   that has color different from   black   and   a k   ∈   a i a . But since   a   is interior then also   a k   is interior, and so   s k   =   black .   2 Lemma   2
We now show that the safe area   S ′ ( e )   computed by an edge-agent on   e   is such that  S ′ ( e )   ⊆   S ( e )   and thus its movement is still safe (it does not transform a   red   corner into an interior or edge-agent).  Lemma 3.   Given a configuration   C r   and an edge   e   =   v 0 v 1   of   H r   , if an agent   a j   ∈   e  moves from   e , it moves inside the safe zone   S ( e )  Proof.   The case when there is a single edge-agent   b   ∈   e   is trivial because   b   can compute exactly   S ( e ) . Consider now the case when there are two or more edge-agents on   e ; among those, let   b 0   and   b 1   be the two that are neighbors of   v 0 , v 1 . Those agents move only when executing the Brown Edge Case or Brown Interior Case. Let us consider the movement of the first that is activated, say   b 1 . Agent   b 1   has two neighbors on   e : a  brown   neighbor   b   and the   red   corner   v 1 . Agent   b 1   orders the corners in its view from  v 1   to   v last , according to its local notion of clockwise, where   v last   is the last corner before   b , i.e.   v − 1   in Figure 2b. Following the rules of the algorithm,   b 1   computes:   α   = 180 ◦   −   ∠ v last bb 1 ,   β   = 180 ◦   −   ∠ b 1 v 1 v 2 , and   γ   =   min (   α  4   ,   β  4   ) . Angle   ∠ v last bb 1   is an upper bound on   ∠ v last v 0 b 1 , otherwise we could get a contradiction since   v last b   and  v last v 0   will intersect in two points: one is   v last   and the other one is after the intersection of   v last v 0   and   v 0 v 1 , that is impossible. Thus,   α   is a lower bound on the angle that a single agent would compute on   e , which implies that   b 1   will move inside   S ( e ) . The same holds for   b 0 . Notice that, given two points   x   and   y   inside the safe zone, any point  z   ∈   xy   is still inside the safe zone, thus any agent that moves on the lines connecting two agents inside   S ( e )   will still be in   S ( e ) , completing the proof.   2 Lemma   3  The next lemma shows that the moves of our algorithm cannot transform any   red  corner-agents into an interior-agent.  Lemma 4.   Consider a corner-agent   v 1   of   H r ′   with   s 1   =   red , we have that   ∀ r   ∈   N +  with   r > r ′ ,   v 1   is also a   red   corner-agent of   H r   .  Proof.   It is easy to see that during the ID phase we have that   H r   =   H 0   since the interior-agents will never trespass the edges of   H 0 , so the hypothesis holds. We have to show that the same holds during the ED phase. We have that   v 1   never moves after it sets   s 1   =   red   so if   v 1   is a corner it cannot become interior as a consequence of its own move. Consider the two edges adjacent to   v 1 :   e 1   =   v 0 v 1   and   e 2   =   v 1 v 2 . Assume, by contradiction, that there exists a round   r   in which the moves of a set   X   of agents on these two edges is such that   v 1   is a corner-agent in   H r − 1   but not in   H r   . From Lemma 3 we have that agents in   X   move to points inside the safe zones   S ( e 1 )   and   S ( e 2 )   of  e 1 , e 2 . Let us consider two points   x   ∈   S ( e 1 )   and   y   ∈   S ( e 2 ) , such that agents on them will make   v 1   interior. If   v 1   is interior in   H r   , we have that   ∠ xv 1 y >   180 ◦ . It is easy to see that   ∠ v 0 v 1 x < γ   (see Brown Edge Case and Brown Interior Case of Figure 3) and that   γ   ≤   180 ◦   − ∠ v 0 v 1   v 2  4   , since   γ   =   min (   α  4   ,   β  4   ) , and that at least one of the two among   β, α   is a lower bound on   180 ◦   −   ∠ v 0 v 1 v 2 . The same holds for   y , so we have  ∠ v 2 v 1 y   ≤   180 ◦   − ∠ v 0 v 1 v 2  4   . Thus, we have   ∠ v 0 v 1 x   +   ∠ v 2 v 1 y   +   ∠ v 0 v 1 v 2   <   180 ◦   and then   ∠ xv 1 y <   180 ◦ , which is a contradiction. So,   v 1   cannot be interior in   H r   . The same arguments hold if at round   r   −   1   we consider a set of agents   X   on two edges   e ′ , e ′′  that are not adjacent to   v 1 ; this is easy to see since, given   x   ∈   S ( e ′ )   and   y   ∈   S ( e ′′ )   we
have   ∠ xv 1 y   ≤   ∠ v 0 v 1 v 2   <   180 ◦ , which is another contradiction to the hypothesis of   v 1  being interior in   H r   .   2 Lemma   4  In the next sequence of lemmas, we show that, given an edge   e   in a configuration   C  of the ED phase, all edge-agents in   e   will eventually became   red   corners.  Lemma 5.   Given a configuration   C r   and an edge   e   of   H r   with a single brown agent   b  on   e , eventually   b   will be a   red   corner.  Proof.   Since   red   corners never move and no interior-agents can be moving on   e , while inactive, agent   b   maintains its single position inside   e . When activated at some round  r ′ , agent   b   executes the Brown Edge Case with a single agent. Thus   b   switches color to  yellow   and it moves perpendicularly to   e   of at least   min ( d ( v h , x ) , δ ) . At round   r ′   + 1 ,   b  is a corner-agent of   H r ′ +1 ; in the next activation, after executing the Yellow Case code,  b   becomes   red .   2 Lemma   5  Lemma 6.   Given a configuration   C r   and an edge   e   of   H r   with exactly two brown agents  b 0 , b 1   on   e , eventually they will set their state variable to   yellow   and they will move outside   e .  Proof.   Let   b 1   be the first to be activated at some round   r ′   ≥   r . At that time,   b 1   switches its color to   yellow   and it moves perpendicularly to   e   (see Brown Edge Case). Agent   b 0  will do the same, no matter if it is activated in round   r ′   or in some successive rounds (see Brown Edge Case and Brown Interior Case).   2 Lemma   6  Lemma 7.   Given a configuration   C , any agent   b 1   with   s 1   =   yellow   eventually becomes corner and will sets its state variable to   red .  Proof.   If   b 1   is   yellow   then   a 1   has moved from an edge   e   =   v 0 v 1 . If   b 1   was not the only agent on   e   that could move, then there is (or there will be) another   yellow   agent  b 0   moving from   e . By construction,   b 1   waits until it sees the other   yellow   agent   b 0   (see Yellow Case). If both   b 1   and   b 0   realize to be corners of the current convex hull, then they eventually set their color to   blue   and then to   red , thus the lemma is proved. However, due to the non-rigidity or the different local views of   b 1   and   b 0 , the pathological case of Figure 2c may arise where one of the two, say   b 0 , becomes an interior-agent. This case is adjusted by the Yellow Case rule: each time   a 1   is activated, it will move towards   v 1  until a round   r ′′   is reached when   b 0   is not interior anymore in   C r ′′   [ b 1 ] . Note that, since  b 1   moves always half of the distance   d ( b 1 , v 1 ) , and the number of rounds until the next activation of   b 0   is finite, we have that   b 1   will never touch   v 1 . Two possible sub-cases may happen at round   r ′′ :   ( i )   b 1 v 1   ∩   b 0 v 0   6   ∈   ( b 0 v 0   ∪   b 1 v 1 ) : in this case, in the subsequent activations,   b 1   and   b 0   will set their colors to   blue ;   ( ii )   b 1   ∈   b 0 v 0 : this might not be detected by the local view of   b 1 , but it is detected by   b 0   that sets its color to   orange   ; in the next activations   b 1   will move so to transform   b 0   into a corner and, after this move, an activation of   b 0   will set   s 0   =   blue . So, in both sub-cases we eventually reach a configuration in which   b 1   and   b 0   are   blue   corner-agents. In the subsequent activations, they will set their color to   red   , proving the lemma.   2 Lemma   7  Lemma 8.   Given a configuration   C , let   e   =   v 0 v 1   be an edge with   q >   2   edge-agents on it. Eventually all these agents will become corners and set their color to   red .
Proof.   The two edge-agents   b 0 , b 1   ∈   e   that are neighbors of   red   corners, execute the same code described in the previous lemma. So, they wil reach a configuration   C r ′   in which   b 0   and   b 1   are   blue   corner-agents. In this case, they wait until all the agents on   e  move on the segment   b 0 b 1 ; then, they set their color to   red   (see the rule 3 of Blue Case). It is straightforward to see that each remaining agent on   e   will move now towards this new edge without colliding, since all movements to the same edge are on parallels trajectories. It follows that, in finite time, a new edge   e ′   is formed with   q   −   2   agents. Iterating the reasoning we will end up in a case where the number of edge-agents on the same edge is at most 2, hence, by Lemmas 5-7, the lemma follows.   2 Lemma   8  Theorem 2.   The   C OMPLETE   V ISIBILITY   problem is solvable in SSYNC by a team of oblivious, obstructable agents, using five colors without creating any collision.  Proof.   From Theorem 1 we have that from any configuration   C 0   we reach a config- uration   C ID   where   I ID   =   ∅ . This is locally detected by agents (see Lemma 2), that start executing the ED phase. By Lemma 4 we have that the number of   red   corners is not decreasing during the execution of the algorithm. From Lemmas 5-8 we have that eventually each edge-agent   a   of   H ID   will became a   red   corner. So we will reach a configuration   C f inal   in which all agents are corner of   H f inal , thus, they cannot obstruct each other. Moreover, It is easy to see that each agent is able to detect not only local termination, when it sets its color to   red , but also global termination of ED phase, and thus of the algorithm, when each agent in its local view is   red .   2 T heorem   2  4   Complete Visibility in ASYNC  In this section we consider the asynchronous model (ASYNC), where there is no com- mon notion of time or rounds, there are no assumptions on time, on activation, on syn- chronization; moreover, each Compute and Move operation and inactivity may take ant unpredictable (but finite) amount of time, unknown to the agent. As a consequence, agents can be seen while moving, and their computations and movements may be based on obsolete information.  Asynchronous Interior Depletion phase.   The I NTERIOR   D EPLETION   algorithm of Sec. 3.1 works also in ASYNC without modifications. We only need to show that the asynchronous behaviour of the agents, and in particular the asynchronous assignment of colors, cannot induce a collision among interior-agents. Since agents always move perpendicularly to the closest edge, it is easy to see that this does not happen and thus Lemmas 1 and Theorem 1 hold also in the asynchronous case.  Asynchronous Edge Depletion phase.   The Edge Depletion phase has to be modified for ASYNC. To see why the E DGE   D EPLETION   algorithm would not work, consider, for example, the Yellow Case in Algorithm 3: it is possible that a moving   yellow   agent is seen by another   yellow   agent, this could lead to scenarios in which an agent assumes color   red   while it is on the edge of the convex hull and not on a corner. The source of inconsistencies is the fact that agents can be seen while in transit. To prevent this problem we use new colors ( yellow moving   and   blue moving   ) to signal
that the agents are in transit; those agents will take color   yellow   (resp.   blue ) once as the movement is completed. Using these intermediate colors, we can simulate the ED phase of the previous Section (for   |V 0 |   >   2 ). More precisely, in the   Edge Depletion   algorithm of Figure 3, instead of becoming  yellow , a   brown   agent becomes   yellow moving , turning   yellow   at the next activation. Similarly, instead of becoming   blue , a   yellow   agent becomes   blue moving , turning   blue  only when seeing that the “companion” agent is   blue moving   or   blue . It is not difficult to see that, with these additional colors, since agents will always move inside the safe zones of   H , the validity of Lemmas 4, 7-8 holds also in ASYNC.  The case of   |V 0 |   = 2 .   When the agents initially form a line, the algorithm described for SSYNC where the agents first move to a configuration   |V 0 |   >   2 , and then apply the general Algorithm, would not work. Consider, for example, the following scenario: both extreme agents compute and their destination is in opposite direction, but only one of them actually moves. At this point, the agents on the line set their color to   red   or  brown   , but they will became interior-agents as soon as the slower extreme agent moves from the line towards its destination, thus changing the convex hull. The idea is to use a completely different algorithm in ASYNC when the initial configuration is a line (refer to Figure 5b). Two additional special colors ( line-extreme  and   line-moving ) are used. The color   line-extreme   is taken by the two agents   a 1   and   a 2  located at the extreme points of the line,   x 1   and   x n , when activated; this color is used to acknowledge the line condition, and to define the smallest enclosing circle   SEC   with diameter   x 1 , x n . Notice that, due to obstructed visibility, the diameter, and thus   SEC , is unknown to the agents. The two extreme agents will never move. The general strategy is to have the other agents move to points on   SEC . First notice that an agent   a   can detect that the configuration is a line, either by geometric conditions (i.e., it sees only one or two collinear agents), or by the special color of some visi- ble agents ( line-extreme   or   line-moving ). If an uncolred agent   a   located in   x   sees a  line-extreme   agent (say   a 1 ), then   a   changes its color to   line-moving   and it moves per- pendicularly to   xx 1   toward the perimeter of the circle whose diameter is identified by  a 1   and the closest agent   b   6   =   a 1   on the line   xx 1   (note that there must be at least one, possibly the other extreme). A   line moving   agent follows similar rules; if it can detect  SEC   (e.g., it sees two   line-extreme ) it continues its perpendicular move towards it. Oth- erwise, it does not move. It can be shown that, at any time, there is at least one agent that, if activated, can move. A non extreme agent switches its color to   red   when it sees only agents on the SEC; an extreme agents switches its color to   red   when it sees only  red   or   line-extreme   agents. It is not difficult to see that this set of rules will allow the agents to reach   SEC   in finite time becoming   red , and thus to solve the C OMPLETE   V ISIBILITY   problem.  Theorem 3.   The   C OMPLETE   V ISIBILITY   problem is solvable in ASYNC by a team of oblivious, obstructable agents, using eight colors without creating any collision.
5   Circle Formation in ASYNC  When executing the previous algorithm, the agents reach a configuration   C f inal   in which all agents are corners of   H f inal . Starting from this particular configuration it is possible to arrange the agents in such a way to reach a configuration   C circ   in which each agent is positioned on the   SEC ( C f inal ) . Note that the solution of the C OMPLETE  V ISIBILITY   problem when   |V 0 |   = 2   already form a circle, hence we focus on the case  |V 0 |   >   2 . b  c   a  (a)   C IRCLE   F ORMATION : Agent   a   is neighbor of an agent   b  on   SEC , so it moves on line   ca   in direction of   SEC . During this movement, the corner-agents of the convex hull are not modified, and visibility with the other agents is preserved.  (b)   A SYNCH FORMATION FOR   |V 0   |   = 2 : the two extreme agents signal the line configuration with color   line-extreme , the other agents move perpendicularly to them until they reach the  SEC   whose diameter is defined by the extreme agents.  ptionEdge Depletion Phase  Notice that, when all agents are on   ∂H f inal   they can compute the same   SEC ( C f inal )  since all the local views are consistent. Moreover, there exists a set of agents   X ⊆ A  that are already on   SEC , and   |X | ≥   2 . The idea of the algorithm is to move all agents on   SEC   in such a way that in each point of their trajectories they can see a subset of nodes   Y   such that   SEC ( Y ) =   SEC ( X   ) =   SEC ( C f inal ) . More precisely, the mov- ing rule allows agents to move towards   SEC   if they are “neighbors” (i.e., neighboring corner) of some agent on   SEC   in   C f inal   (see Figure 5a). Let   a   be neighbor of some   b  already on   SEC , and let   c   be its other neighbor:   a   will move toward   SEC   on line   ca  guaranteeing that the corner-agents of the convex hull stay corner-agents, and do not loose visibility with any other agent. Note that, unless in final position, there is always at least one agent that can move. The algorithm terminates when all the agents are on  SEC . It is not difficult to see that:  Theorem 4.   Starting from a configuration   C f inal   in which all the agents are corners, there is an algorithm in ASYNC that makes the agents reach a configuration   C circ   in which each agent occupies a different position on   SEC ( C f inal )   without colliding.
Acknowledgements.   This work has been supported in part by the National Science and Engineering Research Council of Canada, under Discovery Grants, and by Professor Flocchini’s University Research Chair.  References  1. C. Agathangelou, C. Georgiou, and M. Mavronicolas.   A distributed algorithm for gather- ing many fat mobile robots in the plane. In   Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC) , 250–259, 2013. 2. K. Bolla, T. Kovacs, and G. Fazekas.   Gathering of fat robots with limited visibility and without global navigation. In   Int. Symp. on Swarm and Evolutionary Comp. , 30–38, 2012. 3. R. Cohen and D. Peleg. Local spreading algorithms for autonomous robot systems.   Theo- retical Computer Science , 399:71–82, 2008. 4. J. Czyzowicz, L. Gasieniec, and A. Pelc.   Gathering few fat mobile robots in the plane.  Theoretical Computer Science , 410(67):481 – 499, 2009. 5. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The power of lights: Syn- chronizing asynchronous robots using visible bits. In   Proceedings of the 32nd International Conference on Distributed Computing Systems (ICDCS) , 506–515, 2012. 6. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Synchronized dancing of oblivious chameleons. In   Proc. 7th Int. Conf. on FUN with Algorithms (FUN) , 2014. 7. S. Datta, A. Dutta, S. Gan Chaudhuri, and K. Mukhopadhyaya. Circle formation by asyn- chronous fat robots. In   Proceedings of the 9th international conference on Distributed Com- puting and Internet Technology (ICDCIT) , 195-207, 2013. 8. X. D ́ efago and S. Souissi.   Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity.   Theor. Comp. Sci. , 396(1,3):97–112, 2008. 9. O. Petit F. Dieudonn ́ e, Labbani-Igbida.   Circle formation of weak mobile robots.   ACM Transactions on Autonomous and Adaptive Systems , 3(4):1–16, 2008. 10. A. Efrima and D. Peleg. Distributed models and algorithms for mobile robot systems. In  Proceedings of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , 70–87, 2007. 11. P. Flocchini, G. Prencipe, and N. Santoro.   Distributed Computing by Oblivious Mobile Robots . Morgan & Claypool, 2012. 12. P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita.   Rendezvous of two robots with constant memory. In   Proceedings of the 20th International Colloquium on Structural Infor- mation and Communication Complexity (SIROCCO) , 189–200, 2013. 13. B. Katreniak.   Biangular circle formation by asynchronous mobile robots.   In   Proc. 12th Int. Coll. on Structural Information and Communication Complexity (SIROCCO) , 185–199, 2005. 14. D. Peleg. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In   Proc. 7th Int. Workshop on Distr. Comp. (IWDC) , 1–12, 2005. 15. K. Sugihara and I. Suzuki. Distributed motion coordination of multiple mobile robots. In  Proceedings of 5th IEEE Int. Symposium on Intelligent Control , 138–143, 1990. 16. G. Viglietta. Rendezvous of two robots with visible bits. In   Proc. 9th Symp. on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGO- SENSORS) , 291–306, 2013.