Information Technology Reference
In-Depth Information
ties and performs phase
MULTIPLICITY
-
CREATION
whose aim is to create one mul-
tiplicity where all the robots will eventually gather, or a symmetric configuration
with two multiplicities. In the former case, phase
CONVERGENCE
is performed to
gather all the robots into the multiplicity. In the latter case, phases
COLLECT
and
then
MULTIPLICITY
-
CONVERGENCE
are performed in order to first collect all the
robots but two into the two multiplicities and then to join the two multiplicities into
a single one. After that, phase
CONVERGENCE
is performed. Special cases of six
robots on a seven nodes ring are considered separately in phase
SEVEN
-
NODES
.
In each phase, the robots can distinguish the type of configuration and apply the
suitable strategy/move. The way a robot can identify the type of configuration is
based on basic and simple calculations. Given a configuration
C
=(
q
0
,
q
1
,...,
q
j
)
,
a robot compute the following parameters:
1. Number of nodes in the ring,
n
(
C
)
;
2. Number of multiplicities,
m
;
3. Number of nodes occupied or number of robots in the case without multiplici-
ties,
OCCUPIED
(
C
)
;
4. Distance between single robots and multiplicities;
5. If
C
is symmetric;
6. If
C
is at one move from one of the symmetries allowed by the algorithm.
(
C
)
Parameters 1-3 can be computed by formulas
n
(
C
)=
∑
(
q
i
+
1
)
,
m
(
C
)=
q
i
≥
0
|{
, respectively. The dis-
tance between single robots and multiplicities is easily computed by summing the
intervals between a single robot and a
mu
ltiplicity. The symmetry of a configuration
is computed by checking whether
C
q
i
=
−
1
,
0
≤
i
≤
j
}|
,and
OCCUPIED
(
C
)=
j
+
1
−
m
(
C
)
j
.
To understand when
C
is at one move from a symmetry allowed by the algorithm,
it is sufficient to simulate such a move backwards and checking whether the obtained
configuration is symmetric.
Based on the perceived configuration, and once calculated the above parameters,
a robot is able to answer to basic questions that check the accomplishment of the
gathering task. In particular, a robot can distinguish if the current configuration is
gatherable, which type of configuration it perceived, which strategy/move should be
applied, if it is allowed to move and towards which direction.
The algorithm solves all the gatherable cases, hence closing also the ones left
open by other strategies. However, different assumptions on the model may consti-
tute very interesting directions for further investigations.
=
C
i
for some 0
≤
i
≤
13.2.3 Local-Weak Multiplicity Detection
Using the local-weak multiplicity detection capability, not all the cases has been
addressed so far. In [
17
], it has been proposed an algorithm for the case of rigid
initial configurations where the number of robots
k
is strictly smaller than
2
.
In [
18
], the case where
k
is odd and strictly smaller than
n
−
3 has been solved.
Search WWH ::
Custom Search