M10-T2 — Inverse Sensor Models

Learning objectives

After this lesson, you should be able to:

• Define the inverse sensor model and contrast it with the forward model of Module 5.
• Estimate an inverse sensor model from data by counting, and read its shape.
• Explain why a free-space update that is too strong erases thin walls, even with a perfect sensor.
• Choose p_occ, p_free, clamps and handling of max-range and spurious readings.

The intuition

The forward model of Module 5 says: if the world is like this, what will the sensor read? Occupancy mapping needs the opposite: given this reading, what do I believe about this cell? That is the inverse sensor model $p(m_i\mid z,x)$. It is harder to write down because it depends on everything about the beam (its width, its noise, the angle of incidence) and on the world's prior.

We can estimate it from data when we have a map and a pose: simulate readings, and for each cell at a given distance from the reading, count how often it truly contains a wall.

The left panel shows what the data say, for a scanner with 10 cm noise in a grid with 25 cm cells. Cells half a metre or more in front of the reading are walls with probability 0.03 or less, so they are free. At the reading, the probability that the cell contains a wall is only 0.39: not 0.7, and not near 1. Noise and quantisation put the true wall often one cell away: the cell a quarter metre in front of the reading is a wall 23% of the time and the cell a quarter metre behind 32%. Behind, the probability falls to about 0.1, the fraction of the grid that is wall: the reading says nothing about what lies beyond.

The hand-set rule (0.3 for free, 0.7 at the end) is a coarse approximation of this shape, and it is a good one only if its two numbers are chosen well. The right panel shows what happens when the free-space number is too strong. With p_free = 0.45 only 3 of the 160 wall cells are wrongly believed free; with 0.30, 59; with 0.10, 90 (more than half of the walls) with a sensor that has no spurious readings at all. The reason: a wall cell is crossed tangentially by many beams that end beyond it or just in front of it, and each of those votes “free”; if free votes are strong they outweigh the occasional hit.

Every cell is judged by all beams that touch it. A wall cell touched by one hit and several near misses needs an inverse model in which a near miss is weak evidence of free space, weaker than a hit is of occupation.

Definitions

Forward model

$p(z\mid m,x)$: the sensor’s physics, as in Module 5. Easy to write and to calibrate.

Inverse model

$p(m_i\mid z,x)$: what a reading says about a cell. Needed by the grid, and obtained either from the forward model by Bayes’ rule or directly from data.

Learned inverse model

The table $P(m_i=1\mid d)$ of the fraction of cells that are occupied among those at signed distance $d$ from a reading, over many readings with a known map.

Beam width

The angle over which a real sensor integrates (a sonar’s 15–30° cone, a laser’s 0.25°). Wide beams must update all cells in the cone.

Spurious reading

A reading of something that is not part of the static map (a person, dust, a reflection). It gives wrong free-space votes behind itself and wrong hits in front.

Derivation: from the forward model, and why near misses matter

Suppose a cell of size $s$ lies at signed distance $d$ from where the reading ended, and the sensor noise has standard deviation $\sigma$. The probability that the true surface is within the cell, given the reading, is the probability that the true range lies in the cell's interval.

1. $$r_\mathrm{true}\mid z\sim\mathcal{N}(z,\sigma^2)$$

   With a flat prior over the range, the true range is Gaussian around the reading (the likelihood read as a function of the range).

2. $$P(\text{surface in cell at } d)=\Phi\!\left(\frac{d+s/2}{\sigma}\right)-\Phi\!\left(\frac{d-s/2}{\sigma}\right)$$

   Integrate the Gaussian over the cell. At $d=0$ with $s=0.25$ and $\sigma=0.1$ this is $2\Phi(1.25)-1=0.79$. For the neighbouring cell at $d=\pm0.25$ it is $\Phi(3.75)-\Phi(1.25)=0.11$.

3. $$P(m=1\mid d)\approx P(\text{surface in cell})\cdot 1+\bigl(1-P(\text{surface in cell})\bigr)\,p_0$$

   A cell that does not hold the surface can still be occupied for another reason: an obstacle behind, a corner. This is the prior share $p_0$ of occupied cells.

