Résolution garantie de systèmes d’équations différentielles ordinaires avec des méthodes de programmation par contraintes.

Résolution garantie de systèmes d’équations différentielles ordinaires avec
des méthodes de programmation par contraintes.
Laboratoire : LIGM, Ecole des Ponts Paristech
Encadrement : Bertrand Neveu

Contexte
Le LIGM propose un stage de Master2 de 5 à 6 mois dans le laboratoire de
l’Ecole des Ponts à Champs-sur-Marne. Ce stage s’inscrit dans le cadre du projet ANR
CONTREDO “Intervalles et contracteurs pour les systèmes dynamiques”.
L’objectif principal de ce projet est de proposer des méthodes pour résoudre
de manière garantie des systèmes dynamiques d’équations différentielles couplées avec des
contraintes. Le cadre des problèmes de satisfaction de contraintes (CSP) est un modèle général
permettant de poser un problème sous forme d’un ensemble fini de variables, ayant chacune
un domaine et étant soumise à des contraintes. Une solution du CSP sera une affectation
de chacune des variables avec une valeur de leur domaine telle que les contraintes soient
satisfaites.
Quand les variables sont à valeurs réelles et que les domaines sont des intervalles, on a
un CSP numérique (NCSP). Il s’agit d’étudier dans CONTREDO des CSP sur trajectoires
(TrajCSP), qui comprennent en plus des variables réelles, des variables fonctionnelles y(t)
(fonctions à une variable représentant le temps, d’où le nom de trajectoires),
ayant pour domaines des tubes.

Sujet du stage
Dans ce cadre des TrajCSP, le problème le plus simple est l’intégration
garantie des systèmes d’ ́équations différentielles ordinaires (EDO) avec des valeurs
initiales données (IVP).
Ces valeurs peuvent être ponctuelles ou appartenir à des intervalles.
Il existe d’une part des méthodes permettant d’encadrer la solution y(t) d’une
EDO en des instsnts préd ́efinis et ces m éthodes font l’objet d’un module spécifique
DynIbex [AC16] du solveur de contraintes sur intervalles Ibex.
D’autre part, un module Tubex[RJM+ 17] définissant en Ibex des trajectoires
sous forme de tubes a été développé, mais il ne comprend actuellement qu’une méthode simple
d’intégration garantie.
Il s’agit dans ce stage d’étudier et de réaliser une extension de Tubex avec
les méthodes d’intégration garantie déjà programmées dans DynIbex. Ce développement
logiciel se fera sous la forme de contracteurs, qui constituent la base de la programmation par
contraintes sur intervalles[CJ09].

Poursuite en thèse
Ce stage pourra faire l’objet d’une suite en une tèse plus générale sur les
algorithmes pour la résolution de problèmes de satisfaction de contraintes sur trajectoires.
Ces algorithmes seront intégrés dans la plateforme logicielle développée dans le projet
Contredo et testés sur des applications des partenaires du projet en robotique marine ou en
planification de missions.

Connaissances souhaitées
algorithmique, C++, programmation par contraintes.

Contact
Bertrand Neveu
LIGM Ecole des Ponts Paristech
Bertrand.Neveu@enpc.fr
Tel : 0164152175

Références
[AC16]
Julien AlexandreDitSandretto and Alexandre Chapoutot. Dynibex : a
differential
constraint library for studying dynamical systems. In Proc.of HSCC 2016, 2016.
http ://perso.ensta-paristech.fr/ chapoutot/dynibex/.
[CJ09]
Gilles Chabert and Luc Jaulin. Contractor Programming. Artificial
Intelligence,
173 :1079–1100, 2009. http ://www.ibex-lib.org/.
[RJM+ 17] Simon Rohou, Luc Jaulin, Lyudmila Mihaylova, Fabrice Le Bars, and
Sandor M.
Veres. Guaranteed computation of robot trajectories. Robotics and Autonomous
Systems, 2017. http ://simon-rohou.fr/research/tubex-lib/.