language: en

On-Line Search in a Simple Polygon

Jon M. Kleinberg

Abstract We consider a number of search and exploration problems, from the perspective of robot navigation in a simple polygon. These problems are "on-line" in the sense that the robot does not have access to the map of the polygon; it must make decisions as it proceeds, based only on what it has seen so far. For the problem of exploring a simple rectilinear polygon (under the L 1 norm), Deng, Kameda, and Papadimitriou give a 2-competitive deterministic algorithm; we present a randomized exploration algorithm which is 5=4-competitive. Using similar techniques, we are able to give an algorithm for searching an arbitrary, unknown rectilinear polygon. No constant competitive ratio is attainable in this case, but our algorithm is within a constant factor of optimal in the worst case; in a sense, it is a generalization of some of the strategies of Baeza-Yates, Culberson, and Rawlins to a much more general class of search spaces. Finally, we examine a type of polygon for which competitive search is possible | the class of "streets" considered by Klein, who gave a 1 + 3 2 -competitive algorithm for the search problem in this case. We present a simple algorithm with a competitive ratio of at most q p 8 (~ 2:61); in rectilinear streets it achieves the optimal competitive ratio of 2.

[This work was supported in part by the Sloan Fellowship and NSF PYI award of Eva Tardos. Author is supported by an ONR Graduate Fellowship Laboratory for Computer Science, MIT, Cambridge MA 02139 USA.]