Weighted line fitting algorithms for mobile robot map building and efficient data representation

This paper presents an algorithm to find the line-based map that best fits set 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 a 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 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.