The learned values, 0.39 at the reading, are lower than the Gaussian computation (0.79) because in the data a cell at a wall is only counted if the wall passes through that cell, and the angle of incidence spreads the hit position along the beam by more than the range noise: at a glancing angle the surface crosses many cells along the beam. The shape (a peak at the reading, a fall in front, the prior behind) agrees.

Why a free update can erase a wall

Consider a wall cell. A beam that hits that cell adds $\log(p_\mathrm{occ}/(1-p_\mathrm{occ}))$. A beam that passes through the cell and ends further along (because it hit the wall at a glancing angle, further along the wall, or a spurious object behind) adds $\log(p_\mathrm{free}/(1-p_\mathrm{free}))$. If $h$ beams hit the cell and $f$ pass through it, the log odds is

1. $$\ell=h\,\log\frac{p_\mathrm{occ}}{1-p_\mathrm{occ}}+f\,\log\frac{p_\mathrm{free}}{1-p_\mathrm{free}}$$

   The sum of the evidence of each type.

2. $$\ell<0\quad\Longleftrightarrow\quad \frac{f}{h}>\frac{\log\bigl(p_\mathrm{occ}/(1-p_\mathrm{occ})\bigr)}{\log\bigl((1-p_\mathrm{free})/p_\mathrm{free}\bigr)}$$

   The wall cell is believed free when the ratio of pass-throughs to hits exceeds this threshold. With p_occ = 0.7 the numerator is 0.85; with p_free = 0.45 the denominator is 0.20, so the threshold is 4.2; with p_free = 0.3 it is 0.85/0.85 = 1; with 0.1 it is 0.85/2.2 = 0.39.

3. $$f/h\ \text{for a wall cell at a glancing angle can exceed 1}$$

   Beams that hit the wall at a small angle to its surface cross each wall cell and end in a later cell, so f is large, and h small. Hence the erased walls in the data.

The strength of the free update, relative to the occupied one, sets how many near misses a wall cell can survive. For thin walls and oblique beams p_free must be weak (near 0.5), or the model must treat the cells next to the endpoint differently.

A worked example

The room of the last lesson (10 × 8 m, a divider, 160 wall cells, 25 cm cells), mapped from 10 poses with 180-beam scans. Two programs.

1. Learned model. From five runs of the room with 5% spurious readings and 10 cm noise, the printed table gives, for a cell at signed distance d from the reading: 0.004 at −1.0 m, 0.032 at −0.5 m, 0.229 at −0.25 m, 0.394 at 0 m, 0.319 at +0.25 m, 0.115 at +0.5 m and about 0.10 beyond. The model is a bump of width about 0.5 m around the reading, with a long flat tail.
2. Strength of the free update. With p_occ = 0.7 and a perfect sensor (0% spurious), the number of the 160 wall cells that end up believed free is 3 for p_free = 0.45, 59 for 0.30 and 90 for 0.10. Occupied cells at walls fall from 310 to 194 to 142 (fewer cells survive as walls, with holes where beams grazed them).
3. Spurious readings. With 10% spurious readings, the erased walls become 8, 57 and 101; with 25%, 18, 81 and 116. A spurious reading casts a free ray through the walls behind it and, when it ends in front, a false hit; the harm grows with the strength of p_free and with the spurious fraction.

import math
from robotprob import Rng, OccupancyGrid, mean

SEGS = [((0, 0), (10, 0)), ((10, 0), (10, 8)), ((10, 8), (0, 8)), ((0, 8), (0, 0)), ((5, 0), (5, 4))]
ZMAX, RES = 6.0, 0.25
def cast(x, y, th):
    dx, dy, best = math.cos(th), math.sin(th), ZMAX
    for (x1, y1), (x2, y2) in SEGS:
        ex, ey = x2 - x1, y2 - y1
        den = dx * ey - dy * ex
        if abs(den) < 1e-12: continue
        t = ((x1 - x) * ey - (y1 - y) * ex) / den
        u = ((x1 - x) * dy - (y1 - y) * dx) / den
        if t > 0.0 and 0.0 <= u <= 1.0 and t < best: best = t
    return best
