arXiv:1105.4082v1 [cs.NI] 20 May 2011  Emergent Velocity Agreement in Robot Networks  Davide Canepa ∗   Xavier Defago †   Taisuke Izumi ‡   Maria Potop-Butucaru ∗  Abstract  In this paper we propose and prove correct a new self-stabilizing velocity agreement (flocking) algorithm for oblivious and asynchronous robot networks. Our algorithm allows a flock of uniform robots to follow a flock head emergent during the computation whatever its direction in plane.   Robots are asynchronous, oblivious and do not share a common coordinate system. Our solution includes three modules architectured as follows: creation of a common coordinate system that also allows the emergence of a flock-head, setting up the flock pattern and moving the flock. The novelty of our approach steams in identifying the necessary conditions on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed) that allow the flock to both follow the exact same head and to preserve the flock pattern.   Additionally, our system is   self-healing   and   self-stabilizing . In the event of the head leave (the leading robot disappears or is damaged and cannot be recognized by the other robots) the flock agrees on another head and follows the trajectory of the new head. Also, robots are   oblivious   (they do not recall the result of their previous computations) and we make no assumption on their initial position. The step complexity of our solution is   O ( n ).  ∗ LIP6, Univ. Pierre & Marie Curie - Paris 6, LIP6-CNRS UMR 7606, France.  † JAIST, Japan Advanced Institute in Science and Telecomunication, Japan  ‡ Graduate School of Engineering, Nagoya Institute of Technology, Japan
1   Introduction  Flocking gained recently increased attention in diverse areas such as biology, economy, language study or agent/sensor networks. In biology, flocking refers the coordinate behaviour of a group of birds or animals when they sense some imminent threat or lookup for food. In economy, the emergent behaviour that regulates the stock markets can be seen as a form of flocking.   The emergency of a common language in primitive societies is also an instantiation of flocking. In the context of robot networks, flocking is the ability of a group of robots to coordinate and move in the plane or space. This coordinated motion has several civil and military applications ranging from zone exploration to space-crafts self-organization. In distributed robot networks there are two types of agreement problems that have been studied so far: point or pattern agreement and velocity agreement.   Point agreement   (gathering or convergence) aims at instructing robots to reach an exact or approximate common point not known   a priori .   The dual is the scattering problem where robots are instructed to reach different positions in the plane. Furthermore, pattern agreement deals with instructing robots to eventually arrange in a predefined shape (i.e. circular, rectangular etc).  Velocity agreement   or flocking refers the ability of robots to coordinate and move in 2D or 3D spaces without any external intervention. The literature agrees on two different strategies to implement flocking. The first strategy is based on a predefined hierarchy. That is, there is an a priori leader clearly identified in the group that will lead the group and each group member will follow the leader trajectory.   An alternative is to obtain an emergent coordination of the group without a predefined leader. The difficulty of this approach comes from the permanent stress for connectivity maintenance. That is, if the flock splits then it may never converge to a single flock. In this paper we are interested in uniform flocking strategies. That is, the head of the flock emerges during the computation hence the solution is self-healing.   Also, the flock does not know a priori the motion trajectory. That is, the head of the flock will lead the flock following its own trajectory that may be predefined or decided on the fly.   Our work is developed in the asynchronous CORDA model [5 ,   13] one of the two theoretical models proposed so far for oblivious distributed robot networks. The first distributed model for robot networks, SYm, was introduced by Suzuky and Ya- mashita [17 ,   18 ,   19].   In SYm model robots are oblivious and perform a cycle of elementary actions as follows : observation (the robot observes the environment), computation (the robot computes its next position based on the information collected in the observation phase) and motion (the robot changes its position to the newly computed position). In this model robots cannot be interrupted during the execution of a cycle. The CORDA model breaks the execution cycle in elementary actions.   That is, a robot can be activated/turned off while it executes a cycle. Hence, robots are not any more synchronized. The   flocking problem   although largely discussed for real robots ([9, 11, 15]) was studied from distributed theoretical point of view mainly by Prencipe [7 ,   8]. The authors propose non- uniform algorithms where robots play one of the following roles: leader or follower. The leader is unique and all the followers know the leader robot.   Obviously, when the leader crashes, disappears or duplicates the flock cannot finish its task. In [1] we extend the results in [14] and propose a probabilistic flocking architecture. However, we make the assumption that the leader and consequently the flock do not change their direction and trajectory. Our current approach is different, the leader is not known a priori but it will emerge during the computation. When the current leader disappears or is damaged and not recognized as a correct robot, the other robots in the system agree on another leader and the flock can finish its task. Furthermore, the flock can change both its direction and trajectory in order to agree with the emergent leader 1
velocity. Fault-tolerant (but not self-stabilizing) flocking has been addressed in [16, 20]. In [16] the authors propose a fault tolerant flocking algorithm in the SYm model using a leader oracle and a failure detector. In our solution the leader or the head of the flock emerges during the computation.   Also, our solution works in asynchronous settings and their decision is solely based on their current observation. In [20] the authors also propose a fault tolerant flocking. It is assumed the SYm model (awaken robots execute their operations in synchronous steps) and the k-bounded scheduler (in between two actions of a robot any other robot executes at most  k   actions).   Also the solution needs agreement on one axis, agreement on chirality and non- oblivious robots. Contrary to this approach, our solution does not need any a priori agreement on axis or chirality. Moreover, we assume oblivious robots. Several works from robotics propose recently heuristics for flocking(e.g. [10, 12]). In [10], for example, the authors propose a solution for non-uniform flocking. In their proposal the leader has to execute a different strategy than the rest of the flock. Hence, the system is not uniform.  Our contribution.   In this paper we propose and prove correct a new asynchronous flocking algorithm in systems with oblivious and uniform robots. Additionally, we identify the necessary conditions on the flock pattern placement and the flock head velocity (rotation, translation, speed) to allow the flock to maintain the same leader and the common coordinate system and also to preserve the motion pattern.   Our solution is composed of three asynchronous   self- stabilizing   and   self-healing   phases.   First robots agree on a common coordinate system and a leader. Once this phase is finished robots form a flocking pattern and move preserving the same system of coordinates and the same leader. In the event of the head leave (the leading robot disappears or is damaged and cannot be recognized by the other robots) the flock agrees on another head and follows the trajectory of the new head.   Also, robots are   oblivious   (they do not recall the result of their previous computations) and we make no assumption on their initial position. The complexity of our solution is   O ( n ).  Paper organization.   The paper is organized as follows: Section 2 defines the model of the system, Section 3 specifies the problem based on the flocking informal definitions in different areas ranging from biological systems to space navigation.   In this section we also propose a brief description of our system architecture. Section 4 sets up the common coordinate system, Section 5 details the formation of the flocking pattern and the necessary conditions on the flock placement, Section 6 proposes the rules for moving the flock and identifies the necessary conditions on the flock head velocity.  2   Model  Most of the notions presented in this section are borrowed from [8, 13]. We consider a system of autonomous mobile robots that work in the CORDA model [13]. Each robot is capable of observing its surrounding, computing a destination based on what it observed, and moving towards the computed destination: hence it performs an (endless) cycle of observing, computing, and moving.   Each robot has its own local view of the world.   This view includes a local Cartesian coordinate system having an origin, a unit of length, and the directions of two coordinate axis (which we will refer to as the x and y axis), together with their orientations, identified as the positive and negative sides of the axis. The robots are model as units with computational capabilities, which are able to freely move in the plane. They are equipped with sensors that let each robot observe the positions of the 2
others with respect to their local coordinate system. Each robot is viewed as a point, and can see all the other robots in the flock. The robots act totally independent and asynchronously from each other, and do not rely on any centralized directives, nor on any common notion of time. Furthermore, they are oblivious, meaning that they do not remember any previous observation nor computations performed in the previous steps. Note that this feature combined with no assumptions on the initial position of the robots gives to the algorithms designed in this model the nice property of   self-stabilization  [4]. That is, every decision taken by a robot does not depend on what happened previously in the system and robots do not use potentially corrupted data stored in their local memory. Robots in the flock are anonymous (i.e. they are a priori indistinguishable by their appear- ances and they do not have any kind of identifiers that can be used during the computation). Moreover, there are no explicit direct means of communication; hence the only way they have to acquire information from their fellows robots is by observing their positions. They execute the same algorithm (the system is uniform), which takes as input the observed positions of the fellow robots, and returns a destination point towards which they target their move. Summarizing, each robot moves totally independent and asynchronously from the others, not having any bound on the time it needs to perform a move, hence a cycle; therefore, a robot can be seen while it moves.   In addition, robots are oblivious, and anonymous.   We make no assumption on the initial position of robots or a common coordinate system.  3   The flocking problem  Reynolds proposed in the mid of 80’s three rules that have to be respected by any algorithm that simulates a flock-like behaviour.   He successfully applied these rules in designing several animations. At that time the flock entities were called boids and the model was as follows: each boid has the ability to sense its local neighbours; each boid can sense the whole environment, all boids recalculate their current state simultaneously once each time unit during the simulation. In this model, according to Reynolds, the flocking rules are as follows:  •   Separation: steer to avoid crowding local flock-mates.  •   Alignment: steer towards the average heading of local flock-mates.  •   Cohesion: steer to move toward the average position of local flock mates. Interestingly, the model proposed by Reynolds is similar to the previously described SYm model.   Robots can sense the environment (the other robots in the system) and they period- ically and simultaneously recalculate their state.   However, in CORDA model (the one used in the current work) the computation is asynchronous. Nevertheless, the main and important difference with respect to the Reynolds assumptions is the impossibility to use the history of the computation in order to implement the flocking rules. Note that the second rule of Reynolds indirectly use this information. Therefore, in the case of robot networks these rules should be adapted. In distributed robot networks acceptance, flocking allows a group or a formation of robots to change their position either by following a pre-designated or an emergent leader. In this case the flocking is reffered as   uniform . Intuitively, a flock is a group of robots that move in the plane in order to execute a task while maintaining a specific formation. This informal definition implicitly assumes the existence of an unique leader of the flock that will lead the group during the task execution and the existence of a flocking pattern. Also it is assumed a virtual link between the head and the rest of the group. Therefore, three elements seem to be essential in the definition 3
of the flocking :   the head or the leader of the group, the pattern and the orientation of the pattern with respect to the leader. Based on these elements, flocking can be seen as the motion of the virtual rigid formed by the flock and its head following a trajectory predefined or defined on-the-fly. It follows that both the flock and its head periodically synchronize their velocity in order to maintain the flock. In the following we specify the uniform flocking problem (i.e. the leader emerges during the computation).   We first recall the definition of leader election and pattern formation. According to a recent study, [3, 6], pattern formation and leader election are related problems. Our specification naturally extends this observation to the flocking problem.  Definition 1 (Leader Election)   [6] Given the positions of   n   robots in the plane, the   n   robots are able to deterministically agree on the same robot called the leader.  Definition 2 (Pattern Formation)   [6] The robots have in input the same pattern, called the target pattern   F , described as a set of positions in the plane given in lexicographic order (each robot sees the same pattern according to the direction and orientation of its local coordinate system). They are required to form the pattern: at the end of the computation, the positions of the robots coincide, in everybody’s local view, with the positions of   F , where   F   may be translated, rotated, and scaled in each local coordinate system.  Definition 3 (Uniform Flocking)   Let   r 1   . . . r n   be a set of robots and let   F   be the flocking pattern. The set of robots satisfy the flocking specification if the following properties hold:  •   head/leader emergence   eventually robots agree on an unique head (leader),   r 1 ;  •   pattern emergence   eventually robots,   r 2 , . . . , r n , form the pattern   F ;  •   velocity agreement   after any modification of the   r 0   position, robots in the pattern rotate and translate   F   in order to converge to the same relative position and orientation between  r 0   and   F   as it was before the modification.  •   no collision   any robot motion is collision free.  Note the common flavour between the Reynolds rules and the above properties.   No collision  property corresponds to the separation rule.   Velocity agreement   corresponds to the alignment rule and finally   leader and pattern emergence   are similar to the cohesion property. In the following we combine three different tasks to solve the uniform flocking in systems where robots are asynchronous, do not share the same coordinate systems, are oblivious and uniform.   First, we design a novel strategy for equipping a set of robots with a common co- ordinate systems. To this end we propose a probabilistic strategy that creates two singularity points.   Then, we combine this module with existing probabilistic election strategies ([1, 2]) in order to create the third singularity point.   The motion of this third point will eventually designate the head of the flock (robot   r 0 ) and the orientation of the common coordinate sys- tem.   Then, the emergent common coordinate system is further used by all the robots but   r 0  to arrange themselves in a flocking pattern,   F , that will further follow the head   r 0 . During the pattern motion, both the head and the common coordinate system are preserved.  4   Common Coordinate System and Flock Head Emergence  The construction of a common coordinate system is as follows. First, robots agree on one axis, then they agree on the second axis, orientation of axis and the head of the flock. Due to space limitation, the details and the correctness proof of these algorithms are proposed in the Annexes (section 9). 4
Figure 1: Alignment of   F ar Robots   and Leader  Agreement on the first axis.   Note that one axis is defined by two distinct points.   The algorithm idea is very simple:   robots compute the barycentre of their convex hull.   The fur- therest couples of robots with respect to the barycentre (if their number is greater than one) probabilistically move further from the barycentre along the line defined by themselves and the barycentre. Two robots   r i   and   r j   belong to the set of the   F ar Robots   if dist(i, j)   ≥   dist(w,k)   ∀  w,k robots in the system. With high probability the above strategy converges to a configuration where the set   F ar Robots   contains an unique couple of robots.  Agreement on the second axis.   The construction of this second axis is conditioned by the existence of two unique nodes. We chose these two nodes as follows: one is the centre of smallest enclosing circle while the second one is given by any leader election algorithm. Several papers discuss the election of a leader (e.g. [1, 2]).  Axis orientation and flock head emergence.   In order to orient the axis we first align the two   F ar Robots ,   R A   and   R B   , and the leader (see Figure 1). Once the alignment is performed, the first is oriented instructing the leader to create a disimetry between the two points. The alignment strategy is as follows. If the leader is not aligned with the other two robots then it will choose between the two robots belonging to the   F ar Robots   the one with a bigger value of   x . In case of symmetry, a bigger value of   y . Then, it will move toward the intersection of the radius of that robot and the circumference of the cercle with center in   O   (the center of the   SEC ) and the radius equal to   dist ( O, Leader ). Finally, the robot not chosen by the Leader (referred as   R B   ) will align with the other two robots.   R B   moves only when the Leader is aligned with   R A .   That is, when one of the two Far robots, sees that the Leader is aligned with the other   F ar Robot   and   O , then it moves following the   SEC   until it forms a line with the Leader, the center of the SEC and the other robot in   F ar Robots . Note that the two   F ar Robots   are on the   SEC . For now on, the   F ar Robots   nearest to the Leader will be referred as   R 1 and the other one  R 2. Robot   R 1 will play the   flock head   role.  5   Pattern Emergence  In this section we address the formation of the flocking pattern.   Note that we work in a system where robots do not have a common coordinate system. The previous section propose strategies to uniquely identify 3 robots that altogether with the center of the SEC define a common coordinate system.   In the following, we assume that over the initial set of   n   robots 3 robots (referred in the previous section Leader, R1 and R2) are reserved for maintaining the coordinate system while the other   n   −   3 can be placed in any shape that will be further reffered as the flocking pattern.   However, we impose a condition on the placement of the shape with 5
respect to the position of the robots that define the references (Leader, R1 and R2) in order to preserve both the unicity of the references and the common coordinate system.  Lemma 1   The area where the pattern is placed has to satisfy the following three conditions in order to preserve the common coordinate system defined by Leader, R1 and R2. 1. All robots must be inside the circumference having   R 1 R 2   as diameter. 2. All the robots must be in the side of the   SEC   with   R 2   and   y   negative. 3. The circle with radius   dist ( Leader, O )   and center in   O   must be empty.  Proof:   If a robot moves outside the   SEC , at the next round 1   the   SEC   will change and consequently the references.   It follows the necessity of condition one.   If there exist robots in symmetrical positions with respect to the   x   axis, then the system loses the capability to distinguish   R 1 and   R 2. This proves the necessity of point two. Point three is motivated by the need of an unique leader. If a robot goes closer to the center of the   SEC   than the leader then it becomes   Leader   and so the references will change.  In order to realize the flocking additional constraints on the shape of the area where the pattern is deployed are needed. These conditions will be discussed in the next section. The flocking pattern is obtained in two steps. A first step called bootstraping and a second step that is basically a colission free strategy to move to the pattern positions. In between these two phases the Leader will move perpendiculary to the segment   R 1 R 2 in order to orient the second axis. This orientation will be used by the robots in defining a total order among them.  Pattern Bootstraping.   The bootstraping process takes two phases. In the first phase, all robots but the leader are placed on the smallest enclosing circle(SEC). First, the robots closest to the boundaries of the SEC are placed, then recursivelly the other robots. The algorithm avoids collisions and ensures that robots preserve the referenced (e.g. Leader, R1 and R2) computed in the previous section. In the second phase, the robots on the SEC but R1 will be placed on the semi-circle not occupied by the R1 as follows.   R 1 is in the position   SEC   ∩   [ O, Leader ) and   R 2 is on the opposite side of the   SEC . The other robots are disposed on the quarter of circle around   R 2.   During this process the references are used to help the deployement of the others robots. Also, the movement of robots is done such that the semantic of the references is preserved. The code of the algorithms and their analysis are proposed in Annexes, Section 10.  Flocking Pattern Formation.   In the following we defined the flocking pattern robots can form in order to maintain the common coordinate system and the references defined in the previous section. The flocking pattern   F   =   { p 1 , p 2 ,   · · ·   , p n − 3 , p o , p R 2 }   is the set of points given in input to the robots.   It has two distinguished points   p o   and   p R 2 .   We call the two distinguished points the   Anchor Bolts   of the pattern, that will correspond to the position of robots   R 2 and to the point ( O ,   dist ( Leader, O )) of the common coordinate system. Note that robots start this phase in the following configuration: The segment   OLeader   is perpendicular to the segment   R 1 R 2 (where   O   is the center of the SEC) and all the other robots are disposed on the quarter of circle around   R 2. In order to form the flocking pattern in a colision free manner robots adopt the following strategy.   First, all robots but the references hook the pattern, eventually scale and rotate it to   R 2 and to the point ( O ,   dist ( Leader, O )). Then they totally order the set of  1 A round is a fragment of execution where each robot in the system executes its actions  6
Figure 2: Pattern formation strategy robots based on their coordinates in the common coordinate system and associate to each robot a position in the pattern. Since the order is based on the common coordinate system, all robots will define the exact same order.   Then robots move following their order hence collisions are avoided. In Figure 2 robot   r 2   has a trajectory that intersects the trajectory of both robots   r 1  and   r 3 .   However collisions are avoided since following the total order   r 1   moves first, then   r 2  and finally   r 3 .   The detailed code of the algorithm and its analysis are proposed in Annexes, Section 11. Once the flocking pattern is formed the Leader moves to the center of the   SEC . This last movement brings the robots in what will be called latter   Flocking Formation . The motion of this formation will be studied in the next section.  6   Velocity Agreement  In this section we propose a strategy to synchronize the   F locking F ormation   and the head of the flock. The idea is to use   R 1 and   R 2 as two ends of a virtual spring. The other robots will be ”pulled” by   R 1   and ”pushed” by   R 2 .   Any time   R 1   or   R 2   moves, the center of the  SEC   changes. It follows that the   F locking F ormation   is not valid since the Leader position in not anymore on the center of the   SEC . Then, the motion of   R 1   and   R 2   is blocked until the flocking pattern is reformed. The Leader moves back to the center of the SEC which makes the  F ocking F ormation   valid and deblocks the motion of robots   R 1   and   R 2 . In the following we precisely characterize two safe regions   M   and   K .   M   is the zone where  R 1 is allowed to move and   K   is the area where the pattern can be disposed. In the following we propose a general definition of   M   and   K .  Definition 4   Let   M   be the area with   y   ≥ ± ( kx   +   R 1) .   Let   K   be the area between the axis  y   =   ± h ′ x   for   y <   0   and   y   =   ± hx   +   R 2   for   y <   0 .  We additionally define two particular angles,   α   and   β   between the axis that border   M   and  K . Latter, we prove that   α   and   β   should be greater than 90 0   in order to verify the conditions stated in Lemma 1.  Definition 5   Let   α   be the angle between   y   =   ± hx   +   R 2   and   y   =   ∓ kx   +   R 1 .   Let denote by  A   the intersection of these two lines. Let   β   be the angle between   y   =   ± h ′ x   and   y   =   ∓ kx   (see Figure 3).  The flocking algorithm, Algorithm 6.1 is executed only when the   Flocking Formation   is reached (see Section 5). The algorithm foresee the movement of robots   R 1,   R 2 and the   Leader .  R 1 is the robot that imposes the direction of the movement so it can move to any point in the  M   area. When it moves, thanks to the constraints we have imposed, the references hold steady and so, at the next observation, all the robots can recognize the references: Leader, R1 and R2. 7
Figure 3: Angles   α   and   β   and the safe areas   M   and   K  Additionally, all the other robots will be inside the   SEC   (on the   R 2 side). Then, all the other robots but   R 2 execute the flocking pattern formation algorithm (presented in Section 5) to align the pattern to the new direction (defined by the axis   R 2 R 1). Once the   F locking F ormation   is recreated the robots   R 1 or   R 2 can move again. When the distance between   R 1 and   R 2 is greater than some parameter   d Rmax , then   R 2 moves inside the   K   area (along the   R 2 R 1 segment) within distance   d .   Following Lemma 2 below this distance should be less or equal than (   dist ( R 1 R 2)  2   −   dist ( R 1 B )  2 cosδ   ) where   B   is the closest robot to   R 2 and   δ   is the angle   6   R 2 R 1 B . 1)   if   (Robots form the   Flocking Formation )  If   ( dist ( R 1 , R 2)   < d Rmax  then   R1 moves to a point   ∈   M   ; 2)   else if   ( dist ( R 1 , R 2)   ≥   d Rmax  then   R2 moves within distance   d   along the segment   R 2 R 1; 3)   else   Leader moves perpendicular to   R 1 R 2 at the center of the SEC; then robots execute Flocking Formation algorithm (Section 5). Algorithm 6.1: The motion of the Flocking Formation with parameters   d   and   d Rmax . In the sequel we determine the relation between the axis that define the areas   M   and   K  (i.e. angles   α   and   β ) so that after each movement of   R 1 or   R 2 all the references are preserved. Firstly, we must guarantee that the   SEC   will change coherently with the movement of   R 1 and  R 2. At each step the   SEC   corresponds to the circumference having   R 1 and   R 2 as diameter.  Lemma 2   Let   R 1 ′   be the point where robot   R 1   moves ( inside the   M   area). The circle having as diameter   R 1 ′ R 2   contains all the robots if the angle   α   is at least   90 0 .  Proof:   Consider the worst case:   R 1 ′   belongs to   y   =   ± kx   +   R 1 and there exists a robot   B   6   =  R 2 on the border of the   M   areas:   y   =   ± hx   +   R 2. Without restraining the generality consider the case where   R 1 ′   moves on the segment   y   =   − kx   +   R 1 and   B   is on the line   y   =   hx   +   R 2. When   R 1 ′   diverges from   R 1 the circumference of the new SEC defined by the point   R 1 ′   and   R 2 intersects the line   R 1 B   in a point   T   . When   α <   90 0   and   R 1 ′   diverges from   R 1,   T   moves inside the segment   R 1 B   towards   R 1.   Hence, at least one robot in the formation (robot   B ) will be 8
Figure 4: Angle   β  outside the new position of the SEC. When   α   ≥   90 0   and   R 1 ′   diverges from   R 1 the   T   diverges from   B   hence every robot in the formation will be inside the new SEC.  Lemma 3   After the movement of   R 2 , the circle having as diameter   R 1 R 2 ′ , contains all the robots if   d   ≤   (   dist ( R 1 R 2)  2   −   dist ( R 1 B )  2 cosδ   )   where   B   is the closest robot to   R 2   and   δ   is the angle  6  R 2 R 1 B .  Proof:   According to Algorithm 6.1,   R 2 will move on the   y   axis within distance   d   from its current position. Let this position be   R 2 ′ . Now we will find a value of   d   such that any robot inside the   K   zone, is always inner (or at least on) the circumference having   R 1 R 2 ′   as diameter. Consider the robot   B   such that after   R 2 moves,   B   is on the border of the new SEC and no other robot is outside the new SEC. Let   δ   be the angle between   R 2 , R 1 and   B . Using simple geometrical constructions it follows that   d , the maximal distance   R 2 can move, should less or equal than (   dist ( R 1 R 2)  2   −   dist ( R 1 B )  2 cosδ   ).  Note that after the movement of   R 1 or   R 2 they are still in the set   F ar Robots . In the following we identify a second relation between the axis defining the areas   M   and   K  in order to verify the conditions of Lemma 1.  Lemma 4   After the movement of   R 1   or   R 2 , the Leader is preserved and also the references, if  β   ≥   90 0   (Figure 4).  Proof:   Now we will find the smallest value of   β   such that the   Leader   is preserved.   First, note that the pattern formation algorithm described in the previous sections starts only if the  Leader   is perpendicular to the   R 1 R 2 axis, with respect the center of the   SEC . So, if one of   R 1 or   R 2 moves, the only one that can move after them is the   Leader . Then, all the other robots must wait until it reaches its final position. After the Leader motion it is still the Leader since it is the closest to the SEC. Note also that if   R 2 moves, the Leader is always preserved independently of the value of   β . In this case the new center   O ′   of the   SEC   will ever be on the   R 1 R 2 axis, between the   Leader  and   R 1. Once again the   Leader   is preserved since it is the closest robot to   O ′ . Cosider the case   R 1 moves. In the worst case   R 1 moves on the border of   M . Let   R 1 ′   be the next position of   R 1. At each point   R 1 ′   corresponds a new point   O ′   (the middle point of the 9
segment   R 1 ′ R 2) which is the center of the new SEC. If   R 1 ′   moves on the axis   y   ≥ ∓ kx   +   R 1, then   O ′   moves on the parallel axis   y   ≥ ∓ kx   and if   R 1 ′   goes to infinity, then   O ′   also goes to infinity. Let   B   be a robot on one of the borders of   K ,   y   =   ± h ′ x   for   y <   0.   In the following we determin the value of   β   in order to preserve the   Leader . That is, there is no robot closer to   O ′  than the   Leader . Assume robot   B   and   Leader   are equidistant with respect to   O ′ . Let   M   be the middle point of the segment   BLeader . Notice that : 1) if   Leader   and   B   are equidistant to   O ′   then the triangle ( B, O ′ , Leader ) is isosceles. 2) if the triangle ( B, O ′ , Leader ) is isosceles then the angle   γ   between   Leader, M, O ′   is right. It follows that   β <   90 0 . So, in order to never have   O ′ Leader   ≤   O ′ B ,   β   ≥   90 0 .  Lemma 5   Starting in any configuration or after any movement of robot   R 1   or robot   R 2   the the system converges to the flocking specification in O(n) steps.  Proof:   Starting in a configuration that is not a   F locking F ormation   the system converges in  O ( n ) to a   F locking F ormation (the analysis is provided in the Annexes). After the movement of either   R 1 or   R 2, the center of the   SEC   will change. It follows that the   Leader   is not anymore on the center of the SEC and the   F locking F ormation   is invalide. Now, due to the first condition in Algorithm 6.1 any movement of   R 1 or   R 2 is impossible. Then the flocking formation algorithm is executed until a new   F ocking F ormation , consistent with the new references, will be reached. Following the analysis provided in the Annexes this takes O(n) steps.   Then,   R 1   and   R 2   are again free to move.  7   Conclusions and open questions  The current work studies the flocking problem in the most generic settings:   asynchronous robot networks, oblivious robots, arbitrary initial positions. We proposed a solution with nice self ∗   properties.   That is, in the event of the head leave the flock agrees on another head. Moreover, robots are oblivious, can start in any initial configuration and do not share any common knowledge. Additionally, the flock follows the head whatever its trajectory. Also, the algorithm makes sure that the flock will follow the same head (once emerged) and the system of coordinates does not change during the execution.   To this end we identified the necessary conditions that both the pattern and the head velocity have to satisfy in order to maintain the flock pattern, the same unique head and the same coordinate system. A nice extension of this problem would be to use energy constraints as in biological systems. There, in order to conserve the energy of the group, the head is replaced from time to time. Including energy considerations in the model is a challenge in itself. Also, assuming that heads may change in order to conserve the energy of the group it is also assumed that some kind of common knowledge is shared by all the members of the group.   This common knowledge may help in bypassing the impossibility results related to symmetric configurations.   Another interesting extension would be the volumic model. The current solution cannot work in these settings since it is based essentially on alignement properties.  Acknowledgements   The last author would like to thank Ted Herman for helpfull discus- sions related to flocking in biological systems that inspired the current specification and also the open question stated in the Conclusion section. 10
References  [1] Davide Canepa and Maria Gradinariu Potop-Butucaru.   Stabilizing flocking via leader election in robot networks. In   SSS , pages 52–66, 2007. [2] Yoann Dieudonne and Franck Petit.   Circle formation of weak robots and lyndon words.  Inf. Process. Lett. , 101(4):156–162, 2007. [3] Yoann Dieudonn ́ e, Franck Petit, and Vincent Villain.   Leader election problem versus pattern formation problem. In   DISC , pages 267–281, 2010. [4] Shlomi Dolev.   Self-stabilization . MIT Press, 2000. [5] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Distributed coordination of a set of autonomous mobile robots.   IVS, pages 480-485. , 2000. [6] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pat- tern formation by asynchronous, anonymous, oblivious robots.   Theor. Comput. Sci. , 407(1- 3):412–447, 2008. [7] V. Gervasi and G. Prencipe. Coordination without communication: The case of the flocking problem.   Discrete Applied Mathemathics , 2003. [8] Vincenzo Gervasi and Giuseppe Prencipe. Flocking by a set of autonomous mobile robots. Technical Report TR-01-24, Universitat di Pisa, 2001. [9] A. Qadi Jiangyang Huang, S.M. Farritor and S. Goddard.   Localization and follow-the- leader control of a heterogeneous group of mobile robots.   Mechatronics, IEEE/ASME Transactions on , 11:205–215, 2006. [10] Geunho Lee and Nak Young Chong. Adaptive flocking of robot swarms: Algorithms and properties.   IEICE Transactions , 91-B(9):2848–2855, 2008. [11] Magnus Lindhe.   A flocking and obstacle avoidance algorithm for mobile robots . PhD thesis, KTH Stockholm, 2004. [12] Christoph Moeslinger, Thomas Schmickl, and Karl Crailsheim. Emergent flocking with low- end swarm robots. In   Proceedings of the 7th international conference on Swarm intelligence , ANTS’10, pages 424–431, 2010. [13] G. Prencipe. Corda: Distributed coordination of a set of autonomous mobile robots.   Proc. ERSADS, pages 185–190, May 2001. , 2001. [14] Giuseppe Prencipe. Achievable patterns by an even number of autonomous mobile robots. Technical Report TR-00-11 Universitat di Pisa, 17 2000. [15] P. Renaud, E. Cervera, and P. Martiner.   Towards a reliable vision-based mobile robot formation control.   Mechatronics, IEEE/ASME Transactions on , 4:3176– 3181, 2004. [16] Samia Souissi, Taisuke Izumi, and Koichi Wada. Oracle-based flocking of mobile robots in crash-recovery model. In   SSS , pages 683–697, 2009. [17] Ichiro Suzuki and Masafumi Yamashita. A theory of distributed anonymous mobile robots formation and agreement problems.   Technical report, Wisconsin Univ. Milwaukee Dept. of Electrical Engineering and Computer Science, 6 1994. 11
[18] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots—formation and agreement problems.   Proceedings of the 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO ’96), Siena, Italy, June 1996. , 1996. [19] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns.   SIAM Journal on Computing , 28(4):1347–1363, 1999. [20] Yan Yang, Samia Souissi, Xavier D ́ efago, and Makoto Takizawa.   Fault-tolerant flocking for a group of autonomous mobile robots.   Journal of Systems and Software , 84(1):29–36, 2011. 12
8   Appendix 9   Setting up a common coordinate system  The construction of a common coordinate system is built gradually. First, robots agree on one axis, then they agree on the second axis.  9.1   Agreement on the first axis  One axis is defined by two distinct points. In order to get two common points, robots move in order to distinguish an unique couple. The algorithm idea is very simple: robots compute the barycentre of their convex hull. The furtherest robots with respect to the barycentre (if their number is greater than two) probabilistically moves further from the barycentre along the line defined by themselves and the barycentre.  Functions:  Far   (myself) returns true if   ∃ r i , d ( myself, r i )   ≥   d ( r w , r k ) ∀ w, k   robots  Procedure:  FarRobots()   returns the set of robots,   r , Far(r)=true }  1) Compute the distance   d ( myself, r i ) between myself and each robot   r i , 2) FarRobots() 3)   if   ( myself   ∈   FarRobots   ∧ ‖   FarRobots   ‖ >   2)  then   {   compute the baricentrum of FarRobots() move away from the barycentre with probability  p >   0 of a distance   d   myself   ·   p }  Algorithm 9.1: Robot Separation executed by robot   myself  Definition 6   Two robots   r i   and   r j   belong to the set of the   Far Robots   if dist(i, j)   ≥   dist(w,k)  ∀   w,k robots in the system.  Definition 7 (legitimate configuration)   A legitimate configuration for Algorithm 9.1 is a configuration with only two   Far Robots .  Lemma 6   Starting from a configuration with more than two robots belonging to the set   Far Robots , the system executing Algorithm 9.1 converges to a legitimate configuration (see Defi- nition 7) with high probability.  The proof follows the same lines as the leader election proof in [1].  9.2   Agreement on the second axis  The construction of this second axis is conditioned by the existence of two unique nodes. We chose these two nodes as follows: one is the centre of smallest enclosing circle while the second one is given by any leader election algorithm. Several papers discuss the election of a leader. In [1] the authors prove the impossibility of deterministically electing a leader without additional assumptions and propose probabilistic solutions. In [2] discuss the conditions to deterministi- cally elect a leader. 13
9.3   Axis orientation and head emergence  The following strategy, referred as Algorithm 9.3 allows the alignment of points computed with Algorithm 9.1 with respect to the centre of the smallest enclosing circle and the leader. Once the alignment performed this first axis can be easily oriented using the position of the leader.  Functions:  Lined(A,B,C)   returns true is the three points form a line.  Lined(A,B,C,D)   returns true is the four points form a line.  choose ( F arRobots ) returns one between the   Far robots : the far robot with bigger value of   y   or a bigger value of   x , in case   y   values are equal  Note : We will call the two far robots   R A   and   R B   only to the sake of precision in the algorithm description.   While executing the algorithm robots make no distinction between them. 1) if   (R   ∈   Far Robots   and R not on the   SEC )  then   move to the   SEC . 2)   if   ( ¬ Lined ( R A , R B   , Leader, O )) 3)   if   ( ¬ Lined ( R A , Leader, O ) and   ¬ Lined ( R B   , Leader, O ) and   R   =   Leader )  then   move towards   OX ,   X   =   choose ( F arRobots ) at a distance   dist ( Leader, O ). 4)   if   ( Lined ( R A , Leader, O ) and   ¬ Lined ( R B   , Leader, O ) and   R   =   R B  then   move towards   R A Leader   ∩   SEC . In the sequel we will call   R 1 the   F ar Robot   closest to   Leader   and   R 2 the other one. Algorithm 9.2: Alignment algorithm executed by robot   R  The first operation is to make sure that the two elected   F ar Robots   are on the   SEC . Otherwise, they move to the SEC (smallest enclosing circle). If the leader is not aligned with the other two robots then it will choose between the two robots belonging to the   F ar Robots   the one with a bigger value of   x . In case of symmetry, a bigger value of   y . Then, it will move toward the intersection of the radius of that robot and the circumference with center in   O   (the center of the   SEC ) and radius equals to   dist ( O, Leader ). Finally, the robot not chosen by the Leader (referred in the algorithm is   R B   ) will align with the other two robots.   R B   moves only when the Leader is aligned with the other robot. That is, when one of the two Far robots, sees that the Leader is lined up with the other   F ar robot  and   O , then it moves following the   SEC   until it form a line with the Leader, the center of the SEC and the other robot in   F ar Robots . Recall that the two   F ar robots   moved previously to the   SEC . For now on, the   F ar Robots   nearest to the Leader will be referred as   R 1 (Reference 1) and the other one   R 2.  Lemma 7   During its movement,   R 2 , will never collide with another robot.  Proof:   Assume   R 2 collides with a robot   R 3.   R 3 will belong to the   SEC   and it will be closer than   R 2 to the point at the end of the diameter of the   R 1, so the the angle   α 3   between diameter of   R 1 and   R 1 R 3 will be smaller than the angle   α 2   between diameter of   R 1 and   R 1 R 2.   But 14
distance(R1, R2) is equal to   diameter   ·   cos ( α 2 ) that is smaller than   diameter   ·   cos ( α 3 ).   It follows that   R 3 will be farther than   R 2 with respect to the   R 1 position which contradicts the hypothesis ( R 2   is the furthest robots with respect to   R 1).  10   Bootstraping the flocking pattern  In this section we execute a pre-processing that prepares the set up of the flocking pattern used further by the flocking algorithm. We build on top of the algorithms described in the previous section. The pattern includes three robots used as references (called Leader, R1 and R2) and other n-3 robots that can be placed in any shape. The bootstraping process takes two phases. First, all robots but the leader will be placed on the smallest enclosing circle.   Then, the robots on the SEC but R1 will be placed on the semi-circle not occupied by the leader.  10.1   Phase 1: Placement on the Smallest Enclosing Cercle  The idea of the algorithm proosed as Algorithm 10.1 is very simple. First, the robots closest to the boundaries of the smallest enclosing circle are placed. Than recursivelly the other robots. The algorithm avoids collisions and ensures that robots preserve the referenced (e.g.   Leader, R1 and R2) computed in the previous section.  Definition 8   Let   F reeT oM ove   be the set of robots without robots between themselves and the  SEC   (including the border) along the radius passing through them, and that does not belong to the   SEC .  Definition 9   Let   AlreadyP laced   be the set of the robots belonging to the border of the   SEC .  Definition 10   A legitimate configuration for Algorithm 10.1 is a configuration where all robots but the leader are in the set   AlreadyP laced .  Note that the algorithm does not change the leader position neither the position of   AlreadyP laced  nodes ( R 1 and   R 2 belong to the set of the   AlreadyP laced ). Moreover, there is no node behind the leader and sharing the same radius as the leader. Otherwise this node will be the closest to the center of the   SEC .  Lemma 8   Algorithm 10.1 is silent.  Proof:   The leader does not change its position and once all robots but the leader are in the set   AlreadyP laced   no robot can execute its actions so the algorithm is silent.  Lemma 9   If two robots   r i   and   r j   belong to the set   F reeT oM ove , than their final position will be different.  Proof:   If there are no robots between   r i   and the   SEC   along   radius i   and there are no robots between   r j   and the   SEC   along   radius j   than   radius j   and   radius i   must be different. To different radius correspond different positions on the   SEC   so   r i   and   r j   , thanks to Rule 1, will be placed on different positions.  Lemma 10   A robot always moves towards a free position on the   SEC .  15
Preprocessing:  ∀ r i   compute the value of the radius passing through   r i .   Let   rad r i   be the value of the angle between my radius ( rad myself   = 0) and the radius of robot   r i , in clockwise direction (note that clockwise depends only on the coordinate system of each robot)  ∀ r i   compute the value of   dist r i   , distance of the robot   r i   to the border of the smallest enclosing circle ( SEC )  Predicates:  Leader ( myself   )   ≡ ∀ r i   with   i   6   =   myself   ,   dist i   < dist myself  Functions:  OccupiedP osition ( rad myself   )   : returns   r i , i   6   =   myself, dist r i   =   0   and rad r i   =  rad myself   otherwise   ⊥  N extT oM ove   : returns the set of closest robots   r   to the   SEC   with   dist r   6   = 0 1)   if   ¬ Leader ( myself   )   ∧   myself   ∈   F reeT oM ove  then   {   move to   SEC   with distance   dist myself   }  2)   if   ( ¬ Leader ( myself   )   ∧   ( myself   ∈   N extT oM ove )   ∧   ( F reeT oM ove   =   ∅ )   ∧  ( OccupiedP osition ( rad myself   )   6   =   ⊥ ))  then   {   Move   to   the   first   quarter   point   of   the   arch   between   robot OccupiedPosition( rad myself   ) and robot   r j   belonging to the   SEC   such that   rad j  is minimum. }  Algorithm 10.1: Placement executed by robot   my   self  Proof:   Rule 1 moves robots in the set   F reeT oM ove .   By definition these robots move only on free positions on the   SEC . Some robots not in the set   F reeT oM ove   are allowed to move only when the set   F reeT oM ove  is empty and they are in the set   N extT oM ove .   Let   r i   and   r j   be such robots.   r i   and   r j   are enabled for the Rule 2 and move towards the quarter point of the arc between the robot   r ii  (and   r jj   ) and their next robot on the border of   SEC . The worst case is if   r i   and   r j   can move together and their own system of coordinate is such that the next robot for   r i   is   r jj   and the next for   r jj   is   r ii   (see Figure 5). Firstly we can notice that the arc between the two robots is free before their movement ( otherwise   r j   would not be the next one of   r ii   and vice versa).   Moreover, the sector between  r jj   and   r ii   is free.   Assume a robot exists in that area.   Following Rule 2 it must go towards  SEC   before   r i   moves and hence becoming the next robot of the   SEC   after   r ii . Now   r i   and   r j  can move freely in this sector, the only problem can be due to a reciprocal collision. But, since  r i   and   r j   can move only in the first quarter of their area, starting from an opposite side (the  K   zones of Figure 2), then they cannot collide.   If instead one of the robots cannot reach the quarter point in one move (due to scheduler interference), at its next schedule it will still verify the conditions of Rule 1, so it will move to the   SEC   following this same rule.  Lemma 11   Algorithm 10.1 is collisions free (two robots never move towards the same free position).  Proof:   Firstly if two robots   r i   and   r j   start at different distances from the   SEC , only the one closest to SEC can move. The other one must wait until the former reaches the circumference. 16
O  r ii  r jj  r j  r j  r i  r i  r i   zone   K  Figure 5: If the two robots   r i   and   r j   have the same distance with respect to the   SEC , than they may move at the same time. If they are enabled for the Rule 1 then they never collide since they will reach different positions on the   SEC   moving along their respective radius which are different (Lemma 9). If both   r i   and   r j   are enabled for Rule 2 then both robots must move towards the quarter point between the robot   r p   on   SEC   belonging to its radius and the next robot   r P next  on the   SEC   in their own clockwise direction. Following Lemma 10 the sector between   r p   and   r P next   is free from other robots and a robot can move only inside the zone   K   (see Figure 5).   Since   r i   and   r j   do not belong to the same radius so   r p i   6   =   r p j   and   r P next i   6   =   r P next j   . So the two   K   zone where   r i   and   r j   can move have no intersection. It follows,   r i   never reaches   r P next i   . Overall   r i   and   r j   will never reach the same final position nor meet on the way to their respective final positions.  Lemma 12   Algorithm 10.1 converges in   O ( n )   steps to a legitimate configuration.  Proof:   Rule 1 allows only robots in   F reeT oM ove   to move to the   SEC . Thanks to Rule 2 all robots that don’t belong to this set must wait until that it is empty.   Once this set is empty, robots, excepted the leader, that are not on the   SEC   can execute the Rule 2.   This rule is such that it can be executed only by the set of robots   i   with   min ( dist i ) and   dist i   6   = 0.   Now these robots can move towards the middle point of the arc of   SEC   between the robot on   SEC  belonging to its radius and the next robot on the   SEC   in clockwise direction. Once these robots have arrived on the   SEC   and their corresponding   dist   = 0, other robots can satisfy Rule 2 and move to the   SEC . This process will be iterate until all the robots except the Leader are on the  SEC . Following Lemma 11 robots do not collide and no robot obstructs the trajectory of other robots. In the worst case the algorithm converges in O(n) steps.  10.2   Phase 2: Setting the circular flocking configuration  This phase is a pre-processing phase for forming the final motion pattern.   Starting from the final configuration of Algorithm 10.1 the curent phase reaches a circular flocking configuration as shown in Figure 6. The circular shape has the following caracteristics:   Leader   is inside the  SEC   (the one computed by Algorithm 10.1) and all the other robots are disposed on the SEC border. These robots are placed as follows:   R 1 is in the position   SEC   ∩   [ O, Leader ) and   R 2 is on the opposite side of the   SEC . The other robots are disposed on the quarter of circle around 17
R 2.   In the following this configuration will be referred as   circular flocking configuration   (see Figure 6 for a nine robots example).  O  R 1  Leader  p 2  p 3  p 4  p 1  p 4  p 1  R 2  Figure 6: Circular flocking configuration In order to construct the circular flocking configuration we introduce the concept of oriented configuration:  Definition 11 (oriented circular configuration)   A configuration is called circular oriented if the following conditions hold: 1. All robots are at distinct positions on the   SEC   , except only one of them, called   Leader , located inside   SEC   ; 2.   Leader   is not located at the center of   SEC ; 3. Two robots, named   R 1   and   R 2 , form with   Leader   and   O   (the center of the   SEC ) a line;  Note that the output of Algorithm 10.1 satisfies point 1 of the definition above. Note also that the alignment of the references phase supply the point 2 and 3 of the definition above. Algorithm 10.2 below started in an oriented configuration eventually converges to a circular flocking configuration. The algorithm makes use of the following function:   F inalP ositions ( SEC, R 1 , R 2) which returns, when invoked by a robot, the set of positions in the circular flocking configuration with respect to   SEC   and to the points   R 1 and   R 2.   R 1 is the robot on the intersection between the segment [ O, Leader ) and the circle   SEC .   R 2 is the robot on the intersection between the diameter of   SEC   passing through   R 1 and the center of   SEC . To calculate the position of the other robots, we split the circumference in two parts, taking   R 1 and   R 2 as terminal points. Each robot counts how many robots are in its semi-circumference, so it will create, in the first quarter closest to   R 2, as many equidistant final positions as many robots are(considering that the last position is already occupied by   R 2).   The order of these positions is given from the closest to   R 1, to the furthest 18
Functions:  get   number ( myself   ) returns the number of robots between   myself   and position   p 1   (including robot myself) clockwise  get   position ( myself   ) returns the position   get   number ( myself   ) in   F inalP ositions ( SEC, p 1 )  F reeT oM ove ( myself   ) returns true if there are no robots between   myself  and   get   position ( myself   ) Motion Rule:  if   FreeToMove(myself)   then  move to   get   position ( myself   ) Algorithm 10.2: Setting the motion formation executed by robot   myself  The idea of the algorithm is as follows. Robots started in an oriented configuration reach their final positions in the circular flocking configuration. If a robot is blocked by some other robots than it waits until all these robots are placed in their final positions.  Lemma 13   In a system with   n   robots, Algorithm 10.2 started in an oriented configuration converges in   O ( n )   steps to a configuration where all robots reached their final positions computed via FinalPositions function.  Proof:   For this proof we can consider only one semi-circumference, the behavior of the other one will be totally symmetric to the former. Let   p 1 , . . . , p n   be the robots’ final positions returned by   F inalP ositions ( SEC, R 1 , R 2) and let   r 1 , . . . , r n   be the set of robots to be placed. Assume the worst initial configuration:   no robot is placed in its final position Let denote by   L   the segment defined by the robots which are not placed in their final positions. The initial length of   L   is   n . The robots   r 1   (the first robot in   L ) can freely move to its final position   p 1 . Once this robot is placed the length of segment   L   becomes   n   −   1. One of the new ends of   L   can be placed to its final position. Assume the contrary. All robots are blocked. So, there is a waiting chain such that   r 2   →   r 3   →   . . .   →   r n   or   r n   →   . . . r 2 . Since the chain is finite and not cyclic (due to the total order) one of the ends of the chain can move ( r 2   or   r n ). After this robot moves the length of the segment   L   decreases. Eventually, all robots in   L   finish in their final positions. In the worst case, the algorithm converges in   O ( n ) steps.  11   Flocking Pattern  In the following we describe the pattern the robots can form.  Definition 12 (Pattern)   A pattern   P   =   { p 1 , p 2 ,   · · ·   , p n − 3 , p o , p R 2 }   is the set of point given in input to the robots. It has two distinguished points   p o   and   p R 2 . We call the two distinguished points the   Anchor Bolts   of the pattern, that will correspond to the position of robots   R 2   and to the point ( O ,   dist ( Leader, O ) ) of the common coordinate system.  First, all robots but the   ref erences   hook the pattern, eventually scale and rotate it, to   R 2 and to the point ( O ,   dist ( Leader, O )).   Then they associate to each robot a position in the pattern.   Algorithm 11.1 ensures that each robot goes to its position without colliding with other robots. Several definitions are needed. 19
Definition 13   A robot   r i   belongs to the set   F ree Robot   if   r i   6   =   p i .  Definition 14   A position   p i   belongs to the set   F ree P osition   if   r i   6   =   p i .  Functions:  T rajectory i : the segment that joins   r i   to   p i  N ext ( P i , P j   ): returns true if   x P i   < x P j   or, if ( x P i   =   x P j   ) and   y P i   < y P j   ; otherwise returns false We can also say   P i   has   P j   as Next robot(position) Assignments to all the   F ree Robots   but the references and to all   F reeP osition   6   =   p L  but the   anchorbolts   of a sequential number from the robot (position) with the smaller value of   x   to the bigger. If two or more robots have the same   x   value, then consider their   y   value. 1)   for   (all   r i   6   =   r me )  If   ( p me   ∈   T rajectory i )  then   Exit; 2)   if   (Next( p me , r me ))  If   (Next( r me − 1   , p me ))  then   (move along the   T rajectory me   until   x me − 1   +   ε   );  Else   (move to   p me )  If   (Next( r me , p me ))  If   (Next( r me +1 , p me ))  then   (move along the   T rajectory me   until   x me +1   −   ε   );  Else   (move to   p me ) Algorithm 11.1: Pattern Formation executed by robot ”me”  Definition 15 (DeadLock)   A Deadlock configuration is a configuration where each robot is blocked by another robot.  Note that: 1) Following Rule 1 a Deadlock arrives if there exists a robot   i   on each   trajectory j   .  ∀ i   6   =   j   and 2) Following Rule 2 a Deadlock can occur if all the robots have a Next robot. In the following we prove that none of these two conditions are satisfied.  Lemma 14   No deadlock configuration is reached.  Proof:   In the following we prove that none of the two deadlock conditions are satisfied. Assume that the three robots are in a DeadLock situation. We call these three robots   r 1 ,  r 2   and   r 3 . To these three robots will correspond three position   p 1 ,   p 2 ,   p 3 . Assume also that the following statements are true: Next( p 1 ,   p 2 ) and Next( p 2 ,   p 3 ). If DeadLock then:   p 1   ∈   T rajectory 2   and   p 2   ∈   T rajectory 3   and   p 3   ∈   T rajectory 1 . In the following we prove that none of the previous situations can happen.   First assume Next( r 2 , p 2 ) returns true 2 : If   p 1   ∈   T rajectory 2   then Next( p 1 , p 2 ) returns true . Let   p 2   on the   T rajectory 3   then Next( p 2 , p 3 ) returns true.   If   p 3   ∈   T rajectory 1   then Next( p 3 , p 1 ) returns true which contradicts the hypothesis Next( p 1 ,   p 3 ).  2 The case Next( p 2 , r 2 ) is totally symmetric  20
From the definition of   N ext   we can assert that the relation is unequivocal (unambiguous) so if we have two robots A and B and Next(A,B) returns true then Next(B,A) must return false. Also if Next(A,B) returns true and Next(B,C) returns true then also Next(A,C) should return true. As before we can say that A and B have a next robot but C do not has any Next robot. If we iterate the process we will always find one robot without a Next robot.  Lemma 15   The algorithm is collision free 3 .  Proof:   Easily by the point 2 no robot can surpass another robot, moreover thanks to the same point, two FreeRobots, starting from position with different   x   values will never occupy two positions with the same   x   value. Similarly if two robots start from positions with the same  x   value, after the activation of one of the two robots, they will be in positions with a different  x   value. Having at each round position with a different   x   value, the robots never collide.  Lemma 16   All robots will eventually reach their final position in the pattern.  Proof:   Lemma 15 and Lemma 14 guarantee that all robots can move to their own position.  The last operation, once the pattern is bootstrapped is to bring the Leader to the center of the   SEC . This last movement brings the robots in what will be called latter   F locking F ormation . The motion of this formation will be studied in the next section.  3 Note that is the algorithm is collision free two robots cannot try to get the same position.  21