Now that we have a conceptual framework for thinking about a wide range of motion planning problems, in terms of planning trajectories to configuration space, we can talk about various approaches to solving this problem. Specifically, in the next few sections I'm going to talk about three approaches, all of which have a common theme. Namely, they start with the motion planning problem framed on a continuous configuration space and then use various approaches to reformulate this problem in terms of a graph, so that we can apply the kinds of algorithms we discussed earlier like Grassfire, Dijkstra, and Astock. We could illustrate these approaches using the 2D planing program depicted on the following slide. As usual, our goal is to come up with a trajectory from the starting two deconfiguration to the ending configuration. In this case, the configuration space obstacles are modeled as polygons, which suggests the following discretization. We associate a node with every configuration space optical vertex, as shown here. Then, we compute what is known as a visibility graph. More specifically, we draw an edge between any two vertices that can be connected by a straight line that lies entirely in free space. Note that this includes every pair of neighboring vertices on the same configuration space obstacle. In order to be able to run this algorithm, we need to be able to determine whether a line segment between any two points intersects a configuration space obstacle. In the situation shown here, where the configuration space obstacles are polygons, this is actually relatively straightforward. We also include the start and end points as nodes in our graph. Once we've done this, we're back to original planning problem we considered earlier, where our goal is to construct the shortest path through the graph between the start node and the end node. A problem that can be readily solved using Dijkstra's algorithm. Here is a result of finding the shortest path in our example. This visibility graph algorithm is actually complete. That is, it will find a path if one exists and report failure if no path can be constructed. This could happen if the start position or end position was entirely surrounded by an obstacle. Moreover, you can prove that this visibility algorithm are actually construct the shortest possible path between the two points. You can see the intuition for this by thinking of the path between the two vertices as a piece of string. Imagine what would happen if you pull this string as tight as possible to eliminate all of the slack. The resulting trajectory would consist of a series of straight lines between vertices corresponding exactly to the edges of the visibility graph However, we can debate whether it's a great idea for our trajectory to clip the obstacles so closely. In practice, we may want to pretend that the robot is actually a bit bigger than it truly is. This would inflate the configuration space obstacles by a safety margin.