Skip to content
LumenaryAcademy
Perception 70 min

Particle filters and localisation

Represent a belief by thousands of guesses, keep the ones the sensors agree with, and a robot can find itself in a building that looks the same in every direction.

Code tested · 5AI-draftedAwaiting review by a roboticist

Your guides: Chloe · The Builder, Margaret · The Experimenter, Gideon · The Safety Engineer

MotivationH

When the answer has several peaks

A cleaning robot is switched on in a hotel in Kyoto in the middle of the night. Somebody carried it from the corridor where it last stopped and set it down in a different one. Every corridor on the floor has the same carpet, the same doors at the same spacing, the same fire extinguisher in a niche. What should the robot believe about where it is?

Not "somewhere in the middle of the floor", which is what a Kalman filter's single Gaussian would say if it tried to cover every corridor at once, and which is the one place the robot certainly is not. The honest belief has a peak in each corridor that matches what it sees, and nothing in between. Only after it drives to the end and sees the lift lobby, or the window, can it decide which peak is real. The histogram filter could represent such a belief, but a grid over a hotel floor at useful resolution has hundreds of millions of cells. The Kalman filter is cheap but has one peak.

The particle filter keeps the Bayes filter and represents the belief by a few thousand samples, called particles, each a complete guess at the robot's pose. Particles cluster where the robot is likely to be and avoid where it is not, so they spend memory only where it matters, and any number of peaks costs nothing extra. Applied to robots, it is called Monte Carlo localisation (MCL), and in the form of AMCL it is the default localiser of ROS 2's navigation stack, used on many research and commercial mobile robots.

IntuitionH

A belief made of guesses

Think of each particle as a small ghost robot with its own pose. The filter repeats three steps.

  1. Move. Every ghost executes the real robot's command, each with its own random slip drawn from the motion model. The cloud shifts and spreads, as a belief should when the robot moves.
  2. Weigh. When a reading arrives, each ghost asks: "if I were the real robot, how likely is this reading?" That likelihood is its weight. Ghosts in places that match the reading weigh a lot; the rest weigh almost nothing.
  3. Resample. Draw a new set of ghosts from the old one, each picked with probability proportional to its weight. Heavy ghosts are copied several times; light ones die out. The total number stays the same.

After a few rounds, the ghosts crowd into the places consistent with everything the robot has seen, which is exactly what the belief should look like.

true pose10 m × 10 m hall; arrows show each cluster's heading
Monte Carlo localisation in a symmetric hall: five identical posts, four in a square and one by the east wall. A robot that sees two posts and nothing else is consistent with several poses, each a quarter-turn of the others about the hall's centre, and the particles gather around them. The fourth cluster, beside the east post, is nearly empty: a robot there would have seen that post.

Analogy, not a formal construction

A search party looking for a lost hiker spreads out, everyone walking the route the hiker's phone says they took. Each time the hiker radios a landmark ("I can see a waterfall below me"), searchers who can see a waterfall below them call back, and the coordinator sends more searchers to those spots and recalls the others. No one needs a map of probabilities: the density of searchers is the map.

DefinitionsH

Importance sampling and the particle filter

Definition— Particle representation

A belief bel(x)\mathrm{bel}(x) is represented by NN samples x[1],…,x[N]x^{[1]}, \dots, x^{[N]} with weights w[1],…,w[N]w^{[1]}, \dots, w^{[N]} summing to 1. Any expectation is approximated by a weighted average: E[g(x)]≈∑iw[i]g(x[i])\mathbb{E}[g(x)] \approx \sum_i w^{[i]} g(x^{[i]}), with an error that shrinks like 1/N1/\sqrt{N} whatever the dimension of xx.

Why weight by the likelihood? Suppose we want samples from a target distribution ff but can only draw from a proposal gg. Drawing from gg and giving each sample the weight f(x)/g(x)f(x)/g(x) corrects the mismatch exactly in expectation; this is importance sampling. In the particle filter, the target is the posterior η p(zt∣xt) bel‾(xt)\eta\,p(z_t \mid x_t)\,\overline{\mathrm{bel}}(x_t) and the proposal is the prediction bel‾(xt)\overline{\mathrm{bel}}(x_t), from which the move step has already sampled. Their ratio is η p(zt∣xt)\eta\, p(z_t \mid x_t): the importance weight is just the measurement likelihood.

