## Abstract

We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is*1 + 2 m*We show that if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least

^{m}/ (m - 1)^{(m-1)}*1 + 2 m*) which is again optimal---but in a stricter sense.

^{m}/ (m - 1)^{(m-1)}- O(1 / log^{2}DTo show the optimality of our lower bound we construct a search strategy that achieves this ratio. Surprisingly, our strategy does not need to know an upper bound on the distance to the target in advance; it achieves a competitive ratio of

*1 + 2 m*) if the target is found at distance

^{m}/ (m - 1)^{(m-1)}- O(1/log^{2}D*D*Finally, we also present an algorithm to compute the strategy that allows the robot to search the farthest for a given competitive ratio

*C*.