M3-T1 — Occupancy Grid Mapping

Learning objectives

After this lesson, you should be able to:

• State the occupancy mapping problem and its assumptions, including known robot poses.
• Derive the log-odds update and apply it to a cell over several observations.
• Trace a beam through a grid with Bresenham’s algorithm and identify free and occupied cells.
• Explain how resolution, memory, pose error and dynamic objects limit a grid map.

The problem and the intuition

Picture a sheet of graph paper laid over the floor plan. A laser beam goes out from the robot. Every square it crosses must have been empty, otherwise the light would have stopped there; the square where it stops probably has something in it. Do this thousands of times and the squares that were often crossed are free, those that were often hit are occupied, and the rest are unknown. That is occupancy grid mapping.

A grid map does not store objects. It stores, for every cell, how strongly the evidence says “empty” or “full”. Unknown is a real state.

The algorithm: occupancy by log-odds

Problem. Given the robot poses x_1:t and range scans z_1:t, estimate for each cell m_i the probability p(m_i = occupied | x_1:t, z_1:t).

Assumptions. The poses are known (this is mapping, not SLAM); the cells are independent of each other; each cell is either free or occupied and does not change over time; the sensor noise is independent between beams and scans.

The log-odds update

Multiplying probabilities from many observations is numerically awkward. In log-odds form, the Bayes update becomes an addition:

l(m_i)

log-odds of cell i being occupied. 0 means 50% (unknown); positive means more likely occupied; negative more likely free.

inv_sensor

the inverse sensor model: the log-odds contributed by one beam to the cell: l_occ for the cell at the beam end, l_free for cells the beam crossed, 0 for cells not reached.

l₀

the prior log-odds, 0 when the prior is 50%.

p_hit, p_miss

the probabilities behind the two constants: l_occ = log(p_hit/(1−p_hit)), l_free = log(p_miss/(1−p_miss)).

Pipeline

1. Take the pose x_t and the scan; convert each beam’s endpoint into world coordinates and then into cell indices.
2. Trace the beam from the sensor cell to the endpoint cell with Bresenham’s line algorithm.
3. Add l_free to every cell on the ray except the last, and l_occ to the last cell (only if the beam hit something, that is, the range is below the sensor’s maximum).
4. Clamp each l to a range such as [−5, 5] so that the map can still change if the world changes.
5. Convert to probabilities when the map is used: p = 1 / (1 + e^(−l)). Typical thresholds: occupied above 0.65, free below 0.35, unknown in between.

Strengths and limitations

A worked example: one cell, several beams

Take p_hit = 0.7 and p_miss = 0.4 (so a hit says “probably occupied” and a pass-through says “probably free”). Then l_occ = log(0.7/0.3) = +0.847 and l_free = log(0.4/0.6) = −0.405. A fresh cell starts at l = 0 (p = 0.5).

1. One hit: l = 0.847, p = 1/(1 + e^−0.847) = 0.70.
2. Two hits: l = 1.695, p = 0.845. Three hits: l = 2.542, p = 0.927. The evidence accumulates by simple addition.
3. A contradicting pass-through (the cell was also crossed by a beam that went through it): after hit, hit, miss l = 0.847 + 0.847 − 0.405 = 1.289, p = 0.784. One contradiction lowers confidence but does not erase two hits.
4. Bresenham. A beam from cell (0, 0) to cell (5, 2): the line rises 2 cells over 5 columns, so the cells along it are (0,0), (1,0), (2,1), (3,1), (4,2), (5,2). The first five receive l_free and the last l_occ.
5. Clamping. With limits ±5, a cell hit 20 times sits at 5 (p = 0.993) rather than 17. If the object moves, about 12 contradicting beams (5 / 0.405) are enough to flip the cell to free, instead of 42.

Note what the example does not need: any knowledge of what the object is, or even whether the same object caused each hit.

Engineering implications and limitations

Engineering implications

• Choose the resolution to match the sensor and the task. A cell smaller than the sensor noise adds memory without information; a cell larger than the robot’s clearance hides doorways. 5 cm is common indoors.
• Sparse or tiled storage is necessary for large maps: allocate blocks only where beams have been, and keep submaps (Module 5) so that a global correction does not need rewriting the whole grid.
• Apply the update in the right order. Cells near the end of a beam are affected by the range noise: some systems update a small neighbourhood of the endpoint, or lower l_free near the hit.
• Use good poses. The map blurs by exactly the pose error. A 5 cm drift turns a 5 cm resolution map into one with walls two cells thick. Scan matching (M3-T4) before updating keeps the walls sharp.
• Handle dynamic objects. Clamped log-odds lets the map recover, but a person standing still for ten seconds becomes a wall. Filter dynamic returns (Module 8) or keep a separate short-term layer for the planner.

Limits

Occupancy grids are a good map for planning and a poor one for recognising places or for optimisation: a grid has no compact features to match. They assume independence of cells, which is false for walls (neighbouring cells are strongly related) and a source of over-confidence. 3D versions (voxels, OctoMap) pay a steep memory price.

Common misconceptions

Engineering takeaways

1. An occupancy grid keeps one log-odds value per cell and updates it by addition: l_free along the beam, l_occ at the hit.
2. Bresenham’s algorithm gives the cells a beam passes through; cells behind the hit are not updated.
3. Clamping the log-odds keeps the map adaptable; the thresholds 0.35 and 0.65 give free, unknown and occupied.
4. The map is only as sharp as the poses it was built with: pose error turns into wall thickness.
5. Resolution, memory and dynamic objects decide whether a grid is practical.

References and further reading

Established fundamentals. Learned and neural map representations are covered in Module 8.

• Moravec, H. and Elfes, A. (1985). High resolution maps from wide angle sonar. IEEE International Conference on Robotics and Automation: the original occupancy grid paper.
• Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation. Computer 22(6).
• Thrun, S., Burgard, W. and Fox, D. (2005). Probabilistic Robotics. MIT Press, chapter 9: occupancy grid mapping with the log-odds formulation.
• Hornung, A. et al. (2013). OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots 34(3).
• Bresenham, J. E. (1965). Algorithm for computer control of a digital plotter. IBM Systems Journal 4(1).

Knowledge check

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

What’s next

A grid is one kind of map. Next, maps made of explicit landmarks, with a covariance for each.

Related content

Nothing below is required to finish this lesson. The last 2 entries are lessons of other courses on this site that teach the background or go further.

• Before
  M2-T7: Data Association

  Match observations to landmarks with nearest neighbour, Mahalanobis gating and joint compatibility, and see how wrong matches break estimates.

• Lesson
  M5-T11: Dense Map Representations

  Compare occupancy octrees, signed distance fields and surfels, fuse range measurements into a TSDF, and say what a loop closure does to a dense map.

• Lab
  M3-L1: Build a 2D Occupancy Grid

  Turn known-pose range scans into an occupancy grid with a log-odds update and ray tracing.

• Probability
  Occupancy Grids and the Binary Bayes Filter

  The log-odds update derived from the binary Bayes filter.

• Probability
  Inverse Sensor Models

  How a range measurement becomes an occupancy update.