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 (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.
|Keywords||Cycle, Direction of movement, Moving bus, Robot, Search, Speed|
|Series||Lecture Notes in Computer Science|
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