Skip to the lesson
FixTheRobot Explore Robotics / Localization & SLAM / M2 Mathematical Foundations / M2-T5

Localization & SLAM · Theory · M2

M2-T5 — Bayesian Estimation

Every filter in SLAM is the same two steps: predict with motion, correct with measurement.

  • Lesson 5 of 7
  • Module 2: Mathematical Foundations
  • Theory
  • About 8 minutes to read

Bayes’ rule says how to change your mind when evidence arrives. Applied repeatedly to a moving robot it becomes the Bayes filter: a recursion with a prediction step that uses the motion model and a correction step that uses the measurement model. EKF, particle filters and histogram filters are all special cases. Get this lesson right and the rest of the track is bookkeeping.

Learning objectives

After this lesson, you should be able to:

  • State Bayes’ rule and name the prior, likelihood and posterior in a robotics setting.
  • Write the recursive Bayes filter and explain the prediction and correction steps.
  • Run a discrete Bayes filter by hand on a small corridor example.
  • Name the Markov and independence assumptions that make the recursion possible.

The intuition

You are in a corridor with a few identical doors and you do not know where. You see a door. That tells you something: you are probably next to one of the doors, probably not next to a wall. Then you walk a few steps, and your belief must move with you, and also get a little blurrier because your steps are not exact. Then you see a blank wall, and the belief sharpens again. That is the whole algorithm: blur while moving, sharpen while sensing.

Belief = what the robot thinks, as a probability over states. Predict spreads it. Correct concentrates it.

Belief after the first measurementTwo bar charts of probability over five corridor cells. Left: uniform prior 0.2 each. Right: after sensing a door, cells 1 and 3 (the doors) have 0.36 and the wall cells 0.09.00.2010.2020.2030.2040.20prior: no idea (0.20 each)00.0910.3620.0930.3640.09after “door” (cells 1 and 3 are doors)
A belief over five corridor cells before and after one measurement. Sensing a door raises the probability of the door cells and lowers the wall cells, but cannot tell the doors apart.

The mathematics

Bayes’ rule relates what we want (the state x given the measurement z) to what we can model (the measurement given the state):

Bayes rule
p(x ∣z)=p(z ∣x) p(x)p(z)p(x\,\mid z)=\frac{p(z\,\mid x)\,p(x)}{p(z)}
p(z)=∑x p(z ∣x) p(x)p(z)=\sum _{x}\,p(z\,\mid x)\,p(x)
p(x)
the prior: belief about the state before seeing z.
p(z | x)
the likelihood: how probable the measurement is if the state were x. This is the sensor model.
p(x | z)
the posterior: belief after seeing z.
p(z)
a normaliser that makes the posterior sum to one. It does not depend on x, so in practice we write the posterior ∝ likelihood × prior and normalise at the end.

The recursive Bayes filter

For a robot we track the belief bel(xt) = p(xt | z1:t, u1:t) over time. Two steps, given the previous belief, the control ut and the measurement zt:

predict
bel−(xt)=∑xt−1 p(xt ∣xt−1, ut) bel⁡(xt−1)\mathrm{bel}^{-}(x_{t})=\sum _{x_{t-1}}\,p(x_{t}\,\mid x_{t-1},\,u_{t})\,\operatorname{bel}(x_{t-1})
correct
bel⁡(xt)=η p(zt ∣xt) bel−(xt)\operatorname{bel}(x_{t})=\eta \,p(z_{t}\,\mid x_{t})\,\mathrm{bel}^{-}(x_{t})

η is the normaliser, and for continuous states the sum becomes an integral. The prediction step uses the motion model p(xt | xt−1, ut); the correction uses the measurement model p(zt | xt) (next lesson).

Why a recursion is allowed

  • Markov assumption: the current state summarises everything relevant from the past. Given xt−1 and ut, older data tell us nothing more about xt.
  • Measurement independence: given the state, the measurement does not depend on earlier measurements. Noise is not correlated over time.
  • A correct, static map in the localization case. With an unknown map the state includes it, which is the SLAM filter.

Implementations differ in how they represent the belief: a table of cell probabilities (histogram filter), a Gaussian (Kalman filters, EKF), or a set of samples (particle filters). The two steps are always the same.

A worked example: five cells, doors at 1 and 3

