Localisation et suivi robustes d’un robot mobile grâce à l’analyse par intervalles
Robust robot localization and tracking using interval analysis
OPEN ACCESS
This paper presents a new solution to the problem of localizing and tracking a robot from distance measurements provided by on-board ultrasonic sensors. The measurement errors and state perturbations are assumed to be bounded. A parameter and state estimation technique based on interval analysis is employed to compute, as a function of time, a set guaranteed to contain all robot configurations (position and orientation) that are consistent with the measurements provided by the ultrasonic sensors, given bounds on the acceptable errors. The unavoidable presence of many outliers is taken into account to provide robust estimates. A realistic simulated example is treated in detail to illustrate the properties of the technique.
Résumé
Cet article présente une solution originale au problème de localisation et de suivi d’un robot mobile à partir de données télé- métriques fournies par des capteurs à ultrasons. Le problème est traité dans un contexte d’erreurs de mesure et d’incertitudes sur l’état bornées. Grâce à une technique d’estimation de paramètres et d’état utilisant l’analyse par intervalles, les mesures provenant des capteurs à ultrasons sont fusionnées en tenant compte de la présence inévitable de nombreuses données aberrantes. Un ensemble contenant la configuration (position et orientation) du robot est fourni à chaque instant. Un exemple simulé réaliste est présenté en détail pour illustrer les propriétés de la technique.
data fusion, interval computation, outliers, parameter estimation, robotics, robustness, state estimation, ultrasonic sensors
Mots clés
calcul par intervalles, capteurs à ultrasons, données aberrantes, estimation de paramètres, estimation d’état, fusion de données, robotique, robustesse
[Castellanos] J.A. Castellanos, J.M.M. Monteil, J. Neira, et J.D. Tardos. « The SMAP : A probabilistic framework for simultaneous localization and map building ». IEEE Trans. on Robotics and Automation, 15(5) : 948-952, 1999.
[Crowley] J. Crowley. « World modeling and position estimation for a mobile robot using ultrasonic ranging ». Dans Proc. IEEE Int. Conf. on Robotics and Automation, pages 674-680, Scottsdale, Arizona, 1989.
[Durieu-a] C. Durieu, M.J. Aldon, et D. Meizel. « La fusion de données multisensorielles pour la localisation en robotique mobile ». Traitement du Signal, 13(2) : 144-166, 1996.
[Durieu-b] C. Durieu, B. Polyak, et E. Walter. « Trace versus determinant in ellipsoidal outer bounding with application to state estimation ». Dans Proc. 13th IFAC World Congress, volume I, pages 43-48, San Francisco, 1996.
[Drumheller] M. Drumheller. « Mobile robot localization using sonar ». IEEE Trans. on Pattern Analysis and Machine Intelligence, 9(2) : 325-332, 1987.
[Grimson] W.E. Grimson et T. Lozano-Perez. « Localizing overlapping parts by searching the interpretation tree ». IEEE Trans. on Pattern Analysis and Machine Intelligence, 9(4) : 469-482, 1987.
[Hecht] E. Hecht. Optics. Addison-Wesley, Reading, second edition, 1987.
[Hammer] R. Hammer, M. Hocks, U. Kulisch, et D. Ratz. C++ Toolbox for Verified Computing. Springer Verlag, Berlin, 1995.
[Halbwachs] E. Halbwachs et D. Meizel. « Multiple hypothesis management for mobile vehicule localization ». Dans CD-ROM of the European Control Conference, Louvain, 1997.
[Hanebeck] U.D. Hanebeck et G. Schmidt. « Set theoretic localization of fast mobile robots using an angle measurement technique ». Dans Proc. IEEE Int. Conf. on Robotics and Automation, pages 1387-1394, Minneapolis, 1996.
[Jaulin-a] L. Jaulin et E. Walter. « Set inversion via interval analysis for nonlinear bounded-error estimation ». Automatica, 29(4) : 1053-1064, 1993.
[Jaulin-b] L. Jaulin et E. Walter. « Guaranteed nonlinear parameter estimation from bounded-error data via interval analysis ». Math. and Comput. in Simulation, 35 : 1923-1937, 1993.
[Jaulin-c] L. Jaulin, E. Walter, et O. Didrit. « Guaranteed robust nonlinear parameter bounding ». Dans Proc. CESA’96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation), pages 1156-1161, Lille, 1996.
[Kieffer-a] M. Kieffer. Estimation ensembliste par analyse par intervalles, application à la localisation d’un véhicule. Thèse de doctorat, Université ParisSud, Orsay, 1999.
[Kieffer-b] M. Kieffer, L. Jaulin, et E. Walter. « Guaranteed recursive nonlinear state estimation using interval analysis ». Dans Proc. 37th IEEE Conf. on Decision and Control, pages 3966-3971, Tampa, 1998.
[Kieffer-c] M. Kieffer, L. Jaulin, E. Walter, et D. Meizel. « Nonlinear identification based on unreliable priors and data, with application to robot localization ». Dans A. Garulli, A. Tesi, et A. Vicino, editeurs, Robustness in Identification and Control, pages 190-203, LNCIS 245, Londres, 1999. Springer.
[Kieffer-d] M. Kieffer, L. Jaulin, E. Walter, et D. Meizel. « Robust autonomous robot localization using interval analysis ». Reliable Computing 6(3) : 337-362, 2000.
[Leonard-a] J.J. Leonard et H.F. Durrant-Whyte. « Mobile robot localization by tracking geometric beacons ». IEEE Trans. on Robotics and Automation, 7(3) : 376-382, 1991.
[Leonard-b] J.J. Leonard et H.F. Durrant-Whyte. Directed Sonar Sensing for Mobile Robot Navigation. Kluwer Academic Publishers, Boston, 1992.
[Lévêque] O. Lévêque. Méthodes ensemblistes pour la localisation de véhicules. Thèse de doctorat, Université de Technologie, Compiègne, 1998.
[Lahanier] H. Lahanier, E. Walter, et R. Gomeni. « OMNE : a new robust membership-set estimator for the parameters of nonlinear models ». J. of Pharmacokinetics and Biopharmaceutics, 15 : 203-219, 1987.
[Maksarov] D. Maksarov et J.P. Norton. « State bounding with ellipsoidal set description of the uncertainty ». Int. J. of Control, 65(5) : 847-866, 1996.
[Milanese] M. Milanese, J. Norton, H. Piet-Lahanier, et E. Walter (éditeurs). Bounding Approaches to System Identification. Plenum Press, New York, 1996.
[Moore] R.E. Moore. « Practical aspects of interval computation ». Appl. Math, (13) : 52-92, 1968.
[Meizel] D. Meizel, A. Preciado-Ruiz, et E. Halbwachs. « Estimation of mobile robot localization: geometric approaches ». Dans M. Milanese, J. Norton, H. Piet-Lahanier, et E. Walter, editeurs, Bounding Approaches to System Identification, Plenum Press, New York, 1996, pages 463-489.
[Neira] J. Neira, J. Horn, J. D. Tardoz, et G. Schmidt. « Multisensor mobile robot localization ». Dans Proc. IEEE Int. Conf. on Robotics and Automation, pages 673-679, Mineapolis, 1996.
[Norton-a] J.P. Norton (Ed.). « Special issue on bounded-error estimation 1 ». Int. J. of Adaptive Control and Signal Processing, 8(1) : 1-118, 1994.
[Norton-b] J.P. Norton (Ed.). « Special issue on bounded-error estimation 2 ». Int. J. of Adaptive Control and Signal Processing, 9(1) : 1-132, 1995.
[Olson] C.F. Olson. « Probabilistic self-localization for mobile robots ». IEEE Trans. on Robotics and Automation, 16(1) : 55-66, 2000.
[Pronzato] L. Pronzato et E. Walter R. « Robustness to outliers of bounded-error estimators and consequences on experiment design ». Dans M. Milanese, J. Norton, H. Piet-Lahanier, et E. Walter, editeurs, Bounding Approaches to System Identification, Plenum Press, New York, 1996, pages 199-212.
[Walter-a] E. Walter (Ed.). « Special issue on parameter identification with error bounds ». Mathematics and Computers in Simulation, 32(5&6) : 447-607, 1990.
[Walter-b] E. Walter et L. Pronzato. Identification of Parametric Models from Experimental Data. Springer-Verlag, Londres, 1997.
[Walter-c] E. Walter et H. Piet-Lahanier. « Estimation of the parameter uncertainty resulting from bounded-error data ». Mathematical Biosciences, 92 :55-74, 1988.