A Review: Simultaneous Localization and Mapping Algorithms

Authors

  • Saif Eddine Hadji Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Suhail Kazi Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Tang Howe Hing Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia
  • Mohamed Sultan Mohamed Ali Faculty of Electrical Engineering, Universiti Teknologi Malaysia, 81310 UTM Johor Bahru, Johor, Malaysia

DOI:

https://doi.org/10.11113/jt.v73.4188

Keywords:

SLAM, localization, mapping, Kalman filter, particle filtre

Abstract

Simultaneous Localization and Mapping (SLAM) involves creating an environmental map based on sensor data, while concurrently keeping track of the robot’s current position. Efficient and accurate SLAM is crucial for any mobile robot to perform robust navigation. It is also the keystone for higher-level tasks such as path planning and autonomous navigation. The past two decades have seen rapid and exciting progress in solving the SLAM problem together with many compelling implementations of SLAM methods. In this paper, we will review the two common families of SLAM algorithms: Kalman filter with its variations and particle filters. This article complements other surveys in this ï¬eld by reviewing the representative algorithms and the state-of-the-art in each family. It clearly identifies the inherent relationship between the state estimation via the KF versus PF techniques, all of which are derivations of Bayes rule.

References

Rodrigo, R. Chen, Z. and Samarabandu, J. 2006. Feature Motion for Monocular Robot Navigation. In 2006 International Conference on Information and Automation. 201–205.

Burgard, W. Stachniss, C. and Dirk, H. 2007. Mobile Robot Map Learning from Range Data in Dynamic Environments. In Autonomous Navigation in Dynamic Environments. L. Christian and R. Chatila, Eds. Springer Berlin Heidelberg. 35: 3–28.

Eric, J. Thorn, L. 2009. Autonomous Motion Planning Using A Predictive Temporal Method. University of Florida.

Smith, R. Self, M. and Cheeseman, P. 1990. Autonomous Robot Vehicles. New York, NY: Springer New York. 167–193.

Ayache, N. and Faugeras, O. D. 1989. Maintaining Representations of the Environment of a Mobile Robot. IEEE Trans. Robot. Autom. 5(6): 804–819.

Chatila, R. and Laumond, J. 1985. Position Referencing and Consistent World Modeling for Mobile Robots. In Proceedings. 1985 IEEE International Conference on Robotics and Automation. 2: 138–145.

Durrant-Whyte, H. and Bailey, T. 2006. Simultaneous Localization and Mapping: Part I. IEEE Robot. Autom. Mag. 13(2): 99–110.

Bailey, T. and Durrant-Whyte, H. 2006. Simultaneous Localization and Mapping (SLAM): Part II. IEEE Robot. Autom. Mag. 13(3): 108–117.

Thrun, S. Burgard, W. and Fox, D. 1998. A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots. Auton. Robots. 5(3–4): 253–271.

Xi, B. Guo, Sun, R. F. and Huang, Y. 2008. Simulation research for active Simultaneous Localization and Mapping based on Extended Kalman Filter. In 2008 IEEE International Conference on Automation and Logistics. 2443–2448.

Diosi, A. and Kleeman, L. 2004. Advanced Sonar and Laser Range Finder Fusion for Simultaneous Localization and Mapping. In 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No.04CH37566). 2: 1854–1859.

Thrun, S. 2002. Probabilistic robotics. Commun. ACM. 45(3): 1999–2000.

Hahnel, D. Burgard, W. Fox, D. and Thrun, S. 2003. An Efficient Fastslam Algorithm for Generating Maps of Large-scale Cyclic Environments from Raw Laser Range Measurements. In Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453). 1: 206–211.

Montemerlo, M. 2003. FastSLAM : A Factored Solution to the Simultaneous Localization and Mapping Problem With Unknown Data Association. Doctoral Dissertation, Tech. Report CMU-RI-TR-03-28, Robotics Institute, Carnegie Mellon University, July.

Estrada, C. Neira, J. and Tardos, J. D. 2005. Hierarchical SLAM: Real-time Accurate Mapping of Large Environments. IEEE Trans. Robot. 21(4): 588–596.

Cheng, G. 2006. Vision-based Mobile Robot Navigation : A Qualitative Approach. Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA. 2686–2692.

Z. Chen, J. Samarabandu, R. Rodrigo. 2007. Recent Advances in Simultaneous Localization and Map-building Using Computer vision. In Advanced Robotics. 21(3–4): 233–265.

Paz, L. M. Jensfelt, P. Tardos, J. D. and Neira, J. 2007. EKF SLAM updates in O(n) with Divide and Conquer SLAM. In Proceedings 2007 IEEE International Conference on Robotics and Automation. 1657–1663.

R. Siegwart,R. Nourbakhsh. 2004. Introduction to Autonomous Mobile Robots. In Bradford Book, The MIT Press.

