M10-T1 — Occupancy Grids and the Binary Bayes Filter

Learning objectives

After this lesson, you should be able to:

• Write the occupancy of a cell as a binary Bayes filter and convert it to log odds, where an update is an addition.
• Define the inverse sensor model and explain why the prior must be subtracted.
• Update a grid from a range beam: free cells along the ray, an occupied cell at its end.
• Explain clamping and how it lets the map follow a changing world.

The intuition

A range scanner fires a beam and gets a range. The beam travelled through empty space up to that range, so every cell along it is probably free; at the end, it hit something, so that cell is probably occupied. Beyond that nothing is known. Do this for hundreds of beams from many poses and the walls build up as cells that are repeatedly seen occupied, and free space as cells repeatedly seen empty.

Each reading is uncertain (the sensor can be wrong, a beam can graze a corner), so one reading only nudges the probability of a cell: from 0.5 to 0.7 for “occupied”, to 0.3 for “free”. Several agreeing readings push it further. The tool that does this exactly is Bayes' rule, and the form that makes it easy is log odds.

The left panel follows a single cell that is a closed door for 15 readings and then opens. The sensor is right 80% of the time. The log-odds sum climbs steadily while the door is closed, to a probability of 1.000 at reading 15. When the door opens, the evidence has to be un-learned reading by reading. With the limit of ±10 on the log odds (practically no limit), the probability is still 0.97 at reading 20, and falls below 0.5 only around reading 25; with a clamp at ±2 the cell recovers within five readings. Clamping is a deliberate loss of certainty to keep the map able to change.

The right panel shows a map being built. One scan from one pose sees only the walls in line of sight; 79 of the wall cells are found and 80 missed, and 881 of the 1 584 cells have never been seen. After three poses nearly all are found (7 missed). After ten, the walls are complete and no wall cell is missing.

A grid map is a collection of independent binary Bayes filters, one per cell. Independence is an approximation (a wall is a joint object) that makes the problem cheap and works well.

Definitions

Cell $m_i$

A binary variable: occupied (1) or free (0). The map is $m=\{m_i\}$.

Occupancy $p(m_i\mid z_{1:t},x_{1:t})$

The probability that the cell is occupied given all readings and poses (the poses are known here).

Log odds $\ell_i$

$\log\dfrac{p(m_i)}{1-p(m_i)}$: zero at probability ½; additive evidence.

Inverse sensor model $p(m_i\mid z_t,x_t)$

What a single reading says about a cell, from the sensor’s point of view: 0.7 for the cell at the end of the beam, 0.3 for the cells before it, and no information (0.5) for the rest.

Clamping

Limiting the log odds to $[\ell_{\mathrm{min}},\ell_{\mathrm{max}}]$ so that a cell can change its mind.

Derivation: the log-odds update from Bayes’ rule

For one cell $m$ (index dropped), apply Bayes' rule to the latest reading $z_t$, given the earlier ones.

1. $$p(m\mid z_{1:t})=\frac{p(z_t\mid m,z_{1:t-1})\,p(m\mid z_{1:t-1})}{p(z_t\mid z_{1:t-1})}$$

   Bayes’ rule with the earlier readings in the background (the Bayes filter of Module 6, for a static state).

2. $$p(z_t\mid m,z_{1:t-1})=p(z_t\mid m)$$

   Given the cell’s state, the readings are conditionally independent (the Markov assumption).

3. $$p(z_t\mid m)=\frac{p(m\mid z_t)\,p(z_t)}{p(m)}$$

   Bayes again, to express the likelihood through the inverse sensor model $p(m\mid z_t)$, which is what is easy to specify.

4. $$\frac{p(m\mid z_{1:t})}{p(\neg m\mid z_{1:t})}=\frac{p(m\mid z_t)}{1-p(m\mid z_t)}\cdot\frac{1-p(m)}{p(m)}\cdot\frac{p(m\mid z_{1:t-1})}{1-p(m\mid z_{1:t-1})}$$

   Divide the equation for $m$ by that for $\neg m$: the normaliser $p(z_t\mid z_{1:t-1})$ and $p(z_t)$ cancel. This is the odds form of Module 3, lesson 4.

5. $$\ell_t=\ell_{t-1}+\log\frac{p(m\mid z_t)}{1-p(m\mid z_t)}-\ell_0$$

   Take logarithms. Multiplication of odds becomes addition of log odds, and the prior odds are subtracted because the inverse sensor model has already included the prior once.

Why subtract the prior

