How a Robot Maps a Room It Has Never Seen

Chapter 1: The Occupancy Grid — Chopping the World into Cells

The first design decision is the most consequential: how do we represent the map at all? Back in Lesson 1 we surveyed four map types — occupancy, topological, feature, semantic. For "is this exact spot safe to drive on?" the answer is the occupancy grid (also called a metric grid map), and this lesson builds it in full.

The idea is almost embarrassingly direct. Lay a regular grid over the floor. Each square is a cell, written m_i for the i-th cell. The whole map is the collection of cells, m = {m₁, m₂, …, m_n}. Each cell stores one number: P(m_i), the probability that cell i is occupied by an obstacle. That's the entire data structure — a 2D array of probabilities.

Each cell lands in one of three intuitive regimes, which is all a planner really needs:

• Free — P(m_i) near 0 (say below 0.3). The robot can drive here. Drawn dark.
• Occupied — P(m_i) near 1 (say above 0.7). A wall or obstacle. Drawn red — do not enter.
• Unknown — P(m_i) near 0.5. Never observed; the robot has no evidence either way. Drawn grey.

The two thresholds — 0.3 for free, 0.7 for occupied — are not sacred; they are a tuning choice. A timid robot in a crowded warehouse might demand 0.8 before it trusts a cell is free enough to drive on; a confident robot in open space might accept 0.6. The wide "unknown" band in the middle (0.3 to 0.7) is deliberate: it forces the planner to treat barely-observed cells as suspect rather than committing to them. The grid is only as bold as the thresholds you let it be.

From world to cell: the index map

A subtle but essential piece of plumbing: the robot lives in continuous metric space (a pose at x = 3.42 m, y = 1.07 m), but the grid is a discrete integer-indexed array. The bridge is a fixed resolution r (metres per cell) and an origin (the world coordinate of cell (0,0)). Converting a world point to a cell index is one floor-division per axis:

python — world ↔ cell
RES = 0.05            # 5 cm per cell
ORIGIN = (-10.0, -10.0)  # world coord of cell (0,0)

def world_to_cell(wx, wy):
    ci = int((wx - ORIGIN[0]) / RES)   # floor to an integer column
    cj = int((wy - ORIGIN[1]) / RES)   # floor to an integer row
    return ci, cj

def cell_to_world(ci, cj):
    wx = ORIGIN[0] + (ci + 0.5) * RES   # centre of the cell
    wy = ORIGIN[1] + (cj + 0.5) * RES
    return wx, wy

This little function is where discretization error is born: every world point inside a cell collapses to the same index, so a wall that grazes a cell's corner and the cell's exact centre are stored identically. The finer r is, the smaller that rounding loss — and the more cells you pay for. That trade is the next section.

Resolution: the memory-versus-precision dial

A cell covers some physical area — its resolution. Choose 5 cm cells and a doorway is crisp, but a 20 m × 20 m floor needs 400 × 400 = 160,000 cells. Choose 50 cm cells and the same floor is only 40 × 40 = 1,600 cells — 100× less memory — but now a 30 cm gap might vanish inside a single "occupied" cell, and the robot thinks a doorway is a wall.

Worked memory budget

Let's put numbers on the trade. Map a 20 m × 20 m floor at three resolutions, storing one 4-byte float (the log-odds) per cell:

Halving the cell size from 10 cm to 5 cm quadrupled the count (40,000 → 160,000) and quadrupled the memory (160 KB → 640 KB). That is the square law in action: cells scale with area, and area scales with the square of linear resolution. For a small indoor robot, 5–10 cm is the sweet spot — fine enough to see a doorway, coarse enough to fit in cache and update fast.

Drag the slider below to re-grid one room. Coarse cells are cheap but blur the doorway; fine cells capture it but explode the count. The readout shows total cells and how the doorway fares at each resolution.

An occupancy grid is the workhorse of indoor robotics precisely because it answers the planner's exact question — "is this cell safe?" — in a single array lookup. The cost is memory; the payoff is that path planning (Lesson 3's A*) runs directly on it with no translation. Now: where do those per-cell probabilities come from?

Chapter 2: Why Probabilities, Not Booleans — A Filter Per Cell

Imagine for a moment we stored booleans: each cell is either "wall" or "free." The first beam that grazes a glossy floor and returns a spurious short reading flips a free cell to "wall" — forever. The map is one bad reading away from a phantom obstacle, and the robot reroutes around nothing. Booleans have no memory of how sure they are, so they cannot tell a lucky guess from overwhelming evidence.

