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

• Type: Article in International Scientific Journal
• Date: 2019

Authors

Héber Sobreira (Author) Other; Carlos M. Costa (Author) Other; Ivo Sousa (Author) Other; Luís Rocha (Author) FEUP; José Lima (Author) Other; Paulo C. M. A. Farias (Author) Other; Paulo Gomes da Costa (Author) FEUP; António Paulo Moreira (Author) FEUP

Journal

Title: Journal of Intelligent and Robotic Systems: Theory and Applications

Vol. 93 No. 3-4

Pages: 533-546

ISSN: 0921-0296

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 56 Citations

Scopus - 60 Citations

INSPEC

Other information

Authenticus ID: P-00N-H8M

DOI: 10.1007/s10846-017-0765-5

Abstract (EN): The self-localization of mobile robots in the environment is one of the most fundamental problems in the robotics navigation field. It is a complex and challenging problem due to the high requirements of autonomous mobile vehicles, particularly with regard to the algorithms accuracy, robustness and computational efficiency. In this paper, we present a comparison of three of the most used map-matching algorithms applied in localization based on natural landmarks: our implementation of the Perfect Match (PM) and the Point Cloud Library (PCL) implementation of the Iterative Closest Point (ICP) and the Normal Distribution Transform (NDT). For the purpose of this comparison we have considered a set of representative metrics, such as pose estimation accuracy, computational efficiency, convergence speed, maximum admissible initialization error and robustness to the presence of outliers in the robots sensors data. The test results were retrieved using our ROS natural landmark public dataset, containing several tests with simulated and real sensor data. The performance and robustness of the Perfect Match is highlighted throughout this article and is of paramount importance for real-time embedded systems with limited computing power that require accurate pose estimation and fast reaction times for high speed navigation. Moreover, we added to PCL a new algorithm for performing correspondence estimation using lookup tables that was inspired by the PM approach to solve this problem. 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 in PCL and allowed the Iterative Closest Point algorithm to perform point cloud registration 5 to 9 times faster.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14