Seminar of Theoretical Computer Science - Stefan Dobrev (8.12.2017)

Friday 1.12.2017 at 11:00, Lecture room M/213

---

Stefan Dobrev:
Searching for a Non-adversarial, Uncooperative Agent on a Cycle

Abstract:
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π(1 + 1 ). Moreover, s+1 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.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2 
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php 

 

 

---