Journée "calcul ensembliste" au CNAM

Groupe de travail MEA (*méthodes
ensemblistes pour l’automatique*)

La prochaine réunion du GT MEA aura lieu **le Jeudi 14 novembre 2013**
au Conservatoire National des Arts et Métiers CNAM 292, Rue St-Martin, Paris
03, **salle 11B02 (accès 11)**.

**Program**

**10h. Speaker. **Vincent
Drevelle (ENSTA-Bretagne, Brest).

**Title.** Guaranteed
Characterization of the Explored Space of a Mobile Robot by using Subpavings. Slides.

**Abstract**. We propose a
method to characterize the space explored by a mobile robot during a mission.
Because of localization uncertainty, the area osculated by a sensor at a given
time is uncertain too. The problem is modelled by using intervals to represent
trajectory uncertainties and a “visibility function” to describe
the area in view at a given time. A set-inversion method is then applied to
compute a “guaranteed visible area” and a “possible visible
area” with respect to positioning uncertainty. A bracketing of the actual
explored area between a “guaranteed explored area” and a
“possible explored area” for the whole mission is finally obtained
by respectively taking the union of the guaranteed and possible areas. Results
from a simulated underwater exploration mission are presented.

**10h30. Speaker. **Moussa
MAIGA (LAAS, Toulouse)

**Title. **Efficient method
for guard set intersection in nonlinear hybrid reachability. Slides.

**Abstract**. Reachability
computation formulates the problem of simulating the behavior of a continuous
or hybrid dynamical system in a set-theoretical framework. Compared to the
stochastic approach, it provides guaranteed results and has been shown highly
valuable for verification or synthesis tasks. This issue is still quite
challenging for uncertain nonlinear hybrid dynamical systems. Recently, [1]
proposed a method for solving the flow/guard intersection problem that is at
the core of hybrid reachability. It first derives an analytical expression for
the boundaries of continuous flows using interval Taylor methods and techniques
for controlling the wrapping effect. It then expresses the event detection and
localization problem underlying flow/guard intersection as a
constraint-satisfaction problem (CSP). One of the main issues in interval
integration is to control, at each step, the overestimation of the reachable state
set due to the wrapping effect. For this purpose, [1] only relies on the
geometrical transformation induced by Lohner’s QR-factorization method
[2], which acts at the integration step. But when dealing with hybrid systems,
another source of overestimation exists at the transition step. In this talk we
will describes an efficient method for solving flow/guard intersection: using
the standard contractor HC4Revise at the transitions step, we will show how to
minimize both the overestimation of the flow/guard intersection and the

computational complexity, hence computation time. Interestingly, the geometrical transformation introduced by Lohner’s QR-factorization method combined with our method, eventually minimizes the overestimation for the whole hybrid flow trajectory. The performance of the new method is illustrated on examples involving typical hybrid systems.

REFERENCES

[1] N. Ramdani and N.S. Nedialkov. Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint propagation techniques. In Nonlinear Analysis Hybrid Systems, pages 149–162, 2011.

[2] R. J. LOHNER, Enclosing the solutions of ordinary initial and boundary value problems, in Computer Arithmetic: Scientific Computation and Programming Languages, E. W. Kaucher, U. W. Kulisch, and C. Ullrich, eds., Wiley-Teubner Series in Computer Science, Stuttgart, 1987.

** **

**11h00. Speaker**. Rihab El
Houda El Thabet (IMS Bordeaux)

**Title**. Synthèse d'observateurs pour des systèmes LPV et LTV. Slides.

