Speaker: Oren Salzman

Title: Asymptotically near-optimal RRT for fast, high-quality, motion planning

Abstract:
---------
Motion planning is a fundamental research topic in robotics with  
applications in diverse domains such as surgical planning,  
computational biology, autonomous exploration, search-and-rescue, and  
warehouse management. Sampling-based planners such as PRM, RRT and  
their many variants enabled solving motion-planning problems that had  
been previously considered infeasible. Recently, there is growing  
interest in the robotics community in finding high-quality paths,  
which turns out to be a non-trivial problem. In their seminal work,  
Karaman and Frazzoli have given a rigorous analysis of the performance  
of the commonly used RRT and PRM algorithms. They show that with  
probability one, the algorithms will not produce the optimal path. By  
modifying certain basic procedures in the existing algorithms, they  
propose the PRM* and the RRG and RRT* algorithms (variants of the PRM  
and RRT algorithms, respectively) all of which are shown to be  
asymptotically optimal. However, assuring asymptotic-optimality comes  
with a price: the PRM* algorithm constructs large, dense graphs and  
the RRT* algorithm exhibits much longer running time to find a  
solution when compared to original RRT.

In this talk I will review different sampling-based motion-planning  
algorithms and propose several methods where we only slightly relax  
the optimality requirement. These relaxations allow for high-quality,  
efficient, motion planning.

Based on joint work with Dan Halperin.