seminaires talk jaulin

Lessons and seminars

1998

[1] 23 juin 1998, exposé au GDR Alp Analyse par intervalles ;
Titre : "application a la localisation d'un robot, L. Jaulin (LISA, Angers)".
Pour plus d'information, voir http://www.loria.fr/~ringeiss/reunion-23juin/node3.html

1999

[2] 7 janvier 1999, ENSAM (Paris)
Titre : "Analyse par intervalles - Application à l'estimation à erreurs bornées - Application à la localisation de robots"
Pour plus d'information, voir http://laii.univ-poitiers.fr/identification/crendus/cr070199.htm

[3] 14 octobre 1999, IRIN (Nantes).
Titre : "Analyse par intervalles pour le calcul ensembliste ; Application à la robotique".
Pour plus d'information, voir : http://www.sciences.univ-nantes.fr/irin/Vie/Semirin/1999/Jaulin.html

2000

[4] Decembre, 2000, EPFL (Lauzanne, Suisse) :
Titre : "2k trees and interval computation, application to set estimation". Pour plus d'information, voir
http://diwww.epfl.ch/w3di/depart/pub/publication/RAS2000-01.pdf

2001

[5] 7 juin 2001, CEMIF (Evry) :
Titre : "Propagation de contraintes sur les intervalles; application à l'estimation à erreurs bornées".
Pour plus d'information, voir http://lsc.cemif.univ-evry.fr:8080/News/liste.php3

[6] 4 avril 2001, IRCYN (Nantes)
Titre : Méthodes par intervalles : Principes et applications
Résumé : Le calcul par intervalles permet de résoudre proprement et efficacement une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues.
Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un
temps fini, même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème. Cependant, les méthodes par intervalles classiques deviennent inapplicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité exponentielle des problèmes traités. L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et autorise ainsi le traitement de problèmes plus grandes dimensions (supérieures à 50 par exemple). Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Quelques applications en automatique et en robotique seront données.

