Projet MathSTIC " SQUASH "

Analyse Qualitative des Systèmes Hybrides

(proposition)

Participants

1. Laboratoire de modélisation et de calcul (LMC) UMR 5523 CNRS (STIC et SPM) -INPG UJF. Equipe MOSAIC

Jean Della Dora (Prof. ENSIMAG)

Jean-Guillaume Dumas (MdC UJF, contact LMC)

LMC-IMAG, B.P. 53 38041 Grenoble cedex 9

Tel : 04 76 51 46 05, Fax : 04 76 63 12 63

Jean.Delladora@imag.fr, Jean-Guillaume.Dumas@imag.fr

4 thésards.

2. VERIMAG UMR 5104 CNRS (STIC) - INPG UJF. Equipe TEMPO

Eugène Asarin (Prof. UJF, coordinateur, contact VERIMAG)

Oded Maler (DR CNRS)

Sergio Yovine (CR HDR CNRS)

VERIMAG

Centre Equation, 2 avenue de Vignate

38610 Gières

Tel : 04 76 63 48 33 Fax : 04 76 63 48 50

Eugene.Asarin@imag.fr; Oded.Maler@imag.fr; Sergio.Yovine@imag.fr

1 thésard.

Contexte scientifique

Le domaine scientifique des systèmes hybrides combinant les composants (ou comportements) discrets et continus date de dix ans. Initialement développés comme modèles des procédés continus avec contrôleurs digitaux, les modèles hybrides s'avèrent très utiles dans l'automatique, la productique, la télécommunication, aussi bien que dans la biologie. Tout en étant de définition simple, les systèmes hybrides offrent dans l'étude de leur dynamique une très grande richesse mathématique.

L'analyse des systèmes hybrides est aujourd'hui un domaine de recherche très actif dans les milieux académiques et industriels [1-5]. Issue à l'origine d'une problématique à cheval entre l'automatique et l'informatique, la recherche sur la modélisation et l'analyse de systèmes hybrides fut menée, jusqu'à présent, principalement par ces deux disciplines.

Analyse Qualitative des Systèmes Hybrides le défi

Pendant la première décennie de la recherche sur les systèmes hybrides, la problématique de l'analyse qualitative du comportement de tels systèmes restait à l'ombre de questions d'atteignabilité et de commande automatique. Nous sommes certains que l'exploration théorique et la création des outils informatiques, permettant de calculer le portrait de phase d'un système hybride, d'énumérer ses attracteurs, ses zones de comportement chaotique etc, auront un intérêt majeur pour la théorie des systèmes hybrides, pour ses applications à l'automatique, et aussi pour la théorie des systèmes dynamiques. Naturellement, une telle recherche doit tenir compte de la " malédiction de l'indécidabilité ". Cependant, la plupart des problèmes seraient décidables en dimension deux pour les systèmes généraux, et en dimension supérieure pour les systèmes non-chaotiques. Le défi consiste donc à faire l'exploration complète des cas décidables, à trouver des semi-algorithmes efficaces dans les cas indécidables et à trouver les conditions géométriques et dynamiques garantissant la décidabilité.

Compétences des partenaires

L'équipe TEMPO (VERIMAG) travaille dans le domaine des systèmes hybrides depuis cinq ans. Sa reconnaissance internationale dans le domaine est confirmée par des nombreuses publications, participation dans des comités de programmes et surtout par la coordination de deux projets européens sur les systèmes hybrides (VHS : 1999-2001 et CC : 2001-2003) consacrés plutôt aux aspects automatique et informatique du sujet. Le groupe a des compétences dans les domaines de la vérification, de l'analyse de décidabilité, de l'algorithmique pour l'analyse d'atteignabilité et pour la vérification des systèmes hybrides, dans le développement des outils informatiques pour une telle analyse (KRONOS pour les systèmes temporisés, d/dt [11] pour l'analyse approchée des systèmes hybrides).

L'équipe MOSAIC (LMC) a des compétences dans les domaines des équations différentielles et algébro-différentielles, du calcul formel et dans le développement des outils logiciels (DESIR, PAC, LINBOX). Le groupe dirigea un Groupe de travail européen CATHODE et participe au projet NSF-CNRS LINBOX. Depuis deux ans le groupe travaille sur les systèmes hybrides et leurs applications à l'analyse numérique et à la biologie.

La coopération entre les deux partenaires date de deux ans et se réalise dans le cadre du projet grenoblois IMAG-MASH (Modélisation et Analyse de Systèmes Hybrides [10]). Cette coopération aboutit à plusieurs publications (par ex. [8,9]) ainsi qu'à la découverte des perspectives décrites dans ce document.

