Two friends have become separated in a building or shopping mall and and wish to meet as quickly as possible. There are n possible locations where they might meet. However, the locations are identical and there has been no prior agreement where to meet or how to search. Hence they must use identical strategies and must treat all locations in a symmetrical fashion. Suppose their search proceeds in discrete time. Since they wish to avoid the possibility of never meeting, they will wish to use some randomizing strategy. If each person searches one of the n locations at random at each step, then rendezvous will require n steps on average. It is possible to do better than this: although the optimal strategy is difficult to characterize for general n, there is a strategy with an expected time until rendezvous of less than 0.829 n for large enough n. For n = 2 and 3 the optimal strategy can be established and on average 2 and 8/3 steps are required respectively. There are many tantalizing variations on this problem, which we discuss with some conjectures. DYNAMIC PROGRAMMING; SEARCH PROBLEMS In this paper we introduce a new class of problems concerned with two players who wish to meet as quickly as possible. The problem we describe has some unusual features and gives rise to a bewildering number of related problems, many of which appear to be interesting in their own right. In the last part of this paper we give a brief review of some of these related problems, together with a number of conjectures and open problems. Perhaps the best way to introduce the problem is to suppose that two people become separated in a building, a department store for example, and wish to meet again. If they have no prearranged plan to deal with this situation, it will not be easy to decide what to do. Should one of them stay where he or she is until found by the other? And, if so, for how long should they wait (since perhaps they have both decided to stay still)? The simplest mathematical formulation which captures some of the features of this situation is to suppose that there are n different locations in the building, and
In asymmetric rendezvous, the optimal strategy is for a robot with a known ID to remain still while the other robot visits every vertex REF .
The Rendezvous Problem on Discrete Locations
Journal of Applied Probability
Mathematics