Groupe de travail MEA (méthodes
ensemblistes pour l’automatique)
Méthodes ensemblistes pour l’Automatique est un
groupe de travail du GDR
MACS
Son site officiel est : http://www.lirmm.fr/ensemble/
Pour s’inscrire
au GT
Liste
des membres du GT
Pour écrire à tout le gt : nom_du_gt(pour nous mea)-gdrmacs(at)univ-valenciennes.fr
Télécharger les slides de la réunion du 3 décembre 2009.
Télécharger les slides de la réunion du 13 novembre 2008.
Télécharger les slides de la réunion de juillet 2007.
Télécharger une version de QUIMPER déjà compilé pour Windows.
Pour la
réunion du 3 décembre 2009
10h00. Younis Hijazi
Title. Interval arithmetic in
visualization and computer graphics
Abstract. Interval arithmetic is
a powerful mathematical tool which has various applications in several computer
science fields, particularly in computational geometry, visualization and
computer graphics. I present three robust, general and efficient algorithms
based on interval arithmetic: first a novel approach for computing the arrangement of arbitrary implicit planar
curves; then two algorithms (one on the CPU, the other one on the GPU) for
ray-casting arbitrary implicit functions by jointly achieving, for the first
time, robustness, efficiency and flexibility. Indeed any implicit function can
be rendered at least interactively, at high resolution and with topological
guarantees. The visualization of dynamic surfaces in real-time is naturally
obtained using this technique. Also several shading effects enhancing the
visualization are demonstrated: shadows, transparency, multiple iso-values...
The combination of subdivision methods with interval arithmetic is the key
ingredient which guarantees the generality and robustness of all those
algorithms.
10h45. Nathalie Revol
Title: IEEE-1788 working group for the Standardization of
Interval Arithmetic
Abstract: In 2008, IEEE has approved the creation of a working
group that works to establish a standard for interval arithmetic. I will give a
short history of the creation of this working group. Then I will recapitulate the
main motions discussed so far and I will attempt to highlight the main issues
of a few
selected ones.
11h30. Gaetan videau.
Title : Guaranteed methods for state estimation and
consistency checks of continuous nonlinear systems.
Abstract. This work deals with the development of
set-membership methods for set estimation and consistency checks for nonlinear
continuous-time systems. The main objective is to setup a methodology for fault
detection and isolation for the systems where the determinism of faults
indicators on the health system is a necessary condition. Once placed in a
set-membership framework, the evolution of each variable is represented by an
envelope reflecting the internal and external uncertainties. This envelope
corresponds to the threshold beyond which the observed behavior is an abnormal
discrepancy over its nominal behavior, thus preventing the accomplishment the
mission objectives. The proposed methods are applied on a hydraulic laboratory
process.
12h15-13h30. Repas.
13h45. Ignacio ArayaTitle: Exploiting Monotonicity and Common Subexpressions for improving interval constraint propagation algorithms.
Abstract: When interval methods are used for solving systems of equations the constraint propagation algorithms issued from constraint programming are in the heart of the interval-based solvers. HC4 [1] and Box [1] are two of the best-known constraint propagation algorithms (contractors). They perform a propagation (AC3-like) loop and filter/contract the variable domains (reducing the bounds) with a REVISE procedure (HC4-Revise and BoxNarrow resp.) handling each constraint individually. One of the major obstacles to the performance of contractor algorithms is the dependency problem related to the multiple occurrence of variables in a constraint. When several variables appear several times in a constraint, neither HC4-Revise nor BoxNarrow perform an optimal contraction (i.e., they cannot remove all the incosistent values from the bounds of the interval domains). In this talk a monotonicity-based revise algorithm (Mohc-Revise) is presented [2]. It exploits the monotonicity of functions for performing better contractions of the variables domains. This revise algorithm uses three procedures for narrowing the domains, one is a monotonic version of HC4-Revise, another is close to BoxNarrow but, thanks to the monotonicity, is less costly and more effective (this procedure is similar to the Octum procedure proposed by Chabert and Jaulin [5]). The third procedure performs a preprocessing of the function with the objective of improving the effectiveness of the monotonicity-based methods. If f is monotonic w.r.t. all its variables Mohc-Revise performs an optimal contraction (i.e., it enforces the Hull-consistency). Experiments show that Mohc is a relevant approach to handle constraints having several variables with multiple occurrences, contrarily to HC4 and Box. The other major obstacle is related to the local scope of the contractor algorithms. Addressing this problem the well-known common subexpression elimination technique (CSE) is presented as an important preprocessing tool for bringing additional filtering during the propagation [3]. CSE basically consists in replacing each subexpression g(X) shared by two or more expressions by an auxiliary variable v and to add the new constraint v=g(X). The auxiliary variables allows to maintain and share contraction information that otherwise would be lost. Experiments show that I-CSE (a variant of CSE oriented to interval methods) leads generally to significant gains in performance, of sometimes several orders of magnitude.
References.[1] F. Benhamou, F. Goualard, L. Granvilliers, and J.-F. Puget. Revising Hull In Proc. ICLP, pages 230–244, 1999.[2] I. Araya, B. Neveu, G. Trombettoni. An Interval Constraint Propagation Algorithm Exploiting Monotonicity.International workshop IntCP, interval analysis, constraint propagation, applications, at CP conference, p. 65-83, 2009.[3] I. Araya, B. Neveu, G. Trombettoni. Exploiting Common Subexpressions in Numerical CSPs.Proc. of CP, constraint programming, LNCS 5202, Springer, p. 342-357, 2008.[4] I. Araya, B. Neveu, G. Trombettoni A New Monotonicity-Based Interval Extension Using Occurrence Grouping.International workshop IntCP, interval analysis, constraint propagation, applications, at CP conference, p. 51-64, 2009[5] G. Chabert, L. Jaulin: Hull
14h15.
Alexandre Goldsztejn and
Title: On the Exponentiation
of Interval Matrices
Abstract: The numerical
computation of the exponentiation of a real matrix has been intensively
studied. The main objective of a good numerical method is to deal with
round-off errors and computational cost. The situation is more complicated when
dealing with interval matrices exponentiation: Indeed, the main problem will
now be the dependency loss of the different occurrences of the variables due to
interval evaluation, which may lead to so wide enclosures that they are
useless. In this paper, the problem of computing a sharp enclosure of the
interval matrix exponential is proved to be NP-hard. Then the scaling and
squaring method is adapted to interval matrices and shown to drastically reduce
the dependency loss w.r.t. the interval evaluation of the
15h00. Luc Jaulin, Jan Sliwka, Fabrice Le Bars, Kai Xiao.
Title. Combining flatness theory with
interval analysis for state estimation; Application to sailboat robotics.
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
(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
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. 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
15h30-16h30. Discussion (SWIM 2010, ...)
1)
SWIM'10 devrait se produire à Nantes
2) Appel
de N. Revol à participer à SCAN'2010 qui se tiendra à Lyon
3)
Appel de T. Raissi à participer dans le cadre de NOLCOS 2010 (8th IFAC
Symposium on Nonlinear Control Systems)
qui aura lieu du 1er au 3 septembre 2010 à Bologne en Italie, à la session invitée
"Set-membership state and parameter
estimation for nonlinear systems".
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Retour à http://www.ensieta.fr/jaulin/