Over the past few years, particle filters have been applied with great success to a variety of state estimation problems. In this paper we present a statistical approach to increasing the efficiency of particle filters by adapting the size of sample sets during the estimation process. The key idea of the KLD-sampling method is to bound the approximation error introduced by the sample-based representation of the particle filter. The name KLD-sampling is due to the fact that we measure the approximation error using the Kullback-Leibler distance. Our adaptation approach chooses a small number of samples if the density is focused on a small part of the state space, and it chooses a large number of samples if the state uncertainty is high. Both the implementation and computation overhead of this approach are small. Extensive experiments using mobile robot localization as a test application show that our approach yields drastic improvements over particle filters with fixed sample set sizes and over a previously introduced adaptation technique.
Get full access to this article
View all access options for this article.
References
1.
Arras, K. O., Castellanos, J. A., and Siegwart, R. 2002. Feature-based multi-hypothesis localization and tracking for mobile robots using geometric constraints . In Proceedings of the IEEE International Conference on Robotics and Automation.
2.
Arras, K. O., and Vestli, S. J. 1998. Hybrid, high-precision localization for the mail distributing mobile robot system MOPS . In Proceedings of the IEEE International Conference on Robotics and Automation.
3.
Arulampalam, S., Maskell, S., Gordon, N., and Clapp, T. 2002. A tutorial on particle filters for on-line nonlinear/non-Gaussian Bayesian tracking . IEEE Transactions on Signal Processing50(2): 174-188 .
4.
Austin, D., and Jensfelt, P. 2000. Using multiple Gaussian hypotheses to represent probability distributions for mobile robot localization . In Proceedings of the IEEE International Conference on Robotics and Automation.
5.
Baker, J. E. 1987. Reducing bias and inefficiency in the selection algorithm . In Proceedings of the 2nd International Conference on Genetic Algorithms.
6.
Bar-Shalom, Y., and Li, X.-R. 1995. Multitarget-Multisensor Tracking: Principles and Techniques, Yaakov Bar-Shalom .
7.
Burgard, W.,Fox, D.,Hennig, D., and Schmidt, T. 1996. Estimating the absolute position of a mobile robot using position probability grids . In Proceedings of the National Conference on Artificial Intelligence.
8.
Burgard, W.,Derr, A.,Fox, D., and Cremers, A. B. 1998. Integrating global position estimation and position tracking for mobile robots: the Dynamic Markov Localization approach . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
9.
Burgard, W., Cremers, A. B., Fox, D., Hähnel, D., Lakemeyer, G., Schulz, D.,Steiner, W., and Thrun, S. 1999. Experiences with an interactive museum tour-guide robot . Artificial Intelligence114(1-2): 3-55 .
10.
Castellanos, J. A., Montiel, J. M. M., Neira, J., and Tardós, J. D. 1999. The SPmap: A probabilistic framework for simultaneous localization and map building . IEEE Transactions on Robotics and Automation15(5): 948-952 .
11.
Choset, H., and Nagatani, K. 2001. Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization . IEEE Transactions on Robotics and Automation17(2): 125-137 .
12.
Cover, T. M., and Thomas, J. A. 1991. Elements of Information Theory, Wiley Series in Telecommunications, Wiley, New York .
13.
Cox, I. J. 1991. Blanche—an experiment in guidance and navigation of an autonomous robot vehicle . IEEE Transactions on Robotics and Automation7(2): 193-204 .
14.
Cox, I. J. 1993. A review of statistical data association techniques for motion correspondence . International Journal of Computer Vision10(1): 53-66 .
15.
Cox, I. J., and Leonard, J. J. 1994. Modeling a dynamic environment using a Bayesian multiple hypothesis approach . Artificial Intelligence66: 311-344 .
16.
Deans, M. C. 2002. Maximally informative statistics for localization and mapping . In Proceedings of the IEEE International Conference on Robotics and Automation.
17.
de Freitas, N. 2002. Rao-Blackwellised particle filtering for fault diagnosis. IEEE Aerospace.
18.
Del Moral, P., and Miclo, L. 2000. Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to non linear filtering. In Seminaire de Probabilites XXXIV, Lecture Notes in Mathematics Vol. 1729, Springer-Verlag, Berlin .
19.
Dellaert, F., Burgard, W., Fox, D., and Thrun, S. 1999. Using the condensation algorithm for robust, vision-based mobile robot localization . In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
20.
Dissanayake, M. W. M., Newman, P., Clark, S., Durrant-Whyte, H. F., and Csorba, M. 2001. A solution to the simultaneous localization and map building (SLAM) problem . IEEE Transactions on Robotics and Automation17(3): 229-241 .
21.
Doucet, A., Godsill, S. J., and Andrieu, C. 2000a. On sequential Monte Carlo sampling methods for Bayesian filtering . Statistics and Computing10(3): 197-208 .
22.
Doucet, A., de Freitas, J. F. G., Murphy, K., and Russell, S. 2000b. Rao-Blackwellised particle filtering for dynamic Bayesian networks . In Proceedings of the Conference on Uncertainty in Artificial Intelligence.
23.
Doucet, A., de Freitas, N., and Gordon, N., editors. 2001. Sequential Monte Carlo in Practice, Springer-Verlag, New York .
24.
Enderle, S., Ritter, M., Fox, D., Sablatnög, S., Kraetzschmar, G., and Palm, G. 2000. Soccer-robotlocalization using sporadic visual features . In Proceedings of the International Conference on Intelligent Autonomous Systems.
25.
Engelson, S., and McDermott, D. 1992. Error correction in mobile robot map learning . In Proceedings of the IEEE International Conference on Robotics and Automation.
26.
Fox, D. December 1998. Markov Localization: A Probabilistic Framework for Mobile Robot Localization and Naviagation. Ph.D. thesis, Department of Computer Science, University of Bonn, Germany.
27.
Fox, D. 2002. KLD-sampling: Adaptive particle filters. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14 (NIPS), MIT Press, Cambridge, MA .
28.
Fox, D., Burgard, W., Dellaert, F., and Thrun, S. 1999a. Monte Carlo Localization: Efficient position estimation for mobile robots . In Proceedings of the National Conference on Artificial Intelligence.
29.
Fox, D., Burgard, W., and Thrun, S. 1999b. Markov localization for mobile robots in dynamic environments . Journal of Artificial Intelligence Research (JAIR)11: 391-427 .
30.
Fox, D., Burgard, W., Kruppa, H., and Thrun, S. 2000. A probabilistic approach to collaborative multi-robot localization . Autonomous Robots8(3): 325-344 .
31.
Fox, D., Thrun, S., Dellaert, F., and Burgard, W. 2001. Particle filters for mobile robot localization. In A. Doucet, N. de Freitas, and N. Gordon, editors, Sequential Monte Carlo in Practice, Springer-Verlag, New York .
32.
Gelb, A. 1974. Applied Optimal Estimation, MIT Press, Cambridge, MA .
33.
Ghahramani, Z. 2001. An introduction to hidden Markov models and Bayesian networks . International Journal of Pattern Recognition and Artificial Intelligence15(1): 9-42 .
34.
Gilks, W. R., and Berzuini, C. 2001. Following a moving target—Monte Carlo inference for dynamic Bayesian models . Journal of the Royal Statistical Society, Series B63(1): 127-146 .
35.
Godsill, S., and Clapp, T. 2001. Improvement strategies for Monte Carlo particle filters. In A. Doucet, N. de Freitas, and N. Gordon, editors, Sequential Monte Carlo in Practice, Springer-Verlag, New York .
36.
Gustafsson, F., Gunnarsson, F., Bergman, N., Forssell, U., Jansson, J., Karlsson, R., and Nordlund, P.-J. 2002. Particle filters for positioning, navigation and tracking . IEEE Transactions on Signal Processing.
37.
Gutmann, J. S., Burgard, W., Fox, D., and Konolige, K. 1998. An experimental comparison of localization methods . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
38.
Gutmann, J. S., and Fox, D. 2002. An experimental comparison of localization methods continued . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
39.
Gutmann, J. S., Weigel, T., and Nebel, B. 1999. Fast, accurate, and robust self-localization in polygonal environments . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
40.
Hertzberg, J., and Kirchner, F. 1996. Landmark-based autonomous navigation in sewerage pipes . In Proceedings of the 1st Euromicro Workshop on Advanced Mobile Robots, IEEE Computer Society Press, Los Alamitos, CA.
41.
Isard, M. and Blake, A. 1998. Condensation - conditional density propagation for visual tracking . International Journal of Computer Vision29(1): 5-28 .
42.
Jensfelt, P., and Kristensen, S. 2001. Active global localization for a mobile robot using multiple hypothesis tracking . IEEE Transactions on Robotics and Automation17(5): 748-760 .
43.
Jensfelt, P., Wijk, O., Austin, D., and Andersson, M. 2000. Feature based condensation for mobile robot localization . In Proceedings of the IEEE International Conference on Robotics and Automation.
44.
Johnson, N., Kotz, S., and Balakrishnan, N. 1994. Continuous Univariate Distributions, Vol. 1, Wiley, New York .
45.
Julier, S. J., and Uhlmann, J. K. 1997. A new extension of the Kalman filter to non-linear systems . In Proceedings of Aero Sense: The 11th International Symposium on Aerospace/Defense Sensing, Simulation and Controls.
46.
Kaelbling, L. P., Cassandra, A. R., and Kurien, J. A. 1996. Acting under uncertainty: Discrete Bayesian models for mobile-robot navigation . In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
47.
Kalman, R. E. 1960. A new approach to linear filtering and prediction problems . Transactions of the ASME, Journal of Basic Engineering82: 35-45 .
48.
Kitagawa, G. 1996. Monte Carlo filter and smoother for non-Gaussian non-linear state space models . Journal of Computational and Graphical Statistics5(1): 1-25 .
49.
Koller, D., and Fratkina, R. 1998. Using learning for approximation in stochastic processes . In Proceedings of the International Conference on Machine Learning.
50.
Koller, D., and Lerner, U. 2001. Sampling in factored dynamic systems. In A. Doucet, N. de Freitas, and N. Gordon, editors, Sequential Monte Carlo in Practice, Springer-Verlag, New York .
51.
Konolige, K., and Chou, K. 1999. Markov localization using correlation . In Proceedings of the International Joint Conference on Artificial Intelligence.
52.
Kuipers, B. 2000. The spatial semantic hierarchy . Artificial Intelligence119: 191-233 .
53.
Kuipers, B., and Beeson, P. 2002. Bootstrap learning for place recognition . In Proceedings of the National Conference on Artificial Intelligence.
54.
Lenser, S., and Veloso, M. 2000. Sensor resetting localization for poorly modelled mobile robots . In Proceedings of the IEEE International Conference on Robotics and Automation.
55.
Leonard, J. J., and Durrant-Whyte, H. F. 1991. Mobile robot localization by tracking geometric beacons . IEEE Transactions on Robotics and Automation7(3): 376-382 .
56.
Leonard, J. J., and Feder, H. J. S. 1999. A computationally efficient method for large-scale concurrent mapping and localization . In Proceedings of the 9th International Symposium on Robotics Research.
57.
Liu, J., and Chen, R. 1998. Sequential Monte Carlo methods for dynamic systems . Journal of the American Statistical Association93(443): 1032 .
58.
Lu, F., and Milios, E. 1997. Robot pose estimation in unknown environments by matching 2D range scans . Journal of Intelligent and Robotic Systems18: 249-275 .
59.
Montemerlo, M., Thrun, S., Koller, D., and Wegbreit, B. 2002a. FastSLAM: A factored solution to the simultaneous localization and mapping problem . In Proceedings of the National Conference on Artificial Intelligence.
60.
Montemerlo, M., Thrun, S., and Whittaker, W. 2002b. Conditional particle filters for simultaneous mobile robot localization and people-tracking . In Proceedings of the IEEE International Conference on Robotics and Automation.
61.
Moore, A. W., Schneider, J., and Deng, K. 1997. Efficient locally weighted polynomial regression predictions . In Proceedings of the International Conference on Machine Learning.
62.
Murphy, K., and Russell, S. 2001. Rao-Blackwellised particle filtering for dynamic Bayesian networks. In A. Doucet, N. de Freitas, and N. Gordon, editors, Sequential Monte Carlo in Practice, Springer-Verlag, New York .
63.
Olson, C. F. 2000. Probabilistic self-localization for mobile robots . IEEE Transactions on Robotics and Automation16(1): 55-66 .
64.
Omohundro, S. M. 1991. Bumptrees for efficient function, constraint, and classification learning. In R. P. Lippmann, J. E. Moody, and D. S. Touretzky, editors, Advances in Neural Information Processing Systems 3, Morgan Kaufmann, San Mateo, CA .
65.
Pelikan, M., Goldberg, D. E., and Cantú-Paz, E. 2000. Bayesianoptimizationalgorithm, populationsize, and time to convergence . In Proceedings of the Genetic and Evolutionary Computation Conference.
66.
Pitt, M. K., and Shephard, N. 1999. Filtering via simulation: auxiliary particle filters . Journal of the American Statisti- cal Association94(446): 590-599 .
67.
Rice, J. A. 1995. Mathematical Statistics and Data Analysis, 2nd edition, Duxbury Press, Belmont, CA .
68.
Roumeliotis, S. I., and Bekey, G. A. 2000. Bayesian estimation and Kalman filtering: A unified framework for mobile robot localization . In Proceedings of the IEEE International Conference on Robotics and Automation.
69.
Schulz, D., Burgard, W., Fox, D., and Cremers, A. B. 2001. Trackingmultiplemovingtargetswithamobilerobotusing particle filters and statistical data association . In Proceedings of the IEEE International Conference on Robotics and Automation.
70.
Simmons, R., and Koenig, S. 1995. Probabilistic robot navigation in partially observable environments . In Proceedings of the International Joint Conference on Artificial Intelligence.
71.
Smith, A. F. M., and Gelfand, A. E. 1992. Bayesian statistics without tears: A sampling-resampling perspective . American Statistician46(2): 84-88 .
72.
Smith, R., Self, M., and Cheeseman, P. 1990. Estimating uncertain spatial relationships in robotics. In I. Cox and G. Wilfong, editors, Autonomous Robot Vehicles, Springer Verlag, Berlin .
73.
Thrun, S., Langford, J., and Fox, D. 1999. Monte Carlo hidden Markov models: Learning non-parametric models of partially observable stochastic processes . In Proceedings of the International Conference on Machine Learning.
74.
Thrun, S., Beetz, M., Bennewitz, M., Burgard, W., Cremers, A. B., Dellaert, F., Fox, D., Haehnel, D., Rosenberg, C., Roy, N., Schulte, J., and Schulz, D. 2000. Probabilistic algorithms and the interactive museum tour-guide robot Minerva . International Journal of Robotics Research19(11): 972-999 .
75.
Thrun, S., Fox, D., Burgard, W., and Dellaert, F. 2001. Robust Monte Carlo localization for mobile robots . Artificial Intelligence128(1-2): 99-141 .
76.
Verma, V., Langford, J., and Simmons, R. 2001. Nonparametric fault identification for space rovers . In International Symposium on Artificial Intelligence and Robotics in Space.
77.
Vermaak, J., Andrieu, C., Doucet, A., and Godsill, S. J. 2002. Particle methods for Bayesian modelling and enhancement of speech signals . IEEE Transactions on Speech and Audio Processing10(3): 173-185 .
78.
Vlassis, N., Terwijn, B., and Kröse, B. 2002. Auxiliary particle filter robot localization from high-dimensional sensor observations . In Proceedings of the IEEE International Conference on Robotics and Automation.
79.
Wan, E. A., and van der Merwe, R. 2000. The unscented Kalman filter for non-linear estimation . In Proceedings of Symposium 2000 on Adaptive Systems for Signal Processing, Communications, and Control.
80.
Welch, G., and Bishop, G. 2001. An introduction to the Kalman filter. Notes of ACM SIGGRAPH tutorial on the Kalman filter.
81.
Wolf, J., Burgard, W., and Burkhardt, H. 2002. Robust vision-based localization for mobile robots using an image retrieval system based on invariant features . In Proceedings of the IEEE International Conference on Robotics and Automation.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
