Groupe Spécification formelle des modèles de simulation Responsables : Norbert Giambiasi (LSIS, Marseille) et David Hill (SIMA/LIMOS, Cler-mont Ferrand)

Les méthodes analytiques conduisent à établir des solutions générales, à partir desquelles se déduisent des solutions particulières par affectation de valeurs aux variables des expressions symboliques produites. L’utilisation de ces méthodes a, cependant, des limites. Leur principale limitation est issue de la complexité des systèmes à modéliser. Leur application nécessite, souvent, de simplifier le modèle du système à un niveau tel que les solutions obtenues sont alors difficilement transposables à la réalité. Face à une telle situation, les méthodes basées sur la simulation offrent une alternative. Cesméthodes, bien qu’inaptes à fournir une solution générale, permettent de trouver des solutions particulières transposables au système réel. En effet, les performances des techniques actuelles de simulation [22] autorisent le traitement de modèles présentant une grande complexité qualitative et quantitative (qualitative, liée à la sémantique du paradigme, quantitative, liée aux nombres de composants) tout en reproduisant assez fidèlement le comportement dynamique de systèmes réels complexes. Il est cependant évident que si le problème peut être correctement résolu par une méthode analytique, l’utilisation de la simulation ne se justifie pas.
La construction d’un modèle de simulation nécessite de passer par une spécification for-melle de ce modèle, spécification indépendante des détails de réalisation de la technique de simulation.
En fait, partant d’une spécification générale d’un système dynamique, il est possible de construire une spécification d’un modèle simulable dans l’un des trois paradigmes suivants :

  • équations différentielles,
  • formalismes à temps discrets,
  • formalismes à événements discrets.
Sur un plan plus formel, la classification des formalismes de spécifications par rapport au temps fait apparaître un quatrième formalisme : les équations aux différences.
On distingue alors les modèles à temps continus : équations différentielles et événements discrets, les modèles à temps discrets : automates et équations aux différences. Les travaux de recherche menés dans le cadre de la simulation et plus particulièrement la simulation à événements discrets ont contribué à la richesse de ces méthodes. Nous citons le formalisme DEVS offrant un cadre théorique et formel pour la spécification des modèles jusqu’à la simulation et l’analyse des résultats. Ce formalisme a été proposé par Zeigler dans les années 70, qui trouve ses fondements dans la théorie des systèmes [1]. Ce formalisme se distingue par rapport aux autres formalismes de simulation (automates à états finis, State-charts, réseaux de Petri, équations aux différences, etc.) par sa puissance d’expressivité et sa sémantique opérationnelle claire et non ambiguë.

DEVS et ses extensions

