In this work we address the problem of optimal Bayesian filtering for dynamic systems with observation models that cannot be approximated properly as any parameterized distribution. In the context of mobile robots this problem arises in localization and simultaneous localization and mapping (SLAM) with occupancy grid maps. The lack of a parameterized observation model for these maps forces a sample-based representation, commonly through Monte Carlo methods for sequential filtering, also called particle filters. Our work is grounded on the demonstrated existence of an optimal proposal distribution for particle filters. However, this optimal distribution is not directly applicable to systems with non-parametric models. By integrating ideas from previous works on adaptive sample size, auxiliary particle filters, and rejection sampling, we derive a new particle filter algorithm that enables the usage of the optimal proposal to estimate the true posterior density of a non-parametric dynamic system. This new filter is better suited, both theoretically and in practice, than previous approximate methods for indoor and outdoor localization and SLAM, as confirmed by experiments with real robots.
Arulampalam, M., Maskell, S., Gordon, N., Clapp, T., Sci, D., Organ, T. and Adelaide, S. ( 2002). A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing , 50(2): 174-188.
2.
Beevers, K. and Huang, W. ( 2007). Fixed-lag sampling strategies for particle filtering SLAM. International Conference on Robotics and Automation (ICRA).
3.
Blanco, J., Fernández-Madrigal, J. and Gonzalez, J. ( 2007). A new approach for large-scale localization and mapping: hybrid metric-topological SLAM. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2061-2067.
4.
Blanco, J., Gonzalez, J. and Fernández-Madrigal, J. ( 2008). An optimal filtering algorithm for non-parametric observation models in robot localization. IEEE International Conference on Robotics and Automation (ICRA’08), pp. 461-466.
5.
Bosse, M., Newman, P., Leonard, J. and Teller, S. ( 2004). Simultaneous localization and map building in large-scale cyclic environments using the Atlas framework. The International Journal of Robotics Research, 23(12): 1113-1139.
6.
Choo, K. and Fleet, D. ( 2001). People tracking using hybrid Monte Carlo filtering. Proceedings of IEEE International Conference on Computer Vision , Vol. 2, pp. 321-328.
7.
Cover, T. and Thomas, J. ( 1991). Elements of Information Theory. New York, Wiley.
8.
Davison, A., Reid, I., Molton, N. and Stasse, O. ( 2007). MonoSLAM: real-time single camera SLAM. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(6): 1052-1067.
9.
Dissanayake, M., Newman, P., Clark, S., Durrant-Whyte, H., and Csorba, M. ( 2001). A solution to the simultaneous localization and map building (SLAM) problem. IEEE Transactions on Robotics and Automation , 17(3): 229-241.
10.
Doucet, A., Briers, M. and Senecal, S. ( 2006). Efficient block sampling strategies for sequential Monte Carlo methods. Journal of Computational and Graphical Statistics , 15(3): 693-711.
11.
Doucet, A., de Freitas, N. and Gordon, N. ( 2001). Sequential Monte Carlo Methods in Practice. Berlin, Springer.
12.
Doucet, A., de Freitas, N., Murphy, K. and Russell, S. ( 2000a). Rao-Blackwellised particle filtering for dynamic Bayesian networks. Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, pp. 176-183.
13.
Doucet, A., Godsill, S. and Andrieu, C. ( 2000b). On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 10(3): 197-208.
14.
Estrada, C., Neira, J. and Tardos, J. ( 2005). Hierarchical SLAM: real-time accurate mapping of large environments. IEEE Transactions on Robotics, 21(4): 588-596.
15.
Fox, D. ( 2003). Adapting the sample size in particle filters through KLD-sampling. International Journal of Robotics Research, 22(12): 985-1003.
16.
Fox, D., Burgard, W., Dellaert, F. and Thrun, S. ( 1999a). Monte Carlo localization: Efficient position estimation for mobile robots. Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 113-114.
17.
Fox, D., Burgard, W. and Thrun, S. ( 1999b). Markov localization for mobile robots in dynamic environments . Journal of Artificial Intelligence Research, 11(3): 391-427.
18.
Gonzalez, J., Muñoz, A., Galindo, C., Fernández-Madrigal, J. and Blanco, J. ( 2006). A description of the SENA robotic wheelchair. Proceedings of the IEEE Mediterranean Electrotechnical Conference , pp. 437-440.
19.
Gordon, N., Salmond, D. and Smith, A. ( 1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEEE Proceedings on Radar and Signal Processing , 140(2): 107-113.
20.
Grisetti, G., Stachniss, C. and Burgard, W. ( 2007a). Improved techniques for grid mapping with Rao-Blackwellized particle filters. IEEE Transactions on Robotics, 23: 34-46.
21.
Grisetti, G., Tipaldi, G., Stachniss, C., Burgard, W. and Nardi, D. ( 2007b). Fast and accurate slam with Rao-Blackwellized particle filters. Robotics and Autonomous Systems, 55(1): 30-38.
22.
Guivant, J. and Nebot, E. ( 2001). Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE Transactions on Robotics and Automation, 17(3): 242-257.
23.
Gutmann, J. and Konolige, K. ( 1999). Incremental mapping of large cyclic environments. Proceedings of IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 318-325.
24.
Hahnel, D., Burgard, W., Fox, D. and Thrun, S. ( 2003). An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 1.
25.
Julier, S. ( 2002) The scaled unscented transformation. Proceedings of the American Control Conference, Vol. 6, pp. 4555-4559.
26.
Julier, S. and Uhlmann, J. ( 1997). A new extension of the Kalman filter to nonlinear systems . International Symposium of Aerospace/ Defense Sensing, Simulation and Controls pp. 182-193.
27.
Kalman, R. ( 1960). A new approach to linear filtering and prediction problems . Journal of Basic Engineering, 82(1): 35-45.
28.
Knuth, D. ( 1981). The Art of Computer Programming: Seminumerical Algorithms , Vol. 2. Reading, MA, Addison-Wesley.
29.
Liu, J. ( 1996). Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Statistics and Computing, 6(2): 113-119.
30.
Liu, J. and Chen, R. ( 1998). Sequential Monte Carlo Methods for dynamic systems. Journal of the American Statistical Association, 93(443): 1032-1044.
31.
Loutfi, A., Lilienthal, A., Blanco, J., Galindo, C. and Gonzalez, J. ( 2007). Integrating SLAM into gas distribution mapping. Proceedings of the IEEE International Conference on Robotics and Automation.
32.
Montemerlo, M. ( 2003). FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem With Unknown Data Association. PhD Thesis, University of Washington.
33.
Montemerlo, M., Thrun, S., Koller, D. and Wegbreit, B. ( 2002a). FastSLAM: a factored solution to the simultaneous localization and mapping problem. Proceedings of the AAAI National Conference on Artificial Intelligence, pp. 593-598.
34.
Montemerlo, M., Thrun, S. and Whittaker, W. ( 2002b). Conditional particle filters for simultaneous mobile robot localization and people-tracking. Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1, pp. 695-701.
35.
Moravec, H. and Elfes, A. ( 1985). High resolution maps from wide angle sonar. Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 2.
36.
Murphy, K. ( 1999). Bayesian map learning in dynamic environments. Advances in Neural Information Processing Systems (NIPS), 12: 1015-1021.
37.
Neira, J. and Tardós, J. ( 2001). Data association in stochastic mapping using the Joint Compatibility test. IEEE Transactions on Robotics and Automation , 17(6): 890-897.
38.
Nummiaro, K., Koller-Meier, E. and Van Gool, L. ( 2003). An adaptive color-based particle filter. Image and Vision Computing, 21(1): 99-110.
39.
Okuma, K., Taleghani, A., de Freitas, N., Little, J. and Lowe, D. (2004). A boosted particle filter: Multitarget detection and tracking. European Conference on Computer Vision, 1: 28-39.
40.
Pitt, M. and Shephard, N. ( 1999). Filtering via simulation: auxiliary particle filters . Journal of the American Statistical Association, 94(446): 590-591.
41.
Ranganathan, A., Menegatti, E. and Dellaert, F. ( 2006). Bayesian inference in the space of topological maps. IEEE Transactions on Robotics, 22(1): 92-107.
42.
Ristic, B., Arulampalam, S. and Gordon, N. ( 2004). Beyond the Kalman Filter: Particle Filters for Tracking Applications. Norwood, MA, Artech House.
43.
Rubin, D. ( 1987). A noniterative sampling/importance resampling alternative to the data augmentation algorithm for creating a few imputations when fractions of missing information are modest: the SIR algorithm. Journal of the American Statistical Association, 82(398): 543-546.
44.
Rubin, D. ( 1988). Using the SIR algorithm to simulate posterior distributions . Bayesian Statistics, 3: 395-402.
45.
Schulz, D., Burgard, W., Fox, D. and Cremers, A. ( 2001). Tracking multiple moving targets with a mobile robot using particle filters and statistical data association. Proceedings of the IEEE International Conference on Robotics and Automation , Vol. 2.
46.
Tenne, D. and Singh, T. ( 2003). The higher order unscented filter. Proceedings of the American Control Conference, Vol. 3, pp. 2441-2446.
47.
Thrun, S. ( 2001). A probabilistic on-line mapping algorithm for teams of mobile robots. The International Journal of Robotics Research , 20(5): 335.
48.
Thrun, S. ( 2002). Robotic Mapping: A Survey. School of Computer Science, Carnegie Mellon University.
49.
Thrun, S. ( 2003). Learning occupancy grid maps with forward sensor models . Autonomous Robots, 15(2): 111-127.
50.
Thrun, S., Burgard, W. and Fox, D. ( 2005). Probabilistic Robotics. Cambridge, MA, The MIT Press.
51.
Thrun, S., Fox, D., Burgard, W. and Dellaert, F. ( 2001). Robust Monte Carlo localization for mobile robots. Artificial Intelligence, 128(1-2): 99-141.
52.
Thrun, S., Liu, Y., Koller, D., Ng, A., Ghahramani, Z. and Durrant-Whyte, H. ( 2004). Simultaneous localization and mapping with sparse extended information filters. The International Journal of Robotics Research, 23(7-8): 693.
53.
Vlassis, N., Terwijn, B. and Krose, B. ( 2002). Auxiliary particle filter robot localization from high-dimensional sensor observations. Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1.
54.
Wan, E. and Van Der Merwe, R. ( 2000). The unscented Kalman filter for nonlinear estimation . Proceedings of the IEEE Adaptive Systems for Signal Processing, Communications, and Control Symposium, pp. 153-158.
