eCommons

 

Algorithms for On-Line Navigation

Other Titles

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 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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1992-11

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR92-1316

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record