Information Technology Reference
In-Depth Information
In the general case, the algorithm compares
b
and
d
, and performs a pair of moves
such as when
b
d
,then
b
is reduced. In this
way, the axis of symmetry and its direction do not change.
Apart from some special cases, the algorithm works as follows. When
b
>
d
,then
b
is enlarged, while, if
b
<
>
d
,
x
↑
and
x
↑
and
y
↑
are performed. In both cases,
(apart for some special cases) the ordering between
b
and
d
is maintained in the new
configuration. Eventually, either one multiplicity is created at the middle node of the
original interval
A
by means of robots
x
and
x
, or two symmetric multiplicities are
created on the positions originally occupied by
x
and
x
by means of the moves of
y
and
y
, respectively. In the second case, the two multiplicities will move up again to
the middle node of the original interval
A
by allowing at most four robots to move
all together. Once such a multiplicity has been created, the remaining robots join it,
and conclude the gathering. In the special case of
b
are performed, while, when
b
<
d
,
y
↑
d
, which can only happen in
the initial configuration, the algorithm tries to break this equality by enlarging or
reducing
d
by means of either
z
=
and
z
↑
and
z
↓
↑
(when
C
>
0) or
z
↓
(when
C
=
0
and
D
>
0). The special cases when
C
=
D
=
0 require specific arguments that can
be found in [
9
].
13.2.2.4 Unifying Algorithm
Recently in [
11
], a new technique has been proposed for addressing all the gather-
able initial configurations by means of a single algorithm that exploits some of the
described strategies while also solving the remaining cases left open. In particular,
existing algorithms are used as subroutines for solving the basic gatherable cases
with four or six robots from [
23
]and[
9
], respectively. Also, Property
1
is exploited
in some cases. Then, the main strategy is based on the definition of a particular read
of the configurations perceived by the robots during their Look phase.
The current configuration of the system can be described in terms of the view
of a robot
r
that is performing the Look operation. A configuration seen by
r
is
represented as a tuple
Q
1, that represents the sequence
of the numbers of free consecutive nodes broken up by robots when traversing the
ring in one direction, starting from
r
. Unless differently specified,
Q
(
r
)=(
q
0
,
q
1
,...,
q
j
)
,
j
≤
k
−
represents
the configuration providing the lexicographical minimum among the two possible
views. For instance, in the configuration of Fig.
13.2
a, robot
x
can read either
Q
(
r
)
=
or
Q
=(
(
1
,
2
,
1
,
3
,
1
,
2
)
2
,
1
,
3
,
1
,
2
,
1
)
, hence
Q
(
x
)=
Q
. A multiplicity is represented
as
q
i
=
−
j
, regardless the number of r
ob
ots composing it.
Given a generic configuration
C
1forsome0
≤
i
≤
,
and let
C
i
be the configuration obtained by reading
C
starting from
q
i
as first interval,
that is
C
i
=(
=(
q
0
,
q
1
,...,
q
j
)
,let
C
=(
q
0
,
q
j
,
q
j
−
1
,...,
q
1
)
q
i
,
q
(
i
+
1
)
mod
j
+
1
,...,
q
(
i
+
j
)
mod
j
+
1
)
. The above definitions imply:
Property 2.
Given a configuration
C
,
(i) There exists 0
<
i
≤
j
such that
C
=
C
i
if
f
C
is periodic;
iff
C
is symmetric;
(iii)
C
is aperiodic and symmetric iff there exists only one axis of symmetry.
(ii) There exists 0
≤
i
≤
j
such that
C
= (
C
i
)
Search WWH ::
Custom Search