M8-T4 — When Gaussian Filters Fail

Learning objectives

After this lesson, you should be able to:

• Recognise problems in which the belief is multimodal, and explain why a single Gaussian summary is misleading there.
• Explain the kidnapped-robot problem and why a filter that is certain cannot recover.
• List the failure modes of Gaussian filters: ambiguity, linearisation, wrong association, overconfidence.
• Choose between a Gaussian filter, a grid and particles for a given localisation problem.

The intuition

The robot is in a corridor with three identical doors, 5 to 6 m apart. It does not know where it is. Its door detector is 90% reliable and gives a false alarm 10% of the time. It drives forward 25 cm per step. What should it believe?

At first, nothing helps: the belief is spread over the corridor. After the first door reading, the belief is a set of three peaks, one for each door the robot might be standing at (and later, one for each door it might have passed); the readings that follow keep the three alive until a door appears where the pattern of the doors rules two of them out (the gap to the next door is 5 m for the first and 6 m for the second). Only then does it become a single narrow peak.

Compare the two curves in the first panels. The Gaussian that summarises the belief has a mean of about 10 m, in the middle of the corridor, and a standard deviation of 4.5 m. At step 1 it is a broad hump that says nothing. At step 16 its centre sits on the middle of the three peaks, 5 m from the true position, and its width of 4.5 m is neither the width of one peak nor a statement that there are three. If the robot asked “how much probability do you put within 1 m of where I really am?”, the histogram says 0.33 at step 16, and a Gaussian of the same mean and spread says 0.09. At step 32 two peaks are left with 93% of the mass in the right one: the Gaussian says 0.48.

A Kalman filter would not even start: it needs an initial Gaussian, and any Gaussian placed in the corridor would have most of its mass at the wrong place. Once it is placed, it can only move and narrow that single hump, never split it. If the prior is wrong the filter converges to a wrong, confident answer.

A Gaussian belief says: I am in one place, and here is how sure I am. When the truth is “in one of several places”, the mean is meaningless and the covariance is misleading. The Gaussian filters then need help from a different representation.

Definitions

Multimodal belief

A belief with several separate peaks, each holding a significant fraction of the probability.

Perceptual aliasing

Different places that give the same sensor readings (identical doors, similar corridors, repeated shelves), which is what creates multimodal beliefs.

Global localisation

Finding the pose with no prior: the initial belief is spread over the map.

Kidnapped robot

The robot is moved without being told (picked up, wheel slippage, a fall) so its belief is wrong and, if concentrated, gives the truth almost no probability.

Belief floor

A small probability $\varepsilon$ mixed into the belief at every step, $\mathrm{bel}\leftarrow(1-\varepsilon)\,\mathrm{bel}+\varepsilon/N$, so that no place ever has zero probability.

Derivation: why the summary fails and why certainty cannot recover

The moment-matched Gaussian of a mixture

The Gaussian with the mean and variance of a mixture is the best single-Gaussian summary in the sense of minimising the Kullback–Leibler divergence $\mathrm{KL}(p\,\|\,q)$ over Gaussians $q$. For two equal peaks at $\pm a$ with standard deviation $s$:

1. $$\mu = 0,\qquad \sigma^2 = s^2 + a^2$$

   The mean of the mixture is the midpoint; its variance adds the squared separation to the variance of each peak (the law of total variance, module 4).

2. $$q(\pm a) = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-a^2/2(s^2+a^2)}\quad\text{vs.}\quad q(0)=\frac{1}{\sqrt{2\pi\sigma^2}}$$

   The summary is tallest at the midpoint, where the true belief has the least mass (for $a\gg s$ practically none). It is lowest in density near the true peaks.

3. $$\text{mass of } q \text{ within } \pm s \text{ of a peak} \approx 2s\,q(a) \ll \tfrac12$$

   Each real peak holds half the probability; the Gaussian gives it a fraction. It is under-confident about each hypothesis and over-confident about the empty middle.

A certain filter cannot recover

By Bayes' rule the posterior is proportional to the prior times the likelihood. If the prior probability of a place is zero, so is its posterior, whatever the sensors say.

1. $$\mathrm{bel}_t(x)\propto p(z_t\mid x)\sum_{x^\prime} p(x\mid x^\prime,u_t)\,\mathrm{bel}_{t-1}(x^\prime)$$

   The Bayes filter. If the robot is moved to $x_k$ and the belief near $x_k$ is $\delta$, then the posterior there is at most $\delta$ times the best likelihood ratio.

2. $$\mathrm{bel}_t(x_k)\le\delta\,\Lambda^t$$

   With $\Lambda$ the maximum likelihood ratio per step (for the door sensor 0.9/0.1 = 9). The belief at the true place grows by at most that factor per step and must climb out of $\delta$; if $\delta = 0$ (or underflows) it stays at 0.

