Pattern Formation for Asynchronous Robots without Agreement in Chirality  Sruti Gan Chaudhuri 1 , Swapnil Ghike 2 , Shrainik Jain 3   and Krishnendu Mukhopadhyaya 4  1   Information Technology, Jadavpur University, Kolkata - 700032, India. Email: srutigan@gmail.com  2   LinkedIn, Mountain View, CA - 94043, USA. email: swapnil.ghike@gmail.com  3   University of Washington, USA, email: shrainik@gmail.com  4   ACM Unit, Indian Statistical Institute, Kolkata - 700108, India. Email: krishnendu@isical.ac.in  Abstract  This paper presents a deterministic algorithm for forming a given asymmetric pattern in finite time by a set of   autonomous ,   homogeneous ,   oblivious   mobile robots under the CORDA model. The robots are represented as points on the 2D plane. There is no explicit communication between the robots. The robots coordinate among themselves by observing the positions of the other robots on the plane.   Initially all the robots are assumed to be stationary.   The robots have local coordinate systems defined by Sense of Direction (SoD), orientation or chirality and scale. Initially the robots are in asymmetric configuration. We show that these robots can form any given asymmetric pattern in finite time.  Keywords:   Asynchronous, oblivious, mobile robots, pattern formation, chirality.  1. Introduction  Executing a collaborative task by a set of small, autonomous, mobile robots (also known as   robot swarm   [18]) has been a popular topic for the research for last few decades. The robots are assumed to be anonymous, homogeneous, oblivious and asynchronous. The robots together perform a complex job, e.g., moving a big body [16], cleaning a big surface [13] etc. The individual unit or robot in a system of swarm robots is less expensive than a big robot. Increasing or decreasing the number of robots in this system involves very simple hardware or software modifications and thus provides good scalability. Moreover, having similar capability, if some robots fail, others can manage to execute the work. This feature makes the system to be more resilient to malfunction.   In hostile environments, these robots are easily deployable to perform various complex tasks cooperatively.  Preprint submitted to Elsevier   October 14, 2018  arXiv:1403.2625v1 [cs.DC] 11 Mar 2014
An important task for a set of mobile robots is   pattern formation   [22].   A set of robots is required to arrange themselves on a 2D plane to form a pattern, in finite time.   The robots are considered as points.   Initially all robots are at distinct positions on the 2D plane. If the robots can form any pattern, they can agree on their subsequent roles in future coordinated action. In this paper we propose a deterministic distributed algorithm for a given asymmetric pattern formation by a set of asynchronous mobile robots.  1.1. Earlier Works  An extensive volume of research [1, 2, 3, 5, 7, 9, 12, 14, 15, 17, 20] has been reported in the context of multiple autonomous mobile robots exhibiting coop- erative behavior for the swarm robots. Many of them are based on geometric pattern formation. There exists several algorithms for forming specific patterns such as circle [4], straight line [21] etc. Arbitrary pattern formation is a general case of pattern formation. The pattern is usually given as an input described either in the form of a set of points expressed by their mutual distances and angles, or as geometric figures like polygon, circle, straight line etc. A complete characterization of the class of formable patterns [23, 24, 25] has been reported for the robots under Sync and SSync model and also when the robots have an unbounded amount of memory. Flocchini et al. [6, 8, 9] investigated arbitrary pattern formation problem for asynchronous and oblivious robots for different cases where robots may or may not have common SoD and/or chirality. With common SoD and common chirality any pattern is formable for any number of robots [8]. With common SoD and without common chirality any pattern may be formed with odd number of robots [6]. If the number of robots is even, they can form   symmetric patterns   [6].   Without common SoD, the robots can not form an arbitrary pattern even if they agree on chirality [8]. They also showed that without common SoD, a set of initial configurations, known as   symmetric configurations , exists, for which it is impossible to form an arbitrary pattern [9]. Ghike and Mukhopadhyaya [11] presented a deterministic algorithm for a given pattern formation without SoD and Chirality. Their solution finds collision free paths for the robots. In order to achieve this, some robots are selected for mov- ing at a time. However, their solution assumed that no tie occurs when a robot is selected for movement. They also assumed that the robots on the Smallest Enclosing Circle (SEC) of the robots are less than or equal to the number of robots inside the SEC. In this paper we propose algorithms for arbitrary pattern formation for points robots which eliminates these limitations in [11].  2. Overview of the problem  This paper presents an algorithm for formation of arbitrary asymmetric pat- terns by point robots under the CORDA model. The features of the robots are described as follows:  •   Robots are autonomous, anonymous and homogeneous in the sense that they are not uniquely identifiable, neither with a unique identification number nor with some external distinctive mark (e.g., color, flag, etc.). 2
•   They are represented as points on the 2D plane. Robots have no common coordinate system.   Each robot uses its own local coordinate system de- fined by its origin, Sense of Direction (SoD), orientation or chirality and scale or unit distance.   A robot has no knowledge about the coordinate system of any other robot.  •   Robots can not communicate explicitly. Each robot has a camera/sensor which can take picture or sense over 360 degrees. The robots communicate only by means of observing other robots using the camera/sensor. A robot can compute the coordinates (w.r.t. its own coordinate system) of other robots by observing through the camera/sensor.  •   Robots have infinite visibility range , i.e., a robot can see all other robots.  •   Robots execute the cycle ( Wait-Look-Compute-Move ) asynchronously. A robot does nothing in   Wait   state.   In   Look   state, it gets the positional information of other robots by observing its surroundings.   In   Compute  state it computes a destination point to move to. Finally in   Move   state, it moves to the computed destination along a straight line.  •   Under the CORDA model [19], the movement of the robots is not instan- taneous. While in motion, a robot may be observed by other robots. A robot may also stop before reaching its destination.  •   Robots are oblivious. They do not retain the information from the previ- ous cycles.  •   Initially all robots are stationary. Let  ̄ r   =   { r 1 , r 2 , . . . , r n }   be a set of robots.   Initially,  ̄ r   is assumed to be in asymmetric configuration [10] 1 . Our algorithm finds collision free paths (non- intersecting paths) for all the robots such that finally the robots form the given pattern. A pattern   P   is defined by a set of   n   points represented by their coordinate values with respect to an arbitrary coordinate system. i.e.,   P   =   { ( x i , y i ) : 1   ≤  i   ≤   n } . Formally the problem is stated as follows:  Problem 1.   We are given a set of robots    ̄ r   which are in asymmetric configu- ration and an asymmetric pattern   P . The robots in    ̄ r   have to move themselves to form   P   in finite time.  3. Solution approach  This section gradually builds an algorithm to form the input pattern   P   by the robots in  ̄ r . The pattern formation algorithm has multiple sub-algorithms. We describe them one by one.  1 In asymmetric configuration there exists no straight line which divides the set of robots into two halves such that one half is the mirror image of the other.  3
3.1. Agreement in coordinate system  An important issue in the problem is representation of the given pattern. The pattern, given, is defined by an arbitrary coordinate system and the robots interpret it in their own coordinate system. An agreement in coordinate system with respect to the given pattern is found such that the representation of the pattern is same for all the robots.   AgreementPattern()   does this job. First the   SEC   of   P   is constructed. Let   c P   be the center of the   SEC .   c P   becomes the common origin, for the pattern. We fix an ordering   Ord ( P ) for the point in  P . A point,   p l   ∈ P , is selected so that it is the first point on the   SEC   of   P , in  Ord ( P ).  Lemma 1.   It is possible to elect a leader   p l   ∈ P   such that   p l   is on the   SEC   of  P . Proof:   P   is asymmetric and hence orderable.   If we fix an ordering and from that ordering choose the first point that is on the   SEC   of   P , we shall have a leader lying on the   SEC   of   P .     | c P   p l |   is the common unit distance,   − − → c P   p l   is the common positive   X   axis for the pattern. Let   p ′  l   ∈ P   be a point on   SEC , which is presented next to   p l   in  Ord ( P ).  Lemma 2.   It is possible to select a point   p ′  l   ∈ P , different from   p l , such that  p ′  l   is on the   SEC   of   P . Proof:   P   is asymmetric and hence orderable.   If we fix an ordering and from that ordering choose the first non leader point,   p ′  l , such that it does not lie on  c P   p l . Since, the SEC contains at least two points existence of such a point is guaranteed.     The side of   X   axis where   p ′  l   lies is considered as the side of the common positive   Y   axis for the pattern. Note that the algorithm   AgreementPattern()  also normalizes the pattern by representing the radius of the   SEC   as the unit distance.  Algorithm 1 : AgreementPattern()  Input :   P : the set of pattern points.  Output :   A common center, unit distance and axes of   P . Compute   SEC   of   P ;   c P   ←   center of   SEC ;  Ord ( P )   ←   ordering of   P ;  p l   ←   the first point from   SEC   in   Ord ( P ); +ve   X   axis   ←   c P   p l ;  p ′  l   ←   a point next to   p l   in   Ord ( P ) such that it does not lie on   c P   p l ; +ve   Y   axis   ←   the perpendicular of   c P   p l , drawn at   c P   , at that side of +ve  X   axis, where   p ′  l   lies; Return   c P   as center,   | c P   p l |   as unit distance, +ve   X   and +ve   Y   ; 4
Correctness of AgreementPattern():.   The correctness of the algorithm fol- lows from lemma 3.  Lemma 3.   The origin, unit distance and axes are uniquely defined by   Agree- mentPattern() . Proof:   SEC   of   P   is unique. Hence,   c P   , i.e., the origin is unique. Lemmas 1 and 2 ensure that,   p l   and   p ′  l   are unique. Hence, orientation of the axes (+ve   Y   axis w.r.t. the +ve   X ) are unique.     Using algorithm   AgreementCoordinateSystem() , the robots plot   P   in their local coordinate systems and fix common origin, axes and scale.   The pattern formation algorithm is designed in such a way that, the agreement in coordinate system remains unchanged till the formation of   P   by  ̄ r   is complete. Algorithm   AgreementCoordinateSystem()   first computes the   SEC   of  ̄ r . Let   c  ̄ r   be the center of the   SEC . An ordering   Ord ( ̄ r ) is fixed for  ̄ r . The first robot,   r l , in   Ord ( ̄ r ), which is lying on   SEC   of  ̄ r , is selected as leader.  Lemma 4.   It is possible to select an   r l   ∈    ̄ r   from   SEC   of    ̄ r . Proof:   Since,  ̄ r   is in asymmetric configuration, it is orderable.   If we fix an ordering,   r l   may be chosen as the first robot in that ordering which lies on the  SEC   of  ̄ r .     P   is plotted so that   c  ̄ r   =   c P   and   r l   =   p l .   c  ̄ r   becomes the common origin, denoted by   O .   c P   p l   or   c  ̄ r   r l   becomes the positive   X   axis. The positive   Y   axis for  P   is the common positive   Y   axis for the robots.   | c  ̄ r   r l |   =   | c P   p l |   is the common unit distance, denoted by   u . The other points in   P   are plotted accordingly.   P∗  is the set of the coordinate values of the pattern points computed in the defined 5
coordinate system.  Algorithm 2 : AgreementCoordinateSystem()  Input :  ̄ r : the set of robots,   P : the set of pattern points.  Output :   O : Common origin,   XY   axes,   u : unit distance for the robots in  ̄ r , and   P∗ : set of coordinates of the pattern points. Compute   SEC   of  ̄ r ;  c  ̄ r   ←   Center of   SEC   of  ̄ r ;  Ord ( ̄ r )   ←   an ordering of  ̄ r ;  r l   ←   first robot in   Ord ( ̄ r ); AgreementPattern(); Plot   P   such that:  O   ←   c  ̄ r   ←   c P   ;  r l   ←   p l ;  u   ← | Or l | ; +ve   X   axis for  ̄ r   ←   c  ̄ r   r l ; +ve   Y   axis for  ̄ r   ←   +ve   Y   axis for  ̄ r ; Compute all pattern points in   P ;  P∗ ←   set of coordinates of the pattern points; Return   O , +ve   X   and   Y   for  ̄ r ,   u ,   P∗ ;  Correctness of AgreementCoordinateSystem():.   Algorithm   Agreement- CoordinateSystem()   ensures that all robots agree on the orientation and scale of pattern to be formed. The correctness of the algorithm follows from lemma 5.   Since the coordinate system has been uniquely defined for  ̄ r , we can state the following lemma.  Lemma 5. AgreementCoordinateSystem()   computes the coordinate val- ues of all pattern points in   P   uniquely and the computation is invariant of the position of the robots in    ̄ r . 3.2. Pattern formation  Note that, the algorithms described so far do not require any robot to move. Once a robot fixes the coordinate axes and the pattern points, it is ready to move. However, the movements are designed in such a way that a robot that starts late will have the same coordinate system. This is ensured by maintaining the   SEC   of the robots and the leader in the initial configuration remains the leader.   The formation of pattern   P   by the robots in  ̄ r   is carried out through the following steps:  •   Step 1.   If   O / ∈ P∗   and   ∃   a robot   r 0   at   O , then   r 0   moves by distance   < d   (where   d   is the distance of a nearest robot not at   O , from   O ) in the direction of positive   X   axis.  •   Step 2.   If   O   ∈ P∗   and   @   a robot at   O , a robot nearest to   O   moves to   O . Tie, if any, is broken using   Ord ( ̄ r ). 6
•   Step 3.   Let   p 1   be the pattern point nearest to   O   (if there are many, we choose the first one in   Ord ( P )).   r 1   is the robot nearest to   O   (if there are many, we choose the first one in   Ord ( ̄ r )). Let   d   =   max ( | Or 1 | ,   | Op 1 | ). The robots which lie inside or on   Cir ( O, d ), move radially to a distance   d   +     from   O .  •   Step 4.   r 1   moves to   p 1 .  •   Step 5.   If   ∃   free pattern points in   P∗   on the   SEC , they are filled as follows:  –   If   ∃   free robots inside   SEC , then these robots move to fill the points in   P∗   on the boundary of the   SEC .  –   Else, robots on the   SEC   move to occupy free   P∗   on   SEC   (without changing   SEC   itself).  •   Step 6.   The rest of the robots which are not in position in   P∗   move to occupy the free points in   P∗ . Algorithm   MoveRadiallyOut( r i )   executes the 3 rd   step of the above list of operations. This algorithm also assures that there will be no collision between robots during movements.   The algorithm assumes that the robots agree in coordinate system (using   AgreementCoordinateSystem() ).  Algorithm 3 : MoveRadiallyOut( r i )  Input :  ̄ r : the set of robots,   P : the set of pattern points.  Output :   A new configuration for the robots such that the executing robot lies at a distance   d   +      from   O . Find   r 1   and   p 1 ;  d   ←   max ( | Or 1 | ,   | Op 1 | );  ̄ r ′   ← { r k   ∈    ̄ r : s.t.   r k   lies inside   Cir ( O, d ) } ; Compute   Ord ( ̄ r );  r i   ∈    ̄ r ′   ←   robot nearest to the boundary of   Cir ( O, d   +    ) (in case of tie use   Ord ( ̄ r ));  h   ←   intersection of   Or i   and   Cir ( O, d   +    );  if   h   is not occupied by any robot   then  r i   moves to   h ;  else  g   ←   a point at a side of   h   which is not occupied by other robot and  ∠ gr i h   ≤   90 o ;  r i   moves to   g ;  Correctness of MoveRadiallyOut( r i ):.   The correctness of the algorithm is established by lemma 6.  Lemma 6. MoveRadiallyOut( r i )   ensures collision free movement of the robots.  7
Proof:   MoveRadiallyOut( r i )   checks if the robot executing the algorithm is inside the circle of radius   d . If the robot is inside the circle, then it moves     distance radially outward. To do so, first the robot nearest to the boundary of  Cir ( O, d   +    ) is identified. There may be more than one such robots. In order to avoid possible collisions between robots the algorithm selects one robot for moving. The robot which is nearest to the boundary of   Cir ( O, d   +    ) and comes first in   Ord ( ̄ r ) is selected for moving. After selecting the robot for movement, the algorithm finds the destination for movement. The destination is selected in such a way that, it is not already occupied by other robots.   Robots being points, a point, not occupied by other robot, will always exist on the boundary of   Cir ( O, d +  ). Moreover, during the movement towards destination, the robot remains nearest to the boundary of   Cir ( O, d   +    ).   Thus collisions with other robots are avoided.     MoveRadiallyOut( r i )   also makes sure that all robots lie in the annular region between the SEC and   Cir ( O, d ). This also ensures that the subsequent movement   r 1   to   p 1   in step 4 is collision free. Now we describe algorithm   MoveToDestination( r i )   which finds destina- tions for each robot in  ̄ r , such that the paths of the robots to their respective destinations are collision free. The algorithm assumes that the robots agree in 8
coordinate system (using   AgreementCoordinateSystem() ).  Algorithm 4 : MoveToDestination( r i )  Input :  ̄ r : the set of robots,   P : the set of pattern points.  Output : Destination for each robot in   P∗ .  F reeP   ← { p j   ∈ P∗ :   p j   is not occupied by any robot } ;  F ree  ̄ r   ← { r j   ∈    ̄ r :   r j   / ∈ P∗} ;  S ← { ( | Or j   | ,   ∠ r j   Op k ) :   r j   ∈   F ree  ̄ r, p k   ∈   F reeP   } ; Let ( | Or 0 | ,   ∠ r 0 Op 0 ) be the lexicographic minimum of   S ;  d ′   ← | Op 1 | ;  if   r i   6   =   r 0   then  Destination   ←   null ;  else if   r 0 p 0   does not intersect   Cir ( O, d ′   +    )   then if   no other robots lie on   r 0 p 0   then  Destination   ←   p 0 ;  else  Saf eRegion   ←   the part of the region inside the   SEC   but outside   Cir ( O, d ′   +    ) that lies between   − − →  Or 0   and   − − →  Op 0   s.t.  ∠ r 0 Op 0   ≤   180 o ;  d 0   ←   a point in   Saf eRegion , s.t. there exists no robots on  d 0 p 0 ;  Destination   ←   d 0 ;  else  Find   T   1  r 0   ,   T   2  r 0   , the tangents from   r 0   to   Cir ( O, d ′   +    ) at points   t 1  r 0  and   t 2  r 0   respectively ; Find   T   1  p 0   ,   T   2  p 0   , the tangents from   p 0   to   Cir ( O, d ′   +    ) at points   t 1  p 0  and   t 2  p 0   respectively;  K ←   the set of points of intersection of   T   i r 0   , T   j p 0   for 1   ≤   i, j,   ≤   2; Find   d 1   ∈ K   s.t.   | r 0 t i r 0   | + | p 0 t j p 0   |   is minimum, for 1   ≤   i, j,   ≤   2;  if   no robot lies on   r 0 d 1   (excluding point   d 1   itself )   then  Destination   ←   d 1 ;  else  Saf eRegion   ←   the part of the region inside the   SEC   but outside   Cir ( O, d ′   +    ) that lies between   − − →  Or 0   and   − − →  Op 0   s.t.  ∠ r 0 Op 0   ≤   180 o ;  d 0   ←   a point   ∈   Saf eRegion , s.t. there exists no robots on  d 0 d 1 ;  Destination   ←   d 0 ;  r i   moves to   Destination ;  Correctness of MoveToDestination( r i ):.   The correctness of the algorithm is established by lemma 7. 9
Lemma 7.   Algorithm   MoveToDestination( r i )   ensures collision-free move- ments of all robots to their final positions in finite time, without affecting the agreement on coordinate system. Proof:   The movement of robots in   F ree  ̄ r   to final positions in   F reeP   , is designed in such a way that only one robot at a time moves (Figure 1). No robot in   F ree  ̄ r   gets closer to   O   than   r 1 , which is already is at   p 1 . The algorithm selects a pair ( r 0   ∈   F ree  ̄ r ,   p 0   ∈   F reeP   ) such that   ∠ r 0 Op 0   is minimum. If the line   r 0 p 0  does not intersect   Cir ( O, d ′   +    ), then   r 0   moves to   p 0 .   Else, if the line   r 0 p 0  intersects   Cir ( O, d ′   +    ), then   r 0   travels through the tangents of   Cir ( O, d ′   +    ), while ensuring that the path to   p 0   is the shortest. This is achieved by computing a point   d 1 , s.t.   d 1   is the intersection of tangents from   p 0   and   r 0   to   Cir ( O, d ′   +    ) and the distance from   r 0   to   p 0   via   d 1   is minimum.   r 0   then moves towards   d 1 . Since,   r 0 ’s last move was along   r 0 d 1   towards of   d 1 , one of the following may happen:   (i) no robot takes snapshot till   r 0   reaches   d 1 ; (ii) other robots take snapshot during the movement of   r 0   along   r 0 d 1 . In situation (ii), a robot which takes snapshot, will find   r 0   at a point   a   on   r 0 d 1 , other than   d 1 . ( aO,   ∠ aOp 0 ) remains minimum during this movement. Hence,   r 0   will again be selected for movement. SEC  Circle ( O, d   +    )  O r 0   p 0  d 1  a   d ′  1  6  r 0 Op 0   decreases during the movement of   r 0 ;  even if a robot takes a snapshot when   r 0   is at   a  r 0   will again be selected for movement  Figure 1: An Example execution of MoveToDestination( r i )  The movement of   r 0   does not result in any other robot getting closer to   p 0  than   r 0   or   r 0   does not get closer to any point in   P∗ , other than   p 0 .   Hence, in finite number of cycles,   r 0   reaches   d 1 .   Moreover, when   r 0   reaches   d 1 , it is selected for movement again. Thus, in every subsequent computation cycle the robot   r 0   will be selected to move, until it reaches   p 0 . Hence, no collision occurs in the path of   r 0 , until   r 0   reaches   p 0   (either direct or via some   d 1 ).   r 0   reaches  p 0   in finite number of cycles. Throughout the execution of   MoveToDestination( r i ) , no robot moves such that the   SEC   changes.   Hence, the agreement on   O   i.e., the origin re- mains intact.   The robots on   SEC   and +ve   X   axis is already is in   P∗ .   Thus the axes and unit distance are also unchanged.     10
Now we present an algorithm,   MoveOnBoundary( r i ) , for the movement strategy of the robots lying on the   SEC . The algorithm assumes that the robots agree in coordinate system (using   AgreementCoordinateSystem() ). In or- der to avoid collisions we define a configuration called   alternate configuration .  Definition 1.   If there exists at least one pair   ( r   ∈   F ree  ̄ r ,   p   ∈   F reeP   )   on the  SEC , such that   p   lies on the   SEC   and   r   can move to   p   without passing through a filled final position, then the corresponding configuration is called an alternate configuration.  In   MoveOnBoundary( r i )   which is described next, we use three procedures.  •   M oveOnCircle ( r i ,   p ′ ) ensures that a robot reaches   p ′   moving strictly on  SEC .  •   M oveEnsuringAlternate ( r i ) is executed when only one robot on   SEC   is at its final position on   SEC . The function moves a robot in such a way that the alternate configuration is maintained. For example in Figure 2,  r x   moves to   B   even though   A   is nearer, just to ensure that the resulting configuration is alternate. (a)   (b)   (c)  r x  B   A  Figure 2: (a)A non-alternate configuration, (b)An alternate configuration, (c)Example execu- tion of   moveEnsuringAlternate()  •   GenerateAlternate ( r i ) is executed when two robots on   SEC   are at their final position on   SEC   and the configuration is not alternate.   The algo- rithm generates an alternate configuration. The function selects one robot  r x   6   =   r l   ( r l : leader on   SEC ) out of the two robots in   P F illed , s.t.   ∠ r x Op ′  ( ∀ p ′   ∈ (free points in   P SEC   )) is minimum and moves it along   SEC   by a very small distance      towards   p ′ . 11
Algorithm 5 : MoveOnBoundary( r i )  Input :  ̄ r : the set of robots,   P : the set of pattern points.  Output :   A configuration of robots where a robot on   SEC   is in its final position.  ̄ r SEC   ← { r j   :   r j   is on the   SEC } ;  P SEC   ← { p k :   p k   ∈ P∗   and   p k   is on the   SEC } ;  P F illed   ← { p l :   p l   ∈ P∗ ,   p l   is on the   SEC , and   p l   is occupied by a robot } ;  switch   P F illed   do case   |P F illed |   = 0 :  Find a robot   r n   ∈    ̄ r SEC   and a point   p ′   ∈ P SEC   s.t.   | r n p ′ |   is minimum a   ;  if   r i   ==   r n   then  M oveOnCircle ( r i ,   p ′ );  else  r i   does not move;  case   |P F illed |   = 1 :  if   ∃   p ′   ∈ P SEC   diametrically opposite to the point in   P F illed   then  Find a robot   r n   s.t. distance   | r n p ′ |   is minimum a ;  if   r i   ==   r n   then  M oveOnCircle ( r i ,   p ′ );  else  r i   does not move;  else  M oveEnsuringAlternate ( r i );  case   |P F illed |   = 2 :  if   the two robots in   P F illed   lie on a diameter of   SEC   then  MoveToDestination( r i );  else if   configuration is alternate   then  Find a robot   r n   ∈    ̄ r SEC   and point   p ′   ∈ P SEC   s.t.   | r n p ′ |   is minimum a ;  if   r i   ==   r n   then  M oveOnCircle ( r i ,   p ′ );  else  r i   does not move;  else  GenerateAlternate ( r i );  otherwise  /*   |P F illed |   >   2:*/ MoveToDestination( r i );  a The ties are resolved using the lexicographic ordering.  12
Correctness of the algorithm MoveOnBoundary( r i ):.   The correctness of the algorithm is established by lemma 8.  Lemma 8. MoveOnBoundary( r i )   ensures that when a robot is moving on  SEC , it does not collide with other robots and all points in   P∗   on the   SEC   are filled by robots in finite time. Proof:   Algorithm   MoveOnBoundary( r i )   maintains alternate configuration on the   SEC , during its execution.   It avoids collision between the robots.   If the configuration is already alternate, then   M oveEnsuringAlternate ( r i ) makes sure that the configuration will remain alternate.   If the configuration is not alternate, then   GenerateAlternate ( r i ) ensures the resulting configuration is an alternate configuration. It also assures that only one robot on the   SEC   occupies a final position on the   SEC .   As a result, in the next cycle, the robots will execute Case 1 of the algorithm.   Since the configuration is already alternate configuration, the robot executes   M oveEnsuringAlternate ( r i ), which will then result in (i) two robots are in their final positions on the   SEC , and (ii) robots on boundary are in an alternate configuration.   If the   SEC   is in alternate configuration, in each cycle a robot on   SEC   has a movement to its destination in   P∗   on SEC. Since, the number of robots is finite and they complete their cycles in finite time, the points in   P∗   on the   SEC   will be filled by the robots in finite time.     13
We have already presented all algorithms on which our pattern formation depends. Now we present the main algorithm,   PatternFormation( r i ) .  Algorithm 6 : PatternFormation( r i )  Input :  ̄ r : the set of robots,   P : the set of pattern points.  Output :   A configuration of robots where   r i   is at its final position. Agreement coordinate system();  switch   r i   do case   r i   =   O :  if   O   ∈ P∗   then  r i   does not move;  else  r i   moves to   p   (a point on positive X-axis at a distance      from   O );  case   r i   =   r 1 :  if   ( O / ∈ P∗ )   then if   ( ∃   a robot at   O )   then  r i   does not move;  else  r i   moves to   O ;  else if   ( ∃   a robot at   O )   then if   ( r i   6   =   p 1 )   and (   ∃   exactly one robot   r i   s.t.   0   <   | Or i |   <   ( d   +    ) )  then  r i   moves to   p 1 ;  else  r i   does not move;  else  r i   moves to   O ;  case   r i   ∈    ̄ r SEC   :  if   (( O / ∈ P∗ )   and   ( ∃   a robot at   O ))   or   (( O   ∈ P∗ )   and   ( @   a robot at   O ))  or   ( ∃   more than one robot at a distance   <   ( d   +    ))   or   ( r 1   6   =   p 1 ))   then  r i   does not move;  else if   ( ∃ p   ∈ P SEC   s.t.   @   a robot at   p )   and   ( @   a free robot strictly inside  SEC )   then  MoveOnBoundary( r i );  else  MoveToDestination( r i );  otherwise if   (( O / ∈ P∗ )   and   ( ∃   a robot at   O ))   or   (( O   ∈ P∗ )   and   ( @   a robot at   O ))  then  r i   does not move;  else if   ∃   more than one robot at a distance   <   ( d   +    )   then  MoveRadiallyOut( r i );  else if   r 1   6   =   p 1   then  r i   does not move;  else if   ∃   p   ∈ P SEC   s.t.   @   a robot at   p   then  MoveToDestination( r i );  else  MoveToDestination( r i );  14
Correctness of the algorithm PatternFormation( r i ):.   The correctness of algorithm   PatternFormation( r i )   is justified by following lemmas.  Lemma 9.   Once an agreement on origin ( O ) of the coordinate system is achieved, it remains invariant until the pattern is formed. Proof:   All robots agree on the center of the   SEC , as their origin ( O ) of the coordinate system. No robot on the   SEC   is allowed to make a movement such that the   SEC   changes. Hence,   SEC   remains intact throughout the execution of the algorithm. Therefore,   O   also does not change throughout the execution of the algorithm.     Lemma 10.   If   O / ∈ P∗ , the agreement on   XY-axis   remains invariant until the pattern is formed. Proof:   The   X   axis is decided by the ray   Or l   ( r l   is the leader on   SEC   and in  P∗ ).   r l   does not move. Hence, the   X   axis remains invariant.   Y   axis is decided by the   X   axis and the final positions on boundary of   SEC . Since   SEC   remains invariant, the final positions on   SEC   also remain invariant. Hence, the   Y   axis also remains invariant until the pattern is formed.     Lemma 11.   If   O   ∈ P∗ , then the agreement on coordinate axes remains invari- ant from the point a robot reaches   O   till the pattern is formed. Proof:   If   O   ∈   Final Positions, according to the algorithm   r 1   moves to   O . Fol- lowing lemma 10 the agreement on   XY-axis   remains invariant until the pattern is formed.     Let us denote the initial configuration of the robots as   I 0 .   I 1   denotes con- figuration when   r 1   occupies its final position at   p 1 .  Lemma 12.   I 0   gets transformed to   I 1   in finite number of cycles. Proof:   PatternFormation( r i )   ensures that   I 1   is formed as follows: if   O / ∈ P∗   and   ∃   a robot   r 0   at   O , then   r 0   moves to distance      in the direction of positive  X   axis.   If   O   ∈ P∗   and   @   robot at   O , a robot moves to origin.   Subsequent execution of   PatternFormation( r i )   finds a new   r 1   which remains invariant because, every robot (other than   r 1 ) inside or on a circle with radius   d , moves to a distance   d   +      from   O .   r 1   then occupies the position   p 1 . Owing to the fact that the distance   d   is finite,   I 1   is formed in finite number of cycles.     Consider another configuration   I 2   defined as one in which the robot   r 1   is at final position   p 1   and all the final positions on the   SEC   are occupied by some robots.  Lemma 13. PatternFormation( r i )   transforms   I 1   to   I 2 , in finite number of cycles. Proof:   According to algorithm   PatternFormation( r i )   the robots in  ̄ r SEC  do not move unless, either all position in   P SEC   have been occupied or number 15
of free robots strictly inside   SEC   becomes zero. This is assured because once  I 1   is formed, the robots move in a specific order: First, the robots on   SEC   fill the final positions in   P SEC   . Subsequently, if the number of free robots strictly inside   SEC   becomes zero and the total number of free positions in   P SEC   6   = 0, the free robots on   SEC   follow algorithm   MoveOnBoundary( r i )   to fill final positions on   SEC , while keeping   SEC   intact. This continues until all the final positions on the   SEC   are occupied by some robot. Hence,   I 2   is formed form   I 1  in finite number of cycles.     Lemma 14. PatternFormation( r i )   transforms   I 2   to   P , in finite number of cycle. Proof:   Once   I 2   is formed, free robots execute   MoveToDestination( r i )  to reach the unoccupied final positions. Robots already at their final position remain stationary.  MoveToDestination( r i )   ensures robots reach their final positions in finite time. Hence, whatever unoccupied final positions exist in   I 2   are filled by robots in a finite number of cycles and   P   is formed.     Lemma 15.   Even if the number of free robots strictly inside   SEC   is less than the number of elements in   P SEC   , algorithm   PatternFormation( r i )   executes successfully while keeping   SEC   invariant. Proof:   If the number of free robots strictly inside   SEC   is less than the num- ber of elements in   P SEC   ,   PatternFormation( r i )   ensures that after configura- tion   I 0   is formed,   MoveToDestination( r i )   moves the free robots inside   SEC  to the free points in   P SEC   . After which the algorithm   MoveOnBoundary( r i )  is called and one of the following cases arises:  •   There is no robot occupying a final position on the   SEC : In this case, only robot   r n   (the robot closest to a point   p ′   in   P SEC   ) moves to   p ′ . Note that, since nothing else has changed, in the next computation cycle a robot will execute Case 1.  •   There is exactly one robot occupying a final position on the   SEC : In this case, first the algorithm checks if there exists a point in   P SEC  which is diametrically opposite to the robot already occupying a final po- sition. If this is true then the robot nearest to this diametrically opposite point moves to it. Subsequently the circle   SEC   will remain intact even if the free robots on   SEC   are allowed to move. Otherwise, i.e., if no such diametrically opposite pattern point exists, the algorithm makes one robot move on the circle to a pattern point, while ensuring that the configura- tion remains alternate configuration. Next, the robot will see that there are two robots occupying final positions on the   SEC   and the next case will be executed.  •   There are exactly two robots occupying final positions on the   SEC : In this case, the robot first checks if two robots occupying the   P∗   on 16
SEC   form a diameter of   SEC . If this is true, then the circle will remain invariant even if other free robots on the   SEC   are allowed to move. Robots call algorithm   MoveToDestination( r i )   (which ensures that the rest of the free robots occupy their final positions).   Otherwise, robot checks if the configuration is an alternate configuration.   If it is true, the robot nearest to a pattern point on the boundary moves on the circle to towards it, else the robot call   GenerateAlternate ( r i ), which moves one of the two robots (which is not on the   X   axis) at final position (on the   SEC ) in such a way that an alternate configuration is formed. It also assures that the  X   axis does not change. This alternate configuration has only one robot remaining at a final position on the   SEC .   In the next cycle the robot enters the previous case.  •   There are three or more robots occupying final positions on the   SEC : In this case   MoveToDestination( r i )   can be called with rest of the free robots as argument. Here, we do not need to worry about keeping   SEC  invariant (since there are already at least three stationary points on the boundary of   SEC ). Under none of the above cases does the algorithm allow any changes to   SEC . Hence   SEC   remains invariant. Also since only the number of robots occupying final positions on   SEC   change in a cycle, the next cycle (if there is one) also executes one of the above cases, and after some finite number of steps, all the robots on boundary occupy points from   P SEC   .     Finally we present theorem 1.  Theorem 1.   If a set of robots is in asymmetric configuration then an asym- metric pattern formation is possible by the robots even without agreement in common coordinate system.  4. Conclusion  In this paper we present an algorithm to form a given asymmetric pattern. This assumes no agreement on coordinate axes (SoD, orientation and scale). Although we assume the robots to be point, it is possible to extended the al- gorithm for pattern formation by transparent fat robots.   The only thing we need to ensure in the case of fat robots is that at every step, the robots check if the minimum enclosing circle of their initial configuration is sufficiently large to ensure collision free movement.   This can be done by making one robot on the boundary of the circle move away from the center of the circle until the diameter becomes large enough. The detailed work on pattern formation for fat robots may be an interesting continuation of this work.  References  [1] N. Agmon and D. Peleg.   Fault-tolerant gathering algorithms for au- tonomous mobile robots. In   Proceedings of the fifteenth annual ACM-SIAM  17
symposium on Discrete algorithms , SODA ’04, pages 1070–1078, Philadel- phia, PA, USA, 2004. Society for Industrial and Applied Mathematics. [2] T. Balch and R. C. Arkin. Behavior-based formation control for multirobot teams.   Robotics and Automation, IEEE Transactions on , 14(6):926 –939, dec 1998. [3] G. Beni and J. Wang. Theoretical problems for the realization of distributed robotic systems.   In   Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on , pages 1914 –1920 vol.3, apr 1991. [4] X. D ́ efago and S. Souissi. Non-uniform circle formation algorithm for obliv- ious mobile robots with convergence toward uniformity.   Theoretical Com- puter Science , 396(1   3):97 – 112, 2008. [5] A. Efrima and D. Peleg. Distributed algorithms for partitioning a swarm of autonomous mobile robots.   Theoretical Computer Science , 410(14):1355 – 1368, 2009.   Structural Information and Communication Complexity (SIROCCO 2007). [6] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer.   Hard tasks for weak robots: The role of common knowledge in pattern formation by au- tonomous mobile robots. In   Algorithms and Computation , volume 1741 of  Lecture Notes in Computer Science , pages 93–102. Springer Berlin Heidel- berg, 1999. [7] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Distributed co- ordination of a set of autonomous mobile robots.   In   Intelligent Vehicles Symposium, 2000. IV 2000. Proceedings of the IEEE , pages 480 –485, 2000. [8] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Pattern formation by anonymous robots without chirality. In   SIROCCO , pages 147–162, 2001. [9] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots.   Theor. Comput. Sci. , 407(1-3):412–447, November 2008. [10] S. Gan Chaudhuri and K. Mukhopadhyaya.   Leader election and gath- ering for asynchronous transparent fat robots without chirality.   CoRR , abs/1208.4484, 2012. [11] S. Ghike and K. Mukhopadhyaya. A distributed algorithm for pattern for- mation by autonomous robots, with no agreement on coordinate compass. In   Distributed Computing and Internet Technology , volume 5966 of   Lecture Notes in Computer Science , pages 157–169. Springer Berlin Heidelberg, 2010. [12] N. Gordon, Y. Elor, and A. Bruckstein. Gathering multiple robotic agents with crude distance sensing capabilities. In   Ant Colony Optimization and Swarm Intelligence , volume 5217 of   Lecture Notes in Computer Science , pages 72–83. Springer Berlin Heidelberg, 2008. 18
[13] D. Jung, G. Cheng, and A. Zelinsky. Experiments in realising cooperation between autonomous mobile robots. In   Experimental Robotics V , volume 232 of   Lecture Notes in Control and Information Sciences , pages 609–620. Springer Berlin Heidelberg, 1998. [14] Y. Katayama, Y. Tomida, H. Imazu, N. Inuzuka, and K. Wada. Dynamic compass models and gathering algorithms for autonomous mobile robots. In   Structural Information and Communication Complexity , volume 4474 of  Lecture Notes in Computer Science , pages 274–288. Springer Berlin Hei- delberg, 2007. [15] R. Klasing, E. Markou, and A. Pelc.   Gathering asynchronous oblivious mobile robots in a ring.   Theoretical Computer Science , 390(1):27 – 39, 2008. [16] F. R. Noreils. Toward a robot architecture integrating cooperation between mobile robots: Application to indoor environment.   The International Jour- nal of Robotics Research , 12(1):79–98, 1993. [17] L. E. Parker and C. Touzet. Multi-robot learning in a cooperative obser- vation task. In   Distributed Autonomous Robotic Systems 4 , pages 391–401. Springer, 2000. [18] D. Peleg.   Distributed coordination algorithms for mobile robot swarms: New directions and challenges.   In   Distributed Computing - IWDC 2005 , volume 3741 of   Lecture Notes in Computer Science , pages 1–12. Springer Berlin Heidelberg, 2005. [19] G. Prencipe. Instantaneous actions vs. full asynchronicity: Controlling and coordinating a sset of autonomous mobile robots. In   Theoretical Computer Science , volume 2202 of   Lecture Notes in Computer Science , pages 154–171. Springer Berlin Heidelberg, 2001. [20] G. Prencipe.   Impossibility of gathering by a set of autonomous mobile robots.   Theoretical Computer Science , 384(2 - 3):222 – 231, 2007. Structural Information and Communication Complexity (SIROCCO 2005). [21] G. Prencipe and N. Santoro. Distributed algorithms for autonomous mobile robots. In   Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006 , volume 209 of   IFIP International Federation for In- formation Processing , pages 47–62. Springer US, 2006. [22] K. Sugihara and I. Suzuki.   Distributed motion coordination of multiple mobile robots. In   Intelligent Control, 1990. Proceedings., 5th IEEE Inter- national Symposium on , pages 138 –143 vol.1, sep 1990. [23] I. Suzuki and M. Yamashita. Formation and agreement problems for anony- mous mobile robots. In   Proc. 31st Annual Conference on Communication, Control and Computing , pages 93 – 102, 1993. 19
[24] I. Suzuki and M. Yamashita. Distributed anonymous mobile robots - forma- tion and agreement problems. In   Problems, in the Proceedings of the 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO’96 , pages 1347–1363, 1996. [25] I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: For- mation of geometric patterns.   SIAM Journal on Computing , 28:1347–1363, 1999. 20