Randomized robot navigation algorithms

Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks

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

34 Scopus citations


We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot has no prior knowledge about the positions or sizes of the obstacles, and acquires such knowledge only when obstacles are encountered. Our goal is to minimize the distance the robot must travel, using the competitive ratio as our measure. We give a new randomized algorithm for this problem whose competitive ratio is O(n 4/9 log n), beating the deterministic Ω(√n) lower bound of [PY], and answering in the affirmative an open question of [BRS] (which presented an optimal deterministic algorithm). We believe the techniques introduced here may prove useful in other on-line situations in which information gathering is part of the on-line process.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)0898713668
StatePublished - Jan 28 1996
Event7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996 - Atlanta, United States
Duration: Jan 28 1996Jan 30 1996

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129447


Other7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Randomized robot navigation algorithms'. Together they form a unique fingerprint.

Cite this