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