M6-T1 — The Bayes Filter

Learning objectives

After this lesson, you should be able to:

• Write the belief, the predicted belief, and the two steps of the Bayes filter, and say what each means physically.
• Derive the prediction and correction steps from the Markov assumption, the law of total probability and Bayes’ rule.
• Run the filter by hand on a small discrete world, and explain why prediction increases uncertainty and correction decreases it.
• Explain why the filter as written cannot be computed exactly in general, and what the practical filters approximate.

The intuition

Rover is in a corridor loop of five cells. Cells 1 and 4 have doors, the others are plain wall. It does not know where it is, so its belief is flat: 0.2 for each cell. Two things happen in turn, forever.

• It senses. The door detector fires. That evidence favours the two door cells (it fires with probability 0.8 at a door and 0.1 at a wall), and the belief becomes two peaks at 0.42 each. This is Bayes' rule, the correction step, and the belief becomes sharper: its entropy (a measure of how undecided it is) falls from 2.32 bits to 1.72.
• It moves. Rover commands one cell forward. It usually makes it (80%), sometimes stays (10%) or overshoots by two (10%). Every peak of the belief shifts one cell and also smears a little. This is the law of total probability, the prediction step, and the belief becomes broader: the entropy rises, to 2.06 bits.

After a door, a move, a wall, a move and another door, the belief has settled on cell 1 (63%): only one of the two possible starting doors is consistent with “door, then two cells of wall-and-door pattern, then a door”. But 24% is still on cell 4, the wrong candidate. A few more steps would settle it. Notice what the robot never had to do: it never stored the readings. Everything it has learned is in the five numbers, and each step updates them from the previous five numbers, the new command and the new reading.

The sawtooth

The entropy in the figure goes down at every sensing step and up at every motion step. A working filter always shows this pattern. Sensing brings in information and sharpens the belief; moving costs information because the motion is noisy. A robot localizes well only if sensing wins on average, and the whole business of choosing a sensor and a motion model is a negotiation between the two. If the robot stops sensing, the belief spreads until it is flat again, and if it stops moving, it keeps sharpening until the evidence is exhausted.

The Bayes filter is a loop of two steps. Predict: spread the belief with the motion model. Correct: multiply by the likelihood of the measurement and renormalize. Uncertainty rises in the first and falls in the second.

Definitions

Belief $\mathrm{bel}(x_t)$

The probability of each state after all the data up to and including time $t$: $p(x_t \mid z_{1:t},\, u_{1:t})$.

Predicted belief $\overline{\mathrm{bel}}(x_t)$

The probability of each state after the control $u_t$ but before the measurement $z_t$: $p(x_t \mid z_{1:t-1},\, u_{1:t})$. Also called the prior of the correction step.

Prediction (time update)

Moving the belief forward with the motion model.

Correction (measurement update)

Conditioning the predicted belief on the measurement with Bayes’ rule.

Entropy $H = -\sum_x p(x)\log_2 p(x)$

A number in bits for how undecided a belief is: 0 when the state is certain, $\log_2 n$ when all $n$ states are equally likely.

Derivation: the two steps from first principles

The derivation uses nothing but the Markov assumptions of the last module and the two rules of the third.

Correction

1. $$\mathrm{bel}(x_t) = p(x_t \mid z_{1:t}, u_{1:t}) = \dfrac{p(z_t \mid x_t, z_{1:t-1}, u_{1:t})\; p(x_t \mid z_{1:t-1}, u_{1:t})}{p(z_t \mid z_{1:t-1}, u_{1:t})}$$

   Bayes’ rule (the Bayes lesson) with the earlier data $z_{1:t-1}, u_{1:t}$ carried along as background knowledge.

2. $$p(z_t \mid x_t, z_{1:t-1}, u_{1:t}) = p(z_t \mid x_t)$$

   Markov assumption for the measurement. Given the current state, the reading depends on nothing else.

3. $$\mathrm{bel}(x_t) = \eta\; p(z_t \mid x_t)\; \overline{\mathrm{bel}}(x_t), \qquad \overline{\mathrm{bel}}(x_t) = p(x_t \mid z_{1:t-1}, u_{1:t})$$

   The denominator does not depend on $x_t$ and is absorbed into $\eta$. The remaining factor is the predicted belief.

Prediction

1. $$\overline{\mathrm{bel}}(x_t) = \int p(x_t \mid x_{t-1}, z_{1:t-1}, u_{1:t})\; p(x_{t-1} \mid z_{1:t-1}, u_{1:t})\;dx_{t-1}$$

   The law of total probability (the joint-probability lesson), summing over the previous state, all conditioned on the earlier data.

2. $$p(x_t \mid x_{t-1}, z_{1:t-1}, u_{1:t}) = p(x_t \mid x_{t-1}, u_t)$$

   Markov assumption for the motion. Given the previous state and the current control, the earlier readings and controls add nothing.