**Abstract**. Le problème de l'estimation d'état a été largement
étudié dans la littérature. Cependant, caractériser explicitement des bornes
sur les états estimés pour des classes génériques de systèmes dynamiques non
linéaires avec des incertitudes sur les entrées et les paramètres reste un
problème difficile, notamment dans un contexte de surveillance en ligne avec
des contraintes de calcul en temps-réel. La présentation portera sur
l'estimation d'état de systèmes continus a incertitudes bornées, en se basant
sur des approximations à base de dynamiques LPV (Linéaires à Paramètres
Variant) et LTV (Linéaires à Temps Variant). Pour cela, des observateurs
intervalles seront présentés en s'appuyant sur des notions de monotonie et des
changements de variables pour construire des systèmes englobant. Les principes
des preuves de stabilité relatives aux valeurs estimées et aux largeurs des
bornes calculées seront présentés et les principaux résultats obtenus seront
illustrés numériquement.

**11h30. Speaker**.** **Luc
jaulin (LabSTICC, Brest).

**Title**. Pure range-only SLAM with indistinguishable landmarks; a
constraint programming approach. Slides.

**Abstract**. This presentation deals with the simultaneous localization
and mapping problem (SLAM) for a robot. The robot has to build a map of its
environment while localizing itself using a partially built map. It is assumed
that (i) the map is made of punctual static landmarks, (ii) the landmarks are
indistinguishable (which is the main contribution of this work), (iii) the only
exteroceptive measurements correspond to the distance between the robot and the
landmarks. In our SLAM problem, the unknown
variables have an heterogeneous nature: the landmarks are vectors of R2, the
trajectories belong to the set of functions from R → Rn, the free space
is a subset of R2 and the data associations can be represented by a graph G.
This talk shows that constraint propagation methods can easily deal with
heterogeneous variables and that solving the SLAM problem amounts to use a fixed
point method with specific contractors. The resulting method will inherit
properties of constraint propagation tools: a polynomial time algorithm which
provides guaranteed results.

**12H00**. **REPAS**

**14h00. Speaker**. Aymeric
Bethencourt (DGA, ENSTA-Bretagne). Slides.

**Title**. Solving non-linear
constraint satisfaction problems involving time-dependent functions.

**Abstract**. In this
presentation, we consider the resolution of non-linear problems in the case
where the variables of the problem are functions from R to Rn. In order to use
a constraint propagation approach, we introduce intervals of functions (named
tubes), which lower and upper bounds are functions from R to Rn with respect to
the inclusion. We propose basic operations on tubes and contractors that allow
us to solve problem involving functions as unknown variables. In order to
illustrate the principle and efficiency of the approach, several test-cases are
presented and a implementation with IBEX will be provided.

**14h30. Speaker**. Julien
Alexandre dit Sandretto (INRIA, COPRIN, Nice).

**Title**. Certified
calibration of parallel cable-driven robots. Slides.

**Abstract**. Our objective
is to propose new methods for the calibration of a large scale cable-driven
robot.

The principal method to improve the global behavior of a robot consists to identify the parameters of the model. For this, it is important to get redundant information by measuring the state of the robot in different configurations. However, the model used is a compromise between its ability to represent the actual behavior of the manipulator and the information available to fill in it. In the special case of the large scale cable-driven robots, mass and elasticity of the cables have a significant influence on the behavior of the robot but they are difficult to model. Indeed, the physical model of the cable is complex and requires knowledge of the tension inside it. Available sensors can not provide this information with a sufficient accuracy to fill in a model of a realistic cable, we thus propose to use a simplified model. In order to provide an efficient calibration, it is necessary to fix the requirements to use this simplified model. Then, we have adapted and implemented some classical techniques for the calibration of parallel robots, but we also developed more innovative approaches. We propose a model for cable robots based on a representation of the uncertainties from modelling, measurements and parameters using intervals. By exploiting the interval analysis, we have developed various approaches to identify with certification the geometric parameters of the structure. We thus propose a new approach and associated algorithms to characterize and compute different kind of solutions for the calibration problem. In addition, based on recent results obtained with constraint programming, this thesis describes a new method for the identification of parameters, robust to outliers and modeling uncertainties. The methods presented were implemented and applied to the calibration of the large scale parallel cable-driven robot built in the CoGiRo national project.