3. $$\mathrm{bel}(x_k)\ge\varepsilon/N;\Rightarrow;\text{recovery in } O\bigl(\log(N/\varepsilon)/\log\Lambda\bigr)\text{ informative steps}$$

   With a floor the belief at the true place starts at $\varepsilon/N$, and each informative reading multiplies it by up to $\Lambda$. The floor sets how quickly the filter recovers, and how much confidence it gives up all the time.

A filter must keep a little probability everywhere it could possibly be. Certainty is a bet that the model is right, and the filter cannot detect that it lost it.

A worked example

Two programs on the corridor of the figure (20 m, 80 cells of 25 cm, doors at 3, 8 and 14 m, the robot starting at 1 m).

1. Ambiguity. At step 1 the belief has four modes (the first reading says nothing). At step 8 the robot is at the first door and the belief has three modes with 33% of the mass within 1 m of the truth. At step 24 the robot is at the second door and the belief still has three modes, 43% on the right one. By step 32 two modes remain (93%), and from step 60 one (100%).
2. The Gaussian summary. At step 16 its mean is 10.3 m (the robot is at 5.0 m) and its standard deviation 4.5 m; it puts 0.09 of the mass within 1 m of the truth against 0.33 in the histogram. At step 32 it says 0.48 against 0.93. The summary only becomes adequate when the belief has collapsed to one mode (step 60: 1.0 and 1.0).
3. Kidnapping. After step 40 the robot is carried 7 m back down the corridor. Before, the histogram puts 0.84 of the mass within 1 m. Without a floor the mass at the true position drops to 0 and never returns in 40 more steps. With a floor of 2% it climbs back: 0.14 at step 61, 0.70 at step 80.

import math
from robotprob import Rng, hist_predict, hist_update, normalize, gaussian_pdf

# a 20 m corridor with three identical doors; the robot knows the map but not where it is
N, CELL = 80, 0.25
DOORS = [3.0, 8.0, 14.0]
cell_x = [(i + 0.5) * CELL for i in range(N)]
near_door = [any(abs(x - d) < 0.6 for d in DOORS) for x in cell_x]
P_HIT, P_FALSE = 0.9, 0.1                      # P(says door | at a door), P(says door | not at a door)
kernel = {0: 0.1, 1: 0.8, 2: 0.1}               # the robot moves about 1 cell = 0.25 m per step

def likelihood(says_door):
    return [(P_HIT if nd else P_FALSE) if says_door else ((1 - P_HIT) if nd else (1 - P_FALSE)) for nd in near_door]

def modes(b, thr=0.05):                        # separate peaks that hold more than 5% of the probability
    out, cur = [], 0.0
    for i in range(N):
        if b[i] > 0.002:
            cur += b[i]
        else:
            if cur > thr: out.append(cur)
            cur = 0.0
    if cur > thr: out.append(cur)
    return out

def moments(b):
    mu = sum(bi * x for bi, x in zip(b, cell_x))
    return mu, math.sqrt(sum(bi * (x - mu) ** 2 for bi, x in zip(b, cell_x)))

rng = Rng(5)
x = 1.0
b = [1.0 / N] * N
print('step  robot x  door?  modes  mass within 1 m  belief mean  belief std  mass within 1 m if a Gaussian')
for t in range(1, 61):
    x += 0.25 + rng.gauss(0.0, 0.03)
    at_door = any(abs(x - d) < 0.6 for d in DOORS)
    says = rng.random() < (P_HIT if at_door else P_FALSE)
    b = hist_predict(b, kernel)
    b = hist_update(b, likelihood(says))
    if t in (1, 8, 16, 24, 32, 40, 50, 60):
        mu, sd = moments(b)
        ms = modes(b)
        near = sum(bi for bi, xc in zip(b, cell_x) if abs(xc - x) < 1.0)
        # a single Gaussian with the same mean and std puts this much mass within 1 m of the truth
        g = sum(gaussian_pdf(xc, mu, sd) * CELL for xc in cell_x if abs(xc - x) < 1.0)
        print(str(t).rjust(4), str(round(x, 2)).rjust(8), str('yes' if says else 'no').rjust(6), str(len(ms)).rjust(6), str(round(near, 2)).rjust(18), str(round(mu, 2)).rjust(12), str(round(sd, 2)).rjust(11), str(round(g, 2)).rjust(14))

