Information Technology Reference
In-Depth Information
The lexicographically smallest sequence between the two readings from any
corner is associated to the corner itself. In rectangular grids, these two sequences
can be equal but it is possible to distinguish one of them by assuming the reading in
the direction of the smallest side.
The
minimal
sequence is defined as follows. If the configuration is symmetric, it
is the smallest sequence between the two sequences associated to the two corners
through which passes the axis of symmetry, otherwise it is the smallest among the
four sequences associated to the four corners. In any case there exists a minimal
sequence
C
=(
,
,...,
)
which identifies a single corner
c
, unambiguously.
An important property of the gathering strategy is that a robot is not allowed to
move to a corner different from
c
.
Firstitisproventhatforany
EG
configuration with no corners occupied and at
least one robot on the border there exists a strategy that leads to a configuration with
exactly one corner occupied. The idea is to reduce
q
0
by moving the robot towards
c
(or the two robots, when the configuration is symmetric) on the border which is
(are) closest to
c
. The authors show that no symmetric configuration, other than the
possible original one, can be created.
Then, it is shown that for any configuration in
EG
with more than three nodes
occupied and at least two corners occupied there exists a strategy that leads to a con-
figuration with either exactly one corner occupied or exactly three corners occupied.
Finally the main contribution is proven: Aperiodic configurations on even
q
0
q
1
q
j
×
even
grids larger than 2
2, that do not admit an axis of symmetry passing through edges,
are gatherable, without assuming any multiplicity detection.
To achieve this result, it has been first observed that the set of possible grids can
be restricted by considering the minimal even
×
even sub-grid which is centered in
the geometrical middle of the original grid and includes all the occupied nodes of it.
Such minimal
wrapping
grid is still of type even
×
even and preserves the possible
symmetry of the original one. Moreover, it always has at least an occupied node on
the border. Then it is possible to apply the first partial result mentioned above.
The proposed algorithm only uses such sub-grid without changing its size, i.e.,
it neither enlarges nor reduces the sub-grid by moving robots outside the border or
from the border to the inside.
If no corners are occupied, by reducing
q
0
, a configuration with one corner oc-
cupied can be reached. In this case, all the robots move towards
c
by reducing the
Manhattan distance to
c
and then achieving the gathering.
When two corners are occupied, as said above, it is possible to reach a configu-
ration with one or three corners occupied. In the former case the gathering can be
easily finalized, in the latter case all the robots, but those in the corners, are moved
towards the corner that does not share any coordinate with the empty corner. This
process finishes with a symmetric configuration with exactly three corners occu-
pied. In this configuration,
c
is the corner on the axis of symmetry, and the other
two robots move one step towards
c
either concurrently or alternately, until creating
a configuration with only one corner occupied.
×
Search WWH ::
Custom Search