3. $$p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) = p(x_{t-1} \mid z_{1:t-1}, u_{1:t-1}) = \mathrm{bel}(x_{t-1})$$

   The current control $u_t$ is chosen after $x_{t-1}$ and cannot tell us anything about it, so it can be dropped. What remains is the previous belief.

4. $$\overline{\mathrm{bel}}(x_t) = \int p(x_t \mid x_{t-1}, u_t)\;\mathrm{bel}(x_{t-1})\;dx_{t-1}$$

   Substitute. The prediction needs only the motion model and the previous belief.

Why the uncertainty breathes

Prediction is a mixture of shifted copies of the belief, which can only spread it: the entropy after a noisy motion is at least that before (for a motion model that does not depend on the state, it is exactly a convolution). Correction multiplies by a likelihood, which reweights the cells and, on average, concentrates the belief: the expected entropy after a reading is no larger than before it. A single surprising reading can nevertheless raise it, for example when a measurement contradicts a confident belief and splits it between hypotheses.

What cannot be computed

For a general motion model the integral has no closed form, and for a continuous state it cannot be stored. The filter above is therefore a specification. Every practical filter replaces the belief and the two steps with something computable, and is named by what it assumes.

Every filter in this course computes the same two lines, prediction by total probability and correction by Bayes’ rule, with the belief stored in a different form.

A worked example

The five-cell corridor of the figure: doors at cells 1 and 4. The door detector says “door” with probability 0.8 at a door and 0.1 at a wall, and “wall” with probability 0.2 at a door and 0.9 at a wall. A move command shifts the robot one cell with probability 0.8, leaves it in place with 0.1, and moves it two cells with 0.1 (the corridor is a loop).

1. Start. The belief is flat: (0.2, 0.2, 0.2, 0.2, 0.2), entropy $\log_2 5 = 2.32$ bits.
2. Door detected. Likelihoods (0.1, 0.8, 0.1, 0.1, 0.8); products 0.02, 0.16, 0.02, 0.02, 0.16; sum (the evidence) 0.38. Posterior (0.053, 0.421, 0.053, 0.053, 0.421), 1.72 bits.
3. Move one cell. The belief of each cell is sent to the cell one ahead with weight 0.8, to the same cell with 0.1 and two ahead with 0.1: (0.347, 0.126, 0.347, 0.089, 0.089), 2.06 bits. The two peaks have moved from cells 1 and 4 to 2 and 0, and have lost height.
4. Wall detected. Cells 0 and 2 are walls and are favoured: (0.417, 0.034, 0.417, 0.108, 0.024), 1.69 bits. Both candidates survive, because both predict a wall.
5. Move, then door. After the second move: (0.072, 0.340, 0.110, 0.348, 0.130). The door detector now favours cells 1 and 4: (0.017, 0.634, 0.026, 0.081, 0.243), 1.44 bits. The robot, which is in fact at cell 1, has a 63% belief there. The wrong candidate (cell 4) keeps 24%.
6. Check one prediction by hand. From (0.5, 0.5, 0, 0, 0): cell 0 sends 0.4 to cell 1, 0.05 to cell 0 and 0.05 to cell 2; cell 1 sends 0.4 to cell 2, 0.05 to cell 1 and 0.05 to cell 3. Totals: (0.05, 0.45, 0.45, 0.05, 0), exactly what the program gives.
7. Two limits. If the robot only predicts, any belief spreads until it is flat: after 40 moves from a certain start, (0.201, 0.200, 0.199, 0.199, 0.200). Without sensing there is no way to hold on to what was known.

from robotprob import hist_predict, hist_update, entropy

world = ['wall', 'door', 'wall', 'wall', 'door']
kernel = {1: 0.8, 0: 0.1, 2: 0.1}               # move one cell: usually, stay, or overshoot

def likelihood(z):                               # the measurement model for each cell
    if z == 'door':
        return [0.8 if c == 'door' else 0.1 for c in world]
    return [0.2 if c == 'door' else 0.9 for c in world]

bel = [0.2] * 5
def show(label):
    print(label.ljust(20), [round(b, 3) for b in bel], ' entropy', round(entropy(bel), 2), 'bits')
show('start (no idea)')
bel = hist_update(bel, likelihood('door')); show('sees a door')                     # correction
bel = hist_predict(bel, kernel, cyclic=True); show('moves one cell')                # prediction
bel = hist_update(bel, likelihood('wall')); show('sees a wall')
bel = hist_predict(bel, kernel, cyclic=True); show('moves one cell')
bel = hist_update(bel, likelihood('door')); show('sees a door')

print('hand check of one prediction:', [round(b, 3) for b in hist_predict([0.5, 0.5, 0, 0, 0], kernel, cyclic=True)])
b = hist_update(hist_predict([0.5, 0.5, 0, 0, 0], kernel, cyclic=True), likelihood('door'))
print('then a door:', [round(v, 3) for v in b])

bel = [1.0, 0.0, 0.0, 0.0, 0.0]                  # predicting forever, without any sensing
for _ in range(40):
    bel = hist_predict(bel, kernel, cyclic=True)
