Information Technology Reference
In-Depth Information
c
1
c
2
c
3
c
4
Fig. 13.7
Case of a 6
×
10 grid. The
arrows
indicate the horizontal direction of the reading
from corner
c
1
,itgives
(
6
,
8
,
14
,
10
,
5
,
12
)
. The other seven sequences read by the robots are:
(
3
,
6
,
20
,
4
,
9
,
13
)
from
c
1
vertically,
(
3
,
10
,
24
,
2
,
5
,
11
)
and
(
16
,
1
,
6
,
26
,
4
,
2
)
from
c
2
horizontally
and vertically, respectively,
(
12
,
5
,
10
,
14
,
8
,
6
)
and
(
13
,
9
,
4
,
20
,
6
,
3
)
from
c
3
,
(
11
,
5
,
2
,
24
,
10
,
3
)
and
(
2
,
4
,
26
,
6
,
1
,
16
)
from
c
4
.The
minimal
sequence is
(
2
,
4
,
26
,
6
,
1
,
16
)
and
c
=
c
4
Once all the robots belong to one half of the grid, then they are allowed to move,
during their Move operation, towards the gathering node. In fact, such a node is
well-defined and cannot change as the robots are not allowed to move to the other
half of the grid.
13.3.3 Even
×
Even Grids
In this section, the case of grids whose sides are both even is studied. Also in this
case, there are some configurations which are ungatherable, namely the periodic
configurations and those configurations having a vertical or a horizontal axis of
symmetry. In [
10
], it is shown that all the other cases are gatherable without any
multiplicity detection, but for the case of 2
×
2grids.
2 grids, configurations with two or four nodes occupied are ungather-
able due to periodicity and edge-edge symmetries. If three nodes are occupied with
robots having the local-weak multiplicity detection, the configuration is gatherable
by moving the robot in between the other two occupied nodes arbitrarily, and then
moving the robot not in the multiplicity towards the other occupied node. Hence,
the remaining gatherable configurations are the aperiodic, asymmetric, and those
with only one axis of symmetry passing through the diagonal of a square grid
of dimensions larger than 2
On 2
×
2. All such configurations are referred to as the set
EG
(Even-Gatherable) and it is proved that all the configurations in
EG
are indeed
gatherable without any multiplicity detection. In order to achieve this results, it is
first assumed that at least one node on the border of the grid is occupied. Then,
the gathering node is identified among the eight sequences of distances (number
of empty nodes) between occupied nodes obtained by traversing the grid starting
from the four corners and proceeding towards the two possible directions (see, e.g.
Fig.
13.7
).
×
Search WWH ::
Custom Search