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

MULTIPLICITY-CREATION COLLECT

MULT.-CONVERGENCE

CONVERGENCE

SEVEN-NODES

Fig. 13.3 Phases interchanges

either has not yet started its Look phase, or it is taking more time. If there might be
a pending move, then the algorithm forces it before any other decision.
In contrast, asymmetric configurations cannot produce pending moves as the
algorithm allows the movement of only one robot. In fact, it reduces the unique
supermin by deterministically distinguish among the two adjacent robots, until one
multiplicity is created. Finally, all the other robots will join the multiplicity one-by-
one. In some special cases, from asymmetric configurations at one “allowed” move
from symmetry (i.e., with a possible pending move), robots must guess which move
would have been realized from the symmetric configuration, and force it in order to
avoid unexpected behaviors. By doing this correctly, the algorithm eventually brings
the configuration to have two symmetric multiplicities as above. From here, a new
phase that collects all the other robots but two into the multiplicities starts. Still the
configuration may move from symmetric configurations to asymmetric ones at one
move from symmetry. Once the desired symmetric configuration with two multi-
plicities and two single robots is reached, a new phase starts and moves the two
multiplicities to join each other. The node where the multiplicities join represents
the final gathering location. This strategy reminds the one used in [ 21 ]asittriesto
preserve the symmetry until the guards can join all the other robots in the gathering
node.
Actually, sometimes the strategy that affects only the supermin cannot be applied,
as a move may produce some undesired “side-effects”, i.e., leading the configuration
to ungatherable cases. In order to cope with such cases, two other moves have been
defined. However, it can be shown that a robot is always able to understand the
correct move to be performed.
An alternative move is to try to reduce the second supermin, i.e., the supermin of
the configuration is evaluated after the real one. Another move, called XN , is applied
when specific configurations occur. The definition of XN and the description of the
cases where it must be applied are not provided in this chapter.
The algorithm works in five phases and depends on the configuration perceived
by the robots, see Fig. 13.3 . First, it starts from a configuration without multiplici-