Le formalisme DEVS (Discrete Event System specification) permet d’avoir une descrip-tion déterministe et donc exécutable sur machine. Cette description est réalisée en amont d’un modèle informatique en vue de vérifier et valider par simulation cette dernière. Lesmodèles de base décrivent un système selon les trois vues préconisées par le génie logiciel : données, fonctions et contrôle (comportement). Ces éléments sont décrits par la structure algébrique suivante :
M = , où X et Y sont les ensembles d’événements d’entrée et de sortie respectivement. S est l’ensemble des états possibles du système (il peut être infini). Les transitions sont décomposées en deux sousensembles : les transitions externes et inter-nes exprimées par les fonctions dext et dint. Lors de l’occurrence d’un événement externe x et pour un état courant s, le système transite vers le nouvel état dext(s, e, x) avec e le temps écoulé dans l’état s. Si pendant l’intervalle [0,e[ aucun événement est prévu et la variable e atteint une certaine valeur D(s) qui définit la durée de vie de l’état s, une transition interne est déclenchée et le système passe à l’état dint(s). En parallèle la fonction de sortie l envoie l’événement de sortie y à l’environnement du système.
Ce comportement dirigé par des événements discrets est encapsulé dans des boîtes qui communiquent par le biais d’interaction (les événements déclenchés). Ce principe d’encapsulation permet d’avoir des modèles modulaires et réutilisables dans des nouveauxmodèles. Ajoutons à ceci le principe de composition qui permet de décrire des systèmes complexes par des modèles hiérarchisés en couplant des modèles de base, et obtenir par la suite un réseau de modèles simulables.
De nombreuses extensions basées sur ce formalisme ont été proposées. Elles ont pour but d’élargir le champ d’application de DEVS et de proposer des solutions à un niveau concep-tuel. A ce titre nous pouvons citer :
  • DS-DEVS [2] permet de décrire des systèmes à structure variable, systèmes dont les composantes et variables sont ajoutées, supprimées ou modifiées dynamiquement,
  • – G-DEVS [23] pour construire une abstraction plus concise et fidèle au système réel, et par conséquent une généralisation du formalisme DEVS, et RT-DEVS [14] a été proposé pour effectuer des simulations temps réel. Il repose sur la définition de fenêtres temporelles dans lesquelles les événements sont reçus et envoyés. Il permet d’inclure des comportements imprécis comme le délai de réaction des êtres humains par exemple.
  • Outils et plateformes DEVS

    Nous recensons actuellement une cinquantaine d’outils et plateformes mis à la disposition de la communauté scientifique. Certains de ces outils sont listés par le groupe de standardisa-tion DEVS. Ils vont de la pure implémentation des modèles par programmation jusqu’à offrir une interface graphique codant la totalité des éléments DEVS (état, transition, événement, port, etc.).
    L’outil ADEVS (A Discrete EVent Simulation) a été développé par l’équipe de Zeigler à l’université d’Arizona. Il offre un ensemble de librairies extensibles pour l’implémentation des modèles DEVS spécifiés. Le noyau de simulation est codé en C++. Une version en Java existe sous le nom DEVSJava, intégrant une partie graphique pour les modèles couplés. L’environnement VLE (Virtual Laboratory Environment), développé au sein du laboratoire LIL, offre une interface utilisateur plus convivial. Un gain majeur en temps pour le dévelop-pement des modèles à moindre erreur de codage. D’autres fonctionnalités font parties de cet environnement comme la définition des schémas d’expérimentation pour le chargement des données de la simulation, la sauvegarde des modèles en XML, etc.

    Défis de la M&S DEVS en France

    Ces dernières années plusieurs groupes de travail ont adopté le formalismeDEVS comme base de leurs travaux de recherche. Cette reconnaissance acquise en France est due en grande partie à la volonté et l’effort fourni de certains laboratoires de recherche comme l’IRIT, LIMOS, LIL et LSIS pour promouvoir ce formalisme.
    Récemment, il y a eu un consensus sur le rôle que doit jouer la communauté française DEVS : faire de cette discipline une science reconnue par les acteurs actifs de la recherche en France. Sur le plan pédagogique, les chercheurs de cette communauté fournissent des efforts considérables pour intégrer la M&S (Modélisation & Simulation) DEVS dans les cursus universitaires, et pourquoi pas dans le futur proche offrir des formations complètement dé-diées à la simulation. Le papier de [53] retrace leur expérience d’enseignant et propose un guide pour le montage de cours en simulation avec les principales clés de réussite. L’environnement LSIS_DME (DEVSModel Editor) développé par des chercheurs du LSIS contribue dans ce sens en offrant un cadre pédagogique : construction graphique des modèles atomiques et couplés, réutilisation des modèles développés par cliquer-glisser, animation des simulations, etc.Une particularité qui le distingue des autres environnements de simulation.
    Sur le plan scientifique, plusieurs projets de recherche sont en cours. Le plus intéressant est SiMoDEVS (SImulation desModèles DEVS) qui regroupe en majorité des laboratoires de recherche français avec la participation de chercheurs étrangers dans le but de définir un standard pour la modélisation et la simulation à événements discrets sur la base de DEVS. Par des mécanismes de mapping et de wrapping des modèles hétérogènes décrits dans d’autres formalismes hors DEVS (les extensions de DEVS, Statecharts, équations différen-tielles, etc.) seront simulés par un noyau DEVS, afin de garantir une unique sémantique opérationnelle et par conséquent une meilleure interopérabilité des modèles et des environ-nements utilisés

    • [53] H. Szczerbicka, J. Banks, R. Rogers, T. Ören, H. Sarjoughian et B. Zeigler : Concep-tions of curriculum for simulation education : panel.Winter Simulation Conference, pp.1635-1644, 2000.
    • [22] R Fujimoto. Parallel discrete event simulation : Will the field survive ? ORSA Jour-nal on Computing, 5(3) :213- 230. 1993.
    • [23] Giambiasi,N. and B. Escudé : GDEVS : A generalized discrete event specification for accurate modeling of dynamic systems, Transactions of the Society for Computer Simulation International, v.17 n.3, pp.120-134, 2000.
    • [14] S. Cho et T. G. Kim : Real time simulation framework for RT-DEVS models. v. 18 n.4 décembre 2001
    • [1] M.A Arbib, Theories of abstract automata. Prentice- Hall ed. 1967, New York : Prentice-Hall. [2] F. J. Barros. Modeling formalisms for dynamic structure systems. ACM Trans. Model. Comput. Simul. 7(4), pp. 501-515, 1997.

Accueil  | Actualités  | Groupes  | Equipes  | Livres  | Cours  | HDRs / Thèses  | JFSMA  | Liens  | 


GDRI3 CNRS


Modifié en par Cédric Herpson