Minimax rendezvous on the line

作者：Lim WS^*; Alpern S

来源：SIAM Journal on Control and Optimization, 1996, 34(5): 1650-1665.

DOI：10.1137/S036301299427816X

• rendezvous
• search game

Suppose that n players are placed randomly on the real line at consecutive integers, and faced in random directions, Each player has maximum speed one, cannot see the others, and doesn';t know his relative position. What is the minimum time M(n) required to ensure that all the players can meet together at a single point, regardless of their initial placement? We prove that M(2) = 3, M(3) = 4, and M(n) is asymptotic to n/2. We also consider a variant of the problem which requires players who meet to stick together. and find in this case that three players require 5 time units to ensure a meeting. This paper is thus a minimax version of the rendezvous search problem, which has hitherto been studied only in terms of minimizing the expected meeting time.

• 出版日期1996-9