[7] Lesson. November 2001, "Interval analysis for identification, state estimation and robust control",
Lecturers: L. Jaulin (Univ. d'Angers), M. Kieffer (Univ. Paris Sud) and E. Walter (CNRS) Graduate School in Systems and Control, 2001 - 2002.
More information can be found at http://www.auto.ucl.ac.be/AUTO/graduate.html.

[8] 6 décembre 2001, LESIR (Cachan),
Titre : "Application des méthodes de propagation de contraintes à l'automatique".
Pour plus d'information, voir http://www-lag.ensieg.inpg.fr/gt-ensembliste/CR/cr20011206.htm

2002

[9] Lesson. May 6-10 2002, "Interval and constraint propagation methods for control", 10 hours.
Lecturers: L. Jaulin,
Departement d'Electrònica, Informàtica i Automàtica, Institut d'Informàtica i Aplicacions, Universitat de Girona.

[10] 8 novembre 2002, UTC, Eudiasyc (Compiègne), séminaire du thème SPC(http://www.hds.utc.fr/themes/SPCseminaires.html).
Télécharger les transparents
Titre : "Intervalles et propagation de contraintes, applications en automatique et en robotique".
Résumé : Le calcul par intervalles permet de résoudre proprement et efficacement une grande classe de problèmes non-linéaires, comme par exemple
le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues.
Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un
temps fini, même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème. Cependant, les méthodes par intervalles
classiques deviennent inapplicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité exponentielle des problèmes traités. L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et autorise ainsi le traitement de problèmes plus grandes dimensions (supérieures à 1000 par exemple). Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Quelques applications en automatique et en robotique seront
données.

[11] 20 Novembre 2002, Séminaire d'Automatique de Paris, Conservatoire National des Arts et Métiers (CNAM). Télécharger les transparents.
Titre : "Méthodes par intervalles : Principes et applications"
Résumé : Le calcul par intervalles permet de résoudre proprement et efficacement une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème. Cependant, les méthodes par intervalles classiques deviennent inapplicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité exponentielle des problèmes traités. L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et autorise ainsi le traitement de problèmes plus grandes dimensions (supérieures à 1000 par exemple). Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Quelques applications en automatique et en robotique seront données. Des outils logiciels de résolution gratuits, utilisant le calcul par intervalles, seront présentés. Ils seront alors utilisés pour la résolution
de problèmes de commande robuste et d'estimation d'état.

[12] Mardi 10 décembre 2002, Séminaire MATHINFO de l'E.S.I-E-A 16h30 - 18h30 (Amphi A, rue Vésale). Télécharger les transparents
Titre : "L'arithmétique des intervalles pour la résolution numérique (mais garantie) de systèmes d'équations non-linéaires"
Pour plus d'information, voir http://professeurs.esiea.fr/erra/ESIEA-MATHINFO.html

2003

[13] Mercredi 22 janvier 2003, 10h, Journées Nationales de Calcul Formel 2003 CIRM, Luminy, 20-24 janvier 2003.
Pour plus d'information voir http://www.loria.fr/~hanrot/jncf2003.html
Titre : Méthodes par intervalles, propagation de contraintes et calcul formel : principes et applications.
Les actes sont sur http://www.loria.fr/~hanrot/jncf.pdf
Télécharger les transparents.

[14] Mardi 28 janvier 2003, Séminaire du LAAS (Toulouse). Télécharger les transparents
Pour plus d'informations, voir http://www.laas.fr/MAC/MAC-EVENT.html
Titre : "Méthodes par intervalles pour la résolution globale et garantie de problèmes non convexes ; application à l'automatique et à la robotique"
Résumé : Le calcul par intervalles permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple
le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues.
Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un
temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème. Cependant, les méthodes par intervalles
classiques deviennent inapplicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité
exponentielle des problèmes traités. L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et
autorise ainsi le traitement de problèmes plus grandes dimensions (supérieures à 1000 par exemple). Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Quelques applications en automatique (commande robuste et estimation d'état) et en robotique (localisation et planification de chemins) seront données. Des logiciels de résolution gratuits, utilisant le calcul par intervalles, seront présentés.

[15] Lesson. 18 Mars 2003, "Calcul par intervalles et propagation de contraintes pour l'optimisation globale", 3 hours.
Lecturers: L. Jaulin (LISA, Univ. d'Angers) et Pascal Roustant (AC système),
Ecole des mines de Saint Etienne. Pour plus d'informations, voir http://www.emse.fr/~leriche/GTopti.html
Télécharger le cours

[16] Jeudi 26 juin 2003, JNA'03, 40 minutes, session plénière, Valenciennes. Télécharger les transparents
Pour plus d'information sur les JNA, voir http://www.univ-valenciennes.fr/LAMIH/JDA03/intro_jna.html
Titre : Calcul ensembliste pour l'automatique et ses applications en identification, diagnostic, et robotique.
Résumé : Lorsque les incertitudes de modélisation, les perturbations ou les bruits de mesure intervenant sur le système sont représentés par des ensembles (et non pas par des lois de probabilité), de nombreux problèmes d'automatique peuvent se ramener à la caractérisation d'un ensemble défini par des inégalités qui peuvent être non-linéaires. Les méthodes ensemblistes forment une panoplie d'outils capables de caractériser un tel ensemble, de lui trouver un point (éventuellement optimal) intérieur, de lui trouver sur-ensemble (pavé, ellipsoïde, zonotope), de montrer qu'il est ou qu'il n'est pas vide, ...
Le calcul par intervalles est un de ces outils. Il permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème. L'efficacité des méthodes par intervalles a été grandement améliorée grâce à l'utilisation de techniques de propagation de contraintes, récemment introduites en automatique. Le traitement de problèmes de plusieurs milliers de variables est désormais envisageable.
Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul ensembliste et des techniques de propagation de contraintes. Quelques applications en automatique (commande robuste et estimation de paramètres et d'état) et en robotique (localisation et planification de chemins) seront données. Des logiciels de résolution gratuits, utilisant le calcul par intervalles, seront présentés.

[17] Jeudi 3 juillet 2003, 9h30,10h30, Institut de Mathématiques Appliquées (IMA), Université Catholique d'Angers,
Titre : Calcul ensembliste pour l'automatique et ses applications en identification, diagnostic, et robotique. Télécharger les transparents

[18] Mercredi 19 novembre 2003, 14h00,16h00, LIRMM, Montpellier, le cadre des conférences pour les élèves de DEA. Télécharger les transparents
Titre : Calcul ensembliste pour l'automatique et ses applications en identification, commande et robotique.
Résumé : Lorsque les incertitudes de modélisation, les perturbations ou les bruits de mesure intervenant sur le système sont représentés par des ensembles (et non pas par des lois de probabilité), de nombreux problèmes d'automatique peuvent se ramener à la caractérisation d'un ensemble défini par des inégalités qui peuvent être non-linéaires. Les méthodes ensemblistes forment une panoplie d'outils capables de caractériser un tel ensemble, de lui trouver un point (éventuellement optimal) intérieur, de lui trouver sur-ensemble (pavé, ellipsoïde, zonotope), de montrer qu'il est ou qu'il n'est pas vide, ...
Le calcul par intervalles est un de ces outils. Il permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème. L'efficacité des méthodes par intervalles a été grandement améliorée grâce à l'utilisation de techniques de propagation de contraintes, récemment introduites en automatique. Le traitement de problèmes de plusieurs milliers de variables est désormais envisageable.
Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base du calcul ensembliste et des techniques de propagation de contraintes. Quelques applications en automatique (commande robuste et estimation de paramètres et d'état) et en robotique (localisation et planification de chemins) seront données. Des logiciels de résolution gratuits, utilisant le calcul par intervalles, seront présentés.

2004

[19] Lesson. 9-12 February 2004, "Interval contractors and their applications", 16 hours, L. Jaulin (Univ. d'Angers). Download the lesson
Universitat Politècnica de Catalunya, Rambla S Nebridi,10. 08222 Terrassa (Barcelona). Pour plus d'information sur le plan du cours : http://webesaii.upc.es/doct/tap/assig/seminari040209-13.htm

[20] Lesson. 26 février 2004, "Calcul par intervalles et propagation de contraintes pour l'optimisation globale", 3 hours.
Lecturers: L. Jaulin (LISA, Univ. d'Angers),
Ecole des mines de Saint Etienne. Pour plus d'informations, voir http://www.emse.fr/~leriche/GTopti.html
Télécharger le cours

[21] Mercredi 15 septembre 2004, 11h-11h45. Laboratoire E3I2, Brest. Télécharger les transparents
Titre : Calcul par intervalles pour la résolution garantie de problèmes non-linéaires.
Résumé : Le calcul par intervalles permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème. L'efficacité des méthodes par intervalles a été grandement améliorée grâce des techniques venues de l'informatique comme la propagation de contraintes, l'analyse syntaxique ou la différentiation automatique.
Le but de cet exposé est de donner les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Une application sur la localisation dynamique d'un robot à roues à partir de télémètres à ultrasons sera présentée.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

[22] Mardi 7 septembre 2004, Department of Computer Science, University of Texas, El Paso

Title : Interval analysis and constraint propagation; applications to control, estimation and robotics. Download slides

Abstract : Interval analysis makes it possible to solve a large class on nonlinear problems such as (i) computing all global minimizers of a nonconvex criterion, (ii) computing all solutions of a set of nonlinear equations, (iii) characterizing sets defined by nonlinear inequalities, ...
Unlike classical numerical approaches (Monte Carlo or local methods, for instance), the results provided by interval analysis are obtained in a guaranteed way and in a finite time, even when strong nonlinearities and discontinuities are involved in the problem.

Unfortunately, classical interval methods have some difficulties to deal with problems involving a large number of variables (greater than 10, for instance). This limitation is mainly due to the bisections involved in the interval algorithms that makes the complexity exponential with respect to the number of variables.

Contraint propagation techniques make it possible to push back this frontier and to deal with high dimentional problems (with more than 1000 variables for instance). Even so, these techniques are no widely known in the interval community.

The purpose of this seminar is to introduce in a pedagogical way the principles of interval methods and constraint propagation techniques.

Some applications to robust control, state estimation, robot calibration, path planning, ... will be given. Moreover, some free windows solvers (Proj2d, Interval peeler, CIA) combining interval analysis and constraint propagation and developed by our interval team in Angers and Brest, will be presented.

[23] Mardi 14 décembre 2004, 14h , Séminaire au laboratoire de mathématiques de l'université de Bretagne occidentale, unite CNRS UMR6205

Télécharger les transparents

Titre : "L'arithmétique des intervalles pour l'étude de propriétés topologiques d'un ensemble défini par des inégalités"

Résumé: L'arithmétique des intervalles est un outil numérique permettant la résolution propre et efficace d'une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système d'équations non-linéaires. Contrairement aux méthodes numériques classiques (méthodes de Newton ou de MontéCarlo, par exemple), la solution est caractérisée avec une précision arbitraire, de façon globale et en un temps fini. Ceci s'applique même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème.

Le but de cet exposé est de présenter de façon brève et pédagogique les principes de base de l'arithmétique par intervalles. Ensuite, nous montrerons qu'en combinant les techniques de calcul par intervalles avec la théorie des graphes, il est possible d'étudier quelques propriétés topologiques (comme par exemple compter le nombre de composantes connexes ou calculer le type d'homotopie) d'ensembles définis par des inégalités.

À titre d'illustration, quelques exemples académiques issus de l'automatique et la robotique seront traités. Des logiciels de résolution que nous avons développés seront présentés. Ces logiciels sont disponibles gratuitement et utilisent les méthodes présentées dans l'exposé.

2005

[24] Vendredi 26 septembre 2005, Int 05 workshop in Copenhagen, Denmark, Download slides

Title : " Nonlinear control using interval constraint propagation"

Abstract : Interval methods combined with constraints propagation techniques have been shown to be very efficient to deal in a reliable way with control problems when the system to be considered is described by linear differential equations. The main idea is to transform the linear differential equation problem into a set of nonlinear inequalities by using the notions of characteristic polynomial and Routh criterion and then to use classical interval algorithms. Now, most systems that can be encountered in practice can only be described properly by nonlinear differential equations and the notion of characteristic polynomial does not exist anymore. For such nonlinear systems, interval methods have rarely been used to solve any realistic control problems. The aim of this talk is to present two recent realistic applications related to nonlinear control where interval constraint propagation methods have been successful. The first application results from a collaboration with M. Dao, M. Lhommeau, P. Herrero, J. Vehi and M. Sainz. The problem to be considered is to control a sailboat in order to go in the right direction, to the right speed, or to go as fast as possible. The second application is the control of a wheeled stair-climbing robot that we are building with some colleagues from the ENSIETA engineering school in Brest. Masses supported by the robot have to be moved in order to avoid any sliding of the wheels. For such control problems where strong nonlinearities occur, conventional control methods fail to provide any reliable controller whereas constraints satisfaction techniques seem to be adapted.

[25] Lesson. 12-16 septembre 2005, « Set computation and its applications to identification, observation, control and robotics », Control summer school of Grenoble. Télécharger le dépliant.

Download the lesson.

[26] Mercredi 8 novembre 2005, Nice-Sophia Antipolis, I3S, Download slides

Title : " Nonlinear control of robots using interval constraint propagation"

Abstract : Interval methods combined with constraints propagation techniques have been shown to be very efficient to deal in a reliable way with control problems when the system to be considered is described by linear differential equations. The main idea is to transform the linear differential equation problem into constraint satisfaction problems (CSP) over continuous domains by using the notions of characteristic polynomial and Routh criterion. Now, most systems that can be encountered in robotics can only be described properly by nonlinear differential equations and the notion of characteristic polynomial does not exist anymore. For such nonlinear systems, interval methods have rarely been used to solve any realistic control problems. The aim of this talk is to present two recent applications related to nonlinear control of robots where interval constraint propagation methods have been successful. The first application results from a collaboration with M. Dao, M. Lhommeau, P. Herrero, J. Vehi and M. Sainz. The problem to be considered is to control a sailboat in order to go in the right direction, to the right speed, or to go as fast as possible. The second application is the control of a wheeled stair-climbing robot that we are building with some colleagues from the ENSIETA engineering school in Brest. Masses supported by the robot have to be moved in order to avoid any sliding of the wheels. For such control problems where strong nonlinearities occur, conventional control methods fail to provide any reliable controller whereas constraints satisfaction techniques seem to be adapted.

[27] Workshop franco-japonais sur la programmation par contraintes du 14 au 16 novembre 2005. Download slides
Title : " Nonlinear control using interval constraint propagation"
Abstract : Interval methods combined with constraints propagation techniques have been shown to be very efficient to deal in a reliable way with control problems when the system to be considered is described by linear differential equations. The main idea is to transform the linear differential equation problem into a set of nonlinear inequalities by using the notions of characteristic polynomial and Routh criterion and then to use classical interval algorithms. Now, most systems that can be encountered in practice can only be described properly by nonlinear differential equations and the notion of characteristic polynomial does not exist anymore. For such nonlinear systems, interval methods have rarely been used to solve any realistic control problems. The aim of this talk is to present three recent realistic applications related to nonlinear control where interval constraint propagation methods have been successful. The first application results from a collaboration with M. Dao, M. Lhommeau, P. Herrero, J. Vehi and M. Sainz. The problem to be considered is to control a sailboat in order to go in the right direction, to the right speed, or to go as fast as possible. The second application is the control of a wheeled stair-climbing robot that we are building with some colleagues from the ENSIETA engineering school in Brest. Masses supported by the robot have to be moved in order to avoid any sliding of the wheels. The last application is related to a collaboration with the GESMA (Groupe d'Etude Sous Marine Atlantique). The application concerns the control and the localization of an AUV (Autonomous Underwater Vehicle). The sensors that are available are a camera to be used in deep water, a GPS at the surface of the ocean and an accelerometer that can always be used.

For such control problems where strong nonlinearities occur, conventional control methods fail to provide any reliable controller whereas constraints satisfaction techniques seem to be adapted.

2006

[28] Jeudi 18 mai 2006, Journées calcul ensembliste (ENSAM),

Authors : Luc Jaulin, Alain Betholom, Frédéric Dabe
Titre : Interval constraint propagation for the SLAM (Simultaneous Localization And Mapping) of a submarine robot.

Download slides

[29] Jeudi 8 juin 2006, Concours de robotique microtransat (ENSICA),

For more information, see http://www.ensica.fr/microtransat

Author : Luc Jaulin
Title : Control of a sailboat and robotics in ENSIETA

Download slides

[30] Mardi 5 Décembre 2006, Vienne.

GICOLAG Workshop (Global optimization - Integrating Convexity, Optimization, Logic and Algebraic Geometry).

Title : Interval constraints propagation techniques for the simultaneous localization and map building of an actual underwater robot.

Download slides.

Abstract. The SLAM (Simultaneous localization and map building) problem asks if it is possible for an autonomous robot to move in an unknown environment and build a map of this environment while simultaneously using this map to compute its location.

During the talk, I will show that a general SLAM problem can be cast into a huge constraint propagation problem (CSP) where the variables are vectors/matrices and where domains are interval vectors/interval matrices. The corresponding CSP is nonlinear and classical nonlinear methods have some difficulties to deal with this type of problems in a reliable way.

Then, I will propose to use a basic interval constraint propagation algorithm, adapted to vector/matrix constraints, to solve the CSP.

The efficiency of the approach will be illustrated on a two-hour experiment where an actual underwater robot is involved. This four-meter long robot build by the GESMA (Groupe d'étude sous-marine de l'Atlantique) is equipped with many sensors (such as sonars, Loch-Doppler, gyrometers, ...) which provide the data.

The corresponding algorithm will be able to provide an accurate envelope for the trajectory of the robot and to compute sets which contain some detected mines in less than one minute.

[31] Lundi 18 décembre 2006, 14h, Orléans, LIFO

Titre : Arithmétique par intervalles et applications en robotique. Slides.

Résumé : L'arithmétique des intervalles est un outil numérique permettant la résolution propre et efficace d'une grande classe de problèmes non-linéaires sur les domaines continus, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système d'équations non-linéaires. Contrairement aux méthodes numériques classiques (méthodes de Newton ou de MontéCarlo, par exemple), la solution est caractérisée avec une précision arbitraire, de façon globale et en un temps fini. Ceci s'applique même lorsque des fonctions trigonométriques ou non-continues apparaissent dans notre problème. Cependant, les méthodes par intervalles classiques deviennent difficilement applicables lorsque le nombre de variables devient élevé, (supérieur à 10 par exemple), principalement à cause de la complexité exponentielle des problèmes traités.

L'utilisation de techniques de propagation de contraintes permet de repousser largement cette barrière et autorise ainsi le traitement de problèmes de plus grandes dimensions (supérieures à 1000 par exemple).

Dans cet exposé je présenterai, tout d'abord, de façon brève et pédagogique les principes de base de l'arithmétique des intervalles et des techniques de propagation de contraintes sur les domaines continus.

Ensuite, quelques applications du calcul par intervalles en robotique seront montrées, comme par exemple

1) la planification de chemin pour un robot mobile,

2) l'étude de la topologie d'un espace de configuration d'un robot,

3) et la localisation d'un sous-marin démineur.

[32] December 21, 2006, 11h, University of Girona.

Title : Interval constraint propagation techniques for the simultaneous localization and map building of an actual underwater robot. Slides.

During the talk, I will show that a general SLAM problem can be cast into a constraint propagation problem (CSP). The corresponding CSP is nonlinear and classical nonlinear methods have some difficulties to deal with this type of problems in a reliable way.

After a brief presentation of interval analysis, I will propose to use a basic interval constraint propagation algorithm, to solve the CSP.

The corresponding algorithm will be able to provide an accurate envelope for the trajectory of the robot and to compute sets which contain some detected mines in less than one minute.

2007

[33] Vendredi 19 janvier 2007, Sophia-Antipolis, I3S, Coprin.

Titre : Nouveau test intérieur pour un ensemble défini par des égalités existentiellement quantifiées ; application à commande de robots. Slides.

Résumé. Dans cet exposé, je m'intéresserai à la caractérisation de sous-ensembles de Rn définis comme des projections de contraintes égalités. Nous allons nous placer dans la situation (qui se produit fréquemment) où l'ensemble à caractériser admet un intérieur et un extérieur. De nombreuses méthodes efficaces (utilisant par exemple la propagation de contraintes sur les intervalles) permettent d'obtenir une caractérisation extérieure de notre ensemble. En revanche, sauf dans des cas bien particuliers, la caractérisation intérieure est beaucoup plus difficile. Le but de cet exposé est de proposer un nouveau intérieur (issu d'une collaboration avec A. Goldsztejn) qui nous permettra d'obtenir une caractérisation intérieure de notre ensemble, et ceci même lorsque les variables existentielles sont partagées entre les égalités. Les notions et les résultats seront illustrés à travers des exemples issus de la robotique (voilier et robot escaladeur).

[34] February 12, 2007, AUV'06, Brest.

Titre : Localization of an AUV using interval analysis. Slides.

[35] March 7, 2007, Heriot-Watt University

Title : Interval constraint propagation techniques for the simultaneous localization and map building of an actual underwater robot. Slides.

After a brief presentation of interval analysis, I will propose to use a basic interval constraint propagation algorithm, to solve the CSP.

The corresponding algorithm will be able to provide an accurate envelope for the trajectory of the robot and to compute sets which contain some detected mines in less than one minute.

[36] Mardi 23 avril 2007, ENSIETA, Brest (Journée sur les nouvelles technologies de la sécurité en mer).

Titre : Anticollision : difficultés et méthodes. Slides.

[37] Lundi 14 mai 2007, LIP, Lyon.

Titre : Calcul par intervalles, applications en robotique. Slides.

[38] Lesson. 15 mai 2007, "Calcul par intervalles et applications", 2h30. Au master recherche de l'ENS Lyon.
Lecturer: L. Jaulin. Download slides.

[39] Jeudi 14 juin 2007, GESMA, Brest,

Workshop sur la navigation sur amers en milieu sous-marin

Titre : Evaluation de performance en navigation. Slides.

[40] Jeudi 19 juillet 2007, Paris, GT calcul ensembliste du GDR Macs.

Title : Interval controllers. Slides.

Abstract : An interval controller is a controller that uses interval computation to control a plant. In control theory, interval analysis is often used for offline nonlinear state/parameter estimation and for the conception of controllers for linear/ nonlinear systems. But interval computation is rarely used by the controller itself : I don't know any actual system which is controlled by an interval controller; I don't know any actual robot which uses interval arithmetic during its mission.

The aim of this talk is to provide some examples where using intervals inside the controller could make the controller more reliable, more robust with respect to outliers, ... than it could be without intervals.

As an illustration, the control of an underwater robot inside a swimming pool will be considered. The robot localizes itself with a sonar and has to execute a mission inside the pool. This robot has been built at ENSIETA School for the SAUC'E competition (Studient Autonomous Underwater Challenge European) that will take place in England July 14^th 2007.

[41] Lundi 30 juillet 2007, Girona.

Title : SAUC'ISSE: our interval underwater robot. Slides.

[42] Lundi 1er octobre 2007, Lyon, GT calcul ensembliste du GDR Macs.

Title : Calcul par intervalles, propagation de contraintes et applications. Slides.

[43] Jeudi 22 novembre 2007, Paris

Title: Resolution of nonlinear interval problems using symbolic interval arithmetic, Slides.

Abstract: An interval-valued problem is a problem where the unknown variables take interval values. Such a problem can be defined by interval constraints, such as "the interval X=[a,b] is a subset of X*X". Interval valued problems often appear when we want to analyze a priori the behavior of an interval solver. To solve interval-valued problems, we propose to transform the constraints on intervals into constraints on their bounds. For instance, the previous interval constraint (X is a subset of X*X) can be transformed into the following bound constraint "a>min(a*a,a*b,b*b) and b<max(a*a,a*b,b*b)". Classical interval solvers can then be used to solve the resulting bound constraints. The procedure which transforms interval constraints into equivalent bound constraints can be facilitated by using symbolic interval arithmetic. While classical intervals can be defined as a pair of two real numbers, symbolic intervals can be defined as a pair of two symbolic expressions. An arithmetic similar to classical interval arithmetic can be defined for symbolic intervals. The approach will be motivated by several examples related to estimation and experimental design.

[44] mercredi 19 décembre 2007, GESMA, Brest

Titre : SLAM en robotique sous-marine. Slides.

2008

[45] Jeudi 13 mars 2008

Title : Contractors and QUIMPER language. Slides

Abstract: QUIMPER is a new programming language devoted to set computation. It makes possible to implement a large class of interval-based algorithms in a very easy way. This language has been implemented in C++ using the IBEX interval library. After introducing briefly some fundamental notions related to contractors the QUIMPER language will be presented. Some examples taken from the control and estimation literature will then be treated with QUIMPER.

[46] 27 mai 2008, LEST, Brest

Titre : Calcul par intervalles pour la résolution garantie de problèmes non-linéaires. Slides.
Résumé : Le calcul par intervalles permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème.

Le but de cet exposé est de donner les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Des applications en robotique, estimation, et localisation seront présentées.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

[47] Lesson. Vendredi 14 juin 2008, 13h30-17h. "Calcul par intervalles et applications". Cours de master recherche UBO (Brest)

[48] 4 juin 2008, demi-journée industrielle, JFPC, Nantes

Titre : Programmation par contraintes pour la localisation d'un robot sous-marin. Slides.

Résumé : La programmation par contraintes est de plus en plus utilisée en robotique pour deux raisons principales. La première raison est que de nombreux problèmes issus de la robotique se formulent naturellement en termes de contraintes faisant généralement intervenir des variables discrètes et continues. La deuxième raison est que les systèmes de contraintes impliqués se résolvent avec une très grande efficacité avec des méthodes de propagation de contraintes.

Le but de cet exposé est de présenter de façon pédagogique quelques exemples issus de robotique où la programmation par contrainte a son intérêt. En particulier nous montrerons un robot sous-marin autonome qui utilise en temps réels une méthode de propagation de contraintes sur les intervalles pour se localiser, et ceci alors que de très nombreuses données aberrantes perturbent fortement le système de contraintes courant.

[49] SWIM 08, Montpellier

Title: Resolution of nonlinear interval problems using symbolic interval arithmetic. Slides.

Abstract: An interval-valued problem is a problem where the unknown variables take interval values. Such a problem can be defined by interval constraints, such as "the interval X=[a,b] is a subset of X*X". Interval valued problems often appear when we want to analyze a priori the behaviour of an interval solver. To solve interval-valued problems, we propose to transform the constraints on intervals into constraints on their bounds. For instance, the previous interval constraint (X is a subset of X*X) can be transformed into the following bound constraint "a>min(a*a,a*b,b*b) and b<max(a*a,a*b,b*b)". Classical interval solvers can then be used to solve the resulting bound constraints. The procedure which transforms interval constraints into equivalent bound constraints can be facilitated by using symbolic interval arithmetic. While classical intervals can be defined as a pair of two real numbers, symbolic intervals can be defined as a pair of two symbolic expressions. An arithmetic similar to classical interval arithmetic can be defined for symbolic intervals. The approach will be motivated by several examples related to estimation and experimental design.

[50] SWIM 08, Montpellier. Slides.

Title: Interval and Boolean constraint propagation for simultaneous localization and map building.

During the talk, it will be shown that, when the landmarks are identical and when outliers occur, the general SLAM problem can be cast into a constraint propagation problem (CSP) where Boolean and numerical variables occur. The corresponding CSP is nonlinear and classical nonlinear methods have some difficulties to deal with this type of problems in a reliable way.

A basic interval constraint propagation algorithm to solve the CSP will be proposed.

[51] Cours. Vendredi 21 novembre 2008, 14h, Amphi A 301 à l'ENSPS, Strasbourg.

Titre : Calcul par intervalles pour la résolution garantie de problèmes non-linéaires. pdf.

Résumé : Le calcul par intervalles permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

[52] 22 octobre 2008, workshop du PEA action, LAAS, Toulouse. pdf.

Titre : Méthodes ensemblistes pour la localisation et la cartographie dans un contexte de robotique sous-marine.

Résumé : Un robot sous-marin est généralement muni d'un écho-sondeur pour mesurer sa distance au fond, d'un capteur de pression pour mesurer sa profondeur, d'un loch-doppler pour mesurer sa vitesse, d'une centrale inertielle pour mesurer son orientation et d'un GPS pour se localiser lorsqu'il se trouve à la surface. Pourtant, malgré tous ces capteurs, une dérive apparaît lorsque le robot reste trop longtemps sous l'eau et le robot finit par se perdre. Une approche permettant des recalages en cours de mission consiste à observer attentivement son environnement et de chercher à se localiser tout en reconstituant une carte de la zone parcourue. C'est l'approche SLAM (Simultaneaous Localization And Mapping) qui a déjà montré ses potentialités dans le domaine de la robotique terrestre et aérienne. A l'heure actuelle, on peut dire que les méthodes fondées sur le filtre de Kalman étendu fonctionnent correctement si les conditions suivantes sont satisfaites : (i) le modèle d'évolution du robot est quasi-linéaire, (ii) les amers détectés ont une nature ponctuelle, (iii) à chaque détection, le robot est capable de localiser les amers détectés dans son propre repère, (iv) le robot est capable de distinguer les amers les uns des autres sans se tromper, (v) le robot rencontre plusieurs fois un nombre suffisamment important d'amers. Lorsque le modèle d'évolution du robot est non-linéaire des méthodes plus récentes comme le filtrage particulaire ou les méthodes ensemblistes parviennent à résoudre le problème du SLAM de façon satisfaisante. Cependant en milieu sous-marin, les hypothèses qui rendent les approches de type Kalman adaptées sont rarement respectées. (i) Les équations d'état d'un robot sous-marin sont souvent fortement non linéaires, (ii) les amers ont rarement une nature ponctuelle (les câbles sous-marins, les rides de sable, les zones rocheuses,... sont considérés comme des amers) (iii) on est rarement capables de positionner l'amer détecté dans le repère du robot, (iv) les amers ne sont pas facilement distinguables les uns des autres, (v) le nombre d'amers fiables est faible et cela se traduit en pratique par des erreurs d'appariement entre les amers, (vi) il existe de nombreuses données aberrantes, qu'on ne peut détecter que de façon dynamique (les informations qui nous permettront de montrer qu'une donnée est aberrante se trouvent souvent dans un futur plus ou moins proche). Les approches ensemblistes utilisent principalement le calcul par intervalles et les méthodes de propagation de contraintes. Elles peuvent résoudre avec efficacité des problèmes impliquant un grand nombre d'équations ou inéquations non-linéaires où interviennent des contraintes discrètes (c'est-à-dire, faisant intervenir des variables booléennes ou entières). Le but de cet exposé est de donner les principes de base du calcul par intervalles et des techniques de propagation de contraintes. Dans le contexte du SLAM, nous montrerons comment elles permettent par exemple la mise en correspondance automatique des amers détectés, la détection dynamique des données aberrantes et la prise en compte des non-linéarités. Des illustrations de l'approche sur des robots réels seront présentées. Enfin, dans un contexte où plusieurs robots, qui communiquent entre eux, sont impliqués dans la mission, nous donnerons des pistes pour montrer comment distribuer les calculs entre les robots et représenter l'information afin que le système complet (constitué de tous les robots) puisse résoudre le problème du SLAM de façon collective.

[53] Lundi 27 octobre 2008, Belo Horizonte, Brésil. pdf.

Title: Interval analysis and constraint propagation; applications to control, estimation and robotics.
Abstract: Interval analysis makes it possible to solve a large class on nonlinear problems such as (i) computing all global minimisers of a nonconvex criterion, (ii) computing all solutions of a set of nonlinear equations, (iii) characterizing sets defined by nonlinear inequalities, ...
Unlike classical numerical approaches (Monte Carlo or local methods, for instance), the results provided by interval analysis are obtained in a guaranteed way and in a finite time, even when strong nonlinearities and discontinuities are involved in the problem.
Unfortunately, classical interval methods have some difficulties to deal with problems involving a large number of variables (greater than 10, for instance). This limitation is mainly due to the bisections involved in the interval algorithms that make the complexity exponential with respect to the number of variables.
Constraint propagation techniques make it possible to push back this frontier and to deal with high dimensional problems (with more than 1000 variables for instance). Even so, these techniques are no widely known in the interval community.
The purpose of this seminar is to introduce in a pedagogical way the principles of interval methods and constraint propagation techniques.
Some applications to robust control, state estimation, robot calibration, path planning ... will be given. Moreover, some free windows solvers (Proj2d, Interval peeler, CIA) combining interval analysis and constraint propagation and developed by our interval team in Angers and Brest, will be presented.

[54] Jeudi 13 novembre 2008 de 10h-17h, à l'ENSAM Paris, journée MEA. pdf.

Title: Image Shape Extraction using Interval Methods.

Abstract: This talk proposes a new method for recognition of geometrical shapes (such as lines, circles or ellipsoids) in an image. The main idea is to transform the problem into a bounded error estimation problem and then to use an interval-based method which is robust with respect to outliers. The approach is illustrated on images taken by an underwater robot where geometrical objects (such as spherical buoy or cylinders) have to be detected. The results will then be compared to those obtained by the more classical generalized Hough transform.

[55] Jeudi 20 novembre 2008. Journées de Rencontre «Mathématiques, Entreprises et Innovations » UHA- Mulhouse.

Titre : Calcul par intervalles : état de l'art et applications industrielles. pdf.
Résumé : Le calcul par intervalles permet de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système de n équations à n inconnues. Contrairement aux méthodes numériques classiques (méthodes de MontéCarlo, par exemple), le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

Télécharger l'article associé.

2009

[56] Lesson. Jeudi et vendredi 19-20 mars 2009, Ecole des JD MACS, Angers (4H).

Titre : Calcul par intervalles et contracteurs

Télécharger le polycopié.

Slides.

Pour plus d'infos.

[57] Mardi 7 avril 2009. Journée Intelligence Artificielle Embarquée , Cergy-Pontoise, 10h45.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

[58] Mercredi 29 avril 2009, ENSIETA.

Titre. Présentation des activités de robotique à DTN, ENSIETA. Slides.

[59] DyToComp 2009, 1-7 juin 2009, Poznan, Pologne.

Title. Interval methods with applications to robotics. Slides.

Abstract. Interval analysis makes it possible to solve a large class on nonlinear problems such as (i) computing all global minimisers of a nonconvex criterion, (ii) computing all solutions of a set of nonlinear equations, (iii) characterizing sets defined by nonlinear inequalities, ...

Combined with constraint propagation techniques, interval methods make possible to deal efficiently with high dimensional problems (with more than 1000 variables for instance).
The purpose of this presentation is to introduce in a pedagogical way the principles of interval constraint propagation techniques.

Some applications to robotics (such as path-planning, dynamic localization, viability analysis) will be given.

[60] 11-12 juin 2009. SWIM'09.

Title: Probabilistic set-membership estimation. pdf.

Abstract: Interval constraint propagation methods have been shown to be efficient and reliable to solve difficult nonlinear bounded error estimation problems. However they are considered as unsuitable in a probabilistic context, where the approximation of a probability density function by a set cannot be accepted as reliable. This talk shows how probabilistic estimation problems can be transformed into a set estimation problem by assuming that some rare events will never happen. Since the probability of occurrence of those rare events can be computed, we can give some prior lower bounds for the probability associated to solution set of the corresponding set estimation problem. The approach will be illustrated on a parameter estimation problem and on the dynamic localization of an underwater robot.

[61] 25 juin 2009, DGA - Journée Technique ERA 2009, Paris.

Titre : Méthodes ensemblistes pour la localisation et la cartographie robuste dans un contexte de robotique sous-marine. pdf.

[62] Munich, 9-15 september 2009. Second Workshop on Principles and Methods of Statistical Inference with Interval Probability, WPMSIIP'09, Tuesday 15, 10h. pdf.

Title: Probabilistic set-membership estimation.

[63] Bagneux, 8 octobre 2009

Titre : Réalisation d'un robot sous-marin autonome pdf

[64] LIRMM, 20 octobre 2009

Title. Some applications of interval analysis to sea robotics. pdf.

Abstract. In this talk, I will present some applications of interval analysis to sea robotics.

1) The first application is the Simultaneous Localization and Mapping (SLAM) of an underwater robot which has to move inside the ocean. The four-meter long robot, build by the GESMA (Groupe d'étude sous-marine de l'Atlantique) is equipped with many sensors (such as sonars, Loch-Doppler, gyrometers, ...) which provide the data. The approach will be illustrated on a two-hour experiment made in the Douarnenez bay.

2) The second application is the localization of an underwater robot inside a swimming pool using mechanical sonar. The main difficulty of the localization is due the large number of outliers generated by the sonar during the mission. A robust interval observer will be presented and its efficiency will be illustrated on a localization of the robot SAUC'ISSE during the SAUCE competition. A presentation movie can be found at http://www.youtube.com/watch?v=LWsRCn1vuBk

