Original subtitles

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.