Occupancy grid mapping with Markov Chain Monte Carlo Gibbs sampling

Occupancy grids have been widely used for mapping with mobile robots for nearly 30 years. Occupancy grids discretize the analog environment and seek to determine the occupancy probability of each cell. Traditional occupancy grid mapping methods make two assumptions for computational efficiency and it has been shown that the full posterior is computationally intractable without these assumptions. This paper employs a form of Markov Chain Monte Carlo (MCMC) known as Gibbs sampling to sample from the full posterior. By drawing many samples, we are able to capture the full posterior, which more accurately represents the uncertainty in the map due to sensor measurement error. The MCMC method is shown to compute the full posterior in a 1D toy example, and it is shown to be computationally tractable, though not online, for realistic 2D simulations.