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

Chapter 13
Gathering Asynchronous and Oblivious
Robots on Basic Graph Topologies Under
the Look-Compute-Move Model ∗
Gianlorenzo D'Angelo, Gabriele Di Stefano, and Alfredo Navarra
Abstract Recent and challenging models of robot-based computing systems
consider identical, oblivious and mobile robots placed on the nodes of anonymous
graphs. Robots operate asynchronously in order to reach a common node and remain
with it. This task is known in the literature as the gathering or rendezvous problem.
The target node is neither chosen in advance nor marked differently compared to the
other nodes. In fact, the graph is anonymous and robots have minimal capabilities.
In the context of robot-based computing systems, resources are always limited and
precious. Then, the research of the minimal set of assumptions and capabilities re-
quired to accomplish the gathering task as well as for other achievements is of main
interest. Moreover, the minimality of the assumptions stimulates the investigation
of new and challenging techniques that might reveal crucial peculiarities even for
other tasks. The model considered in this chapter is known in the literature as the
Look-Compute-Move model. Identical robots initially placed at different nodes of
an anonymous input graph operate in asynchronous Look-Compute-Move cycles.
In each cycle, a robot takes a snapshot of the current global configuration (Look),
then, based on the perceived configuration, takes a decision to stay idle or to move to
one of its adjacent nodes (Compute), and in the latter case it makes an instantaneous