Multipartite RRTs for Rapid Replanning in Dynamic Environments

Matthew Zucker, James Kuffner, and Michael Branicky
Proc. IEEE Int. Conf. Robotics and Automation, April, 2007.


Download
  • Adobe portable document format (pdf) (456KB)
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.

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.

Keywords
Motion planning, Dynamic Re-Planning, Randomized Algorithms

Notes
Associated Center(s) / Consortia: Center for the Foundations of Robotics

Text Reference
Matthew Zucker, James Kuffner, and Michael Branicky, "Multipartite RRTs for Rapid Replanning in Dynamic Environments," Proc. IEEE Int. Conf. Robotics and Automation, April, 2007.

BibTeX Reference
@inproceedings{Zucker_2007_5677,
   author = "Matthew Zucker and James Kuffner and Michael Branicky",
   title = "Multipartite RRTs for Rapid Replanning in Dynamic Environments",
   booktitle = "Proc. IEEE Int. Conf. Robotics and Automation",
   month = "April",
   year = "2007",
}