Bounded uncertainty roadmaps for path planning

Leonidas J. Guibas, David Hsu, Hanna Kurniawati, Ehsan Rehman

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Citations (Scopus)

Abstract

Motion planning under uncertainty is an important problem in robotics. Although probabilistic sampling is highly successful for motion planning of robots with many degrees of freedom, sampling-based algorithms typically ignore uncertainty during planning. We introduce the notion of a bounded uncertainty roadmap (BURM) and use it to extend sampling-based algorithms for planning under uncertainty in environment maps. The key idea of our approach is to evaluate uncertainty, represented by collision probability bounds, at multiple resolutions in different regions of the configuration space, depending on their relevance for finding a best path. Preliminary experimental results show that our approach is highly effective: our BURM algorithm is at least 40 times faster than an algorithm that tries to evaluate collision probabilities exactly, and it is not much slower than classic probabilistic roadmap planning algorithms, which ignore uncertainty in environment maps.

Original languageEnglish
Title of host publicationAlgorithmic Foundations of Robotics VIII - Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics
Pages199-215
Number of pages17
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event8th International Workshop on the Algorithmic Foundations of Robotics, WAFR - Guanajuato, Mexico
Duration: 7 Dec 20089 Dec 2008

Publication series

NameSpringer Tracts in Advanced Robotics
Volume57
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Conference

Conference8th International Workshop on the Algorithmic Foundations of Robotics, WAFR
Country/TerritoryMexico
CityGuanajuato
Period7/12/089/12/08

Fingerprint

Dive into the research topics of 'Bounded uncertainty roadmaps for path planning'. Together they form a unique fingerprint.

Cite this