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

patrol linear spaces efficiently. In [ 5 ], an alternative performance measure based on
power consumption was used to assess efficiency of proposed rendezvous strategies.
Finally, somewhere between the model of networks and agents is agents ability
to interact with the environment. This includes ability to release special marks in
the form of stationary or mobile tokens [ 21 ] or longer messages stored in special
message repositories such as whiteboards[ 15 ].
11.3 Rendezvous
Recall that the rendezvous problem refers to the algorithmic challenge in which two
or more agents are expected to meet at the same time and point is space. The first
reference to rendezvous problem is very often attributed to political science mono-
graph [ 26 ] by Schelling, which initiated the discussion of coordination problems.
Schelling considered approach in which each of the two players have only one at-
tempt to choose the meeting location, and if they miss each other at the first attempt
they fail.
The rendezvous problem as we now know it was first informally introduced by
Steve Alpern in mid 1970s. He posed several problems including famous two:
Astronaut Problem Two astronauts land on a spherical body that is much
larger than the detection radius (within which they can see each other). The
body does not have a fixed orientation in space, nor does it have an axis of
rotation, so that no common notion of position or direction is available to the
astronauts for coordination. Given unit walking speeds for both astronauts, how
should they move about so as to minimize the expected meeting time T (before
they come within the detection radius)?