print('predict only, from a certain start, 40 steps:', [round(v, 3) for v in bel], round(entropy(bel), 2), 'bits')

start (no idea)      [0.2, 0.2, 0.2, 0.2, 0.2]  entropy 2.32 bits
sees a door          [0.053, 0.421, 0.053, 0.053, 0.421]  entropy 1.72 bits
moves one cell       [0.347, 0.126, 0.347, 0.089, 0.089]  entropy 2.06 bits
sees a wall          [0.417, 0.034, 0.417, 0.108, 0.024]  entropy 1.69 bits
moves one cell       [0.072, 0.34, 0.11, 0.348, 0.13]  entropy 2.07 bits
sees a door          [0.017, 0.634, 0.026, 0.081, 0.243]  entropy 1.44 bits
hand check of one prediction: [0.05, 0.45, 0.45, 0.05, 0.0]
then a door: [0.012, 0.867, 0.108, 0.012, 0.0]
predict only, from a certain start, 40 steps: [0.201, 0.2, 0.199, 0.199, 0.2] 2.32 bits

In robotics

Every localizer is this loop

A robot's localization software runs the loop at the rate of its sensors: predict when new odometry arrives, correct when a scan or a landmark does. What differs is how the belief is stored. A grid localizer holds a table (next lesson), a Kalman or extended Kalman filter a mean and covariance (modules 7 and 8), a Monte Carlo localizer a few thousand particles (module 9). If you can write down the motion model and the measurement model, you can build any of them. The SLAM course introduces the same loop in Bayesian Estimation and Filtering-Based SLAM.

Asynchronous sensors

Real sensors do not arrive in lockstep. A filter predicts to the timestamp of each new measurement and then corrects, even if the sensor rate is irregular, and a late measurement is handled by predicting to its time and correcting there, or by re-running recent history. The prediction step is therefore a function of the time gap: the longer the gap, the more the belief spreads.

Several sensors, one filter

Each sensor contributes its own correction step with its own measurement model. Because the corrections multiply the belief by independent likelihoods, the order does not matter (the recursive-updating lesson), and a sensor that fails simply skips its step. This makes the filter a natural framework for fusing odometry, a lidar, a compass and a GNSS receiver.

Uncertainty as a health signal

Because the filter's own uncertainty rises during motion and falls during sensing, a belief whose entropy only ever grows is a sign that the sensors are no longer informative (a featureless corridor, a blocked camera, a failed lidar). A belief whose entropy is suspiciously small after a large surprise is a sign of overconfidence (module 7). Monitoring the belief is monitoring the robot.

Where the exact filter is feasible

When the state takes a handful of values, as in a five-cell corridor, in a map of rooms, or in discrete fault modes of a machine (“sensor OK”, “sensor stuck”), the Bayes filter can be computed exactly. Many practical systems use this: a hidden Markov model is exactly this filter on a discrete state.

Common misconceptions

Key takeaways

1. The Bayes filter alternates two steps: prediction, bel̄(xₜ) = ∫ p(xₜ | xₜ₋₁, uₜ) bel(xₜ₋₁) dxₜ₋₁, and correction, bel(xₜ) = η p(zₜ | xₜ) bel̄(xₜ).
2. Prediction is the law of total probability and spreads the belief (raises entropy). Correction is Bayes’ rule and sharpens it (lowers entropy on average).
3. Both steps follow from the Markov assumptions: the measurement depends only on the current state, the motion on the previous state and the control.
4. The belief is the only memory: the filter has constant cost per step however long it runs. Without sensing the belief goes flat; without motion it converges on the evidence.
5. The filter is exact only for small discrete states. Kalman, extended Kalman, grid and particle filters are different ways of storing the belief and approximating the two steps.

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, section 2.4 (Bayes filters), including the mathematical derivation of section 2.4.3. Paid book.
• C. Stachniss, “Bayes Filter” (video lecture) . Free to watch.
• S. Särkkä and L. Svensson, Bayesian Filtering and Smoothing, 2nd edition, Cambridge University Press, 2023 , chapter 6 (Bayesian filtering equations and exact solutions). Free to read for personal use; no redistribution or derivative works.
• T. D. Barfoot, State Estimation for Robotics, 2nd edition, Cambridge University Press, 2024 , chapter “Nonlinear Non-Gaussian Estimation” (the Bayes filter). Free to read as the author’s PDF; the book is copyrighted.
• S. Thrun, Artificial Intelligence for Robotics (Udacity CS373) , the first lessons build exactly this filter in Python. Free course.

Knowledge check

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

What’s next

The five-cell filter was small enough to do by hand. The next lesson scales the same filter to a real corridor with a hundred cells, and learns when a grid is the right choice and when it is not.

Related content

Nothing below is required to finish this lesson.

• Lab
  M6-L1: Histogram Localization

  Rover is switched on somewhere in a corridor with three identical doors. Implement the predict and update steps and watch three hypotheses collapse into one.

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

• SLAM M2-T5: Bayesian Estimation
• Robot Foundations 05: Where Am I?