A Novel Voronoi Based Particle Filter for Multi-Sensor Data Fusion

Vani Cheruvu, Priyanka Aggarwal, Vijay Devabhaktuni

Mathematics and Statistics, Electrical Engineering and Computer Science, University of Toledo, Toledo, USA.

DOI: 10.4236/am.2012.331244                

Abstract

Seamless and reliable navigation for civilian/military application is possible by fusing prominent Global Positioning System (GPS) with Inertial Navigation System (INS). This integrated GPS/INS unit exhibits a continuous navigation solution with increased accuracy and reduced uncertainty or ambiguity. In this paper, we propose a novel approach of dynamically creating a Voronoi based Particle Filter (VPF) for integrating INS and GPS data. This filter is based on redistribution of the proposal distribution such that the redistributed particles lie in high likelihood region; thereby increasing the filter accuracy. The usual limitations like degeneracy, sample impoverishment that are seen in conventional particle filter are overcome using our VPF with minimum feasible particles. The small particle size in our methodology reduces the computational load of the filter and makes real-time implementation feasible. Our field test results clearly indicate that the proposed VPF algorithm effectively compensated and reduced positional inaccuracies when GPS data is available. We also present the preliminary results for cases with short GPS outages that occur for low-cost inertial sensors.

Keywords

Sensor Fusion; Global Positioning System; Inertial Navigation System; Voronoi Tessellations; Particle Filter

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Misra and P. Enge, “Global Positioning System: Signals, Measurements and Performance,” Ganga-Jamuna Press, Massachusetts, 2010.
[2]	M. Grewal, L. Weill and A. Andrews, “Global Positioning Systems Inertial Navigation, and Integration,” 2nd Edition, Wiley-Interscience, New Jersey, 2007. doi:10.1002/0470099720
[3]	N. El-Sheimy, “Inertial Techniques and INS/DGPS Integration,” ENGO 623-Course Notes, University of Calgary, Calgary, 2006.
[4]	P. Aggarwal, Z. Syed, A. Noureldin and N. El-Sheimy, “Integrated MEMS Based Navigation Systems,” Artech House, Norwood, 2010.
[5]	P. Aggarwal, Z. Syed, X. Niu and N. El-Sheimy, “A Standard Testing and Calibration Procedure for Low Cost MEMS Inertial Sensors and Units,” Journal of Navigation, Vol. 61, No. 2, 2007, pp. 323-336.
[6]	C. Hide, “Integration of GPS and Low-Cost INS Measurements,” Ph.D. Thesis, University of Nottingham, Nottingham, 2003.
[7]	B. Ristic, S. Arulampalan and N. Gordon, “Beyond the Kalman Filter: Particle Filters for Tracking Applications,” Artech House, 2004.
[8]	S. Julier, J. Uhlmann and H. Durrant, “A New Approach for Nonlinear Transformations of Means and Covariances in Filters and Estimators,” IEEE Transactions on Automatic Control, Vol. 45, No. 3, 2000, pp. 477-482. doi:10.1109/9.847726
[9]	N. Bergman, “Recursive Bayesian Estimation: Navigation and Tracking Applications,” Ph.D. Thesis, Link?ping University, Link?ping, 1999.
[10]	A. Doucet, N. Freitas and N. Gordon, “Sequential Monte Carlo Methods in Practice,” Springer, New York, 2001.
[11]	M. Arulampalam, S. Maskell, N. Gordon and T. Clapp, “A Tutorial on Particle Filters for Online Nonlinear/NonGaussian Bayesian Tracking,” IEEE Transactions on Signal Processing, Vol. 50, No. 2, 2002, pp. 174-188. doi:10.1109/78.978374
[12]	A. Doucet and A. Johansen, “A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later,” In: D. Crisan and B. Rozovsky, Eds., Handbook of Nonlinear Filtering, Oxford University Press, Oxford, 2011.
[13]	F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson and P. Nordlund, “Particle Filters for Positioning, Navigation and Tracking,” IEEE Transactions on Signal Processing, Vol. 50, No. 2, 2002, pp. 425-437. doi:10.1109/78.978396
[14]	G. Kitagawa, “Monte Carlo Filter and Smoother for NonGaussian Nonlinear State Space Models,” Journal of Computational and Graphical Statistics, Vol. 5, No. 1, 1996, pp. 1-25.
[15]	R. Merwe, A. Doucet, J. Freitas and E. Wan, “The Unscented Particle Filter,” University of Cambridge, Cambridge, 2000.
[16]	A. Haug, “A Tutorial on Bayesian Estimation and Tracking Techniques Applicable to Nonlinear and Non-Gaussian Processes,” MITRE Technical Report, MTR 05W0000004, MITRE Corporation, 2005.
[17]	N. Gordon, D. Salmond and A. Smith, “Novel Approach to Nonlinear and Non-Gaussian Bayesian State Estimation,” Proceedings of the IEEE, Vol. 140, 1993, pp. 107-113.
[18]	P. Aggarwal, D. Gu and N. El-Sheimy, “Extended Particle Filter (EPF) for Land Vehicle Navigation Applications,” International Global Navigation Satellite Systems (IGNSS), Sydney, 4-6 December 2007.
[19]	P. Aggarwal, Z. Syed and N. El-Sheimy, “Hybrid Extended Particle Filter for Integrated Navigation and Global Positioning System,” Measurement Science and Technology, Vol. 20, No. 5, 2009.
[20]	A. Doucet, N. Freitas, K. Murphy and S. Russell, “RaoBlackwellised Particle Filtering for Dynamic Bayesian Networks,” Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, Stanford, 30 June 3 July 2000, pp. 176-183.
[21]	Z. Chen, “Bayesian Filtering: From Kalman Filters to Particle Filters, and Beyond,” Adaptive Systems Laboratory Technical Report, McMaster University, Hamilton.
[22]	Y. Jianjun, Z. Jianqiu and M. Klaas, “The Marginal RaoBlackwellized Particle Filter for Mixed Linear/Nonlinear State Space Models,” Chinese Journal of Aeronautics, Vol. 20, No. 4, 2007, pp. 346-352. doi:10.1016/S1000-9361(07)60054-5
[23]	M. Pitt and N. Shephard, “Filtering via Simulation: Auxiliary Particle Filters,” Journal of the American Statistical Association, Vol. 94, No. 446, 1999, pp. 590-599. doi:10.1080/01621459.1999.10474153
[24]	J. Georgy, A. Noureldin, M. Korenberg and M. Bayoumi, “Low Cost 3-D Navigation Solution for RISS/GPS Integration Using Mixture Particle Filter,” IEEE Transactions on Vehicular Technology, Vol. 59, No. 2, 2010, pp. 599-615. doi:10.1109/TVT.2009.2034267
[25]	Q. Du, V. Faber and M. Gunzburger, “Centroidal Voronoi Tesselations: Applications and Algorithms”, SIAM Review, Vol. 41, No. 4, 1999, pp. 637-676. doi:10.1137/S0036144599352836