Navigating in Unfamiliar Geometric Terrain

Avrim Blum, Prabhakar Raghavan, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

65 Scopus citations

Abstract

Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position and that of the target. It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them. We compare the distance walked by the robot in going from .s to t to the length of the shortest path between s and t in the scene. We describe and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. We study scenes with non-convex obstacles, which are related to the study of maze-Traversal. We also show scenes where randomized algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991
PublisherAssociation for Computing Machinery
Pages494-504
Number of pages11
ISBN (Electronic)0897913973
DOIs
StatePublished - Jan 3 1991
Externally publishedYes
Event23rd Annual ACM Symposium on Theory of Computing, STOC 1991 - New Orleans, United States
Duration: May 5 1991May 8 1991

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F130073
ISSN (Print)0737-8017

Conference

Conference23rd Annual ACM Symposium on Theory of Computing, STOC 1991
Country/TerritoryUnited States
CityNew Orleans
Period5/5/915/8/91

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Navigating in Unfamiliar Geometric Terrain'. Together they form a unique fingerprint.

Cite this