The goal of an occupancy mapping algorithm is to estimate the
posterior probability over maps given the data: p(m\mid z_{1:t}, x_{1:t}), where m is the map, z_{1:t} is the set of measurements from time 1 to t, and 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 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 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 p(m_i) represents the probability that cell i is occupied. The computational problem with estimating the posterior 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 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 :p(m_i\mid z_{1:t}, x_{1:t}) for all grid cells 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 :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. ==See also==