3) The last application is a wind observer that we want to implement on our actual sailboat robot (photos and videos of our robot can be found at www.ensta-bretagne.fr/jaulin/mt.html) in order avoid using anemometers which cannot be considered as reliable.

[65] ITT'09, ENSTA, Paris 27 octobre 2009

Title. Analyse par intervalles pour la robotique mobile. pdf.

[66] UTC, 19 novembre 2009

Title. Some applications of interval analysis to sea robotics. pdf.

Abstract. In this talk, I will present some applications of interval analysis to sea robotics.

[67] Journée ensembliste MEA. Jeudi 3 décembre 2009.

Luc Jaulin, Jan Sliwka, Fabrice Le Bars, Kai Xiao.

Title. New approach for interval state estimation. Estimation to sailboat robotics. pdf.

Abstract : This talk deals with the state estimation of sailboat robot. This problem is motivated by the microtransat challenge where small autonomous sailboat robots are designed to cross the Atlantic ocean. All components of such robots should be robust with respect to all situations (heavy weather, waves, salt water, low level of energy, long trip, ...). Two types of sensors can be considered.

(i) Reliable sensors, which could survive to all situations. Such sensors are the GPS, the compass, the gyrometers and accelerometers. All these sensors are low energy consumers, can be enclosed inside a waterproof tank and can survive for years. The GPS gives us the position of the boat and new generation GPS can also return the speed with a good accuracy by using the Doppler effect. Since the magnetic perturbation inside the ocean can be neglected, the compass measures the north direction with a rather good accuracy. The gyrometer returns the rotational speed and the accelerometers make possible to get the roll and pitch of the robot.

