IEEE Robotics & Automation Magazine - June 2013 - 51

they require some benchmarking suited to the specific
problem conditions and size, as noted in the section
"Graph Optimization." In light of recent results [21],
[25], further study of updated CPU hardware (Core i7)
together with other more efficient CPU exact solvers is
also required.
Many existing open-source tools and data sets are
used in this work. Consequently, the entire C++ source
code for the algorithms presented in this article can be
found in [18], in the spirit that it will also be useful for
the community.
Acknowledgments
The authors would like to thank all the open-source tool
and data set providers: CARMEN grid mapping [14], CNC
[23], Alglib [26], and SuperLU [22]. Data sets Fr079 and
Fr101 are obtained from Radish [16] (thanks to C. Stachniss), the TORO algorithm and its data sets are taken from
[24], and thanks go to G. Grisetti. This work was supported
in part by the Spanish R&D National Program (Project
Robonauta Ref: DPI2007-66848-C02-01 and project
ARABOT, Ref: DPI 2010-21247-C02-01) and supervised by
CACSA, whose kindness we gratefully acknowledge.
References

[1] S. Thrun and J. Leonard, "Simultaneous localization and mapping," in
Handbook Robotics, B. Siciliano and O. Khatib, Eds. New York: Springer-Verlag, 2008, ch. 37.
[2] H. Durrant-Whyte and T. Bailey, "Simultaneous localisation and mapping
(SLAM): Part I the essential algorithms," IEEE Robot. Autom. Mag., vol. 13, no.
2, pp. 99-110, 2006.
[3] F. Wörsdörfer, F. Stock, E. Bayro-Corrochano, and D. Hildenbrand, "Optimizations and performance of a robotics grasping algorithm described in geometric algebra," in Progress Pattern Recognition, Image Analysis, Computer
Vision, Applications (Lecture Notes Computer Science), vol. 5856.
New York: Springer-Verlag, 2009, pp. 263-271.
[4] P. Michel, J. Chestnutt, S. Kagami, K. Nishiwaki, J. Kuffner, and T. Kanade,
"GPU-accelerated real-time 3D tracking for humanoid locomotion and stair
climbing," in Proc. IEEE/RSJ Int. Conf. Intelligent Robots Systems, 2007,
pp. 463-469.
[5] B. Charmette, E. Royer, and F. Chausse, "Efficient planar features matching
for robot localization using GPU," in Proc. 2010 IEEE Computer Society Conf.
Computer Vision Pattern Recognition Workshops, pp. 16-23.
[6] J. F. Ferreira, J. Lobo, and J. Dias, "Bayesian real-time perception algorithms on GPU," J. Real-Time Image Process., vol. 6, no. 3, pp. 171-186, 2001.
[7] (Dec. 2012). Institute for Computer Graphics and Vision, Graz University
of Technology. Gpu4Vision project. [Online]. Available: www.gpu4vision.org
[8] M. Yguel, O. Aycard, and C. Laugier, "Efficient GPU-based construction of
occupancy grids using several laser range-finders," Int. J. Veh. Auton. Syst.,
vol. 6, nos. 1-2, pp. 48-83, 2008.
[9] D. Borrmann, J. Elseberg, K. Lingemann, A. Nüchter, and J. Hertzberg,
"Globally consistent 3D mapping with scan matching." J. Robot. Auton. Syst.
Elsevier Sci., vol. 56, no. 2, pp. 130-142, 2008.
[10] D. Qiu, S. May, and A. Nüchter, "GPU-accelerated nearest neighbor search for
3D registration," in Proc. Int. Conf. Computer Vision Systems, 2009, pp. 194-203.
[11] Willow Garage. (Dec. 2012). ROS support for CUDA. [Online]. Available:
http://www.ros.org/wiki/gpgpu
[12] A. Elfes, "Sonar-based real-world mapping and navigation," IEEE J. Robot.
Autom., vol. 3, no. 3, pp. 249-265, 1987.

