Skip to content
LumenaryAcademy
Perception 60 min

Uncertainty and Bayes filters

A robot never knows exactly where it is. It can know how unsure it is, and update that every time it moves and every time it looks.

Code tested · 5AI-draftedAwaiting review by a roboticist

Your guides: Chloe · The Builder, Margaret · The Experimenter, Gideon · The Safety Engineer

MotivationH

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.

IntuitionH

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.

1. no idea2. sees tape3. moves 5 cells4. sees tape again0.69
A belief over 20 cells on a loop, with tape under the cells marked in gold. 1: uniform, no information. 2: after seeing tape, three peaks (25% each). 3: after moving five cells, the peaks have shifted and spread. 4: after seeing tape again, one hypothesis dominates (69% on cell 8), with some doubt left on cell 14. Bar heights are the filter's actual probabilities.
DefinitionsH

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 XX, the next reading ZZ. Its distribution assigns a probability to every value, p(x)=P(X=x)p(x) = P(X = x), with ∑xp(x)=1\sum_x p(x) = 1 (for continuous quantities, a density that integrates to 1). The robot's belief at time tt is the distribution of its state given everything it has done and seen:

bel(xt)=p(xt∣u1:t, z1:t),\mathrm{bel}(x_t) = p(x_t \mid u_{1:t},\, z_{1:t}),

where u1:tu_{1:t} are the commands (controls) u1,…,utu_1, \dots, u_t and z1:tz_{1:t} the measurements z1,…,ztz_1, \dots, z_t.

Three rules do almost all the work. Conditional probability: p(a∣b)=p(a,b)/p(b)p(a \mid b) = p(a, b)/p(b), the probability of aa once you know bb. Total probability (marginalisation): p(a)=∑bp(a∣b) p(b)p(a) = \sum_b p(a \mid b)\,p(b); to get the chance of a reading, average over every place you might be. And their consequence:

Theorem— Bayes' rule

For a state xx and a measurement zz with p(z)>0p(z) > 0,

