All language subtitles for 01_2-4-visibility-graph.en

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.