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
SWIM 2012.
5th edition of the
Small Workshop on Interval Methods will
be held on 4-6 June 2012 in
http://hs.informatik.uni-oldenburg.de/swim2012
Pour la
réunion du 2 février 2012 sur les méthodes ensemblistes pour la navigation
Voir le mini-site de la journée
Télécharger les slides de la réunion du 9 décembre 2010.
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ée pour Windows.
Pour la
réunion de 9 décembre 2010
Malgré la neige, nous étions 18 et les 6 présentations prévues ont eu lieu.
Vous pouvez télécharger les http://www.ensieta.fr/jaulin/mea_dec10.zip
10h00. Set-membership identifiability:
definitions and analysis
Carine Jauberthie, Louise Trave-Massuyes, Nathalie Verdiere.
Abstract. Definitions and
methods for checking the identifiability of linear and
non
linear systems are now well established. However this property has
not
really been investigated for uncertain system, in particular for
set-membership
models in a bounded-error context. We propose two
complementary
definitions, set-membership identifiability and
mu-set-membership
identifiability, the first one is conceptual whereas
the
second can be out in correspondence
with existing set-membership
parameter
estimation methods. The links between these definitions are
exhibited
and some methods to verify them are proposed. Some examples
are
developed.
10h45. Beyond the bounded error framework for non linear
state estimation
Fahed Abdallah
Abstract. In many application
areas it is necessary to estimate the state of a dynamic system using a
sequence
of noisy sensor
measurements. When making real data measurements, different results are
usually obtained when
the same measurement is repeated. Usually, statistical methods are used to
model maximum information
from the results. The interval framework would appear to be a good
methodology for
dealing with non-white, biased measurements, particularly when these measures
vary around a
central value within certain bounds. This framework will be used in order to
introduce
an interval-based
multisensor data fusion approach based on the well-known particle filter
algorithm.
Instead of point
particles and probabilistic models for the errors and for the inputs, the key
idea of
the presented
method, called BPF for Box Particle Filter, is to use box particles and a
bounded error
model.
In this talk I will
present also a survey on some new results on state estimation using another
theory
than that of
intervals, namely probability and belief functions theories. In fact, the BPF
algorithm and
variants have been
the starting points of many important developments where a link is established
between the BPF
method and an original algorithm to estimate the posterior density of the state
using
weighted sum of
uniform distributions. The idea of BPF where also extended to the case of the
belief
functions theory.
The extension uses belief structures composed of a finite number of axis-aligned
boxes with
associated masses. Such belief structures can represent partial information on
model and
measurement
uncertainties more accurately than can the bounded-error approach alone. Focal
sets
are propagated in
system equations using interval arithmetics and constraint-satisfaction
techniques,
thus generalizing
pure interval analysis.
These methods were
applied to various problems as for example to locate a land vehicle using a
dynamic fusion of
Global Positioning System measurements with dead reckoning sensors, or to
locate
sensors in a sensor
network applications.
The talk will
conclude with a discussion of some open problems concerning state estimation
using
different frameworks.
11h30. Performances analysis of controlled interval systems using H∞ approach
Sofiane Khadraoui, Micky Rakotondrabe and Philippe
Lutz
Abstract:
Control strategies for dynamical systems are based on an appropriate
model and often
require a good knowledge of the system properties and its environment.
However, the
characteristics of the most physical systems are complex and non interpretable
due to the
nonlinearities, high-dimensional aspect, time-varying parameters and the
complex sensitivity to the
environmental conditions. For that, many simplifications are often introduced
during the modelling
in order to obtain usable models. As a result, the used models are subjected to
uncertainties. These
uncertainties present a challenge to control systems when particularly the
objective is to achieve
robust performances using limited information.
One
method to deal with uncertainty and robust control design is interval analysis
where
the parametric uncertainties are characterized by intervals. The principle of
the control design
consists to combine a linear theory of control with interval arithmetic. The
controller design
problem is based on a given interval model which represents a family of models
and a wanted
interval closed-loop (a family of models describing desired performances).
Hence, interval
techniques are automatically introduced to solve the problem and to compute the
set solution of the
controller parameters.
In this
talk, after designing a controller by combining interval arithmetic and a
linear
control theory, we perform the robust performances analysis of the closed-loop
by means of the H∞
approach. The objective consists to check if the computed controller
ensures the required
performances for the uncertain system (interval system). The analysis is based
on the H∞ standard
problem which – for its classical use - consists to compute a controller C(s)
such that
||Fl(P(s),C(s))||∞≤
γ, where γ≤1 and Fl(P(s),C(s))
represents the interconnection between C(s) and
the augmented plant P(s) that contains the system to be controlled and
the weightings defining the
specifications. An example is given via the control and robust performances
analysis of
piezoelectric cantilevers used to develop Microsystems.
12h15. Repas.
14h. A parallelotope method
for the simulation of nonlinear hybrid systems
Alexandre Goldsztejn and Daisuke Ishii
Abstract: Parallelotope methods
allow dealing with the wrapping effect better
than boxes. They proved to be very efficient for the rigorous
simulation of ODE for small sets of initial conditions. We extend a
previously proposed parallelotope method to the simulation of hybrid
systems. Presented experiments show that the proposed parallelotope
method for hybrid systems presents the same advantages as its simple
ODE counterpart: It successfully strongly reduces the wrapping effect
for small initial conditions.
14h45. On the
Lyapunov stability problem for discrete-time non-stationary systems in the
framework of asymptotically contractive sets
Rachid Bouyekhf
Abstract. This talk
provides theoretical solutions to the problems of the
stability theory for discrete-time non-stationary systems in the
framework of asymptotically contractive sets. It is shown that the
classical Lyapunov stability conditions cannot be applied to the
stability test as soon as the system instantaneous domain of
asymptotic stability is asymptotically contractive. In order to investigate
asymptotic stability of the zero state in such a case, novel criteria
are developed by using properties of the set generating
function rather than the Lyapunov function. The main advantage
of this approach is that the set generating function need not be
continuous
with respect to time and/or the state, hence it is not necessary to
be
positive definite.
15h30 State estimation
with fleeting data
F. Lebars, J. Sliwka, O. Reynet, L. Jaulin
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.
16h15. Discussions
17h. Fin.
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".
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Come back to http://www.ensta-bretagne.fr/jaulin/