Information Technology Reference
In-Depth Information
The next definition represents the key feature for the gathering algorithm.
Definition 1.
Given a configuration
C
=(
q
0
,
q
1
,...,
q
j
)
such that
q
i
≥
0, for each
j
, the view defined as
C
SM
0
is called the
su-
permin configuration v
iew
.
An interval is called
supermin
if it belongs to the set
I
C
=
{
≤
i
≤
=
min
{
C
i
,
(
C
i
)
, |
0
≤
i
≤
j
}
C
SM
C
SM
q
i
|
C
i
=
or
(
C
i
)=
,
0
≤
i
≤
j
}
.
Once a robot is able to distinguish where a supermin is located, the next lemma
provides a useful mean for computing whether the current configuration is gather-
able or not.
Lemma 1 ([
11
]).
Given a configuration C
=(
q
0
,
q
1
,...,
q
j
)
with q
i
≥
0
,
0
≤
i
≤
j:
1.
|
1
if and only if C is either asymmetric and aperiodic or it admits only one
axis of symmetry passing through the supermin;
I
C
|
=
2.
|
2
if and only if C is either aperiodic and symmetric with the axis not
passing through any supermin or it is periodic with period
I
C
|
=
n
2
;
n
3
.
3.
|
I
C
| >
2
if and only if C is periodic, with period at most
The above lemma already provides useful information for a robot when it wakes
up. In fact, during the Look operation, it can easily recognize if the configuration
contains only two robots, or if it belongs to the set
SP
4, or if
|
I
C
| >
2(i.e.,the
configuration is periodic), or in case
2, if the configuration admits an edge-
edge axis of symmetry or it is again periodic. After this check, a robot knows if
the configuration is gatherable, and proceeds with its computations. Indeed, all the
remaining configurations are shown to be gatherable.
The main strategy allows only the movements which affect the supermin. In
fact, if there is only one supermin, and the configuration allows its reduction, the
subsequent configuration would still have only one supermin (the same as before
but reduced), or a multiplicity is created. In general, such a strategy would lead
asymmetric configurations or also symmetric ones with the axis passing through the
supermin to create one multiplicity where the gathering will be easily finalized by
collecting at turn the closest robots to the multiplicity. This strategy reminds the one
used in [
22
] but with the difference to deal with the minimum rather than with the
maximum.
For gatherable configurations with
|
I
C
|
=
2, the algorithm requires more phases
before creating the final multiplicity where the gathering ends. In this case, there
are two supermins that can be reduced. If both are reduced simultaneously, then the
configuration is still symmetric and gatherable. Possibly, it contains two symmetric
multiplicities. In fact, this is the status that one wants to reach even when only one of
the two supermins is reduced. In general, the algorithm tries to preserve the original
symmetry or to create a gatherable symmetric configuration from an asymmetric
one. It is worth to remark that in all symmetric configurations with an even number
of robots, the algorithm always allows the movement of two symmetric robots. Then
after the initial movement, it is possible to obtain a symmetric configuration or an
asymmetric one with a possible
pending
move. In fact, if only one robot (among the
two allowed to move) performs its movement, it is possible that its symmetric one
|
I
C
|
=
Search WWH ::
Custom Search