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 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.