All language subtitles for 01_3-1-introduction-to-probabilistic-road-maps.en

[MUSIC]

In the previous module,
we talked about configuration space, and

we discussed the idea of
a collision check function

that could be used to decide
whether a given point

in configuration space
was in free space or not.

By checking whether that configuration
led to a collision with the obstacles in

the work space.

We also talked about the idea of a simple
planning scheme that worked by using

the collision check function to sample
the configuration space at a set of

regularly spaced discreet
locations on a grid.

Linking adjacent points in
free space with edges, and

then using this graph to
plan pass through the space.

This approach of discreetizing
the configuration space evenly on a grid,

can work well when the dimension of
the space is small, say two or three.

But the number of samples required
can grow to be frighteningly large

as we increase the dimension of the space
to five, six, eight, ten, or beyond.

An alternative idea for dealing with
these situations is to choose the points

in the configuration space
randomly instead of uniformly.

In the hope that we will choose
a set of configurations that

capture the underlying
structure of the free space.

This set of slides
illustrates the basic idea

on a two dimensional configuration space.

On every iteration, the system chooses
a configuration in the configuration space

at random, and tests whether it is in free
space using the collision check function.

In this figure,
the new random node is the green dot.

If it is in free space, it then
tries to see if it can forge routes

between this new configuration and
the closest existing samples in the graph.

Every path that it creates is
recorded as a new edge in the graph

that the system is building.

In this figure,

the solid green lines correspond to new
links that are added, while the dashed

green line represents a connection that
failed due to collision with the obstacle.

Here's the basic outline of
the procedure in pseudo code.

Again, our goal here is to construct
a graph of configuration space points and

edges that capture the underlying
topology of the freespace.

We can think of the edges between
the random samples as roadways

that form a network that
hopefully spans this freespace.

This helps to explain why we call this
procedure the Probabilistic Road Map

method, or PRM for short.

Probabilistic to reflect the stochastic
nature of the process and road map for

the graph that the procedure constructs
which we hope will serve as a road map for

the freespace.

Note that this procedure
requires two ingredients.

Firstly, a distance function that
considers the configuration space

coordinates of two points, x1 and
x2, and returns a real number

which is supposed to be reflective of the
distance between those two configurations.

Often, this can be done pretty simply by
computing standard functions like the L1

or L2 distances as shown here.

For robots that involve rotational joints,

you usually need to be a bit more careful
to handle wrap around correctly so that

your distance function correctly captures
the topology of the configuration space.

For example, if theta 1 and theta 2
are two angular values in degrees between

0 and 360, you may choose to use a
distance function like this that captures

the fact that 0 and 360 actually
correspond to the same orientation.

The other element of the PRM
procedure is a local planner,

which decides whether there is a path
between two points, x1 and x2.

A common way to handle this is to
construct a set of evenly spaced

samples on a straight line
between the two configurations.

And to use the collision
check function to check that

all of these intermediate
configurations are collision free.

So in this example, the local planet
would decide that there is a path

between the two points in question.

While in the second case,
it would decide that there isn't.

If the sampling between the two
endpoints is fine enough,

this procedure is usually sufficient.

Once the PRM procedure has generated

what we believe to be a sufficient
sampling of the configuration space,

we can try to generate paths between
designated start and end configurations.

We start off by attempting
to connect the start and

goal configurations to
nearby nodes on the roadmap.

If this step succeeds,

one can then attempt to find
a path between the start and

end nodes via the road map using our usual
suite of graph-based planning algorithms.

Like [INAUDIBLE] method or A star.

This second phase, where we are planning
a path between two specific locations

is referred to as the query phase.

This first slide shows the original
probabilistic road map

constructing via random sampling.

The next slide shows the road map
augmented with the start and end notes,

which are attached to the road
map using the green edges.

This final version shows the path
planned through this augmented graph.

Note that once the road
map has been constructed,

it can be used to answer
various path planning problems.

So the cost of constructing
the road map graph

can be amortized over multiple queries.

This is great if you're going to
be running your robot back and

forth through the same environment.