A cloud of guesses

Representing a belief as a thousand samples, and what that buys over a mean and a variance.

U7.2LocalisationUniversity30 min

Do this lesson in the simulator

The particle filter's idea is blunt and it works: instead of describing the belief with a formula, keep a few hundred guesses and treat the collection as the belief.

Each particle is a complete guess about the state: a pose the robot might have. A thousand of them scattered over the mat is the statement "it could be anywhere". A thousand clustered in a 5 cm patch is "it is there, and I am confident".

from bugbot import *
import random
connect()

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

# what the cloud says, summarised
xs = [p[0] for p in particles]
mean = sum(xs) / N
spread = (sum((x - mean) ** 2 for x in xs) / N) ** 0.5
print("mean x", round(mean, 1), "spread", round(spread, 1))
print("a uniform spread over 200 cm should be about", round(200 / 12 ** 0.5, 1))

Run this in the simulator

What this buys

  • Any shape of belief. Two clusters, a stripe, a ring: the particles simply sit where the belief is.
  • Any motion model. No linear algebra, no Jacobians. If you can simulate the robot, you can move a particle.
  • Any measurement model. If you can say how likely a reading is given a pose, you can weight a particle. Non-Gaussian, discontinuous, table-driven: all fine.

That last point is why particle filters took over robot localisation. Range sensors have horrible likelihood functions, full of spikes and floors for "no return", and none of it fits a Gaussian. It fits a particle filter without complaint.

What it costs

  • Compute. Every particle is moved and weighted every tick. A thousand particles at 10 Hz is ten thousand evaluations a second.
  • The curse of dimensionality. The number of particles needed grows exponentially with the number of dimensions of the state. For a ground robot with (x, y, heading) a few hundred to a few thousand is fine. For a 12 degree of freedom arm it is hopeless, and this is not the tool.
  • Randomness. Two runs give slightly different answers, which makes debugging harder.

How many particles

Enough that some of them start near the truth. If none do, the filter cannot recover, because it has no way to invent a guess it never had. For a 200 by 200 mat with heading unknown, a few hundred to a thousand is sensible; for tracking a known position, fifty is plenty.

Adaptive schemes exist, of which KLD sampling is the standard one: many particles while the robot is lost, few once it is confident. Worth knowing the name.

Task: a thousand guesses

Make a cloud spread evenly over the whole mat and print particles:, mean x: and spread x:.

from bugbot import *
import random
connect()

N = 600

Challenges

  1. Print the spread of a cloud that is all in one place. What is it?
  2. Make a cloud that says "in one of two corners" and print its mean. Is the mean a sensible answer?
  3. Work out how much of the mat 600 particles cover if each represents a 5 cm patch.