On-line search in a simple polygon

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 BaezaYates, Culberson, and Rawlins to a much more general class of search spaces. Finally, we examine a type of polygon for which competitive search is po...