An Optimal Strategy for Searching in Unknown Streets

Abstract. We consider the problem of a robot searching for an unknown, yet visually recognizable target in a street. A street is a simple polygon with start and target on the boundary so that the two boundary chains between them are weakly mutually visible. We are interested in the ratio of the search path length to the shortest path length which is called the competitive ratio of the strategy. We present an optimal strategy whose competitive ratio matches the known lower bound of p2, thereby closing the gap between the lower bound and the best known upper bound