Original subtitles

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