Open Access Open Access  Restricted Access Subscription or Fee Access

Efficient EKF-SLAM’s Jacobian Matrices Hardware Architecture and its FPGA Implementation


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/iree.v16i5.20149

Abstract


Simultaneous Localization And Mapping (SLAM) algorithm allows a mobile robot to localize itself and move safely in an unknown environment while exploring and mapping it. The increasing use of SLAM in autonomous robots leads to the design of novel real-time hardware architectures. This paper presents an efficient EKF-SLAM’s (Extended Kalman Filter SLAM) Jacobian matrices hardware architecture design and implementation on a Field-Programmable Gate Array (FPGA). The proposed architecture is designed by using the Taylor Expansions with fixed-point arithmetic operators. The implementations for trigonometric functions cover the whole dynamic range i.e. [-π,π]. The proposed technique leads to higher accuracy and lower complexity. The design has been implemented on Cyclone II FPGA. It can reach up to 112 MHz and it uses 1517 logic elements, 1438 registers, and 44 embedded 9-bit multipliers, with 12 cycles of latency. Finally, a hardware resource comparison between this design and different state of the art techniques has been done. The proposed design uses very low resources with high frequency.
Copyright © 2021 Praise Worthy Prize - All rights reserved.

Keywords


SLAM; EKF-SLAM; Implementation; FPGA; Hardware Architecture; VHDL

Full Text:

PDF


References


R. Dutt, and A. Acharyya, A High Speed and Low Complexity Architecture Design Methodology for Square Root Unscented Kalman Filter based SLAM. 2020 European Conference on Circuit Theory and Design (ECCTD). IEEE, 2020.‏
https://doi.org/10.1109/ECCTD49232.2020.9218287

H. Taheri and Z.C. Xia. SLAM; definition and evolution. Engineering Applications of Artificial Intelligence. 2021 Jan 1;97:104032.
https://doi.org/10.1016/j.engappai.2020.104032

J. Piat, P. Fillatreau, D. Tortei, F. Brenot and M. Devy. HW/SW co-design of a visual SLAM application, Journal of Real-Time Image Processing, 2018, p. 1-23.
https://doi.org/10.1007/s11554-018-0836-2

H. Durrant-Whyte and T. Bailey. Simultaneous localization and mapping: part I. IEEE robotics & automation magazine, 2006, vol. 13, no 2, p. 99-110.
https://doi.org/10.1109/MRA.2006.1638022

S. Thrun, Simultaneous localization and mapping. In: Robotics and cognitive approaches to spatial mapping. Springer, Berlin, Heidelberg, 2007, p. 13-41.
https://doi.org/10.1007/978-3-540-75388-9_3

S. Thrun, W. Burgard and D. Fox. Probabilistic Robotics, Massachusetts Institute of Technology MIT Press, USA, 2005, ISBN: 978- 0262201629.

L.E. Fabrice, A. Bertholom, J. Sliwka, and L. Jaulin, Interval SLAM for underwater robots; a new experiment, NOLCOS 2010, France, 2010, Vol. 43, ffhal-00636026f.
https://doi.org/10.3182/20100901-3-IT-2016.00083

G. Dissanayake, H. Durrant-Whyte and T. Bailey, A computationally efficient solution to the simultaneous localisation and map building (SLAM) problem. Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), San Francisco, CA, USA, 2000, pp. 1009-1014 vol.2.

S. Thrun, W. Burgard, and D. Fox, A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots, Autonomous Robots, 1998, vol. 5, no 3-4, p. 253-271.
https://doi.org/10.1023/A:1008806205438

M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, FastSLAM: A factored solution to the simultaneous localization and mapping problem, in: Proceedings of the AAAI National Conference on Artificial Intelligence, AAAI, 2002, pp. 593-598.

M.Y.I. Idris, N.M. Noor, E.M. Tamil, Z. Razak and H. Arof. Parallel matrix multiplication design for monocular SLAM. In 2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation, 2010 May 26, pp. 492-497, IEEE.
https://doi.org/10.1109/AMS.2010.100

J. Neira and J. D. Tards, Data association in stochastic mapping using the joint compatibility test, IEEE Transactions on Robotics and Automation 17, 2001, 890-897.
https://doi.org/10.1109/70.976019

