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