Searching for a Non-adversarial, Uncooperative Agent on a Cycle

摘要

Assume k robots are placed on a cycle-the perimeter of a unit (radius) disk-at a position of our choosing and can move on the cycle with maximum speed 1. A non-adversarial, uncooperative agent, called bus, is moving with constant speed s along the perimeter of the cycle. The robots are searching for the moving bus but do not know its exact location; during the search they can move anywhere on the perimeter of the cycle. We give algorithms which minimize the worst-case search time required for at least one of the robots to find the bus. The following results are obtained for one robot. (1) If the robot knows the speed s of the bus but does not know its direction of movement then the optimal search time is shown to be exactly (la) 2π, if s > 1, (lb) 4π/(s+1), if 1/3≤ s≤ 1, and (1c) 2π/(1-s), if s ≤ 1/3. (2) If the robot does not know neither the speed nor the direction of movement of the bus then the optimal search time is shown to be 27π(l + 1/(s+1)). Moreover, for all e > 0 there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least 4π - c to meet the bus. These results are also generalized to k > 2 robots and analogous tight upper and lower bounds are proved depending on the knowledge the robots have about the speed and direction of movement of the bus.