Rendezvous Problem - Search Theory: A Game Theoretic Perspective - page 158

One of the novel, promising, and perhaps challenging alternatives in supporting
such network protocols are dedicated teams of mobile entities that can work inde-
pendently on top of basic network processes. Mobile entities may, e.g., represent
software agents [ 22 ] residing in nodes or traversing through network connections,
autonomous mobile robots [ 27 ] located in a (real) geometric environment, or a group
of people that have to meet in a city whose streets form a road network [ 2 ]. The
structure of the network environment can be stable or it can change in time due
to accidental failures, mobility or instability of objects including malicious perfor-
mance of nodes, unwanted visits of intruders, etc.
Apart from populating network environments, teams of mobile entities can be
also seen as more complex systems on their own. For example, a traditional com-
munication network can be replaced by a more arbitrary environment in which a
collection of networked or free-standing agents representing groups of humans, ani-
mals, vehicles or specialised robots are asked to perform a dedicated computational
task. This could be done in the form of a fully-coordinated effort or as a collection
of (semi-)independent individual (possibly greedy) performances.
Rendezvous of mobile entities (agents, players) is often a goal on its own.
Alternatively, it can be used as a subroutine in a range of basic network integrity and
coordination mechanisms. The agent's ability to act autonomously including obser-
vation, communication and relocation impels the design and further implementation
of efficient communication and navigation mechanisms.
11.2 Models
In this section we briefly survey basic properties of network environments and
agents populating them. A specific choice of network and agents attributes results
in a certain type of the rendezvous problem. This type refers to the difficulty of the
problem and in turn to the efficiency of possible algorithmic solutions.
11.2.1 Networks
Recall that we consider two types of network environments: graph based and ge-
ometric. In the graph based representation the nodes of the network may not have
distinct identities. In such case we say that the network is anonymous. In anonymous
networks two nodes of the same degree are virtually impossible to distinguish. In
order to enable navigation in such networks all edges incident to a given node are
either explicitly or implicitly arranged in a periodic order.
A network can be either finiteor of unboundedinsize. In the latter case one needs
to design search protocols that preserve locality of the solution. Otherwise the com-
plexity of the solution could be unbounded. Another important network attributes