(ii) Unreliable sensors, which have a high probability to brake down in case of heavy weather. Anemometers (device that is used for measuring wind speed), weather vane (which returns the direction of the wind), dynamometers which measures the forces on the sail or the rudder are considered as unreliable. They are directly in contact with aggressive natural elements (wind, wave, salt) and can fail down at any time.

On the one hand, to control the robot, it is necessary to know where the wind comes from, what is its power, how strong are the forces on the sail or on the rudder, if the mainsheet is tight or not, .... On the other hand, a reliable boat can only enclose reliable sensors. This talk provides a new method which combines classical nonlinear observation technique, based on flatness concepts, with interval analysis. The first tool makes possible to transform the observation problem into equations that have to be solved at each time. Interval analysis gives a systematic way to solve the inversion problem and makes possible to take into account some interval uncertainties on the measurement data.

A youtube video of our sailboat robot can be found at http://www.youtube.com/watch?v=jOjxRPnwQ9g

[68] Méthodes ensemblistes pour la robotique. Présentation DTN à l'ENSIETA. Slides.

2010

[69] Caen, March 11, 2010. Slides.

Title: Nonlinear interval observers

Abstract: In this talk, I will consider the state estimation of sailboat robot. This problem is motivated by the Microtransat challenge where small autonomous sailboat robots are designed to cross the Atlantic ocean. All components of such robots should be robust with respect to all situations (heavy weather, waves, salt water, low level of energy, long trip, ...). Two types of sensors can be considered.

