Graphics enhanced version of this site

Anytime RRTs
D. Ferguson and A. Stentz
Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '06), October, 2006, pp. 5369 - 5375.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [1108 KB]

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.

We present an anytime algorithm for planning paths through high-dimensional, non-uniform cost search spaces. Our approach works by generating a series of Rapidly-exploring Random Trees (RRTs), where each tree reuses information from previous trees to improve its growth and the quality of its resulting path. We also present a number of modifications to the RRT algorithm that we use to bias the search in favor of less costly solutions. The resulting approach is able to produce an initial solution very quickly, then improve the quality of this solution while deliberation time allows. It is also able to guarantee that subsequent solutions will be better than all previous ones by a user-defined improvement bound. We demonstrate the effectiveness of the algorithm on both single robot and multirobot planning domains.

Associated centers: VASC and FRC
Associated lab/group: NavLab
Associated project: CTA Robotics

Number of pages: 7

D. Ferguson and A. Stentz, "Anytime RRTs," Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '06), October, 2006, pp. 5369 - 5375.

@inproceedings{Ferguson_2006_5652,
   author = "David Ferguson and Anthony (Tony) Stentz",
   title = "Anytime RRTs",
   booktitle = "Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '06)",
   month = "October",
   year = "2006",
   pages = "5369 - 5375"
}