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

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: SLAM explained: simultaneous localisation and mapping

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.

A belief with one peak, which a Gaussian can hold, and one with two peaks, which it cannotTrackingone peak: a Gaussian fits0100200place across the mat, cmhere, give or take 3 cmGlobal localisationtwo peaks: a Gaussian cannot0100200place across the mat, cmhereor therebest singleGaussian: its peakis in the middle
A Gaussian always has one peak. Asked to say "here or over there", the nearest it can get is the dashed hump: low, wide, and most sure of the middle, the one place the robot is not.

One reading, many places

The robot below sits facing the far wall square on and measures the distance to it. The far wall is at y = 200, so a robot at height y up the mat should read 200 - y. 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

It reads 139.7 cm, and the answer is a stripe of hashes: the whole row at y = 60, from one side of the mat to the other. The robot really is at y = 60, but 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.

Every place on the row y = 60 would give the same reading of the far wallfar wall, y = 200060180y, cmall read 140y = 60:200 - 60 = 140,within 8 of 139.7every other rowis too far out
The lesson's grid, one dot every 10 cm across and 20 cm up. Only the 20 dots on the row y = 60 explain a reading of 139.7 cm, and they explain it equally well: the reading fixes y and says nothing about x.

200 - y is only the right prediction while the robot faces the far wall square on. Turned part of the way to another wall, the sensor looks along a slant and reads something else entirely. U7.4 comes back to this.

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.

In a square room the same two readings come from four different placesababababa ahead, b to the left,in all four
The robot is at the green one. Turn the room a quarter turn and it looks exactly the same, so the three red places give the same two readings and nothing the robot measures can pick between them.

What resolves it is moving. Drive somewhere else, or turn to face another wall, 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. Take it once the turn has finished: a reading taken part way round is at a slant and matches neither wall. 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.