Skip to main content
SpringerLink
Log in

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

  • Published:
Journal of Intelligent & Robotic Systems Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Burguera, A., González, Y., Oliver, G.: Sonar scan matching by filtering scans using grids of normal distributions. Intell. Auton. Syst. 10, 64–73 (2008)

    Google Scholar 

  2. Besl, P.J., McKay, H.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239–256 (1992)

    Article  Google Scholar 

  3. Biber, P., Strasser, W.: The normal distributions transform: a new approach to laser scan matching. In: EEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 3, pp 2743–2748 (2003)

  4. Costa, C.M., Sobreira, H.M., Sousa, A.J., Veiga, G.M.: Robust 3/6 DoF self-localization system with selective map update for mobile robot platforms. Robot. Auton. Syst. 76, 113–140 (2016). ISSN 0921–8890

    Article  Google Scholar 

  5. Lauer, M., Lange, S., Riedmiller, M.: Calculating the perfect match: an efficient and accurate approach for robot self-localization, Rob. 2005 Robot soccer world cup, no. c, pp. 142–153 (2006)

  6. Magnusson, M., Lilienthal, A., Duckett, T.: Scan registration for autonomous mining vehicles using 3D-NDT. J. Field Rob. 24, 803–827 (2007)

    Article  Google Scholar 

  7. Magnusson, M.: The Three-Dimensional Normal-Distributions Transform - An Efficient Representation for Registration, Surface Analysis, and Loop Detection Örebro University (2009)

  8. Magnusson, M., Nuchter, A., Lorken, C., Lilienthal, A.J., Hertzberg, J.: Evaluation of 3D registration reliability and speed - A comparison of ICP and NDT. In: IEEE international conference on robotics and automation. ICRA 09 (2009)

  9. Meijster, A., Roerdink, J.B.T.M., Hesselink, W.H.: A general algorithm for computing distance transforms in linear time. In: Mathematical morphology and its applications to image and signal processing, pp 331–340 (2000)

  10. Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 286–307 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  11. Pinto, M., Sobreira, H., Paulo Moreira, A., Mendonça, H., Matos, A.: Self-localisation of indoor mobile robots using multi-hypotheses and a matching algorithm. Mechatronics 23(6), 727–737 (2013)

    Article  Google Scholar 

  12. Schulze, L., Wullner, A.: The approach of automated guided vehicle systems. In: 2006 IEEE international conference on service operations and logistics, and informatics, pp 522–527 (2006)

  13. Schulze, L., Behling, S., Buhrs, S.: Automated guided vehicle systems: a driver for increased business performance. In: Proceedings of the international multiconference of engineers and computer scientists, pp 19–21 (2008)

  14. Sobreira, H.M., Rocha, L., Costa, C.M., Lima, J., Costa, P., Moreira, A.P.: 2D cloud template matching - a comparison between iterative closest point and perfect match. In: 2016 IEEE international conference on autonomous robot systems and competitions (2016)

  15. Tomatis, N.: Bluebotics: navigation for the clever robot [Entrepreneur]. IEEE Robot. Autom. Mag. 18(2), 14–16 (2011)

    Article  Google Scholar 

Download references

Acknowledgments

The research leading to these results has received funding from the European Union’s Horizon 2020 - The EU Framework Programme for Research and Innovation 2014-2020, under grant agreement No. 688807. Project “TEC4Growth - Pervasive Intelligence, Enhancers and Proofs of Concept with Industrial Impact/NORTE-01-0145-FEDER-000020” is financed by the North Portugal Regional Operational. Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF). This work is also financed by the ERDF European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme, and by National Funds through the FCT Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project POCI-01-0145-FEDER-006961. This work is financed by the ERDF European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme, and by National Funds through the Portuguese funding agency, FCT -Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology), within project SAICTPAC/0034/2015- POCI-01-0145-FEDER-016418. The research leading to these results has received funding from the European Unions Horizon 2020 - The EU Framework Programme for Research and Innovation 20142020, under grant agreement No. 688807 ColRobot. P. C. M. A. Farias acknowledge support from CNPq/CsF PDE 233517/2014-6 for providing a scholarship.

Author information

Authors and Affiliations

  1. INESC-TEC, Rua Dr. Roberto Frias, 4200-465, Porto, Portugal

    Héber Sobreira, Carlos M. Costa, Ivo Sousa, Luis Rocha, José Lima, P. C. M. A. Farias, Paulo Costa & A. Paulo Moreira

  2. Polytechnic Institute of Bragança, Campus Sta Apolónia, 5301-857, Bragança, Portugal

    José Lima

  3. Polytechnic School of Federal University of Bahia, Rua Aristides Novis, 40210-630, Salvador, Brazil

    P. C. M. A. Farias

  4. Faculty of Engineering of University of Porto, Rua Dr. Roberto Frias, 4200-465, Porto, Portugal

    Paulo Costa & A. Paulo Moreira

Authors
  1. Héber Sobreira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos M. Costa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ivo Sousa
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luis Rocha
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. José Lima
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. P. C. M. A. Farias
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Paulo Costa
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. A. Paulo Moreira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Héber Sobreira.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sobreira, H., Costa, C.M., Sousa, I. et al. Map-Matching Algorithms for Robot Self-Localization: A Comparison Between Perfect Match, Iterative Closest Point and Normal Distributions Transform. J Intell Robot Syst 93, 533–546 (2019). https://doi.org/10.1007/s10846-017-0765-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-017-0765-5

Keywords

Search

Navigation