Original subtitles

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.