Abstract

In this paper we tackle the problem of providing a mobile robot with the ability to build a map of its environment using data gathered during navigation. The data correspond to the locations visited by the robot, obtained through a noisy odometer, and the distances to obstacles from each location, obtained from a noisy laser sensor. The map is represented as an occupancy grid. In this paper, we represent the process using a Graphical Representation based on a statistical structure resembling a Hidden Markov model. We determine the probability distributions involved in this Graphical Representation using a Motion Model, a Perception model, and a set of independent Bernoulli random variables associated with the cells in the occupancy grid forming the map. Our formulation of the problem leads naturally to the estimation of the posterior distribution over the space of possible maps given the data. We exploit a particular factorization of this distribution that allows us to implement an Importance Sampling algorithm. We show the results obtained by this algorithm when applied to a data set obtained by a robot navigating inside an office building type of indoor environment. © Springer-Verlag Berlin Heidelberg 2004.