With $p_0=\tfrac12$ the term vanishes. With a different prior, for example $p_0=0.2$ (most cells are free), the inverse sensor model quoted as a probability already contains the prior; without the subtraction, each reading would add the prior's odds again and the cell would drift towards 0 or 1 even with uninformative readings.

Rays through the grid

A beam from a cell $(i_0,j_0)$ to the cell $(i_1,j_1)$ where it ended passes through the cells found by a line-drawing algorithm (Bresenham). The cells before the end get the “free” reading (0.3, log odds ≈ −0.85) and the last cell the “occupied” reading (0.7, ≈ +0.85). A reading at maximum range is a miss: all its cells are free and none is occupied.

Assumptions and their cost

• Independent cells. The posterior of the whole map is taken as the product of the posteriors of the cells. Walls are correlated, so the grid cannot say “this is a wall, so its neighbours probably are too”, but this keeps the map update linear in the number of cells touched.
• Known poses. The derivation conditions on the poses. With a drifting pose estimate the walls smear (next lessons).
• Static world. The update is for a cell with a fixed state, so old evidence is never forgotten except through clamping.

Occupancy mapping is the binary Bayes filter per cell, in log odds so that fusing a reading is one addition. The clamp is not a technicality: it is the map’s memory length.

A worked example

Two programs with the library's $OccupancyGrid$.

1. One cell. The sensor says “occupied” with probability 0.8 while the door is closed (readings 1 to 15) and 0.2 afterwards. Each reading is turned into 0.7 or 0.3. The unclamped cell (±10) goes to 0.927 after 5 readings, 0.994 after 10 and 1.000 after 15. After the door opens it is still 0.967 at reading 20 and 0.300 at reading 25, as its large evidence is paid back. The cell clamped at ±2 stays at 0.881 from reading 5 to 15, and is at 0.119 by reading 20.
2. A room. A room of 10 × 8 m with a divider, a grid of 44 × 36 cells of 25 cm (1 584 cells) with 160 wall cells. A range scan has 180 beams with 5 cm noise. From one pose, 79 occupied cells lie at a wall, 10 occupied cells are more than one cell from any wall (grazing beams and noise), 80 wall cells have no occupied cell next to them, and 881 cells have never been seen. With three poses: 173 found, 1 false, 7 missed, 242 unseen. With ten: 203, 0, 0, 182.
3. The unseen cells. The 182 cells never touched by a ray after ten poses are outside the room (behind the walls), where no beam goes. Cells inside the room are all known.

import math
from robotprob import Rng, OccupancyGrid, logodds_update, logit, inv_logit

# 1. one cell: the binary Bayes filter in log odds. The cell is a closed door for 15 readings, then the door opens.
print('reading  sensor says  p(occupied), clamp +-10   p(occupied), clamp +-2')
l_a = l_b = 0.0
rng = Rng(4)
for t in range(1, 41):
    door_closed = t <= 15
    says_occ = rng.random() < (0.8 if door_closed else 0.2)         # the sensor is right 80% of the time
    p = 0.7 if says_occ else 0.3                                    # the inverse sensor model: what one reading says about the cell
    l_a = logodds_update(l_a, p, 0.0, -10.0, 10.0)
    l_b = logodds_update(l_b, p, 0.0, -2.0, 2.0)
    if t in (1, 5, 10, 15, 20, 25, 30, 40):
        print(str(t).rjust(7), str('occ' if says_occ else 'free').rjust(11), str(round(inv_logit(l_a), 3)).rjust(21), str(round(inv_logit(l_b), 3)).rjust(24))

# 2. a grid of a 10 m x 8 m room with a divider, built from a robot at known poses with 36-beam scans
SEGS = [((0, 0), (10, 0)), ((10, 0), (10, 8)), ((10, 8), (0, 8)), ((0, 8), (0, 0)), ((5, 0), (5, 4))]
ZMAX = 6.0
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

RES = 0.25
def new_grid(): return OccupancyGrid(44, 36, RES, origin=(-0.5, -0.5))
truth_occ = set()                                                   # the cells that really contain a wall
for (x1, y1), (x2, y2) in SEGS:
    n = int(max(abs(x2 - x1), abs(y2 - y1)) / 0.05)
    g0 = new_grid()
    for k in range(n + 1):
        truth_occ.add(g0.cell(x1 + (x2 - x1) * k / n, y1 + (y2 - y1) * k / n))

def build(poses, seed=5, beams=180):
    rng = Rng(seed)
    g = new_grid()
    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, 0.05)
            g.update_ray(px, py, a, max(0.1, r), ZMAX, 0.7, 0.3)
    return g

