The Bayes filter

Where am I, given everything I have seen so far?

Every estimation problem in this series has been about a quantity you cannot see directly. Here the quantity is the robot's state: its position along the corridor, a number that changes as the robot drives and that no sensor reports exactly. The robot has two noisy sources of information — how far it tried to drive, and what a sensor observed, such as a door somewhere ahead. Neither alone pins down the position.

The honest answer to "where am I?" is therefore a probability distribution over the corridor, called the belief: your current knowledge given every control command and measurement so far. Because data arrive one at a time, the belief is updated one step at a time — take the belief you had a moment ago, account for the motion, then account for the new measurement. That is the whole idea, and it repeats forever.

What makes the recursion worth a part of its own is that it is general. Whether the state is a robot in a corridor, an aircraft in the sky, or a parameter being tracked as data stream, the same three ingredients appear: a prior belief, a motion model, and a measurement model. Only the way you store the belief changes, and this part deliberately uses the crudest storage — a histogram — so that nothing is hidden behind algebra. Later parts swap in smarter storage.

Prior, predict, update — the same three lines forever

Write $x_t$ for the state at time $t$ and $z_t$ for the measurement. The belief is the conditional density $bel(x_t) = p(x_t \mid z_{1:t}, u_{1:t})$, a distribution over where the robot could be. The filter computes it recursively, because holding the whole history explicitly would grow without bound — and it gets away with that thanks to one assumption.

The Markov assumption says the present state is a sufficient summary of the past: once you know where the robot is now, earlier positions add nothing, and the last measurement depends on the state and nothing older. Written out, $p(x_t \mid x_{t-1}, \dots) = p(x_t \mid x_{t-1})$ and $p(z_t \mid x_t, \dots) = p(z_t \mid x_t)$. The first factor is the motion model, the second the measurement model. With those two assumptions the history collapses to a two-line loop.

The first line is predict, also called the control update. The robot applies a control $u_t$ and moves. Because the motion is uncertain, the belief spreads: the new prediction is the old belief convolved with the motion model,

For a robot driving forward this is a shift and a blur. Mass that was at one position is carried forward and smeared over the distance the robot might have travelled. In a histogram the integral becomes a sum, and the convolution is a loop over bins: each bin's mass is redistributed to its neighbours, shifted forward. Prediction never adds information; uncertainty goes up.

The second line is update, also called the measurement update. A measurement $z_t$ arrives and is compared against what each candidate state would have predicted. Bayes' rule multiplies the prediction by the likelihood at each position and normalises,

The constant $\eta$ is just the normaliser that makes the result a distribution again. This step multiplies whatever the sensor's model says is plausible, and it is where information enters: positions that explain the measurement keep their mass or gain it, positions that cannot explain it are multiplied down. Uncertainty goes down. Bayesian inference is not a special technique here; it is what happens when you keep applying Bayes' rule one observation at a time. The order matches the events: predict because the robot moved, update because a sensor fired. Skip the predict and the belief never follows the robot; skip the update and it only ever spreads.

The histogram filter, one metre at a time

The robot below drives down a corridor twelve metres long with five doors. The doors carry colour codes — three blue, one red, one green — and the sensor reports which colour it sees, not how far away it is. The belief is a histogram: the corridor is cut into $121$ narrow bins, each holding the probability that the robot is in that slice. At the start nothing is known, so the histogram is flat: a uniform prior over the whole corridor. This is global localisation, the hard case where the robot has no idea where it is.

Press Move +1 m and the robot takes one step. Its true position advances only approximately — the wheels slip, so the step is one metre plus a random error the filter does not know. It therefore predicts by shifting the histogram one metre forward and blurring it by an amount set by the process noise slider. A wide slider smears the belief badly; a narrow one keeps it crisp but overconfident. Entropy climbs on every move: prediction is lossy by construction.

Now press See door. The sensor reports a colour, and the filter builds a likelihood that is a sharp Gaussian around every door carrying that colour, multiplies the belief by it, and renormalises. Because the blue doors are spread along the corridor, seeing blue produces three separate peaks: the measurement rules out the stretches between doors but cannot tell which blue door is in front of the robot. The belief snaps to a set of spikes. Seeing the single red or green door is far more decisive. This is the honest behaviour of global localisation — a sensor that distinguishes only a few door types leaves real ambiguity, and a correct filter represents it rather than pretending to one answer.

