Mapping with an occupancy grid

A map that remembers

A scan lasts a moment; to plan a route the rover needs a map that remembers. An occupancy grid splits the floor into 1 cm cells and keeps, for each, how likely it is to be solid.

What one beam says

A beam that stopped after $r$ metres says two things: every cell it passed through is free, and the cell it stopped in is occupied. A miss says only the first. One beam can be wrong, so each only nudges its cells.

Log-odds

Each cell stores its belief as log-odds, $l = \ln\frac{p}{1 - p}$, where $p$ is the probability that the cell is solid. $l = 0$ means $p = \tfrac{1}{2}$: unknown. In log-odds, Bayes' rule becomes addition: each beam adds $L_\text{free} = -0.4$ to the cells it crosses and $L_\text{occ} = +0.85$ to the one it stopped in, so evidence piles up. Three beams through a cell make $-1.2$, or $p = 0.23$. Every cell is clamped to $[-4, 4]$ so the map can still change its mind, and $p = 1 - 1/(1 + e^{l})$ turns it back into a probability for display. Foundations: Bayes' rule explains why the evidence adds up.

Walking a beam through the grid

Which cells does a beam cross? Sample the segment from the rover to the beam's end every half a cell: with $n$ steps, point $k$ is $\text{start} + (\text{end} - \text{start})\,k/n$. grid.cell(points) gives the (rows, cols) of every point at once. Drop each cell that repeats the one before, and what's left is the beam's cells, in order. Half-cell steps are short enough that each cell touches the next.

Your task

1. Write beam_cells(grid, start, end): the (row, col) cells from the start's cell to the end's cell, in order, each once.
2. Finish update(logodds, pose, scan): for each beam, add L_FREE to all its cells but the last, and L_OCC to the last if the beam hit (r < scan.max_range), skipping cells off the grid.

The rover follows a route through a maze you don't have the map of, and the Images tab shows your map filling in. The grader tests both functions, then wants ≥ 95 % of the scored cells right and ≥ 90 % of the scored wall cells occupied. It scores the cells the scans reached, except those beside a wall face, where lidar noise decides which side a hit lands on.