Algorithms for On-Line Navigation

Abstract

We consider a number of problems faced by a robot trying to navigate inside a simple polygon. Such problems are "on-line"g 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. Specifically, we examine algorithms for the related problems of exploration and search. We present a 5/4-competitive randomized algorithm for exploring a rectilinear polygon; the only privious work here is the deterministic 2-competitive algorithm claimed in Deng, Kameda and Papadimitrou. For the problem of searching for a distinguished point in a polygon, we give a $\sqrt{3}$-competitive algorithm for traversing a street, which improves on a result of Klein by more than a factor of 3. Finally, the techniques we use in exploration and the construction of search patterns are combined to give an algorithm for searching an arbitrary and unknown rectilinear polygon; here, no constant competitive ratio can be achieved, but our algorithm is within a constant factor of optimal in the worst case.