Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6214
 Title: Algorithms for On-Line Navigation Authors: Kleinberg, Jon M. Keywords: computer sciencetechnical report Issue Date: Nov-1992 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR92-1316 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. URI: http://hdl.handle.net/1813/6214 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat