A NOVEL DATA ASSOCIATION TECHNIQUE TO IMPROVE RUN-TIME EFFICIENCY OF SLAM ALGORITHMS

Abstract

Simultaneous Localization and Mapping (SLAM) problem is a very popular research area in robotic applications. EKF-SLAM and FastSLAM are widely used algorithms for SLAM problem. The greatest advantage of FastSLAM over EKF-SLAM is that it reduces the quadratic complexity of EKF-SLAM. On the other hand, increasing number of estimated landmarks naturally slows down the operation of FastSLAM. In this paper, we propose a new method called as Intelligent Data Association-SLAM (IDA-SLAM) which reduces this slowing down problem. In data association step also known as likelihood estimation, IDA-SLAM skips comparing a new landmark with all of the pre-calculated landmarks. Instead of this, it compares the newly found one with only nearby landmarks that was found previously. The simulation results indicate that the proposed algorithm significantly speeds up the operation of SLAM without a loss of state estimation accuracy. Real world experiments which have been performed in two different scenarios verify the simulation results. A runtime reduction of 43% and 52% is observed respectively for each of the test environments.

Keywords

• Simultaneous localization and mapping,fastslam,data association,particle filter

References

1. 1] Tzafestas SG. Mobile Robot Control and Navigation: A Global Overview. Journal of Intelligent & Robotic Systems. 2018:1-24.
2. [2] Burgard W, Fox D, Thrun S. Probabilistic robotics. The MIT Press. 2005.
3. [3] Smith RC, Cheeseman P. On the representation and estimation of spatial uncertainty. The international journal of Robotics Research. 1986 Dec;5(4):56-68.
4. [4] Smith R, Self M, Cheeseman P. Estimating uncertain spatial relationships in robotics. InAutonomous robot vehicles 1990 (pp. 167-193). Springer, New York, NY.
5. [5] Leonard JJ, Durrant-Whyte HF. Simultaneous map building and localization for an autonomous mobile robot. In: Proc. IEEE Int. Workshop on Intelligent Robots and Systems (IROS); 3-5 November 1991; Osaka, Japan. pp. 1442-1447.
6. [6] Dissanayake G, Newman P, Clark S, Durrant-Whyte HF and Csorba M. An experimental and theoretical investigation into simultaneous localisation and map building (SLAM). Lecture Notes in Control and Information Sciences: Experimental Robotics VI, Springer, 2000.
7. [7] Wen S, Sheng M, Ma C, Li Z, Lam HK, Zhao Y, Ma J. Camera Recognition and Laser Detection based on EKF-SLAM in the Autonomous Navigation of Humanoid Robot. Journal of Intelligent & Robotic Systems. 2017:1-3.
8. [8] Guivant JE, Nebot EM. Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE transactions on robotics and automation. 2001 Jun;17(3):242-57.

