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 one. 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. Moreover, 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.