Information Technology Reference
In-Depth Information
13.3 Gathering on Grids
In this section, results achieved in [ 10 ] are reported. The authors consider the gath-
ering problem on an anonymous and undirected grid of n
n .
The main assumption that distinguish these results from those obtained on rings is
the lack of any multiplicity detection capability: if a node is occupied by more than
one robot, it is not perceived by the robots, even if they reside on such a node.
Initially, each node is occupied by at most one robot. During a Look operation,
a robot perceives the relative locations on the grid of occupied nodes, regardless of
the number of robots at a node.
The current configuration of the system can be described in terms of the view of
a robot r which is performing the Look operation at the current moment. A configu-
ration seen by r is denoted as an n
×
m nodes, with m
×
m matrix M that has elements belonging ot the
set
. Value 0 represents an empty node, and 1 represents an occupied node.
Since the grid is anonymous and undirected, each robot can perceive the current
configuration with respect to different rotations and reflections leading to any view
of the grid satisfying the n
{
0
,
1
}
×
m dimension. In particular, when n
=
m each of the
four rotations and four reflections provides a feasible view.
Definition 2. A configuration is periodic if it is invariant with respect to rotations
of 90 or 180 , where the rotation point coincides with the geometric center of the
grid.
Definition 3. A configuration is symmetric if it is invariant after a reflection with
respect to a vertical, horizontal, or diagonal (in case of square grids) axis passing
through the geometric center of the grid.
13.3.1 Odd
×
Odd Grids
This case is trivially solvable, in fact in odd
odd grids, a robot can always detect,
during its Look operation, the central node of the grid M
×
[ 2 , 2 ]
, regardless of
its possible view. This means that all the robots can move toward the center, concur-
rently.
13.3.2 Odd
×
Even Grids
In this case, the gathering is not always feasible. In fact, similarly to the ring case
on periodic or symmetric configurations of type edge-edge [ 22 ], if a configuration
C is periodic, or symmetric with respect to an axis passing through the edges (i.e.,
dividing the grid into two halves from the even side), then C is ungatherable.
Search WWH ::




Custom Search