Return to Video

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:
Unit 1: http://www.youtube.com/playlist?list=PL1EF620FCB11312A6
Unit 2: http://www.youtube.com/playlist?list=PL107FD47786234011
Unit 3: http://www.youtube.com/playlist?list=PL5493E5D24A081719
Unit 4: http://www.youtube.com/playlist?list=PLAADAB4F235FE8D65
Unit 5: http://www.youtube.com/playlist?list=PL1B9983ACF22B1920
Unit 6: http://www.youtube.com/playlist?list=PLC9ED5AC39694C141
QA: http://www.youtube.com/playlist?list=PL3475310BFB1CBE34

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