TY - GEN
T1 - Bounded uncertainty roadmaps for path planning
AU - Guibas, Leonidas J.
AU - Hsu, David
AU - Kurniawati, Hanna
AU - Rehman, Ehsan
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77949856337&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00312-7_13
DO - 10.1007/978-3-642-00312-7_13
M3 - Conference contribution
AN - SCOPUS:77949856337
SN - 9783642003110
T3 - Springer Tracts in Advanced Robotics
SP - 199
EP - 215
BT - Algorithmic Foundations of Robotics VIII - Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics
T2 - 8th International Workshop on the Algorithmic Foundations of Robotics, WAFR
Y2 - 7 December 2008 through 9 December 2008
ER -