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