All language subtitles for 03_2-6-collision-detection-and-freespace-sampling-methods.en

[INAUDIBLE] obstacles are really
convenient to work with, because

they provide an explicit description
of the configure space obstacles.

Often times, we don't have this luxury and

the obstacles are instead defined
implicitely through a collision function.

More specifically, if we let x denote the
coordinates of a point in configuration

space, we're usually able to define
a function, let's call it CollisionCheck,

that returns zero if the configuration
is in freespace, and one otherwise.

In this slide, we show a situation
where our putitive robot,

the red polygon, is entirely in freespace.

So we want our CollisionCheck
function to return a zero.

In this next case, the robot is
colliding with one of the obstacles.

So we would want our CollisionCheck
function to return a one for

this configuration.

Collision detection is a key subroutine
for most path planning algorithms, and

it often boils down to computing the
answer to some basic geometric questions.

Lets go back and consider our example.

Here we can imagine
representing both our robot and

our obstacle as collections of triangles,
as shown in this figure.

Deciding whether the robot and

the obstacle intersect is now
a matter of determining whether

any of the robot's triangles overlap
any of the obstacle's triangles.

Here we can make use of the fact
that triangles are convex polygons.

In this circumstance, it means that we can
test where the two triangles intersect

by checking all of the sides on both
triangles, and testing whether any of

those sides act as separating lines, where
all of the points from one triangle lie

on one side of the line, and all of those
from the other lie on the opposite side.

If you can find such a separating edge,
among the six edges among

the two triangles, you have proved
that the triangles don't intersect.

If not, you can conclude that they do.

This idea of finding a separating line, or

plane, actually generalizes
to higher dimensions.

For instance, If you have a robot composed
of convex polygons in three dimensions

like boxes or pyramids.

You can check for collision by
testing if any of the faces on one of

the polygons acts as
a separating hyperplane.

In the cases that we've considered so
far, the robots and

the obstacles are basically
composed of simple polygons.

So to test for collision,

we first transform the robot according to
the configurations space parameters and

then test for collision between
the robot's components and the obstacles.

In this case, this amounts to testing
whether any of the red triangles

overlap any of the black triangles.

In this case we would want our
CollisionCheck function to return a zero,

indicating that no
intersections are found.

In this next case, there are in
fact red triangles that do overlap

the black triangles so our CollisionCheck
function should return a one.

Another question that we may be
interested in answering is whether all of

the points along the line segment between
two configuration space points x1 and

x2 are in freespace.

Sometimes we're lucky and

we can actually answer that
question definitively by analysis.

In practice,
if two points are both in freespace, and

they are close enough to each other,
given some reasonable distance metric,

then we tend to assume that a straight
line path between them is collision free.

This can obviously go horribly
wrong if we're not careful.

But let's live dangerously for a second.

In considering our 2D planning problem,

we can proceed by sampling a grid of
locations in the configuration space.

For each grid point we
determine whether or

not it is in freespace using
our CollisionCheck function.

All the grid points that are in
freespace are going to be treated as

nodes in our graph.

This figure shows the resulting
sampled freespace points.

in this example, we're going to go ahead
and assume that if two adjacent grid

points are both in freespace, then all the
points between them are also in freespace.

And we connect them by an etch,
as shown here.

In this case, we've chosen matters so

that the start and
end points are both nodes in the graph.

We can then employ anyone of our usual
suite of graph-based planning tools

to search for
a path between the two nodes.

The resulting path through
the graph is shown here, in red.