1) Reliable sensors, which could survive to all situations. Such sensors are the GPS, the compass, the gyrometers and accelerometers. All these sensors are low energy consumers, can be enclosed inside a waterproof tank and can survive for years. The GPS gives us the position of the boat and new generation GPS can also return the speed with a good accuracy by using the Doppler effect. Since the magnetic perturbation inside the ocean can be neglected, the compass measures the north direction with a rather good accuracy. The gyrometer returns the rotational speed and the accelerometers make possible to get the roll and pitch of the robot.

2) Unreliable sensors, which have a high probability to brake down in case of heavy weather. Anemometers (device that is used for measuring wind speed), weather vane (which returns the direction of the wind), dynamometers which measures the forces on the sail or the rudder are considered as unreliable. They are directly in contact with aggressive natural elements (wind, wave, salt) and can fail down at any time.

The aim of the talk is twofold. The first goal is to show that the variables that could be measured by the unreliable sensors could be reconstructed dynamically from the data collected by the reliable sensors. This is new in a sailboat context. The second goal is to give a new method which combines classical nonlinear observation techniques, based on flatness concepts, with interval analysis. The first tool makes possible to transform the observation problem into equations that have to be solved at each time whereas interval analysis provides a systematic way to solve the inversion problem and makes possible to take into account some interval uncertainties on the measurement data.

