Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model - Search Theory: A Game Theoretic Perspective - page 205

NS

NS

a b

EW EW

c

d

NS

NS

EW EW

Fig. 13.6 Case of a 6 9grid.( a ) The two halves have the same number of nodes. The maximal

binary string is that read from the upper left corner which starts with

×

( 0 , 1 , 0 , 0 , 0 , 0 ,... ) .( b )-( d )

Examples of 6 9 grids with two lexicographically largest strings: ( b ) The two lexicographically

largest strings correspond to the views starting from two symmetric corners with respect to the
EW line; ( c ) The two lexicographically largest strings correspond to the views starting from two
corners residing on one of the two diagonals of the grid; ( d ) The two lexicographically largest
strings correspond to the views starting from two symmetric corners with respect to the NS line

×

Once the gathering node has been unambiguously identified by a robot during its
Compute operation, if the robot resides on the half grid where the south pole is, then
it moves towards the north pole. Note that, each time a robot in the southern half
of the grid performs such a movement, the gathering node cannot change. In fact,
two following two cases can occur: (1) the number of occupied nodes decreases in
the southern part of the grid, either because a robot moves to the northern part or
because a multiplicity is created; (2) the string associated to the corners in the south
are decreasing due to the robots' movements. In this case, the corresponding strings
defining the current configuration starting from the northern corners are increasing.
This clearly leaves unchanged the direction on the NS line. Note that the corner to
which the lexicographically largest string was associated might change during the
described process, but the only option is the other corner on the same odd side of
the original one. This preserves the direction on the NS line. By keeping on moving
in the described way, all the robots will reach the northern part. The case in which a
subset of robots from a multiplicity move, increasing the number of occupied nodes,
does not require any special argument. More precisely, since the initial configuration
does not contain multiplicities, either the minimality of the number of robots in one
half of the grid is preserved, or case (2) ensures that the lexicographically largest
string is associated to a corner in the north.