Searching on m Bounded Rays Optimally

Abstract

We consider the problem of searching on m current rays for a target of unknown location. It is well-known that the optimal strategy to solve this problem achieves a competitive ratio of Cm = 1 + 2m m =(m \\Gamma 1) m\\Gamma1 . We investigate the case where the target is known to be within a fixed distance D of the origin. We present an algorithm to compute the optimal competitive ratio C D m that can be achieved by a deterministic on-line strategy. 1 Introduction Searching for a target is an important and well studied problem in robotics. In many realistic situations the robot does not possess complete knowledge about its environment, for instance, the robot may not have a map of its surroundings, or the location of the target may be unknown [DI94, IK95, Kle92, LOS95, PY89]. Since the robot has to make decisions about the search based only on the part of its environment that it has explored before, the search of the robot can be viewed as an on-line problem. One way to judg...