Information Technology Reference
In-Depth Information
A
x
x
a = 1
B
x
B
x
= b = 2
b = 2
b
y
y
y
y
C
C
z
z
= c =
1
c = 1
c
z
z
d = 3
D
Fig. 13.2
A symmetric configuration and its representation
with an even number of robots but asymmetric, with an even number of robots
admitting a robot-robot axis of symmetry, and with more than 18 robots admitting
a node on the axis of symmetry. This has left open the cases of an even number of
robots between 4 and 18 admitting a node on the axis of symmetry. Note that, the
cases left for few robots might require more effort and different techniques for the
resolution. In fact, lesser the robots lesser the information encoded by their disposal.
This encouraged further investigation on configurations with few robots.
Gatherable configurations with four robots have been addressed in [
16
,
23
]. The
main idea is still to define a North and a South pole on the axis of symmetry (of
type node-node). Then similarly to [
21
], the two northern nodes are moved while
preserving the symmetry until creating a multiplicity on the North pole. After that,
the other two robots join the multiplicity, hence finalizing the gathering.
The case of six robots is more intriguing as it requires different techniques from
the older ones in order to fully characterize the gatherable configurations. It has
been addressed in [
9
]. A symmetric configuration can be represented as shown in
Fig.
13.2
. In detail, without multiplicities, the ring is divided by the robots into 6
intervals:
A
,
B
,
C
,
B
,
C
,and
D
with
a
,
b
,
c
,
b
,
c
,and
d
free nodes, respectively.
In the case of node-edge symmetry,
A
is the interval where the axis passes through
a node and
D
is the interval where the axis passes through an edge; in the case
of node-node symmetry,
A
and
D
are the intervals such that either
a
<
d
or
a
=
d
and
b
c
cannot occur as it generates two axis
of symmetry. Note that, in the case of node-node symmetry,
a
and
d
are both odd,
while, in the case of node-edge symmetry,
a
is odd and
d
is even. Robots between
A
and
B
(
B
, respectively) are denoted by
x
(
x
, respectively); those between
B
and
C
(
B
and
C
, respectively) are
y
(
y
, respectively); those between
C
(
C
, respectively)
and
D
are
z
(
z
, respectively), see Fig.
13.2
.
A robot
r
<
c
; the case where
a
=
d
and
b
=
x
,
y
,
z
}
∈{
x
,
y
,
z
,
can perform only two moves: it moves
up
(
r
↑
)ifit
goes towards
A
;itmoves
down
(
r
) if it goes towards
D
.
The main idea of the algorithm is to perform moves
x
↓
,
x
↑
and
y
↑
, with
the aim of preserving the symmetry and gathering in the middle node of interval
A
, where the axis is directed. In some special cases, it may happen that the axis of
symmetry changes at run time. Before multiplicities are created, the algorithm in a
symmetric configuration allows only two robots to move in order to create a new
symmetric configuration.
↑
,
y
↑
Search WWH ::
Custom Search