A robot that knows what it does not know
A small robot rides on a rail through a vertical-farm greenhouse in Nairobi, pausing at each rack of seedlings to photograph the leaves. The rail is a 20-metre loop. The robot counts wheel turns, so it has an idea how far it has gone, but its wheel slips a little on the damp rail, and after a few laps that idea is wrong by metres. To correct itself it has a downward-looking light sensor that sees strips of reflective tape stuck to the rail at a few places. The sensor is good but not perfect: a wet patch sometimes shines like tape, and dirty tape is sometimes missed.
Where is the robot? The honest answer is never a single number. It is something like: "probably near rack 7; possibly near rack 15, which looks the same; certainly not near the door". In Wheeled robots and odometry you saw dead reckoning drift without bound. In State-space models and LQR you met observers, which correct a model's prediction with measurements, but they track a single estimate and say nothing about how far to trust it. This lesson gives the robot a richer state of mind: a belief, a probability for every place it might be, updated with one rule every time it moves and every time it senses.
That rule is the Bayes filter. Every estimator in the rest of this level is a version of it: the Kalman filter when beliefs are Gaussian, the particle filter when beliefs are clouds of samples, occupancy maps in Depth sensing and point clouds, and the estimation half of SLAM. Here we implement it in its plainest form, a histogram over a grid of places, and watch a robot become certain, lose its certainty and win it back.
Belief: a probability for every place
Chop the greenhouse loop into cells and give each cell a number between 0 and 1, the robot's probability that it is there; the numbers add up to 1. That list of numbers is the belief. Two things change it.
- Moving blurs it. If the robot was surely in cell 3 and commands "advance one cell", it is now probably in cell 4, but perhaps in 3 (the wheel slipped) or 5 (it overshot). Motion shifts the belief along and spreads it out. Motion alone can only make the robot less certain.
- Sensing sharpens it. If the sensor reports "tape", every taped cell becomes more plausible and every bare cell less. Each cell's probability is multiplied by how likely that reading would have been from there, and the whole list is rescaled to add up to 1.
The figure shows four moments on a short loop of 20 cells with tape under cells 3, 8 and 14. At first the robot has no idea. One sighting of tape leaves three equally good hypotheses. Moving five cells carries all three along and blurs them. A second sighting of tape is consistent with only one of the three stories, because only one taped cell lies five cells after another, and that hypothesis now holds 69% of the belief.
The probability a robot needs
Lumenary Math's Conditional probability and independence and Probability theory develop these ideas carefully. Here is the toolkit a robot uses, in robot language.
Definition— Random variable, distribution, belief
A random variable is a quantity whose value the robot is unsure of: its cell , the next reading . Its distribution assigns a probability to every value, , with (for continuous quantities, a density that integrates to 1). The robot's belief at time is the distribution of its state given everything it has done and seen:
where are the commands (controls) and the measurements .
Three rules do almost all the work. Conditional probability: , the probability of once you know . Total probability (marginalisation): ; to get the chance of a reading, average over every place you might be. And their consequence:
Theorem— Bayes' rule
For a state and a measurement with ,
Read it as: posterior ∝ likelihood × prior. The prior is what the robot believed before the reading. The likelihood is the sensor's datasheet in probabilistic form: how often this reading occurs from each state. It is the direction a robot can actually model, because it is about the physics of the sensor. Bayes' rule turns it round into what we want, . The constant just rescales so the posterior sums to 1, so in code we multiply and then normalise.
Definition— Conditional independence
Readings and are conditionally independent given if : once you know the true state, one reading tells you nothing more about the other. Their errors are unrelated.
Conditional independence is what lets a robot multiply evidence. It also answers the question left open in How robots sense the world: why does averaging four times as many readings only halve the error? If readings have independent errors, each with variance , the variance of their mean is (variances of independent quantities add, and dividing by divides the variance by ). The standard deviation, the typical error, is therefore : four times the readings, half the error. If the errors are not independent, for instance a sensor with a fixed offset, averaging does not remove them at all.
Bayes' rule with a real sensor
Example— One reading of the tape sensor
The greenhouse rail has 40 cells, 10 of them taped, and the robot has no idea where it is: its prior that it is on tape is . The sensor reports "tape" () with probability when over tape and with probability over bare rail. It reports . How likely is it that the robot is over tape?
Total probability gives the chance of the reading: . Bayes' rule gives
Now suppose only 2 cells of 40 were taped. The same sensor, the same reading, but : less than a coin toss. When the thing you are looking for is rare, false alarms from the many places where it is absent can outnumber true detections from the few places where it is present. This is the base-rate effect, and it is why a "90% accurate" sensor never makes a robot 90% sure.
A convenient form for repeated evidence uses odds, . Bayes' rule becomes "posterior odds = prior odds × likelihood ratio", where the likelihood ratio of a reading is . Independent readings multiply their ratios. The program checks both numbers above and shows what repeated readings do.
# Bayes' rule for one reading of the tape sensor
p_hit, p_false = 0.9, 0.05 # p(T | tape), p(T | bare rail)
for name, prior in [("10 of 40 cells taped", 10 / 40), ("2 of 40 cells taped", 2 / 40)]:
p_T = p_hit * prior + p_false * (1 - prior) # total probability of seeing "T"
post = p_hit * prior / p_T # Bayes' rule
print(f"{name}: p(T) = {p_T:.4f}, p(tape | T) = {post:.3f}")
# The same reading, repeated k times while the robot stands still.
prior = 10 / 40
odds0 = prior / (1 - prior)
ratio = p_hit / p_false # likelihood ratio of one "T"
print(f"\nlikelihood ratio of one 'T' reading: {ratio:.0f}")
for k in range(1, 5):
odds = odds0 * ratio ** k # valid only if readings are independent given the cell
print(f"{k} reading(s) of 'T': p(tape) = {odds / (1 + odds):.5f}")Two readings take the robot from 0.857 to 0.991 and four to 0.99997. That is correct if the readings are independent given the cell. If the robot is parked over a wet patch that shines like tape, all four readings make the same mistake, and the real probability that it is over tape has barely moved from 0.857. The filter has no way to know this; only the person who wrote the sensor model can.
Motion models, measurement models and the Bayes filter
A filter needs two models of the world, both written as conditional probabilities.
Definition— Motion model and measurement model
The motion model (or transition model) gives the probability of arriving in state when command is executed from state . For the rail robot, "advance one cell" lands one cell on with probability and zero or two cells on with probability each.
The measurement model (or sensor model) gives the probability of reading from state . For the tape sensor, and .
In State-space models and LQR the same two ingredients appeared as and . The probabilistic versions add the noise explicitly: they say not "where the robot goes" but "where it might go, and how likely each possibility is".
Definition— The Markov assumption
The state is complete: given and , the new state does not depend on any earlier states, commands or readings; and given , the reading does not depend on anything else. In symbols, and .
Theorem— The Bayes filter
Under the Markov assumption, the belief can be updated recursively. Given , a command and a reading :
For continuous states the sum is an integral.
Proof
Apply Bayes' rule to and , keeping everything else as background knowledge: . By the Markov assumption the first factor is . For the second, use total probability over the previous state: . The Markov assumption reduces the first factor to . In the second, the command was issued after and carries no information about it (the robot chooses commands from its data, not from a secret view of the truth), so it is . Substituting gives the two lines.
∎
The filter's memory is one distribution: everything the robot ever saw and did is summarised in . That is what makes it usable in real time. The predict step is a convolution of the belief with the motion noise; the correct step is a pointwise multiplication by the likelihood, followed by normalisation. The same recursion appears, with different names, as the forward algorithm for hidden Markov models in speech recognition and genomics (Lumenary Math's Markov chains covers the chain of states underneath).
A histogram localiser
On a finite grid, the belief is a NumPy array and each step of the filter is a line or two. The robot below starts with a uniform belief, drives 42 cells round the 40-cell loop (one commanded cell per step, slipping now and then), and reads its tape sensor after every step, except between steps 15 and 28, when it passes through a misting zone that wets the sensor and the readings are discarded. Each printed line shows the belief as a strip of 40 characters, one per cell (blank for less than 0.005, then ., :, +, #, and @ for 0.4 or more), its entropy , a measure of uncertainty in bits ( for a uniform belief, 0 for certainty), the most probable cell, and the true cell.
import numpy as np
rng = np.random.default_rng(2)
N = 40 # a loop of rail: 40 cells of 0.5 m each
tape = np.zeros(N, dtype=bool)
tape[[1, 2, 7, 15, 16, 17, 22, 30, 34, 35]] = True # reflective tape under these cells
P_HIT, P_FALSE = 0.9, 0.05 # p(z = tape | tape), p(z = tape | bare rail)
MOVE = {0: 0.05, 1: 0.9, 2: 0.05} # "advance one cell": p(actual advance = k)
def predict(bel):
"""Motion update: bel(x) <- sum over k of p(advance k) * bel(x - k), on a loop."""
return sum(p * np.roll(bel, k) for k, p in MOVE.items())
def update(bel, saw_tape):
"""Measurement update: multiply by p(z | x) cell by cell, then normalise."""
if saw_tape:
like = np.where(tape, P_HIT, P_FALSE)
else:
like = np.where(tape, 1 - P_HIT, 1 - P_FALSE)
post = like * bel
return post / post.sum()
def entropy_bits(bel):
p = bel[bel > 0]
return float(-(p * np.log2(p)).sum())
def strip(bel):
"""One character per cell: ' ' < 0.005 <= '.' < 0.02 <= ':' < 0.05 <= '+' < 0.15 <= '#' < 0.4 <= '@'."""
return "".join(" .:+#@"[int(np.searchsorted([0.005, 0.02, 0.05, 0.15, 0.4], b, side="right"))] for b in bel)
true, bel = 5, np.full(N, 1.0 / N) # the filter starts with no idea where it is
print(" rail [" + "".join("T" if m else "_" for m in tape) + "]")
for t in range(1, 43):
true = (true + rng.choice(3, p=[0.05, 0.9, 0.05])) % N # the real robot moves...
bel = predict(bel) # ...and the filter predicts
blind = 15 <= t <= 28 # misting zone: no usable readings
if not blind:
z = rng.random() < (P_HIT if tape[true] else P_FALSE)
bel = update(bel, z)
if t in (1, 3, 6, 9, 12, 14, 17, 20, 23, 26, 28, 30, 33, 36, 39, 42):
best = int(np.argmax(bel))
seen = "--" if blind else ("T" if z else "_")
print(f"t={t:2d} z={seen:2s} [{strip(bel)}] H={entropy_bits(bel):4.2f} bits"
f" best={best:2d} (p={bel[best]:.2f}) true={true:2d}")Read the run in three acts.
- Becoming certain (steps 1 to 14). The first "no tape" reading only rules out the taped cells, and the entropy barely moves from 5.32 to 5.07 bits. By step 3 the robot has several hypotheses moving in step with each other. At step 9 it sees tape, and by step 12, having seen the end of the three-cell strip go by, it is 82% sure it is in cell 18, which is correct. Entropy has fallen to 1.21 bits.
- Becoming uncertain (steps 15 to 28). In the misting zone the filter can only predict. Each step convolves the belief with the motion noise, so the peak sinks (0.69, 0.54, 0.44, 0.38, 0.33, 0.31) and spreads into a hump four or five cells wide, while the entropy climbs to 2.93 bits. Note that the peak still tracks the truth: the robot is not lost, it is honestly less sure.
- Certain again (steps 29 to 42). Two readings after leaving the mist, the belief snaps back to 80% on the correct cell, and after the tape at cells 1 and 2 and then 7 it reaches 94%.
When the model is too sure of itself
A tempting shortcut is to tell the filter that its sensor and wheels never err: , , and "advance one cell" always advances exactly one. The arithmetic is simpler and the belief collapses to a single cell faster. The program runs that filter beside an honest one on the same robot.
import numpy as np
N = 40
tape = np.zeros(N, dtype=bool)
tape[[1, 2, 7, 15, 16, 17, 22, 30, 34, 35]] = True
def make_filter(p_hit, p_false, move):
def step(bel, z):
bel = sum(p * np.roll(bel, k) for k, p in move.items()) # predict
like = np.where(tape, p_hit, p_false) if z else np.where(tape, 1 - p_hit, 1 - p_false)
post = like * bel
total = post.sum()
return post / total if total > 0 else post # all zero: nothing left to normalise
return step
honest = make_filter(0.9, 0.05, {0: 0.05, 1: 0.9, 2: 0.05}) # the noise the robot really has
certain = make_filter(1.0, 0.0, {1: 1.0}) # "my sensor and wheels never err"
rng = np.random.default_rng(11)
true = 5
bel_h = bel_c = np.full(N, 1.0 / N)
for t in range(1, 41):
advance = rng.choice(3, p=[0.05, 0.9, 0.05])
true = (true + advance) % N
z = rng.random() < (0.9 if tape[true] else 0.05)
bel_h, bel_c = honest(bel_h, z), certain(bel_c, z)
note = "" if advance == 1 else f" <- wheel slip: advanced {advance}"
if t % 5 == 0 or advance != 1 or bel_c.sum() == 0:
c = "all zero!" if bel_c.sum() == 0 else f"best={int(np.argmax(bel_c)):2d} p={bel_c.max():.2f}"
print(f"t={t:2d} true={true:2d} | honest: best={int(np.argmax(bel_h)):2d} p={bel_h.max():.2f}"
f" | certain: {c}{note}")
if bel_c.sum() == 0:
print("The overconfident filter has ruled out every cell, including the true one.")
breakFor ten steps the overconfident filter looks better: at step 10 it is 50% sure of the right cell while the honest one is 44% sure. At step 11 the wheel slips and the robot advances two cells. The overconfident filter, which believes slips are impossible, moves its belief one cell and is now 100% sure of cell 16 while the robot is in 17. At step 12 the next reading contradicts every hypothesis it has left, every cell's probability is zero, and there is nothing to normalise. In floating point the division would produce nan; in a robot it means a localiser that has crashed or, worse, one that keeps reporting the wrong place. The honest filter took the slip in its stride.
The lesson generalises: never assign probability zero to something that can happen. A zero in a Bayes filter can never be undone, because multiplication by any likelihood keeps it zero. Real sensor models add a small floor for "something unexpected" (a random reading, a person walking past), and real motion models are a little wider than the measured noise.
The professional view
Grid-based Bayes filtering on real robots is called Markov localisation, and it made its name in museums. In 1997 the robot RHINO, built at the University of Bonn, guided visitors around the Deutsches Museum in Bonn for six days, and in 1998 its successor MINERVA did the same at the Smithsonian's National Museum of American History in Washington. Both had to localise among crowds that blocked their sonar and laser beams; the papers by Burgard, Fox, Thrun and colleagues in the references describe how a grid belief over coped, including filtering out readings that were probably people rather than walls.
Today the grid form survives where the state is small or naturally discrete: a robot on a rail or in a lift shaft, a topological map ("which room am I in?"), the heading of a compass-less robot, and above all occupancy grids, where the grid is over the map rather than the robot's pose. Each cell holds the belief that it is occupied, and each lidar beam is a measurement update; you will build one in Depth sensing and point clouds.
For pose estimation, practitioners choose a representation of the belief to make the Bayes filter affordable:
| Belief representation | Filter | Good at | Weak at |
|---|---|---|---|
| Histogram over a grid | Grid (histogram) filter | Any shape, multiple hypotheses, easy to understand | Cost grows exponentially with state dimension |
| Gaussian (mean and covariance) | Kalman filter, EKF, UKF | Fast, high-dimensional, smooth tracking | Only one hypothesis; needs near-linear models |
| Weighted samples | Particle filter | Multiple hypotheses, any noise, global localisation | Needs many samples in high dimensions |
| A whole trajectory, optimised | Factor graphs, smoothing | Large-scale mapping, revisiting the past | Heavier computation, not a simple recursion |
The next two lessons are the second and third rows; the last row is SLAM. In a typical ROS 2 navigation stack, a particle filter (AMCL) localises against the map, an extended Kalman filter fuses wheels and inertial sensors (the robot_localization package), and an occupancy grid stores the map: three Bayes filters with three belief representations, running side by side.
The Bayes filter also connects robotics to machine learning. A recurrent neural network that reads sensor data and outputs a state estimate has the same shape: a hidden state carried forward and updated with each new input. Research on "differentiable filters" trains the motion and measurement models of a Bayes filter from data while keeping its structure; Lumenary CS's learning from data and neural networks lessons cover the learning side.
Common misconceptions
Misconception
"Probability describes randomness in the world; the robot's position is not random." The robot is somewhere definite. The belief describes the robot's knowledge, and two robots with different data hold different beliefs about the same fact. That is exactly what we want: the belief is an honest summary of evidence, used to decide how carefully to act.
Misconception
"A sensor that is right 90% of the time makes the robot 90% sure." The posterior depends on the prior. With tape under 2 of 40 cells, a single "tape" reading from a sensor with a 90% hit rate and a 5% false-alarm rate leaves the robot only 49% sure it is over tape.
Misconception
"More readings always mean more certainty." Only if their errors are independent given the state. Ten readings from a sensor parked over the same reflective puddle are worth little more than one. Good systems downsample correlated data (using every fifth lidar beam, say) or inflate the noise in the model to compensate.
Misconception
"The motion step and the sensor step are both corrections." Prediction can only add uncertainty (it spreads the belief); correction usually removes it. The misting zone in the simulation shows a filter that predicts without correcting: still right on average, steadily less sure.
Misconception
"A sharper model is a better model." A model that rules out what can happen (a zero likelihood, a motion with no slip) makes the filter overconfident and eventually catastrophically wrong, as the second simulation showed. Err on the side of a model that is slightly too uncertain.
A short history
Thomas Bayes's essay on inverse probability was published in 1763, after his death, and Pierre-Simon Laplace developed the rule into a general method of reasoning from evidence over the following decades. Recursive estimation came from engineering in the 1960s: Rudolf Kálmán's filter (1960) and the work of Ruslan Stratonovich on nonlinear filtering. Hidden Markov models and their forward algorithm, developed by Leonard Baum and colleagues in the late 1960s, became the backbone of speech recognition. Probabilistic robotics took shape in the 1990s, when grid-based Markov localisation ran on museum robots in Germany and the United States, and the textbook Probabilistic Robotics by Thrun, Burgard and Fox (2005) made "represent uncertainty explicitly" the field's working assumption.
Exercises
1. Uncertainty and Bayes filters
Warm-upHumanA Bayes filter alternates a predict step (after a command) and a correct step (after a reading). Which statement is true?
2. Uncertainty and Bayes filters
CoreHumanA cleaning robot has a downward infrared cliff sensor that warns of a stair edge. Over a stair edge it raises an alarm with probability . Over ordinary floor it raises a false alarm with probability (dark carpet absorbs the light and looks like a drop). On this robot's route, of the places it checks are stair edges. The sensor raises an alarm. What is the probability, in percent, to the nearest whole number, that the robot really is at a stair edge?
3. Uncertainty and Bayes filters
CoreHumanA robot on a loop of 5 cells (numbered 0 to 4) believes it is in cell 0 or cell 1, with probability each. It is told to advance one cell; it does so with probability and stays put with probability . Tape lies under cell 2 only. The tape sensor then reports "tape"; it does so with probability over tape and over bare rail. What is the robot's probability of being in cell 2, in percent, to the nearest whole number?
4. Uncertainty and Bayes filters
CoreHumanA filter multiplies the likelihoods of readings as if their errors were independent given the state. In which of these situations is that assumption badly wrong? Select all that apply.
5. Uncertainty and Bayes filters
Warm-upHumanA histogram localiser for a robot in a hall stores a belief over with cells cm on a side and heading bins of . How many cells does the grid have?
6. Uncertainty and Bayes filters
CoreComputationalWrite the two steps of a histogram filter on a loop of cells.
predict(bel, move):belis a 1-D array of probabilities;moveis a dict mapping an advancek(an integer, possibly 0 or negative) to its probability. Return the predicted belief.update(bel, likelihood):likelihood[i]is . Return the normalised posterior.
7. Uncertainty and Bayes filters
StretchComputationalReal corridors have ends. Write predict_corridor(bel, move) for a corridor of len(bel) cells with a wall at each end: a move that would take the robot past either end leaves it in the end cell instead (it pushes against the wall). move is a dict {advance k: probability} as before. Then think about the last test: a robot that keeps driving forward with no sensor at all becomes certain where it is. Why?
Further reading and resources
- Probabilistic Robotics · Sebastian Thrun, Wolfram Burgard and Dieter Fox · 2005The standard textbook on probabilistic state estimation for robots (MIT Press). Chapters 2 and 8 cover the Bayes filter and grid localisation.
- Markov Localization for Mobile Robots in Dynamic Environments · Dieter Fox, Wolfram Burgard and Sebastian Thrun · 1999Grid-based Bayes filtering on real robots, including the museum tour guides, and how to cope with people walking past the sensors.
- Experiences with an interactive museum tour-guide robot · Wolfram Burgard et al. · 1999RHINO, which guided visitors at the Deutsches Museum in Bonn in 1997 using Markov localisation.
- Bayesian Filtering and Smoothing (2nd edition, free pre-publication PDF) · Simo Särkkä and Lennart Svensson · 2023A rigorous, readable treatment of Bayes filters, Kalman filters and particle filters.
- A tutorial on hidden Markov models and selected applications in speech recognition · Lawrence R. Rabiner · 1989The same recursion as this lesson's filter, under the name "forward algorithm", from speech recognition.