Formation of General Position by Asynchronous Mobile Robots  S. Bhagat  ACM Unit Indian Statistical Institute Kolkata-700108  subhash.bhagat.math@gmail.com  S. Gan Chaudhuri  Department of Information Technology Jadavpur University Kolkata-700032  srutiganc@it.jusl.ac.in  K. Mukhopadhyaya  ACM Unit Indian Statistical Institute Kolkata-700108  krishnendu@isical.ac.in  ABSTRACT  The traditional distributed model of autonomous, homoge- neous, mobile point robots usually assumes that the robots do not create any visual obstruction for the other robots, i.e., the robots are see through. In this paper, we consider a slightly more realistic model, by incorporating the notion of   obstructed visibility   (i.e., robots are not see through) for other robots.   Under the new model of visibility, a robot may not have the full view of its surroundings. Many of the existing algorithms demand that each robot should have the complete knowledge of the positions of other robots. Since, vision is the only mean of their communication, it is required that the robots are in   general position   (i.e., no three robots are collinear). We consider   asynchronous   robots. They also do not have common   chirality   (or any agreement on a global coordinate system). In this paper, we present a distributed algorithm for obtaining a general position for the robots in finite time from any arbitrary configuration. The algorithm also assures collision free motion for each robot. This algo- rithm may also be used as a preprocessing module for many other subsequent tasks performed by the robots.  Keywords  Asynchronous, oblivious, obstructed visibility, general posi- tion.  1.   INTRODUCTION  The study of a set of autonomous mobile robots, popularly known as swarm robots or multi robot system, is an emerg- ing research topic in last few decades. Swarm of robots is a set of autonomous robots that have to organize themselves in order to execute a specific task in collaborative manner. Various problems in several directions, have been studied in the framework of swarm robots, among the others dis- tributed computing is an important area with this swarm robots. This paper explores that direction.  Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$15.00.  1.1   Framework  The traditional distributed model [12] for multi robot sys- tem, represents the mobile entities by distinct points located in the Euclidean plane. The robots are anonymous, indistin- guishable, having no direct means of communication. They have no common agreement in directions, orientation and unit distance. Each robot has sensing capability, by   vision , which enables it to determine the position (within its own coordinate system) of the other robots.   The robots oper- ate in rounds by executing   Look-Compute-Move   cycles. All robots may or may not be active at all rounds. In a round, when becoming active, a robot gets a snapshot of its sur- roundings (Look) by its sensing capability.   This snapshot is used to compute a destination point (Compute) for this robot.   Finally, it moves towards this destination (Move). The robot either directly reaches destination or moves at- least a small distance towards the destination.   The choice of active robot in each round is decided by an adversary. However, it is guaranteed that each robot will become active in finite time. All robots execute the same algorithm. The robots are oblivious, i.e., at the beginning of each cycle, they forget their past observations and computations [10].   De- pending on the activation schedule and the duration of the cycles, three models are defined.   In the   fully-synchronous  model, all robots are activated simultaneously. As a result, all robots acts on same data. The   semi-synchronous   model is like the fully synchronous, except that the set of robots to be activated is chosen at random. As a result, the active robots act on same data.   No assumption, is made on tim- ing of activation and duration of the cycles for   asynchronous  model. However, the time and durations are considered to be finite. Vision and mobility enable the robots to communicate and coordinate their actions by sensing their relative posi- tions. Otherwise, the robots are silent and have no explicit message passing. These restrictions enable the robots to be deployed in extremely harsh environments where communi- cation is not possible, i.e an underwater deployment or a military scenario where wired or wireless communications are impossible or can be obstructed or erroneous.  1.2   Earlier works  Majority of the investigations[9, 12] on mobile robots as- sume that their visibility is unobstructed or full, i.e., if two robots   A   and   B   are located at   a   and   b , they can see each other though other robots lie in the line segment   ab   at that time. Very few observations on obstructed visibility (where  arXiv:1408.2072v1 [cs.DC] 9 Aug 2014
A and B are not mutually visible if there exist other robots on the line segment   ab ) have been made in different models; such as, (i) the robots in the one dimensional space [5]; (ii) the robots with visible lights [7, 8] and (iii) the unit disc robot called   fat robots   [1, 6]. The first model studied the uniform spreading of robots on a line [5].   In the second model, each agent is provided with a local externally visible   light , which is used as colors [7, 8, 9, 11, 12, 13, 2]. The robots implicitly communicate with each other using these colors as indicators of their states. In the third model, the robots are not points but unit discs [4, 6, 1]) and collisions among robots are allowed. Obstructed visibility have been addressed recently in [2] and [3].   In [2] the authors have proposed algorithm for robots in light model.   Here, the robots starting from any arbitrary configuration form a circle which is itself an unob- structed configuration. The presence of a constant number of visible light(color) bits in each robot, implicitly help the robots in communication and storing the past configuration. In [2], the robots obtain a obstruction free configuration by getting as close as possible.   Here, the robots do not have light bits.   However, the algorithm is for semi-synchronous robots.  1.3   Our Contribution  In this paper, we propose algorithm to remove obstructed visibility by making of general configuration by the robots. The robots start from arbitrary distinct positions in the plane and reach a configuration when they all see each other. The robots are asynchronous, oblivious, having no agree- ment in coordinate systems. The obstructed visibility model is no doubt improves the traditional model of multi robot system by incorporating real-life like characteristic.   The problem is also a preliminary step for any subsequent tasks which require complete visibility. The organization of the paper is as follows: Section 2, de- fines the assumptions of the robot model used in this paper and presents the definitions and notations used in the algo- rithm. Section 3 presents an algorithm for obtaining general position by asynchronous robots.   We also furnish the cor- rectness of our algorithm in this section. Finally in section 4 we conclude by providing the future directions of this work.  2.   MODEL AND DEFINITIONS  Let   R   =   { r 1   . . . , r n }   be a set of   n   homogeneous robots rep- resented by points. Each robot can sense (see) 360 o   around itself up to an unlimited radius. However, they obstruct the visibility of other robots. The robots execute   look-compute- move   cycle in   asynchronous   manner. They are   oblivious   and have   no direct communication   power. The movement of the robots are   non-rigid , i.e., a robot may stop before reaching its destination. However, a robot moves at-least a minimum distance   δ >   0 towards its destination. This assumption as- sures that a robot will reach its destination in finite time. Initially the robots are positioned in distinct locations and are stationary. Now we present some notations and conven- tions which will be used throughout the paper.  •   Position of a robot:   r i   ∈ R   represents a location of a robot in   R   at some time, i.e.,   r i   is a position occupied by a robot in   R   at certain time. To denote a robot in  R   we refer by its position   r i .  •   Measurement of angles:   By   an angle between two line segments , if otherwise not stated, we mean the angle made by them which is less than equal to   π .  • V ( r i ) : For any robot   r i , we define the vision of   r i ,  V ( r i ), as the set of robots visible to   r i   (excluding   r i  itself). The robots in   V ( r i ) can also be in motion due to asynchronous scheduling. If we sort the robots in   V ( r i ) by angle at   r i , w.r.t.   r i  and connect them in that order, we get a star-shaped polygon, denoted by   ST R ( r i ). Note that   r j   ∈ V ( r i ) if and only if   r i   ∈ V ( r j   ) (Figure 1). r i  Figure 1: An example of STR ( r i )  •   CR ( r i ) : This is the set of line segments joining   r i  to all its neighbors or all robots in   V ( r i ).   CR ( r i ) =  { r i r j   :   r j   ∈ V ( r i ) }   (Figure 2). r i  r j  Figure 2: An example of CR ( r i )  •   L r i   r j   :   Straight line through   r i   and   r j   :   r j   ∈ V ( r i ) (Figure 3)  •   COL ( r i ) :   COL ( r i ) denotes the set of robots for which  r i   creates visual obstructions.  •   DISP ( r i r j ) : When a robot   r i   moves to new position ˆ r i , we call   ∠ r i r j   ˆ r i   as the angle of displacement of   r i  w.r.t.   r j   and denote it by   DISP   ( r i r j   ) (Figure 3). r j  r i  r k  ˆ r i  DISP   ( r i r j   )  L r i r j  Figure   3:   Examples   of   L r i r j   ,   DISP ( r i r j ) =   ∠ r i r j ˆ r i , COL ( r i ) =   { r l ,   r m }
r j − 1  r j  r j +1  r i  r j − 2   r j +2  α ( r i )  Bisec ( r i )  DIR ( r i )  intersect ( r i ) Figure   4:   Examples   of   Γ ( r i ) ,   α ( r i ) ,   Bisec ( r i ) , intersect ( r i )  •   Γ ( r i   :) Set of angles   ∠ r j   r i r k   where   r k   and   r j   are two consecutive vertices of   ST R ( r i ) (Figure 4) .  •   α ( r i ) :   Maximum of Γ( r i ) if maximum value of Γ( r i ) is less than   π   otherwise the 2 nd   maximum of Γ( r i ). The tie, if any, is broken arbitrarily (Figure 4).  •   Bisec ( r i ) : Bisector of   α ( r i ). Note that   Bisec ( r i ) is a ray from   r i   towards the angle of consideration (Figure 4).  •   DIR ( r i ) : The direction of   Bisec ( r i ).   We say that  DIR ( r i ) lies on that side of any straight line where infinite end of   DIR ( r i ) lies (Figure 4).  •   intersect ( r i ) : We look at the intersection points of  Bisec ( r i ) and   L jk   ,   ∀   r j   , r k   ∈ V ( r i ). The intersection point closest to   r i   is denoted by   intersect ( r i ) (Figure 4).  •   Γ ′ ( r i ):   Set of angles   ∠ r i − 1 r j   r i   and   ∠ r i r j   r i +1 ,   ∀ r j   ∈ V ( r i ), where   r i − 1   and   r i +1   are the two neighbors of   r i  on   ST R ( V ( r j   )) (Figure 5). r i  r j  r i +1 r i − 1  r i +2  r j − 1  β ( r i )  Figure 5: Examples of Γ ′ ( r i ) ,   β ( r i ) =   ∠ r j − 1 r i + 2 r i  •   β ( r i ) :   Minimum of Γ( r i )   ∪   Γ ′ ( r i ) (Figure 5).  •   θ ( r i ) :   β ( r i )  n 2   .  •   d   ( r i ) : Distance between   r i   and   intersect ( r i ).  •   D ( r i ) : Distance between   r i   and the robot nearest to it.  •   ∆( r i ) :   min {   d ( r i )  n 2   , D ( r i ) Sin ( θ ( r i )) } .  •   ˆ r i   :   The point on   Bisec ( r i ), ∆( r i ) distance apart from  r i   (Figure 6).  •   C ( r i ) :   The circle of radius ∆( r i ) centered at   r i . Note that ˆ r i   always lies on   C ( r i ) (Figure 6).  •   T   ( C ( r i ) , r j   ) :   Any one of the tangential points of the tangents drawn to   C ( r i ) from   r j   (Figure 6). r i  C ( r i )  T   ( C ( r i ) , r j   )  r j  Bisec ( r i )  ˆ r i  Figure 6: Examples of C ( r i ) , ˆ r i , T ( C ( r i ) ,   r j ) We classify the robots in   R   depending upon their positions with respect to   CH ( R ) (the convex hull of   R ), as below:  •   External vertex robots ( R EV   ):   A set of robots ly- ing on the vertices of   CH ( R ) .   These robots do not obstruct the visibility of any robot in   R   and hence they do not move during whole execution of the algo- rithm. Note that, if   r i   lies outside of   ST R ( r i ) , then  r i   is an external vertex robot.  •   External edge robots ( R EE   ):   A set of robots lying on the edges of   CH ( R ). These robots either block the visibility of external vertex robots or other robot edge robots.   Note that, if   r i   lies on an edge of   ST R ( r i ), then   r i   is an external edge robot.  •   Internal robots ( R I   ):   A set of robots lying inside the   CH ( R ). Note that, if   r i   lies within   ST R ( r i ),   r i   is an internal robot.  3.   ALGORITHM FOR MAKING OF GEN- ERAL POSITION  Consider initially robots in   R   are not in general position. Our objective is to move the robots in   R   in such a way that after a finite number of movements of the robots in   R , it will be in general position.   In order to do so, our approach is to move the robots which create visual obstructions to the other robots.   If a robot   r i   lies between two other robots, say   r p   and   r q   such that   r i ,   r p   and   r q   are in straight line, then   r i   is selected for movement. The destination of   r i , say  T   ( r i ), is computed in such a way that, there always exists a   r j   ∈ R   (where   r j   does not have full visibility), such that when   r i   moves, the cardinality of the set of visible robots of   r j   increases.   Since, the number of robots are finite, the number of robots having partial visibility, is also finite. Our algorithm assures that at each round at-least one robot with partial visibility will have full visibility. This implies that in finite number of rounds all robots will achieve full visibility, hence, the robots will be in general position in finite time.
3.1   Computing the destinations of the robots  A collinear middle robot is selected to move from its po- sition.   A robot finds its destination for movement using algorithm   ComputeDestination ( r i ).   A robot   r i , selected for moving, moves along the bisector of the minimum angle created at   r i   by the robots in   V ( r i ). The destination is cho- sen in such a way that   r i   will not block the vision of any  r j   ∈ V ( r i ), where the vision of   r j   was not initially blocked by   r i , throughout the paths towards its destination.   Each movement of   r i   breaks at least one initial collinearity.  Algorithm 1:   ComputeDestination()  Input :   r i   ∈   R   with   COL ( r i )   6   =   φ .  Output : a point on   Bisec ( r i ). 1. Compute   α ( r i ),   Bisec ( r i ),   β ( r i ),   θ ( r i ),   D ( r i ), 2.   Case 1:   β ( r i )   6   = 0, ∆( r i )   ←   min {   d ( r i )  n 2   , D ( r i ) Sin ( θ ( r i )) }  3.   Case 2:   β ( r i ) = 0, ∆( r i )   ←   D ( r i ) 4. Compute the point ˆ r i   on   Bisec ( r i ), ∆( r i ) distance apart from   r i ; 5. return ˆ r i ;  Proof of Correctness of algorithm ComputeDestina- tion().  Correctness of the algorithm is established by following observations, lemmas. r j  r i  r i − 1   r r +1  r j   r j +1  r i +1  r i  (a)   (b)  r i − 1  Figure 7: An example for lemma 1  Lemma   1.   β ( r i )   ≤   π  3   .  Proof.   If all the robots lie on a straight line, then   β ( r i ) = 0. Suppose there are at least three non-collinear robots. For three robots forming a triangle,   β ( r i ) is maximum when the triangle is equilateral. For all other cases, consider the trian- gle formed by   r i , r j   and   r i − 1   where   r j   is any robot in   V ( r i ) and   r i − 1   is a neighbor of   r i   on   ST R ( V ( r j   )). If   r j   is also a neighbor of   r i   on   V ( r i − 1 ) (Figure 7(a)), then   ∠ r i r j   r i − 1   and  ∠ r i r i − 1 r j   are in Γ ′ ( r i ) and either   ∠ r j   r i r i − 1   or an angle less than it is in Γ( r i ). On the other hand, if   r j   is not a neighbor of   r i   on   V ( r i − 1 ) (Figure 7(b)), then instead of   ∠ r i r i − 1 r j   , an angle less than it, is in Γ ′ ( r i ). In all cases,   β ( r i ) is less than the minimum of the angles of the triangle formed by   r i , r j  and   r i − 1 . Hence,   β ( r i )   ≤   π  3   .  Observation   1.   Maximum value of   DISP   ( r i r j   ) , denoted by   M ax ( DISP   ( r i r j   ) , is attained when   ˆ r i   coincides with one of the tangential points   T   ( C ( r i ) , r j   ) .  Lemma   2.   For any   r i ,   DISP   ( r i r j   )   ≤   θ ( r i )   ∀   r j   .  Proof.   Let   r j   be a robot in   V ( r i ) and   r k   a robot closest to   r i . By observation 1, maximum values of   DISP   ( r i r j   ) and  DISP   ( r i r k   ) are attained at tangential points   T   ( C ( r i ) , r j   ) and   T   ( C ( r i ) , r k   ) respectively.   Hence,   DISP   ( r i r j   ) is less than   π  2   for all   j . By definition, ∆( r i )  | r i r k   |   =   sin ( max ( DISP   ( r i r k   )))  ≤   sin ( θ ( r i ))   (1) Again, ∆( r i )  | r i r j   |   =   sin ( max ( DISP   ( r i r j   )))   (2) Since   | r i r k   |   <   | r i r j   | , from (1) and (2) we have,  sin ( max ( DISP   ( r i r j   )))   ≤   sin ( θ ( r i )) .   (3)  DISP   ( r i r j   ) and   θ ( r i ) are in [0 ,   π  2   ) (by lemma 1) and   sine  is an increasing function in [0 ,   π  2   ]. From (3) we conclude,  DISP   ( r i r j   )   ≤   θ ( r i ) Suppose a robot   r i   ∈ R   moves according to our algorithm. We claim that it will never become collinear with any two robots   r j   and   r k   in   R   where   r i ,   r j   and   r k   are not collinear initially. Now we state arguments to prove our claim.  Observation   2.   Let   ABC   be a right-angled triangle with  ∠ ABC   =   π  2   .   Let   D   be a point on the side   AC   such that  | DC | ≤   1 2   | AC | . Then,  ∠ BDA   ≤   2 ∠ ACB .  Lemma   3.   Suppose   r i   and   r j   move to new positions   ˆ r i  and   ˆ r j   in at most one computation cycle. Let   φ   be the an- gle between   L r i r j   and   L ˆ r i   ˆ r j   i.e.,   φ   =   ∠ r i c ˆ r i   where c is the intersection point between   L r i r j   and   L ˆ r i   ˆ r j   . Then,  φ <   2 Max   { θ ( r i ) , θ ( r j   ) }  Proof.   If any one   r i   and   r j   moves, then lemma is trivially true. Suppose both of them move once.  Case 1:  Suppose   r i   and   r j   move synchronously. Without loss of generality, let ∆( r i )   ≥   ∆( r j   ).  • – Case 1.1:  Suppose   DIR ( r i ) and   DIR ( r j   ) lie in the opposite sides of   L r i r j   (Figure 8). In view of observation 1, Max { φ } , the maximum value of   φ , is attained when   L ˆ r i   ˆ r j   is a common tangent to   C ( r i ) and  C ( r j   ).   Let   M   be the middle point of   r i r j   .   If
ˆ r i  r j  M   c r i  C ( r i )  C ( r j   )  φ  ˆ r j Figure 8: An example of case 1.1 for lemma 3  C ( r i ) is strictly larger than   C ( r j   ),   c   is closer to  r j   than   r i . If they are equal,   c   coincides with   M   . Consider the right-angled triangle   4 r i   ˆ r i r j   .   By observation 2,  φ   ≤   M ax { φ } ≤   2 DISP   ( r i r j   )  <   2 M ax { DISP   ( r i r j   ) } ≤   2 θ ( r i )  – Case 1.2:  If   DIR ( r i ) and   DIR ( r j   ) lie in the same side of  L r i r j   (Figure 9), Max { φ }   is attained when   L ˆ r i   ˆ r j  is a tangent to   C ( r i ) from the point   c   and   c   co- incides with the closest point of   C ( r j   ) from   r i . Then following same argument as in case-1, we have the proof. ˆ r i  r j  M   c r i  C ( r i )   C ( r j   )  ˆ r j  Figure 9: An example of case 1.2 for lemma 3  •   Case 2:  Suppose   r i   and   r j   move asynchronously.   Suppose   r i  is moving and is at   r ′  i   when   r j   takes the snapshot of its surroundings to compute the value of ∆( r j   ). Since  r i   has already computed the value of ∆( r i ) and com- putation of ∆ values of   r i   and   r j   are independent, the proof follows from the same arguments as in case 1. In this case the value of ∆( r j   ) may be different from the value in case 1.  Lemma   4.   Suppose two robots   r i   and   r j   move to   ˆ r i   and  ˆ r j   respectively in at most one movement. Then  M ax { DISP   ( r i   ˆ r j   ) , DISP   ( r j   ˆ r i ) }   <   2 M ax { θ ( r i ) , θ ( r j   ) } .  Proof.   Follows from observation 2 and lemma 3 (Figure 10).  Lemma   5.   If   r i , r j   and   r k   are not collinear and mutually visible to each other, then during the whole execution of the above algorithm, they never become collinear.  Proof.   We have the following cases, ˆ r j  r i  ˆ r i  DISP   ( r i   ˆ r j   )  DISP   ( r j   ˆ r i )  r j  DISP   ( r j   r i )  DISP   ( r i r j   )  Figure 10: An example for lemma 4  •   Case 1 (Only one robot moves):  Without loss of generality, suppose   r j   , r k   stand still and   r i   moves.   If   DIR ( r i ) does not intersect   L r j   r k  (Figure 11(a)), then the claim is trivially true. Suppose   DIR ( r i ) intersects   L r j   r k   (Figure 11(b)). Since distance traversed by   r i   is bounded above by   d ( r i )  n 2   ,   r i  can not reach   L r j   r k   and   r i , r j   and   r k   will not become collinear. r i  r k  r j  r i  r j  r k  DIR ( r i )  DIR ( r i )  (a)   (b)  Figure 11:   An example of case 1 for lemma 5  •   Case 2 (Two of the robots move):  Without loss of generality, suppose   r i   and   r j   move while   r k   remains stationary. This case would be feasi- ble only if   n   ≥   4.  – Case 2.1:  Suppose   r i   and   r j   move synchronously. Then by lemma 2,  DISP   ( r i r k   )   ≤   ∠ r i r k   r j  n 2   (4) And  DISP   ( r j   r k   )   ≤   ∠ r i r k   r j  n 2   (5) From equation 4 and 5  DISP   ( r i r k   ) +   DISP   ( r j   r k   )   <   ∠ r i r k   r j   (6) The minimum value of   DISP   ( r i r k   )+ DISP   ( r j   r k   ) for which   r i , r j   and   r k   could become collinear is  ∠ r i r k   r j   .   In view of equation (6), we conclude that   r i , r j   and   r k   would never become collinear.  – Case 2.2:  Suppose that   r i   is in motion and is at ˆ r i ′   when   r j  computes the value of ∆( r j   ). If ˆ r i ′   and   r j   lie in opposite sides of   L r i r k   (Figure 12(a)), then
r i  r j   r k  ˆ r ′  i  ˆ r ′  i  r i  r j   r k  (a)   (b) Figure 12: An example of case 2.2 for lemma 5  ∆( r j   )   ≤   1  n 2   dist ( r j   ,   L r k   ˆ r i ′   ) which implies that   r j   can not reach   L r i r k   when  r i   reaches its destination and hence the lemma. Suppose ˆ r i ′   and   r j   lie in same side of   L r i r k   (Figure 12(b)). Then we have,  DISP   ( r i r k   )   ≤   ∠   ˆ r i ′ r k   r j  n 2  <   ∠   ˆ r i r k   r j  n 2  Lemma follows from the same arguments as used in Case 2 . 1. Consider the case: suppose   r j   takes the snapshot at time   t   and moves to its destination at time   t ′ . In between times   t   and   t ′ , suppose   r i   has made at most   n − 1 2   moves (we shall prove in case 3.2 that number of movements of any robot is bounded above by   n − 1 2   ). If   r i   moves towards   r j   , after   n − 1 2  moves, we would have  DISP   ( r i r j   )   <   (1   −   1  n 2   )   n − 1 2   ∠ r i r k   r j  which is less than (1   −   1  n 2   ) ∠ r i r k   r j   . Hence equa- tion (6) is satisfied in this case and we have the proof of the lemma.   If   r i   moves away from   r j   , then there is nothing to prove.  •   Case 3 (All three robots move): – Case 3.1:  Suppose   r i , r j   and   r k   move synchronously.  – Case 3.1.1:  Suppose   L ˆ r i   ˆ r j   intersects   L r i r j   at an angle   φ >   0 (Figure 13). ψ  φ  r i  r k r j  ˆ r j  A  B  C  ˆ r i  Figure 13: An example of case 3.1.1 for lemma 5  By lemma 3,  φ <   2 M ax { θ ( r i ) , θ ( r j   ) } ≤   2  n 2   ∠ r i r j   r k   (7) In   4 ABr j   ,  ψ   =   ∠ r i r j   r k   −   φ >   ∠ r i r j   r k   −   2  n 2   ∠ r i r j   r k  =   n   −   2  n 2   ∠ r i r j   r k  ≥   3 5 2   ∠ r i r j   r k   (8) Now   r i ,   r j   and   r k   would be collinear only if  DISP   ( r k   B ) =   ψ   (9) From lemma 4,  DISP   ( r k   B )   < DISP   ( r k   ˆ r j   )  <   2 M ax { θ ( r i ) , θ ( r j   ) } ≤   2 5 2   ∠ r i r j   r k   (10) Equations 8, 9 and 10 imply that   r i ,   r j   and   r k   do not become collinear.  – Case 3.1.2:  Suppose   L ˆ r i   ˆ r j   and   L r i r j   are parallel i.e.,   φ   = 0 which implies that   ψ   =   ∠ r i r j   r k   (Figure 14). Let  Bisec ( r k   ) intersect   L r i r j   at   P   and   | r k   P   |   =   l . Since ∆( r k   )   ≤ | r i r j   | sin (   ∠ r i r j   r k  n 2   ) and   n   ≥   5, r i  ˆ r i  r j  ˆ r j  r k  Bisec ( r k )  P  Figure 14: An example of case 3.1.2 for lemma 5  l   −   ∆( r k   )   ≥ | r i r j   | sin ( ∠ r i r j   r k   )   −   ∆( r k   )  ≥ | r i r j   | sin ( ∠ r i r j   r k   )   − | r i r j   | sin (   ∠ r i r j   r k  n 2   )  ≥ | r i r j   | ( sin ( ∠ r i r j   r k   )   −   sin (   ∠ r i r j   r k  5 2   ))  >   | r i r j   | sin (   ∠ r i r j   r k  5 2   )   (11) ∆( r i ) and ∆( r j   ) are bounded above by   | r i r j   | sin  (   ∠ r i r j   r k  5 2   ). Hence by equation (11),   r i   and   r j   and  r k   do not become collinear.  •   Case 3.2:  Suppose   r i ,   r j   and   r k   move asynchronously. The main problem in this case is the following scenario: suppose
r j   or   r k   takes the snapshot at time   t j   or   t k   respectively and starts moving to its computed destination at time  t ′  j   or   t ′  k   respectively.   Suppose the configuration has been changed in between the times due to the move- ments of the other robots. Then the corresponding ∆ value of   r j   or   r k   is not consistent w.r.t.   the current configuration.   We have to show that this would not create any problem for our algorithm. The main idea of proof in this case is that we have to estimate the maximum amount of inclination of   L r i r j   towards   r k  between the times   r j   or   r k   takes the snapshot of sur- roundings and it reaches the destination.   So, in the following proofs we only consider the scenarios (as in the case 3.1.1. and case 3.1.2) in which there are pos- sibilities of maximum reduction in the   ∠ r i r j   r k   , which depicts the inclination of   L r i r j   towards   r k   . Note that the inclination of   L r i r j   towards   r k   is maximum when both   r i   and   r j   move synchronously. So, we only prove the case when   r k   holds the old value of ∆.  •   Case 3.2.1  Suppose   r k   holds the old value of ∆ w.r.t. to the cur- rent configuration.   Suppose   r i   and   r j   are at   r 0  i   and  r 0  j   respectively when   r k   takes the snapshot at time   t k   . Suppose till   t ′  k   ,   r i   and   r j   move   x   and   x ′   times respec- tively.   Note that initially   r i   and   r j   can be collinear with   n   −   1 robots and to remove these collinearity they have to move at most   n − 1 2   times if they do not create any new collinearity (this bound is obtained by con- sidering the degenerate case i.e., when all the robots are collinear initially). First we prove that   x   and   x ′   are bounded above by  n − 1 2   . To prove this we show that   r i   and   r j   do not cre- ate any new collinearity while moving. We prove this for arbitrary robots.   Suppose some robot   r s , while moving, creates a new collinearity with   r l   and   r m   for the first time during the execution of our algorithm (Figure 15).   Then either one of   r l   and   r m   or both r s  r l  r m  Figure 15: An example of case 3.2.1 for lemma 5  have ∆ values w.r.t. old configurations. As stated ear- lier we only prove the case in which only one robot, say   r m , has old ∆ value.   r m   computes ∆( r m ) at the time   t m   i.e., ∆( r m )   ≤   1  n 2   ∠ r s r l r m .  Suppose   r m   does not move till time   t ′  m . The number of times   r s   and   r l   move to break the initial collinearities before time   t ′  m   is upper bounded by   n − 1 2   .   r m   would become collinear with   r s   and   r l   when   L r s   r l   would be inclined enough towards   r m   so that by moving a ∆( r m ) amount it would reach this straight line.   We try to estimate the inclination of   L r s r l   towards   r m   (which is depicted by the angle   ψ   as in the case 3.1.1.   and by the displacement of   L r s r l   towards   r m   as in the case 3.1.2.)   after   n − 1 2   number of movements of   r s   and   r l  (note that we have consider the over estimated value of the number of movements of   r s   and   r l ). As computed in the case 3.1.1, after first movement,  ψ >   (1   −   1  n 2   ) ∠ r s r l r m  and   ∠ r s r l r m   will become at most (1+   1  n 2   ) ∠ r s r l r m . By the same repeated arguments, we can say that after   d  movements  ψ >   (1   −   1  n 2   ) d ∠ r s r l r m  which is strictly greater than   1  n 2   ∠ r s r l r m   for   d   ≤   n − 1 2   . This contradicts the fact that   r s   creates collinearity with   r l   and   r m .   For the scenario same as the case 3.1.2., we have,  | r l r m | sin ( ∠ r s r l r m )   −   n   −   1 2   | r l r m | sin (   ∠ r s r l r m  n 2   )   >  | r l r m | sin (   ∠ r s r l r m  n 2   ) (12) This also contradicts the fact that   r s   creates collinear- ity with   r l   and   r m . Hence, we conclude that   r s   would not become collinear with   r l   and   r m . In the above proof, we replace   r s ,   r l   and   r m   by   r i ,  r j   and   r k   respectively to conclude that   r i   would not become collinear with   r j   and   r k   during the whole ex- ecution of our algorithm.  Lemma   6.   Consider any two robots   r i   and   r j   .   r i   does not cross   Bisec ( r j   ) . r k  r j   r i  a   b  p  Figure 16: An example for lemma 6  Proof.   If   Bisec ( r i ) and   Bisec ( r j   ) do not intersect, then there is nothing to prove. Suppose   Bisec ( r i ) and   Bisec ( r j   ) intersect at a point   p   (Figure 16). If at least one of   intersect ( r i ) and   intersect ( r j   ) is closer to   r i   and   r j   respectively than   p , then we are done.   Else   α ( r i ) and   α ( r j   ) are angle of same triangle   4 r i r j   r k   for some   r k   ∈ R   i.e,   α ( r i ) =   ∠ r k   r i r j   and  α ( r i ) =   ∠ r k   r j   r i .   In   4 r i r j   r k   , let   Bisec ( r i ) and   Bisec ( r j   ) intersect   r j   r k   and   r i r k   at   a   and   b   respectively. Here   n >   5.
In   4 ar j   p ,  | ap |   =   sin (   ∠ r k   r j   r i  2   )   | r j   a |  sin ( ∠ apr j   )   (13) In   4 pr i r j   ,  | pr i |   =   sin (   ∠ r k   r j   r i  2   )   | r i r j   |  sin ( ∠ π   −   apr j   ) =   sin (   ∠ r k   r j   r i  2   )   | r i r j   |  sin ( ∠ apr j   )   (14) From equation 13 and 14,  | ap | | pr i |   =   | r j   a | | r i r j   |   (15) Since   | r j   a |   <   | r i r j   | ,   | ap |   <   | pr i |   which implies, ∆( r i )   <   | r i a |  5 2  <   | pr i | . Hence   r i   can not cross   Bisec ( r j   ). Similarly,   r j   can not cross  Bisec ( r i ).  Lemma   7.   Suppose, for any robot   r i   ∈ R ,   r k   / ∈ V ( r i ) . Then during the whole execution of the algorithm   r i   will not block the vision between   r j   and   r k   where   r j   ∈ V ( r k   ) . r j   r ′  j  r i  r ′  l  r l r k  Figure 17: An example for lemma 7  Proof.   Let   r j   ∈ V ( r i )   ∩ V ( r k   ). Suppose   r l   be the near- est robot of   r i   such that   r k   lie on   L r i r l   (Figure 17).   If  Bisec ( r i ) does not intersect   r j   r l , there is no possibility that  r i   will block the vision between   r j   and   r k   .   Let   Bisec ( r i ) intersect   r j   r l . Then   r j   is one of the immediate neighbor of  r l   on   ST R ( V ( r i )).   Let   r ′  j   and   r ′  l   be the other immediate neighbors of   r j   and   r l   respectively on   ST R ( V ( r i )).   First we prove that   r i   will always lie on the same side of   L r j   r l  as it is initially even if   r i ,   r j   ,   r k   and   r j   move.   By lemma 6 and the observation that the movements of   r i ,   r j   ,   r l   are bounded by the edges and chords of the polygon formed by  { r j   , r l , r ′  l , r i , r ′  j   } , we conclude   r i   never crosses the line   L r j   r l   . To block the vision between   r k   and   r j   ,   r i   has to move on the line segment   r k   r j   .   Since   r i   and line segment   r j   r k   lies on different sides of   L r j   r l   ,   r i   will never block the vision be- tween   r k   and   r j   . Let   r j   / ∈ V ( r i ) .   Then there is a robot   r m  which creates visual obstruction between   r i   and   r j   . Now the movement of   r i   is bounded by the line   L r l   r m   and hence the lemma.  Lemma   8.   If at any time   t ,   r j   ∈ V ( r i ) , then at   t ′ ( > t ) ,  r j   ∈ V ( r i )   even if   r i   changes its position.  Proof.   The proof is immediate from 5 and 7.  Lemma   9.   Cardinality of   V ( r i )   is strictly increasing.  Proof.   Lemma 5, 7 and 8 imply the proof.  Lemma   10.   There exist at least two robots   r j   , r k   ∈ R   for which   V ( r j   )   and   V ( r j   )   increase whenever   r i   changes its po- sition.  Proof.   r i   moves whenever   r i   is collinear with at least one pair of robots, ( r j   ,   r k   ), and   r i   lies in between those robots.   If   r j   and   r k   do not move then   V ( r j   ) and   V ( r k   ) increase whenever   r i   moves because no robot can reach   r j   r k  due to the facts stated in lemma 5 and 7.   When either   r j  or   r k   or both   r i   and   r k   moves, one member of   COL ( r j   ) and one member of   COL ( r k   ) can see each other. Hence the lemma.  3.2   Moving the robots to obtain general posi- tion  Next we will discuss the algorithm   M akeGenaralP osition (), by which the robots in   R   move to obtain full visibility. The robots in   R I   which create obstacle to other robots and the robots in   R EE   are eligible for movement by this algorithm. The robots compute destinations using   ComputeDestination () and move towards it. The robots keep on executing the al- gorithm till there exist no three collinear robots in   R .  Algorithm 2:   MakeGenaralPosition()  Input :   R , a set of robots with their positions.  Output :   ˆ R , which is in general position.  while   r i   ∈   R EE   ∨   ( r i   ∈   R I   ∧   COL ( r i )   6   =   φ )   do  1.   T   ( r i )   ←   ComputeDestination ( r i ); 2. Move to   T   ( r i ); 3. Compute   COL ( r i );  Proof of Correctness of algorithm MakeGenaralPo- sition().  The algorithm assures that the robot will form general position in finite number of movements.   The termination of the algorithm is established by following observation and lemmas.  Observation   3.   ComputeDestination   is not executed by a robot   r l   ∈   R   if   r l   ∈   R EV   ∨   ( R I   ∧   COL ( r l ) =   φ ) .  Lemma   11.   COL ( r i )   will be   φ   in finite time.  Proof.   In the initial configuration the number of robots in   COL ( r i ) is upper bounded by   n   −   1.   During the whole execution of our algorithm no new collinearity is created and for each iteration cardinality of   COL ( r i ) is reduced by at least two. Hence after at most   n − 1 2   number of iterations of the while loop in the above algorithm,   COL ( r i ) will become null.  Lemma   12.   ∀ r i ,   V ( r i )   will be   ( n   −   1)   in finite number of execution of the cycle.
Proof.   Let   η   =   |   ⋃ n i =1   V ( r i ) | . The algorithm for a robot  r i   terminates whenever   |V ( r i ) |   reaches the value   n − 1. Hence the algorithm for all robots terminates when   η   =   n ( n − 1) 2  which is a finite integer.   By lemma 9 and 10 the value of  η   increases whenever any robot moves.   Hence after finite number of execution cycles   η   reaches its maximum value  n ( n − 1) 2   . From the above results, we can conclude the following theorem:  Theorem   1.   A set of asynchronous, oblivious robots (ini- tially not in general position) without agreement in common chirality, can form general position in finite time.  4.   CONCLUSION  In this paper we have presented an algorithm for obtain- ing general position by a set of autonomous, homogeneous, oblivious, asynchronous robots having no common chirality. The algorithm assures the robots to have collision free move- ments. Another important feature of our algorithm is that the convex hull made by the robots in initial position, re- mains intact both in location and size. In other words, the robots do no go out side the convex hull formed by them. This feature can help in many subsequent pattern forma- tions which require to maintain the location and size and of the pattern. Once the robots obtain general position,   the next job could be to form any pattern maintaining the general po- sition.   Most of the existing pattern formation algorithms have assumed that the robots are see through.   Thus, de- signing algorithms for forming patterns by maintaining gen- eral position of the robots, may be a direct extension of this work.  5.   REFERENCES  [1] C. Agathangelou, C. Georgiou, and M. Mavronicolas. A distributed algorithm for gathering many fat mobile robots in the plane. In   Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC) , 250–259, 2013. [2] G. Antonio Di Luna, P. Flocchini, S. Gan Chaudhuri, N. Santoro, and G. Viglietta. Robots with Lights: Overcoming Obstructed Visibility Without Colliding In  Proc. 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS’14) , to appear. [3] G. Antonio Di Luna, P. Flocchini, F. Poloni” N. Santoro, and G. Viglietta. The Mutual Visibility Problem for Oblivious Robots. In   Proc. 26th Canadian Conference on Computational Geometry (CCCG’14) , to appear. [4] 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. [5] R.Cohen and D.Peleg. Local spreading algorithms for autonomous robot systems.   Theoretical Computer Science , 399:71–82, 2008. [6] J. Czyzowicz, L. Gasieniec, and A. Pelc. Gathering few fat mobile robots in the plane.   Theoretical Computer Science , 410(6ˆ a7):481 – 499, 2009. [7] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The power of lights: Synchronizing asynchronous robots using visible bits. In   Proceedings of the 32nd International Conference on Distributed Computing Systems (ICDCS) , 506–515, 2012. [8] 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. [9] 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. [10] P. Flocchini, G. Prencipe, and N. Santoro.   Distributed Computing by Oblivious Mobile Robots . Morgan & Claypool, 2012. [11] 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 Information and Communication Complexity (SIROCCO) , 189–200, 2013. [12] 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. [13] 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 (ALGOSENSORS) , 291–306, 2013.