Navigating in unfamiliar geometric terrain

Avrim Blum, Prabhakar Raghavan, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

69 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 (obstacle-free) 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. For many of these situations, our algorithms are optimal up to constant factors. We study scenes with nonconvex obstacles, which are related to the study of maze traversal. We also show scenes where randomized algorithms are provably better than deterministic algorithms.

Original languageEnglish (US)
Pages (from-to)110-137
Number of pages28
JournalSIAM Journal on Computing
Volume26
Issue number1
DOIs
StatePublished - Feb 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Computational geometry
  • On-line algorithms
  • Robot navigation

Fingerprint

Dive into the research topics of 'Navigating in unfamiliar geometric terrain'. Together they form a unique fingerprint.

Cite this