Les compétences complémentaires des partenaires et leur expérience positive de coopération donnent la certitude que le projet proposé sera mené à terme avec succès.
 
 

Le Projet : partie théorique

  1. Systèmes non-déterministes constants par morceaux sur le plan

  2. Pour toute cette classe de systèmes nous espérons développer des algorithmes complets pour calculer le portrait de phases. Ceux-ci devraient se baser sur les résultats de TEMPO relatifs au problème d'atteignabilité [6,7]. Dans cette partie du projet nous étendrons la notion du portrait de phase sur les systèmes hybrides non-déterministes et adapterons l'algorithme d'atteignabilité.

  3. Systèmes linéaires par morceaux sur le plan

  4. Nous explorerons la dynamique de cette classe de systèmes pour laquelle nous pouvons espérer l'existence d'un algorithme complet. Si un tel algorithme n'existe pas, des semi-algorithmes et une méthodologie pratique d'analyse seront développés.

  5. Géométrie et décidabilité pour la dimension deux

  6. Nous explorerons la dynamique des systèmes hybrides avec des " resets ", ce qui se ramène aux systèmes dynamiques constants ou linéaires par morceaux sur des variétés de dimension deux. Nous explorerons comment la géométrie d'une telle variété influence la décidabilité du problème.

  7. Systèmes hybrides de dimension supérieure

  8. Nous savons qu'à partir de la dimension trois des algorithmes complets n'existent pas [6]. Nous développerons des semi-algorithmes et une méthodologie pratique d'analyse pour des systèmes constants et linéaires par morceaux.

  9. Approximation des équations et inclusions différentielles non-linéaires par des systèmes hybrides
Les méthodes développés dans le cadre de ce projet pourront être pour une nouvelle approche de l'analyse numérique consistant à approcher les systèmes (algébriques ou différentiels) complexes par des systèmes hybrides analysables [8]. A cette fin nous développerons des méthodes efficaces pour de telles approximations.

Le Projet : implantation

Pour valider les résultats théoriques et pour effectuer le travail expérimental et applicatif nous implanterons les algorithmes dans un atelier de systèmes hybrides. Dans le premier temps cet atelier serait limité aux systèmes sur planaires, avec la perspective de l'étendre en dimension supérieure.

L'atelier de systèmes hybrides planaires contiendrait plusieurs outils interconnectables, tels que

Une réflexion sur l'architecture du système est nécessaire. En particulier les trois premiers outils doivent être compatibles avec les outils existants (Matlab, Hytech, d/dt).

En raison des problèmes algorithmiques complexes soulevés par les deux derniers outils, leur création sera une tâche plus lourde.
 
 

Avancement des travaux
 
25 avril 2002 Un prototype matlab de l'hybridisateur est disponible : CASCADE (Computational Analysis and Simulation using Continuous Approximations for Differential Equations)
Fin mai 2002 Prototype Java de l'éditeur
Fin mai 2002 Définition XML d'un système hybride : HSML
Fin mai 2002 Prototype Java de compilateur HSML vers d/dt

 

Bibliographie

[1-5] Hybrid Systems: Computation and Control: HART'97, HSCC'98, HSCC'99, HSCC'2000, HSCC'2001: LNCS 1201, 1386, 1569, 1790, 2034, Springer-Verlag.

[6] E. Asarin, O. Maler, A. Pnueli, On the Analysis of Dynamical Systems having Piecewise-Constant Derivatives, Theoretical Computer Science 138, 35-65, 1995

[7] E. Asarin, G. Schneider, S. Yovine. On the decidability of the reachability problem of planar differential inclusions. Dans " Hybrid Systems: Computation and Control, HSCC'01 ". Rome, Italie, 28-30 Mars 2001. LNCS 2034, Springer-Verlag.

[8] J. Della Dora, A. Maignan, M. Mirica-Ruse, S. Yovine. Hybrid computation. Dans " International Symposium on Symbolic and Algebraic Computation ISSAC'01 ". London, Ontario, Canada, Juillet 2001.

[9] J. Della Dora, S. Yovine. A methodology for analyzing the dynamics of hybrid systems. Dans "European Control Conference, ECC'01". Porto, Portugal, 4-7 Septembre 2001.

[10] Page web du projet MASH : http://www-lmc.imag.fr/MOSAIC/MASH

[11] Page web de l'outil d/dt : http://www-verimag.imag.fr/~tdang/ddt.html