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

    Abstract

    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
    Pages75-84
    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

    Other

    Other7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
    Country/TerritoryUnited States
    CityAtlanta
    Period1/28/961/30/96

    All Science Journal Classification (ASJC) codes

    • Software
    • Mathematics(all)

    Fingerprint

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

    Cite this