Watch the two markers on the upper canvas. The mean is the probability-weighted average position and the MAP is the most likely bin. After a decisive measurement they agree. After a blue-door measurement they can disagree sharply: the mean averages across three spikes and may land in an empty stretch where the robot certainly is not, while the MAP picks one spike. A mean is only meaningful for a belief with one hill; for a multimodal belief it can be actively misleading, and the filter should report the distribution rather than a point.

Try a sequence: Reset, then Move 10 steps, and watch the flat prior smear into an even flatter, edge-heavy belief. Now press See door twice: the first sighting collapses the belief onto the doors of one colour, the second reinforces whichever of those the robot is actually near and the spikes sharpen. The filter has localised from a uniform prior using nothing but blur and multiply.

Histograms, particles, and the single Gaussian

The recursion never changes; only the way you store $bel(x_t)$ does. The histogram is the most literal storage: a grid of bins, each holding a probability. Its virtue is that it assumes nothing about the shape of the belief — flat, spiked, skewed, or a row of separate hills, exactly what global localisation produces. Multimodal beliefs are represented without apology.

The price is resolution and cost. A histogram with $n$ bins has a fixed precision of one bin width, and the predict convolution naively touches every pair of bins, which is $O(n^2)$ work; it can be reduced to $O(n)$ with a compact kernel, but the number of bins multiplies with each new state variable, so the cost of good resolution grows steeply in higher dimensions. That curse of dimensionality is why a fixed grid is rarely the end of the story.

The particle filter replaces the grid with a cloud of weighted samples that move to wherever the belief has mass, concentrating effort on the likely regions. It keeps the freedom to be multimodal and scales to many dimensions, at the risk of particle deprivation when the cloud loses a hypothesis. It is the subject of a later part of this series.

The Kalman filter makes the opposite bet: the belief is always a single Gaussian, described completely by a mean and a covariance. Predicting a Gaussian through a linear motion model gives another Gaussian, and multiplying two Gaussians gives a third — the Gaussian fusion from earlier in the series, now run as a loop in time. The whole filter reduces to updating an ellipse: cheap and exact for linear-Gaussian systems, but unable to represent two hypotheses at once. A Kalman filter started from a uniform prior cannot do global localisation, because it has no way to say "either here or there." That is the representation trade in one sentence: histograms and particles can be wrong-shaped and expensive, Gaussians are cheap and forced to be single-hilled.

Two threads from earlier run underneath. The normaliser $\eta$ is a marginal likelihood, the probability that the sensor would have produced this reading under the current belief; when the numbers get small, working in logs keeps the arithmetic from underflowing, which is why numerical care matters even here. And the shift-and-blur picture is precisely a convolution, the same object that made the central limit theorem tangible. The machinery is not new; it is the same statistics, one time step at a time.

One recursion, many robots

The pattern repeats wherever a hidden state evolves and noisy observations arrive. A vision pipeline tracking a calibration parameter across frames runs a Bayes filter with one state variable; a recommender revising a user's taste as clicks arrive predicts and updates the same way. Whenever the object you care about changes over time and you see it only through noise, this recursion is the thing to reach for.

Further reading

The references below treat the Bayes filter as the unifying recursion rather than a collection of algorithms, which is the order that makes the two-step loop memorable. If you take away one thing, take away the picture of a belief that blurs when it moves and multiplies when it sees.

Thrun, Burgard and Fox derive the general filter and then the histogram, Kalman and particle versions from it in sequence — exactly the arc this part begins. Murphy's chapter is the cleanest probabilistic treatment for a reader who wants the graphical-model view, and Stachniss's lectures make the same material concrete on a board.

• Sebastian Thrun, Wolfram Burgard and Dieter Fox, Probabilistic Robotics, chapter 2 — the recursive Bayes filter and the histogram filter worked in one dimension.
• Kevin Murphy, Probabilistic Machine Learning: Advanced Topics, chapter on state-space models — the filter as inference in a hidden Markov model.
• Cyrill Stachniss, "Probabilistic Robotics" lecture series — the corridor-with-doors example used here, developed on a board.
• 3Blue1Brown, probability and Bayes series — the visual style behind the histogram smoother.

Cheat sheet