# kidnapping: at step 41 the robot is carried 7 m back down the corridor. Does the filter recover?
def kidnapped(floor):
    rng = Rng(9)
    x = 1.0
    b = [1.0 / N] * N
    out = []
    for t in range(1, 81):
        if t == 41: x -= 7.0
        x += 0.25 + rng.gauss(0.0, 0.03)
        at_door = any(abs(x - d) < 0.6 for d in DOORS)
        says = rng.random() < (P_HIT if at_door else P_FALSE)
        b = hist_predict(b, kernel)
        b = hist_update(b, likelihood(says))
        if floor > 0:
            b = normalize([bi + floor / N for bi in b])
        out.append(sum(bi for bi, xc in zip(b, cell_x) if abs(xc - x) < 1.0))
    return out
print('mass within 1 m of the truth at steps 40, 42, 51, 61, 71, 80 (kidnapped after step 40):')
for floor in (0.0, 0.02):
    o = kidnapped(floor)
    print(' floor', floor, [round(o[i], 2) for i in (39, 41, 50, 60, 70, 79)])

step  robot x  door?  modes  mass within 1 m  belief mean  belief std  mass within 1 m if a Gaussian
   1     1.27     no      4               0.11        10.54        5.88           0.04
   8     2.97    yes      3               0.33         8.55        4.57           0.08
  16     5.04     no      3               0.33        10.29        4.51           0.09
  24      7.0    yes      3               0.43        11.58        4.48           0.11
  32     9.05     no      2               0.93         9.35         1.5           0.48
  40    11.04     no      2               0.93        11.34        1.53           0.48
  50    13.59    yes      1               0.96         13.7        1.02           0.66
  60     16.1     no      1                1.0        16.15        0.31            1.0
mass within 1 m of the truth at steps 40, 42, 51, 61, 71, 80 (kidnapped after step 40):
 floor 0.0 [0.84, 0.0, 0.0, 0.0, 0.0, 0.0]
 floor 0.02 [0.63, 0.01, 0.04, 0.14, 0.15, 0.7]

In robotics

Which filter for which problem

Multi-hypothesis and hybrid filters

A bank of Kalman filters, one per hypothesis, weighted by their likelihoods, represents a mixture at a low cost when the number of modes is small and the modes are well separated. Hybrid schemes use a particle filter to find the pose and a Kalman filter to track it once it is certain. The Navigation course shows Monte Carlo localisation, the standard answer, in its localisation lessons.

Detecting that the filter has failed

• The NIS or the fraction of rejected measurements rises persistently (module 7).
• The belief is confident but readings repeatedly disagree with it.
• For a particle filter: the average likelihood of the measurements falls (the next module uses this to inject random particles).

Linearisation failures are a form of the same problem

The banana of the last lessons is a mild case of a belief that is not Gaussian: one hump, but curved. The remedies run from inflating Q and re-linearising to particle filters, in the same order as the severity.

Common misconceptions

Key takeaways

1. A Gaussian belief is one hump. Identical doors, symmetric corridors and global localisation give several; the moment-matched Gaussian is then a single broad hump whose centre can sit on a wrong hypothesis or between them.
2. The histogram filter represents any shape: with three identical doors it holds three modes until the geometry rules two out (33% of the mass on the true place at step 16, 93% at step 32).
3. A belief of zero cannot be revived by Bayes’ rule: without a floor the kidnapped robot never recovers, with a 2% floor it does.
4. Choose by the problem: Gaussian filters for tracking from a good start, grids or particles for global localisation, aliasing and kidnapping, hybrids for the best of both.
5. Watch for the signs of failure: rising NIS, rejected readings, disagreement between a confident belief and the sensors.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, chapter 7 (mobile robot localisation: Markov and Gaussian, including the global and kidnapped problems) and section 8.3. Paid book.
• C. Stachniss, “Particle Filter and Monte Carlo Localization” (video lecture) , motivates particles by these failures. Free to watch.
• T. D. Barfoot, State Estimation for Robotics, 2nd edition, 2024 , chapter 4 discusses the limits of Gaussian approximations. Free to read as the author’s PDF; the book is copyrighted.
• D. Fox, W. Burgard, F. Dellaert and S. Thrun, “Monte Carlo Localization: Efficient Position Estimation for Mobile Robots”, AAAI 1999. Paid or institutional access; free copies are posted by the authors in some places, which was not checked here.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

This closes the Gaussian filters. Module 9 develops the answer to the failures seen here: represent the belief by a set of weighted samples, the particle filter, and use it for Monte Carlo localisation.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T3: The Unscented Transform and the UKF

  Choose sigma points and weights, propagate them through a nonlinear function, and assemble the unscented Kalman filter.

Other courses on this site treat neighbouring topics from their own angle:

• UAV M3-T5: Extended Kalman Filter
• SLAM M3-T7: EKF-SLAM
• SLAM M3-L5: Implement a Simplified EKF-SLAM