The fix is to treat each cell as a tiny estimation problem in its own right. The true state of cell i is binary — it really is occupied or really is free — but the robot only sees it through noisy beams. So the robot maintains a belief P(m_i) and updates that belief every time a beam delivers fresh evidence. This is exactly the Bayes filter from the estimation lessons, specialized to a two-outcome (binary) state. We call it the binary Bayes filter.

The binary Bayes filter, written out

Let's derive the per-cell update in raw probability, so the log-odds shortcut in Chapter 4 feels earned rather than magic. Cell i has two possible truths: occupied (call it o_i) or free (¬o_i). The robot holds a belief P(o_i) and just got a measurement z. Bayes' rule says the posterior is the likelihood times the prior, divided by a normalizer:

Every symbol: P(o_i) is the belief before the measurement (the prior); p(z | o_i) is how likely this reading is if the cell really is occupied (the likelihood); the denominator sums over both truths so the two posteriors add to one. The recursive part is that the posterior P(o_i | z) becomes the prior for the next measurement — the belief is carried forward, refined reading by reading.

Worked update in probability (no shortcut)

Suppose a cell currently believes P(occupied) = 0.5 and a beam stops here (a "hit"). Our inverse model says a hit is consistent with occupancy 70% of the time: p(hit | occupied) = 0.7 and p(hit | free) = 0.3. Plug straight into Bayes:

One hit lifts the cell from 0.50 to 0.70. Feed a second hit, now with prior 0.70:

Two hits: 0.50 → 0.70 → 0.845. The belief sharpens, but every single step needs a multiply and a division by that fiddly normalizer. Do this 160,000 times per scan and the divisions hurt. The next chapter shows how a clever change of variables makes the whole thing a single addition — same answer, none of the arithmetic pain.

The cells-are-independent assumption

To make a 160,000-cell map tractable, occupancy grid mapping makes one bold simplification: it assumes the cells are independent of one another. The probability of the whole map factors into a product over individual cells:

Here ∏ (capital pi) means "multiply over all i." This factorization is the entire reason the algorithm is fast: instead of reasoning about 2¹⁶⁰⁰⁰⁰ possible maps jointly, the robot runs n independent two-state filters — one per cell — each updated by the beams that touch it.

Watch evidence sharpen a belief

Below is a single cell's belief, a probability bar. Feed it "hit" votes (a beam stopped here → occupied) and "miss" votes (a beam passed through → free) and watch the bar climb or fall. Critically, notice that one stray vote against a pile of consistent ones barely moves the bar — that robustness is what a probability buys you that a boolean cannot.

Chapter 3: The Inverse Sensor Model — What a Beam Says

A range beam delivers one number: the distance z to the nearest surface it hit. To update the grid, the robot must translate that one number into a statement about every cell along the beam. The function that does this is the inverse sensor model, written p(m_i | z, x): the probability that cell i is occupied, given the measurement z and the robot's pose x.

Why "inverse"? The ordinary (forward) sensor model answers "given the map, what reading would I expect?" — cause to effect. We need the reverse: "given the reading, what does the map look like?" — effect to cause. That backward direction is what the word inverse flags.

The physics gives us three clean regions along a single beam. Picture a beam leaving the robot, flying through air, and stopping when it hits a wall at distance z:

• Before the hit (range < z): the beam passed through this cell to get to the wall, so the cell must have been empty. Vote FREE — return a low occupancy probability, p_free (say 0.3).
• At the hit (range ≈ z): the beam stopped here, so something is here. Vote OCCUPIED — return a high probability, p_occ (say 0.7).
• Beyond the hit (range > z): the beam never reached this far; we learned nothing about it. Vote UNKNOWN — return the prior, 0.5 (no update).

The shape of the model

Two parameters tune the inverse model. The first is the obstacle thickness α: a real wall isn't infinitely thin, so we mark a small band of width α around the endpoint as occupied. The second is the beam width β: a laser beam is a near-perfect line (β < 1°), while sonar spreads into a wide cone (β = 15–30°). A wider beam updates more cells per reading but with less spatial precision — you learn about a fat wedge of space, not a thin ray.

The values p_free = 0.3 and p_occ = 0.7 are deliberately timid — not 0.05 and 0.95. They encode "this one beam is suggestive, not conclusive." A single reading should never slam a cell to certain; certainty must be earned by many agreeing beams. We make that timidity precise in the next chapter.

The model as a function, from scratch

