# Scan Matching by Cross-Correlation and Differential Evolution
## 2 Related Work  
Although indoor localization has been addressed by a plethora of methods and algorithms with various properties, it still remains an open problem. Tightly linked to mapping of (unknown) indoor environments, it is an essential element of the compound problem of simultaneous localization and mapping (SLAM) [13; 14]. Different types of localization and SLAM algorithms have been developed for various types of environments [15]. Accurate SLAM algorithms have been proposed for large outdoor areas [16] and limited indoor spaces [17]. Monte Carlo localization (MCL) is a popular family of localization methods [9; 18; 19] that use, among others, particle and Kalman filters [20]. At the starting point of the MCL process, a pool of random positions and angles is created. When the robot moves through an environment, the algorithm updates all positions in the pool according to a robot motion model. The expected robot surrounding is compared to data from a sensor (e.g., the LiDAR) surveying the actual environment and the positions that correspond to the real data most are rewarded. The disadvantage of the MCL method is the necessity for robot movement and the need for additional sensors (e.g., odometers) that are required by the motion model [21]. Another family of promising SLAM approaches is based on the use of event cameras [22]. Event cameras produce sequences of video frames and, additionally, information about brightness changes on the pixel level. The advantages of event cameras include very high dynamic range, absence of motion blur and only a small latency (in the order of microseconds [23]). An overview of SLAM algorithms that use event cameras is provided, for example, in [24]. Localization is also one of the major challenges of UAVs. They require information about precise location in to order to avoid obstacles [25] and for trajectory planning [26]. UAVs can, in general, implement similar localization approaches as mobile robots. However, the localization methods need to be adjusted to address the specifics of aerial movement such as 3D SLAM. A comprehensive review of localization strategies for UAVs can be found in [6]. Scan matching [27; 28] is a group of popular high-level localization/SLAM methods that process laser range scans of an environment [29]. They align two laser range scans of the (usually unknown) environment in order to detect the change of the location and orientation of a moving object [30]. Scan matching algorithms can be classified as point-based and feature-based. Point-based methods process laser range scans point-by-point whereas feature-base methods extract higher-level features such as lines, corners and so forth, and align these features. Feature-based methods extract distinctive features before matching itself and thus decrease the amount of data that needs to be processed. As a result, their scan matching phase has lower computational costs but they suffer from lower robustness and worse accuracy in rich and well-structured environments. Iterative closest point (ICP) is a typical representative of point-based scan matching algorithms [31]. ICP is a seminal method that has a number of modifications [32; 33]. A representative of feature-based scan matching strategies is the complete line segment (CLS) method [34]. It looks for flat areas in point clouds, extracts lines and detects complete and incomplete line segments. It expects that a complete line segment in an environment has a specific constant length from any point of view. Other feature-based scan matching strategies include the anchor point relationships (APR) algorithm [35] that detects specific anchors, plane extraction approaches [36] and keypoint and keyline extraction [37]. Nature-inspired methods, such as evolutionary computation, have been used in the area of mobile robot localization as well. In [38], the differential evolution algorithm was used in conjunction with the traditional normal distribution transform (NDT) algorithm [39].