Information Technology Reference
In-Depth Information
Besides the gathering problem, the Look-Compute-Move model has been studied
also for the problem of
graph exploration with stop
and
exclusive perpetual graph
exploration
[
4
-
6
,
12
-
14
]. In the first problem [
12
-
14
], it is required that each node
(or each edge) of the input graph is visited for a finite number of times by at least one
robot and, eventually, all the robots have to stop. This implies that after performing
the exploration step, the algorithms need some mean to empower the robots by the
capability of recording the part of the graph that has been already explored. Since the
robots are oblivious, this task is performed by identifying particular configurations
of the robots indicating that the exploration task has been accomplished. The exclu-
sive perpetual graph exploration [
4
-
6
] requires that each robot visits each node of
the graph infinitely many times. Moreover, it adds the constraint that no two robots
should concurrently be on the same node or cross the same edge.
13.1.1 Outline
The chapter is organized in three main sections, dictated by the graph topologies
considered. The next section provides techniques and results for the gathering on
ring networks. In particular, the section is divided in three parts. First, impossibility
results concerning the gathering on rings are summarized. Those hold even though
the global-strong multiplicity detection is assumed. Then, results for the case of
global-weak multiplicity detection are shown. Under such assumptions, all possi-
ble initial gatherable configurations have been addressed. Finally, partial results for
the case of local-weak multiplicity detection are described. In Sect.
13.3
, the prob-
lem for grids is fully characterized even when no multiplicity detection is assumed.
Similarly, in Sect.
13.4
a full characterization without any multiplicity detection ca-
pability is provided for tree topologies. This is indeed an original contribution of
the chapter. Finally, Sect.
13.5
concludes the chapter and outlines some possible
research directions for robot-based computing systems.
13.2 Gathering on Rings
In this section, the gathering over ring networks is presented. After providing
some necessary definitions, impossibility results are summarized when the global-
strong multiplicity detection is assumed. Then, differences between the case of
global-weak and local-weak multiplicity detection assumptions are presented. In
particular, when the global-weak multiplicity detection is assumed, a full character-
ization of the gatherable configurations is provided. Whereas, when the local-weak
multiplicity detection is assumed, only some sub-cases are solved. However, the
different techniques used to accomplish the gathering task among the approached
scenarios are very interesting for further investigations in robot-based computing
systems.
Search WWH ::
Custom Search