Definition— Monte Carlo localisation (the bootstrap particle filter)

Given particles {xt−1[i]}\{x_{t-1}^{[i]}\}, a command utu_t and a reading ztz_t:

  1. Sample: for each ii, draw xt[i]∼p(xt∣xt−1[i],ut)x_t^{[i]} \sim p(x_t \mid x_{t-1}^{[i]}, u_t).
  2. Weight: w[i]∝p(zt∣xt[i])w^{[i]} \propto p(z_t \mid x_t^{[i]}), normalised to sum to 1.
  3. Resample: draw NN new particles, each equal to xt[i]x_t^{[i]} with probability w[i]w^{[i]}, and reset all weights to 1/N1/N.

Resampling is what keeps the filter healthy. Without it, after a few dozen readings almost all the weight would sit on one or two particles and the others would be wasted computation. A standard measure of this degeneracy is the effective sample size,

Neff=1∑i(w[i])2,N_{\text{eff}} = \frac{1}{\sum_i \big(w^{[i]}\big)^2},

which equals NN when all weights are equal and 1 when one particle has all the weight. Many implementations resample only when NeffN_{\text{eff}} falls below, say, N/2N/2.

Definition— Low-variance (systematic) resampling

Lay the normalised weights end to end along the interval [0,1)[0, 1). Draw one random number rr in [0,1/N)[0, 1/N) and place NN pointers at r,r+1/N,r+2/N,…r, r + 1/N, r + 2/N, \dots. Each pointer selects the particle whose segment it falls in.

0.050.10.050.20.60.10.30.50.70.9
Low-variance resampling of five particles with weights 0.05, 0.1, 0.05, 0.2 and 0.6, laid end to end. Five evenly spaced pointers, shifted by one random offset, pick the particles: the heaviest is picked three times, the 0.1 and 0.2 particles once each, the two lightest not at all. With independent draws instead, the heaviest could be picked anywhere from zero to five times.

A particle with weight ww gets either ⌊Nw⌋\lfloor Nw \rfloor or ⌈Nw⌉\lceil Nw \rceil copies, never wildly more or fewer, and the whole step costs O(N)O(N) with a single random number.

ComputationC

Monte Carlo localisation in a symmetric hall

The program below localises a robot in a 10 m×10 m10\,\text{m} \times 10\,\text{m} hall with five identical posts: four in a square, which makes the hall look the same after a quarter turn, and one by the east wall, which breaks the symmetry. The robot's sensor reports the range and bearing of every post within 4 m but cannot tell posts apart, so each reading's likelihood is an average over all the posts it might have come from, plus a small floor for outliers. Seeing a different number of posts from the number a particle expects also lowers its weight. The robot drives anticlockwise round a 2.5 m circle; 5,000 particles start spread uniformly over every position and heading. The table tracks how the weight is shared between the truth and the three quarter-turned look-alike poses; the maps show the particle cloud (after resampling, so density is belief) with P for posts and R for the robot's cell, drawn on top of any particles there.

python
import numpy as np

rng = np.random.default_rng(5)
posts = np.array([[2, 2], [8, 2], [2, 8], [8, 8], [9, 5]], dtype=float)  # identical posts; (9, 5) breaks the symmetry
SIZE, RANGE, N = 10.0, 4.0, 5000             # a 10 m x 10 m hall; the sensor sees posts within 4 m
sig_r, sig_b = 0.2, np.radians(6)            # range and bearing noise
wrap = lambda a: (a + np.pi) % (2 * np.pi) - np.pi

def move(p, v, w):
    """Sample the motion model: unicycle step with noisy speed and turn, for an (n, 3) array of poses."""
    n = len(p)
    th = p[:, 2] + w + rng.normal(0, 0.02, n)
    v = v + rng.normal(0, 0.03, n)
    return np.stack([p[:, 0] + v * np.cos(th), p[:, 1] + v * np.sin(th), wrap(th)], axis=1)