**15h00. Auteur**: Olivier
Boussiou (CEA Saclay Nano-INNO), Alexandre Chapoutot (ENSTA ParisTech) , Adel
Djaballah (ENSTA ParisTech) , Michel Kieffer (Supelec).

**Title**: Template-Based
Computation of Barrier Certificates of Continuous Dynamical Systems using
Interval Constraints. Slides.

**Abstract**. The formal
verification of safety properties for hybrid systems is an important but
challenging problem. Recently, barrier functions have been introduced to prove
safety without requiring the computation of the reachable set of continuous or
hybrid dynamical systems. We present a new approach for the construction of
barrier functions for safety verification of nonlinear and non-polynomial
dynamical systems. Our method is based on the search of the parameters of a
parametric barrier function using interval analysis. This technique allows to
handle complex dynamics without the need of a relaxation of the barrier
certificate constraints in an efficient manner, as demonstrated through several
examples.

**15h30. Speaker**. Victor
Lecointre, Stéphane Le Menec (MBDA, Paris).

**Title**. Verification of
the convergence properties of non-holonomous robots using interval analysis and
Lyapunov methods. Slides.

**Abstract**. This
presentation deals with the Validation and Verification of dynamic systems when
uncertainties occur in the system evolution; i.e. differential inclusions
[1]. The systems under investigation are non holonomous vehicles
following references trajectories. The aim of this study is to check how such
mobile vehicles are able to follow pre-planned 4D trajectories (x, y, z, t).
Thanks to interval-based methods we study the validity of complex systems. In
accordance to this approach we adjust parameters of the vehicle controller; we
modify the vehicle mission (trajectory planning); we specify the maximum system
uncertainties we can handle in a way to stay inside acceptable error margins
when following reference trajectories. The challenge is clearly about how such
approaches are able to deal with realistic systems; and can take into account
time dependent reference trajectories. The resolution process is based on set
arithmetic methods implemented in the C++ library IBEX 2.0 which provides
interval arithmetic tools.

References

[1] J.P. Aubin, A. Bayen and P. Saint-Pierre. Viability Theory. Springer- Verlag Berlin Heidelberg 2011.

[2] P. Arnaudin. Safety of robot patrols with interval analysis. ENSTA-Bretagne student report. 2013.

[3] L. Jaulin and F. Le Bars. An interval approach for stability analysis; Application to sailboat robotics. IEEE TRO. 2012.

[4] Ibex 2.0. A C++ library based on interval arithmetic. http://www.emn.fr/z-info/ibex/.

**16h00**. Speaker. Hoda Dandach,
Jérome De Miras, Ali Charara, Heudiasyc (Compiègne).

**Title**. Guaranteed
Characterization of the Vehicle Stable State Domain. Slides.

**Abstract**. We propose a new
approach to compute the vehicle state stability domain described with two
essential elements: the longitudinal velocity and the side slip angle at the
vehicle centre of gravity. The stable behaviour is determined in respect to
risks involving vehicle roll-over and over/under steering. The stability domain
is computed in a guaranteed way, using interval analysis. A validation with
simulated data is provided in order to illustrate the principle and the
efficiency of the approach.

**16h30. Résultats de la discussion**

- Bilan de SWIM2013 Brest. Positif, à continuer.

- Le numéro spécial de revue *Mathematics in Computer Science* suite
à SWIM'2013: les soumissions sont attendues.

- SWIM 2014. C'est officiel, SWIM'14 se tiendra a Uppsala en Suède les 9-10-11 juin. Warwick Tucker nous accueille.

- La proposition de Nicolas Langlois et Estelle Courtial de faire une
réunion inter GT : *Méthodes ensemblistes pour l'automatique *et *Commande
prédictive non-linéaire *a été très bien accueillie. Elle sera probablement
organisée en 2014 (février, mars, avril ?).

- Notre prochaine réunion MEA se tiendra à Brest le jeudi 5 décembre sur
le thème *intervalles et géométrie.*

** **

**17h. Fin de la journée**

** **