Information Technology Reference
In-Depth Information
In the first phase, the robots move towards the d -blocks with the biggest size.
By using the hypothesis of an odd number of robots, the d -blocks of biggest size
can merge together in order to create a unique d -block. The obtained configuration
is symmetric and, as the number of robots is odd, there is a robot on the axis of
symmetry. The algorithm proceeds by moving the two robots adjacent to that on the
axis of symmetry towards it, achieving a
-block of size 2 or 3. The algorithm
is then iterated until a single 1-block is achieved.
The second phase starts with a configuration with a single 1-block. Note that
this configuration is symmetric and has a robot r on the axis of symmetry. The
algorithm moves the two robots adjacent to r towards it, creating a multiplicity (see
Fig. 13.4 a). If the two robots move synchronously, the configuration achieved is
still symmetric and a multiplicity containing r is created on the axis of symmetry
(see Fig. 13.4 c). Due to the asynchronicity, only one of the two robots adjacent to
r can move, creating a configuration made of two 1-blocks separated by an empty
node (see Fig. 13.4 b). Such configuration can be distinguished by observing that
this is the only case where the number of occupied nodes is even. Hence the robot
which did not move can easily identify itself and perform the correct move. In the
obtained configuration, the neighbors of the multiplicity on the axis are two empty
nodes followed by two 1-blocks. At this point, the algorithm moves the two robots
on the border of the 1-blocks that are closest to the multiplicity, towards it. For
the hypothesis of asynchornicity, it can occur that three 1-blocks are created (see
Fig. 13.4 d). In this case, the robot that has to move can be identified thanks to the
hypothesis that the number of occupied nodes is always smaller that n
(
d
1
)
3. In fact, in
these configurations, the 1-blocks are interleaved by two single empty nodes and by
a path of empty nodes of size at least three. By iterating this process, a new 1-block
a
c
b
Fig. 13.5 Third phase of the gathering algorithm for an even number of robots in an odd ring
with local-weak multiplicity detection capability. A multiplicity is denotes as a circle around an
occupied node
is created with the size reduced by 2 with respect to the original 1-block and where
there is a multiplicity on the axis of symmetry (see Fig. 13.4 g). The algorithm is then
iterated until the gathering is achieved. In the final step of the algorithm a single 1-
block of size 2 can be created as a consequence of asynchronicity (see Fig. 13.4 i).
Search WWH ::




Custom Search