Volume 15 Number 3
June 2018
Article Contents
Tai-Zhi Lv, Chun-Xia Zhao and Hao-Feng Zhang. An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF. International Journal of Automation and Computing, vol. 15, no. 3, pp. 325-334, 2018. doi: 10.1007/s11633-016-1050-y
Cite as: Tai-Zhi Lv, Chun-Xia Zhao and Hao-Feng Zhang. An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF. International Journal of Automation and Computing, vol. 15, no. 3, pp. 325-334, 2018.

# An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF

Author Biography:
• Chun-Xia Zhao  received the B.Sc.degree in industrial automatization from Harbin Institute of Technology, China in 1985, the M.Sc.degree in pattern recognition and artificial intelligence control from Harbin Institute of Technology, China in 1988, and the Ph.D.degree in electromechanics and automatization from Harbin Institute of Technology, China in 1998.She is currently a professor at School of Computer Science and Technology, Nanjing University of Science and Technology, China.She has published above 100 refereed journal and conference papers.
Her research interests include underground robotics, computer vision and navigation.
E-mail:zhaochx@mail.njust.edu.cn

Hao-Feng Zhang   received the B.Sc.in computer science and technology from Nanjing University of Science and Technology, China in 2003, and the Ph.D.degree in pattern recognition and intelligent systems from Nanjing University of Science and Technology, China in 2007.He is currently an associate professor at School of Computer Science and Technology, Nanjing University of Science and Technology, China.
His research interests include robotics, robot navigation and image process technology.
E-mail:zhanghf@njust.edu.cn

• Corresponding author: Tai-Zhi Lv  received the B.Sc.degree in computer science from Nanjing University, China in 2002, and the M.Sc.degree in computer software and theory from Nanjing University of Science and technology, China in 2006.He is currently a Ph.D.degree candidate of Nanjing University of Science and Technology, China.
His research interests include SLAM (Simultaneous localization and mapping) and robot navigation.
E-mail:lvtaizhi1@gmail.com(Corresponding author)
ORCID iD:0000-0003-1994-9841
• Accepted: 2014-05-09
• Published Online: 2018-12-29
Fund Project:

Research Fund for the Doctoral Program of Higher Education of China 20093219120025

National Natural Science Foundation of China 61101197

