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

When no robots reside on the axis, the algorithm works in four phases. During
the first phase, since the configuration is symmetric, two robots are always allowed
to move. In order to detect the two symmetric robots that must perform their moves,
the robots have to elaborate the perceived configuration during their Compute phase.
Based on the sequence of distances between robots along the ring, two symmetric
minimal interval are detected and reduced concurrently, until two multiplicities are
created. The number of robots grater than 18 comes from this computational step. In
fact, the need to guarantee to break possible ties among minimal intervals, and the
fact that some robots are needed between the detected intervals and the two poles
defined by the axis of symmetry on the ring, gives a minimal number of required
robots equal to 20.
It is very important to remark that the proposed technique is the first one that
forces robots to maintain the original symmetry rather than breaking it. In fact, based
on the perceived configurations, robots are always able to detect whether the current
configuration is at one step from a reachable symmetry or not. In the latter case,
the algorithm from [ 22 ] for asymmetric configurations can be applied. In the former
case, the robot that can re-establish the symmetry will be the only one allowed to
move. Note that, such a robot could have been already started its Look-Compute-
Move cycle concurrently with its symmetric one, or it simply starts later. In any
case, the algorithm guarantees to recover the original symmetry with two steps less
towards the desired configuration with two multiplicities where the second phase
starts.
When two multiplicities have been created, the idea is to move all the remain-
ing single robots but few of them towards the two multiplicities. During the second
phase, it is necessary to decide on one of the two poles of the axis of symmetry
as the gathering point (the North pole). The poles are chosen so that the northern
arc between multiplicities contains more robots than the southern arc; in the case
of a tie, the side on which the nearest robots are closer to the multiplicities is the
northern one. The robots are moved in symmetrical pairs towards their respective
multiplicities, starting from the robots on the northern arc. In this way, North and
South are consistently preserved throughout the phase. The phase ends with two
multiplicities, two symmetric robots located at the southern part far from the multi-
plicities of at least one node, and two symmetric robots located at the northern part
neighbors of the multiplicities. The two robots on the south are called guards .
The third phase is based on the position of the guards that maintain the direction
to the gathering node. During this phase, the remaining single robots and those
belonging to the multiplicities can move towards the North pole. The movement
is performed always maintaining the robots associated to each multiplicity either
as part or as neighbors of it. In this way, the configuration pattern is maintained
throughout the process, until all robots except for the guards gather at the North
pole in a single multiplicity.
The fourth phase simply moves the guards towards the multiplicity, and the
gathering will be eventually finalized.
The algorithm has been also integrated with the one from [ 22 ], hence obtaining a
full characterization of the gatherable configurations with an odd number of robots,