def observe(pose):
    """(range, bearing) to every post within range. The posts look identical: no labels."""
    d = posts - pose[:2]
    r, b = np.hypot(d[:, 0], d[:, 1]), wrap(np.arctan2(d[:, 1], d[:, 0]) - pose[2])
    s = r < RANGE
    return np.stack([r[s] + rng.normal(0, sig_r, s.sum()), b[s] + rng.normal(0, sig_b, s.sum())], axis=1)

def likelihood(p, z):
    """p(z | pose) for every particle: each reading may come from any post, plus a small outlier floor."""
    d = posts[None, :, :] - p[:, None, :2]
    r, b = np.hypot(d[..., 0], d[..., 1]), np.arctan2(d[..., 1], d[..., 0]) - p[:, None, 2]
    w = np.ones(len(p))
    for zr, zb in z:
        g = np.exp(-0.5 * (((zr - r) / sig_r) ** 2 + (wrap(zb - b) / sig_b) ** 2))
        w *= g.mean(axis=1) + 1e-3
    return w * np.where((r < RANGE).sum(axis=1) == len(z), 1.0, 0.1)   # seeing the wrong number of posts is evidence too

def low_variance_resample(p, w):
    positions = (rng.random() + np.arange(len(w))) / len(w)          # one random offset, evenly spaced pointers
    return p[np.minimum(np.searchsorted(np.cumsum(w), positions), len(w) - 1)]

def picture(p, truth):
    """ASCII map of the hall, 2 characters per metre across and 1 per metre up. P = post, R = robot."""
    H, _, _ = np.histogram2d(p[:, 0], p[:, 1], bins=[20, 10], range=[[0, SIZE], [0, SIZE]])
    rows = [[" .:#@"[int(np.searchsorted([1, 20, 100, 400], H[i, j], side="right"))] for i in range(20)] for j in range(10)]
    for x, y in posts:
        rows[int(y)][int(2 * x)] = "P"
    rows[int(truth[1])][int(2 * truth[0])] = "R"
    return "\n".join("|" + "".join(r) + "|" for r in reversed(rows))

def turned(pose, k):                          # the robot's position turned k quarter-turns about the hall's centre
    c, s = np.cos(k * np.pi / 2), np.sin(k * np.pi / 2)
    dx, dy = pose[0] - 5, pose[1] - 5
    return np.array([5 + c * dx - s * dy, 5 + s * dx + c * dy])

truth = np.array([5.0, 7.5, np.pi])           # the robot starts at the top of a 2.5 m circle, heading west
p = np.column_stack([rng.uniform(0, SIZE, N), rng.uniform(0, SIZE, N), rng.uniform(-np.pi, np.pi, N)])
print(" t   N_eff   share of particles within 1 m of: truth | truth turned 90, 180, 270 deg   error of mean")
for t in range(0, 61):
    if t > 0:
        truth = move(truth[None], 0.3, 0.12)[0]          # the robot drives anticlockwise round the circle
        p = move(p, 0.3, 0.12)                            # every particle samples the same motion
    w = likelihood(p, observe(truth))
    w /= w.sum()
    share = [w[np.hypot(*(p[:, :2] - turned(truth, k)).T) < 1.0].sum() for k in range(4)]
    if t in (0, 3, 6, 9, 12, 15, 18, 24, 40, 60):
        err = np.hypot(*(w @ p[:, :2] - truth[:2]))
        print(f"{t:2d}  {1 / np.sum(w**2):6.0f}        {share[0]:5.2f} | {share[1]:5.2f} {share[2]:5.2f} {share[3]:5.2f}"
              f"                     {err:5.2f} m")
    p = low_variance_resample(p, w)
    if t in (3, 24):
        print(picture(p, truth))              # after resampling, particle density shows the belief
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

At the first reading the effective sample size is 25: of 5,000 random guesses only a handful explain two posts at those ranges and bearings. After three steps the particles have gathered into clusters, and the weight is split between the truth (0.18), its 90° look-alike (0.28) and its 180° look-alike (0.42), with nothing on the 270° pose beside the east post. The map at step 3 shows these clusters, plus another just above the truth that fits the readings almost as well. At step 6 the filter is in real danger: 93% of the weight sits on the 90° look-alike and only 4% on the truth. Then the look-alike begins to approach the east post, which it should be able to see and cannot, and the truth's share climbs to 0.62, 0.84, 0.92 and finally 1.00 by step 18. From then on the weighted mean stays within 0.2 m of the truth, usually within a few centimetres.

