Rendezvous on a line

Importance: High ✭✭✭
Author(s): Alpern, Steve
Subject: Unsorted
Recomm. for undergrads: no
Posted by: mdevos
on: September 21st, 2007

\begin{problem} Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time $R$ (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? \end{problem}

This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. See [AG2] for a thorough development of this subject. This is a \emph{symmetric} rendezvous problem since each player is forced to adopt the same strategy. If we drop this constraint, Alpern and Gal [AG] have shown that the inf expected meeting time is 3.25.

Han, Du, Vera, and Zuluaga [HDVZ] have shown that strategies in which the players move at maximum speed and only change direction at integer times dominate among all possible strategies - thus reducing this problem to a discrete one. These same authors improve upon a series of results by tightening the upper and lower bounds, proving $4.1520 < R < 4.2574$. Further, they conjecture $R=4.25$.

Bibliography

*[A] S. Alpern, The rendezvous search problem. SIAM J. Control Optim. 33 (1995), no. 3, 673--683 \MRhref{1327232}

[AG1] S. Alpern and S. Gal, Rendezvous search on the line with distinguishable players. SIAM J. Control Optim. 33 (1995), no. 4, 1270--1276. \MRhref{1339065}

[AG2] S. Alpern and S. Gal, The theory of search games and rendezvous. International Series in Operations Research & Management Science, 55. Kluwer Academic Publishers, Boston, MA, 2003. \MRhref{2005053}

[HDVZ] Q. Han, D. Du, J. C. Vera, and L. F. Zuluaga, \href[Improved bounds for the symmetric rendezvous search problem on the line]{http://www.optimization-online.org/DB_FILE/2006/05/1400.pdf}


* indicates original appearance(s) of problem.