# FFT-Based Scan-Matching for SLAM Applications with Low-Cost Laser Range Finders
## 1 Introduction  
With the rapid development of artificial intelligence and pattern recognition technology, intelligent robots have entered all aspects of industrial automation and human life. One of the most important features/functions of robot intelligence is to move autonomously, which is usually supported by precise localization and reliable navigation. To achieve this, the common technique is Simultaneous Localization and Mapping (SLAM). SLAM includes two parts: localization and mapping, where localization is an important premise of mapping. The SLAM problem can be solved by maintaining a robot-state (pose and map) probability-density function or its moments [1]. Depending on whether the environment is pre-given, localization can be divided into localization in a known environment and localization in an unknown environment [2]. The localization in a known environment mainly considers the problem of positioning accuracy. Localization in an unknown environment often requires the use of external sensors to obtain information for estimating the robot's position after processing. The self-localization method can also be divided into two categories: relative positioning and absolute positioning. Relative positioning refers to determining the relative distance and direction in which a robot moved in a shorttime. This method measures the change of the mobile robot's current location related to its initial position, usually based on dead reckoning, Kalman Filter, Markov, Montecarlo, and Extended Kalman Filter (EKF). Absolute positioning refers to the direct determination of position in the world coordinate system that mainly includes map matching and positioning [3]. When a robot is moving, the position calculated by the internal sensors (such as an encoder, Inertial Measurement Unit (IMU), etc.) inevitably drifts. As a result, sensors that can perceive the surrounding environment are usually needed for robot positioning, including vision sensors, range sensors, GPS, etc. Vision-based approaches have been widely studied in recent years [4]. They analyze and track natural landmarks [5], significant features [6; 7], or image pixel values directly [8; 9; 10]. Special cameras are used for achieving better performance under different situations, such as omnidirectional camera approaches [11; 12], RGB-D camera approaches [10; 13], etc. However, vision methods usually have high computational complexity or it is difficult to create maps for navigation and obstacle avoidance. Laser range finder (LRF) sensors occupy an essential role in robot navigation because they can build occupancy grid maps with low computational cost. SLAM based on LRF sensors has been studied thoroughly [14; 15; 16; 17; 18; 19; 20]. [PERSON] [14] presented an approach to parallelize two well-known mapping algorithms, namely Iterative Closest Point (ICP) and Lu Milios (LUM), which were used for scan matching in Robotic 3D mapping. [PERSON] and [PERSON] [15] achieved real-time performance by developing a novel branch-and-bound, multi-resolution approach that made use of rasterized lookup tables of Gaussian mixture maps. Methods based on particle filters were proven to be effective for building the map based on the odometry message and scan data [16; 17]. [PERSON] et al. [16] proposed a SLAM method based on an improved Rao-Blackwellized particle filter, which used proposal distribution and an adaptive resampling technique to improve accuracy and reduce computational resource consumption. Particle distribution not only considers the motion model, but also considers observations. The advantage of this method is that it avoids the nonlinear problem. The problem is that as more particles are needed, more computing resources are consumed. [PERSON] and [PERSON] [17] implemented a minimal SLAM system in 2010 using 200 lines of C code, called Core-SLAM. The algorithm is simplified into two processes of distance calculation and map update, which greatly reduces the consumption of computing resources.