The inverse sensor model is just three branches keyed on a cell's distance r from the robot versus the beam's range z. With α the obstacle thickness:

python — the inverse sensor model
P_FREE, P_OCC, P_PRIOR = 0.3, 0.7, 0.5
ALPHA = 0.10     # obstacle thickness band (m): how deep to call "occupied"

def inverse_sensor_model(r, z, z_max):
    # r: cell's distance from robot along the beam; z: measured range
    if z >= z_max:          # max-range "no hit" reading
        return P_FREE         # every cell on the ray is free; nothing to occupy
    if r < z - ALPHA:       # before the endpoint band
        return P_FREE         # beam passed through -> free
    if abs(r - z) <= ALPHA: # inside the endpoint band
        return P_OCC          # beam stopped here -> occupied
    return P_PRIOR          # beyond the endpoint -> unknown (no update)

Trace it for a beam with z = 3.0 m, α = 0.10 m: a cell at r = 1.5 m returns 0.3 (free), a cell at r = 2.95 m returns 0.7 (inside the band, occupied), a cell at r = 4.0 m returns 0.5 (beyond, no update). The whole model is four ifs. The art is entirely in choosing P_OCC, P_FREE, and ALPHA to match your sensor — a noisy sonar wants gentler values and a fatter α than a crisp laser.

Read the row left to right and you can recite the model: free, free, free, …, free, occupied, unknown, unknown. Move the wall closer and the free corridor shrinks; push it past the end of the beam and the whole row is free with no occupied cell at all (the beam reached its max range without hitting anything).

Chapter 4: The Log-Odds Update — Turning Multiplication into Addition

We have a per-cell belief and an inverse model that votes free/occupied/unknown. Now the mechanics: how does a cell combine a new vote with everything it already believed? Done naively, the Bayes update for cell i looks like this — multiply the prior belief by the new likelihood and renormalize so the two outcomes sum to one:

That is correct but clumsy: every update is a multiplication and a division (the normalizer), and as P creeps toward 0 or 1 the arithmetic gets numerically touchy. There is a change of variables that makes the whole thing a single addition with no normalizer at all. The trick is to track belief in log-odds.

The odds of a cell being occupied is the ratio P(occupied) / P(free). The log-odds ℓ is the natural logarithm of that ratio:

And we can always recover the probability from the log-odds with the logistic function:

Why bother? Because logarithms turn the multiplication in Bayes' rule into addition. The update rule for a cell touched by measurement z becomes simply:

Let's name every symbol. ℓ is the cell's running log-odds belief. ℓ_sensor(z) = log( p(m_i|z) / (1 − p(m_i|z)) ) is the log-odds form of the inverse sensor model's vote — positive for a hit, negative for a miss. ℓ₀ = log( P_prior / (1 − P_prior) ) is the prior log-odds, which we subtract so we don't double-count the prior on every update. With a 0.5 prior, ℓ₀ = log(0.5/0.5) = log(1) = 0, so the term vanishes and the update is just ℓ ← ℓ + ℓ_sensor — add a number, done.

Worked example: one cell, five measurements, by hand

Let's grind the arithmetic with no shortcuts. Set the inverse-model log-odds increments to ℓ_hit = +0.85 (a beam stopped here) and ℓ_miss = −0.40 (a beam passed through). Prior P = 0.5, so ℓ₀ = 0 and we start at ℓ = 0.00. Now feed the cell five measurements — including one stray bad reading at step 4 — and convert to probability at every step using P = 1/(1 + e^−ℓ):

Trace it. Three honest hits march the cell to 93% sure it's occupied. Then a single bad "miss" at step 4 — a beam that glanced off and returned long — only knocks it back to 90%, not down to a coin flip. One more hit recovers to 95%. The cell remembers its accumulated evidence; a lone liar cannot overturn a crowd of honest witnesses. Verify one row yourself: at step 4, ℓ = 2.55 − 0.40 = 2.15, and P = 1/(1 + e^−2.15) = 1/(1 + 0.117) = 1/1.117 = 0.895 ≈ 0.90. That is the robustness Chapter 2 promised, made arithmetic.

Clamping: don't let certainty run away

If a stationary wall gets hit 500 times, ℓ climbs to +425 and P pins to a value indistinguishable from 1.000. That sounds fine until the world changes — a door opens where the wall was. Now the cell needs hundreds of "free" votes to climb back down, and the map lags reality by minutes. The cure is to clamp ℓ to a fixed range, say [−6, +6] (which corresponds to P in roughly [0.0025, 0.9975]):

