Section 28.4: Occupancy grids and voxel maps

"An occupancy grid does not ask what an object is, only whether the space ahead is safe to enter."

A Patient Embodied AI Agent

Problem First: Why This Representation Exists

A robot moving through a warehouse aisle must answer one question faster than it is traveling: "is the next meter of space safe to enter?" Point clouds give dense geometry but no persistent memory. Camera images give texture but no direct answer about occupancy. A planner needs a structure it can query cell-by-cell in microseconds, one that accumulates evidence across many sensor sweeps rather than discarding it, and one that distinguishes "confirmed free," "confirmed occupied," and "never seen" as three distinct answers. Occupancy grids and voxel maps exist specifically to provide that structure. The log-odds update rule accumulates this evidence, resolution and decay parameters trade against a latency budget, and the resulting three-state map (free, occupied, unknown) feeds a cost-map planner. As Figure 28.4A illustrates, the central discipline is that unknown space is never silently treated as free.

For occupancy and voxel maps, track resolution, decay, inflation, unknown-space policy, and update latency. The robot evidence is not map beauty; it is whether the planner used the map to avoid collision or request exploration.

For occupancy and voxel maps, track resolution, decay, inflation, unknown-space policy, and update latency. The robot evidence is not map beauty; it is whether the planner used the map to avoid collision or request exploration. Treat the representation as a typed state estimate, not as a visualization.

Each of these five terms is defined in the order it is used below: the log-odds update and resolution tradeoffs come first under Mathematical Core, inflation and decay follow once the update rule is in place, and unknown-space policy and update latency close out the section once both a representation and a forgetting mechanism exist to apply a policy to.

Figure 28.4.2 shows the ray traversal itself: the sensor cell, the free cells it passes through, the occupied hit cell, and the surrounding unknown cells that remain unlabeled. Figure 28.4.1, immediately below, should be read as the Occupancy grids and voxel maps handoff diagram: the ray, the free cells before the hit, the hit cell, the surrounding unknown space, and the planner that consumes the cost map are each separate failure points.

Mathematical Core

Occupancy mapping usually updates log odds so repeated evidence accumulates without probabilities saturating too quickly.

The log-odds value \(\ell_t\) increases for occupied evidence and decreases for free-space evidence. This distinction enforces the three-state epistemic contract: unknown is not free; it is a separate epistemic state that planners should treat according to task risk.

What happens when a planner's map says "clear" but the robot's shoulder clips a shelf at full speed? The answer is almost always the same: the map treated the robot as a point mass with no physical width. A map that knows the space but not the body navigating it is geometry without consequence.

Inflation matters because a planner that treats the robot as a point mass will route it through gaps it cannot physically fit through. A real robot occupies volume. Every cell within one body-radius of an obstacle must be marked forbidden before the path search begins. Without inflation, the planned path may graze a wall or shelf by centimeters, leaving no margin for localization error or wheel slip. The consequence on hardware is contact: not a planning artifact but a physical collision. Inflation turns a geometry measurement into a reachability constraint that accounts for body size.

How inflation is computed

Mechanically, inflation is a morphological dilation, where the obstacle region is grown outward by a fixed radius rather than resized or reshaped: the planner convolves the binary obstacle layer with a disc (2D) or sphere (3D) sized to the robot's largest cross-section, marking every cell within that radius of an obstacle as forbidden or high-cost. ROS 2 Nav2 ships this as the inflation layer plugin, where inflation_radius sets the hard-stop boundary and cost_scaling_factor tunes how cost decays past it (this is a spatial cost falloff with distance from the obstacle, unrelated to the time-based log-odds decay discussed later). The decay gives the optimizer a gradient that pulls paths away from obstacles rather than merely skirting them.

Clamping tunes how a single representation forgets; the next decision is which representation to reach for in the first place.

Clamping is not the only forgetting mechanism promised above: a separate decay policy periodically nudges every cell's log-odds back toward zero (unknown) on a fixed schedule, independent of new evidence, so that a cell nobody has re-observed in, say, 30 seconds gradually loses certainty rather than staying frozen at whatever value the last sweep produced. Clamping bounds how confident a cell can become from repeated evidence; decay bounds how long that confidence persists without fresh evidence. Systems tracking moving obstacles typically need both.

Worked Miniature

Having chosen a resolution that fits the latency budget, the next step is to see the update rule that fills each of those cells in action.

Code Fragment 28.4.1 performs a tiny log-odds update for free and occupied cells along one range ray. The same idea powers larger occupancy and voxel maps.

# Apply one log-odds occupancy update along a range ray.
# Free cells decrease, the hit cell increases, and unknown cells remain unchanged.
import numpy as np

log_odds = np.zeros(6)
free_cells = [0, 1, 2, 3]
hit_cell = 4
log_odds[free_cells] += -0.4
log_odds[hit_cell] += 0.9
prob = 1 / (1 + np.exp(-log_odds))
print(np.round(prob, 2))

The expected output shows cells 1 through 4 moving toward free space, cell 5 accumulating occupied evidence, and cell 6 staying unknown at 0.50. A planner should therefore interpret this vector as "one likely obstacle, several cleared cells, and one unobserved cell," not as a complete map.

Consider a representative case, illustrative rather than a documented vendor specification: a legged robot such as the Boston Dynamics Spot navigating a construction site might reasonably use OctoMap at 5 cm resolution. Each LiDAR sweep would cast on the order of 100,000 rays; free cells along each ray receive a log-odds decrement of about 0.4 and the hit cell receives an increment of 0.9, matching the Code Fragment values above. After three consistent sweeps a hit cell reaches probability 0.88, which crosses a typical planner's obstacle threshold. The inflation layer then expands that cell by the robot's shoulder width (roughly 0.5 m for a quadruped this size) before passing the cost map to the navigation stack. A pipeline built this way would need to run end-to-end in well under 100 ms to stay inside the latency budget for safe walking speed; whether a specific implementation hits that budget depends on the CPU, point count, and voxel count actually deployed.

Debugging And Evaluation

Evaluate the representation inside the consuming action loop with calibration, frame transform, representation version, latency, selected action, and failure label.

Perturb exactly one geometric assumption, such as depth dropout, scale, occlusion, pose drift, motion, or calibration, then record the action change.