How Robots Map a Room, One Probability at a Time

Introduction

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.

Try It

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).

<!-- Occupancy-grid mapping demo: true room on the left, probabilistic map on the right -->
<div class="toolbar">
  <button id="btn-scan" type="button">Scan</button>
  <button id="btn-auto" type="button">Auto</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span class="scan-count" id="scan-count"></span>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-label">True room</div>
    <canvas id="truth-canvas" width="200" height="200"></canvas>
  </div>
  <div class="panel">
    <div class="panel-label">Robot's map</div>
    <canvas id="map-canvas" width="200" height="200"></canvas>
  </div>
</div>
<div class="status" id="status">Press Scan to fire a sweep of beams.</div>

/* Styles for the two-panel occupancy-grid mapping demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Grid dimensions — each cell is one square in the occupancy grid
const COLS = 20, ROWS = 20;
const CELL = 10; // pixels per cell on canvas

// Log-odds update constants derived from the sensor model
const L_OCC = Math.log(0.85 / 0.15);  // added to a cell when the beam hits it (occupied evidence)
const L_FREE = Math.log(0.15 / 0.85); // added to a cell the beam passes through (free evidence)
const L_CLAMP = 6;                     // clamp log-odds so probabilities stay away from 0 and 1

// Ground-truth room: border walls + one inner pillar
// 1 = wall, 0 = free. The room is a rectangle with an inner pillar.
const ROOM = (() => {
  const g = [];
  for (let r = 0; r < ROWS; r++) {
    const row = [];
    for (let c = 0; c < COLS; c++) {
      const onEdge = r === 0 || r === ROWS - 1 || c === 0 || c === COLS - 1;
      const pillar = r >= 7 && r <= 9 && c >= 7 && c <= 9;
      row.push(onEdge || pillar ? 1 : 0);
    }
    g.push(row);
  }
  return g;
})();

// Log-odds grid initialised to 0 (p=0.5, maximum uncertainty)
let logOdds = Array.from({ length: ROWS }, () => new Float32Array(COLS));
let scanCount = 0;
let autoTimer = null;

const truthCtx = document.getElementById('truth-canvas').getContext('2d');
const mapCtx = document.getElementById('map-canvas').getContext('2d');
const statusEl = document.getElementById('status');
const scanCountEl = document.getElementById('scan-count');
const btnAuto = document.getElementById('btn-auto');

// Render the ground-truth room: dark = wall, light = free
function drawTruth() {
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      truthCtx.fillStyle = ROOM[r][c] ? '#1d3557' : '#f0f4f8';
      truthCtx.fillRect(c * CELL, r * CELL, CELL, CELL);
    }
  }
  // red dot marks the robot position
  const rx = Math.floor(COLS / 2) * CELL + CELL / 2;
  const ry = Math.floor(ROWS / 2) * CELL + CELL / 2;
  truthCtx.beginPath();
  truthCtx.arc(rx, ry, 4, 0, Math.PI * 2);
  truthCtx.fillStyle = '#e63946';
  truthCtx.fill();
}

// Render the probabilistic map: dark = likely occupied, light = likely free
function drawMap() {
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const l = logOdds[r][c];
      const p = 1 - 1 / (1 + Math.exp(l));
      // convert probability to grayscale: p=1 (occupied) -> black, p=0 (free) -> white
      const gray = Math.round((1 - p) * 255);
      mapCtx.fillStyle = `rgb(${gray},${gray},${gray})`;
      mapCtx.fillRect(c * CELL, r * CELL, CELL, CELL);
    }
  }
  // robot position on the map
  const rx = Math.floor(COLS / 2) * CELL + CELL / 2;
  const ry = Math.floor(ROWS / 2) * CELL + CELL / 2;
  mapCtx.beginPath();
  mapCtx.arc(rx, ry, 4, 0, Math.PI * 2);
  mapCtx.fillStyle = '#e63946';
  mapCtx.fill();
}

// Ray-casting: march in direction (dr,dc) until hitting a wall or leaving the grid
// Cast a ray from (r0,c0) in direction (dr,dc). Returns cells along the beam.
function castRay(r0, c0, dr, dc) {
  const cells = [];
  let r = r0, c = c0;
  const maxSteps = Math.max(ROWS, COLS) * 2;
  for (let i = 0; i < maxSteps; i++) {
    r += dr; c += dc;
    const ri = Math.round(r), ci = Math.round(c);
    if (ri < 0 || ri >= ROWS || ci < 0 || ci >= COLS) break;
    cells.push({ ri, ci, hit: ROOM[ri][ci] === 1 });
    if (ROOM[ri][ci] === 1) break; // stop ray at first wall hit
  }
  return cells;
}

// One scan: cast 36 beams from the robot centre and update log-odds
function scan() {
  const rr = Math.floor(ROWS / 2), rc = Math.floor(COLS / 2);
  const NUM_BEAMS = 36;
  for (let b = 0; b < NUM_BEAMS; b++) {
    const angle = (b / NUM_BEAMS) * Math.PI * 2;
    const dr = Math.sin(angle), dc = Math.cos(angle);
    const cells = castRay(rr, rc, dr, dc);
    for (let i = 0; i < cells.length; i++) {
      const { ri, ci, hit } = cells[i];
      if (hit) {
        logOdds[ri][ci] = Math.min(logOdds[ri][ci] + L_OCC, L_CLAMP);
      } else {
        logOdds[ri][ci] = Math.max(logOdds[ri][ci] + L_FREE, -L_CLAMP);
      }
    }
  }
  scanCount++;
  scanCountEl.textContent = i18nFmt('Scans: %n%', { n: scanCount });
  statusEl.textContent = i18nFmt('After %n% scan(s) — walls are emerging from noise.', { n: scanCount });
  drawMap();
}

function reset() {
  logOdds = Array.from({ length: ROWS }, () => new Float32Array(COLS));
  scanCount = 0;
  scanCountEl.textContent = '';
  statusEl.textContent = 'Press Scan to fire a sweep of beams.';
  stopAuto();
  drawMap();
}

function stopAuto() {
  if (autoTimer !== null) { clearInterval(autoTimer); autoTimer = null; }
  btnAuto.textContent = 'Auto';
  btnAuto.classList.remove('active');
}

function toggleAuto() {
  if (autoTimer !== null) {
    stopAuto();
  } else {
    autoTimer = setInterval(scan, 180);
    btnAuto.textContent = 'Stop';
    btnAuto.classList.add('active');
  }
}

document.getElementById('btn-scan').addEventListener('click', scan);
document.getElementById('btn-auto').addEventListener('click', toggleAuto);
document.getElementById('btn-reset').addEventListener('click', reset);

drawTruth();
drawMap();

<!-- Occupancy-grid mapping demo: true room on the left, probabilistic map on the right -->
<div class="toolbar">
  <button id="btn-scan" type="button">Scan</button>
  <button id="btn-auto" type="button">Auto</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span class="scan-count" id="scan-count"></span>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-label">True room</div>
    <canvas id="truth-canvas" width="200" height="200"></canvas>
  </div>
  <div class="panel">
    <div class="panel-label">Robot's map</div>
    <canvas id="map-canvas" width="200" height="200"></canvas>
  </div>
</div>
<div class="status" id="status">Press Scan to fire a sweep of beams.</div>

/* Styles for the two-panel occupancy-grid mapping demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Grid dimensions — each cell is one square in the occupancy grid
const COLS = 20, ROWS = 20;
const CELL = 10; // pixels per cell on canvas

// Log-odds update constants derived from the sensor model
const L_OCC = Math.log(0.85 / 0.15);  // added to a cell when the beam hits it (occupied evidence)
const L_FREE = Math.log(0.15 / 0.85); // added to a cell the beam passes through (free evidence)
const L_CLAMP = 6;                     // clamp log-odds so probabilities stay away from 0 and 1

// Ground-truth room: border walls + one inner pillar
// 1 = wall, 0 = free. The room is a rectangle with an inner pillar.
const ROOM = (() => {
  const g = [];
  for (let r = 0; r < ROWS; r++) {
    const row = [];
    for (let c = 0; c < COLS; c++) {
      const onEdge = r === 0 || r === ROWS - 1 || c === 0 || c === COLS - 1;
      const pillar = r >= 7 && r <= 9 && c >= 7 && c <= 9;
      row.push(onEdge || pillar ? 1 : 0);
    }
    g.push(row);
  }
  return g;
})();

// Log-odds grid initialised to 0 (p=0.5, maximum uncertainty)
let logOdds = Array.from({ length: ROWS }, () => new Float32Array(COLS));
let scanCount = 0;
let autoTimer = null;

const truthCtx = document.getElementById('truth-canvas').getContext('2d');
const mapCtx = document.getElementById('map-canvas').getContext('2d');
const statusEl = document.getElementById('status');
const scanCountEl = document.getElementById('scan-count');
const btnAuto = document.getElementById('btn-auto');

// Render the ground-truth room: dark = wall, light = free
function drawTruth() {
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      truthCtx.fillStyle = ROOM[r][c] ? '#1d3557' : '#f0f4f8';
      truthCtx.fillRect(c * CELL, r * CELL, CELL, CELL);
    }
  }
  // red dot marks the robot position
  const rx = Math.floor(COLS / 2) * CELL + CELL / 2;
  const ry = Math.floor(ROWS / 2) * CELL + CELL / 2;
  truthCtx.beginPath();
  truthCtx.arc(rx, ry, 4, 0, Math.PI * 2);
  truthCtx.fillStyle = '#e63946';
  truthCtx.fill();
}

// Render the probabilistic map: dark = likely occupied, light = likely free
function drawMap() {
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const l = logOdds[r][c];
      const p = 1 - 1 / (1 + Math.exp(l));
      // convert probability to grayscale: p=1 (occupied) -> black, p=0 (free) -> white
      const gray = Math.round((1 - p) * 255);
      mapCtx.fillStyle = `rgb(${gray},${gray},${gray})`;
      mapCtx.fillRect(c * CELL, r * CELL, CELL, CELL);
    }
  }
  // robot position on the map
  const rx = Math.floor(COLS / 2) * CELL + CELL / 2;
  const ry = Math.floor(ROWS / 2) * CELL + CELL / 2;
  mapCtx.beginPath();
  mapCtx.arc(rx, ry, 4, 0, Math.PI * 2);
  mapCtx.fillStyle = '#e63946';
  mapCtx.fill();
}

// Ray-casting: march in direction (dr,dc) until hitting a wall or leaving the grid
// Cast a ray from (r0,c0) in direction (dr,dc). Returns cells along the beam.
function castRay(r0, c0, dr, dc) {
  const cells = [];
  let r = r0, c = c0;
  const maxSteps = Math.max(ROWS, COLS) * 2;
  for (let i = 0; i < maxSteps; i++) {
    r += dr; c += dc;
    const ri = Math.round(r), ci = Math.round(c);
    if (ri < 0 || ri >= ROWS || ci < 0 || ci >= COLS) break;
    cells.push({ ri, ci, hit: ROOM[ri][ci] === 1 });
    if (ROOM[ri][ci] === 1) break; // stop ray at first wall hit
  }
  return cells;
}

// One scan: cast 36 beams from the robot centre and update log-odds
function scan() {
  const rr = Math.floor(ROWS / 2), rc = Math.floor(COLS / 2);
  const NUM_BEAMS = 36;
  for (let b = 0; b < NUM_BEAMS; b++) {
    const angle = (b / NUM_BEAMS) * Math.PI * 2;
    const dr = Math.sin(angle), dc = Math.cos(angle);
    const cells = castRay(rr, rc, dr, dc);
    for (let i = 0; i < cells.length; i++) {
      const { ri, ci, hit } = cells[i];
      if (hit) {
        logOdds[ri][ci] = Math.min(logOdds[ri][ci] + L_OCC, L_CLAMP);
      } else {
        logOdds[ri][ci] = Math.max(logOdds[ri][ci] + L_FREE, -L_CLAMP);
      }
    }
  }
  scanCount++;
  scanCountEl.textContent = i18nFmt('Scans: %n%', { n: scanCount });
  statusEl.textContent = i18nFmt('After %n% scan(s) — walls are emerging from noise.', { n: scanCount });
  drawMap();
}

function reset() {
  logOdds = Array.from({ length: ROWS }, () => new Float32Array(COLS));
  scanCount = 0;
  scanCountEl.textContent = '';
  statusEl.textContent = 'Press Scan to fire a sweep of beams.';
  stopAuto();
  drawMap();
}

function stopAuto() {
  if (autoTimer !== null) { clearInterval(autoTimer); autoTimer = null; }
  btnAuto.textContent = 'Auto';
  btnAuto.classList.remove('active');
}

function toggleAuto() {
  if (autoTimer !== null) {
    stopAuto();
  } else {
    autoTimer = setInterval(scan, 180);
    btnAuto.textContent = 'Stop';
    btnAuto.classList.add('active');
  }
}

document.getElementById('btn-scan').addEventListener('click', scan);
document.getElementById('btn-auto').addEventListener('click', toggleAuto);
document.getElementById('btn-reset').addEventListener('click', reset);

drawTruth();
drawMap();

Result

Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/occupancy-grid-mapping/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Occupancy-Grid Mapping

Turning range-sensor noise into a probabilistic floor plan