Parallel implementation of mobile robotic self-localization
Authors: 
Priscila Tiemi Maeda Saito, Denis Fernando Wolf, Kalinka R. L. J. C. Branco, Ricardo José SabatineAuthors Info & Claims
Pages 390 - 396
Abstract
Self-localization is a fundamental problem in mobile robotics. It consists of estimating the position of a robot given a map of the environment and information obtained by sensors. Among the algorithms used to address this issue, the Monte Carlo technique has obtained a considerable attention by the scientific community due to its simplicity and precision. Monte Carlo localization is a sample-based technique that estimates robot's pose using a probability density function represented by samples (particles). The complexity of this algorithm scales proportionally to the number of particles used. The larger the environment, the more particles are required for robot localization. This fact limits the use of this algorithm to medium size environments. In order to improve the efficiency of the Monte Carlo technique and allow it to be used in large environments we propose a parallel implementation. Our implementation is based on OpenMP and MPI message passing interface. Experimental results are used to show the efficiency of our approach.
References
[1]
M. Yamakita, Y. Hoshino, K. Morimoto, and K. Furuta. Parallel Implementation of Newton-Euler Algorithm with One Step Ahead Prediction. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation, pages 1842{1849, Sacramento, CA, 1991.
[2]
H. Zhangand R. P. Paul. A Parallel Inverse Kinematics Solution forRobot Manipulators Based on Multiprocessing and Linear Extrapolation. In Proceedings of the 1990 IEEE International Conference on Robotics and Automation, pages 468{474, Cincinnati, OH, 1990.
[3]
M. Vukobratovic, N. Kircanski, and S. G. Li. An Approach to Parallel Processing of Dynamic Robot Models. International Journal of Robotics Research, 7(2):64{71, 1988.
[4]
A. M. Printista, M. L. Errecalde, C. I. Montoya "A Parallel Implementation of Q-Learning Based on Communication with Cache" Journal of Computer Science&Technology, Vol. 6, 2002.
[5]
C. S. G. Lee and P. R. Chang, Efficient parallel algorithm for robot inverse dynamics computation. IEEE Trans. Syst. Man Cybernet. 16 4 (1986), pp. 532--542.
[6]
Maja J Matarić, "Parallel, Decentralized Spatial Mapping for Robot Navigation and Path Planning", Parallel Problem Solving from Nature, Hans-Paul Schwefel and Reinhard Maenner, eds., Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1991, 381--385.
[7]
L. A. Smith and P. Kent. Development and Performance of a Mixed OpenMP/MPI Quantum Monte Carlo Code. Proc. of the 1st European Workshop on OpenMP, pages 6--9, Sept. 1999.
[8]
Esselink, K.; Loyens, L. D. J. C.; Smit, B., Parallel Monte Carlo simulations, Physical Review E, Vol. 51(2), pp. 1560--1568, 1995.
[9]
Thrun, S., Burgard, W., Fox, D., Probabilistic Robotics, MIT Press, 2005.
[10]
F. Dellaert, D. Fox, W. Burgard, and S. Thrun. Monte Carlo localization for mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 1999.
[11]
Borges, C. L. T., Falcão, D. M. "Avaliação da Confiabilidade de Sistemas de Potência em Paralelo Usando Simulação Monte Carlo Seqüencial", Revista Controle&Automaçção. Vol. 11 n°2/Mai, Jun, Jul, Agosto 2000, 94--99.
[12]
Smith, L., Kent, P. "Development and performance of a mixed OpenMP/MPI quantum Monte Carlo code" in Concurrency: Practice And Experience, 2000; 12:1121--1129.
[13]
Ferrari, A. J.; (1998) JPVM: Network parallel computing in Java, In ACM 1998 Workshop on Java for High-Performance Network Computing, Palo Alto, February 1998. Concurrency: Practice and Experience.
[14]
Ferrari, A. J. (2007) JPVM The Java Parallel Virtual Machine. Available at: http://www.cs.virginia.edu/~ajf2j/jpvm.html. Last access June 2009.
[15]
Baker, M. et al. (1998) mpiJava: A Java Interface to MPI. Submitted to First UK Workshop on Java for High Performance Network Computing, Europar.
[16]
Quinn, M. "Parallel Programming in C with MPI and OpenMP". McGraw-Hill Science/Engineering/Math; 1 edition, June 5, 2003.
[17]
Snir, M. Otto, S. M., Huss-Lederman, S., Dongarra, J. (1996) MPI: The Complete Reference, The MIT Press.
[18]
Beguelin, A., PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing, The MIT Press, 1994.
[19]
Pthreads, https://computing.llnl.gov/tutorials/pthreads/last access in June 2009.
[20]
Seinstra, F. J.; Koelma, D. User Transparency: A Fully Sequential Programming Model for Efficient Data Parallel Image Processing, Concurrency and Computation: Practice and Experience, vol. 16, no. 6, pp. 611--644, May 2004.
Index Terms
- Parallel implementation of mobile robotic self-localization
Recommendations
A Parallel Approach for Mobile Robotic Self-Localization
ICCIT '09: Proceedings of the 2009 Fourth International Conference on Computer Sciences and Convergence Information TechnologyNavigation is the foundation of mobile robots. In order to plan its path and successfully move in the environment a robot must know its on position in it. The problem is called self-localization and it consists of estimating the position of a robot ...
Stereo vision based self-localization of autonomous mobile robots
RobVis'08: Proceedings of the 2nd international conference on Robot visionThis paper presents vision based self-localization of tiny autonomous mobile robots in a known but highly dynamic environment. The problem covers tracking the robot position with an initial estimate to global self-localization. The algorithm enables the ...
A practical approach to control and self-localization of an omni-directional mobile robot
Due to their advantages, omni-directional mobile robots have found many applications especially in robotic soccer competitions. Despite recent advances, effective control and self-localization of omni-directional mobile robots remain as important and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2009
687 pages
ISBN:9781605586625
DOI:10.1145/1644993
- General Chairs:
- Geuk Lee,
- Daniel Howard,
- Jeong Jin Kang,
- Program Chairs:
- Dominik Slezak,
- Tae Nam Ahn,
- Chung-Huang Yang
Copyright © 2009 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 August 2009
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ICHIT '09
ICHIT '09: International Conference on Convergence and Hybrid Information Technology
August 27 - 29, 2009
Daejeon, Korea
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 8Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in