• FastSLAM is a popular framework which uses a Rao-Blackwellized particle filter to solve the simultaneous localization and mapping problem (SLAM). However, in this framework there are two important potential limitations, the particle depletion problem and the linear approximations of the nonlinear functions. To overcome these two drawbacks, this paper proposes a new FastSLAM algorithm based on revised genetic resampling and square root unscented particle filter (SR-UPF). Double roulette wheels as the selection operator, and fast Metropolis-Hastings (MH) as the mutation operator and traditional crossover are combined to form a new resampling method. Amending the particle degeneracy and keeping the particle diversity are both taken into considerations in this method. As SR-UPF propagates the sigma points through the true nonlinearity, it decreases the linearization errors. By directly transferring the square root of the state covariance matrix, SR-UPF has better numerical stability. Both simulation and experimental results demonstrate that the proposed algorithm can improve the diversity of particles, and perform well on estimation accuracy and consistency.
•  [1] 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 [2] S. Thrun, W. Burgard, D. Fox. Probabilistic Robotics, Cambridge, USA:The MIT Press, 2005. [3] M. Kaess, A. Ranganathan, F. Dellaert, iSAM:Incremental smoothing and mapping, Robotics, vol. 24, no. 6, pp. 1365-1378, 2008. [4] S. Thrun, M. Montemerlo. The GraphSLAM Algorithm with Application to Large-Scale Mapping of Urban Structures, The International Journal of Robotics Research, vol. 25, no. 5-6, pp. 403-429, 2006.  doi: 10.1177/0278364906065387 [5] H. Wang, W. Mou, G. Seet, M. H. Li, M. W. S. Lau, D. W. Wang. Real-time visual odometry estimation based on principal direction detection on ceiling vision. International Journal of Automation and Computing, vol. 10, no. 5, pp. 397-404, 2013.  doi: 10.1007/s11633-013-0736-7 [6] M. Montemerlo. FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem with Unknown Data Association, Ph. D. dissertation, Carnegie Mellon University, USA, 2003. [7] C. Gamallo, M. Mucientes, C. V. Regueiro. A FastSLAMbased Algorithm for Omni directional Cameras, Journal of Physical Agents, vol. 7, no. 1, pp. 12-21, 2012. [8] S. M. Chen, J. F. Yuan, F. Zhang, H. J. Fang. Multirobot FastSLAM Algorithm Based on Landmark Consistency Correction, Mathematical Problems in Engineering, vol. 2014, pp. 1-7, 2014. [9] R. Martinez-Cantin, J. A. Castellanos. Unscented SLAM for large-scale outdoor environments. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Edmonton, Canada, pp. 3427-3432, 2005. [10] D. B. Liu, G. R. Liu, M. H. Yu. An improved FastSLAM framework based on particle swarm optimization and unscented particle filter. Journal of Computational Information Systems, vol. 8, no. 7, pp. 2859-2866, 2012. [11] K. Chanki, R. Sakthivel, W. K. Chung. Unscented FastSLAM: A robust algorithm for the simultaneous localization and mapping problem. In Proceedings of International Conference on Robotics and Automation, IEEE, Roma, Italy, pp. 2439-2445, 2007. [12] J. H. Zhu, N. N. Zheng, Z. J. Yuan, Q. Zhang. A SLAM algorithm based on central difference particle filter. Acta Automatica Sinica, vol. 36, no. 2, pp. 249-257, 2010. (in Chinese)  doi: 10.3724/SP.J.1004.2010.00249 [13] Y. Song, Y. D. Song, Q. L. Li. Robust iterated sigma point FastSLAM algorithm for mobile robot simultaneous localization and mapping. Chinese Journal of Mechanical Engineering, vol. 24, no. 4, pp. 693-700, 2011.  doi: 10.3901/CJME.2011.04.693 [14] T. Bailey, J. Nieto, E. Nebot. Consistency of the FastSLAM algorithm. In Proceedings of International Conference on Robotics and Automation, IEEE, Orlando, USA, pp. 424-429, 2006. [15] C. Stachniss, D. Hahnel, W. Burgard. Exploration with active loop-closing for FastSLAM. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, Sendai, Japan, pp. 1505-1510, 2004. [16] J. S. Liu. Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Statistics and Computing, vol. 6, no. 2, pp. 113-119, 1996.  doi: 10.1007/BF00162521 [17] G. Grisetti, C. Stachniss, W. Burgard. Improved techniques for grid mapping with Rao-Blackwellized particle filters. IEEE Transactions on Robotics, vol. 23, no. 1, pp. 34-46, 2007. [18] N. Nosan, I. K. Kim, H. C. Lee, B. H. Lee. Analysis of resampling process for the particle depletion problem in fastslam. In Proceedings of the 16th International Symposium on Robot and Human Interactive Communication, IEEE, Jeju Island, Korea, pp. 200-205, 2007. [19] X. Z. Li, S. M. Jia, W. Cui. On sample diversity in particle filter based robot SLAM. In Proceedings of International Conference on Robotics and Biomimetics, IEEE, Phuket, Thailand, pp. 1072-1077, 2011. [20] Y. M. Xia, Y. M. Yang. An improved FastSLAM algorithm based on genetic algorithms. In Proceedings of International Symposium, Communications in Computer and Information Science, Springer, Guangzhou, China, pp. 296-302, 2011. [21] H. Wang, Y. Yan, D. W. Wang. A GA based SLAM with range sensors only. In Proceedings of the 11th International Conference on Control Automation Robotics and Vision, IEEE, Singapore, pp. 1796-1802, 2010. [22] P. Li, S. M. Song, X. L. Chen, G. R. Duan. Square root unscented Kalman filter incorporating Gaussian process regression. Systems Engineering and Electronics, vol. 32, no. 6, pp. 1281-1285, 2010. (in Chinese) [23] R. D. Merw, E. A. Wan. The square-root unscented kalman filter for state and parameter-estimation. Systems Engineering and Electronics, vol. 32, no. 6, pp. 1281-1285, 2010. [24] P. Giordani, R. Kohn. Adaptive independent MetropolisHastings by fast estimation of mixtures of normals. Journal of Computational and Graphical Statistics, vol. 19, no. 2, pp. 243-259, 2010.  doi: 10.1198/jcgs.2009.07174 [25] J. E. Guivant, E. M. Nebot. Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE Transactions on Robotics and Automation, vol. 17, no. 3, pp. 242-257, 2001.  doi: 10.1109/70.938382 [26] T. Bailey. SLAM simulations, [Online], Available: http://www-personal.acfr.usyd.edu.au/tbailey/software/, March 10, 2011. [27] Y. Bar-Shalom, X. R. Li, T. Kirubarajan. Estimation with Applications to Tracking and Navigation:Theory Algorithms and Software, Hoboken, USA:John Wiley and Sons, 2004. [28] E. Nebot, J, Guivant, J. Nieto. ACFR, Experimental outdoor dataset, [Online], Available: http://www.acfr.usyd.edu.au/home-pages/academic/enebot/dataset.htm, July 28, 2012.
•  [1] J. Gimenez, A. Amicarelli, J. M. Toibero, F. di Sciascio, R. Carelli. Iterated Conditional Modes to Solve Simultaneous Localization and Mapping in Markov Random Fields Context . International Journal of Automation and Computing, 2018, 15(3): 310-324.  doi: 10.1007/s11633-017-1109-4 [2] Jian-Wei Li, Wei Gao, Yi-Hong Wu. Elaborate Scene Reconstruction with a Consumer Depth Camera . International Journal of Automation and Computing, 2018, 15(4): 443-453.  doi: 10.1007/s11633-018-1114-2 [3] Yi Yang, Fan Qiu, Hao Li, Lu Zhang, Mei-Ling Wang, Meng-Yin Fu. Large-scale 3D Semantic Mapping Using Stereo Vision . International Journal of Automation and Computing, 2018, 15(2): 194-206.  doi: 10.1007/s11633-018-1118-y [4] Dong-Jie Li, Yang-Yang Li, Jun-Xiang Li, Yu Fu. Gesture Recognition Based on BP Neural Network Improved by Chaotic Genetic Algorithm . International Journal of Automation and Computing, 2018, 15(3): 267-276.  doi: 10.1007/s11633-017-1107-6 [5] Dony Hidayat Al-Janan, Hao-Chin Chang, Yeh-Peng Chen, Tung-Kuan Liu. Optimizing the Double Inverted Pendulum s Performance via the Uniform Neuro Multiobjective Genetic Algorithm . International Journal of Automation and Computing, 2017, 14(6): 686-695.  doi: 10.1007/s11633-017-1069-8 [6] Merras Mostafa, El Hazzat Soulaiman, Saaidi Abderrahim, Satori Khalid, Gadhi Nazih Abderrazak. 3D Face Reconstruction Using Images from Cameras with Varying Parameters . International Journal of Automation and Computing, 2017, 14(6): 661-671.  doi: 10.1007/s11633-016-0999-x [7] Sun-Chun Zhou, Rui Yan, Jia-Xin Li, Ying-Ke Chen, Huajin Tang. A Brain-inspired SLAM System Based on ORB Features . International Journal of Automation and Computing, 2017, 14(5): 564-575.  doi: 10.1007/s11633-017-1090-y [8] Kumaran Rajarathinam,  James Barry Gomm,  Ding-Li Yu,  Ahmed Saad Abdelhadi. PID Controller Tuning for a Multivariable Glass Furnace Process by Genetic Algorithm . International Journal of Automation and Computing, 2016, 13(1): 64-72.  doi: 10.1007/s11633-015-0910-1 [9] Shuo Liu,  Wen-Hua Chen,  Jiyin Liu. Robust Assignment of Airport Gates with Operational Safety Constraints . International Journal of Automation and Computing, 2016, 13(1): 31-41.  doi: 10.1007/s11633-015-0914-x [10] Zhong-Da Tian,  Xian-Wen Gao,  Kun Li. A Hybrid Time-delay Prediction Method for Networked Control System . International Journal of Automation and Computing, 2014, 11(1): 19-24.  doi: 10.1007/s11633-014-0761-1 [11] Han Wang, Wei Mou, Gerald Seet, Mao-Hai Li, M. W. S. Lau, Dan-Wei Wang. Real-time Visual Odometry Estimation Based on Principal Direction Detection on Ceiling Vision . International Journal of Automation and Computing, 2013, 10(5): 397-404.  doi: 10.1007/s11633-013-0736-7 [12] Li-Jie Zhao, Tian-You Chai, De-Cheng Yuan. Selective Ensemble Extreme Learning Machine Modeling of Effluent Quality in Wastewater Treatment Plants . International Journal of Automation and Computing, 2012, 9(6): 627-633 .  doi: 10.1007/s11633-012-0688-3 [13] Qiang Lu,  Ping Luo. A Learning Particle Swarm Optimization Algorithm for Odor Source Localization . International Journal of Automation and Computing, 2011, 8(3): 371-380.  doi: 10.1007/s11633-011-0594-0 [14] Liang He, Zhi Chen, Jing-Dong Xu. Optimizing Data Collection Path in Sensor Networks with Mobile Elements . International Journal of Automation and Computing, 2011, 8(1): 69-77.  doi: 10.1007/s11633-010-0556-y [15] Tung-Kuan Liu, Chiu-Hung Chen, Zu-Shu Li, Jyh-Horng Chou. Method of Inequalities-based Multiobjective Genetic Algorithm for Optimizing a Cart-double-pendulum System . International Journal of Automation and Computing, 2009, 6(1): 29-37.  doi: 10.1007/s11633-009-0029-3 [16] Anna Witkowska,  Roman Smierzchalski. Nonlinear Backstepping Ship Course Controller . International Journal of Automation and Computing, 2009, 6(3): 277-284.  doi: 10.1007/s11633-009-0277-2 [17] Siva S. Sivatha Sindhu, S. Geetha, M. Marikannan, A. Kannan. A Neuro-genetic Based Short-term Forecasting Framework for Network Intrusion Prediction System . International Journal of Automation and Computing, 2009, 6(4): 406-414.  doi: 10.1007/s11633-009-0406-y [18] Kai Leung Yung, Wai Hung Ip, Ding-Wei Wang. Soft Computing Based Procurement Planning of Time-variable Demand in Manufacturing Systems . International Journal of Automation and Computing, 2007, 4(1): 80-87.  doi: 10.1007/s11633-007-0080-x [19] Erfu Yang, Hongjun Xiang, Dongbing Gu, Zhenpeng Zhang. A Comparative Study of Genetic Algorithm Parameters for the Inverse Problem-based Fault Diagnosis of Liquid Rocket Propulsion Systems . International Journal of Automation and Computing, 2007, 4(3): 255-261.  doi: 10.1007/s11633-007-0255-5 [20] . Problems Associated with Evacuation from the Ship in Case of an Emergency Situation . International Journal of Automation and Computing, 2006, 3(2): 165-168.  doi: 10.1007/s11633-006-0165-y
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