T. Bailey, Mobile robot localisation and mapping in extensive outdoor environments, Sydney, Australia: Australian Centre for Field Robotics, Department of Aerospace, Mechanical and Mechatronic Engineering, University of Sydney, 2002.

J. E. Guivant and E. M. Nebot, Optimization of the simultaneous localization and map- building algorithm for real-time implementation, IEEE Transactions on Robotics and Automation 17 , 2001, 242-257.
https://doi.org/10.1109/70.938382

M. G. Dissanayake, P. Newman, S. Clark, H. F. Durrant-Whyte and M. Csorba, A solution to the simultaneous localization and map building (slam) problem, IEEE Transactions on Robotics and Automation 17, 2001, 229-241.
https://doi.org/10.1109/70.938381

S. Holmes, G. Klein and D. W. Murray, A square root unscented kalman filter for visual monoslam, in: IEEE International Conference on Robotics and Automation (ICRA), Pasadena, CA, 2008, pp. 3710-3716.
https://doi.org/10.1109/ROBOT.2008.4543780

G. P. Huang, A. I. Mourikis and S. I. Roumeliotis, A quadratic-complexity observability-constrained unscented kalman filter for slam, IEEE Transactions on Robotics 29, 2013, 1226-1243.
https://doi.org/10.1109/TRO.2013.2267991

F. Dellaert, D. Fox, W. Burgard and S. Thrun, Monte Carlo localization for mobile robots, in Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C), Detroit, MI, USA 999, pp. 1322-1328 vol.2.

S. Thrun and M. Montemerlo, The graph SLAM algorithm with applications to large-scale mapping of urban structures. The International Journal of Robotics Research 25, no. 5-6, 2006,: 403-429.
https://doi.org/10.1177/0278364906065387

F. Lu and E. Milios, Globally consistent range scan alignment for environment mapping. Autonomous robots 4, no. 4, 1997, 333-349.
https://doi.org/10.1023/A:1008854305733

G. Grisetti, R. Kummerle, C. Stachniss and W. Burgard, A tutorial on graph-based SLAM, IEEE Intelligent Transportation Systems Magazine 2, no. 4, 2010, 31-43.
https://doi.org/10.1109/MITS.2010.939925

R. Kummerle, G. Grisetti, H. Strasdat, K. Konolige and W. Burgard, g 2 o: A general framework for graph optimization, In 2011 IEEE International Conference on Robotics and Automation, pp. 3607-3613. IEEE, 2011.
https://doi.org/10.1109/ICRA.2011.5979949

J. Cheng, J. Kim, Z. Jiang. and W. Che, Dual quaternion-based graphical SLAM. Robotics and Autonomous Systems, 2016, 77: 15-24.‏
https://doi.org/10.1016/j.robot.2015.12.001

T. Bailey and H. Durrant-Whyte. Simultaneous localization and mapping (SLAM): Part II. IEEE robotics & automation magazine, 2006, vol. 13, no 3, p. 108-117.
https://doi.org/10.1109/MRA.2006.1678144

R. C. Smith, and P. Cheeseman. On the representation and estimation of spatial uncertainty. The international journal of Robotics Research 1986, 5(4), pp. 56-68.
https://doi.org/10.1177/027836498600500404

R. Smith, M. Self, and P. Cheeseman. Estimating uncertain spatial relationships in robotics. In Machine intelligence and pattern recognition. Vol. 5. North-Holland, 1988, 435-461.
https://doi.org/10.1016/B978-0-444-70396-5.50042-X

A.J. Davison, I.D. Reid, N.D. Molton, O. Stasse. MonoSLAM: Real-time single camera SLAM. IEEE transactions on pattern analysis and machine intelligence. 2007 Apr 23;29(6):1052-67.
https://doi.org/10.1109/TPAMI.2007.1049

D. T. Tertei, J. Piat, et M. Devy. FPGA design and implementation of a matrix multiplier based accelerator for 3D EKF SLAM. In: 2014 International Conference on ReConFigurable Computing and FPGAs (ReConFig14). IEEE, 2014, p. 1-6.
https://doi.org/10.1109/ReConFig.2014.7032523

H. Guo, H. Chen, F. Xu, F. Wang, and G. Lu. Implementation of EKF for vehicle velocities estimation on FPGA. IEEE Transactions on Industrial Electronics. 2012 Aug 13;60(9):3823-35.
https://doi.org/10.1109/TIE.2012.2208436

