Original subtitles

[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.