Information Technology Reference
In-Depth Information
In [
19
], the authors provide and algorithm for the case where
n
is odd,
k
is even,
and 10
5. The remaining cases are still open and a unified algorithm like
that for the case where the global-weak multiplicity detection capability is allowed
is still not known. In the following, the mentioned algorithms are summarized.
≤
k
≤
n
−
<
2
13.2.3.1 Asymmetric Configurations with
k
This algorithm assumes, without loss of generality, that a configuration view seen
by a robot is the lexicographically maximal that the robot can read, instead of the
lexicographically minimal as it was in the case of global-weak multiplicity detec-
tion. These two assumptions are equivalent thus in the rest of the chapter we keep
on using the one in [
17
]. As the configuration is asymmetric, by Property
2
,the
views seen by the robots are all different. Therefore, let
C
=(
q
0
,
q
1
,...,
q
j
)
be the
lexicographically maximal configuration view,
j
k
,and
r
i
be the robot (or the set
of robots in the case of a multiplicity) before the interval
q
i
of empty nodes. First,
an algorithm to achieve the gathering for the case where
q
0
≥
≤
2isgiven.
Then, a strategy to create a configuration of the above type starting from a config-
uration where
q
0
≥
3and
q
1
≥
2 is devised. Finally, the case to increase
q
0
from
2 to 3 is addressed. As it is assumed that
k
3and
q
1
<
<
2
and
q
0
is the maximal interval,
then
q
0
cannot be smaller than 2. All the three algorithms keep the configuration
asymmetric and aperiodic. Here, the algorithm for the case where
q
0
≥
3and
q
1
≥
2
is described, while the details for the other cases can be found in [
17
].
The idea is to generate a configuration with only two occupied nodes where
k
1
robots are gathered on the same node and the other occupied node contains a single
robot. From this configuration the robots can distinguish which is the node occu-
pied by a single robot by using the local-weak multiplicity detection. Therefore, the
single robot moves towards the multiplicity, eventually achieving the gathering.
The algorithm when at least three nodes are occupied (
j
−
≥
2) is as follows.
R1: If
q
j
≥
1 move
r
0
towards
q
j
;
R2: If
j
=
2,
q
j
=
0, and
q
j
−
1
≥
1
R2-1: If
q
0
is the only maximum interval of empty nodes, move
r
j
towards
q
j
−
1
;
R2-2: Otherwise move
r
1
towards
q
1
;
R3: If
j
=
2,
q
j
=
0, and
q
j
−
1
=
0 move
r
0
towards
q
j
;
R4: If
j
=
2and
q
2
=
0 move
r
0
towards
q
2
;
First, it is assumed that
q
0
is the only maximum interval of empty nodes. The
algorithm allows moves where
q
0
is increased,
q
1
is not changed,
q
j
is kept shorter
than
q
1
, and the other intervals are decreased. This ensures that
q
0
remains the only
maximum interval of empty nodes. The algorithm starts by moving the robots
r
0
towards
q
j
until they become neighbors of robots in
r
j
(see rules
R1
and
R3
). Then
robots in
r
j
move towards
q
j
−
1
until they become neighbors of robots in
r
j
−
1
(see
rule
R2-1
). At this point the robots in
r
0
join those in
r
j
. By applying these rules,
Search WWH ::
Custom Search