explainer
Occupancy grid mapping: update free, occupied, and unknown space
Build a small occupancy grid from supplied range readings. Follow free-space and hit updates, calculate log odds, and distinguish unseen cells from conflicting evidence.
What you will learn
- Trace the free cells and hit cell associated with a supplied range observation.
- Update a cell using log odds and subtract the prior term correctly.
- Distinguish an unseen cell from a cell with conflicting evidence.
- Explain the limits of repeated evidence and probability clamps.
- Separate occupancy probability from navigation cost.
Before you start
A range return gives evidence about both the surface it hits and the space before it. An occupancy grid stores that evidence as a probability for each cell. Space behind the return can remain unknown.
Build a small grid below, then inspect how each observation changes one cell. The example uses supplied sensor poses and synthetic readings so every update can be checked by hand.
Represent occupancy one cell at a time
Let mᵢ be a binary variable: cell i is occupied or free under the map's definition. Store pᵢ = P(mᵢ = occupied | observations, poses). A value of 0.7 assigns 70% probability to occupancy; it does not mean that an obstacle fills 70% of the cell's area.
Alberto Elfes's original occupancy-grid paper describes a spatial grid of occupancy estimates updated from sensor readings. Cell size sets the map's spatial detail. A small object and a large object can both make a cell occupied under a chosen mapping rule.
Our grid contains 7 columns × 5 rows of 1 m × 1 m cells. Each starts with occupancy probability 0.5 and zero observations. This neutral prior is a teaching choice; it does not make unseen space safe to enter.
Place each beam using a known pose
The lab supplies each sensor's position and beam direction in one world frame. Column x and row y identify a cell whose center is (x + 0.5, y + 0.5) m. The first sensor sits at (0.5, 2.5) m and measures a hit 4 m east, at (4.5, 2.5) m.
For that reading, the discrete model updates these cells:
| Cells | Interpretation | Single-reading occupancy probability |
|---|---|---|
| (1, 2), (2, 2), (3, 2) | Beam passes through them | 0.3 |
| (4, 2) | Reported hit endpoint | 0.7 |
| (5, 2), (6, 2) | Behind this return | No update |
| Cells outside the beam | No evidence from this reading | No update |
| (0, 2) | Sensor origin | No update in this example |
A real scan needs the sensor's orientation, mounting transform, timestamp, and pose. Review coordinate frames when converting a beam into map coordinates. Pose errors can place a correct range reading in the wrong cells.
This lesson assumes known poses. SLAM estimates poses and a map together; particle-filter localization estimates pose using a supplied map. The widget performs only the occupancy update.
Separate forward and inverse sensor models
A forward sensor model, p(z | m, x), describes readings z that a proposed map m and sensor pose x could produce. An inverse sensor model, p(mᵢ | z, x), assigns cell occupancy from one reading. Our grid update uses the inverse form.
Sebastian Thrun's paper on forward-model mapping reviews the common inverse-model update and explains a limitation: interpreting each cell separately loses dependencies between cells along a measurement. The lab implements that simpler approximation, with explicit parameters.
The beams are narrow, cardinal, and connect cell centers. A hit assigns 0.3 to preceding cells and 0.7 to its endpoint. A valid no-return observation assigns 0.3 through its stated clear range, including the final cell, and creates no hit cell.
These values describe a coarse inverse model, not measured sensor accuracy. The cell-wide update approximates continuous geometry. A real lidar scan model must address range limits, beam width, missed detections, and invalid readings; an invalid reading does not automatically justify clearing space.
Accumulate evidence with log odds
For probability p, define odds p/(1 − p), then take their natural logarithm:
Positive log odds favor occupancy. Negative log odds favor free space. Zero means p = 0.5.
Under the binary-filter approximation, combine the previous estimate with the single-reading inverse model:
Here p₀ is the prior used to construct the inverse model. The subtraction removes the prior already present in that single-reading posterior. Cells outside the observation keep their existing value.
With p₀ = 0.5, the prior term is zero. A hit adds log(0.7/0.3) = 0.847298, and free evidence adds log(0.3/0.7) = −0.847298. The lab then clamps the result to [−ln(9), ln(9)], limiting occupancy to [0.1, 0.9].
The prior subtraction matters beyond the neutral case. If p₀ = 0.4 and one reading gives p_inv = 0.8, the first update must produce 0.8. Adding both log odds without subtracting the prior would give approximately 0.727273, counting the prior twice.
Calculate two hits and one contradiction
Start cell (4, 2) at p = 0.5. The first 4 m return makes its occupancy 0.7. A second matching return multiplies its odds by 7/3 again:
A third hit would give 343/370 ≈ 0.927027 before clipping. The lab's clamp stores 0.9. That ceiling records a design decision, not proof that the cell's real occupancy probability equals 90%.
Now restart with one hit, followed by a longer 6 m hit from the same pose. The longer beam passes through cell (4, 2), adding free evidence. Its opposing log-odds increments cancel, leaving p = 0.5 with one hit and one free update.
This contradiction reduces the earlier preference for occupancy. It cannot identify its own cause: a moving object, pose error, or sensor error could all produce inconsistent ranges. Continuing evidence in one direction can eventually favor the opposite state.
Replay observations on a small grid
The map shows whole percentages for observed cells and ? for unseen cells. Select any cell to inspect its counts, log odds, and probability history. The initial display has already applied the first eastward beam.
Try these checks:
- Choose cell (5, 2) after the first beam. It stays unseen because it lies behind the hit.
- Advance Several beam directions twice. The third beam travels north and updates a column, including cell (2, 2) that the earlier eastward beams crossed.
- Apply all four beams in that sequence. The final northward no-return observation adds free evidence without an occupied endpoint.
- Choose Conflicting ranges, then advance once. Cell (4, 2) returns to 0.5 while retaining its two-observation history.
- Choose Repeated same return, then apply all beams. Its hit cell reaches 0.9 and its three free cells reach 0.1.
The plot shows the prior and every applied update for the selected cell. Both axes keep fixed limits within a sequence. Moving the replay slider recomputes that observation prefix from the prior; it does not reverse a previously clipped update.
Keep unseen cells distinct from conflicting evidence
Probability alone cannot explain how a cell reached 0.5. An untouched cell has no evidence. A cell with one balanced hit/free pair has conflicting evidence under this model.
The widget stores separate hit and free counts, so these cases remain distinguishable. Its Evidence history readout reports unseen, free-only, hit-only, or mixed evidence. Mixed history can still produce a high or low probability when one type of evidence dominates.
A planner may treat unseen space differently from observed but uncertain space. Preserve observation history or an explicit observed flag if that distinction matters to the application. Do not infer “unseen” solely from p = 0.5.
Check independence, clamps, and moving objects
Repeated additions assume more than repeated data. Nearby beams, shared pose errors, and repeated processing of the same scan can correlate the evidence. Counting each reading as fresh independent support can create unjustified certainty.
Thrun's analysis also shows why per-cell independence can fail even in a static environment: a measurement depends on several cells. Our fixed traces illustrate the update mechanics; they do not calibrate these probabilities against real outcomes.
Clamps stop confidence from growing without limit. They also discard accumulated evidence, so later contradictions can change a saturated cell quickly. Starting from the upper clamp, one free update gives 27/34 = 0.794118.
Clipping makes order matter. Four hits followed by one free update end at 0.794118 here; one free update followed by four hits ends at 0.9. Without clipping, the same set of log-odds increments would give the same final sum.
The basic map also assumes a fixed occupancy state. Moving people and opening doors violate that assumption. Practical systems can add time-dependent models or forgetting, but this lesson implements neither.
Convert occupancy into a navigation decision
Occupancy asks whether a cell contains an obstacle. A navigation cost describes how undesirable it is for the robot to use that region. Robot size, clearance, unknown-space policy, and motion constraints affect that decision.
For example, Nav2's Jazzy inflation-layer documentation describes costs that spread outward from obstacles. A cost near an obstacle can be high even when that nearby cell contains free space.
The checked Nav2 costmap example loads a saved grid and compares two inflation radii using the real costmap node. It separates source occupancy values from raw navigation costs.
A low occupancy probability also does not establish that an entire robot can fit. Connect the map to configuration space and collision checking before treating cells as traversable. This widget computes no navigation costs and certifies no path.
Reproduce the grid updates in Python
This standard-library program traces the same eastward beams and keeps independent history counts. The grid has the same dimensions, prior, inverse-model probabilities, and clamps as the widget.
from math import exp, log
WIDTH, HEIGHT = 7, 5
PRIOR, FREE, HIT = 0.5, 0.3, 0.7
LOW, HIGH = -log(9), log(9)
def logit(p):
return log(p / (1 - p))
def replay(ranges):
cells = [[logit(PRIOR), 0, 0] for _ in range(WIDTH * HEIGHT)]
# Every supplied observation starts in cell (0, 2), points east,
# and reports a hit at an integer distance in meters.
for distance in ranges:
for x in range(1, distance + 1):
cell = cells[2 * WIDTH + x]
hit = x == distance
inverse = HIT if hit else FREE
cell[0] = max(LOW, min(HIGH, cell[0] + logit(inverse) - logit(PRIOR)))
cell[2 if hit else 1] += 1
return cells
def report(name, ranges, x):
odds, frees, hits = replay(ranges)[2 * WIDTH + x]
probability = 1 / (1 + exp(-odds))
if abs(odds) < 0.0000005:
odds = 0
print(f"{name}: p={probability:.6f}, log_odds={odds:.6f}, free={frees}, hit={hits}")
report("one hit", [4], 4)
report("two hits", [4, 4], 4)
report("conflict", [4, 6], 4)
report("behind return", [4], 5)
report("eight hits", [4] * 8, 4)
report("clamp then free", [4] * 8 + [6], 4)
Output:
one hit: p=0.700000, log_odds=0.847298, free=0, hit=1
two hits: p=0.844828, log_odds=1.694596, free=0, hit=2
conflict: p=0.500000, log_odds=0.000000, free=1, hit=1
behind return: p=0.500000, log_odds=0.000000, free=0, hit=0
eight hits: p=0.900000, log_odds=2.197225, free=0, hit=8
clamp then free: p=0.794118, log_odds=1.349927, free=1, hit=8
Check two mapping decisions
Exercise 1: Separate equal probabilities with different histories. One eastward beam hits cell (4, 2). A later beam from the same pose hits cell (6, 2). What is the resulting occupancy of cell (4, 2), and how does its state differ from an untouched cell (0, 4)?
Show the update and observation histories
Cell (4, 2) receives one hit and one free update. The increments +0.847298 and −0.847298 cancel, giving p = 0.5, with hit count 1 and free count 1. Cell (0, 4) also has p = 0.5, but both counts remain zero; it is unseen.
Exercise 2: Check how a clamp changes later evidence. A cell has reached the upper log-odds bound ln(9). One free observation arrives. What probability follows, and why cannot the stored probability reveal whether three or eight earlier hits caused saturation?
Show the odds calculation and clamp limitation
The starting odds are 9. Free evidence multiplies them by 3/7, giving 27/7, so the new probability is 27/(27 + 7) = 0.794118. The clamp stores the same ln(9) after either three or eight consecutive hits; only the separate history count distinguishes them.
To inspect an occupancy grid produced by a ROS mapping node, run the SLAM Toolbox tutorial. It saves the received cells and metadata, then checks wall, obstacle, and free-space locations against its supplied scan geometry.
Sources and further study
- Alberto Elfes, Using Occupancy Grids for Mobile Robot Perception and Navigation (1989): the original grid representation, sensor interpretation, and incremental probabilistic updates.
- Sebastian Thrun, Learning Occupancy Grids with Forward Models (2001), Sections 2–3: the inverse-model log-odds rule, its independence assumptions, and the distinction from forward models.
- Nav2 Jazzy, Inflation Layer Parameters: a concrete example of navigation costs around obstacles.
Read the lidar scan model next to examine the observations that feed this map, or use Bayesian inference to review what a prior and an observation each contribute.