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

3. Rendezvous on the infinite line (agent-symmetric form). In this version
of the rendezvous problem, the two players are randomly placed on a com-
mon line and try to find each other. Even for the apparently simpler version
where the initial distance (taken for simplicity as 2) is known, the problem
is open.

It has been shown by Lim, Alpern and Beck [ 27 ] and Qiaoming, Du, Vera and
Zuluaga [ 31 ] that the players can optimally restrict their mixing to strategies
which move at unit times along the integer lattice determined by their starting
point. So anyone trying to solve this problem can restrict their search to these
simple strategies.
The author has recently established by a compactness argument that the least
expected time and optimal strategies exist (not just

optimal ones). The au-
thor initially [ 2 , 3 ] suggested the strategy where in each time period of length
3 the players independently chose a forward direction and then move forward,
back, back. This strategy is easily seen to have expected meeting time 5/2. It
has been bettered by strategies using longer sequences of moves, by Anderson
and Essegaier [ 15 ], Baston [ 17 ], Uthaisombut [ 34 ], Alpern [ 7 ]andHanetal.
[ 31 ]. Currently the best estimates combine to give 2

ε −

R s

. 091 ≤ ≤ 2 . 128 7 .

4. Rendezvous on the infinite line (agent-asymmetric form). In this version
of the problem, the cumulative distribution function F

of the initial dis-
tance d between the players is given. In general, this is an easier problem,
though a solution for general F is not known.

( d )

In the case where the initial distance d is given, the solution was found by
Alpern and Gal [ 11 ], and the least expected meeting time is 13 d

Further
progress was made when Alpern and Howard [ 13 ] showed that the problem
was equivalent to a single agent problem where a single searcher seeks to find
an object hidden at one of two possible locations, where each location must
be searched in a given order and alternation between locations is costless (the
alternating search problem ). Using this approach Alpern and Beck [ 10 ]were
able to solve the problem for the case where d has a convex distribution on an
interval

/ 8 .

In these cases the solution is a variation on the so called Wait For
Mommy strategy, where one player (Baby) waits while the other carries out an
optimal search for an immobile hider. In the variation, Mommy doesn't change
her strategy, but Baby moves to meet Mommy. These solutions don't apply to
the symmetric problem because they require coordination in the assignment of
roles (Baby, Mommy) to the players.

[ 0 , D ] .