def new_grid(): return OccupancyGrid(44, 36, RES, origin=(-0.5, -0.5))
truth = set()
g0 = new_grid()
for (x1, y1), (x2, y2) in SEGS:
    n = int(max(abs(x2 - x1), abs(y2 - y1)) / 0.05)
    for k in range(n + 1): truth.add(g0.cell(x1 + (x2 - x1) * k / n, y1 + (y2 - y1) * k / n))
near_wall = lambda i, j: any((i + a, j + b) in truth for a in (-1, 0, 1) for b in (-1, 0, 1))

POSES = [(2.0, 2.0), (3.0, 6.0), (7.5, 2.0), (8.0, 6.5), (4.0, 4.0), (6.5, 5.5), (1.5, 4.5), (9.0, 1.0), (5.5, 7.0), (2.5, 7.0)]
def readings(seed, outliers, noise=0.05, beams=180):
    rng = Rng(seed); out = []
    for (px, py) in POSES:
        for k in range(beams):
            a = 2 * math.pi * k / beams
            r = cast(px, py, a) + rng.gauss(0.0, noise)
            if rng.random() < outliers: r = rng.uniform(0.3, ZMAX)           # a spurious reading: an object that is not in the map
            out.append((px, py, a, max(0.1, r)))
    return out

def build(data, p_occ, p_free, clamp=10.0):
    g = OccupancyGrid(44, 36, RES, origin=(-0.5, -0.5), l_min=-clamp, l_max=clamp)
    for (px, py, a, r) in data: g.update_ray(px, py, a, r, ZMAX, p_occ, p_free)
    return g

def score(g):
    P = g.probabilities(); found = false_wall = 0
    for j in range(g.h):
        for i in range(g.w):
            if P[j][i] > 0.5:
                if near_wall(i, j): found += 1
                else: false_wall += 1
    free_wrong = sum(1 for (i, j) in truth if P[j][i] < 0.5)                  # wall cells believed free
    return found, false_wall, free_wrong

print('10 poses, p_occ = 0.7: how much should one beam passing through a cell count as evidence of free space?')
print('spurious  p_free   occupied at walls  false walls  wall cells believed free')
for out in (0.0, 0.1, 0.25):
    data = readings(5, out)
    for pf in (0.45, 0.3, 0.1):
        f, fw, fr = score(build(data, 0.7, pf))
        print(str(out).rjust(8), str(pf).rjust(7), str(f).rjust(15), str(fw).rjust(14), str(fr).rjust(18))

# an inverse sensor model learned from data: how likely is a cell to be occupied, given its distance along the beam from the reading?
rng = Rng(8)
counts = {}
for seed in range(1, 6):
    for (px, py, a, r) in readings(seed, 0.05, noise=0.1):
        for k in range(-6, 7):                                                # cells at signed distances -1.5 ... +1.5 m from the reading
            d = k * RES
            x, y = px + (r + d) * math.cos(a), py + (r + d) * math.sin(a)
            i, j = g0.cell(x, y)
            if not g0.inside(i, j): continue
            c = counts.setdefault(k, [0, 0])
            c[1] += 1
            if near_wall(i, j) and (i, j) in truth: c[0] += 1
print('learned inverse sensor model (a cell at signed distance d from the reading; negative = in front of it)')
print('d (m)  P(cell contains wall)  samples')
for k in sorted(counts):
    if -4 <= k <= 6:
        occ, n = counts[k]
        print(str(round(k * RES, 2)).rjust(5), str(round(occ / n, 3)).rjust(15), str(n).rjust(12))

10 poses, p_occ = 0.7: how much should one beam passing through a cell count as evidence of free space?
spurious  p_free   occupied at walls  false walls  wall cells believed free
     0.0    0.45             310              3                  3
     0.0     0.3             194              0                 59
     0.0     0.1             142              0                 90
     0.1    0.45             304              7                  8
     0.1     0.3             190              4                 57
     0.1     0.1             119              4                101
    0.25    0.45             291              8                 18
    0.25     0.3             155              0                 81
    0.25     0.1              89              0                116
learned inverse sensor model (a cell at signed distance d from the reading; negative = in front of it)
d (m)  P(cell contains wall)  samples
 -1.0           0.004         8919
