Answers

U7.6 Monte Carlo localisation

Localisation · University · about 35 min

What this lesson is about

The three steps in a loop on a real mat, with tags as the measurement.

• Mat coordinates, not travel
• Only while it faces the wall
• Using tags as well
• When it goes wrong

Questions 7 marks in all

1. [1 mark]Put one tick of Monte Carlo localisation in order.

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

   1. Weigh every particle against the sensor reading
   2. Move every particle by the odometry, plus noise
   3. Report the weighted mean as the estimate
   4. If neff is low, resample
   Answer:

   Move every particle by the odometry, plus noise
   Weigh every particle against the sensor reading
   If neff is low, resample
   Report the weighted mean as the estimate

   Predict, correct, resample if needed, then report. Resampling before weighting would copy particles on stale weights.

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

   depth = [0.9, 0.3, 0.05]
   tag = [0.05, 0.3, 0.9]
   both = [a * b for a, b in zip(depth, tag)]
   total = sum(both)
   print([round(w / total, 2) for w in both])
   added = [a + b for a, b in zip(depth, tag)]
   print([round(w, 2) for w in added])
   

   Answer:

   [0.25, 0.5, 0.25]
   [0.95, 0.6, 0.95]

   Multiplying gives 0.045, 0.09, 0.045, so the middle particle, which neither sensor rules out, wins with half the weight. Adding scores the outer particles higher even though one sensor all but rules each of them out.

3. [1 mark]The filter has a weight from the depth sensor and a weight from a tag seen by the camera for each particle. How should they be combined?

   1. AMultiply them, which is Bayes' rule for independent measurements
   2. BAdd them, so that each sensor contributes its share
   3. CTake whichever is larger
   4. DAverage them, so neither sensor dominates
   Answer: A. Independent evidence multiplies. A particle one sensor rules out should stay ruled out, and multiplication is what does that.

4. [1 mark]The cloud collapses onto the wrong answer. Which of these could cause it?

   Tick every answer that is true.

   1. ANot enough jitter when resampling
   2. BA measurement sigma that is too small
   3. CA motion model that is too confident
   4. DReadings taken while the robot turns, weighed with a model that assumes it faces the wall square on
   5. EA measurement that is not informative enough to rule places out
   Answer: A, B, C, D. The first three all make the filter over-confident, and readings its model cannot explain drag the cloud to the wrong place. An uninformative measurement causes the opposite failure: a cloud that never collapses.

5. [1 mark]The spread of the cloud stays large however long the robot stands still. What does the page recommend?

   1. AMove the robot, so one ambiguous reading becomes several that disagree about the wrong places
   2. BInject more scattered particles each tick
   3. CReduce the jitter to zero
   4. DIncrease the number of particles until it collapses
   Answer: A. A cloud that never collapses means the measurement is not informative enough from here. More particles or less jitter cannot create information.

6. [1 mark]The filter tracks well for a minute and then loses the robot for good. What is the likely cause and fix?

   1. AParticle deprivation; inject a few scattered particles each tick
   2. BToo many particles; reduce N
   3. CSigma too large; reduce it
   4. DThe odometry noise is too small; set it to zero
   Answer: A. Over time the cloud loses diversity, and once it is wrong there is nothing elsewhere to rescue it. A few injected particles are the insurance.

7. [1 mark]What does MCL give the robot that dead reckoning does not?

   1. AA position in the mat's own frame, which other things are described in, rather than a distance from wherever it started
   2. BA smoother velocity estimate
   3. CAn estimate with no noise in it
   4. DThe map of the mat
   Answer: A. Localisation places the robot in the frame the goal is described in, which is what lets it go somewhere on purpose.

The task: Monte Carlo localisation

from bugbot import *
import math, random
connect()

DT, N, SIGMA = 0.1, 300, 3.5
particles = [random.uniform(0, 200) for i in range(N)]

from bugbot import *
import math
import random
connect()

DT = 0.1
N = 300
SIGMA = 3.5
particles = [random.uniform(0, 200) for i in range(N)]
weights = [1.0 / N] * N

def weigh(measured):
    global weights
    w = []
    for y in particles:
        d = (200 - y) - measured
        w.append(math.exp(-d * d / (2 * SIGMA * SIGMA)) + 1e-12)
    total = sum(w)
    weights = [v / total for v in w]

def resample():
    global particles, weights
    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] + random.gauss(0, 0.8))
    particles = fresh
    weights = [1.0 / N] * N

forward(60)
for tick in range(70):
    v = flow()[1]
    particles = [y + v * DT + random.gauss(0, 0.4) for y in particles]
    weigh(distance())
    neff = 1.0 / sum(w * w for w in weights)
    if neff < N / 2:
        resample()
    mean = sum(w * y for w, y in zip(weights, particles))
    spread = math.sqrt(sum(w * (y - mean) ** 2 for w, y in zip(weights, particles)))
    plot("spread", spread)
    if mean > 118:
        stop()
    wait(DT)
stop()
mean = sum(w * y for w, y in zip(weights, particles))
print("my y:", round(mean, 1))