Occupancy Grid Mapping

An occupancy grid splits the world into small cells and keeps, for each one, the probability that it is blocked. Every LiDAR ray says two things: the cell where it hit is probably occupied, and every cell it passed through is probably free.

Cell size Evidence per hit Evidence per pass-through Range noise

Log-odds updates

Each cell stores the log-odds of being occupied, $\ell = \log\frac{p}{1-p}$, starting at 0, which means 50 percent. For every ray:

$$\ell_{\text{hit cell}} \mathrel{+}= \ell_{\text{occ}} \qquad \ell_{\text{cells passed through}} \mathrel{-}= \ell_{\text{free}} \qquad p = 1 - \frac{1}{1 + e^{\ell}}$$

Adding log-odds is the same as applying Bayes' rule, and it is just one addition per cell.

What to notice

Unseen cells stay gray at 50 percent. Rays carve out light free space and leave dark walls at their ends. Cells seen many times become very certain. Large cells make a coarse but cheap map, small cells a detailed but costly one. Range noise blurs the walls, but repeated views average it out. This is how ROS 2 mapping packages such as slam_toolbox store their maps.