Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,980 --> 00:00:04,162
[INAUDIBLE] obstacles are really
convenient to work with, because
2
00:00:04,162 --> 00:00:07,700
they provide an explicit description
of the configure space obstacles.
3
00:00:08,830 --> 00:00:11,070
Often times, we don't have this luxury and
4
00:00:11,070 --> 00:00:15,110
the obstacles are instead defined
implicitely through a collision function.
5
00:00:16,330 --> 00:00:21,766
More specifically, if we let x denote the
coordinates of a point in configuration
6
00:00:21,766 --> 00:00:26,570
space, we're usually able to define
a function, let's call it CollisionCheck,
7
00:00:26,570 --> 00:00:31,600
that returns zero if the configuration
is in freespace, and one otherwise.
8
00:00:33,300 --> 00:00:38,630
In this slide, we show a situation
where our putitive robot,
9
00:00:38,630 --> 00:00:42,030
the red polygon, is entirely in freespace.
10
00:00:42,030 --> 00:00:44,560
So we want our CollisionCheck
function to return a zero.
11
00:00:46,930 --> 00:00:52,340
In this next case, the robot is
colliding with one of the obstacles.
12
00:00:52,340 --> 00:00:55,490
So we would want our CollisionCheck
function to return a one for
13
00:00:55,490 --> 00:00:56,220
this configuration.
14
00:00:59,140 --> 00:01:03,640
Collision detection is a key subroutine
for most path planning algorithms, and
15
00:01:03,640 --> 00:01:07,150
it often boils down to computing the
answer to some basic geometric questions.
16
00:01:08,290 --> 00:01:09,770
Lets go back and consider our example.
17
00:01:11,200 --> 00:01:13,928
Here we can imagine
representing both our robot and
18
00:01:13,928 --> 00:01:17,615
our obstacle as collections of triangles,
as shown in this figure.
19
00:01:18,905 --> 00:01:20,505
Deciding whether the robot and
20
00:01:20,505 --> 00:01:23,825
the obstacle intersect is now
a matter of determining whether
21
00:01:23,825 --> 00:01:27,935
any of the robot's triangles overlap
any of the obstacle's triangles.
22
00:01:29,705 --> 00:01:34,470
Here we can make use of the fact
that triangles are convex polygons.
23
00:01:34,470 --> 00:01:39,599
In this circumstance, it means that we can
test where the two triangles intersect
24
00:01:39,599 --> 00:01:44,207
by checking all of the sides on both
triangles, and testing whether any of
25
00:01:44,207 --> 00:01:49,336
those sides act as separating lines, where
all of the points from one triangle lie
26
00:01:49,336 --> 00:01:54,348
on one side of the line, and all of those
from the other lie on the opposite side.
27
00:01:54,348 --> 00:01:58,236
If you can find such a separating edge,
among the six edges among
28
00:01:58,236 --> 00:02:02,780
the two triangles, you have proved
that the triangles don't intersect.
29
00:02:03,890 --> 00:02:06,950
If not, you can conclude that they do.
30
00:02:06,950 --> 00:02:09,270
This idea of finding a separating line, or
31
00:02:09,270 --> 00:02:13,020
plane, actually generalizes
to higher dimensions.
32
00:02:13,020 --> 00:02:18,380
For instance, If you have a robot composed
of convex polygons in three dimensions
33
00:02:18,380 --> 00:02:20,830
like boxes or pyramids.
34
00:02:20,830 --> 00:02:24,741
You can check for collision by
testing if any of the faces on one of
35
00:02:24,741 --> 00:02:27,651
the polygons acts as
a separating hyperplane.
36
00:02:27,651 --> 00:02:31,064
In the cases that we've considered so
far, the robots and
37
00:02:31,064 --> 00:02:35,150
the obstacles are basically
composed of simple polygons.
38
00:02:35,150 --> 00:02:36,520
So to test for collision,
39
00:02:36,520 --> 00:02:41,060
we first transform the robot according to
the configurations space parameters and
40
00:02:41,060 --> 00:02:45,470
then test for collision between
the robot's components and the obstacles.
41
00:02:45,470 --> 00:02:49,970
In this case, this amounts to testing
whether any of the red triangles
42
00:02:49,970 --> 00:02:51,899
overlap any of the black triangles.
43
00:02:53,990 --> 00:02:58,996
In this case we would want our
CollisionCheck function to return a zero,
44
00:02:58,996 --> 00:03:02,209
indicating that no
intersections are found.
45
00:03:02,209 --> 00:03:07,214
In this next case, there are in
fact red triangles that do overlap
46
00:03:07,214 --> 00:03:12,859
the black triangles so our CollisionCheck
function should return a one.
47
00:03:12,859 --> 00:03:18,072
Another question that we may be
interested in answering is whether all of
48
00:03:18,072 --> 00:03:23,881
the points along the line segment between
two configuration space points x1 and
49
00:03:23,881 --> 00:03:25,540
x2 are in freespace.
50
00:03:25,540 --> 00:03:26,470
Sometimes we're lucky and
51
00:03:26,470 --> 00:03:29,589
we can actually answer that
question definitively by analysis.
52
00:03:31,080 --> 00:03:34,240
In practice,
if two points are both in freespace, and
53
00:03:34,240 --> 00:03:38,820
they are close enough to each other,
given some reasonable distance metric,
54
00:03:38,820 --> 00:03:42,670
then we tend to assume that a straight
line path between them is collision free.
55
00:03:42,670 --> 00:03:46,510
This can obviously go horribly
wrong if we're not careful.
56
00:03:46,510 --> 00:03:48,830
But let's live dangerously for a second.
57
00:03:48,830 --> 00:03:51,490
In considering our 2D planning problem,
58
00:03:51,490 --> 00:03:56,380
we can proceed by sampling a grid of
locations in the configuration space.
59
00:03:57,760 --> 00:03:59,874
For each grid point we
determine whether or
60
00:03:59,874 --> 00:04:02,820
not it is in freespace using
our CollisionCheck function.
61
00:04:03,930 --> 00:04:06,945
All the grid points that are in
freespace are going to be treated as
62
00:04:06,945 --> 00:04:08,620
nodes in our graph.
63
00:04:08,620 --> 00:04:12,359
This figure shows the resulting
sampled freespace points.
64
00:04:14,020 --> 00:04:18,200
in this example, we're going to go ahead
and assume that if two adjacent grid
65
00:04:18,200 --> 00:04:23,570
points are both in freespace, then all the
points between them are also in freespace.
66
00:04:23,570 --> 00:04:26,290
And we connect them by an etch,
as shown here.
67
00:04:27,340 --> 00:04:29,240
In this case, we've chosen matters so
68
00:04:29,240 --> 00:04:33,560
that the start and
end points are both nodes in the graph.
69
00:04:33,560 --> 00:04:38,410
We can then employ anyone of our usual
suite of graph-based planning tools
70
00:04:38,410 --> 00:04:40,590
to search for
a path between the two nodes.
71
00:04:42,350 --> 00:04:45,546
The resulting path through
the graph is shown here, in red.6656
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.