A circular corridor of five cells (0 to 4) has doors in cells 1 and 3. The robot has no idea where it is: bel = 0.2 each. The sensor says “door” with probability 0.8 if the cell is a door and 0.2 if it is a wall. A move command “one cell right” works with probability 0.8, undershoots (stays) with 0.1 and overshoots (two cells) with 0.1.

  1. Correct with “door”. Unnormalised: door cells 0.2 × 0.8 = 0.16 each; wall cells 0.2 × 0.2 = 0.04 each. The sum is 2 · 0.16 + 3 · 0.04 = 0.44. Normalised: door cells 0.364 each, wall cells 0.091 each.
  2. Predict “move right”. bel⁻(i) = 0.8 bel(i−1) + 0.1 bel(i) + 0.1 bel(i−2), indices modulo 5. Cell 0: 0.8·0.091 + 0.1·0.091 + 0.1·0.364 = 0.118. Cell 1: 0.8·0.091 + 0.1·0.364 + 0.1·0.091 = 0.118. Cell 2: 0.8·0.364 + 0.1·0.091 + 0.1·0.091 = 0.309. Cell 3: 0.8·0.091 + 0.1·0.364 + 0.1·0.364 = 0.146. Cell 4: 0.8·0.364 + 0.1·0.091 + 0.1·0.091 = 0.309. The sum is 1.00. The mass moved one cell right and spread out a little: the peaks at 2 and 4 are the old door cells shifted by one.
  3. Correct with “wall”. The wall likelihood is 0.8 for wall cells and 0.2 for door cells. Unnormalised: cell 0: 0.118·0.8 = 0.095; cell 1 (door): 0.118·0.2 = 0.024; cell 2: 0.309·0.8 = 0.247; cell 3 (door): 0.146·0.2 = 0.029; cell 4: 0.309·0.8 = 0.247. The sum is 0.642. Normalised: 0.147, 0.037, 0.385, 0.045, 0.385.
  4. Read the result. The robot is nearly sure it is in a wall cell next to a door’s right side: cell 2 or cell 4. It cannot decide between them because the corridor is symmetric: two hypotheses of equal weight. Another observation, or a move that crosses a landmark, is needed to break the tie.

Notice what a Gaussian could not do here: it would have forced one bump between cells 2 and 4. That is why filters other than the Kalman filter exist (Module 3).

Engineering implications and limitations

Practical consequences

  • Prediction increases entropy, correction decreases it. Plot the belief entropy or the covariance trace over time: a healthy filter oscillates; one that only grows has lost its measurements.
  • The sensor model decides the filter. A likelihood that is too sharp (overconfident sensor) kills correct hypotheses after one bad reading. Include a floor (a small probability for any reading) to survive outliers.
  • Symmetric worlds give multi-modal beliefs. A single Gaussian cannot represent them; histogram and particle filters can. Many failures in repetitive corridors are a collapsed belief that chose the wrong mode.
  • Cost. A histogram filter over a 2D grid with heading is large. The Gaussian filter is cheap but unimodal; particle filters sit between.
  • Normalise. Skipping the normaliser, or normalising wrongly, leaves probabilities that do not sum to one, which silently changes the relative weight of old and new evidence.

Limits

The Bayes filter is exact only when its assumptions hold. A map error, correlated measurement noise, or a motion model that ignores slip all violate them, and the filter keeps being confident anyway. The cure is better models, inflated noise, or robust likelihoods, not more updates.

Common misconceptions

“The correction step needs the full history.”

It needs only the predicted belief and the current measurement: the Markov assumption folds the history into the belief.

“A measurement tells you where you are.”

It updates a belief. A door reading in a corridor with several doors leaves several candidates.

“The filter forgets old evidence.”

It folds it into the belief. A belief that is wrong with confidence, however, takes many contradicting measurements to recover.

“Bayes’ rule is about subjective opinion.”

In a filter every term is a model that is tested and tuned against data: motion noise, sensor noise, map. Poor models give poor posteriors.

Engineering takeaways

  1. Posterior ∝ likelihood × prior; normalise at the end.
  2. The Bayes filter alternates prediction (motion model, entropy grows) and correction (measurement model, entropy shrinks).
  3. It relies on the Markov assumption and independent measurement noise.
  4. Symmetric environments produce multi-modal beliefs; Gaussians cannot hold them.
  5. EKF, particle and histogram filters differ only in how the belief is represented.

References and further reading

Primary papers and authoritative documentation.

Knowledge check

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

Question 1

In the corridor example the belief after the second correction has two equal peaks. Name one thing the robot could do to break the tie.

Explanation

Move to cross a distinguishing landmark or a door again, or use a different sensor reading that differs between the two candidate cells. Any new measurement whose likelihood differs between cell 2 and cell 4 will favour one of them after correction.

Question 2

What happens to the belief if the prediction step is skipped while the robot is actually moving?

Explanation

The belief stays centred on the old position while the robot moves away. The next correction compares the new measurement with the wrong cells, may assign near-zero likelihood to the true cell, and the filter can lock onto a wrong place with high confidence.

Question 3

A sensor model assigns probability 0 to seeing a wall in a door cell. After one false “wall” reading in a door cell, what is the consequence?

Explanation

The posterior for the true cell becomes exactly 0 and can never recover, because multiplying by zero is permanent. Real sensor models keep a small floor probability so a single outlier does not eliminate the truth.

What’s next

The filter needs two models: how the robot moves, and what a sensor sees from a given pose. The next lesson writes both for a 2D robot with range-bearing sensing, with their Jacobians.

Practice this lesson

Understand Pose Uncertainty

Propagate a pose covariance through odometry steps and a landmark update, and compare your ellipses with a Monte Carlo cloud.

Next lesson

M2-T6 — Motion and Observation Models

Write the process and measurement models for a 2D robot with range-bearing sensing, with their Jacobians.

Nothing below is required to finish this lesson. The last 2 entries are lessons of other courses on this site that teach the background or go further.