Pattern Formation for Asynchronous Robots without
Agreement in Chirality
Sruti Gan Chaudhuri1, Swapnil Ghike2, Shrainik Jain3 and Krishnendu
Mukhopadhyaya4
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 = {r1, r2, . . . , rn} 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 = {(xi, yi) : 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.
1In 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 cP be the center of the SEC. cP becomes
the common origin, for the pattern. We fix an ordering Ord(P) for the point in
P. A point, pl ∈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 pl ∈P such that pl 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.
□
|cPpl| is the common unit distance, −−→
cPpl is the common positive X axis for
the pattern. Let p′
l ∈P be a point on SEC, which is presented next to pl in
Ord(P).
Lemma 2. It is possible to select a point p′
l ∈P, different from pl, 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
cPpl. 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; cP ←center of SEC;
Ord(P) ←ordering of P;
pl ←the first point from SEC in Ord(P);
+ve X axis ←cPpl;
p′
l ←a point next to pl in Ord(P) such that it does not lie on cPpl;
+ve Y axis ←the perpendicular of cPpl, drawn at cP, at that side of +ve
X axis, where p′
l lies;
Return cP as center, |cPpl| 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, cP, i.e., the origin is unique. Lemmas 1 and
2 ensure that, pl 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, rl, in Ord(¯r), which is lying on SEC of ¯r, is selected as leader.
Lemma 4. It is possible to select an rl ∈¯r from SEC of ¯r.
Proof: Since, ¯r is in asymmetric configuration, it is orderable.
If we fix an
ordering, rl may be chosen as the first robot in that ordering which lies on the
SEC of ¯r.
□
P is plotted so that c¯r = cP and rl = pl. c¯r becomes the common origin,
denoted by O. cPpl or c¯rrl becomes the positive X axis. The positive Y axis for
P is the common positive Y axis for the robots. |c¯rrl| = |cPpl| 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;
rl ←first robot in Ord(¯r);
AgreementPattern();
Plot P such that:
O ←c¯r ←cP;
rl ←pl;
u ←|Orl|;
+ve X axis for ¯r ←c¯rrl;
+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 r0 at O, then r0 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 p1 be the pattern point nearest to O (if there are many, we
choose the first one in Ord(P)). r1 is the robot nearest to O (if there are
many, we choose the first one in Ord(¯r)). Let d = max(|Or1|, |Op1|). The
robots which lie inside or on Cir(O, d), move radially to a distance d + ϵ
from O.
• Step 4. r1 moves to p1.
• 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(ri) executes the 3rd 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(ri)
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 r1 and p1;
d ←max(|Or1|, |Op1|);
¯r′ ←{rk ∈¯r: s.t. rk lies inside Cir(O, d)};
Compute Ord(¯r);
ri ∈¯r′ ←robot nearest to the boundary of Cir(O, d + ϵ) (in case of tie
use Ord(¯r));
h ←intersection of Ori and Cir(O, d + ϵ);
if h is not occupied by any robot then
ri moves to h;
else
g ←a point at a side of h which is not occupied by other robot and
∠grih ≤90o;
ri moves to g;
Correctness of MoveRadiallyOut(ri):. The correctness of the algorithm is
established by lemma 6.
Lemma 6. MoveRadiallyOut(ri) ensures collision free movement of the robots.
7
Proof: MoveRadiallyOut(ri) 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(ri) 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 r1 to p1 in step 4 is collision free.
Now we describe algorithm MoveToDestination(ri) 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(ri)
Input: ¯r: the set of robots, P: the set of pattern points.
Output: Destination for each robot in P∗.
FreeP ←{pj ∈P∗: pj is not occupied by any robot};
Free¯r ←{rj ∈¯r: rj /∈P∗};
S ←{(|Orj|, ∠rjOpk) : rj ∈Free¯r, pk ∈FreeP};
Let (|Or0|, ∠r0Op0) be the lexicographic minimum of S;
d′ ←|Op1|;
if ri ̸= r0 then
Destination ←null;
else
if r0p0 does not intersect Cir(O, d′ + ϵ) then
if no other robots lie on r0p0 then
Destination ←p0;
else
SafeRegion ←the part of the region inside the SEC but
outside Cir(O, d′ + ϵ) that lies between −−→
Or0 and −−→
Op0 s.t.
∠r0Op0 ≤180o;
d0 ←a point in SafeRegion, s.t. there exists no robots on
d0p0;
Destination ←d0;
else
Find T 1
r0, T 2
r0, the tangents from r0 to Cir(O, d′ + ϵ) at points t1
r0
and t2
r0 respectively ;
Find T 1
p0, T 2
p0, the tangents from p0 to Cir(O, d′ + ϵ) at points t1
p0
and t2
p0 respectively;
K ←the set of points of intersection of T i
r0,T j
p0 for 1 ≤i, j, ≤2;
Find d1 ∈K s.t. |r0ti
r0|+|p0tj
p0| is minimum, for 1 ≤i, j, ≤2;
if no robot lies on r0d1 (excluding point d1 itself) then
Destination ←d1;
else
SafeRegion ←the part of the region inside the SEC but
outside Cir(O, d′ + ϵ) that lies between −−→
Or0 and −−→
Op0 s.t.
∠r0Op0 ≤180o;
d0 ←a point ∈SafeRegion, s.t. there exists no robots on
d0d1;
Destination ←d0;
ri moves to Destination;
Correctness of MoveToDestination(ri):. The correctness of the algorithm
is established by lemma 7.
9
Lemma 7. Algorithm MoveToDestination(ri) 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 Free¯r to final positions in FreeP, is
designed in such a way that only one robot at a time moves (Figure 1). No robot
in Free¯r gets closer to O than r1, which is already is at p1. The algorithm selects
a pair (r0 ∈Free¯r, p0 ∈FreeP) such that ∠r0Op0 is minimum. If the line r0p0
does not intersect Cir(O, d′ + ϵ), then r0 moves to p0. Else, if the line r0p0
intersects Cir(O, d′ + ϵ), then r0 travels through the tangents of Cir(O, d′ + ϵ),
while ensuring that the path to p0 is the shortest. This is achieved by computing
a point d1, s.t. d1 is the intersection of tangents from p0 and r0 to Cir(O, d′ +ϵ)
and the distance from r0 to p0 via d1 is minimum. r0 then moves towards d1.
Since, r0’s last move was along r0d1 towards of d1, one of the following may
happen: (i) no robot takes snapshot till r0 reaches d1; (ii) other robots take
snapshot during the movement of r0 along r0d1. In situation (ii), a robot which
takes snapshot, will find r0 at a point a on r0d1, other than d1. (aO, ∠aOp0)
remains minimum during this movement. Hence, r0 will again be selected for
movement.
SEC
Circle(O, d + ϵ)
O
r0
p0
d1
a
d′
1
̸ r0Op0 decreases during the movement of r0;
even if a robot takes a snapshot when r0 is at a
r0 will again be selected for movement
Figure 1: An Example execution of MoveToDestination(ri)
The movement of r0 does not result in any other robot getting closer to p0
than r0 or r0 does not get closer to any point in P∗, other than p0. Hence,
in finite number of cycles, r0 reaches d1. Moreover, when r0 reaches d1, it is
selected for movement again. Thus, in every subsequent computation cycle the
robot r0 will be selected to move, until it reaches p0. Hence, no collision occurs
in the path of r0, until r0 reaches p0 (either direct or via some d1). r0 reaches
p0 in finite number of cycles.
Throughout the execution of MoveToDestination(ri), 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(ri), 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 ∈Free¯r, p ∈FreeP) 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(ri) which is described next, we use three procedures.
• MoveOnCircle(ri, p′) ensures that a robot reaches p′ moving strictly on
SEC.
• MoveEnsuringAlternate(ri) 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,
rx moves to B even though A is nearer, just to ensure that the resulting
configuration is alternate.
(a)
(b)
(c)
rx
B
A
Figure 2: (a)A non-alternate configuration, (b)An alternate configuration, (c)Example execu-
tion of moveEnsuringAlternate()
• GenerateAlternate(ri) 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
rx ̸= rl (rl: leader on SEC) out of the two robots in PF illed, s.t. ∠rxOp′
(∀p′ ∈(free points in PSEC)) is minimum and moves it along SEC by a
very small distance ϵ towards p′.
11
Algorithm 5: MoveOnBoundary(ri)
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.
¯rSEC ←{rj: rj is on the SEC};
PSEC ←{pk: pk ∈P∗and pk is on the SEC};
PF illed ←{pl: pl ∈P∗, pl is on the SEC, and pl is occupied by a robot};
switch PF illed do
case |PF illed| = 0:
Find a robot rn ∈¯rSEC and a point p′ ∈PSEC s.t. |rnp′| is
minimuma ;
if ri == rn then
MoveOnCircle(ri, p′);
else
ri does not move;
case |PF illed| = 1:
if ∃p′ ∈PSEC diametrically opposite to the point in PF illed then
Find a robot rn s.t. distance |rnp′| is minimuma;
if ri == rn then
MoveOnCircle(ri, p′);
else
ri does not move;
else
MoveEnsuringAlternate(ri);
case |PF illed| = 2:
if the two robots in PF illed lie on a diameter of SEC then
MoveToDestination(ri);
else
if configuration is alternate then
Find a robot rn ∈¯rSEC and point p′ ∈PSEC s.t. |rnp′| is
minimuma;
if ri == rn then
MoveOnCircle(ri, p′);
else
ri does not move;
else
GenerateAlternate(ri);
otherwise
/* |PF illed| > 2:*/
MoveToDestination(ri);
aThe ties are resolved using the lexicographic ordering.
12
Correctness of the algorithm MoveOnBoundary(ri):. The correctness of
the algorithm is established by lemma 8.
Lemma 8. MoveOnBoundary(ri) 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(ri) maintains alternate configuration
on the SEC, during its execution. It avoids collision between the robots. If
the configuration is already alternate, then MoveEnsuringAlternate(ri) makes
sure that the configuration will remain alternate. If the configuration is not
alternate, then GenerateAlternate(ri) 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 MoveEnsuringAlternate(ri), 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(ri).
Algorithm 6: PatternFormation(ri)
Input: ¯r: the set of robots, P: the set of pattern points.
Output:
A configuration of robots where ri is at its final position.
Agreement coordinate system();
switch ri do
case ri = O:
if O ∈P∗then
ri does not move;
else
ri moves to p (a point on positive X-axis at a distance ϵ from O);
case ri = r1:
if (O /∈P∗) then
if (∃a robot at O) then
ri does not move;
else
ri moves to O;
else
if (∃a robot at O) then
if (ri ̸= p1) and ( ∃exactly one robot ri s.t. 0 < |Ori| < (d + ϵ))
then
ri moves to p1;
else
ri does not move;
else
ri moves to O;
case ri ∈¯rSEC:
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 (r1 ̸= p1)) then
ri does not move;
else
if (∃p ∈PSEC s.t. ∄a robot at p) and (∄a free robot strictly inside
SEC) then
MoveOnBoundary(ri);
else
MoveToDestination(ri);
otherwise
if ((O /∈P∗) and (∃a robot at O)) or ((O ∈P∗) and (∄a robot at O))
then
ri does not move;
else
if ∃more than one robot at a distance < (d + ϵ) then
MoveRadiallyOut(ri);
else
if r1 ̸= p1 then
ri does not move;
else
if ∃p ∈PSEC s.t. ∄a robot at p then
MoveToDestination(ri);
else
MoveToDestination(ri);
14
Correctness of the algorithm PatternFormation(ri):. The correctness of
algorithm PatternFormation(ri) 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 Orl (rl is the leader on SEC and in
P∗). rl 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 r1 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 I0. I1 denotes con-
figuration when r1 occupies its final position at p1.
Lemma 12. I0 gets transformed to I1 in finite number of cycles.
Proof: PatternFormation(ri) ensures that I1 is formed as follows: if O /∈
P∗and ∃a robot r0 at O, then r0 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(ri) finds a new r1 which remains invariant
because, every robot (other than r1) inside or on a circle with radius d, moves
to a distance d + ϵ from O. r1 then occupies the position p1. Owing to the fact
that the distance d is finite, I1 is formed in finite number of cycles.
□
Consider another configuration I2 defined as one in which the robot r1 is at
final position p1 and all the final positions on the SEC are occupied by some
robots.
Lemma 13. PatternFormation(ri) transforms I1 to I2, in finite number of
cycles.
Proof: According to algorithm PatternFormation(ri) the robots in ¯rSEC
do not move unless, either all position in PSEC have been occupied or number
15
of free robots strictly inside SEC becomes zero. This is assured because once
I1 is formed, the robots move in a specific order: First, the robots on SEC fill
the final positions in PSEC. Subsequently, if the number of free robots strictly
inside SEC becomes zero and the total number of free positions in PSEC ̸= 0,
the free robots on SEC follow algorithm MoveOnBoundary(ri) 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, I2 is formed form I1
in finite number of cycles.
□
Lemma 14. PatternFormation(ri) transforms I2 to P, in finite number of
cycle.
Proof: Once I2 is formed, free robots execute MoveToDestination(ri)
to reach the unoccupied final positions. Robots already at their final position
remain stationary.
MoveToDestination(ri) ensures robots reach their final positions in finite
time. Hence, whatever unoccupied final positions exist in I2 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 PSEC, algorithm PatternFormation(ri) 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 PSEC, PatternFormation(ri) ensures that after configura-
tion I0 is formed, MoveToDestination(ri) moves the free robots inside SEC
to the free points in PSEC. After which the algorithm MoveOnBoundary(ri)
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 rn (the robot closest to a point p′ in PSEC) 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 PSEC
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(ri) (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(ri), 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(ri) 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 PSEC.
□
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