Josep, A. Yvan, P. Joaquim, S. and Xavier, L. 2008. The SLAM Problem: A Survey. In proceeding of: Artificial Intelligence Research and Development, Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2008, October 22–24, Sant Martí d'Empúries, Spain.

Williams, S. B. Newman, P. Dissanayake, G. and Durrant-Whyte, H. 2000. Autonomous Underwater Simultaneous Localisation and Map Building. In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065). 2: 1793–1798.

Leonard, P. N. J. 2003. Consistent, Convergent, and Constant-time Slam. In proceeding of: IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15. 1143–1150.

Eustice, R. M. Singh, H. Leonard, J. J. and Walter, M. R. 2006. Visually Mapping the RMS Titanic: Conservative Covariance Estimates for SLAM Information Filters. Int. J. Rob. Res. 25(12): 1223–1242.

Pizarro, O. Eustice, R. and Singh, H. 2004. Large Area 3d Reconstructions from Underwater Surveys. In Oceans ’04 MTS/IEEE Techno-Ocean '04 (IEEE Cat. No.04CH37600). 2: 678–687.

Jensfelt, P. Kragic, D. Folkesson, J. and Bjorkman, M. 2006. A Framework for Vision Based Bearing Only 3D SLAM. In Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. 1944–1950.

Cheein, F. A. A. Lopez, N. Soria, C. di Sciascio, M. F. A. Pereira, F. L. and Carelli, R. 2010. SLAM Algorithm Applied to Robotics Assistance for Navigation in Unknown Environments. J. Neuroeng. Rehabil. 7(1): 10.

Davison, A. J. and Murray, D. W. 2002. Simultaneous Localization and Map-Building Using Active Vision. IEEE Trans. Pattern Anal. Mach. Intell. 24(7): 865–880.

Se, S. Lowe, D. and Little, J. 2002. Mobile Robot Localization and Mapping with Uncertainty using Scale-Invariant Visual Landmarks. Int. J. Rob. Res. 21(8): 735–758.

Thrun, S. and Liu, Y. 2005. Multi-robot SLAM with Sparse Extended Information Filers. Springer Tracts in Advanced Robotics Robotics Research. The Eleventh International Symposium. 15: 254–266.

Thrun, S. Martin, C. Liu, Y. Hahnel, D. Emery-Montemerlo, R. Chakrabarti, D. and Burgard, W. 2004. A Real-Time Expectation-Maximization Algorithm for Acquiring Multiplanar Maps of Indoor Environments With Mobile Robots. IEEE Trans. Robot. Autom. 20(3): 433–442.

Matthew Walter, J. L.and Eustice, R. “A Provably Consistent Method for Imposing Sparsity in Feature-Based SLAM Information Filters,†Springer Tracts Adv. Robot., vol. 28, no. 2007, p. pp 214–234, 2007.

Guivant, J. E. and Nebot, E. M. 2001. Optimization of the Simultaneous Localization and Map-building Algorithm for Real-time Implementation. IEEE Trans. Robot. Autom. 17(3): 242–257.

Metropolis, N. and Ulam, S. 1949. The Monte Carlo Method. Journal of the American Statistical Association. 44(247): 335–341.

Pitt, M. K. and Shephard, N. 1999. Filtering via Simulation: Auxiliary Particle Filters. J. Am. Stat. Assoc. 94(446): 590–599.

Blackwell, D. 1947. Conditional Expectation and Unbiased Sequential Estimation. Ann. Math. Stat. 18(1): 105–110.

Doucet, A. de Freitas, N. Murphy, K. P. and Russell, S. J. 2000. Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks. 176–183.

Thrun, S. Hahnel, D. Ferguson, D. Montemerlo, M. Triebel, R. Burgard, W. Baker, C. Omohundro, Z. Thayer, S. and Whittaker, W. 2003. A System for Volumetric Robotic Mapping of Abandoned Mines. In 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422). 3: 4270–4275.

Montemerlo, M. Thrun, S. and Siciliano, B. 2007. FastSLAM: A Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics. Springer Tracts in Advanced Robotics. 27.

Oh, S. Hahn, M. and J. Kim, 2013. Simultaneous Localization and Mapping for Mobile Robots in Dynamic Environments. 2013 Int. Conf. Inf. Sci. Appl. 1–4.

Wolfram Burgard, D. F. 1999. Sonar-Based Mapping of Large-Scale Mobile Robot Environments using EM'. In ICML '99 Proceedings of the Sixteenth International Conference on Machine Learning. 67–76.

Anon. 2004. Real-Time 3D SLAM with Wide-Angle Vision. In: 5th IFAC/EURON Symposium on Intelligent Autonomous Vehicles.

Downloads

Published

2015-03-09

Issue

Vol. 73 No. 2: Special Issue on International Conference of Recent Trends in Information and Communication Technology (IRICT 2014)

Section

Science and Engineering

License

Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.

How to Cite

A Review: Simultaneous Localization and Mapping Algorithms. (2015). Jurnal Teknologi, 73(2). https://doi.org/10.11113/jt.v73.4188