-0.75           0.008         8903
 -0.5           0.032         8897
-0.25           0.229         8881
  0.0           0.394         8867
 0.25           0.319         8840
  0.5           0.115         7280
 0.75            0.09         4094
  1.0           0.105         3174
 1.25           0.109         2722
  1.5            0.09         2415

In robotics

Choosing the numbers in practice

• Start near $p_\mathrm{occ}=0.65\ldots0.75$ and $p_\mathrm{free}=0.40\ldots0.49$: the free update is weak, to avoid erasing walls. Mapping packages use values of this kind (for example the OctoMap defaults are, from memory and not re-checked here, a hit of 0.7 and a miss of 0.4).
• Tune on logged data with a reference map: count wall cells believed free and free cells believed occupied, as the program does. Choose the values that balance both.
• Use clamps of ±2 to ±4 in log odds, so that a changed world can be re-learned.
• Take the cell size into account: a grid finer than the sensor noise spreads hits over several cells and needs a lower p_occ per cell; a coarse grid gets sharper hits.

Beams that are not thin

Sonar and some time-of-flight sensors report the range to the nearest object anywhere in a cone 15–30° wide. The inverse model must then mark every cell at the range inside the cone as only possibly occupied (the object may be at any angle), and the cells before it as free; the walls then appear as arcs and need several poses to sharpen. Depth cameras give a dense set of thin beams and are handled as many rays, often with the occupied update applied only to the endpoint and the free update subsampled for speed.

Spurious readings and dynamic objects

People and carts create hits that are not part of the map and free rays that clear parts of it. Remedies: reject readings that disagree strongly with the current map and the pose uncertainty, mark a cell as “dynamic” when its evidence flips often, and keep the free update weak. Sensor failures (glass, dark absorbing surfaces, direct sun) produce missing hits; these are handled as unknown rather than free.

Learned and hybrid models

The counting method of this lesson extends to richer features (the angle of incidence, the range itself, the intensity of the return) and to learned models (logistic regression or a neural network on a local patch). They give a calibrated probability per cell, which makes the log-odds sum meaningful.

Common misconceptions

Key takeaways

1. The inverse sensor model p(m|z,x) says what a reading means for a cell; it includes the prior share of occupied cells and the geometry of beam and cell.
2. It can be learned by counting against a known map: a cell at the reading was a wall only 39% of the time, 23% and 32% for its neighbours, and nearly never half a metre in front.
3. A cell is judged by the sum over all the beams that touch it, so near misses at glancing angles vote free: with p_free = 0.3 about 37% of the wall cells (59 of 160) were erased even with a perfect sensor.
4. Keep the free update weak (p_free near 0.4 to 0.49) and the clamps modest; treat spurious readings and wide beams explicitly.
5. Tune p_occ, p_free and the clamps on logged data with a reference map, by counting missing walls and false walls.

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, sections 9.2 (the occupancy grid algorithm) and 9.2.2 (learning inverse sensor models). Paid book.
• S. Thrun, “Learning Occupancy Grid Maps with Forward Sensor Models”, Autonomous Robots 15 (2), 2003. Paid journal article.
• C. Stachniss, “Occupancy Grid Maps” (video lecture) . Free to watch.
• T. D. Barfoot, State Estimation for Robotics, 2nd edition, 2024 . Free to read as the author’s PDF; the book is copyrighted.

Knowledge check

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

What’s next

So far the poses were known. The last lesson of the module asks what happens when they are not: the map smears, and the way to measure and correct that leads to the pose graphs of Module 11.

Related content

Nothing below is required to finish this lesson.

• Before
  M10-T1: Occupancy Grids and the Binary Bayes Filter

  Derive the log-odds update of a static binary state and explain the independence assumptions of an occupancy grid.

• Lab
  M11-L1: Occupancy Grid and Pose Graph SLAM

  The map of the lab has a doubled wall where the loop should close. Build the grid in log odds, find why it smears, and correct the trajectory with a pose graph before mapping again.

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

• SLAM M3-T1: Occupancy Grid Mapping
• SLAM M3-L1: Build a 2D Occupancy Grid
• Navigation M2-T1: Occupancy Grids for Planning