Occupancy Grid Mapping refers to a family of computer algorithms in probabilistic robotics for mobile robots which address the problem of generating maps from noisy and uncertain sensor measurement data, with the assumption that the robot pose is known.
Occupancy grids were first proposed by H. Moravec and A. Elfes in 1985.
[1] The basic idea of the occupancy grid is to represent a map of the environment as an evenly spaced field of binary random variables each representing the presence of an obstacle at that location in the environment.
Occupancy grid algorithms compute approximate posterior estimates for these random variables.
[2] There are four major components of occupancy grid mapping approach.
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
as a fine-grained grid over the continuous space of locations in the environment.
denote the grid cell with index i (often in 2d maps, two indices are used to represent the two dimensions), then the notation
Thus calculating a posterior probability for all such maps is infeasible.
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 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.