Rendezvous Search on the Line with Indistinguishable Players
Edward James Anderson, Skander Essegaier · SIAM Journal on Control and Optimization · 1995
Alpern introduced a problem in which two players are placed on the real line at a distance drawn from a bounded distribution F known to both. They can move at maximum velocity one and wish to meet as soon as possible. Neither knows the direction of the other, nor do they have a common notion of a positive direction on the line. It is required to find the symmetric rendezvous value$R^s (F)$, which is the minimum expected meeting time achievable by players using the same mixed strategy. This corresponds to the case where the players are indistinguishable; they both take directions from a controller who does not know their names. In this paper we give a mixed strategy which has an expected meeting time of $1.78D + \mu /2$, where D is the maximum of F and $\mu $ its mean. This leads to an upper bound $R^2 (F) \leqslant 1.78D + \mu /2$ on the symmetric rendezvous value, which is better than the upper bound $R^2 (F) \leqslant 2D + \mu /2$ obtained by Alpern.