화학공학소재연구정보센터
SIAM Journal on Control and Optimization, Vol.36, No.6, 1880-1889, 1998
Rendezvous on the line when the players' initial distance is given by an unknown probability distribution
Two players A and B are randomly placed on a line. The distribution of the distance between them is unknown except that the expected initial distance of the (two) players does not exceed some constant mu. The players can move with maximal velocity 1 and would like to meet one another as soon as possible. Most of the paper deals with the asymmetric rendezvous in which each player can use a different trajectory. We find rendezvous trajectories which are efficient against all probability distributions in the above class. (It turns out that our trajectories do not depend on the value of mu.) We also obtain the minimax trajectory of player A if player B just waits for him. This trajectory oscillates with a geometrically increasing amplitude. It guarantees an expected meeting time not exceeding 6.8 mu. We show that, if player B also moves, then the expected meeting time can be reduced to 5.7 mu.The expected meeting time can be further reduced if the players use mixed strategies. We show that if player B rests, then the optimal strategy of player A is a mixture of geometric trajectories. It guarantees an expected meeting time not exceeding 4.6 mu. This value can be reduced even more (below 4.42 mu) if player B also moves according to a (correlated) mixed strategy. We also obtain a bound for the expected meeting time of the corresponding symmetric rendezvous problem.