Occupancy-Grid Mapping

A robot enters an unknown room. Its laser rangefinder fires a beam and records a distance — but the reading is noisy. Fire again and you get a slightly different number. How does the robot ever build a reliable map?

Occupancy-grid mapping, developed by Moravec and Elfes in the late 1980s, answers that question with a beautifully simple idea: divide space into a grid of cells and assign each cell a number between 0 and 1 that represents the probability it is occupied by an obstacle. At the start, every cell sits at $p = 0.5$ — pure uncertainty. Each sensor reading then nudges those numbers up or down using Bayesian inference.

The key insight is that no single reading is trusted blindly. A return that looks like a wall might just be a dust particle. A return that misses a wall might be a specular reflection. But fire the sensor a hundred times from slightly different positions and the true obstacles accumulate evidence while the noise averages out. The grid remembers every measurement and never throws one away.

The result is a compact, uncertainty-aware map: dark cells are likely walls, light cells are likely free space, and gray cells are still in doubt. It is one of the foundational algorithms in probabilistic robotics — the bedrock under modern self-driving cars and autonomous drones.

Below is a simulated room with walls (shown in the preview on the right). A robot starts at the center and sweeps its laser sensor in all directions. Each beam travels until it hits a wall or reaches the max range; the cell it hits gets its occupancy probability pushed up, and all the cells along the beam get their probability pushed down (they are free space).

<!-- {{c_html_desc}} -->
<div class="toolbar">
  <button id="btn-scan" type="button">{{btn_scan}}</button>
  <button id="btn-auto" type="button">{{btn_auto}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="scan-count" id="scan-count"></span>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-label">{{label_truth}}</div>
    <canvas id="truth-canvas" width="200" height="200"></canvas>
  </div>
  <div class="panel">
    <div class="panel-label">{{label_map}}</div>
    <canvas id="map-canvas" width="200" height="200"></canvas>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>

/* {{c_css_desc}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.toolbar { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #e63946; border-color: #c92f3c; }
.scan-count { font-size: .85rem; color: #555; margin-left: .3rem; }
.panels { display: flex; gap: .8rem; flex-wrap: wrap; }
.panel { display: flex; flex-direction: column; align-items: center; gap: .25rem; }
.panel-label { font-size: .8rem; font-weight: 600; color: #555; letter-spacing: .03em; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; image-rendering: pixelated; display: block; }
.status { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.3em; color: #1d3557; }

// Code not found

Press Scan to fire one sweep of beams and watch the grid update. Press Auto to let the robot scan continuously. Notice how a few scans produce a blurry, uncertain map, while after many sweeps the walls become crisp and dark and the interior turns confidently white. The Reset button restores all cells to $p = 0.5$.

The math behind each update is a single application of Bayes' rule: the new probability is proportional to the likelihood of the reading given occupancy, times the old probability. Working in log-odds makes it an addition rather than a multiplication, which is why the algorithm is fast enough to run on real hardware.

The update rule looks deceptively simple. Let $p_t$ be the probability that a cell is occupied after $t$ measurements. Bayes' rule gives:

$$p_t = \frac{p(z_t \mid \text{occ}) \cdot p_{t-1}}{p(z_t \mid \text{occ}) \cdot p_{t-1} + p(z_t \mid \text{free}) \cdot (1 - p_{t-1})}$$

where $p(z_t \mid \text{occ})$ is the sensor model — how likely is the reading $z_t$ if the cell really is occupied? Multiplying probabilities repeatedly causes numerical underflow, so the standard trick is to work in log-odds:

$$l_t = l_{t-1} + \log \frac{p(z_t \mid \text{occ})}{p(z_t \mid \text{free})}$$

Now each update is just addition. The term being added, called the inverse sensor model, is a constant for each beam outcome (hit vs. free). Converting back: $p = 1 - \frac{1}{1 + e^{l}}$.

• Per-scan cost: $O(R \cdot B)$ where $R$ is the number of beams and $B$ is the maximum beam length in cells.
• Grid size: a $1000 \times 1000$ grid with 10 cm cells covers a $100\,\text{m} \times 100\,\text{m}$ space — 1 million cells, each storing just one float.
• Independence assumption: cells are updated independently. This is the algorithm's big simplification — real obstacles are correlated — but it makes the update trivially parallelizable.

The method was proved sound in the probabilistic-robotics framework by Thrun, Burgard, and Fox (2005). It remains one of the most widely deployed mapping algorithms because its memory and compute costs grow only linearly with grid area, and the log-odds form is immune to probability collapse.

Occupancy-grid mapping is not a curiosity — it runs inside a remarkable range of real systems:

• Self-driving cars: lidar scans feed an occupancy grid hundreds of times per second. The grid tells the planner which cells to treat as obstacles and which to drive through.
• Autonomous drones: depth cameras build 3-D voxel grids (the 3-D extension of the 2-D grid). The drone plans collision-free trajectories through cells marked free.
• Warehouse robots: a robot like those used by Amazon builds a persistent map of its environment on the first shift and then navigates by updating it incrementally — a technique called SLAM (Simultaneous Localization and Mapping).
• Surgical robots: a robotic arm needs a precise map of the workspace to avoid hitting instruments or anatomy. Occupancy grids provide a real-time safety boundary.
• Search and rescue: a ground robot sent into a collapsed building maps passable corridors and blocked zones so human rescuers know where to focus.

The grid abstraction is powerful precisely because it is agnostic to the sensor: lidar, sonar, depth cameras, and even WiFi signal strength can all feed an occupancy update. Whatever measures distance or detects obstacles can become input.

Occupancy-grid mapping is a masterclass in embracing uncertainty rather than fighting it. Instead of asking "is this cell occupied?", the algorithm asks "how confident are we?" — and it updates that confidence every time a sensor fires. The walls emerge not from a single perfect reading but from the accumulation of imperfect evidence.

The log-odds trick makes the math cheap enough to run in real time on embedded hardware. The independence assumption keeps the grid scalable to large environments. And the probabilistic foundation means the map always carries a built-in measure of its own reliability.

It is a fitting reminder that many of the hardest engineering problems — knowing where you are, knowing what surrounds you — yield not to perfect measurements but to principled reasoning about noisy ones. Occupancy grids put Bayesian inference to work in the physical world, one cell at a time.