V. Bonato, E. Marques, and G.A. Constantinides. A floating-point extended kalman filter implementation for autonomous mobile robots. Journal of Signal Processing Systems, 2009, vol. 56, no 1, p. 41-50.
https://doi.org/10.1007/s11265-008-0257-8

B. Xue, W. De-ming, T. Jun-jun and Z. Bu-hui. The hardware design and simulation of kalman filter based on ip core and time-sharing multiplex. In:2011 Fourth International Conference on Intelligent Computation Technology and Automation. IEEE, 2011, p. 266-269.
https://doi.org/10.1109/ICICTA.2011.353

N. K. Quang, N. T. Hieu and Q. P. Ha, FPGA-Based Sensorless PMSM Speed Control Using Reduced-Order Extended Kalman Filters, IEEE Transactions on Industrial Electronics, 2014, vol. 61, no 12, p. 6574-6582.
https://doi.org/10.1109/TIE.2014.2320215

Z. Ma and X. Zhang, FPGA-based sensorless control for PMSM drives using the stator/rotor frame extended Kalman filter. In: 2018 Chinese Control And Decision Conference (CCDC). IEEE, 2018, p. 10.
https://doi.org/10.1109/CCDC.2018.8407113

D.T. Tertei, J. Piat, et M. Devy. FPGA design of EKF block accelerator for 3D visual SLAM. Computers & Electrical Engineering, 2016, vol. 55, p. 123-137.
https://doi.org/10.1016/j.compeleceng.2016.05.003

L. Contreras, S. Cruz, J. M. S. Motta and C. H. Llanos, FPGA implementation of the EKF algorithm for localization in mobile robotics using a unified hardware module approach, International Conference on ReConFigurable Computing and FPGAs (ReConFig), Mexico City, 2015, pp. 1-6.
https://doi.org/10.1109/ReConFig.2015.7393315

S. Bouhoun, R. Sadoun, and M. Adnane. OpenCL implementation of a SLAM system on an SoC-FPGA. Journal of Systems Architecture, 2020, 111: 101825.
https://doi.org/10.1016/j.sysarc.2020.101825

H. Strasdat, J. M. M. Montiel and A. J. Davison. Real-time monocular SLAM: Why filter?, In: 2010 IEEE International Conference on Robotics and Automation. IEEE, 2010, p. 2657-2664.
https://doi.org/10.1109/ROBOT.2010.5509636

J. A. Castellanos, J. M. M. Montiel, J. Neira and J. D. Tardós. The SPmap: A probabilistic framework for simultaneous localization and map building. IEEE Transactions on robotics and Automation, 1999, vol. 15, no 5, p. 948-952.
https://doi.org/10.1109/70.795798

M.G. Dissanayake, P. Newman, S. Clark, H.F. Durrant-Whyte and M. Csorba. A solution to the simultaneous localization and map building (SLAM) problem. IEEE Transactions on robotics and automation, 2001, vol. 17, no 3, p. 229-241.
https://doi.org/10.1109/70.938381

H. Durrant-Whyte, S. Majumder, S. Thrun, M. De Battista, and S. Scheding. A bayesian algorithm for simultaneous localisation and map building. In: Robotics Research. Springer, Berlin, Heidelberg, 2003, p. 49-60.
https://doi.org/10.1007/3-540-36460-9_4

‏M. Abouzahir, A. Elouardi, R. Latif , S. Bouaziz and A. Tajer. Embedding SLAM algorithms: Has it come of age?, Robotics and Autonomous Systems. 2018, Feb 1;100:14-26.
https://doi.org/10.1016/j.robot.2017.10.019

R. Liu, J. Yang, Y. Chen, W. Zhao. eslam: An energy-efficient accelerator for real-time orb-slam on fpga platform. In Proceedings of the 56th Annual Design Automation Conference, 2019 Jun 2 (pp. 1-6).
https://doi.org/10.1145/3316781.3317820

H.M. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, S. Thrun and R.C. Arkin, Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA, USA: The MIT Press, 2005.

https://www.intel.com/content/www/us/en/programmable/support/support-resources/operation-and-testing/dev-cyclone2.html


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize