All language subtitles for 01_3-3-introduction-to-rapidly-exploring-random-trees.en

In the probabilistic roadmap procedure,
the basic idea was to construct

a roadmap of the free space consisting of
random samples and edges between them.

Once that had been constructed,
you could connect your desired start and

endpoints to this graph and
plan a path from one end to the other.

Note that the first phase constructs
a generic roadmap of the entire

free space without considering any
particular pair of start and end points.

The advantage of this approach is that
you can reuse the roadmap over and

over again to answer
multiple planning problems.

There are times though,

when you're only interested in answering
one specific planning problem.

And in those situations,

it can be wasteful to construct roadmaps
that span the entire free space.

In these situations, it may be better to
use procedures that explicitly consider

the start and the goal locations
in the sampling procedure.

In this section,
we will describe one such approach.

The Rapidly Exploring Random Tree or
RRT Method.

Like the probabilistic roadmap technique,

this approach works by generating random
samples and connecting them together

to form a graph, but
the sampling scheme is a bit different.

The RRT procedure proceeds by constructing
a special kind of graph called a tree,

where every node is connected
to a single parent and

the tree is rooted at
a given starting location.

The following animation shows how
the algorithm evolves to construct a tree

in a two-dimensional configuration
space containing obstacles.

Notice how the graph grows outward
organically from the start or

seed location at the center of the figure.

The basic tree construction algorithm
is outlined here in pseudocode.

Just as in the PRM procedure,
the basic algorithm proceeds

by sampling points at random and
connecting them to the current graph.

The difference lies in the way
the construction is carried out.

On every iteration, the system generates
a random point in the configurations base

and checks if there's a free space.

It then searches for
the closest point in the existing tree and

tries to generate a new node in
the tree by moving in a straight line

between the current vertex of the tree and
new random vertex.

The distance that it tries to move,
delta is a parameter of the algorithm.

Note that id the distance between
the random configuration and

the closest existing node in
the tree is less than delta,

the algorithm will try to directly
connect these two locations.

These sequence of figures
shows the basic idea.

The first slide shows the original tree.

Here the red node depicts the new random
configuration that the system generates,

while y depicts the closest
existing node in the tree.

This next figure shows a new node z, which
is generated by finding a configuration

that is distance delta away from
y along the line towards x.

Finally, this slide shows the new state
of the tree after adding the node z.

If the procedure does not succeed in this
process of stepping towards a random node,

it's simply abandons a point and
moves on to the next iteration

where it will generate a new
random sample and try again.

Like the PRM algorithm,

this procedure assumes that we have some
kind of distance function that we can use

to measure the effective displacement
between two points in configuration space.

We also use the same local planner
procedure to decide whether two

points in configuration space can be
linked by a collision free trajectory.

It turns out that this procedure for
generating random samples is

very effective at growing trees that
explore and span the free space.

Hence, the name,
Rapidly Exploring Random Tree or RRT.

In order to construct a path
between the stark configuration and

an end configuration,
we actually construct two trees.

One rooted at the start location and
one at the goal.

The procedure then tries to grow
both trees until they meet.

This animation shows
the procedure in action

on a two-dimensional configuration
space with obstacles.

Here, we have outlined this
two-tree procedure in pseudocode.

On every iteration of the algorithm,
the system generates a random sample and

tries to grow the current tree
towards that random sample.

If it succeeds in adding
a new node to the tree,

it tries to connect that new node
to the other tree to form a bridge.

Note that if you succeed in finding such
a bridge, you can claim success since it

means that you have now forged
a path between the two trees.

On every route of this procedure,
it swaps the two trees.

That way, both trees are growing
towards each other at the same rate.

Here's a depiction of a few
rounds of this procedure.

On the first round,
we generate a random sample and

grow the blue tree towards
that sample as shown here.

We then try to link the newly added node
to the red tree by seeing if we can link

the new node that we just added to
the closest node in the red tree.

In this case,
this linking attempt does not succeed,

because of an intervening obstacle.

In the next round,
we generate a new random sample and

try to grow the red tree
towards that point.

Once we have done this, we turn around and

try to connect that
point to the blue tree.

Here we succeed, so we can now
forge her out between the start and

the goal locations.

Like the probabilistic roadmap procedure,

the RRT algorithm is
probabilisticly complete.

So, there's a certain probability that the
method will find the path from the start

to the goal if one exists.

In practice, the RRT Method is
very effective at forging paths in

high-dimensional configuration spaces.

Another important feature of the RRT
approach is it can be used on systems that

have dynamic constraints,
which limit how they can move.

A simple example of this would be a
car-like robot where limits on the turning

radius imply that it can
not translate sideways or

turn in place around it's center.