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

time as the regular 2 n problem. But can they do better? More generally, we
could have n = mr cafes partitioned into m sets of r . (Unequal partitions could

allow coordination on certain sets.)

7. Multiple agent rendezvous. The rendezvous problems can be modified so
that the goal is for n players to all meet at the same location. For example,
n astronauts could land independently with the same distribution on the
sphere.

For these problems it could be assumed that players who meet must stick to-
gether (sticky) or not. One could also look at problems where there are n
players but only k of them have to meet (say, to carry out some task). Some
references to various versions of this problem (including some in the com-
puter science literature which we have been otherwise excluding) are Alpern
[ 6 ], Lin, Morse, and Anderson [ 28 , 29 ], Baston [ 17 ], Lim, Alpern and Beck
[ 27 ], Alpern and Lim [ 14 , 26 ], Dessmark, Fraigniaud, Kowalski and Pelc
[ 20 ], Marco, Gargano, Kranakis, Krizanc and Pelc [ 30 ], Kranakis, Krizanc and
Rajsbaum [ 25 ],Kowalski and Malinoski [ 24 ], Dobrev, Flocchini, Prencipe and
Santoro [ 21 ].

8. Asynchronous rendezvous. All of the above problems assume that the
two (or more) players enter the search region, and begin their search, at the
same time. This allows some coordination.

This problem has received some attention in unpublished work of V. Baston and
A. Beck, and in the alternative optimization criteria of the theoretical computer
science approach of Marco, Gargano, Kranakis, Krizanc and Pelc [ 30 ]. See also
Lin, Morse and Anderson [ 29 ].

9. Rendezvous without proximity. The classical form of the rendezvous
search problem assumes that the problem is solved (rendezvous achieved)
when the two players meet spatially. That is, when they come within a
specified distance or, in one dimensional scenarios, when they have the
same location. However, other end conditions are possible. More generally
we could posit a subset R of Q where Q is the search region, where

the game ends when the locations of the two players form a pair in R

× Q ,

. The

classical version constitutes the diagonal.

The only problem of this type that has been explored in the literature is by the
author [ 8 ], who considered a rendezvous problem in Manhattan, where the two
players rendezvous when they arrive at a common street or avenue (and thus
can see each other without buildings coming between them). It would be useful
to develop a general theory, or perhaps simply explore another example.