Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 38 ยท Localization and Mapping

Occupancy Grid Mapping

Build an occupancy grid map from range scans with ray tracing and log-odds updates. Learn the inverse sensor model, resolution trade-offs and map formats.

To plan paths, a robot needs a map. One of the most common maps is the occupancy grid: the world is cut into square cells, and each cell stores the probability that it is occupied by an obstacle. It is the map that A* searches on, that particle filters localize against, and that ROS stores in map.pgm files.

The mapping problem sounds easy when you know the robot's pose exactly: the lidar tells you what is where, so draw it. In this lesson you assume the pose is known and learn how to turn noisy range beams into a trustworthy map. The next lesson removes that assumption.

From a range beam to cell evidence

A lidar or sonar beam goes out from the robot at some angle and returns a distance r to the first thing it hit. That one number says two things:

  • Every cell along the beam before r is probably free (the beam passed through).
  • The cell at the end of the beam is probably occupied (the beam hit something).
  • Cells beyond r tell us nothing (the beam never saw them).

So each beam updates a line of cells. To find those cells we ray trace with Bresenham's line algorithm, which lists the grid cells a line crosses.

One beam, three regions

Before the hit Free space. Lower the occupancy.
At the hit Obstacle. Raise the occupancy.
Beyond Unknown. Do not touch.
1 / 2

Log-odds: why mapping uses addition

Storing a probability p per cell and applying Bayes' rule for every beam is awkward. The trick is to store log-odds: l = log(p / (1 - p)).

  • p = 0.5 (unknown) is l = 0.
  • A measurement adds a fixed amount: l += l_occ (for a hit) or l += l_free (for a pass-through), for example +0.85 and -0.4.
  • Convert back with p = 1 - 1 / (1 + exp(l)).

Independent readings simply add up, and every update is one cheap addition. Clamping l between, say, -5 and +5 stops a cell from becoming impossible to change later, so the map can adapt when a door opens or a person moves away.

Building a map from scans

Below, a robot sits at several known positions in a small room (the true world) with a wall, a box, and a corridor. It sweeps 72 beams at each stop, with noisy range readings. We start with a blank grid and fuse all the scans.

Python Occupancy grid from noisy lidar scans

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

# is occupied, . is free, ? would mark cells that were never seen, and + cells whose evidence is still weak. With eleven well-spread stops every cell is seen and the map matches the world. Remove some poses from the list and ? cells appear behind the boxes: mapping needs the robot to actually explore. Note the line that aims the hit end slightly into the wall (reach): with a beam ending exactly on a cell border, noise would sometimes mark the cell in front of the wall instead. Real mappers handle this with the sensor model and cell size.

Accumulating evidence

A single cell can be hit by a rogue reading once and passed through correctly many times. Log-odds let the good readings outvote the bad.

Python Evidence accumulating in one cell

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cell flickers on early noise but trends toward free. Choosing l_occ and l_free encodes how much you trust each kind of reading: a stronger l_occ is more eager to mark obstacles, a stronger negative l_free clears them faster.

Resolution, size and formats

  • Resolution. Typical indoor maps use 2 to 5 cm per cell. Finer is more accurate and costs memory: a 100 m by 100 m area at 5 cm is 2000 x 2000 = 4 million cells.
  • Local versus global. A global map covers the building for planning; a smaller, rolling local costmap around the robot is updated quickly for obstacle avoidance.
  • 3D. Drones and arms use OctoMap (an octree of occupied voxels) to keep 3D maps compact.
  • File format. ROS maps are a grayscale image (.pgm) plus a YAML file with resolution, origin, occupied_thresh and free_thresh. Black means occupied, white free, gray unknown.
  • Dynamic objects. People walking by leave ghost obstacles. Fast free-space clearing, or filtering moving points, keeps the map clean.

The grid assumes you know the robot's pose. If the pose estimate drifts, walls will smear and double, and the map becomes unusable. That is exactly why mapping and localization have to be solved together.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A lidar beam returns a distance of 4 m. Which cells does the update mark as free?

    The beam traveled through the cells before the hit, so they are free. The cell at the end is occupied. Cells beyond are unknown.
  2. 2. Why store log-odds instead of probabilities?

    In log-odds form, multiplying likelihoods turns into adding fixed increments.
  3. 3. What does a log-odds value of 0 mean?

    log(0.5 / 0.5) = log(1) = 0, so zero is maximum uncertainty.
  4. 4. Why clamp log-odds to a range such as -5 to 5?

    Without clamping, cells can become so certain that they need hundreds of contrary readings to flip.

Summary

  • An occupancy grid stores the probability that each cell is occupied.
  • Each beam marks cells along it as free, the end cell as occupied, and leaves the rest alone.
  • Bresenham ray tracing finds the cells; log-odds make updates additive and clamped.
  • Resolution, local versus global maps, OctoMap and the ROS .pgm + YAML format are practical choices.
  • The method requires a good pose estimate, which leads to SLAM.

Next: SLAM Explained