Occupancy grid

Imagine printing a satellite photo of a city on graph paper, then going through each small square and colouring it black if a building occupies it, white if it's open road, and grey if you're not sure. You've just drawn an occupancy grid. Each square holds a single fact: is this patch of the world blocked or not?

It sounds almost too simple, but this structure is the backbone of navigation for the vast majority of mobile robots operating in the real world today.

What each cell stores

An occupancy grid divides the environment into a two-dimensional array of cells, each representing a fixed area of floor space — typically 5 cm × 5 cm or 10 cm × 10 cm for indoor robots. Each cell stores a probability between 0 and 1:

• Near 1.0 — the cell is almost certainly occupied (wall, table leg, box).
• Near 0.0 — the cell is almost certainly free (open corridor, empty floor).
• Near 0.5 — unknown; the sensor hasn't observed this area clearly.

This probabilistic representation is honest about uncertainty. A single noisy lidar reading doesn't make a cell definitively occupied — it updates the probability, which multiple consistent readings gradually push towards certainty.

Building the grid from sensor data

A lidar scan produces a set of distance measurements radiating outward from the sensor. For each laser ray, the cells the ray passed through before hitting something are marked more free (the laser got through, so nothing blocked it), and the cell where the ray terminated is marked more occupied (something reflected the laser there). This update rule, applied thousands of times per second across many rays, builds a crisp map of free and occupied space.

The standard update mechanism uses a log-odds representation — storing log(p / (1−p)) instead of p directly — which makes incremental Bayesian updates a simple addition operation, fast enough to run in real time.

A real system: ROS Costmap 2D

The Nav2 navigation stack uses a "costmap" — a layered occupancy grid — as its core planning representation. One layer holds the static map built during a prior mapping session. Another layer shows dynamic obstacles detected in real time. A third applies an "inflation radius" — marking cells near obstacles as high-cost even if technically free, so the planner keeps the robot away from walls by a safe margin. The path planner then searches through this costmap for the lowest-cost route to the goal.

Limitations

Occupancy grids assume a flat 2D world. They struggle with multi-floor environments, ramps, or objects at different heights (a table is a forbidden obstacle, but the space under it is navigable). 3D occupancy grids (voxel grids, OctoMaps) address this but require far more memory and computation. For most indoor mobile robots on flat floors, the 2D grid remains the practical standard.

Alberto Elfes and Hans Moravec invented the occupancy grid at Carnegie Mellon in 1985, and it remains so effective that forty years later it is still the default map format for indoor robots worldwide.