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 (1a) 2π/s, if s≥1, (1b) 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 2π(Formula presented). Moreover, for all ϵ> 0 there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least 4 π-ϵ 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.

Additional Metadata
Keywords Cycle, Direction of movement, Moving bus, Robot, Search, Speed
Persistent URL dx.doi.org/10.1007/978-3-319-72751-6_9
Series Lecture Notes in Computer Science
Citation
Czyzowicz, J. (Jurek), Dobrev, S. (Stefan), Godon, M. (Maxime), Kranakis, E, Sakai, T. (Toshinori), & Urrutia, J. (Jorge). (2017). Searching for a non-adversarial, uncooperative agent on a cycle. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-72751-6_9