Occupancy grid mapping

Occupancy grid mapping algorithm

The goal of an occupancy mapping algorithm is to estimate the posterior probability over maps given the data: ${\displaystyle p(m\mid z_{1:t},x_{1:t})}$, where ${\displaystyle m}$ is the map, ${\displaystyle z_{1:t}}$ is the set of measurements from time 1 to t, and ${\displaystyle x_{1:t}}$ is the set of robot poses from time 1 to t. The controls and odometry data play no part in the occupancy grid mapping algorithm since the path is assumed known.

Occupancy grid algorithms represent the map ${\displaystyle m}$ as a fine-grained grid over the continuous space of locations in the environment. The most common type of occupancy grid maps are 2d maps that describe a slice of the 3d world.

If we let ${\displaystyle m_i}$ denote the grid cell with index i (often in 2d maps, two indices are used to represent the two dimensions), then the notation ${\displaystyle p(m_i)}$ represents the probability that cell i is occupied. The computational problem with estimating the posterior ${\displaystyle p(m\mid z_{1:t},x_{1:t})}$ is the dimensionality of the problem: if the map contains 10,000 grid cells (a relatively small map), then the number of possible maps that can be represented by this gridding is ${\displaystyle 2^{10,000}}$. Thus calculating a posterior probability for all such maps is infeasible.

The standard approach, then, is to break the problem down into smaller problems of estimating

${\displaystyle p(m_i\mid z_{1:t},x_{1:t})}$

for all grid cells ${\displaystyle m_i}$. Each of these estimation problems is then a binary problem. This breakdown is convenient but does lose some of the structure of the problem, since it does not enable modelling dependencies between neighboring cells. Instead, the posterior of a map is approximated by factoring it into

${\displaystyle p(m\mid z_{1:t},x_{1:t})=\prod _{i}p(m_i\mid z_{1:t},x_{1:t})}$.

Due to this factorization, a binary Bayes filter can be used to estimate the occupancy probability for each grid cell. It is common to use a log-odds representation of the probability that each grid cell is occupied.