Multipartite RRTs for Rapid Replanning in Dynamic Environments - Robotics Institute Carnegie Mellon University

Multipartite RRTs for Rapid Replanning in Dynamic Environments

Matthew Zucker, James Kuffner, and Michael Branicky
Conference Paper, Proceedings of (ICRA) International Conference on Robotics and Automation, pp. 1603 - 1609, April, 2007

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},
}