Rapidly-exploring Random Tree(RRT)
[1] Robotic Motion Planning, RI16-735
[2]Lecture notes of Fall 2019: CS 287 Advanced Robotics by Prof. Pieter Abbeel from UC Berkeley, Dept of Electrical Engineering & Computer Sciences;
[3]H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Boston, 2005.
[4] Justin Svegliato, How does a robot plan a path using RRT?
Basic idea of RRT
- Build up a tree by generating “next states” in the tree
- However: not exactly above to ensure good coverage
A bit of history
RRT Procedure
To start us off, let’s go over each parameter that we’ll send to RRT(the input to RRT).
- Map: the map of the environment that’s partitioned into an obstacle region and an obstacle-free region. It’ll look like that map I posted above where the obstacle region is anything that’s gray and the obstacle-free region is anything that’s white.
- Start Position: the start position of the robot in its environment. This is just the red dot in that map.
- Goal Region: the goal region of the robot in its environment. And this is just the green dot in that map.
- Number of Iterations: the number of iterations performed by RRT.
Let’s go over each step of RRT.
- Initialize an empty tree.
- Insert the root node that represents the start position into the tree. At this point, we’ll just have a tree with a single node that represents the start position.
- Repeat the following steps until we hit the number of iterations or reach the goal, whichever one comes first.
- 3.1. Sample a random position from the obstacle-free region of the map.
- 3.2. Create a node that’s associated with the random position.
- 3.3. Find a node already in the tree that’s closest to the random position.
- 3.4. Calculate a path from the random position [from step 3.2] to the position of the node [from step 3.3] that would work actually be feasible on the robot.
- 3.5. Go to the next iteration [i.e. step 3.1] if the path collides with something.
- 3.6. Insert the node that’s associated with the random position [step 3.2] into the tree with the node (the node nearest to it, from step 3.3) as its parent node.
- 3.7. Return the tree once the random position is within some distance of the goal position. If the tree doesn’t get near the goal region by the time we’ve hit the number of iterations, we’ll just return the tree we’ve built so far.
- Once the tree is built, we can use graph search algorithms to get the path from the start location to the goal location. All we have to do is start at the node that represents the goal location and go back up the tree until we get to the node that represents the start location. That’ll give us the path that gets the robot from the start location to the goal location.
Is it possible to reuse the tree for new goal locations within the same map?
Of course! If there’s already a node in the tree that’s near the new goal location, we’re good to go. However, if there’s nothing close to that new goal location yet, we can just keep sampling until we’ve hit a node that’s near it (This’s why it is a single-query planning, see Planning algorithms basics). As long as the environment doesn’t change, you can just keep building on the same tree for any new goal locations.
While the path generated by RRT will work on an actual robot and avoids obstacles, is it optimal?
It turns out that RRT isn’t guaranteed to produce optimal paths unfortunately. In a future blog post, I’ll discuss RRT*, a better version of RRT, that generates an optimal path eventually.