Occupancy grid mapping

What it computes

An occupancy grid splits the floor into cells and keeps, for each, the probability $p$ that it's solid. The rover's pose is known here, so each lidar scan just adds evidence. Cells store the log-odds $l = \ln \frac{p}{1-p}$, which turns Bayes' rule into addition ($p = 1 - 1/(1 + e^{l})$), and start at $l = 0$: unknown.

The inverse sensor model

A beam that stops after $r$ metres says the cells it crossed are empty and the one it stopped in is solid. For each beam, add L_FREE (−0.4) to every cell it crosses, and L_OCC (+0.85) to the one it stops in, unless $r$ is the maximum range (a miss). Then clamp every cell to [L_MIN, L_MAX], so the map can still change its mind.

Ray traversal: Bresenham

The cells from $(x_0, y_0)$ to $(x_1, y_1)$, one per step along the longer axis:

dx, dy = abs(x1 - x0), -abs(y1 - y0)
sx, sy = sign(x1 - x0), sign(y1 - y0)     # +1 or -1
err = dx + dy
cells = [(x0, y0)]
while (x0, y0) != (x1, y1):
    e2 = 2 * err
    if e2 >= dy: err += dy; x0 += sx
    if e2 <= dx: err += dx; y0 += sy
    cells.append((x0, y0))

A beam's line runs from the rover's cell to its end cell; it crosses all but the last.

Tools

• Beam $i$ points at theta + scan.angles[i] in the world and read scan.ranges[i]. A miss reads scan.max_range.
• logodds.data[row, col] is the map, with $x$ along columns and $y$ along rows. logodds.cell(points) gives the (rows, cols) of world points. Skip cells off the grid.

The program

The rover follows a fixed route through a maze whose map you don't have, scanning 180 beams five times a second; the Images tab shows your map growing. The scored cells are those a correct update touches, minus those beside a wall face, where millimetres of lidar noise decide which side of the face a hit lands on. A cell is right if its log-odds has the right sign.

Your task

Implement bresenham(x0, y0, x1, y1) and update(logodds, pose, scan), which changes logodds.data in place. The grader tests both on made-up lines and scans, then wants ≥ 95 % of the scored cells right and ≥ 90 % of the scored wall cells occupied.