Title of Presentation: Particle RRT for Path Planning in Very Rough Terrain

Primary (Corresponding) Author: Nik Melchior

Organization of Primary Author: Carnegie Mellon University

Abstract:  The Particle-based Rapidly-exploring Random Tree (pRRT) algorithm is a new method for planetary rover path planning in very rough terrain.  The Rapidly-exploring Random Tree algorithm is a planning technique that accounts for effects such as vehicle dynamics by incrementally building a tree of reachable states.  pRRT extends the conventional RRT algorithm by explicitly considering uncertainty in sensing, modeling, and actuation by treating each addition to the tree as a stochastic process.  A specified model of uncertainty is propagated through the tree by the planning algorithm so that the resulting plan may be characterized in terms of robustness and expected probability of successful execution.  This allows continuous autonomous operation of the robot even in the most difficult terrain.

Our recent work has investigated several machine learning techniques to improve the performance and accuracy of the algorithm in simulation.  Although RRT is well-suited to large dimensional configuration spaces, reducing the dimensionality allows for faster planning.  By using Adaboost with Naïve Bayes weak learners, we were able to reduce the representation of the vehicle state and improve the computational complexity of the algorithm.  We also improved the rover slip prediction model by using linear Support Vector Machines and compared various models of the rover itself to reduce disparity between the simulated and actual execution results.

The pRRT algorithm has been experimentally verified in simulation, and shown to produce plans that are significantly more robust than conventional RRT.  The algorithm shows promise both for onboard planning and as a ground-based tool for plan verification.  Based on these results, we have integrated the simulator with the iRobot ATRV-Jr hardware platform and tested and verified the pRRT algorithm using IPC communication.  For the next step, we will apply the pRRT algorithm to JPL's FIDO Rover and ensure the performance and reliability of this method.