This paper presents a multi-scale point and line based representation of two-dimensional range scan data. The techniques are based on a multi-scale Hough transform and a tree representation of the environment's features. The multi-scale representation can lead to improved robustness and computational efficiencies in basic operations, such as matching and correspondence, that commonly arise in many localization and mapping procedures. For multi-scale matching and correspondence we introduce a chi2criterion that is calculated from the estimated variance in position of each detected line segment or point. This improved correspondence method can be used as the basis for simple scan-matching displacement estimation, as a part of a SLAM implementation, or as the basis for solutions to the kidnapped robot problem. Experimental results (using a Sick LMS-200 range scanner) show the effectiveness of our methods

This paper presents an algorithm to find the line-based map that best fits sets of two-dimensional range scan data. To construct the map, we first provide an accurate means to fit a line segment to a set of uncertain points via maximum likelihood formalism. This scheme weights each point's influence on the fit according to its uncertainty, which is derived from sensor noise models. We also provide closed-form formulas for the covariance of the line fit, along with methods to transform line coordinates and covariances across robot poses. A Chi-squared based criterion for "knitting" together sufficiently similar lines can be used to merge lines directly (as we demonstrate) or as part of the framework for a line-based SLAM implementation. Experiments using a Sick LMS-200 laser scanner and a Nomad 200 mobile robot illustrate the effectiveness of the algorithm.

Introduces a "weighted" matching algorithm to estimate a robot's planar displacement by matching two-dimensional range scans. The influence of each scan point on the overall matching error is weighted according to its uncertainty. We develop uncertainty models that account for effects such as measurement noise, sensor incidence angle, and correspondence error. Based on models of expected sensor uncertainty, our algorithm computes the appropriate weighting for each measurement so as to optimally estimate the displacement between two consecutive poses. By explicitly modeling the various noise sources, we can also calculate the actual covariance of the displacement estimates instead of a statistical approximation of it. A realistic covariance estimate is necessary for further combining the pose displacement estimates with additional odometric and/or inertial measurements within a localization framework. Experiments using a Nomad 200 mobile robot and a Sick LMS-200 laser range finder illustrate that the method is more accurate than prior techniques.