Some photos and videos can be found at www.ensta-bretagne.fr/jaulin/mt.html

[70] Mexico March 17, 15h30. slides.

Title: Interval analysis and constraint propagation; applications to control, estimation and robotics.

Abstract : Interval analysis makes it possible to solve a large class on nonlinear problems such as (i) computing all global minimisers of a nonconvex criterion, (ii) computing all solutions of a set of nonlinear equations, (iii) characterizing sets defined by nonlinear inequalities, ...

Unlike classical numerical approaches (Monte Carlo or local methods, for instance), the results provided by interval analysis are obtained in a guaranteed way and in a finite time, even when strong nonlinearities and discontinuities are involved in the problem. Unfortunately, classical interval methods have some difficulties to deal with problems involving a large number of variables (greater than 10, for instance). This limitation is mainly due to the bisections involved in the interval algorithms that make the complexity exponential with respect to the number of variables. Constraint propagation techniques make it possible to push back this frontier and to deal with high dimensional problems (with more than 1000 variables for instance). Even so, these techniques are no widely known in the interval community. The purpose of this seminar is to introduce in a pedagogical way the principles of interval methods and constraint propagation techniques. Some applications to robust control, state estimation, robot calibration, path planning ... will be given. Moreover, some free windows solvers (Proj2d, Interval peeler, CIA) combining interval analysis and constraint propagation and developed by our interval team in Angers and Brest, will be presented.