def near_wall(i, j):
    return any((i + a, j + b) in truth_occ for a in (-1, 0, 1) for b in (-1, 0, 1))

def score(g):
    P = g.probabilities()
    found = false_wall = missed = unknown = 0
    for j in range(g.h):
        for i in range(g.w):
            p = P[j][i]
            if abs(p - 0.5) < 1e-9: unknown += 1
            if p > 0.5 and near_wall(i, j): found += 1
            elif p > 0.5: false_wall += 1
    for (i, j) in truth_occ:                                        # wall cells with no occupied cell within one cell of them
        if not any(P[j + b][i + a] > 0.5 for a in (-1, 0, 1) for b in (-1, 0, 1) if g.inside(i + a, j + b)): missed += 1
    return found, false_wall, missed, unknown

print('wall cells in the true map:', len(truth_occ), '  cells in the grid:', 44 * 36)
print('poses  occupied cells at a wall  occupied cells far from walls  wall cells missed  cells never seen')
for poses in ([(2.0, 2.0)], [(2.0, 2.0), (3.0, 6.0), (7.5, 2.0)], [(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)]):
    f, fw, mi, un = score(build(poses))
    print(str(len(poses)).rjust(5), str(f).rjust(20), str(fw).rjust(30), str(mi).rjust(18), str(un).rjust(17))

reading  sensor says  p(occupied), clamp +-10   p(occupied), clamp +-2
      1        free                   0.3                      0.3
      5         occ                 0.927                    0.881
     10         occ                 0.994                    0.881
     15         occ                   1.0                    0.881
     20        free                 0.967                    0.119
     25        free                   0.3                    0.119
     30         occ                 0.033                     0.24
     40        free                   0.0                    0.119
wall cells in the true map: 160   cells in the grid: 1584
poses  occupied cells at a wall  occupied cells far from walls  wall cells missed  cells never seen
    1                   79                             10                 80               881
    3                  173                              1                  7               242
   10                  203                              0                  0               182

In robotics

The map that planners use

The 2-D occupancy grid is the standard input to global and local planners: free cells are traversable, occupied cells are obstacles, unknown cells are treated as obstacles or as risk. The Navigation course builds on this representation in its mapping and planning lessons and the SLAM course produces such maps in its occupancy-grid lessons. The Robot Learning and Perception tracks use the same cell-wise Bayes idea for depth and semantic maps.

Choosing resolution

A finer grid represents thin obstacles but costs memory (quadratic in 2-D, cubic in 3-D) and needs more readings per cell. A rule of thumb is a resolution a few times finer than the sensor noise and the smallest obstacle that matters. 3-D maps use octrees (OctoMap) to store only the occupied and known parts.

Choosing the model parameters

• p_occ and p_free (here 0.7 and 0.3): how much one reading moves a cell. Larger values converge faster and are less able to average out noise. Values come from the sensor's hit and false-alarm rates.
• Clamps: ±2 (probabilities 0.12 to 0.88) is typical for a world that changes; larger values for a static, precisely measured world.
• Free-space handling for max-range readings and for glass or absorbing surfaces, which produce no hit.

Dynamic and changing worlds

People and doors leave traces: cells marked occupied for a moving person remain so until readings say otherwise. Clamping shortens that memory; ray tracing through the cell with later readings clears it. The map is not a snapshot but a running estimate.

Common misconceptions

Key takeaways

1. An occupancy grid keeps a probability per cell, updated independently by the binary Bayes filter.
2. In log odds the update is an addition: ℓ ← ℓ + logit(p(m|z)) − ℓ₀. The prior is subtracted because the inverse sensor model includes it.
3. A range beam makes the cells along it more likely free and its end cell more likely occupied; a max-range reading makes cells free only.
4. Clamping the log odds (±2) limits the strength of evidence so that the map can change; an unclamped cell took about ten readings to unlearn after the door opened.
5. A grid fills in with the number of scans: 79 of the 160 wall cells found after one scan, 173 (with 7 missed) after three, all after ten in the example.

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, chapter 9 (occupancy grid mapping), sections 9.1 to 9.2. Paid book.
• C. Stachniss, “Occupancy Grid Maps” (video lecture) . Free to watch.
• A. Elfes, “Using Occupancy Grids for Mobile Robot Perception and Navigation”, Computer 22 (6), 1989. Paid journal article.
• 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

We have been giving the grid the probability of a cell from a single reading, by decree: 0.7 or 0.3. The next lesson looks at how that inverse sensor model is built, for laser beams, sonar cones and depth cameras, and at what goes wrong when it is wrong.

Related content

Nothing below is required to finish this lesson.

• 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