Particle RRT for Path Planning with Uncertainty

Nicholas Melchior and Reid Simmons
Conference Paper, 2007 IEEE International Conference on Robotics and Automation, pp. 1617-1624, April, 2007

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


This paper describes a new extension to the rapidly-exploring random tree (RRT) path planning algorithm. The particle RRT algorithm explicitly considers uncertainty in its domain, similar to the operation of a particle filter. Each extension to the search tree is treated as a stochastic process and is simulated multiple times. The behavior of the robot can be characterized based on the specified uncertainty in the environment, and guarantees can be made as to the performance under this uncertainty. Extensions to the search tree, and therefore entire paths, may be chosen based on the expected probability of successful execution. The benefit of this algorithm is demonstrated in the simulation of a rover operating in rough terrain with unknown coefficients of friction.

author = {Nicholas Melchior and Reid Simmons},
title = {Particle RRT for Path Planning with Uncertainty},
booktitle = {2007 IEEE International Conference on Robotics and Automation},
year = {2007},
month = {April},
pages = {1617-1624},
keywords = {mobile robots, path planning, stochastic processes},
} 2017-09-13T10:42:14-04:00