Answers

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))
   

   Answer:

   B B C D

   The pointers are 0.12, 0.37, 0.62 and 0.87 against cumulative weights 0.05, 0.55, 0.85, 1.0. B gets two copies (0.5 x 4 = 2), C and D one each, and A, with 0.05 x 4 = 0.2, gets none.

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
   Answer: A. w x N = 6.5, and low variance resampling gives either floor(wN) or ceil(wN) copies, so 6 or 7. Naive independent draws could give 0 or 15.

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
   Answer: A. Copies are exact, so resampling spends diversity. Once the cloud is a single point, a wrong point can never be corrected.

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
   Answer: A, B, C. Jitter, resampling only when needed and injecting scattered particles all keep diversity. Resampling every tick spends it faster, and a smaller sigma makes the collapse worse.

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
   Answer:

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

   One draw, then equal strides through the cumulative weights. Because the pointer only moves forwards the whole pass is O(N).

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
   Answer: A. It uses one random number, not none, and it does produce duplicates, which is why jitter is still needed.

The task: resample

from bugbot import *
import math, random
connect()

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

from bugbot import *
import math
import random
connect()

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

readings = []
for i in range(10):
    readings.append(distance())
    wait(0.1)
measured = sum(readings) / len(readings)

weights = []
for y in particles:
    d = (200 - y) - measured
    weights.append(math.exp(-d * d / (2 * SIGMA * SIGMA)) + 1e-12)
total = sum(weights)
weights = [w / total for w in weights]
print("before:", round(1.0 / sum(w * w for w in weights), 1))

# low variance resampling: one random start, then equal strides through the cumulative weight
step = 1.0 / N
r = random.uniform(0, step)
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])
particles = fresh

mean = sum(particles) / N
spread = (sum((y - mean) ** 2 for y in particles) / N) ** 0.5
print("after:", round(float(N), 1))
print("spread:", round(spread, 2))