A Rapidly-exploring Random Tree (RRT) algorithm is a method of finding the shortest paths between points in many-dimensional spaces. It was originally developed by Steve LaValle, Assistant Professor of Computer Science at the University of Illinois, in consultation with James Kuffner of the Stanford University Computer Science Department. RRTs work well for path planning problems that involve obstacles and differential constraints (non holonomic or kinodynamic).
Generally, the algorithm goes like this:
- Choose a start point, and an end point in a state space
- Pick a random point in this state space, and move incrementally towards connecting it to a point already in the RRT that is closest to this random point.
- If this movement does not encounter an obstacle, make this new point a node in the RRT.
- Repeat until a node connected to the RRT originating from the start point has reached the goal point threshold.
You can then start thinking about doing things to make this a fun sort of path-planning algorithm, like perhaps... joining a number of these trees together ... which is what the RRT-Connect algorithm does.
The RRT-Connect algorithm works like this:
- Define start points, and optionally, some end points
- From the start and/or points, choose a point randomly to head to, preferably in an area which hasn't been visited before. If there are start and end points, the direction chosen is biased towards heading to the start from the end point, or the end from the start point
- This continues until the path-trees from start and end meet up, or when the space has been explored. At this point, with appropriate biasing values, you'd end up with the shortest path between two points ...
For a more technical explanation, you'll have to wait for either someone else to node, or for me to figure out what it is I'm supposed to be doing for this here thesis project thingy ... aaargh ...
Right, now that I've actually got into some of this thesis project thing, I've done a fair pile more reading ... I just came back to add some stuff that I should've done when I first started this node... which has done exactly what I wanted ... it's made this algorithm clearer than mud in my head! yay!
Applications for RRTs can been found for :
Other related topics include Voronoi and Delaunay diagrams, fractals and other randomness...
Bibliography
- http://msl.cs.uiuc.edu/rrt/about.html
- http://decision.csl.uiuc.edu/~toussant/report30/node3.html
- Class notes from ECE4711 Computer Vision and Robotics, offered at Monash University
- Kuffner Jr, JJ; LaValle, SM; “RRT-Connect: An efficient approach to single-query path planning”, From Proceedings of the 2000 IEEE International Conference on Robotics & Automation, San Francisco CA, April 2000.http://www.kuffner.org/james/papers/icra00.pdf (accessed 12 February 2003)
- http://www.google.com ... must worship the search engine ...