Occupancy Grid Mapping Algorithm
The goal of an occupancy mapping algorithm is to estimate the posterior probability over maps given the data:, where is the map, is the set of measurements from time 1 to t, and 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. The most common type of occupancy grid maps are 2d maps that describe a slice of the 3d world.
If we let denote the grid cell with index i (often in 2d maps, two indices are used to represent the two dimensions), then the notation represents the probability that cell i is occupied. The computational problem with estimating the posterior 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 . 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 for all grid cells . 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 . Due to this factorization, a binary Bayes filter can be used to estimate the occupancy probability for each grid cell. It is frequent to use a log-odds representation of the probability that each grid cell is occupied.
Read more about this topic: Occupancy Grid Mapping