All language subtitles for 02_2-5-trapezoidal-decomposition.en

Another approach to path planning that is
particularly effective in situations where

the configuration space obstacles
can be modeled as polygons,

is cell decomposition.

Here, our goal is to divide the robot's
free space into a set of simpler regions

and then form a graph where
the nodes of the regions and

the edges indicate which regions
are adjacent to each other.

This figure shows a common approach to
constructing such a decomposition for

a two-dimensional configuration space.

In this case, we sort the obstacle
vertices based on their x-coordinates,

and proceed from left to right, dividing
the free space up into regions as we go.

We can show that this procedure ends up
dividing the two dimensional free space

into a collection of trapezoidal or
triangular regions.

The nice thing about this is
that these shapes are convex,

which means that the robot can
safely move in a straight line

between any two points
in each of the cells.

As we said earlier we can form a graph

where the nodes are these trapezoidal
regions of free space and

the edges indicate which of these
regions are adjacent to each other.

Path planning is then carried
out by finding out which

cell contains the start location and
which the goal.

And then planning a path through the graph
between these two nodes as shown here.