ComputationC

Why the way you resample matters

Two resampling schemes are common. Multinomial resampling makes NN independent draws. Low-variance resampling uses the comb of evenly spaced pointers. Both give each particle NwNw copies on average; they differ in the variance around that average, and in what happens when the weights carry no information at all.

python
import numpy as np

rng = np.random.default_rng(0)

def multinomial(w):                    # N independent draws, each picking particle i with probability w[i]
    return rng.choice(len(w), size=len(w), p=w)

def low_variance(w):                   # one random number, N evenly spaced pointers into the cumulative weights
    positions = (rng.random() + np.arange(len(w))) / len(w)
    return np.minimum(np.searchsorted(np.cumsum(w), positions), len(w) - 1)

N = 1000
# 1. Weights carrying real information: how many copies does particle i get, compared with N * w[i]?
w = rng.random(N) ** 4
w /= w.sum()
for name, f in [("multinomial", multinomial), ("low-variance", low_variance)]:
    errs = [np.bincount(f(w), minlength=N) - N * w for _ in range(200)]
    print(f"{name:12s}: RMS deviation of copy counts from N*w = {np.sqrt(np.mean(np.square(errs))):.3f}")

# 2. Weights carrying no information (all equal), resampled 100 times in a row: how many distinct particles survive?
for name, f in [("multinomial", multinomial), ("low-variance", low_variance)]:
    ids = np.arange(N)
    alive = []
    for k in range(1, 101):
        ids = ids[f(np.full(N, 1.0 / N))]
        if k in (1, 10, 100):
            alive.append(len(np.unique(ids)))
    print(f"{name:12s}: distinct original particles after 1, 10, 100 resamplings: {alive}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

With informative weights, low-variance resampling keeps the number of copies about three times closer to NwNw (RMS deviation 0.35 against 1.00). With equal weights, which happens whenever readings are uninformative (a featureless corridor, a sensor that is off), it is far more striking. Multinomial resampling loses 38% of the distinct particles in one step and 98% after a hundred steps: the cloud collapses onto the descendants of a few lucky ancestors by pure chance, the same random drift that shrinks genetic diversity in small populations. Low-variance resampling with equal weights returns every particle exactly once, so it loses nothing. This is why practical filters use it, and why many also skip resampling when NeffN_{\text{eff}} is high.

ExplanationH

Particle deprivation, kidnapping and adaptive particle counts

A particle filter can only find the robot where it has particles. If, by bad luck or a sudden change, no particle lies near the true pose, resampling only multiplies the wrong ones. This is particle deprivation, and it has two common causes: too few particles for the size of the space (in the first run, only a handful of 5,000 particles started anywhere near the truth), and the kidnapped-robot problem, where the robot is moved without its knowledge: carried by a person, pushed by a pallet jack, or simply mislocalised after a long stretch of bad readings. Kidnapping is the hardest localisation test, because a well-converged filter has, by design, no particles anywhere else.

The standard remedy is to inject random particles when the data say the current cloud fits badly. Augmented MCL keeps two running averages of how well the particles explain the readings, a slow one (wsloww_{\text{slow}}) and a fast one (wfastw_{\text{fast}}), and replaces a fraction max⁡(0, 1−wfast/wslow)\max(0,\ 1 - w_{\text{fast}}/w_{\text{slow}}) of the particles with uniformly random poses. While the fit is steady, the two agree and nothing is injected; when the fit drops suddenly, the fast average falls first and injection begins. The program kidnaps a well-localised robot at step 30, carrying it about 4.5 m and turning it, and compares plain and augmented MCL.

python
import numpy as np

posts = np.array([[2, 2], [8, 2], [2, 8], [8, 8], [9, 5]], dtype=float)
SIZE, RANGE, N = 10.0, 4.0, 2000
sig_r, sig_b = 0.2, np.radians(6)
wrap = lambda a: (a + np.pi) % (2 * np.pi) - np.pi

def move(p, v, w, rng):
    th = p[:, 2] + w + rng.normal(0, 0.02, len(p))
    v = v + rng.normal(0, 0.03, len(p))
    return np.stack([p[:, 0] + v * np.cos(th), p[:, 1] + v * np.sin(th), wrap(th)], axis=1)

def observe(pose, rng):
    d = posts - pose[:2]
    r, b = np.hypot(d[:, 0], d[:, 1]), wrap(np.arctan2(d[:, 1], d[:, 0]) - pose[2])
    s = r < RANGE
    return np.stack([r[s] + rng.normal(0, sig_r, s.sum()), b[s] + rng.normal(0, sig_b, s.sum())], axis=1)

def likelihood(p, z):
    d = posts[None, :, :] - p[:, None, :2]
    r, b = np.hypot(d[..., 0], d[..., 1]), np.arctan2(d[..., 1], d[..., 0]) - p[:, None, 2]
    w = np.ones(len(p))
    for zr, zb in z:
        w *= np.exp(-0.5 * (((zr - r) / sig_r) ** 2 + (wrap(zb - b) / sig_b) ** 2)).mean(axis=1) + 1e-3
    return w * np.where((r < RANGE).sum(axis=1) == len(z), 1.0, 0.1)

def run(augmented, a_slow=0.01, a_fast=0.2, seed=8):
    rng = np.random.default_rng(seed)
    truth = np.array([5.0, 7.5, np.pi])
    p = truth + rng.normal(0, [0.1, 0.1, 0.05], (N, 3))             # the robot starts well localised
    w_slow = w_fast = None
    errors, injected = {}, {}
    for t in range(1, 91):
        truth = move(truth[None], 0.3, 0.12, rng)[0]
        if t == 30:
            truth = np.array([2.5, 5.0, -1.57])     # kidnapped: carried 4.5 m away and turned
        p = move(p, 0.3, 0.12, rng)
        z = observe(truth, rng)
        w = likelihood(p, z)
        fit = w.mean() ** (1 / max(1, len(z)))                        # how well the particles explain each reading
        w_slow = fit if w_slow is None else w_slow + a_slow * (fit - w_slow)   # long-run average fit
        w_fast = fit if w_fast is None else w_fast + a_fast * (fit - w_fast)   # short-run average fit
        w /= w.sum()
        p = p[np.minimum(np.searchsorted(np.cumsum(w), (rng.random() + np.arange(N)) / N), N - 1)]
        n_new = int(N * max(0.0, 1.0 - w_fast / w_slow)) if augmented else 0
        if n_new:                                                     # fit suddenly worse: add random guesses
            p[rng.choice(N, n_new, replace=False)] = np.column_stack(
                [rng.uniform(0, SIZE, n_new), rng.uniform(0, SIZE, n_new), rng.uniform(-np.pi, np.pi, n_new)])
        errors[t] = np.hypot(*(np.median(p[:, :2], axis=0) - truth[:2]))
        injected[t] = n_new
    return errors, injected

steps = (10, 29, 30, 33, 35, 40, 45, 50, 55, 60, 90)
(plain, _), (aug, inj) = run(False), run(True)
print("step              " + " ".join(f"{t:5d}" for t in steps))
print("plain MCL error   " + " ".join(f"{plain[t]:5.2f}" for t in steps) + "  m")
print("augmented error   " + " ".join(f"{aug[t]:5.2f}" for t in steps) + "  m")
print("random injected   " + " ".join(f"{inj[t]:5d}" for t in steps) + "  particles")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Plain MCL never recovers: its particles keep tracking a robot that is no longer there, at an error of 4 to 5 m for the remaining sixty steps. In augmented MCL nothing happens for five steps while the fast average sinks below the slow one; then the filter starts replacing up to about half of its particles with random guesses each step. For a while the guesses settle in the hall's look-alike places (the error swings around 3 m), but by step 55 the cloud has found the true pose and injection stops. The price is visible too: random particles cost accuracy when they are not needed, which is why αslow≪αfast\alpha_{\text{slow}} \ll \alpha_{\text{fast}} and why injection is often switched off when the robot's start pose is known.

How many particles? Global localisation in a large building needs tens of thousands; tracking a localised robot needs a few hundred. KLD-sampling (Fox, 2001 and 2003) chooses NN on the fly. It divides the state space into bins (say 0.5 m by 0.5 m by 10°), counts the number kk of bins the particles occupy, and draws particles until there are enough that, with probability 1−δ1 - \delta, the particle approximation is within ε\varepsilon of the true belief in Kullback–Leibler divergence:

N≈k−12ε(1−29(k−1)+29(k−1) z1−δ)3,N \approx \frac{k - 1}{2\varepsilon}\left(1 - \frac{2}{9(k-1)} + \sqrt{\frac{2}{9(k-1)}}\, z_{1-\delta}\right)^{3},

where z1−δz_{1-\delta} is the standard normal quantile.

ExplanationH

The professional view: AMCL in ROS 2

In ROS 2, localisation against a known 2-D map is usually done by AMCL (adaptive Monte Carlo localisation), part of the Nav2 navigation stack. Its lineage runs through this lesson: it implements MCL with KLD-sampling for the particle count and augmented-MCL injection for recovery, and it descends from the amcl driver of the Player project, ported to ROS and then to ROS 2.

What it does each cycle:

  • Motion model: it reads the robot's odometry (the transform from odom to base_link) and samples each particle's motion from a model with noise parameters alpha1 to alpha5, which say how much rotation and translation errors grow with the distance and angle driven. It updates only after the robot has moved more than update_min_d or turned more than update_min_a, saving computation when parked and avoiding repeated use of the same evidence.
  • Measurement model: the default likelihood field model precomputes, for every map cell, the distance to the nearest obstacle. A laser beam's likelihood is then a Gaussian in the distance from its endpoint to the nearest obstacle (width sigma_hit), mixed with a uniform term for random readings (z_rand). This is smooth, fast and forgiving of small map errors; the older beam model, which ray-casts every beam, is more exact and much slower. Only a subset of beams (max_beams) is used, partly to save time and partly because neighbouring beams' errors are correlated, as the first lesson of this level warned.
  • Output: the estimated pose of base_link in map, published as the correction transform from map to odom, exactly the arrangement of Frames and rigid transforms, together with a covariance computed from the particle cloud.

An excerpt of a configuration file might look like this (shown for reading, not run; check the Nav2 documentation for your release's parameters and defaults):

yaml
# Nav2 AMCL parameters (excerpt; values for illustration)
amcl:
  ros__parameters:
    robot_model_type: "nav2_amcl::DifferentialMotionModel"
    laser_model_type: "likelihood_field"
    min_particles: 500          # KLD-sampling bounds
    max_particles: 2000
    pf_err: 0.05                # epsilon of KLD-sampling
    pf_z: 0.99                  # 1 - delta
    recovery_alpha_slow: 0.001  # augmented MCL: zero disables injection
    recovery_alpha_fast: 0.1
    update_min_d: 0.25          # metres
    update_min_a: 0.2           # radians
    max_beams: 60
    sigma_hit: 0.2

In practice the robot is given an approximate starting pose (from a saved pose, a docking station, or a person clicking on the map in RViz), and global localisation over the whole map is reserved for recovery. The two recovery averages are disabled by default; the ROS documentation suggests values around 0.001 and 0.1 when enabling them. A good diagnostic is the particle cloud itself, visualised in RViz: a tight cloud that suddenly fragments is a robot that has lost its way.

Particle filters reach well beyond 2-D localisation. Rao–Blackwellised particle filters sample the robot's trajectory and solve the map analytically for each particle; FastSLAM and the long-popular GMapping work this way, as SLAM describes. Visual trackers follow people and objects with particles. And research on differentiable particle filters learns the motion and measurement models end to end from data, keeping the algorithm's structure as a prior; Lumenary CS's neural networks lesson covers the learning machinery. In large outdoor spaces, 3-D lidar localisation more often matches scans to a map with registration methods (the ICP of Depth sensing and point clouds) inside a Kalman filter or optimiser, with a particle filter, if any, only to find the starting pose.

Common misconceptionsH

Common misconceptions

Misconception

"The weighted mean of the particles is the robot's position." Only when the belief has one peak. With two clusters, the mean lies between them, possibly inside a wall. Report the mean of the dominant cluster, or the mode, and check how spread the cloud is before trusting either. In the first program the mean was 2.5 to 3.1 m off for the first six steps, while the truth itself held a share of the particles throughout.

Misconception

"More particles always fix a struggling filter." They help with deprivation at the start, but not with a wrong model. If the motion noise is set too small, particles cannot spread enough to follow real slip; if the measurement model is too sharp, a single bad reading wipes out the right particles. Both make the filter fail confidently whatever NN is.

Misconception

"Resampling adds information." It adds none; it only moves computation to where the weights already say the robot probably is, and each resampling throws a little diversity away. That is why systematic resampling and resampling only when NeffN_{\text{eff}} is low are both good practice.

Misconception

"A converged particle filter cannot be wrong." A tight cloud is a confident filter, not a correct one. In a symmetric building, a filter can converge on a look-alike and stay there, and without injection or an outside check it will never notice.

History & global context

A short history

Monte Carlo methods, named after the casino, were developed by Stanisław Ulam, John von Neumann and Nicholas Metropolis in the 1940s for problems in physics. Sequential versions for tracking appeared in scattered forms in the 1960s and 1970s, but the method took off with the 1993 bootstrap filter of Gordon, Salmond and Smith, built for tracking targets in defence research in the United Kingdom, and, independently, with Michael Isard and Andrew Blake's CONDENSATION algorithm (1996) for tracking outlines in video at Oxford. In 1999 Dellaert, Fox, Burgard and Thrun applied it to robot localisation, showing that a museum robot could localise itself globally from a uniform start. KLD-sampling followed in 2001, and Andrew Howard's amcl for the Player robot server packaged these ideas in open-source software that, through ROS, became one of the most widely used localisers in robotics.

Exercises

Exercises

1. Particle filters and localisation

Warm-upHuman

A robot is switched on in one of four identical corridors and has seen only things that all four share. Why is a particle filter a better choice than a Kalman filter for this moment?

Choose one

2. Particle filters and localisation

CoreHuman

A particle filter has 100 particles. After a reading, 20 of them have weight 0.040.04 each and the other 80 have weight 0.00250.0025 each (so the weights sum to 1). What is the effective sample size Neff=1/∑iwi2N_{\text{eff}} = 1/\sum_i w_i^2, to the nearest whole number?

3. Particle filters and localisation

CoreHuman

Four particles, numbered 0 to 3, have weights 0.10.1, 0.450.45, 0.050.05 and 0.40.4. Low-variance resampling draws the random number 0.150.15 in [0,1/4)[0, 1/4), so its four pointers are at 0.150.15, 0.400.40, 0.650.65 and 0.900.90. How many copies of particle 1 does the new set contain?

4. Particle filters and localisation

CoreHuman

A warehouse robot's AMCL is well localised when a worker pushes it 15 m down another aisle while it is switched to manual mode. Afterwards the particle cloud stays tight but in the wrong aisle. Which measures would help it recover? Select all that apply.

Choose all that apply

5. Particle filters and localisation

CoreHuman

To make a particle filter "more precise", a student sets the motion model's noise to zero, so that every particle moves exactly as the odometry says. What happens after a few dozen resampling steps?

Choose one

6. Particle filters and localisation

CoreComputational

Write low_variance_resample(weights, r), which returns an integer array of NN indices chosen by low-variance resampling. weights are NN non-negative numbers that may not be normalised; r is the random offset in [0,1)[0, 1), so the pointers are at (r+k)/N(r + k)/N for k=0,…,N−1k = 0, \dots, N-1. (Taking r as an argument makes the function deterministic and testable; in a filter you would pass rng.random().)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Particle filters and localisation

StretchComputational

Write range_weights(particles, ranges, landmarks, sigma) for a robot that measures its distance to LL landmarks of known identity. particles is an (N,3)(N, 3) array of poses, ranges the LL measured distances, landmarks an (L,2)(L, 2) array and sigma the range noise. Each reading is Gaussian around the true distance, independent of the others given the pose. Return the normalised weights. The last test has 60 landmarks and a precise sensor: multiplying 60 small likelihoods underflows to zero for every particle, so your function must work with log-likelihoods.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources