Home/Multipartite RRTs for Rapid Replanning in Dynamic Environments

Multipartite RRTs for Rapid Replanning in Dynamic Environments

Matthew Zucker, James Kuffner and Michael Branicky
Conference Paper, Proceedings of Proc. IEEE Int. Conf. Robotics and Automation, 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.


The Rapidly-exploring Random Tree (RRT) algorithm has found widespread use in the field of robot motion planning because it provides a single-shot, probabilistically complete planning method which generalizes well to a variety of problem domains. We present the Multipartite RRT (MP-RRT), an RRT variant which supports planning in unknown or dynamic environments. By purposefully biasing the sampling distribution and re-using branches from previous planning iterations, MP-RRT combines the strengths of existing adaptations of RRT for dynamic motion planning. Experimental results show MP-RRT to be very effective for planning in dynamic environments with unknown moving obstacles, replanning in high-dimensional configuration spaces, and replanning for systems with spacetime constraints.

author = {Matthew Zucker and James Kuffner and Michael Branicky},
title = {Multipartite RRTs for Rapid Replanning in Dynamic Environments},
booktitle = {Proceedings of Proc. IEEE Int. Conf. Robotics and Automation},
year = {2007},
month = {April},
keywords = {Motion planning, Dynamic Re-Planning, Randomized Algorithms},
} 2017-09-13T10:42:16-04:00