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

move to this neighbor (Move). Cycles are performed asynchronously for each robot.
This means that the time between Look, Compute, and Move operations is finite but
unbounded, and it is decided by the adversary for each robot. Hence, robots may
move based on significantly outdated perceptions. The only constraint is that moves
are instantaneous, and hence any robot performing a Look operation perceives all
other robots at nodes of the ring and not on edges. Robots are all identical, anony-
mous, and execute the same deterministic algorithm. They cannot leave any marks at
visited nodes, nor can they send messages to other robots. In this chapter, we aim to
survey on recent results obtained for the gathering task over basic graph topologies,
that are rings, grids, and trees. Recent achievements to this matter have attracted
many researchers, and have provided interesting approaches that might be of main
interest to the community that studies robot-based computing systems.
13.1 Introduction
The chapter surveys on recent results in robot-based computing systems. Two or
more robots, starting from distinct initial positions, have to meet at some place and
remain there. The problem is known in the literature as the gathering problem while
sometimes it is referred to as the rendezvous problem.
Different assumptions on the capabilities of the robots as well as on the envi-
ronment where they move, lead to very different scenarios. To have an idea of the
work done during the recent years, it is enough to mention that already five different
surveys deal with such a problem from different perspectives. The first distinction
considers the way the robots may take their decisions in order to move towards
some directions. In fact, randomized algorithms can be applied for this purpose or
full determinism might be required. For the former case, there is a comprehensive
survey topic [ 3 ] which also includes results contained in an older survey paper [ 2 ].
The latter case has captured more attention in recent studies. In particular, for the
case where robots are considered to move along the nodes and edges of an input
graph, the survey paper [ 25 ] and in a more extended form [ 26 ] present various sce-
narios and techniques for different graph topologies. Whereas, the survey topic [ 24 ]
focuses on the gathering over ring networks. In the literature, many results also con-
cern the gathering of robots moving on a continuous two-dimensional Euclidean
space have been devised. The interested reader may refer to [ 8 , 15 , 20 , 27 , 29 ]for
the continuous case. However, a recent trend is to study discrete models like the case
where robots move over graphs rather than the continuous case.
In this chapter, the aim is to provide in more details the strategies applied to
accomplish the gathering task on basic graph topologies like rings, grids, and trees,
under a very specific model that has attracted many researchers during the last years.
Very few of such results are already contained in the aforementioned surveys. In
fact, most of the results come from very recent papers and the last section contains
original results for tree topologies.
The model considered in this chapter (sometimes also referred to as CORDA [ 27 ])
is known in the literature as the Look-Compute-Move model. Robots asynchronously