The normal distributions transform: a new approach to laser scan matching

Matching 2D range scans is a basic component of many localization and mapping algorithms. Most scan match algorithms require finding correspondences between the used features, i.e. points or lines. We propose an alternative representation for a range scan, the normal distributions transform. Similar to an occupancy grid, we subdivide the 2D plane into cells. To each cell, we assign a normal distribution, which locally models the probability of measuring a point. The result of the transform is a piecewise continuous and differentiable probability density, that can be used to match another scan using Newton's algorithm. Thereby, no explicit correspondences have to be established. We present the algorithm in detail and show the application to relative position tracking and simultaneous localization and map building (SLAM). First results on real data demonstrate, that the algorithm is capable to map unmodified indoor environments reliable and in real time, even without using odometry data.

I. Introduction

Undoubtedly, simultaneous localization and mapping (SLAM) is a basic capability of a mobile robot system. Laser range scanners are popular sensors to get the needed input, mainly for their high reliability and their low noise in a broad class of situations. Many SLAM algorithms are based on the ability to match two range scans or to match a range scan to a map. Here we present a new approach to the low-level task of scan matching and show, how we use it to build maps.