# FFT-Based Scan-Matching for SLAM Applications with Low-Cost Laser Range Finders
## 1 Introduction
However, its particle filter and matching method are too simple, which could lead to an erroneous position estimation, according to [18]. The graph optimization used to be a common method in visual SLAM, and it was also introduced into LRF-based SLAM. In 2010, [PERSON] et al. [19] proposed a SLAM that uses graph optimization instead of particle filters. This method uses Sparse point adjustment to solve the problem of matrix solution in nonlinear optimization. Cartographer [20] is another new SLAM solution proposed by Google. It adopts the framework of graph optimization and adds the concept of a submap to realize laser loop closure. For robot systems, the use of multi-sensor fusion for mapping and localization is common [21; 22; 23; 24; 25]. Two or more sensors, such as lidar, camera, IMU, encoder, etc., could be combined to achieve a more robust performance of SLAM [16; 20; 21; 22; 23; 24; 25] by using EKF, Unscented Kalman Filter (UKF), graph optimization, and so on. One of the most heavily relied-upon tools for LRF-based SLAM is scan-matching; it is described as the problem of registering two laser scans in order to determine the relative positions from which the scans were obtained. The traditional method for scan matching is the Iterative Closest Point (ICP) algorithm proposed by [PERSON] and [PERSON] [26] in 1992. On account of its simplicity and low complexity, the ICP algorithm used to be very popular. Although it is commonly used, ICP has some defects, such as falling into local extremum, depending on initial registration, and having a high repetition rate. [PERSON] and [PERSON] [27] describe two scan-matching methods based on ICP. The first method considers the rotational and translational components separately: alternately fixing one, then optimizing the other. Given rotation, least-squares is used for optimizing translation. Feature-based methods were then introduced by [PERSON] [28] and [PERSON] [29]. They extract pairs of points that are likely to be part of a connected surface, or lines/splines first, then scan points are matched through these features. [PERSON] et al. [30] proposed a method that uses the Radial distance and Incident Angle (RIA) for scan alignment, which can efficiently estimate the relative transformation between two scans. There are also many other scan-matching methods, such as using polar coordinates [31], Hough transform [32], histogram [33; 34], correlation cost function [35; 36], and Normal Distributions Transform (NDT) [37], etc. A study of perfect match [38] and its comparison to different methods is given in [39]. For commercial robotics, the cost of traditional LRF sensors are usually unacceptable. Serial kinds of low-cost LRF sensors (price lower than 600 RMB) have been developed in recent years, such as Rplidar by the Slantec Company and N1-360 by the Leishen Company, etc. Compared with common expensive LRF sensors, low-cost LRF sensors have much poorer performance in range, precision, and resolution. As a result, scan matching may often fail while using low-cost LRF sensors, especially when the robot is running too quickly in complex environments, and it may cause failure to mapping and localization. High performance and low cost cannot be balanced, but it is an important concern for the realization of a commercial robot SLAM. For the commercial application of robotics, how to improve the SLAM algorithms so that they can adapt to low-cost and low-performance sensors is now becoming a key problem. Most LRF-based SLAM methods need a good initial guess for scan-matching in order to diminish the range of searching and speed up the process. Odometry message is a popular choice [16; 17] for that initial guess. Low-cost LRF sensors have much lower detection frequency and lower resolution, it may make the scan matching fail between two adjacent frames, especially when the odometry drifts. If the scan data is considered as an image, which indicates the outline of obstacles near the robot, then the scan-matching problem can be transformed to an image registration problem.