python
L = max(-6.0, min(6.0, L + l_sensor))   # clamp keeps the map responsive to change

Clamping caps how confident any cell can ever get, so a changed world can be re-learned in a handful of sweeps instead of hundreds. It trades a sliver of peak certainty for the ability to forget — exactly what a robot in a dynamic building needs.

Watch the difference with numbers. A wall cell sits at clamped ℓ = +6 (P = 0.9975). A door opens; now "free" misses of −0.40 arrive. How many to drop the cell below the 0.5 unknown line (ℓ = 0)? Just 6 / 0.40 = 15 misses — about one second of scanning. Without the clamp, an un-clamped cell that had soaked up 500 hits would sit at ℓ = +425 and need 425 / 0.40 ≈ 1,063 misses to forget — minutes of the robot staring at an open door insisting it's a wall. The clamp is the difference between a map that breathes with the world and one frozen in the past.

From scratch, then idiomatic

Here is the whole update for one cell, written out so every step is visible — convert prior to log-odds, add the sensor term, clamp, convert back:

python — from scratch (one cell)
import math

def prob_to_logodds(p):
    return math.log(p / (1.0 - p))      # ℓ = log( P / (1−P) )

def logodds_to_prob(l):
    return 1.0 / (1.0 + math.exp(-l))    # P = 1 / (1 + e^−ℓ)

L_HIT  = prob_to_logodds(0.7)    # inverse model: a hit  → +0.847
L_MISS = prob_to_logodds(0.3)    # inverse model: a miss → −0.847
L0     = 0.0                     # prior 0.5 → log-odds 0

def update_cell(L, observed_hit):
    # L is the cell's running log-odds; observed_hit is True/False/None
    if observed_hit is None:
        return L                                # unknown: no update
    l_sensor = L_HIT if observed_hit else L_MISS
    L = L + l_sensor - L0                        # the log-odds update
    return max(-6.0, min(6.0, L))           # clamp

Across a whole grid you never loop cell by cell — you vectorize with NumPy. Carry the entire grid as a log-odds array and add a same-shaped array of sensor increments in one stroke:

python — idiomatic (whole grid, vectorized)
import numpy as np

L = np.zeros((H, W))                 # prior 0.5 everywhere (log-odds 0)

def integrate(L, hits, misses):
    # hits, misses: boolean grids marking cells this scan voted on
    L = L + np.where(hits,   0.847, 0.0)   # +ℓ_hit where occupied
    L = L + np.where(misses, -0.847, 0.0)  # −ℓ_miss where free
    return np.clip(L, -6.0, 6.0)         # clamp the whole grid

P = 1.0 / (1.0 + np.exp(-L))           # recover probabilities for planning/display

Chapter 5: Building a Map from One Scan — Ray-Casting

A real LiDAR doesn't fire one beam — it fires hundreds in a sweep, each at its own angle. A full scan is a list of (angle, range) pairs. To turn a scan into grid updates we must, for each beam, figure out which cells it flies through (vote free) and which cell it stops at (vote occupied). That cell-marching is called ray-casting, and the classic algorithm for walking a straight line across a grid is Bresenham's line algorithm.

The job: given the beam's start cell (the robot) and its end cell (the hit point), list every grid cell the straight line between them crosses. Bresenham does this with pure integer addition — no floating point, no division per step — which is why it's been the standard since 1965.

Worked example: ray-casting one beam by hand

The robot sits at cell (0, 0). A beam at distance 4 hits a wall whose endpoint lands in cell (4, 2). Bresenham walks from (0, 0) toward (4, 2). The x-step is the dominant axis (Δx = 4 > Δy = 2), so we step x by 1 each iteration and let an error term decide when to bump y. The cells it visits:

So this one beam casts four free votes and one occupied vote — five cell updates. Multiply by the few hundred beams in a scan and a single sweep updates thousands of cells. That is the firehose of evidence that makes occupancy maps converge in a handful of sweeps.

Worked: two overlapping beams on one cell

Here is why a single scan already sharpens the map. Consider cell (3,1) from the ray-cast above. Three beams of the same scan happen to cross it on their way to nearby wall points — each casting a "free" vote. With ℓ_miss = −0.40 and starting from ℓ = 0:

After one scan, that cell already reads 0.23 — confidently free — because several beams of the same sweep independently confirmed it. Meanwhile the wall cell each beam stopped at collected several +0.85 hit votes and climbed past 0.85. A scan is not one beam; it is hundreds of overlapping rays, and their votes pile onto shared cells. That overlap is the firehose that makes a single sweep enough to outline a room.