[13] S. Thrun, A. Bücken, W. Burgard, D. Fox, T. Fröhlinghaus, D. Henning, T.
Hofmann, M. Krell, and T. Schmidt, "Map learning and high-speed navigation
in RHINO," in AI-Based Mobile Robots: Case Studies Successful Robot Systems.
Cambridge, MA: MIT Press, 1998.
[14] (Dec. 2012). CARMEN, The Carnegie Mellon Robot Navigation Toolkit.
[Online]. Available: http://carmen.sourceforge.net
[15] J. E. Bresenham, "Algorithm for computer control of a digital plotter,"
IBM Syst. J., vol. 4, no. 1, pp. 25-30, 1996.
[16] C. Stachniss. (Dec. 2012). Radish, the robotics data set repository.
[Online]. Available: http://radish.sourceforge.net
[17] D. Rodriguez-Losada, P. de la Puente, A. Valero, P. San Segundo, and M.
Hernando, "Fast processing of grid maps using graphical multiprocessors," in
Proc. 7th IFAC Symp. Intelligent Autonomous Vehicles, 2010, vol. 7, pp. 1-6.
[18] D. Rodriguez-Losada. (Dec. 2012). Source code for this paper. [Online].
Available: www.intelligentcontrol.es/diego/gpumapping
[19] F. Lu and E. Milios, "Globally consistent range scan alignment for environment mapping," Auton. Robots, vol. 4, no. 4, pp. 333-349, 1997.
[20] G. Grisetti, C. Stachniss, S. Grzonka, and W. Burgard, "A tree parameterization for efficiently computing maximum likelihood maps using gradient
descent," in Proc. Robotics: Science System, Atlanta, GA, 2007, pp. 1-8.
[21] G. Grisetti, R. Kummerle, C. Stachniss, U. Frese, and C. Hertzberg, "Hierarchical optimization on manifolds for online 2D and 3D mapping," in Proc.
IEEE Int. Conf. Robotics Automation, 2010, pp. 273-278.
[22] J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, and J. W. H. Liu, "A
supernodal approach to sparse partial pivoting," SIAM J. Matrix Anal. Appl.,
vol. 20, no. 3, pp. 720-755, 1999.
[23] L. Buatoisab, G. Caumona, and B. Levy, "Concurrent number cruncher: A
GPU implementation of a general sparse linear solver," Int. J. Parallel, Emergent Distrib. Syst., vol. 24, no. 3, pp. 205-223, 2009.
[24] C. Stachniss, U. Frese, and G. Grisetti. OpenSLAM. (Dec. 2012). [Online].
Available: http://www.openslam.org
[25] K. Konolige, G. Grisetti, R. Kummerle, W. Burgard, B. Limketkai, and R.
Vincent, "Sparse pose adjustment for 2D mapping," in Proc. IROS, 2010, pp.
22-29.
[26] S. Bochkanov. (Dec. 2012). ALGLIB software library. L-BFGS C++ implementation. [Online]. Available: http://www.alglib.net
[27] D. Rodriguez-Losada, P. de la Puente, A. Valero, P. San Segundo, and M.
Hernando, "Computation of the optimal relative pose between overlapping
grid maps through discrepancy minimization," in Proc. 7th IFAC Symp. Intelligent Autonomous Vehicles, 2010, vol. 7, pp. 1-6.
[28] S. Huang, S. Xiao, and W. Feng, "On the energy efficiency of graphics processing units for scientific computing," in Proc. IEEE Int. Symp. Parallel Distributed Processing, 2009, pp. 1-8.

Diego Rodriguez-Losada, EUIT Industriales, Universidad
Politecnica de Madrid, Madrid, Spain. E-mail: diego.rlosada@
upm.es.
Pablo San Segundo, Escuela Técnica Superior de Ingenieros
Industriales, Universidad Politecnica de Madrid, Madrid,
Spain. E-mail: pablo.sansegundo@upm.es.
Miguel Hernando, Universidad Politecnica de Madrid,
Madrid, Spain. E-mail: miguel.hernando@upm.es.
Paloma de la Puente, Universidad Politecnica de Madrid,
Madrid, Spain. E-mail: paloma.py@gmail.com.
Alberto Valero-Gomez, Universidad Carlos III de Madrid,
Madrid, Spain. E-mail: alberto.valero.gomez@gmail.com.

june 2013

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

51
http://carmen.sourceforge.net http://radish.sourceforge.net http://www.intelligentcontrol.es/diego/gpumapping http://www.openslam.org http://www.alglib.net http://www.gpu4vision.org http://www.ros.org/wiki/gpgpu
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2013
