All language subtitles for 02_3-2-issues-with-probabilistic-road-maps.en

Now, there are a couple of characteristics
of random sampling based approaches

that are worth noting.

First off, while these methods
work very well in practice,

they're not strictly speaking complete.

A complete path planning algorithm
would find a path if one existed, and

report failure if it didn't.

With the PRM procedure, it is possible to
have a situation where the algorithm would

fail to find a path even when one exists.

If the sampling procedure fails to
generate an appropriate set of samples.

Consider, for example, the situation shown
in this figure where there is a path but

it involves finding a route
through this small passageway.

In order to find this route,
a sampling algorithm would

have to randomly generate
samples in that narrow area.

As you can imagine,
the smaller this passage way,

the less likely you are to generate
points that lie in that region.

In this first case, the samples were
relatively sparse which means that

the system fail to find a route from
the left side of the figure to the right.

In the second case, the system
generates a lot more samples and

does succeed in finding a route.

What we can say is that
if there is a route and

the planner keeps adding random samples,
it will eventually find a solution.

However, it may take a long time to
generate a sufficient number of samples.

We capture this behavior by saying
that these sampling based algorithms

are probabilistically complete.

To capture this notion
that if a solution exists,

there is a probability, hopefully a large
probability that you will find it.

However, if the procedure
doesn't find a path,

it's hard to know whether
there is in fact no path, or

whether you would be able to find
a way if you kept trying long enough.

So in practice, the number of samples
that you choose to generate for

the road map is an important
parameter of this procedure.

In order to deal with these kinds
of twisty passageway problems,

a number of approaches have been proposed
to bias the sampling algorithm, so

as to increase the chances of
finding routes in these cases.

For example,
one idea is to try to sample more points

closer to the boundaries of
configuration space obstacles.

In the hopes of constructing
path that skirt the surfaces.

To date however there is
no single sampling strategy

that is guaranteed to
work well in all cases.

In practice most path planning
problems are not pathological.

So uniform random sampling is
usually a good place to start.

The other thing to be aware of
with these random sampling methods

is that since the samples
are choosing randomly

the resulting trajectory can sometimes
seem very jerky and unnatural.

Often times people will apply path
smoothing procedures to the recovered

trajectories in an attempt to
smooth out the rough edges and

provide a more pleasing result.

A real advantage of these
PRM based planners,

is that they can be applied to systems
with lots of degrees of freedom.

As opposed to grid based sapling schemes,

which are typically restricted to
problems in two or three dimensions.

Here's an example of a trajectory
constructed for a system with six degrees

of freedom that guides it from
one configuration to another.

Notice the slightly stilted
nature of the trajectory.

Which can be attributed to the random
samples, as we mentioned earlier.

Again, the fact that these random
sampling methods can be applied

to systems like this with a relatively
high number of degrees of freedom

is a decided advantage of
these kinds of methods.

In conclusion, by relaxing
the notion of completeness a bit and

embracing the power of randomization.

These probabilistic road map algorithms
provide effective methods for

planning routes that can be applied
to a wide range of robotic systems.

Including systems with
many degrees of freedom.