9. [9] Leonard JJ, Feder HJ. A computationally efficient method for large-scale concurrent mapping and localization. InRobotics Research 2000 (pp. 169-176). Springer, London. [10] Lu F, Milios E. Globally consistent range scan alignment for environment mapping. Autonomous robots. 1997 Oct 1;4(4):333-49.
10. [11] Kim TH, Park TH. EKF-based simultaneous localization and mapping using laser corner-pattern matching. InInformation and Automation (ICIA), 2016 IEEE International Conference on 2016 Aug 1 (pp. 491-497). IEEE.
11. [12] Saman AB, Lotfy AH. An implementation of SLAM with extended Kalman filter. InIntelligent and Advanced Systems (ICIAS), 2016 6th International Conference on 2016 Aug 15 (pp. 1-4). IEEE.
12. [13] Deng G, Li J, Li W, Wang H. SLAM: Depth image information for mapping and inertial navigation system for localization. InIntelligent Robot Systems (ACIRS), Asia-Pacific Conference on 2016 Jul 20 (pp. 187-191). IEEE.
13. [14] Murphy KP. Bayesian map learning in dynamic environments. InAdvances in Neural Information Processing Systems 2000 (pp. 1015-1021).
14. [15] Montemerlo M, Thrun S, Koller D, Wegbreit B. FastSLAM: A factored solution to the simultaneous localization and mapping problem. Aaai/iaai. 2002 Jul 28;593598.
15. [16] Kim C, Sakthivel R, Chung WK. Unscented FastSLAM: a robust and efficient solution to the SLAM problem. IEEE Transactions on Robotics. 2008 Aug;24(4):808-20.
16. [17] Kwak N, Kim IK, Lee HC, Lee BH. Adaptive prior boosting technique for the efficient sample size in FastSLAM. InIntelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on 2007 Oct 29 (pp. 630-635). IEEE.
17. [18] Xu W, Jiang R, Xie L, Tian X, Chen Y. Adaptive square-root transformed unscented FastSLAM with KLD-resampling. International Journal of Systems Science. 2017 Apr 26;48(6):1322-30.
18. [19] Chang HJ, Lee CG, Lu YH, Hu YC. A computational efficient SLAM algorithm based on logarithmic-map partitioning. InIntelligent Robots and Systems, 2004.(IROS 2004). Proceedings. 2004 IEEE/RSJ International Conference on 2004 Sep (Vol. 2, pp. 1041-1046). IEEE.
19. [20] Yokozuka M, Matsumoto O. Sub-map dividing and re-alignment FastSLAM with scalable voxel map system. InAdvanced Intelligent Mechatronics (AIM), 2012 IEEE/ASME International Conference on 2012 Jul 11 (pp. 180-185). IEEE.
20. [21] Kouzoubov K, Austin D. Hybrid topological/metric approach to SLAM. InRobotics and Automation, 2004. Proceedings. ICRA'04. 2004 IEEE International Conference on 2004 Apr (Vol. 1, pp. 872-877). IEEE.
21. [22] Yang CK, Hsu CC, Wang YT. Computationally efficient algorithm for simultaneous localization and mapping (SLAM). InNetworking, Sensing and Control (ICNSC), 2013 10th IEEE International Conference on 2013 Apr 10 (pp. 328-332). IEEE.
22. [23] Stentz A, Fox D, Montemerlo M. Fastslam: A factored solution to the simultaneous localization and mapping problem with unknown data association. InIn Proceedings of the AAAI National Conference on Artificial Intelligence 2003.
23. [24] Hähnel D, Thrun S, Wegbreit B, Burgard W. Towards lazy data association in SLAM. InRobotics Research. The Eleventh International Symposium 2005 (pp. 421-431). Springer, Berlin, Heidelberg.
24. [25] Montemerlo M, Thrun S. Simultaneous localization and mapping with unknown data association using FastSLAM. InICRA 2003 Sep 14 (pp. 1985-1991).
25. [26] Weingarten J, Siegwart R. EKF-based 3D SLAM for structured environment reconstruction. InIntelligent Robots and Systems, 2005.(IROS 2005). 2005 IEEE/RSJ International Conference on 2005 Aug 2 (pp. 3834-3839). IEEE.
26. [27] Han J, Shao L, Xu D, Shotton J. Enhanced computer vision with microsoft kinect sensor: A review. IEEE transactions on cybernetics. 2013 Oct;43(5):1318-34.
27. [28] Koenig NP, Howard A. Design and use paradigms for Gazebo, an open-source multi-robot simulator. InIROS 2004 Sep 28 (Vol. 4, pp. 2149-2154).
28. [28] Bradski G. OpenCV: Examples of use and new applications in stereo, recognition and tracking. InProc. Intern. Conf. on Vision Interface (VI’2002) 2002 May (p. 347).
29. [30] Núñez P, Vázquez-Martín R, Del Toro JC, Bandera A, Sandoval F. Natural landmark extraction for mobile robot navigation based on an adaptive curvature estimation. Robotics and Autonomous Systems. 2008 Mar 31;56(3):247-64.