Abstract
This paper models the complex simultaneous localization and mapping (SLAM) problem through a very flexible Markov random field and then solves it by using the iterated conditional modes algorithm. Markovian models allow to incorporate: any motion model; any observation model regardless of the type of sensor being chosen; prior information of the map through a map model; maps of diverse natures; sensor fusion weighted according to the accuracy. On the other hand, the iterated conditional modes algorithm is a probabilistic optimizer widely used for image processing which has not yet been used to solve the SLAM problem. This iterative solver has theoretical convergence regardless of the Markov random field chosen to model. Its initialization can be performed on-line and improved by parallel iterations whenever deemed appropriate. It can be used as a post-processing methodology if it is initialized with estimates obtained from another SLAM solver. The applied methodology can be easily implemented in other versions of the SLAM problem, such as the multi-robot version or the SLAM with dynamic environment. Simulations and real experiments show the flexibility and the excellent results of this proposal.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
H. Durrant-Whyte, T. Bailey. Simultaneous localization and mapping: Part I. IEEE Robotics & Automation Magazine, vol. 13, no. 2, pp. 99–110, 2006. DOI: 10.1109/ MRA.2006.1638022.
T. Bailey, H. Durrant-Whyte. Simultaneous localization and mapping (SLAM): Part II. IEEE Robotics & Automation Magazine, vol. 13, no. 3, pp. 108–117, 2006. DOI: 10.1109/MR.2006.1678144.
T. S. Ho, Y. C. Fai, E. S. L. Ming. Simultaneous localization and mapping survey based on filtering techniques. In Proceedings of the 10th Asian Control Conference, IEEE, Kota Kinabalu, Malaysia, pp. 1–6, 2015.
X. C. Zhang, B. Li, S. L. Joseph, J. Z. Xiao, Y. Sun, Y. L. Tian, J. P. Muñoz, C. C. Yi. A SLAM based semantic indoor navigation system for visually impaired users. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, IEEE, Hong Kong, China, pp. 1458–1463, 2015.
C. Arth, C. Pirchheim, J. Ventura, D. Schmalstieg, V. Lepetit. Instant outdoor localization and SLAM initialization from 2.5D maps. IEEE Transactions on Visualization and Computer Graphics, vol. 21, no. 11, pp. 1309–1318, 2015. DOI: 10.1109/TVCG.2015.2459772.
J. Kim. Aerial inertial-slam: Progresses and future challenges. In Proceedings of the 12th International Conference on Ubiquitous Robots and Ambient Intelligence, IEEE, Goyang, South Korea, pp. 212–213, 2015.
[7]L. Paull, S. Saeedi, M. Seto, H. Li. AUV navigation and localization: A review. IEEE Journal of Oceanic Engineering, vol. 39, no. 1, pp. 131–149, 2014. DOI: 10.1109/JOE. 2013.2278891.
F. Hidalgo, T. Bräunl. Review of underwater SLAM techniques. In Proceedings of the 6th International Conference on Automation, Robotics and Applications, IEEE, Queenstown, New Zealand, pp. 306–311, 2015.
C. L. Wang, T. M. Wang, J. H. Liang, Y. C. Zhang, Y. Zhou. Bearing-only visual SLAM for small unmanned aerial vehicles in GPS-denied environments. International Journal of Automation and Computing, vol. 10, no. 5, pp. 387–396, 2013. DOI: 10.1007/s11633-013-0735-8.
D. Y. Bi, Y. L. Yu, Y. Shen, C. Melchiorri. Implementation of trapped personnel detection and evacuation guidance in indoor fire scene based on quadrotor UAV. In Proceedings of International Conference on Intelligent Control and Computer Application, Zhengzhou, China, pp. 57–62, 2016.
S. Thrun, W. Burgard, D. Fox. Probabilistic Robotics (Intelligent Robotics and Autonomous Agents), Cambridge, Mass, UK: The MIT Press, 2005.
C. De la Cruz, T. Freire Bastos, F. A. Auat Cheein, R. Carelli. SLAM-based robotic wheelchair navigation system designed for confined spaces. In Proceedings of IEEE International Symposium on Industrial Electronics, IEEE, Taipei, China, pp. 2331–2336, 2010.
F. Auat Cheein, G. Steiner, G. P. Paina, R. Carelli. Optimized EIF-SLAM algorithm for precision agriculture mapping based on stems detection. Computers and Electronics in Agriculture, vol. 78, no. 2, pp. 195–207, 2011. DOI: 10.1016/j.compag.2011.07.007.
Y. Lee, J. Choi, H. T. Choi. Experimental results of real-time sonar-based underwater localization using landmarks. In Proceedings of MTS/IEEE Washington OCEANS’15, IEEE, Washington DC, USA, 2015.
M. R. Nepali, N. Yadav, U. Dev, S. Mishra, S. L. Shrestha. A strategic methodology for 2D map building in an Indoor environment. In Proceedings of the 1st International Conference on Next Generation Computing Technologies, IEEE, Washington DC, USA, pp. 797–803, 2015.
J. Fuentes-Pacheco, J. Ruiz-Ascencio, J. M. Rendón-Mancha. Visual simultaneous localization and mapping: A survey. Artificial Intelligence Review, vol. 43, no. 1, pp. 55–81, 2015. DOI: 10.1007/s10462-012-9365-8.
S. C. Zhou, R. Yan, J. X. Li, Y. K. Chen, H. J. Tang. A brain-inspired SLAM system based on ORB features. International Journal of Automation and Computing, vol. 14, no. 5, pp. 564–575, 2017. DOI: 10.1007/s11633-017-1090-y.
L. T. Hsu, Y. Wada, Y. L. Gu, S. Kamijo. Rectification of 3D building models based on GPS signal collected by vehicle. In Proceedings of IEEE International Conference on Vehicular Electronics and Safety, IEEE, Yokohama, Japan, pp. 132–139, 2015.
C. S. Jiang, D. P. Paudel, Y. Fougerolle, D. Fofi, C. Demonceaux. Static-map and dynamic object reconstruction in outdoor scenes using 3-D motion segmentation. IEEE Robotics and Automation Letters, vol. 1, no. 1, pp. 324–331, 2016. DOI: 10.1109/LRA.2016.2517207.
G. Bresson, R. Aufrére, R. Chapuis. A general consistent decentralized simultaneous localization and mapping solution. Robotics and Autonomous Systems, vol. 74, pp. 128–147, 2015. DOI: 10.1016/j.robot.2015.07.008.
S. Saeedi, M. Trentini, M. Seto, H. Li. Multiple-robot simultaneous localization and mapping: A review. Journal of Field Robotics, vol. 33, no. 1, pp. 3–46, 2016. DOI: 10.1002/rob.21620.
S. Dominguez, B. Khomutenko, G. Garcia, P. Martinet. An optimization technique for positioning multiple maps for self-driving car’s autonomous navigation. In Proceedings of the 18th International Conference on Intelligent Transportation Systems, IEEE, Las Palmas, Spain, pp. 2694–2699, 2015.
G. P. Huang, A. I. Mourikis, S. I. Roumeliotis. A quadratic-complexity observability-constrained unscented Kalman filter for SLAM. IEEE Transactions on Robotics, vol. 29, no. 5, pp. 1226–1243, 2013. DOI: 10.1109/TRO. 2013.2267991.
J. A. Hesch, D. G. Kottas, S. L. Bowman, S. I. Roumeliotis. Consistency analysis and improvement of vision-aided inertial navigation. IEEE Transactions on Robotics, vol. 30, no. 1, pp. 158–176, 2014. DOI: 10.1109/TRO.2013. 2277549.
I. J. Cox. A review of statistical data association techniques for motion correspondence. International Journal of Computer Vision, vol. 10, no. 1, pp. 53–66, 1993. DOI: 10.1007/BF01440847.
M. Adams, B. N. Vo, R. Mahler, J. Mullane. SLAM gets a PHD: New concepts in map estimation. IEEE Robotics & Automation Magazine, vol. 21, no. 2, pp. 26–37, 2014.
P. J. Huber. Robust Statistics, New York, USA: Wiley, 1981.
R. Smith, M. Self, P. Cheeseman. A stochastic map for uncertain spatial relationships. In Proceedings of the 4th International Symposium on Robotics Research, Santa Clara, USA, pp. 467–474, 1987.
P. Moutarlier, R. Chatila. Stochastic multisensory data fusion for mobile robot location and environment modeling. In Proceedings of the 5th International Symposium on Robotics Research, Tokyo, Japan, pp. 85–94, 1989.
M. Montemerlo, S. Thrun, D. Koller, B. Wegbreit. Fast-SLAM: A factored solution to the simultaneous localization and mapping problem. In Proceedings of AAAI National Conference on Artificial Intelligence, Menlo Park, USA, pp. 593–598, 2002.
T. Z. Lv, C. X. Zhao, H. F. Zhang. An improved Fast-SLAM algorithm based on revised genetic resampling and SR-UPF. International Journal of Automation and Computing, Online First. DOI: 10.1007/s11633-016-1050-y.
M. A. Paskin. Thin junction tree filters for simultaneous localization and mapping. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, San Francisco, USA, pp. 1157–1164, 2003.
F. Dellaert, M. Kaess. Square root SAM: Simultaneous localization and mapping via square root information smoothing. International Journal of Robotics Research, vol. 25, no. 12, pp. 1181–1203, 2006. DOI: 10.1177/ 0278364906072768.
M. Jadaliha, J. Choi. Fully Bayesian simultaneous localization and spatial prediction using Gaussian Markov random fields (GMRFs). In Proceedings of the American Control Conference, IEEE, Washington DC, USA, pp. 4592–4597, 2013.
[35]Z. L. Xiao, H. K. Wen, A. Markham, N. Trigoni. Indoor tracking using undirected graphical models. IEEE Transactions on Mobile Computing, vol. 14, no. 11, pp. 2286–2301, 2015. DOI: 10.1109/TMC.2015.2398431.
J. Nocedal, S. J. Wright, Numerical Optimization, Berlin, Germany: Springer Verlag, 2006.
D. M. Rosen, C. DuHadway, J. J. Leonard. A convex relaxation for approximate global optimization in simultaneous localization and mapping. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Seattle, USA, pp. 5822–5829, 2015.
R. A. Brooks. Elephants don’t play chess. Robotics and Autonomous Systems, vol. 6, no. 1–2, pp. 3–15, 1990. DOI: 10.1016/S0921-8890(05)80025-9.
R. G. Cowell, P. A. Dawid, S. L. Lauritzen, D. J. Spiegelhalter. Probabilistic Networks and Expert Systems, New York, USA: Springer, 1999.
J. Folkesson, H. Christensen. Graphical SLAM-a self-correcting map. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, New Orleans, USA, vol. 1, pp. 383–389, 2004.
J. Sola. Course on SLAM, Technical Report, Robotics Institute and Industrial Computing, Polytechnic University of Catalonia, Barcelona, Spain, 2016.
S. Thrun, D. Koller, Z. Ghahramani, H. Durrant-Whyte, A. Y. Ng. Simultaneous Mapping and Localization with Sparse Extended Information Filters: Theory and Initial Results, Technical Report CMU-CS-02-112, Carnegie Mellon University, Pittsburgh, USA, 2002.
G. Dissanayake, S. B. Williams, H. Durrant-Whyte, T. Bailey. Map management for efficient simultaneous localization and mapping (SLAM). Autonomous Robots, vol. 12, no. 3, pp. 267–286, 2002. DOI: 10.1023/A: 1015217631658.
Y. Latif, C. Cadena, J. Neira. Robust graph SLAM back-ends: A comparative analysis. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Chicago, USA, pp. 2683–2690, 2014.
N. Carlevaris-Bianco, M. Kaess, R. M. Eustice. Generic node removal for factor-graph SLAM. IEEE Transactions on Robotics, vol. 30, no. 6, pp. 1371–1385, 2014. DOI: 10.1109/TRO.2014.2347571.
B. Suger, G. D. Tipaldi, L. Spinello, W. Burgard. An approach to solving large-scale slam problems with a small memory footprint. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Hong Kong, China, pp. 3632–3637, 2014.
M. Mazuran, G. D. Tipaldi, L. Spinello, W. Burgard. Nonlinear graph sparsification for SLAM. In Proceedings of Robotics: Science and Systems, Daejeon Convention Center, Berkeley, USA, 2014.
S. Choudhary, V. Indelman, H. I. Christensen, F. Dellaert. Information-based reduced landmark SLAM. In Proceedings of IEEE International Conference on Robotics and Automation, IEEE, Seattle, USA, pp. 4620–4627, 2015.
R. Kindermann, J. L. Snell. Markov Random Fields and Their Applications, Providence, USA: American Mathematical Society, 1980.
S. Z. Li. Markov Random Field Modeling in Image Analysis, 3rd ed., London, UK: Springer, 2009.
J. Besag. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, vol. 48, no. 3, pp. 259–302, 1986.
J. M. Hammersley, P. Clifford. Markov fields on finite graphs and lattices, Technical Report, University of California, Berkeley, USA, 1971.
S. Geman, D. Geman. Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721–741, 1984.
A. Gelman, C. Robert, N. Chopin, J. Rousseau. Bayesian Data Analysis, London, UK: Chapman & Hall, 1995.
S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi. Optimization by simulated annealing. Science, vol. 220, no. 4598, pp. 671–680, 1983. DOI: 10.1126/science.220.4598.671.
V. Cerný. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, vol. 45, no. 1, pp. 41–51, 1985. DOI: 10.1007/BF00940812.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Council for Scientific and Technological Research (CONICET) and the National University of San Juan (UNSJ).
J. Gimenez received the B. Sc. degree in mathematics from the National University of San Juan (UNSJ),Argentina in 2009, and the Ph. D. degree in mathematics from the National University of Córdoba (UNC), Argentina in 2014. Currently, he is an assistant researcher of the Argentinean National Council for Scientific Research (CONICET), and an adjunct professor in the Institute of Automatics, Argentina
His research interests include probabilistic and statistical implementations of robotics, such as simultaneous localization and mapping (SLAM) algorithms.
A. Amicarelli received the B. Eng. degree in chemical engineering from the National University of San Juan, Argentina in 2000, and the Ph. D. degree in control systems from the Institute of Automatics (INAUT) of the same university in 2007. Her main works are related with state estimations of complex non-linear systems and with bioprocess control. She is an assistant researcher of the Argentinean National Council for Scientific Research from 2012.
Her research interests include systems modeling, process control and state estimation to control porpoises.
J. M. Toibero received the B. Eng degree in electronic engineering from the Facultad Tecnológica Nacional of Argentina, Argentina in 2002, and the Ph. D. degree in control systems from the Institute of Automatics at the National University of San Juan, Argentina in 2007. His main works are related to nonlinear control of robotic platforms and robotics applications in agriculture. He is with the National Council for Scientific and Technological Research of Argentina since 2011, actually he is an adjunct researcher. He leads different technological projects and his current scientific research is at the Institute of Automatics of San Juan, Argentina.
His research interests include wheeled mobile robots, manipulators force/impedance, switched, hybrid, nonlinear control methods applied to automatic control and visual servoing.
F. di Sciascio received the B. Sc. degree in electromechanical engineering with orientation in electronics from the National University of Buenos Aires (UBA), Argentina in 1986. He received the M. Sc. degree in engineering of control systems, and the Ph. D. degree in engineering, from the Institute of Automatics, National University of San Juan, Argentina in 1994 and 1997, respectively. Since 1987, he is a professor and researcher at the INAUT and he is currently a full professor in charge of the subjects artificial intelligence complements and identification and adaptive control in the Department of Electronics and Automation. At the same time, he is a professor of the postgraduate degree at the INAUT, Argentina.
His research interests include modelling, identification and estimation in dynamical systems, and technology developments in automatic process control.
R. Carelli received the B. Sc. degree in engineering from the National University of San Juan, Argentina in 1976, and received the Ph. D. degree in electrical engineering from the National University of Mexico (UNAM), Mexico in 1989. He is a full professor at the National University of San Juan and a senior researcher of the National Council for Scientific and Technical Research, Argentina. He is director of the Automatics Institute, National University of San Juan, Argentina. He is a senior member of IEEE and a member of Argentine Association of Automatic Control - International Federation of Automatic Control (AADECA-IFAC).
His research interests include robotics, manufacturing systems, adaptive control and artificial intelligence applied to automatic control.
Rights and permissions
About this article
Cite this article
Gimenez, J., Amicarelli, A., Toibero, J.M. et al. Iterated Conditional Modes to Solve Simultaneous Localization and Mapping in Markov Random Fields Context. Int. J. Autom. Comput. 15, 310–324 (2018). https://doi.org/10.1007/s11633-017-1109-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11633-017-1109-4