Where am I?

Tracking against global localisation, and why one Gaussian is not enough for the second.

U7.1LocalisationUniversity25 min

Do this lesson in the simulator

Two different problems hide behind that question, and they need different machinery.

Tracking. The robot roughly knows where it is and wants to keep knowing. The error is small, the belief is a single blob, and U6's Kalman filter is exactly right.

Global localisation. The robot has no idea. It has woken up somewhere on the mat, or it has been picked up and put down, or the filter has diverged and has to start again. The belief is not a blob: it is every place consistent with what the robot can see, and there can be dozens of them, scattered.

A Kalman filter cannot represent that. A Gaussian has one peak by construction, and "I am either here or over there" has two.

One reading, many places

The robot below sits facing the far wall and measures the distance to it. That reading pins down y and says absolutely nothing about x.

from bugbot import *
connect()

readings = [distance() for i in range(10) if wait(0.1) is None]
measured = sum(readings) / len(readings)
print("measured", round(measured, 1))

# which places on the mat would produce that same reading?
for gy in range(0, 200, 20):
    row = "".join("#" if abs((200 - gy) - measured) < 8 else "." for gx in range(0, 200, 10))
    print(str(gy).rjust(3), row)

Run this in the simulator

A stripe of hashes. Every position on that stripe explains the measurement equally well, and until the robot moves or sees something else, all of them are the answer.

Why symmetry is the hard case

A square room with four identical corners is the classic. Sit in one and the readings are the same as in any of the other three. No amount of cleverness with a single reading resolves it, because the information is not there.

What resolves it is moving. Drive two metres and take another reading, and most of the candidates become inconsistent with the pair. That is the real work of localisation: not one clever measurement but the accumulation of many ordinary ones, each cutting the possibilities down.

What the belief has to be able to say

  • "I am at (100, 60), give or take 3 cm." A Gaussian does this.
  • "I am on a line somewhere." A Gaussian does not.
  • "I am in one of four corners." A Gaussian certainly does not.
  • "I have no idea." A Gaussian with an enormous variance, which behaves badly in practice.

The particle filter represents all four, by giving up on formulas and using a few hundred samples instead.

Task: which places are possible?

Standing still, print reading:, the distance the robot measures ahead, and possible:, how many positions on a 10 cm grid across the mat would give that same reading to within a few centimetres.

from bugbot import *
connect()

readings = []

Challenges

  1. Add a second sensor reading, to one side, by turning 90 degrees. How many places survive both?
  2. Work out how many places survive if the robot also knows its heading to within 10 degrees.
  3. Describe, in one sentence, a mat on which no number of readings from one spot would ever be enough.