p(x∣z)=p(z∣x) p(x)p(z)=η  p(z∣x) p(x),η=1∑x′p(z∣x′) p(x′).p(x \mid z) = \frac{p(z \mid x)\,p(x)}{p(z)} = \eta\; p(z \mid x)\,p(x), \qquad \eta = \frac{1}{\sum_{x'} p(z \mid x')\,p(x')}.

Read it as: posterior ∝ likelihood × prior. The prior p(x)p(x) is what the robot believed before the reading. The likelihood p(z∣x)p(z \mid x) 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, p(x∣z)p(x \mid z). The constant η\eta just rescales so the posterior sums to 1, so in code we multiply and then normalise.

Definition— Conditional independence

Readings z1z_1 and z2z_2 are conditionally independent given xx if p(z1,z2∣x)=p(z1∣x) p(z2∣x)p(z_1, z_2 \mid x) = p(z_1 \mid x)\,p(z_2 \mid x): 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 nn readings have independent errors, each with variance σ2\sigma^2, the variance of their mean is σ2/n\sigma^2/n (variances of independent quantities add, and dividing by nn divides the variance by n2n^2). The standard deviation, the typical error, is therefore σ/n\sigma/\sqrt{n}: 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.

Worked examplesH

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 10/40=0.2510/40 = 0.25. The sensor reports "tape" (TT) with probability 0.90.9 when over tape and with probability 0.050.05 over bare rail. It reports TT. How likely is it that the robot is over tape?

Total probability gives the chance of the reading: p(T)=0.9×0.25+0.05×0.75=0.2625p(T) = 0.9 \times 0.25 + 0.05 \times 0.75 = 0.2625. Bayes' rule gives

p(tape∣T)=0.9×0.250.2625≈0.857.p(\text{tape} \mid T) = \frac{0.9 \times 0.25}{0.2625} \approx 0.857.

Now suppose only 2 cells of 40 were taped. The same sensor, the same reading, but p(tape∣T)=0.045/0.0925≈0.486p(\text{tape} \mid T) = 0.045 / 0.0925 \approx 0.486: 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, o=p/(1−p)o = p/(1-p). Bayes' rule becomes "posterior odds = prior odds × likelihood ratio", where the likelihood ratio of a TT reading is 0.9/0.05=180.9 / 0.05 = 18. Independent readings multiply their ratios. The program checks both numbers above and shows what repeated readings do.

python
# 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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

DefinitionsH

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) p(xt∣xt−1,ut)p(x_t \mid x_{t-1}, u_t) gives the probability of arriving in state xtx_t when command utu_t is executed from state xt−1x_{t-1}. For the rail robot, "advance one cell" lands one cell on with probability 0.90.9 and zero or two cells on with probability 0.050.05 each.

The measurement model (or sensor model) p(zt∣xt)p(z_t \mid x_t) gives the probability of reading ztz_t from state xtx_t. For the tape sensor, p(T∣taped cell)=0.9p(T \mid \text{taped cell}) = 0.9 and p(T∣bare cell)=0.05p(T \mid \text{bare cell}) = 0.05.

In State-space models and LQR the same two ingredients appeared as xt=Axt−1+Butx_{t} = A x_{t-1} + B u_t and yt=Cxty_t = C x_t. 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 xt−1x_{t-1} and utu_t, the new state xtx_t does not depend on any earlier states, commands or readings; and given xtx_t, the reading ztz_t does not depend on anything else. In symbols, p(xt∣x0:t−1,u1:t,z1:t−1)=p(xt∣xt−1,ut)p(x_t \mid x_{0:t-1}, u_{1:t}, z_{1:t-1}) = p(x_t \mid x_{t-1}, u_t) and p(zt∣x0:t,u1:t,z1:t−1)=p(zt∣xt)p(z_t \mid x_{0:t}, u_{1:t}, z_{1:t-1}) = p(z_t \mid x_t).

xt−1xtxt+1utut+1zt−1ztzt+1
The structure the Bayes filter assumes, drawn as a dynamic Bayesian network. Each state depends only on the previous state and the command; each reading depends only on the current state. Everything the past can tell you about the future passes through the current state.

Theorem— The Bayes filter

Under the Markov assumption, the belief can be updated recursively. Given bel(xt−1)\mathrm{bel}(x_{t-1}), a command utu_t and a reading ztz_t:

predict:bel‾(xt)=∑xt−1p(xt∣xt−1,ut) bel(xt−1),correct:bel(xt)=η  p(zt∣xt) bel‾(xt).\text{predict:}\quad \overline{\mathrm{bel}}(x_t) = \sum_{x_{t-1}} p(x_t \mid x_{t-1}, u_t)\,\mathrm{bel}(x_{t-1}), \qquad \text{correct:}\quad \mathrm{bel}(x_t) = \eta\; p(z_t \mid x_t)\,\overline{\mathrm{bel}}(x_t).

For continuous states the sum is an integral.

Proof

Apply Bayes' rule to xtx_t and ztz_t, keeping everything else as background knowledge: bel(xt)=η p(zt∣xt,u1:t,z1:t−1)  p(xt∣u1:t,z1:t−1)\mathrm{bel}(x_t) = \eta\, p(z_t \mid x_t, u_{1:t}, z_{1:t-1})\; p(x_t \mid u_{1:t}, z_{1:t-1}). By the Markov assumption the first factor is p(zt∣xt)p(z_t \mid x_t). For the second, use total probability over the previous state: p(xt∣u1:t,z1:t−1)=∑xt−1p(xt∣xt−1,u1:t,z1:t−1)  p(xt−1∣u1:t,z1:t−1)p(x_t \mid u_{1:t}, z_{1:t-1}) = \sum_{x_{t-1}} p(x_t \mid x_{t-1}, u_{1:t}, z_{1:t-1})\; p(x_{t-1} \mid u_{1:t}, z_{1:t-1}). The Markov assumption reduces the first factor to p(xt∣xt−1,ut)p(x_t \mid x_{t-1}, u_t). In the second, the command utu_t was issued after xt−1x_{t-1} and carries no information about it (the robot chooses commands from its data, not from a secret view of the truth), so it is p(xt−1∣u1:t−1,z1:t−1)=bel(xt−1)p(x_{t-1} \mid u_{1:t-1}, z_{1:t-1}) = \mathrm{bel}(x_{t-1}). Substituting gives the two lines.

∎

The filter's memory is one distribution: everything the robot ever saw and did is summarised in bel(xt−1)\mathrm{bel}(x_{t-1}). 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).

ComputationC

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 H=−∑xp(x)log⁡2p(x)H = -\sum_x p(x)\log_2 p(x), a measure of uncertainty in bits (log⁡240≈5.32\log_2 40 \approx 5.32 for a uniform belief, 0 for certainty), the most probable cell, and the true cell.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Read the run in three acts.

  1. 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.
  2. 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.
  3. 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%.
ComputationC

When the model is too sure of itself

A tempting shortcut is to tell the filter that its sensor and wheels never err: p(T∣tape)=1p(T \mid \text{tape}) = 1, p(T∣bare)=0p(T \mid \text{bare}) = 0, 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.

python
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.")
        break
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

For 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.

ExplanationH

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 (x,y,θ)(x, y, \theta) 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 representationFilterGood atWeak at
Histogram over a gridGrid (histogram) filterAny shape, multiple hypotheses, easy to understandCost grows exponentially with state dimension
Gaussian (mean and covariance)Kalman filter, EKF, UKFFast, high-dimensional, smooth trackingOnly one hypothesis; needs near-linear models
Weighted samplesParticle filterMultiple hypotheses, any noise, global localisationNeeds many samples in high dimensions
A whole trajectory, optimisedFactor graphs, smoothingLarge-scale mapping, revisiting the pastHeavier 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 misconceptionsH

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.

History & global context

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

Exercises

1. Uncertainty and Bayes filters

Warm-upHuman

A Bayes filter alternates a predict step (after a command) and a correct step (after a reading). Which statement is true?

Choose one

2. Uncertainty and Bayes filters

CoreHuman

A cleaning robot has a downward infrared cliff sensor that warns of a stair edge. Over a stair edge it raises an alarm with probability 0.990.99. Over ordinary floor it raises a false alarm with probability 0.030.03 (dark carpet absorbs the light and looks like a drop). On this robot's route, 1%1\% 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

CoreHuman

A robot on a loop of 5 cells (numbered 0 to 4) believes it is in cell 0 or cell 1, with probability 0.50.5 each. It is told to advance one cell; it does so with probability 0.80.8 and stays put with probability 0.20.2. Tape lies under cell 2 only. The tape sensor then reports "tape"; it does so with probability 0.80.8 over tape and 0.20.2 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

CoreHuman

A 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.

Choose all that apply

5. Uncertainty and Bayes filters

Warm-upHuman

A histogram localiser for a robot in a 20 m×10 m20\,\text{m} \times 10\,\text{m} hall stores a belief over (x,y,θ)(x, y, \theta) with cells 1010 cm on a side and heading bins of 5°5°. How many cells does the grid have?

6. Uncertainty and Bayes filters

CoreComputational

Write the two steps of a histogram filter on a loop of cells.

  • predict(bel, move): bel is a 1-D array of probabilities; move is a dict mapping an advance k (an integer, possibly 0 or negative) to its probability. Return the predicted belief.
  • update(bel, likelihood): likelihood[i] is p(z∣cell i)p(z \mid \text{cell } i). Return the normalised posterior.
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Uncertainty and Bayes filters

StretchComputational

Real 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?

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources