Occupancy Grid Mapping: The Map Representation That Works
The log-odds representation is not a design choice — it is numerical necessity; linear probability updates underflow in 32-bit floats before a wall has 10 LIDAR returns.
🎯 By the end you'll understand
Why Bayesian occupancy estimation, not simple counting, is the right framework for grid mapping. How log-odds emerges from the Bayes filter update and why it is numerically stable where linear probabilities are not. How ray casting fills cells from a single LIDAR scan. The resolution–memory tradeoff and why it is a systems engineering decision, not a hyperparameter. How the inflation layer converts a raw occupancy grid into a robot-safe costmap. And the critical failure mode: a high false-positive sensor inflates phantom obstacles until no navigable path exists.
KEY INSIGHTA grid cell is a Bayes filter, not a counter
The occupancy grid is one of the most widely deployed representations in mobile robotics — and one of the most commonly misunderstood. It is not a histogram of LIDAR hits. It is a field of independent Bayes filters, each estimating whether a single square of floor is occupied.
When FollowBot's LIDAR scans a wall 50 times and each scan returns a hit at roughly the same range, the naïve approach would be to count: cell gets hit 50 times, declare it occupied. But counting ignores the sensor model. A single hit at 1.4 m from a sensor whose false-positive rate is 3% carries less certainty than 50 hits from a sensor with a 0.1% false-positive rate. More critically: if you try to maintain the probability of occupancy directly — a number between 0 and 1 — the repeated Bayesian updates multiply probabilities together and you hit floating-point underflow before the wall has received 10 scans.
Log-odds maps are not an aesthetic choice. In IEEE 754 single precision, 0.05 raised to the 45th power is exactly 0 — indistinguishable from "no information" and from "one hit." The log-odds transformation converts multiplicative Bayesian updates into additive ones, so a wall that has received 1,000 scans is still a distinguishable number, not a float underflow. The representation was forced by arithmetic, not by design preference.
CORE CONCEPTDeriving log-odds from the Bayes filter
Let O denote the event "cell is occupied" and z a sensor measurement. We want to maintain a belief P(O | z1:t) — the probability of occupancy given all measurements up to time t. Each cell is treated as independent, so we can update it one scan at a time.
Let us be concrete. Define:
- l(O) — the log-odds value stored for a cell (a signed real number, initialized to 0)
- l_occ = log(Phit / (1 − Phit)) — the increment when a ray terminates at this cell (measurement: occupied)
- l_free = log(Pmiss / (1 − Pmiss)) — the decrement when a ray passes through this cell (measurement: free)
For a typical LIDAR with Phit = 0.9 and Pmiss = 0.35: l_occ ≈ +2.20, l_free ≈ −0.62. A cell directly behind a confirmed wall receives l_free for each scan that would have measured through it if the wall were absent — but since the ray terminates earlier, it receives neither l_occ nor l_free (the wall occludes it). This is the ray-casting geometry, derived in the next section.
Mathematically, maintaining log-odds l is strictly equivalent to maintaining probability P = 1 − 1/(1 + exp(l)). The difference is numerical. After 45 measurements with l_free ≈ −0.62, the stored value is about −27.9 — a perfectly representable 32-bit float. The equivalent probability is 8×10−13, which rounds to exactly 0.0 in single precision. Once a linear-probability cell bottoms out at 0, subsequent measurements have no effect: the cell is permanently free, even if the sensor was wrong. Log-odds cells do not bottom out; they just become very negative, and they can be reversed by subsequent hits.
CORE CONCEPTThe numerical stability argument, made exact
This is not a theoretical concern. Here is the timeline for a standard 2D LIDAR with 0.7° angular resolution mapping a wall 5 m away, with Phit = 0.9 and Pmiss = 0.35:
| After N scans (hit each time) | Log-odds value | True probability P | float32 representation of P | Status |
|---|---|---|---|---|
| 1 | +2.20 | 0.900 | 0.900 (exact) | Fine |
| 5 | +11.0 | 0.9999 | 0.9999 (ok) | Fine |
| 10 | +22.0 | ~0.999999997 | 1.0 (clamped) | Linear P saturated — no new info |
| 50 | +110 | ~1 − 10−48 | 1.0 (still clamped) | Linear still stuck; log still moving |
| After clamping at l=10 | +10 | 0.99995 | 0.99995 | Clamped log-odds is safe |
The critical row is N=10 in the linear column. After just 10 consistent LIDAR hits, a linear probability representation loses all ability to distinguish "pretty confident" from "extremely confident." More importantly: if the 11th scan returns free for that cell (the sensor had a transient miss), the update P_new = P_miss × P_old / normalizer is multiplied against 1.0 — the result is always 1.0 regardless of the free reading. The cell is locked. Log-odds does not have this problem: the 11th scan would subtract l_free from +22, pulling the value toward uncertainty. The representation is reversible.
While log-odds avoids underflow, it can grow without bound if you allow it. A wall that has received 10,000 LIDAR hits has a log-odds of +22,000. Recovering the probability from exp(22000) overflows a float. The standard practice is to clamp l to [l_min, l_max], typically [−10, 10], which corresponds to probabilities in [0.00005, 0.99995]. nav2's costmap2d uses l_min = −2, l_max = 3.5 by default — a more aggressive clamp that prioritizes responsiveness over long-memory certainty.
HOW IT WORKSRay casting: from one LIDAR scan to grid updates
A single LIDAR scan returns 360 (or 512 or 1080) range values, one per angular step. For each ray, the grid update involves two distinct operations: marking cells along the ray as free (the laser passed through them unobstructed) and marking the endpoint cell as occupied (the laser hit something there).
The standard algorithm for tracing which cells a ray passes through is Bresenham's line algorithm, adapted to grid coordinates. It runs in O(n) where n is the ray length divided by cell size — exactly one cell visited per grid step. For a 10 m ray at 5 cm cell resolution, that is 200 cells per ray, 360 rays per scan, at 10 Hz: 720,000 cell updates per second. This is the dominant computational cost of occupancy grid mapping, and it is why the SLAM Toolbox in ROS 2 performs ray casting in C++ with explicit SIMD vectorization, not Python.
import numpy as np # Sensor model constants (tune to your LIDAR's datasheet) L_OCC = 2.197 # log(0.9/0.1) — cell likely occupied L_FREE = -0.619 # log(0.35/0.65) — cell likely free L_MIN = -10.0 # clamp floor ≈ P = 0.00005 L_MAX = 10.0 # clamp ceiling ≈ P = 0.99995 def update_cell_hit(l_prev: float) -> float: """Ray terminates here — occupied measurement.""" return np.clip(l_prev + L_OCC, L_MIN, L_MAX) def update_cell_free(l_prev: float) -> float: """Ray passes through — free measurement.""" return np.clip(l_prev + L_FREE, L_MIN, L_MAX) def log_odds_to_prob(l: float) -> float: """Recover probability from log-odds.""" return 1.0 - 1.0 / (1.0 + np.exp(l)) # Bresenham ray cast (simplified — see SLAM Toolbox for vectorized version) def cast_ray(grid, sensor_xy, endpoint_xy, cell_size): x0, y0 = [int(v / cell_size) for v in sensor_xy] x1, y1 = [int(v / cell_size) for v in endpoint_xy] for cx, cy in bresenham_cells(x0, y0, x1, y1)[:-1]: grid[cy, cx] = update_cell_free(grid[cy, cx]) # free cells along ray grid[y1, x1] = update_cell_hit(grid[y1, x1]) # occupied at endpoint return grid
Three things to notice. First, L_OCC is positive and L_FREE is negative — consistent with the probabilistic interpretation that l > 0 means more likely occupied. Second, the free update is applied to all cells except the endpoint — the Bresenham slice [:-1] skips it. Third, the endpoint gets the hit update regardless of whether the previous update was free or occupied — each measurement is independent.
SEE ITLog-odds ray-caster
Fire simulated LIDAR rays into a 2D occupancy grid. Adjust sensor range and noise, then watch log-odds cells evolve. After accumulating hits, compare what log-odds stores versus what a linear-probability representation would compute. Toggle the inflation radius to see how it reshapes the navigable corridor for FollowBot.
COMPARISONGrid resolution vs. memory: a systems engineering decision
Every occupancy grid has a resolution parameter — the edge length of one cell. This is not a hyperparameter to be searched; it is a systems engineering decision with hard consequences in both directions.
| Cell size | Grid for 20×20 m map | Memory (float32 per cell) | Min. representable obstacle | Typical use case |
|---|---|---|---|---|
| 5 cm | 400×400 = 160,000 cells | 640 KB | 5 cm (too fine for most LIDARs) | Arm workspace, close-range navigation |
| 10 cm (nav2 default) | 200×200 = 40,000 cells | 160 KB | 10 cm (matches RPLIDAR A2 accuracy) | Indoor mobile robot navigation |
| 20 cm | 100×100 = 10,000 cells | 40 KB | 20 cm (misses narrow obstacles) | Low-compute embedded systems |
| 50 cm | 40×40 = 1,600 cells | 6.4 KB | 50 cm (misses chairs, thin walls) | Rough outdoor terrain only |
The right column reveals the real constraint: cell resolution should match the sensor's range accuracy. The RPLIDAR A2 on FollowBot has a range accuracy of ±2 cm at short range. Using 5 cm cells would imply a false precision that does not exist in the measurements. Using 20 cm cells would cause two adjacent walls 15 cm apart (a narrow doorframe edge) to be merged into one obstacle cell, making the gap appear larger or smaller than it is. 10 cm is the right choice for FollowBot's RPLIDAR A2 in indoor environments — not by convention, but by matching sensor resolution to cell size.
nav2 supports two costmap modes: a static map (loaded once from a YAML/PGM file, usually built by SLAM offline) and a rolling costmap that follows the robot and updates in real time. For FollowBot, the rolling local costmap (typically 4×4 m centered on the robot, 10 cm resolution) handles dynamic obstacles like moving people. The global static map (full room, built by SLAM Toolbox) is used for path planning. They are separate ROS 2 nodes with separate update rates and separate log-odds grids.
HOW IT WORKSThe inflation layer: from raw grid to robot-safe costmap
A raw occupancy grid tells you where obstacles are. It does not tell you where a robot of finite size cannot go. That translation is the inflation layer's job, and it is not optional — without it, the planner would route FollowBot's center point within 2 cm of a wall, which cannot be executed by a robot with a 25 cm body radius.
In nav2's costmap2d, the inflation layer assigns a cost value to every cell within the inflation radius of an occupied cell. The cost decays exponentially with distance from the nearest obstacle. The planner avoids high-cost cells not because they are physically impassable but because the path cost through them is high — the gradient naturally pushes planned paths toward the center of corridors. This is correct behavior: a robot navigating close to a wall has smaller error margins and higher collision risk.
Set it too small and the planner routes FollowBot's wheel through doorframes. Set it too large and narrow corridors become geometrically infeasible in the costmap — the inflated zones of opposite walls overlap, and the planner returns "no path found" even though a human could walk through. For FollowBot with a 25 cm inscribed radius in a building with 80 cm doorways, the maximum safe inflation radius is (80 cm − 25 cm) / 2 ≈ 27 cm. Any larger and a centered doorway path is infeasible. The SPEC uses 30 cm as a starting point — barely below the limit, so edge cases in localization will cause path failures through tight doors.
local_costmap:
local_costmap:
ros__parameters:
width: 4
height: 4
resolution: 0.10 # 10 cm — matches RPLIDAR A2 accuracy
robot_radius: 0.25 # FollowBot inscribed radius (m)
plugins: ["obstacle_layer", "inflation_layer"]
inflation_layer:
plugin: "nav2_costmap_2d::InflationLayer"
inflation_radius: 0.30 # < (doorway_width - robot_diameter)/2
cost_scaling_factor: 3.5 # exponential decay rate
obstacle_layer:
plugin: "nav2_costmap_2d::ObstacleLayer"
observation_sources: scan
scan:
topic: /scan
max_obstacle_height: 2.0
clearing: True # ray cast to clear free space
marking: True # mark occupied endpoints
FOLLOWBOTSLAM Toolbox, grid inflation, and the Stage 5 milestone
At this point in FollowBot's build, the occupancy grid is not just a map — it is the handoff artifact between perception (Stage 5) and navigation (Stage 6). SLAM Toolbox has been building a map of the test environment in real time; this lesson's algorithms are what give that map its semantics.
SLAM Toolbox occupancy grid
SLAM Toolbox (in Lifelong Mapping mode) maintains its internal representation as a graph of scan-matched poses, but publishes a standard nav_msgs/OccupancyGrid on /map at 1 Hz. Each cell contains an integer in [0, 100] (0 = free, 100 = occupied, −1 = unknown), which is a quantized probability — not log-odds. The internal representation uses log-odds for numerical stability; the topic output is converted for ROS 2 compatibility. When you save the map with ros2 run nav2_map_server map_saver_cli -f room_map, you get a PGM image and a YAML header.
Configuring the inflation layer for FollowBot's test environment
FollowBot's test environment has a 0.82 m doorway — the narrowest corridor. With a 25 cm inscribed radius and 30 cm inflation radius, the inflated corridor width is 0.82 − 2×0.30 = 0.22 m — technically navigable but extremely tight. Verify by loading the saved map in RViz with the costmap overlay: you should see the doorway corridor as a thin blue strip, not a fully inflated dead zone. If it shows zero-width, reduce inflation_radius to 0.25 m and accept tighter tolerances on localization accuracy.
Stage 5 milestone verification
The milestone is satisfied when: (a) SLAM Toolbox is producing a map with identifiable room boundaries; (b) ros2 topic hz /map reports ~1 Hz; (c) the occupancy grid loaded in RViz shows walls as black, known free space as white, and unmapped areas as grey; (d) the inflation layer overlay (enable in RViz via CostmapDisplay) shows a non-zero but finite corridor through every doorway the robot must traverse; (e) ros2 topic echo /map --once | grep "resolution" confirms 0.10 m resolution.
Camera intrinsics calibrated (reprojection error < 0.5 px). LIDAR-camera extrinsic calibrated with validated residual. YOLOv8 person detection running at 10 Hz on ROS 2. LIDAR cluster + camera bbox fusion producing stable 3D person position. SLAM Toolbox building an occupancy map. Occupancy grid inflated and ready for nav2 path planning. The FollowBot perception stack is complete — Stage 6 will wire it to the planner and controller.
One subtlety worth flagging: SLAM Toolbox's map and nav2's local costmap are different objects. SLAM builds the global map from all accumulated scans, starting from the first pose. The local costmap uses only recent scans (within the LIDAR's range, centered on the current robot position) and updates every scan cycle. Dynamic obstacles — a person walking through — appear in the local costmap but not in the SLAM global map. Navigation in nav2 uses both: the global planner uses the global (static) map, the local planner uses the local (rolling) costmap. The inflation layer is applied to both, but with potentially different inflation radii.
WEAKNESSWhere the occupancy grid bites
This is the critical failure mode flagged in the brief, and it is worth dwelling on. A sensor with a high false-positive rate fires hits in empty space. Each false hit increments the log-odds of a cell that is actually free. After enough false hits, the cell crosses the occupied threshold. Once enough cells are "occupied" by phantom obstacles, the inflation layer spreads the damage further — a single phantom hit inflates a 0.35 m radius around it. In a narrow corridor, two opposing phantom hits can render the entire corridor impassable in the costmap, even though the robot could physically drive through. The symptom in the field: the planner repeatedly returns "no path found" in a room the robot has been navigating fine. The fix is at the sensor layer (range gating, minimum hit count threshold, confidence filtering) not at the map layer. Attempting to fix phantom obstacles by adjusting the inflation radius will succeed temporarily and hide the underlying sensor problem.
The occupancy grid model assumes each cell is spatially independent. This is physically false — if a cell is occupied, its neighbors are more likely to be occupied (walls are continuous). The independence assumption causes the model to undercount uncertainty in structured environments. In practice, this is tolerable: the map still works. Where it bites is in the sensor model. If your LIDAR has specular reflections (glass, mirrors, polished floors), a single reflection can cause a cluster of false hits across several adjacent cells simultaneously. Because the model treats them as independent, it integrates each as a fresh measurement rather than as correlated noise from a single event. The fix is multi-return filtering and reflectivity masking at the LIDAR driver level, before any hits reach the occupancy grid.
A SLAM map is a snapshot of the environment as it was while the robot built it. If a cardboard box is moved between mapping and navigation, the map shows the box as occupied and the now-clear space as uncertain. The nav2 obstacle layer with clearing: True partially mitigates this: rays passing through a previously-occupied cell can clear it back to free. But the clearing only works within the LIDAR's range and only if the robot is in a position to sense the cleared area. A moved obstacle behind the robot — out of sensor coverage — will remain "occupied" in the local costmap until the robot reorients. This is not a bug in occupancy grids; it is a fundamental limitation of any map-based representation. The solution is to treat the local rolling costmap as ground truth for near-field obstacles and the global static map as prior-only for far-field planning.
KEY INSIGHTHow it connects
- 4.2 · The Bayes Filter and the Predict-Update Cycle — the mathematical foundation used directly in this lesson. The log-odds update rule is the Bayes filter applied cell by cell; the measurement model P(z|O) is a specialization of the Bayes filter observation model. If the Bayes filter derivation felt abstract there, this lesson makes it concrete: every grid cell is one instance of it running independently.
- 1.6 · Sensors: Physics, Noise Models, and Failure Modes — the false-positive rate used in l_free, the specular reflection failure mode, and the RPLIDAR A2 range accuracy that dictates 10 cm cell resolution all originate here. The sensor model is the only place where real-world physics enters the occupancy grid; getting P_hit and P_miss from the sensor's datasheet rather than guessing is the difference between a working map and a phantom-obstacle problem.
- 5.3 · LIDAR Point Cloud Processing: From Scan to Structure — the pre-processing stage that produces the clean scan that ray casting operates on. Clustering, outlier rejection, and intensity filtering happen before the occupancy update. A dirty scan input makes a dirty map; the garbage-in-garbage-out principle applies directly.
- 5.8 · Scan Matching and ICP: LIDAR-Based Pose Estimation → — the next lesson in this stage. Accurate occupancy mapping requires accurate robot poses; scan matching provides the pose correction that prevents map smearing. The two algorithms (occupancy update and scan matching) are coupled in SLAM Toolbox's real-time loop.
GLOSSARYKey terms
- Occupancy grid
- A discrete 2D (or 3D) representation of an environment where each cell stores the probability (or log-odds) that it is occupied by an obstacle. Each cell is modeled as an independent Bayes filter. The standard map representation in mobile robotics and the format used by nav2's costmap server.
- Log-odds
- The logarithm of the odds ratio P(O) / (1 − P(O)). Transforms Bayesian multiplicative probability updates into additive operations, avoiding floating-point underflow. A cell with l = 0 is at 50% occupancy probability; l = +10 ≈ P = 0.99995; l = −10 ≈ P = 0.00005.
- Ray casting
- The process of tracing a LIDAR ray through the occupancy grid cell by cell (using Bresenham's line algorithm) to update cells along the ray as free and the endpoint cell as occupied. The dominant computational cost in real-time occupancy mapping.
- Inverse sensor model
- The probability P(cell occupied | measurement z) — the mapping from a sensor reading to a belief about which cells are occupied. Also written P(O | z). Together with l_occ and l_free, it is the design document for how the sensor populates the occupancy grid.
- Inflation layer
- A post-processing layer in nav2's costmap2d that expands each occupied cell outward by the robot's inscribed radius (lethal zone) plus a safety margin, assigning exponentially decaying costs. Converts a geometric map into a robot-safe costmap that the path planner can use directly.
- Inscribed radius
- The radius of the largest circle that fits entirely within the robot's footprint. For a cylindrical robot like FollowBot's base, it equals the physical radius (0.25 m). The lethal zone extends this radius around each obstacle; the robot center cannot enter the lethal zone without guaranteed collision.
- Clearing (ray cast clearing)
- The costmap operation in which a LIDAR ray passing through a previously-marked-occupied cell resets that cell to free. Enables the local costmap to respond to dynamic environments: obstacles that disappear from the sensor's view are eventually cleared back to free space.
- Lifelong mapping (SLAM Toolbox mode)
- A SLAM operating mode in which the map is never frozen — new observations continuously update old regions. Contrast with "localization only" mode where the map is fixed and only the robot pose is estimated. Lifelong mapping is appropriate when the environment changes slowly; it requires careful management of map memory to prevent unbounded growth.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1Why does a linear probability representation underflow before a wall has received 10 LIDAR hits, and what specific arithmetic property of log-odds prevents this?›
Repeated Bayesian probability updates multiply together: P_new = P(z|O) × P_old / normalizer. When P_old is close to 1 after several consistent hits, the free-space probability 1 − P_old becomes a very small number. In IEEE 754 single precision, numbers smaller than about 1.2×10−38 underflow to 0. With P_miss ≈ 0.35, the probability that a cell is free drops below this threshold after roughly 8–10 consistent occupied measurements. Once it hits 0, the cell is frozen — no amount of contradicting evidence can pull it back toward uncertainty. Log-odds converts the multiplication to addition: l_new = l_old + l_occ. Each update just adds a constant. After 10 updates, the log-odds is +22 — a perfectly representable float. After 1,000 updates with clamping, it is +10 — still representing a very high but reversible belief. The arithmetic property is the log transform turning products into sums: log(A × B) = log(A) + log(B).
2A cell lies directly along a LIDAR ray 2 m from the sensor, but the ray terminates at a wall 1.8 m away. What log-odds updates, if any, does the 2 m cell receive from this scan?›
None. The ray casting algorithm (Bresenham's line) traces cells from the sensor origin to the endpoint at 1.8 m and stops. It marks the endpoint cell as occupied (adds l_occ). It marks all cells along the ray from 0 to 1.8 m as free (adds l_free). The cell at 2 m lies beyond the endpoint and is occluded by the wall. Because the sensor cannot see through the wall, it provides no information about what is beyond it. The 2 m cell's log-odds is unchanged — it remains at whatever value it had before this scan. Over time, as the robot moves to new positions where that cell is no longer occluded, it will receive measurements and update. This is why occupancy maps built from a single robot position leave "shadow" regions of unknown cells behind every obstacle.
3FollowBot's planner returns "no path found" when approaching a doorway it has traversed successfully before. You check the global map and the doorway appears clear. What is the most likely cause and how do you diagnose it?›
The most likely cause is the local costmap's inflation layer blocking the doorway, not the global map. The local costmap is updated in real time from recent LIDAR scans and may have acquired phantom obstacles from a high false-positive measurement, a reflective surface near the doorway, or a person standing briefly in the corridor. The inflation layer then expands these phantom hits across the entire corridor width, making it geometrically infeasible. Diagnose by: (1) enabling the local costmap display in RViz and checking whether the doorway shows as inflated; (2) checking ros2 topic echo /local_costmap/costmap for cells with value 254 (lethal) or 253 (inflated lethal) in the doorway region; (3) watching whether the blockage clears after a few seconds as the ray-casting clearing operation removes transient phantom hits. If it persists, investigate the LIDAR scan for false positives in that angular region.
4You are choosing the cell resolution for FollowBot's occupancy grid. The RPLIDAR A2 has a range accuracy of ±2 cm and an angular resolution of 0.9°. You are mapping corridors as narrow as 0.8 m. What cell size do you choose and why — specifically, why not 5 cm, and why not 20 cm?›
10 cm is the right choice. The RPLIDAR A2's ±2 cm range accuracy means the true wall position is known only to ±2 cm — using 5 cm cells would imply a spatial precision (2 cm per cell) that does not exist in the measurements. The localization error would cause the same wall to map to different cells across scans, creating a smeared or doubled wall boundary. This is false precision, not useful information. 20 cm is too coarse because at 0.9° angular resolution and 5 m range, the LIDAR beam footprint at 4 m range is about 6 cm — a 20 cm cell would merge two distinct objects separated by 10–15 cm into one occupied cell, losing the fine-structure of narrow gaps. Additionally, in a 0.8 m corridor with 20 cm cells, the corridor is only 4 cells wide. With a robot radius of 25 cm and inflation radius of 30 cm, the inflated corridor would be 0.8 − 2×0.3 = 0.2 m = 1 cell wide — one cell of navigable space, with no error tolerance for localization uncertainty. 10 cm gives 8 cells across the corridor, with 2 cells navigable after inflation — tight but functional.