03-35 Resampling Wheel Solution

• 0:00 - 0:03
[Narrator] So, here's my implementation of the resampling step,
• 0:03 - 0:06
and it follows the same logic that I gave you in a diagram.
• 0:06 - 0:11
We're creating a new set of particles called P3; it's an empty set in the beginning,
• 0:11 - 0:15
and inside this routine, every time I resample,
• 0:15 - 0:21
I add a particle from the previous particle set with the index index.
• 0:21 - 0:26
So, that's the main loop over here, and at the end I assign P3 back to P.
• 0:26 - 0:28
So, that's the resampling step.
• 0:28 - 0:31
My very first index is drawn at random.
• 0:31 - 0:34
This is a uniform random sampler of all the indices,
• 0:34 - 0:38
and then I had this running variable beta that I set to 0.0,
• 0:38 - 0:43
and I cash away the max of W just to be slightly faster.
• 0:43 - 0:46
You don't have to do this; they come in over here.
• 0:46 - 0:48
Doesn't really matter if we have max over here,
• 0:48 - 0:51
but then I go and produce exactly N particles, and the way I do this
• 0:51 - 0:55
I add to beta a uniform random that is twice as large
• 0:55 - 1:00
and maximum in the range as my max weight W.
• 1:00 - 1:03
Now, 2 times max weight W will be a very large step,
• 1:03 - 1:06
but by adding a random variable that sits between 0 and 1,
• 1:06 - 1:11
I have uniformity in 0 and 2 times MW,
• 1:11 - 1:16
and then while this beta variable is larger than the weight of the current index,
• 1:16 - 1:19
I subtract this weight from my beta value
• 1:19 - 1:23
and I increment index by 1 modeler N
• 1:23 - 1:27
the total number of particles, and when it's smaller I'm done.
• 1:27 - 1:32
I can just take that particle, add it, append it, and repeat.
• 1:32 - 1:35
So, this entire procedure over here is somewhat involved
• 1:35 - 1:38
if you got that right I'm impressed.
• 1:38 - 1:40
I hope you learn something from doing it.
• 1:40 - 1:43
It happens to be really easy to program once you know what to do,
• 1:43 - 1:46
and every time we write a particle filter you can just reuse it.
• 1:46 - 1:49
You never have to think about it again because there's nothing
• 1:49 - 1:52
domain specific in this specific procedure over here.
• 1:52 - 1:56
So, let's run it; if I run it nothing happens to that empty set.
• 1:56 - 2:00
So, let me print out the resulting set of particles.
• 2:00 - 2:02
So, now I have a print P over here.
• 2:02 - 2:06
Let me run it, and of course, I'm going to get 1000 particles, right?
• 2:06 - 2:10
A lot of particles but let's look through them.
• 2:10 - 2:14
If you just look at the first value over here, they are all about the same.
• 2:14 - 2:18
They are all between 76 and 82.
• 2:18 - 2:26
The second one--they're all about 42, 44, 43, 41, 39, 38.
• 2:26 - 2:29
So, what you've gotten here is a set of particles
• 2:29 - 2:31
that are all co-located .
• 2:31 - 2:34
So, instead of having a complete random set of particles, like we had before,
• 2:34 - 2:38
the resampling step--we can see this already gives me particles
• 2:38 - 2:40
of very similar X and Y positions.
• 2:40 - 2:43
Now it turns out the orientations are not very similar.
• 2:43 - 2:46
They jump like crazy, and the reason is--
• 2:46 - 2:52
--well, if you think about it, we only have 1 location so far,
• 2:52 - 2:57
our distances to landmarks are independent of the orientation.
• 2:57 - 3:02
Such as that our orientation plays no role in the protected measurement,
• 3:02 - 3:04
and therefore has no roll in the selection.
• 3:04 - 3:06
Let me make the point, again; here's our 4 landmarks,
• 3:06 - 3:08
and we measure the distances to those.
• 3:08 - 3:12
A robot facing this direction has a certain set of distances.
• 3:12 - 3:16
A robot facing a different direction, like this one,
• 3:16 - 3:19
has the exact same set of distances.
• 3:19 -
Therefore, in our particle future, the heading direction plays no role.
タイトル：
03-35 Resampling Wheel Solution

Other units in this course below:

To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com

more » « less
Team:
Udacity
プロジェクト：
CS373 - Artificial Intelligence
Duration:
03:23
 Udacity Robot edited 英語(米国) subtitles for 03-35 Resampling Wheel Solution Amara Bot added a translation

English subtitles

改訂 Compare revisions

• Edited
Udacity Robot
• Amara Bot