[71] Mexico March 19, 15h30.

Title: Nonlinear interval observers. slides.

1) Reliable sensors, which could survive to all situations. Such sensors are the GPS, the compass, the gyrometers and accelerometers. All these sensors

are low energy consumers, can be enclosed inside a waterproof tank and can survive for years. The GPS gives us the position of the boat and new generation GPS can also return the speed with a good accuracy by using the Doppler effect. Since the magnetic perturbation inside the ocean can be neglected, the compass measures the north direction with a rather good accuracy. The gyrometer returns the rotational speed and the accelerometers make possible to get the roll and pitch of the robot.

1) Unreliable sensors, which have a high probability to brake down in case of heavy weather. Anemometers (device that is used for measuring wind speed), weather vane (which returns the direction of the wind), dynamometers which measures the forces on the sail or the rudder are considered as unreliable.

They are directly in contact with aggressive natural elements (wind, wave, salt) and can fail down at any time. On the one hand, to control the robot, it is necessary to know where the wind comes from, what is its power, how strong are the forces on the sail or on the rudder, if the mainsheet is tight or not, ... On the other hand, a reliable boat can only enclose reliable sensors.

Some photos and videos can be found at www.ensta-bretagne.fr/jaulin/mt.html

[72] Angers, May 11, 2010 Slides

Title: Image Shape Extraction using Interval Methods.

[73] Brest. Thales, June 7, 2010.

Title: Multilatération using interval analysis. Slides.

Oliver Reynet and Luc Jaulin

http://www.ensta-bretagne.fr/jaulin/paper_reynet_radar09.pdf

Multilateration is commonly used in civil and military surveillance applications to accurately locate targets (such as aircraft or any stationary emitter) by measuring the time difference of arrival (TDOA) of a signal from the emitter at three or more receiver sites. Multilateration can be cast into a set inversion problem that can be used efficiently in a reliable and robust way using interval analysis. The purpose of this seminar is to introduce in a pedagogical way the principles of interval methods and constraint propagation techniques. Then, in a second step, we will show how interval techniques can be applied for TDOA localisation of similar emitters.

[74] Nantes. SWIM 2010. June 15-16, 2010. pdf.

Title. Solving set-valued constraint satisfaction problems.

[75] Lesson. Vendredi 13 novembre 2010, 13h30-17h. "Calcul par intervalles et applications". Cours de master recherche UBO (Brest). Slides.

