rapid exploring random trees

Question

http://msl.cs.uiuc.edu/rrt/

Can anyone explain how rrt works with simple wording that is easy to understand? I read the description in the site and in wikipedia.

What I would like to see, is a short implementation of a rrt or a thorough explanation of the following thing:

Why does the rrt grow outwards instead of just growing very dense around the center? How is it different from a naive random tree?

How is the next new vertex that we attempt to reach picked?

I know there is an Motion Strategy Library I could download but I would much rather understand the idea before I delve into the code rather than the other way around.

Chillon

Answer 1

The simplest possible RRT algorithm has been so successful because it is pretty easy to implement. Things tend to get complicated when you:

• need to visualise planning concepts in more than two dimensions
• are unfamiliar with the terminology associated with planning, and;
• in the huge number of variants of RRT that are have been described in the literature.

Pseudo code

The basic algorithm looks something like this:

1. Start with an empty search tree

2. Add your initial location (configuration) to the search tree

3. while your search tree has not reached the goal (and you haven't run out of time)

   3.1. Pick a location (configuration), q_r, (with some sampling strategy)

   3.2. Find the vertex in the search tree closest to that random point, q_n

   3.3. Try to add an edge (path) in the tree between q_n and q_r, if you can link them without a collision occurring.

Although that description is adequate, after a while working in this space, I really do prefer the pseudocode of figure 5.16 on RRT/RDT in Steven LaValle's book "Planning Algorithms".

Tree Structure

The reason that the tree ends up covering the entire search space (in most cases) is because of the combination of the sampling strategy, and always looking to connect from the nearest point in the tree. This effect is described as reducing the Voronoi bias.

Sampling Strategy

The choice of where to place the next vertex that you will attempt to connect to is the sampling problem. In simple cases, where search is low dimensional, uniform random placement (or uniform random placement biased toward the goal) works adequately. In high dimensional problems, or when motions are very complex (when joints have positions, velocities and accelerations), or configuration is difficult to control, sampling strategies for RRTs are still an open research area.

Libraries

The MSL library is a good starting point if you're really stuck on implementation, but it hasn't been actively maintained since 2003. A more up-to-date library is the Open Motion Planning Library (OMPL). You'll also need a good collision detection library.

Planning Terminology & Advice

From a terminology point of view, the hard bit is to realise that although lots of the diagrams you see in the (early years of) publications on RRT are in two dimensions (trees that link 2d points), that this is the absolute simplest case.

Typically, a mathematically rigorous way to describe complex physical situations is required. A good example of this is planning for a robot arm with n- linkages. Describing the end of such an arm requires a minimum of n joint angles. This set of minimum parameters to describe a position is a configuration (or some publications state). A single configuration is often denoted q

The combination of all possible configurations (or a subset thereof) that can be achieved make up a configuration space (or state space). This can be as simple as an unbounded 2d plane for a point in the plane, or incredibly complex combinations of ranges of other parameters.

Sailesh

So basically you are saying(in 2D), 1. Pick a starting vertex and a goal vertex. 2. Randomly pick a position (p) in the 2D sapce. 3. Find the closes point (q) on an edge of the tree to position (p). 4. Check if you can move from (q) to (p) and if so add a new edge {(p), (q)} and that is all? 5. Go back to 2. ?? – Chillon

Thanks, I really enjoyed reading your answer and realizing it was simply a tree that picks new 'leaves' at random(or with a sampling strategy). Are there any commonly used and simple sampling strategies? – Chillon

... Nancy Amato's groups publications, especially on OB-PRM (Obstacle PRM) and MAPRM (Medial Axis PRM). More recently, there were some demonstrations of newer sampling techniques suitable for real world robots and systems in the MIT course Underactuated Robotics – Sailesh

Wow, I thank you very much for helping me take the first steps – Chillon

@AndrewWalker Hi, is this dependent on a 2D matrix data structure? Or can I generate random node objects at random positions? – Germain

RRTs will work in any types of configuration / state spaces, not just 2D spaces. 2, 3 or even higher numbers of dimensions will work fine. When you have upward of about 10 dimensions (for example robot snakes, robot arms with many linkages or protein folding), you need to think carefully about how you do your sampling. To be probabilitically complete you need to show that with probability 1, the sampling algorithm would eventually sample in the neighborhood of every configuration - uniform sampling in n-dimensions is valid. – Sailesh