Multipartite RRTs for Rapid Replanning in Dynamic Environments
Abstract
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.
BibTeX
@conference{Zucker-2007-9686,author = {Matthew Zucker and James Kuffner and Michael Branicky},
title = {Multipartite RRTs for Rapid Replanning in Dynamic Environments},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2007},
month = {April},
pages = {1603 - 1609},
keywords = {Motion planning, Dynamic Re-Planning, Randomized Algorithms},
}