[76] Lesson. Ecole Navale. Brest. Mercredi 7 juillet 2010. Interval analysis for sea robotics. pdf.

[77] SCAN 2010, Lyon. 30 sept. 2010

Title. Solving set-valued constraint satisfaction problems. Slides.

Abstract. I will consider the resolution of constraint satisfaction problems in the case where the variables of the problem are subsets of Rⁿ. In order to use a constraint propagation approach, we introduce set intervals, which are sets of subsets of Rⁿ with a lower bound and an upper bound with respect to the inclusion. Then, we propose an arithmetic for them. This makes possible to build projection operators that are then used by the propagation. In order to illustrate the principle and the efficiency of the approach, a test-case is provided.

[78] Ifremer Robot voilier de l'ENSIETA. Slides.

2011

[79]. Journée ensembliste MEA. Jeudi 9 décembre 2010.

Title. Fleeting state estimation. pdf.

Abstract. This talk deals with nonlinear state estimation where measurements are available only when some given equality conditions are satisfied. For this type of problems, which are often met in robot localization when sonar or radar are involved, the data are qualified as fleeting because the measurements are available only at some given unknown dates. A new set-membership approach able to deal efficiently and reliably with nonlinear estimation with fleeting data is presented. The main idea to propose an arithmetic for interval functions (or tubes) and to use this arithmetic to allow a propagation through constraints involving functions. An illustration related to SLAM with one rotating telemeter will be given.

[80] Journée IHSEV, ENIB.
Jeudi 7 janvier 2011.

Méthodes ensemblistes pour la robotique. pdf.

[81] Présentation du profil robotique à l'ENSTA-Bretagne.pdf.

[82] Journée ensembliste MEA + SDH. Jeudi 3 février 2011.

Title. Interval state estimation of a nonlinear hybrid system: the sailboat. pdf.

Abstract : This talk deals with the state estimation of a sailboat robot, which is an example of nonlinear hybrid systems (the mainsheet can be tight or not). This problem is motivated by the microtransat challenge where small autonomous sailboat robots are designed to cross the Atlantic ocean. All components of such robots should be robust with respect to all situations (heavy weather, waves, salt water, low level of energy, long trip, ...). Two types of sensors can be considered.

A youtube video of our sailboat robot can be found at http://www.youtube.com/watch?v=jOjxRPnwQ9g

[83] Méthodes ensemblistes pour la localisation (ENSTA-Bretagne), Mardi 29 mars 2011. pdf.

[84] JIME 2011.

Titre : Quelques avancées récentes du calcul par intervalles permettant le traitement robuste de problèmes de grande taille ; applications à la robotique mobile. pdf.

Orateur : Luc Jaulin.

Résumé : Le calcul par intervalles est un outil numérique capable de résoudre une grande classe de problèmes non-linéaires, comme par exemple le calcul de tous les minima globaux d'un critère non-convexe ou bien le calcul de toutes les solutions d'un système d'équations non linéaires. Contrairement aux méthodes numériques classiques, le résultat est obtenu de façon globale et garantie en un temps fini, même lorsque des fonctions trigonométriques ou discontinues apparaissent dans le problème.

Malgré, toutes ses bonnes propriétés, le calcul par intervalles est resté relativement confidentiel dans la communauté automaticienne en raison des préjugés suivants :

· Trop couteux. Le nombre de variables doit être faible car sinon le temps de calcul est beaucoup trop grand.

· Pas robustes. Lorsque des bornes sur les erreurs de mesures ne sont pas rigoureusement respectées ou lorsque des données aberrantes existent, l'ensemble des solutions est vide et le résultat est difficilement exploitable.

· Difficiles mettre en oeuvre. L'implémentation efficace des méthodes intervalles est laborieuse et demande des connaissances approfondies en informatique.

· Peu d'applications réalistes. Il n'existe pas ou peu d'applications industrielles utilisant le calcul par intervalles et qui pourraient difficilement fonctionner sans un tel outil.

Dans cet exposé, nous allons chercher à démentir ces préjugés.

· Les méthodes par intervalles peuvent s'avérer très efficaces même quand le nombre de variables est très grand (>100 000, par exemple). Il suffit pour cela d'utiliser des méthodes de propagation de contraintes.

· Lorsque des données aberrantes sont présentes, on cherche à être cohérent, non pas avec toutes les mesures, mais avec un maximum d'entre-elles. On arrive ainsi à obtenir des méthodes d'estimation très robustes.

· Il existe des outils informatiques (Int4Sci, IntLab, QUIMPER, Alias, Profil Bias, C-XSC, ...) qui permettent de programmer rapidement et aisément des algorithmes ensemblistes.

· Des applications réelles convaincantes utilisant le calcul par intervalles commencent à voir le jour. Des robots utilisant le calcul par intervalles pour se localiser existent. Le SLAM avec des méthodes ensemblistes est utilisé pour la localisation de mines sous-marine, etc.

Quelques applications en robotique mobile sous-marine (localisation et SLAM) impliquant des robots réels dans des situations difficiles seront présentées afin d'illustrer ces affirmations.

Cet exposé sera présenté de façon pédagogique afin d'être compris dans son intégralité et sans difficulté par des non-spécialistes.

[85] Cours Ecole Navale. Brest. Lundi 8 juin 2011. Sea robotics. pdf.

[86] Swim 2011. Range-only SLAM with occupancy maps. June 14 2011. SWIM 2011, Bourges, pdf.

Abstract. This talk proposes a new set-membership approach for solving range-only

SLAM (Simultaneous Localization And Mapping) problems in the case where

the map is described by an arbitrary occupancy set (i.e., we do not assume that the

map is composed of segments, punctual marks,...). The principle is to transform

the SLAM problem into a hybrid constraint satisfaction problem (CSP) where the

variables can either be real numbers, vectors, trajectories or subsets of Rn.

An extension of existing constraint propagation methods is then proposed to

solve hybrid CSPs involving set-valued variables. A simulated test case is then

proposed to show the feasibility of the approach.

2012

[87] Journée ensembliste MEA + SDH.

Title: Reliable control using interval analysis. Application to sailboat robotics. Slides. Paper.

Speaker. Luc Jaulin (ENSTA-Bretagne, LabSticc).

Abstract. This talk proposes an interval based method for the validation of reliable and robust navigation rules for mobile robots. The main idea is to show that for all feasible perturbations, (i) there exists a safe subset A of the state space such that the robot cannot escape as soon as it enters in it and (ii) if the robot is outside A, it cannot stay outside A forever. The methodology will be illustrated on the line following problem of a sailboat robot. A validation on actual experiment made on January 2012 is presented. In this experiment the sailboat robot, named Vaimos, has gone autonomously from Brest to Douarnenez (around 100 km). More details on the experiment can be found at http://www.ensta-bretagne.fr/jaulin/vaimosdouarn.html

Come back to http://www.ensta-bretagne.fr/jaulin/