As I mentioned in previous videos, it is common to represent a continuous free C-space as a graph and to search on that graph. If that graph happens to be something called a "roadmap," then it is possible to ensure the property of completeness: if a path exists, the planner will find one.

To be a roadmap, the graph has to satisfy the following conditions: First, it must be easy, or at least possible, to find free-space paths between any free configuration q and some configuration on the roadmap. Second, there must be a connected component of the roadmap for every connected component of the free C-space.

If these conditions are satisfied, then any path planning problem can be solved by first finding a path from the start configuration to the roadmap, then finding a path from the goal configuration to the roadmap, then finding a path on the roadmap to connect the two.

For most C-spaces, constructing a true roadmap is complex and rarely done, but there are some examples for which it is simple. One such example is the case where a polygonal mobile robot, shown here as a square, translates in a plane among polygonal obstacles, indicated here in gray. The first step is to transform the obstacles into C-space obstacles. Since the obstacles are in a plane, and the C-space is also a plane, this transformation is simple. We just slide the square robot around the edges of the obstacles and keep track of the path traced out by the robot's reference point, at its lower-left corner. This results in C-space obstacles that look like this. If the reference point of the robot is outside the regions shaded gray, then the robot is in free space.

Next, we construct a graph whose nodes are the corners of the C-space obstacles. Edges are between nodes that can see each other by a straight line that does not go through an obstacle. This graph is called a visibility graph, and it is also a roadmap of the free C-space, since any free configuration can be connected to it by a straight line in free space. We can now complete the graph by connecting the start and goal nodes to all visible nodes. Each edge has a weight according to the length of the edge. We can now search the graph using A-star to find the shortest path between the start and goal configurations. This algorithm is complete, since it constructs a true roadmap, and it is optimal, meaning that it finds the shortest path. Visualizing the robot's motion, we see that the shortest path grazes the edges of the obstacles. If this is undesired behavior, the obstacles can be grown slightly.

There are few interesting motion planning problems for which we can find a practical, complete, and optimal planner. In practice, we discretize the free C-space in such a way that resolution or probabilistic completeness is the best we can hope for. In the next video we'll discretize the C-space as a grid.