From scratch: Bresenham + integrate one scan

python — ray-cast and integrate a whole scan
import numpy as np

def bresenham(x0, y0, x1, y1):
    # list the grid cells a straight line from (x0,y0) to (x1,y1) crosses
    cells = []
    dx, dy = abs(x1 - x0), abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx - dy
    while True:
        cells.append((x0, y0))
        if x0 == x1 and y0 == y1: break
        e2 = 2 * err
        if e2 > -dy: err -= dy; x0 += sx   # step x
        if e2 <  dx: err += dx; y0 += sy   # step y
    return cells

L_HIT, L_MISS = 0.85, -0.40

def integrate_scan(L, rx, ry, scan):
    # L: log-odds grid; (rx,ry): robot cell; scan: list of (end_x, end_y, hit?)
    for (ex, ey, hit) in scan:
        ray = bresenham(rx, ry, ex, ey)
        for (cx, cy) in ray[:-1]:        # every cell BEFORE the endpoint = free
            L[cy, cx] += L_MISS
        ex2, ey2 = ray[-1]                   # the endpoint
        if hit:
            L[ey2, ex2] += L_HIT             # endpoint = occupied (only if it hit)
        else:
            L[ey2, ex2] += L_MISS            # max-range: even the last cell is free
    return np.clip(L, -6.0, 6.0)

Press fire scan below to cast a fan of beams from the robot into a hidden room and watch one whole sweep paint the grid: free corridors carve out, walls light up red. Each beam is a Bresenham ray; each cell it crosses gets a log-odds vote.

Chapter 6: Mapping with Known Poses — Fusing Many Scans

One scan from one spot maps only what that spot can see — a single room, the near side of a wall. To map a whole building the robot must move, scan from each new vantage, and fuse the scans into one growing grid. The fusion is trivial in log-odds: every scan from every pose just adds its votes into the same grid. The grid is a running sum of all evidence ever collected.

But there is a hidden assumption doing enormous work here, and naming it is the whole point of this chapter. To cast a beam into the right cells, the robot must know exactly where it was standing and which way it faced when the beam fired. That is the robot's pose — (x, y, θ) from Lesson 1. Occupancy grid mapping assumes the pose is known and correct at every scan.

Why a known trajectory makes this easy

Given a known sequence of poses x₁, x₂, …, x_t and their scans z₁, …, z_t, the full map posterior factors cleanly because (a) cells are independent (Chapter 2) and (b) each scan is conditionally independent given its pose. The grand result is almost anticlimactic: just integrate every scan, in any order, into the same log-odds grid. Order doesn't matter; addition commutes.

python — fuse a whole known trajectory
L = np.zeros((H, W))                       # empty belief, prior 0.5 everywhere
for pose, scan in zip(known_poses, scans):
    rx, ry = world_to_cell(pose)           # robot's cell THIS scan (known pose!)
    endpoints = beams_to_cells(pose, scan) # transform each beam into the global grid
    L = integrate_scan(L, rx, ry, endpoints)
P = 1.0 / (1.0 + np.exp(-L))                 # the fused map

The one subtle step is beams_to_cells: each beam is measured in the robot's own frame (angle relative to its heading), so we rotate by θ and translate by (x, y) to place its endpoint in the global grid. Get θ wrong by 5° and every beam lands in the wrong cell — which is exactly why pose error is so corrosive.

Worked transform: where does this beam land?

The robot is at world pose (x, y, θ) = (2.0 m, 1.0 m, 90°) — sitting at (2,1) and facing straight up (north). A beam fires at angle φ = 0° in the robot's frame (straight ahead) and returns range z = 3.0 m. Where is the hit in world coordinates? First add the heading to the beam angle to get the world-frame direction:

Then walk z metres along that world direction from the robot's position:

So the endpoint is at world (2.0, 4.0). With the 5 cm grid and origin (−10, −10) from Chapter 1, that lands in cell ((2.0−(−10))/0.05, (4.0−(−10))/0.05) = cell (240, 280). The robot's own cell is (240, 220). Now Bresenham walks from (240, 220) to (240, 280) — a straight column — voting free on the 60 cells between and occupied at (240, 280). Notice the θ dependence: had the heading been wrong by even 5°, sin/cos would shift the endpoint by 3.0·sin(5°) ≈ 0.26 m — over five cells off. That is how a small pose error becomes a fat, smeared wall.

