Incremental Map Building with Markov Random Fields and its Evaluation

Abstract

This thesis presents a novel occupancy grid mapping approach which takes the dependencies of neighboring grid cells into account. The grid maps are estimated based on a compact environment representation which is derived from stereo image sequences.<br /> Today, autonomous driving is fundamental work of research teams around the globe. Their aim is to make cars more intelligent in order to provide more safety and comfort systems in the future. Based on on-board sensors autonomous cars must learn and understand their environment to be able to react correctly. Digital maps are essential for such systems since these maps are used for motion planning, and for precise self localization of the ego vehicle. A state-of-the art representation of digital maps are probabilistic occupancy grid maps where the the environment is discretized in a regular grid. Each grid cell has a probability that the cell is occupied which allows the description of static obstacles, free space, and unknown areas in a probabilistic way.<br /> This assumption allows the realization of efficient and straight forward incremental occupancy grid mapping approaches. Nevertheless, the assumption of independent grid cells is incorrect in a probabilistic way.<br /> The main contribution of this thesis is the development and realization of an occupancy grid mapping approach which keeps the dependencies of neighboring grid cells into account, and simultaneously allows an incremental framework with real time requirements. The aim is to produce more accurate and reliable occupancy grid maps. Furthermore, the pose uncertainty of the ego vehicle is also considered which leads to the simultaneous localization and mapping (SLAM) problem.<br /> The novel mapping algorithm is formulated as a probabilistic optimization problem in which the map is interpreted as an undirected graph. To model the dependencies, in other words the correlation between neighboring grid cells, Markov Random Fields are applied. To allow an efficient, and incremental mapping scheme, marginal probabilities for each grid cell are estimated, which is realized by a fast inference algorithm based on graph cuts. The mentioned SLAM problem is solved by a Rao-Blackwellized particle filter which separates the mapping step from the localization process. This allows the realization of the SLAM problem in an on-line fashion. For the mapping step the novel approach based on MRFs is chosen, the localization part is realized by a sampling importance resampling (SIR) particle filter.<br /> The performance of the occupancy grid mapping approach is evaluated on the basis of artificial and real-world data. Detection rates as well as the geometrical accuracy of occupied areas are the foundations of assessing the quality of the learned maps. The performance of the novel approach is compared against the results of an approach which does not model the dependencies of grid cells. The results show that the novel approach has a better performance with regard to the detection rates. Especially free space areas are more precise which is shown in a quantitative and qualitative way. For the validation of the performance of the developed on-line SLAM approach the estimated pose of the ego vehicle is taken into account. It is shown that the approach is able to estimate precise positions using only a small number of particles. The limits of the mapping algorithm, and of the SLAM approach are also discussed in this thesis.