SLAM based on 2D Range Scan Matching

SLAM (Simultaneous Localization and Mapping) is a technique used by a mobile robot to build a map within an unknown environment and at the same time compute its current location. Our research is based on matching two consecutive 2D range scans which are obtained from a LRF (Laser Range Finder) mounted on a mobile robot.

The most widely used algorithm for matching range scans is the Iterative Closest Points (ICP) algorithm. This algorithm is based on an iterative process in two steps: first a set of corresponding pairs between two consecutive scans is selected, and second the error between corresponding pairs is minimized to find the rigid-body transformation between two scans. This process is repeated until two scans are converged. The most critical part of the ICP is the establishment of corresponding point-pairs. For any point in the first scan, the conventional ICP algorithm finds the closest point in the second scan (the nearest neighbor) its correspondence.

While ICP has advantages of easy implementation, it has many drawbacks because of the non-linear characteristic. ICP can fall into a bad local minimum due to outliers, occlusions and poor initial alignment. Our research interest is to increase the performance of the conventional ICP and adapt it to the real-time SLAM. In order to speed up the convergence, the point-to-line metric is adopted. The point-to-line metric has quadratic convergence instead of linear convergence of the conventional point-to-point metric, as shown in the next figure.

nj is the normal vector of tangent line going through point mj. The point-to-line metric minimizes the Euclidean distance from pi to the tangent line through mj, which greatly increase the robustness of the ICP algorithm against sensor noises. Besides, the point-to-line metric can be weighted to reduce the impact of false correspondences caused by outliers and occlusions.