CMU FRC talk: Particle RRT for Path Planning on Very Rough Terrain

Particle RRT for Path Planning on Very Rough Terrain

Nik Melchior. Ph.D. Candidate. Robotics Institute

Wednesday, March 28, 2007

Autonomous navigation algorithms operate on a model of the world built using information perceived by the robot. Despite quantifiable uncertainties in perception and modelling techniques, many navigation algorithms use coarsely quantified evaluations of areas of the world. Often, areas are classified as safe/unsafe or low cost/high cost, when much richer information is available to the planner.
This work introduces a path planning technique which explicitly models the uncertainty in the terrain and its properties. The method is an extension to the Rapidly-exploring Random Tree (RRT) algorithm, a well-known approach to path planning with kinodynamic constraints in high-dimensional state spaces.
Our extension, called Particle RRT (pRRT), uses multiple simulations to propagate the estimated uncertainty in perception to the planned path itself. This allows us to plan paths which are significantly more robust, and which can be followed with greater accuracy, even using open-loop control.