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

run an operative cycle where first they perceive the global configuration of the robots
over the graph (Look phase). That is, during the Look phase a robot is able to per-
ceive the relative locations of the other robots with respect to its own position on
the graph. The only cases where a robot might be misled concern the so called
multiplicities , i.e., when more than one robot occupy the same node. In this case,
different assumptions might be considered. Based on the perceived configuration
which might reveal the exact disposal of all the robots or just which nodes are occu-
pied, a robot evaluates whether to stay idle or to move towards one of its neighbor-
ing nodes (Compute phase). Note that, since robots are asynchronous, the Compute
phase might be accomplished by a robot based on outdated configurations perceived
while other robots are performing their movements. Finally, the robot enters to the
Move phase, where it simply applies the computed movement. Hence, it either re-
mains on its current position or it moves towards the computed neighboring node.
The only assumption in this phase is that the movements are instantaneous and hence
robots are always perceived over nodes, and never over edges. Robots are all iden-
tical, anonymous, and execute the same deterministic algorithm. They cannot leave
any marks at visited nodes, nor send messages to other robots. The scheduler that
wakes the robots up is assumed to be fair, i.e., all the robots will wake up, eventually,
and perform their Look-Compute-Move cycles infinitely many times.
Another assumption that can be considered concerns the ability for the robots to
perceive information about the number of robots occupying the same node, during
the Look operation. This ability is called the multiplicity detection capability and
it has been sometimes exploited in various forms. In any case, a robot perceives
whether a node is empty or not, but in the global-strong version, a robot is able
to perceive the exact number of robots that occupy each node. In the global-weak
version, a robot perceives only whether a node is occupied by one robot or if a
multiplicity occurs, i.e., a node is occupied by an undefined number of robots greater
than one. In the local-strong version, a robot can perceive only whether a node is
occupied or not, but it is able to perceive the exact number of robots occupying the
node where it resides. Finally, in the local-weak version, a robot can perceive the
multiplicity only on the node where it resides but not the exact number of robots
composing it.
In the context of robot-based computing systems, resources are always limited
and precious. Then, the research of the minimal set of assumptions and capabili-
ties required to accomplish the gathering task as well as for other achievements is of
main interest. Moreover, the minimality of the assumptions stimulates the investiga-
tion of new and challenging techniques that might reveal crucial peculiarities even
for other tasks.
Depending on the multiplicity detection capability version chosen for the robots,
some scenarios may be unsolvable while some others are solvable. Intuitive concepts
like symmetry or periodicity might be involved and sometimes are fundamental to
the feasibility of the studied problems. Depending on the assumptions made, the def-
inition of such concepts may vary and require different approaches. This is why in
what follows, the same concept might be re-defined according to the current scope.
Moreover, the considered scenarios lead to very interesting and different strategies
that can be considered also for other areas of applications.