RENDEZVOUS SEARCH ON THE LINE WITH BOUNDED RESOURCES - EXPECTED TIME MINIMIZATION

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 pe rhaps the distribution of this distance. They can move with speed at m ost 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 expe cted 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 an y resource constraint, and indeed for sufficiently large resources giv es the same rendezvous time, i.e. least expected time to meet. The pap er may also be considered a generalization of the Linear Search Proble m, studied by the second author and others, which corresponds to the c ase when one of the resource constraints is zero, so that player canno t move. More specifically, it generalizes the bounded resource version of the Linear Search Problem presented by Foley, Hill and Spruill [Na val Research Logistics 38 (1991) 555-565]. (C) 1997 Elsevier Science B .V.