Rendezvous search on the line with bounded resources: expected time minimization

✍ Scribed by Steve Alpern; Anatole Beck

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 692 KB
• Volume: 101
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(96)00192-0

✦ Synopsis

Two players are placed on the line and want to meet. Neither knows the direction of the other, but they know the distance between them or perhaps the distribution of this distance. They can move with speed at most one, and each has a 'resource constraint' on the total distance he can travel. We first consider the question of whether the two players can ensure that they meet. When they can, then we seek the least expected meeting time. Otherwise, we maximize the probability of a meeting.

This generalizes the similar problem studied by the first author and S. Gal [SIAM J. Control and Optimization 33/4 (1995) 1270] without any resource constraint, and indeed for sufficiently large resources gives the same rendezvous time, i.e. least expected time to meet. The paper may also be considered a generalization of the Linear Search Problem, studied by the second author and others, which corresponds to the ease when one of the resource constraints is zero, so that player cannot move. More specifically, it generalizes the bounded resource version of the Linear Search Problem presented by