THE RENDEZVOUS SEARCH PROBLEM

The author considers the problem faced by two people who are placed ra ndomly in a known search region and move about at unit speed to find e ach other in the least expected time. This time is called the rendezvo us value of the region. It is shown how symmetries in the search regio n may hinder the process by preventing coordination based on concepts such as north or clockwise. A general formulation of the rendezvous se arch problem is given for a compact metric space endowed with a group of isometries which represents the spatial uncertainties of the player s. These concepts are illustrated by considering upper bounds for vari ous rendezvous values for the circle and an arbitrary metric network. The discrete rendezvous problem on a cycle graph for players restricte d to symmetric Markovian strategies is then solved. Finally, the autho r considers the problem faced by two people on an infinite line who ea ch know the distribution of the distance but not the direction to each other.