Figures (9)  / Tables (2)

## An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF

• ###### Corresponding author:Tai-Zhi Lv  received the B.Sc.degree in computer science from Nanjing University, China in 2002, and the M.Sc.degree in computer software and theory from Nanjing University of Science and technology, China in 2006.He is currently a Ph.D.degree candidate of Nanjing University of Science and Technology, China.   His research interests include SLAM (Simultaneous localization and mapping) and robot navigation.   E-mail:lvtaizhi1@gmail.com(Corresponding author)   ORCID iD:0000-0003-1994-9841
Fund Project:

Research Fund for the Doctoral Program of Higher Education of China 20093219120025

National Natural Science Foundation of China 61101197

Abstract: FastSLAM is a popular framework which uses a Rao-Blackwellized particle filter to solve the simultaneous localization and mapping problem (SLAM). However, in this framework there are two important potential limitations, the particle depletion problem and the linear approximations of the nonlinear functions. To overcome these two drawbacks, this paper proposes a new FastSLAM algorithm based on revised genetic resampling and square root unscented particle filter (SR-UPF). Double roulette wheels as the selection operator, and fast Metropolis-Hastings (MH) as the mutation operator and traditional crossover are combined to form a new resampling method. Amending the particle degeneracy and keeping the particle diversity are both taken into considerations in this method. As SR-UPF propagates the sigma points through the true nonlinearity, it decreases the linearization errors. By directly transferring the square root of the state covariance matrix, SR-UPF has better numerical stability. Both simulation and experimental results demonstrate that the proposed algorithm can improve the diversity of particles, and perform well on estimation accuracy and consistency.

Tai-Zhi Lv, Chun-Xia Zhao and Hao-Feng Zhang. An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF. International Journal of Automation and Computing, vol. 15, no. 3, pp. 325-334, 2018. doi: 10.1007/s11633-016-1050-y
 Citation: Tai-Zhi Lv, Chun-Xia Zhao and Hao-Feng Zhang. An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF. International Journal of Automation and Computing, vol. 15, no. 3, pp. 325-334, 2018.
Reference (28)

/