Quick study of random trees

Question

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

Can someone explain how rrt works with simple wording that is easy to understand? I read the description on the site and on Wikipedia.

What I would like to see is a brief rrt implementation or a detailed explanation of the following:

Why does rrt grow outward instead of just growing very densely around the center? How is this different from a naive random tree?

How is the next new peak we are trying to reach selected?

I know that there is a library of motion strategies that I could download, but I would rather understand this idea before I delve into the code, and not vice versa.

Answer 1

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

• it is necessary to visualize planning concepts in more than two dimensions
• not familiar with planning terminology, and;
• in the huge number of RRT options that have been described in the literature.

Pseudo code

The basic algorithm looks something like this:

• Start with an empty search tree

• Add your original location (configuration) to the search tree

• until your search tree has reached the goal (and you did not have time)

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

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

  3.3. Try adding an edge (path) in the tree between q_n and q_r if you can link them without collisions.

Although this description is sufficient, after a while working in this space, I really prefer the pseudo-code in Figure 5.16 on the RRT / RDT in Stephen LaValle's book “Planning Algorithms”.

Tree structure

The reason the tree ends, covering the entire search space (in most cases), is due to the combination of the selection strategy and is always looking for connectivity from the nearest point in the tree. This effect is described as a decrease in Voronoi deviation.

Sampling strategy

Choosing a location to place the next vertex that you will be trying to connect to is a sampling problem. In simple cases, when the search is low-dimensional, uniform random placement (or uniform random placement biased towards the target) works adequately. In problems with large sizes or in very complex movements (when the joints have positions, speeds and accelerations) or configurations are difficult to control, sampling strategies for RRT remain an open area of ​​research.

Libraries

The MSL library is a good starting point if you are really stuck in the implementation, but it has not been actively supported since 2003. A more current library is the Open Motion Planning Library (OMPL) . You will also need a good collision detection library.

Planning terminology and recommendations

From a terminological point of view, the hard bit should understand that although many of the diagrams that you see in the (early years) publications in the RRT are in two dimensions (trees that connect 2d points), this is the absolute simplest case.

As a rule, a mathematically rigorous way of describing complex physical situations is required. A good example of this is planning an n-clutch robot. A description of the end of such a lever requires a minimum of n connection angles. This set of minimum parameters for describing a position is a configuration (or some publication state ). One configuration is often denoted by q

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