Estimating the configuration of a vehicle is crucial for its navigation. Most approaches are based on (extended) Kalman filtering or particle filtering. An attractive alternative is considered here, which relies on interval analysis. Contrary to classical extended Kalman filtering it allows global localization, and contrary to particle filtering it provides guaranteed results in the sense that a set is computed that contains all of the configurations that are consistent with the data and hypotheses. This paper presents a real-time implementation of the process including a description of the platform and its modeling, the integration of the errors on the model and the localization method itself.
Anderson, B. and Moore, J. (1979). Optimal Filtering. Prentice-Hall , Englewood Cliffs, NJ.
2.
Arulampalam, M. et al. (2002). A tutorial on particle filters for on-line non-linear/non-gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2): 174-188.
3.
Bertsekas, D.P. and Rhodes, I.B. (1971). Recursive state estimation for a set-membership description of uncertainty. IEEE Transactions on Automatic Control, 16(2): 117-128.
4.
Borenstein, J., Everett, B. and Feng, L. (1996). Navigating Mobile Robots: Systems and Techniques . A. K. Peters Ltd., Wellesley, MA.
5.
Bouaziz, S. et al. (2003). Picar: experimental platform for road tracking applications. Proceedings of the IEEE International Conference on Intelligent Vehicle (IV), Colombus, pp. 495-499.
6.
Brönnimann, H., Melquiond, G. and Pion, S. (2005). A proposal to add interval arithmetic to the C++ standard library. Technical Report RR-5646, INRIA.
7.
Burgard, W. et al. (1996). Estimating the absolute position of a mobile robot using position probability grids. Proceedings of the National Conference on Artificial Intelligence (AAAI), Portland, OR, Vol. 2, pp. 896-901.
8.
Cox, I. and Wilfong, G. (eds) (1990). Autonomous Robot Vehicles . Springer, New-York.
9.
Crowley, J.L. (1989). World modeling and position estimation for a mobile robot using ultrasonic ranging. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Scottsdale, AZ, pp. 674-680.
10.
Dellaert, F. et al. (1999). Monte-Carlo localisation for mobile robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, pp. 1322-1328.
11.
Gelb, A. (1974). Applied Optimal Estimation. MIT Press, Cambridge, MA.
12.
Gning, A. and Bonnifait, P. (2005). Dynamic vehicle localization using constraints propagation techniques on intervals. A comparison with Kalman filtering. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Barcelona, pp. 4155-4160.
13.
Gollamudi, S. et al. (1996). Set-membership state estimation with optimal bounding ellipsoids. Proceedings of the International Symposium on Information Theory and its Applications. Victoria, B. C., Canada, pp. 262-265.
14.
Gordon, N.J., Salmond, D.J. and Smith, A.F. (1993). Novel approach to non-linear/non-gaussian bayesian state estimation. IEE Proceedings, Part F, 140(2): 107-113.
15.
Hamzo, C. and Kreinovich, V. (1999). On average bit complexity of interval arithmetic . Bulletin of the European Association for Theoretical Computer Science, 68: 153- 156.
16.
Hofschuster, W. and Krämer, W. (2004). C-XSC 2.0: A C++ Library for Extended Scientific Computing (Lecture Notes in Computer Science, Vol. 2991). Springer-Verlag, Heidelberg.
17.
IEEE Computer Society (1985). IEEE standard for binary floating-point arithmetic. Technical Report IEEE Std. 754-1985, American National Standards Institute. Available at: http://standards.ieee.org/.
18.
Ito, K. and Xiong, K. (2000). Gaussian filters for nonlinear filtering problems . IEEE Transactions on Automatic Control, 45: 910-927.
19.
Jaulin, L. et al. (2001). Applied Interval Analysis. Springer, London.
20.
Jaulin, L. et al.(2003). Guaranteed robust nonlinear estimation, with application to robot localization. IEEE Transactions on Systems, Man and Cybernetics; Part C - Applications and Reviews, 32(4): 374-382.
21.
Jaulin, L. and Walter, E. (1993). Set inversion via interval analysis for nonlinear bounded-error estimation. Automatica, 29(4): 1053-1064.
22.
Kalman, R.E. (1960). A new approach to linear filtering and prediction problems. Transactions of the AMSE, Part D, Journal of Basic Engineering, 82: 35-45.
23.
Kieffer, M., Jaulin, L. and Walter, E. (1998). Guaranteed recursive nonlinear state estimation using interval analysis. Proceedings of the 37th IEEE Conference on Decision and Control, Tampa, FL, pp. 3966-3971.
24.
Kieffer, M., Jaulin, L. and Walter, E. (2002). Guaranteed recursive nonlinear state bounding using interval analysis. International Journal of Adaptative Control and Signal Processing, 6(3): 193-218.
25.
Kieffer, M. et al. (2000). Robust autonomous robot localization using interval analysis. Reliable Computing, 6(3): 337- 362.
26.
Kieffer, M. et al. (2005). Guaranteed robust nonlinear state estimator with application to global vehicle tracking. Proceedings of the IEEE International Conference on Decision and Control (CDC), Sevilla, Spain, pp. 6424-6429.
27.
Kitagawa, G. (1996). Monte-Carlo filter and smoother for non-gaussian non-linear state space models. J. Comput. Graph. Statist. , 5(1): 1-25.
28.
Knüppel, O. (1994). PROFIL/BIAS - A fast interval library. Computing, 53: 277-287.
29.
Kreinovich, V. et al. (1998). Computational complexity and feasibility of data processing and interval computations. Reliable Computing , 4(4): 405-409.
30.
Kuc, R. and Barshan, B. (1989). Navigating vehicles through an unstructured environment with sonar. Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 3, Scottsdale, AZ, pp. 1422-1426.
31.
Lambert, A. and Fort-Piat, N.L. (2000). Safe task planning integrating uncertainties and local maps federation. International Journal of Robotics Research , 19(6): 597- 611.
32.
Leonard, J.J. and Durrant-Whyte, H.F. (1992). Directed Sonar Sensing for Mobile Robot Navigation. Kluwer, Boston.
33.
Meizel, D. et al. (2002). Initial localization by set inversion. IEEE Transactions on Robotics and Automation, 18(6): 966-971.
Norton, J. P. (ed.) (1994). Special Issue on Bounded-Error Estimation: Issue 1. International Journal of Adaptive Control and Signal Processing, 8(1): 1-118.
36.
Norton, J. P. (ed.) (1995). Special Issue on Bounded-Error Estimation: Issue 2. International Journal of Adaptive Control and Signal Processing, 9(1): 1-132.
37.
Pion, S. (1999). Interval arithmetic: an efficient implementation and an application to computational geometry. Proceedings of the Workshop on Applications of Interval Analysis to Systems and Control with Special Emphasis on Recent Advances in Modal Interval Analysis MISC'99, Girona, Spain, pp. 99-109.
38.
Pitt, M. and Shephard, N. (1999). Filtering via simulation: Auxiliary particle filters . Journal of the American Statistical Association, 94(446): 590-599.
39.
Schweppe, F.C. (1968). Recursive state estimation: unknown but bounded errors and system inputs. IEEE Transactions on Automatic Control , 13(1): 22-28.
40.
Seignez, E. (2006). Etude et comparaison expérimentale de méthodes de localisation multicapteurs. Thèse de doctorat, Université Paris-Sud.
41.
Seignez, E. et al. (2005a). Experimental vehicle localization by bounded-error state estimation using interval analysis. Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS) , Edmonton, Canada, pp. 1277-1282.
42.
Seignez, E., Lambert, A. and Maurin, T. (2005b). Autonomous parking carrier for intelligent vehicle . Proceedings of the IEEE International Conference on Intelligent Vehicle (IV), Las Vegas, USA, pp. 411-416.
43.
Simmons, R. and Koenig, S. (1995). Probabilistic robot navigation in partially observable environments. Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, Canada.
44.
Sorenson, H. (1985). Kalman Filtering: Theory and Application. IEEE Press, New York.
45.
Terwiesch, P. and Agarwal, M. (1995). A discretized nonlinear state estimator for batch processes. Computers and Chemical Engineering, 19: 155-169.
46.
Thrun, S. et al. (2001). Robust Monte-Carlo localization for mobile robots. Artificial Intelligence Journal, 128(1-2): 99-141.
47.
Wall, R. et al. (2002). Creating a low cost autonomous vehicle . IEEE Internationnal Conference of the Industrial Electronics Society (IECON), Sevilla, Spain.
48.
Woo, E., MacDonald, B. and Trépanier, F. (2003). Distributed mobile robot application infrastructure . Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), Las Vegas, pp. 1475-1480.
