Map-Matching Algorithms for Robot Self-Localization: A Comparison Between Perfect Match, Iterative Closest Point and Normal Distributions Transform uri icon

abstract

  • The self-localization of mobile robots is one of the most fundamental problems in the robotics navigation eld. It is a complex and challenging issue due to the hard requirements that autonomous mobile vehicles are subject to, particularly with regard to the algorithms accuracy, robustness and computational e ciency. In this paper, we present a comparison of the three most used map-matching algorithms for robot self-localization based on natural landmarks, namely our implementation of the Perfect Match (PM) and the Iterative Closest Point (ICP) along with the Normal Distribution Transform (NDT) available in the Point Cloud Library (PCL). Regarding the ICP algorithm, we introduce in this paper a new methodology for performing correspondence estimation using lookup tables that was inspired in the PM approach. This new method for computing the closest map point to a given sensor reading proved to be 40 to 60 times faster than the existing k-d tree approach used in the PCL implementation and allowed the ICP algorithm to perform point cloud registration 5 to 9 times faster. For the purpose of comparing the presented algorithms we have considered a set of representative metrics, such as the pose estimation accuracy, the computational e ciency, the convergence speed, the maximum admissible initialization error and the robustness to the presence of outliers in the robots sensors data. The test results were retrieved using our ROS natural landmark public dataset that contains several tests with simulated and real sensor data. The performance and robustness of the Perfect Match is highlighted throughout this article, showing its advantage for real-time embedded systems with limited computing power which require accurate pose estimation and fast reaction times when the robot is navigating at high speeds.

publication date

  • January 1, 2019