Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Searching for a Non-adversarial, Uncooperative Agent on a Cycle
verfasst von : Jurek Czyzowicz, Stefan Dobrev, Maxime Godon, Evangelos Kranakis, Toshinori Sakai, Jorge Urrutia
Erschienen in: Algorithms for Sensor Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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\pi /s\), if \(s \ge 1\), (1b) \(4\pi /(s+1)\), if \(1/3 \le s \le 1\), and (1c) \(2\pi /(1-s)\), if \(s \le 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 \pi ( 1 + \frac{1}{s+1}) \). Moreover, for all \(\epsilon >0\) there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least \(4\pi -\epsilon \) to meet the bus.
These results are also generalized to \(k \ge 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.