python — one beam endpoint to a world cell
import math
def beam_endpoint_cell(x, y, theta, phi, z):
    th = theta + phi                       # world-frame beam direction
    wx = x + z * math.cos(th)              # world endpoint x
    wy = y + z * math.sin(th)              # world endpoint y
    return world_to_cell(wx, wy)            # Chapter 1's index map

Where the error comes from

Even with "known" poses, real maps blur. The error sources are worth naming, because each one motivates a later lesson:

• Pose error. If the handed-down pose is off by a little, scans from different vantages disagree about where a wall is, and a single wall renders as a fat smear of two parallel lines. This is the dominant error, and the reason SLAM exists.
• Discretization error. A wall that crosses a cell diagonally can only be "in" or "out" of that cell — the grid can't represent the fractional truth. Finer cells reduce this (at the memory cost of Chapter 1).
• Sensor noise & specular surfaces. Glass and polished floors reflect beams away or return spurious ranges. Log-odds robustness (Chapter 4) absorbs the occasional outlier, but a mirror seen consistently can carve a phantom room.
• Dynamic objects. A person walking through leaves a trail of briefly-occupied cells. Clamping (Chapter 4) lets those cells fade back to free once the person leaves.

Chapter 7: Frontiers — The Edge of the Known World

The robot now has a partial map: islands of free space and walls surrounded by a sea of grey unknown. But who tells it where to go next? If a human had to point at the next unexplored hallway, the robot wouldn't be autonomous. We need the robot to find the edge of its own knowledge and head for it. That edge has a name, and it is one of the most elegant ideas in all of robotics: the frontier.

