[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Critical Rays Scan Match SLAM

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

Abstract

Scan matching is one of the oldest and simplest methods for occupancy grid based SLAM. The general idea is to find the pose of a robot and update its map simply by calculating the 2-D transformation between a laser scan and its predecessor. Due to its simplicity many solutions were proposed and used in various systems, the vast majority of which are iterative. The fact is, that although scan matching is simple in its implementation, it suffers from accumulative noise. Of course, there is certainly a trade-off between the quality of results and the execution time required. Many algorithms have been introduced, in order to achieve good quality maps in a small iteration time, so that on-line execution would be achievable. The proposed SLAM scheme performs scan matching by implementing a ray-selection method. The main idea is to reduce complexity and time needed for matching by pre-processing the scan and selecting rays that are critical for the matching process. In this paper, several different methods of ray-selection are compared. In addition matching is performed between the current scan and the global robot map, in order to minimize the accumulated errors. RRHC (Random Restart Hill Climbing) is employed for matching the scan to the map, which is a local search optimization procedure that can be easily parameterized and is much faster than a traditional genetic algorithm (GA), largely because of the low complexity of the problem. The general idea is to construct a parameterizable SLAM that can be used in an on-line system that requires low computational cost. The proposed algorithm assumes a structured civil environment, is oriented for use in the RoboCup - RoboRescue competition, and its main purpose is to construct high quality maps.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Mingas, G. Tsardoulias, E. Petrou, L.: An FPGA implementation of the SMG-SLAM algorithm. Microprocess. Microsyst. 36(3), 190–204 (2012)

    Article  Google Scholar 

  2. Milstein, A.: Occupancy grid maps for localization and mapping: motion planning. In: Jing, X.-J. (ed.) InTech, pp. 381–408 (2008)

  3. Rusinkiewicz, S., Levoy, M.: Efficient variants of the ICP algorithm. In: Proceedings of the 3rd Intl. Conf. on 3D Digital Imaging and Modeling, p. 145152 (2001)

  4. Brenna, M.: Scan matching, covariance estimation and SLAM: models and solutions for the scanSLAM algorithm. Master Thesis, Politecnico di Milano (2008)

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

    Article  Google Scholar 

  6. Zhang, Z.: Iterative point matching for registration of free-form curves and surfaces. Int. J. Comput. Vis. 13(2), 119–152 (1994)

    Article  Google Scholar 

  7. Lu, F., Milios, E.: Robot pose estimation in unknown environments by matching 2D range scans. J. Intell. Robot. Syst. 18(3), 249–275 (1997)

    Article  Google Scholar 

  8. Diosi, A., Kleeman, L.: Laser scan matching in polar coordinates with application to SLAM. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2005), pp. 3317–3322 (2005)

  9. Ze-Su, C., Bing-Rong, H., Hong, L.: An improved polar scan matching using genetic algorithm. Inf. Technol. J. 6, 89–95 (2007)

    Article  Google Scholar 

  10. Montemerlo, M., Roy, N., Thrun, S., Hahnel, D., Stachniss, C., Glover, J.: CARMEN the carnegie mellon robot navigation toolkit. http://carmen.sourceforge.net (2002). Accessed 29 Oct 2011

  11. Grisetti, G., Stachniss, C., Burgard, W.: Improved techniques for grid mapping with Rao-Blackwellized particle filters. IEEE T. Robot. 23(1), pp. 34–46 (2007)

    Article  Google Scholar 

  12. Olson, E.B.: Real-time correlative scan matching. In: IEEE International Conference on Robotics and Automation ICRA 09, pp. 4387–4393 (2009)

  13. Martinez, J.L., Gonzalez, J., Morales, J., Mandow, A., Garcia-Cerezo, A.J.: Mobile robot motion estimation by 2D scan matching with genetic and iterative closest point algorithms. J. Field Robot. 23(1), pp. 21–34 (2006)

    Article  MATH  Google Scholar 

  14. Nieto, J., Bailey, T., Nebot, E.: Recursive scan-matching SLAM. Robot. Auton. Syst. 55(1), 39–49 (2007)

    Article  Google Scholar 

  15. Lakaemper, R., Adluru, N.: Force field simulation based laser scan alignment. In: Lazinica, A. (ed.) Recent Advances in Multi Robot Systems, InTech, pp. 326 (2008)

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

  17. Nunez, P., Vazquez-Martin, R., Bandera, A., Sandoval, F.: Fast laser scan matching approach based on adaptive curvature estimation for mobile robots. Robotica 27, 469–479 (2009)

    Article  Google Scholar 

  18. Sohn, H., Kim, B.: VecSLAM: an efficient vector-based SLAM algorithm for indoor environments. J. Intell. Robot. Syst. 56(3), 301–318 (2009)

    Article  MATH  Google Scholar 

  19. Cox, I.J.: Blanche-an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Trans. Robot. Autom. 7(2), 193–204 (1991)

    Article  Google Scholar 

  20. Taleghani, S. Sharbafi, M.A., Haghighat, A.T., Esmaeili, E.: ICE matching, a robust mobile robot localization with application to SLAM. Proc. ICTAI 1, 186–192 (2010)

    Google Scholar 

  21. Burgard, W., Stachniss, C., Grisetti, G., Steder, B., Kmmerle, R., Dornhege, C., Ruhnke, M., Kleiner, A., Tards, J.D.: A comparison of SLAM algorithms based on a graph of relations. In: Proceedings of IEEE/RSJ International Conference on Intelligent robots and systems, pp. 2089–2095. St. Louis, MO, USA (2009)

  22. Carpin, S., Lewis, M., Wang, J., Balakirsky, S., Scrapper, C.: USARSim: a robot simulator for research and education. IEEE International Conference on Robotics and Automation, pp. 1400–1405 (2007)

  23. Gerkey, B.P., Vaughan, R.T., Howard, A.: The player/stage project: tools for multi-robot and distributed sensor systems. In: Proceedings of the International Conference on Advanced Robotics (ICAR 2003), pp. 317–323 (2003)

  24. Russell S., Norvig, P.: Artificial intelligence: a modern approach 2nd edn. Ser. Prentice Hall series in Artificial Intelligence, Prentice Hall (2002)

  25. Antaris, S., Doulgeri, Z., Nikolaidis, G., Papadopoulos, C., Papanikas, G., Papazoglou, A., Petridis, V., Petrou, L., Serenis, C., Skolarikis, M., Tsalidis, P., Tsardoulias, E., Zolotas, C.: Program for the advancement of non-directed operating robotic agents. In: 19th International Conference on Automated Planning and Scheduling (ICAPS). Thessaloniki, Greece (2009)

  26. Howard A., Roy, N.: The robotics data set repository (radish). http://radish.sourceforge.net/ (2003). Accessed 22 May 2009

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, Division of Electronics and Computer Engineering, Faculty of Engineering, Aristotle University of Thessaloniki, 54124, Thessaloniki, Greece

    Emmanouil Tsardoulias & Loukas Petrou

Authors
  1. Emmanouil Tsardoulias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Loukas Petrou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Loukas Petrou.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tsardoulias, E., Petrou, L. Critical Rays Scan Match SLAM. J Intell Robot Syst 72, 441–462 (2013). https://doi.org/10.1007/s10846-012-9811-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-012-9811-5

Keywords