Worksheet

U7.5 Resampling

Localisation · University · about 30 min

What this lesson is about

Keeping the good guesses without losing the diversity that lets the filter recover.

• Low variance resampling
• Particle deprivation
• Watching it work

Questions 6 marks in all

1. [1 mark]What does this program print?

   particles = ["A", "B", "C", "D"]
   weights = [0.05, 0.5, 0.3, 0.15]
   N = 4
   step = 1.0 / N
   r = 0.12
   c = weights[0]
   i = 0
   fresh = []
   for m in range(N):
       u = r + m * step
       while u > c and i < N - 1:
           i += 1
           c += weights[i]
       fresh.append(particles[i])
   print(" ".join(fresh))
   

2. [1 mark]With low variance resampling and N = 500, a particle has weight 0.013. How many copies does it get?

   1. A6 or 7
   2. BExactly 7
   3. CAny number from 0 to 500, depending on luck
   4. D13

3. [1 mark]After many rounds of resampling without jitter, the filter is confidently and permanently wrong. What has happened?

   1. AParticle deprivation: every particle is an exact copy of one ancestor, so nothing is left elsewhere to rescue it
   2. BThe weights have underflowed to zero and the floor has taken over
   3. CThe motion noise was too large, so the cloud spread off the mat
   4. DThe effective sample size has grown above N

4. [1 mark]Which of these defend against particle deprivation?

   Tick every answer that is true.

   1. AAdd a small amount of jitter to each copy
   2. BResample only when neff falls below N/2
   3. CInject a few particles scattered over the whole map each tick
   4. DResample on every tick whatever neff is
   5. EUse a smaller sigma in the measurement model

5. [1 mark]Put the steps of low variance resampling in order.

   Number the lines 1 to 5 to put them in the right order.

   1. Set c to the first weight and i to 0
   2. For each m, set the pointer u = r + m * step
   3. Copy particles[i], plus a little jitter, into the new set
   4. Set step = 1/N and draw a single number r between 0 and step
   5. While u > c, move i on and add weights[i] to c

6. [1 mark]Why is low variance resampling preferred to drawing N independent samples?

   1. AIt is less noisy, never gives zero copies to a particle that deserves one, and runs in O(N)
   2. BIt needs no random numbers at all, so it is deterministic
   3. CIt keeps the old weights, so no information is lost
   4. DIt guarantees the resampled cloud has no duplicate particles

The task: resample

Weight a scattered cloud against one reading, then resample it. Print before: and after:, the effective sample size each side, and spread:, the standard deviation of the resampled cloud.

from bugbot import *
import math, random
connect()

N, SIGMA = 500, 3.0
particles = [random.uniform(0, 200) for i in range(N)]

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/u7-5-resampling/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Resample ten times in a row without jitter and print how many distinct values are left.
2. Add jitter and repeat. How many now?
3. Inject 5 percent random particles each round and describe what it costs you when the filter is already right.