Read that definition twice, because both halves matter. A frontier cell must be free (the robot can stand on it — you can't drive to the middle of a wall) and border the unknown (standing there reveals new territory). A free cell deep inside a fully-mapped room is not a frontier — all its neighbors are known, so visiting it teaches nothing. A wall cell next to unknown is not a frontier — you can't drive there. Only free-cells-touching-unknown qualify.

Worked example: counting frontier cells by hand

Here is a tiny 5×5 belief map. Write F = free, X = occupied (wall), and U = unknown. The robot has mapped a small free pocket:

To find frontier cells, scan every FREE cell and ask: does it have at least one UNKNOWN 4-neighbor (up/down/left/right)? Walk through the free cells:

• (1,1) F — neighbors: (0,1)=X, (2,1)=F, (1,0)=X, (1,2)=F. No U neighbor. Not a frontier.
• (1,2) F — neighbors: (0,2)=X, (2,2)=F, (1,1)=F, (1,3)=U. Has a U! Frontier.
• (2,1) F — neighbors: (1,1)=F, (3,1)=F, (2,0)=X, (2,2)=F. No U. Not a frontier.
• (2,2) F — neighbors: (1,2)=F, (3,2)=F, (2,1)=F, (2,3)=F. No U. Not a frontier.
• (2,3) F — neighbors: (1,3)=U, (3,3)=U, (2,2)=F, (2,4)=U. Three U's! Frontier.
• (3,1) F — neighbors: (2,1)=F, (4,1)=X, (3,0)=X, (3,2)=F. No U. Not a frontier.
• (3,2) F — neighbors: (2,2)=F, (4,2)=X, (3,1)=F, (3,3)=U. Has a U! Frontier.

Tally: three frontier cells — (1,2), (2,3), and (3,2) — all on the right edge of the free pocket where it meets the unknown. They cluster naturally into one frontier region pointing east, exactly where the robot should look next to grow the map.

Clustering into frontier regions

Individual frontier cells are too fine-grained to be useful goals — a big room might have fifty adjacent frontier cells. So after detecting frontier cells we cluster them: any group of frontier cells that touch each other (connected via flood-fill or connected-components labeling) becomes one frontier region, summarized by its centroid (average position) and its size (how many cells). The robot then picks among a handful of regions, not hundreds of cells.

From scratch: detect and cluster frontiers

Detection is one pass over the grid: for every free cell, check its four neighbors for any unknown. Clustering is a second pass: group touching frontier cells with a flood-fill (connected components), then summarize each group by its centroid and size.

python — frontier detection + clustering
import numpy as np

FREE, OCC, UNK = 0, 1, -1     # cell labels in the thresholded belief grid

def frontier_cells(grid):
    # a frontier cell is FREE and has at least one UNKNOWN 4-neighbor
    H, W = grid.shape
    front = np.zeros_like(grid, dtype=bool)
    for j in range(H):
        for i in range(W):
            if grid[j, i] != FREE: continue
            for dj, di in [(-1,0),(1,0),(0,-1),(0,1)]:
                nj, ni = j+dj, i+di
                if 0 <= nj < H and 0 <= ni < W and grid[nj, ni] == UNK:
                    front[j, i] = True; break
    return front

def cluster(front):
    # flood-fill touching frontier cells into regions; return (centroid, size) each
    H, W = front.shape; seen = np.zeros_like(front, dtype=bool); regions = []
    for j in range(H):
        for i in range(W):
            if not front[j, i] or seen[j, i]: continue
            stack, cells = [(j, i)], []
            seen[j, i] = True
            while stack:
                cj, ci = stack.pop(); cells.append((cj, ci))
                for dj in (-1,0,1):
                    for di in (-1,0,1):
                        nj, ni = cj+dj, ci+di
                        if 0 <= nj < H and 0 <= ni < W and front[nj, ni] and not seen[nj, ni]:
                            seen[nj, ni] = True; stack.append((nj, ni))
            cj = np.mean([c[0] for c in cells])      # centroid row
            ci = np.mean([c[1] for c in cells])      # centroid col
            regions.append({'centroid': (cj, ci), 'size': len(cells)})
    return regions

Run frontier_cells on the 5×5 grid above and you get exactly the three cells we found by hand — (1,2), (2,3), (3,2). Run cluster on them and, because all three touch (diagonally), they collapse into a single region with centroid ≈ (2, 2.3) and size 3. That one region is the goal the explorer will plan toward next chapter.

Below, a partial map. Press find frontiers to highlight every free cell that borders the unknown — the glowing boundary is the edge of the robot's world. Add or remove walls and re-detect to see the frontier shift.

Chapter 8: Frontier-Based Exploration — Choosing Where to Go

Frontiers tell the robot where the edges are. Exploration is the loop that turns "here are the edges" into "go map the whole place." The algorithm, due to Brian Yamauchi, is so clean it fits in one sentence: repeatedly drive to a frontier and look, until no frontiers remain. Spelled out:

Steps 1 (this lesson, Chapters 1–6) and 2 (Chapter 7) you can already do. Step 4 is Lesson 3's A* search, run over the occupancy grid treating occupied cells as obstacles. The one new decision is step 3: which frontier?

Two ways to score a frontier

The simplest rule is nearest frontier: drive to whichever frontier region's centroid is closest (by path length, not straight-line distance — a wall might make a "near" frontier a long detour). It is greedy, fast, and surprisingly effective. The robot tends to sweep outward in a tidy expanding boundary.

The smarter rule maximizes information gain: prefer the frontier whose region is biggest, because a big frontier borders a lot of unknown space and so promises to reveal the most new cells. But a big frontier far away costs travel time. So we score each frontier by a utility that trades the two off:

Here gain(f) is the expected number of unknown cells the frontier f would reveal (well-approximated by the frontier region's size), cost(f) is the path length to reach f, and λ (lambda) is a weight that sets how much the robot values new information versus saved travel. Pick the frontier with the highest U. Large λ → an information-hungry explorer that crosses the building for a big unknown room; small λ → a lazy explorer that mops up nearby edges first.

Worked frontier-selection example

The robot has detected three frontier regions. Take λ = 1.0, with gain measured in unknown-cells-revealed and cost in cells-of-travel:

The two strategies disagree. Nearest-frontier picks A (cost 5, the closest). Information-gain picks B (U = +8, the best trade): B reveals 20 cells for only 12 of travel, beating both tiny-but-close A and huge-but-distant C. Notice C looks tempting (gain 30!) but its 28-cell trek nearly cancels the payoff — the utility score catches that automatically. Now crank λ to 2.0 and recompute: U_C = 2·30 − 28 = +32 now wins — a more information-hungry robot would brave the long trip to C. The λ dial literally changes the robot's personality.

python — pick the best frontier
def choose_frontier(frontiers, robot_cell, lam=1.0):
    # frontiers: list of regions, each with .centroid and .size
    best, best_u = None, -1e9
    for f in frontiers:
        gain = f.size                              # big region ⇒ lots of unknown to reveal
        cost = astar_path_length(robot_cell, f.centroid)   # Lesson 3
        u = lam * gain - cost                      # the utility trade-off
        if u > best_u:
            best, best_u = f, u
    return best                                    # None ⇒ no frontiers ⇒ exploration complete

The loop terminates the moment choose_frontier returns None — there are no free-cells-touching-unknown left, which means every reachable cell is known. The map is complete. The robot explored a building it had never seen, entirely on its own, with nothing but range beams and the frontier idea.

The whole loop in one function

Stitch the pieces together and the autonomous explorer is twelve lines. Each call into another module is named so you can see the stack of Lesson 1 working:

python — autonomous frontier exploration
def explore(robot, lidar, lam=1.0):
    L = np.zeros((H, W))                          # empty occupancy belief (log-odds)
    while True:
        scan = lidar.read(robot.pose)             # SEE  (Lessons 7–10)
        L = integrate_scan(L, robot.cell, scan)   # map: ch.4–5 log-odds update
        grid = threshold(L)                       # to FREE/OCC/UNK for detection
        regions = cluster(frontier_cells(grid))   # ch.7 detect + cluster
        target = choose_frontier(regions, robot.cell, lam)   # ch.8 pick
        if target is None:
            return L                              # no frontiers ⇒ map complete, DONE
        path = astar(grid, robot.cell, target.centroid)   # THINK (Lesson 3)
        if path is None:
            regions.remove(target); continue   # unreachable ⇒ try another
        robot.follow(path)                        # ACT  (Lessons 2, 6)

Read it as the see-think-act loop of Lesson 1, specialized to mapping: see with the LiDAR, think by mapping + detecting frontiers + planning, act by driving the path, then loop. The terminating condition — no frontiers — is a completeness guarantee: if the reachable free space is finite and bounded by walls, frontier exploration is guaranteed to map every reachable cell, because as long as any reachable unknown remains, there must be a free cell bordering it (a frontier) to drive to. Exploration ends only when there is genuinely nothing left to see.

Chapter 9: Showcase — Autonomous Exploration, End to End

Every piece is now on the table: an occupancy grid, the log-odds update, ray-cast scans, known poses, frontier detection, and frontier selection. Below they all run together. A robot wakes up in an unknown floor plan with nothing but a simulated LiDAR. Press Run and watch it map the entire building by itself: scan, find frontiers, pick the nearest one, plan a path, drive, re-map, repeat — until the % explored hits 100 and no frontiers remain.

Trace one cycle on screen. The robot scans — a fan of beams carves free corridors and paints walls red. Frontier detection lights up the cyan boundary where free meets grey. The selector picks the nearest frontier; A* floods the free belief grid and draws a warm path to it. Control steps the robot one cell along the path. Then the loop turns again, from the new vantage, revealing a little more of the world. The % explored climbs monotonically toward 100.

Now break it on purpose. Click cells to wall the robot into a pocket. The next frontier detection finds frontiers it cannot reach; A* returns no path; the explorer marks them unreachable and either re-routes to a different frontier or, if truly sealed in, halts cleanly with the map it has. Click to open a new doorway and fresh frontiers appear through the gap — the robot notices and pours through. That adaptivity, with no replanning by a human, is the see-think-act loop of Lesson 1 realized for mapping.

Experiments to try

• Step through one cycle. Press Step repeatedly and read the Phase card: SCAN → DETECT → SELECT → NAVIGATE. Each press is one beat of the see-think-act loop. Notice the Explored % tick up after every scan.
• Seal the robot in. Click cells to wall off the doorway ahead of the robot before it gets through. Watch the explorer detect frontiers it can't reach and halt cleanly — never driving into a wall.
• Open a surprise room. Once the robot thinks it's done, click to punch a hole into unexplored grey. Fresh frontiers appear at the gap and the robot resumes — exactly the adaptivity that a static, pre-built map could never have.
• Reveal the truth. Toggle Reveal true map to overlay the real walls (dashed red) on the robot's belief. The gap between them is the robot's ignorance — and it shrinks to nothing as exploration completes.

Chapter 10: Connections & Cheat-Sheet

You can now build a metric map of an unseen world from noisy beams, and you can let a robot explore that world autonomously by chasing its own frontiers. Here is the whole machine on one card.

Cheat-sheet

Where this sits on the autonomy stack

Occupancy mapping is the mapping half of the purple Localization & SLAM module from Lesson 1. It assumes known poses, which is exactly the assumption Lesson 11 (SLAM) drops — SLAM estimates poses and map together, and uses a mapper like this one as its inner loop. Frontier exploration drives the planner: every frontier goal becomes an A* query on the Lesson 3 motion planner, run over the very grid this lesson builds. And the per-cell belief update is the binary special case of the Bayes filter.