Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,810 --> 00:00:04,900
Another approach to path planning that is
particularly effective in situations where
2
00:00:04,900 --> 00:00:08,430
the configuration space obstacles
can be modeled as polygons,
3
00:00:08,430 --> 00:00:09,590
is cell decomposition.
4
00:00:10,970 --> 00:00:16,290
Here, our goal is to divide the robot's
free space into a set of simpler regions
5
00:00:16,290 --> 00:00:19,500
and then form a graph where
the nodes of the regions and
6
00:00:19,500 --> 00:00:23,190
the edges indicate which regions
are adjacent to each other.
7
00:00:23,190 --> 00:00:27,170
This figure shows a common approach to
constructing such a decomposition for
8
00:00:27,170 --> 00:00:29,940
a two-dimensional configuration space.
9
00:00:29,940 --> 00:00:34,880
In this case, we sort the obstacle
vertices based on their x-coordinates,
10
00:00:34,880 --> 00:00:39,180
and proceed from left to right, dividing
the free space up into regions as we go.
11
00:00:40,890 --> 00:00:45,290
We can show that this procedure ends up
dividing the two dimensional free space
12
00:00:45,290 --> 00:00:48,700
into a collection of trapezoidal or
triangular regions.
13
00:00:49,790 --> 00:00:53,450
The nice thing about this is
that these shapes are convex,
14
00:00:53,450 --> 00:00:56,220
which means that the robot can
safely move in a straight line
15
00:00:56,220 --> 00:00:59,680
between any two points
in each of the cells.
16
00:00:59,680 --> 00:01:02,380
As we said earlier we can form a graph
17
00:01:02,380 --> 00:01:05,780
where the nodes are these trapezoidal
regions of free space and
18
00:01:05,780 --> 00:01:08,970
the edges indicate which of these
regions are adjacent to each other.
19
00:01:08,970 --> 00:01:12,330
Path planning is then carried
out by finding out which
20
00:01:12,330 --> 00:01:15,530
cell contains the start location and
which the goal.
21
00:01:15,530 --> 00:01:20,210
And then planning a path through the graph
between these two nodes as shown here.2009
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.