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

Chapter 14
Ten Open Problems in Rendezvous Search

Steve Alpern

Abstract The rendezvous search problem asks how two (or more) agents who are
lost in a common region can optimize the process by which they meet. Usually they
have restricted speed (unit speed in the continuous time context; moves allowed to
adjacent nodes in discrete time). In all cases the agents are not aware of each other's
location. This chapter is concerned with the 'operations research' version of the
problem - where optimization of the search process is interpreted as minimizing the
expected time to meet, or possibly maximizing the probability of meeting within a
given time. The deterministic approaches taken by the theoretical computer science
community will not be considered here.

14.1 Introduction

A precursor of the rendezvous problem is the work of Schelling [ 32 ] on the coor-
dination of meeting places (focal points). However these one-shot games lack the
main ingredient of search, namely that the process continues after each failure to
meet until (hopefully) the rendezvous is achieved. The rendezvous search problem
was first proposed by the author at the end of a talk on search games given in Vienna
in 1976 [ 1 ].
We shall be mainly concerned with the so called symmetric ,or player

−
symmetric form of the problem, where both players (agents) must adopt the same
rendezvous strategy, though when using mixed strategies they must randomize inde-
pendently. This version is said to have indistinguishable agents . For example if two
players, Tom and Mary, were trying to rendezvous on a circle drawn on the plane,
we would not allow the solution where Tom proceeds clockwise and Mary counter-
clockwise. The symmetric solution could be written in a topic on rendezvous so that