Ten Open Problems in Rendezvous Search - Search Theory: A Game Theoretic Perspective - page 213

when two people find themselves faced with the rendezvous problem they could
read what to do in this topic, without having decided beforehand on which roles
(e.g. clockwise or counter-clockwise) to play. The asymmetric version allows Tom
and Mary to agree beforehand on which roles to take: for example one could wait
while the other searches (the Wait f or Mommy strategy).
14.2 The Problems
We now list some rendezvous problems which are unsolved. When partial solutions,
or solutions to special cases have been found, we will mention this afterwards.
1. The astronaut problem. Two unit speed astronauts land simultaneously
on a small smooth sphere. They walk at the same speed and can detect
each other when they are a given distance apart. What is the least expected
meeting time they can guarantee, and what strategies should they use to
achieve this time?
As far as we are aware, no significant progress has been made on this prob-
lem. An easier version would spin the sphere, so that the two poles would be
focal points. Even the latter problem seems to be open, though some sort of
randomized oscillation between the poles would seem to be useful in the latter
problem. But how long should one wait before heading for the other pole? A
lower dimension analog of this problem is given next.
2. Rendezvous on a circle. Two players are uniformly and independently
placed on a circle, without any common sense of direction (or of up ,if
the circle is drawn on a plane). They move at unit speed and must use the
same mixed strategy. Determine the least expected meeting time.
It has been conjectured by the author that the solution of this problem is for both
players to use the so called cohato (coin half tour) strategy: oscillate between
your starting point and its antipode, each time choosing equiprobably and inde-
pendently of prior choices between your clockwise and your counter-clockwise
(or simply choose two directions and do one if Heads and the other if Tails on
the coin). Simpler versions of this problem, where the players have some addi-
tional information or common notions, have been solved by Howard [ 22 ]and
Alpern [ 4 , 6 ].