Algorithms for On-Line Navigation
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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