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

refer to localisation mechanism (knowledge of the current location) and sense of
direction. For example, in the geometric setting these two refer to the system of
coordinates accompanied by geographic directions. Sense of direction turned out to
greatly effect the solvability and efficiency of solution of a number of problems in
distributed computing [ 19 ] and has been shown to be important in rendezvous as
well [ 8 ].
Another crucial property refers to global clock availability. In particular, in
a synchronous network one assumes access to the global clock allowing agents
to coordinate their actions, including moves, using time frames. In contrast, in
asynchronous networks the speed with which agent compute and move cannot be
determined. In this case rendezvous is obtained either by adoption of predefined tra-
jectories [ 29 ] or through analysis of the current configuration of the network [ 25 ].
The network can be reliable or it can report to its users imprecise information. In
such error prone network rendezvous time can be largely elongated or meeting may
prove to be impossible [ 18 ].
11.2.2 Agents
One of the major attributes of agents is their identity (e.g., a distinct label) that for
some reason may be missing. Agents without identities are referred to as anony-
mous agents. Anonymous agents must execute the same procedure while agents
with unique identities have the potential to behave differently. Another important
attribute of agents is their initial knowledge. This may refer to the network size and
topology as well as to the number, identities and location of available agents. In this
context it is important whether agents can learn (adapt) throughout the rendezvous
process or whether their control mechanism remains unchanged. In the latter case
we say that the agents are oblivious. The process of learning, adaptivity of agents
depends on their memory as well as on observation and communication abilities.
For example, in some models it is assumed that agents are memoryless, where the
agents rely on the use of random walk procedure [ 12 ]. The random walk is an exam-
ple of a randomised procedure requiring access to random bits. As discussed later in
this chapter in some instances of the rendezvous problem feasibility of the solution
relies on symmetry breaking that cannot be implemented without a random number
generator.
Agents may also have zero visibility without being able to communicate re-
motely [ 14 ]. In such cases the only way in which agents can learn about presence of
one another is via spatial rendezvous. In some other extreme cases agents can con-
stantly monitor movement of the others as it is assumed in the Look-Compute-Move
model [ 25 ].
An interesting aspect of movement coordination of agents equipped with dif-
ferent maximal speeds has been recently studied in the context of network pa-
trolling [ 13 ]. The authors proposed a number of algorithms that allow agents to