Aujourd'hui en France, l'évaluation de la performance de stratégies de sécurité à déployer pour mettre un bâtiment en sécurité vis-à-vis de l'incendie repose sur une étude d'ingénierie en sécurité incendie. Cette étude a pour objectif l'estimation du risque incendie pour différentes stratégies, et pour des scénarios d'incendies jugés pertinents. Pour parvenir à cette estimation, le Centre Scientifique et Technique du Bâtiment français (CSTB) a mis au point un outil de simulation appelé SCHEMA-SI. Cet outil utilise des réseaux de Petri prédicat-transition différentiels orientés objets et des simulations de Monte Carlo pour générer de multiples scénarios d'incendie. Ces scénarios sont ensuite utilisés pour évaluer le risque incendie encouru avec une stratégie de sécurité. La stratégie est alors jugée d'autant plus performante que le risque incendie est faible. L'objectif de la thèse consiste à contribuer au développement d'une méthode d'analyse de risque incendie utilisant l'outil de simulation SCHEMA-SI. La réflexion a débuté par la définition de ce que devrait être cette méthode. A ce stade, il est apparu que l'une des difficultés que la méthode doit surmonter est celle de la mise en donnés du problème par un groupe d'acteurs impliqués dans la sécurité incendie du bâtiment étudié. Pour résoudre cette difficulté, une méthode de modélisation spécifique a été construite. Cette méthode, baptisée ISI-Systema, repose sur deux fondements principaux : d'une part, un langage graphique de modélisation permettant au groupe d'acteurs de réfléchir à la mise en données du problème en s'appuyant sur une approche systémique ; d'autre part, une démarche de traduction des modèles graphiques obtenus avec le langage systémique en réseaux de Petri compatibles avec SCHEMA-SI.Enfin, une application pratique de cette méthode de modélisation est proposée.

Le trafic routier entraine de nombreux effets néfastes, dont la pollution, l'insécurité et la congestion. La plupart de méthodes développées, pour la régulation du trafic urbain au niveau des carrefours, cherche à réduire les temps d’attente et les longueurs des files d'attente. Ces méthodes se fixent principalement comme objectif l’optimisation des cycles de feu sur un horizon fini.Pour la description du trafic, nous adoptons une modélisation par les réseaux de Pétri Hybrides (RdPH), qui représente, simultanément, deux niveaux de représentation complémentaires : l'évolution continue des files d'attente et l'évolution discrète des feux tricolores. Ces deux niveaux sont, respectivement, articulés autour des réseaux de Pétri à vitesses variables et des réseaux de Pétri discrets temporisés.Nous élaborons en plus, une nouvelle stratégie pour résoudre le problème de la régulation du trafic urbain intervenant d'une manière adaptée au niveau des feux de signalisation. Nous cherchons à éviter, en premier lieu,la congestion et la sursaturation des files d'attente, qui ne doivent pas dépasser l'optimum des capacités des voies de l'intersection et, en second lieu, à réduire le temps d'évacuation des véhicules au niveau du carrefour et surtout les temps d'attente des conducteurs.Dans ce sens, un premier algorithme est élaboré pour calculer les longueurs des files d'attente, utilisant une approche qui se base sur la simplification de la modélisation d'un carrefour. Pour optimiser le temps moyen d’attente et le temps total d'évacuation sont, considérés et appliqués, avec succès, une heuristique de contrôle et une stratégie de régulation à feux fixe et à feux variables, suite à la détermination de la durée de feu vert correspondante à la situation de l'intersection en temps réel.Nous envisageons, de généraliser les résultats de nos travaux exploitant le modèle RdPH aux intersections plus complexes pour des situations réelles d'un réseau de carrefour. / Road traffic causes many adverse effects, including pollution, insecurity and congestion. Most of the developedmethods for regulation of urban traffic at crossroads, seeking to reduce wait times and lengths of queues. Thesemethods are mainly set objective optimization fire cycles over a finite horizon.To describe the composition of traffic, we opted for a traffic modeling by hybrid Petri nets, representingsimultaneously two complementary levels of representation: the continuing evolution of queues and discreetchanging traffic lights. These two levels are respectively articulated about Petri nets variable speed and discretetimed Petri nets.We chose, as well, for a new strategy to solve the problem of urban traffic control intervening in an appropriatemanner to the level of the signal lights. We sought to avoid first, congestion and the super saturation of queues,which must not exceed the optimum capacity of the intersection of routes studied and, second, to reduce theevacuation time of vehicles at the crossroads and especially waiting times for drivers.In this sense, a first algorithm is developed to calculate the lengths of queues, using a modeling simplificationapproach to a junction. To optimize the average waiting time and the total evacuation time are considered andapplied successfully by a heuristic control lights and a fixed control strategy and floating lights, following thedetermination of the duration of corresponding green light to the situation in real time intersectionWe plan to generalize the results of our work exploiting RDPH model to complex intersections for real situations of acrossroads network.

Nous proposons dans cette thèse plusieurs contributions relatives à la vérification quantitative des systèmes. Cette discipline vise à évaluer les propriétés fonctionnelles et les performances d'un système. Une telle vérification requiert deux ingrédients : un modèle formel de représentation d'un système et une logique temporelle pour exprimer la propriété considérée. L'évaluation est alors faite par une méthode statistique ou numérique. La complexité spatiale des méthodes numériques, proportionnelle à la taille de l'espace d'états, les rend impraticables si les systèmes présentent une combinatoire importante. La méthode de comparaison stochastique basée sur les chaînes de Markov censurées réduit la mémoire occupée en restreignant l'analyse à un sous-ensemble des états de la chaîne originale. Dans cette thèse nous fournissons de nouvelles bornes dépendant de l'information disponible relative à la chaîne. Nous introduisons une nouvelle logique temporelle quantitative appelée Hybrid Automata Stochastic Logic (HASL), pour la vérification des processus stochastiques à événements discrets (DESP).HASL emploie les automates linéaires hybrides (LHA) pour sélectionner des préfixes de chemins d'exécution d'un DESP. LHA permet de collecter des informations élaborées durant la génération des chemins, fournissant ainsi à l'utilisateur un moyen d'exprimer des mesures sophistiquées. HASL supporte donc des raisonnements temporels mixés avec une analyse à base de récompenses. Nous avons aussi développé COSMOS, un outil qui implémente la vérification statistique de formules HASL pour des réseaux de Petri stochastiques. Les ateliers flexibles (FMS) ont souvent été modélisés par des réseaux de Petri. Cependant le modélisateur doit avoir une bonne connaissance de ce formalisme. Afin de faciliter cette modélisation nous proposons une méthodologie de modélisation compositionnelle orientée vers les applications qui ne requiert aucune connaissance des réseaux de Petri. / We propose in this thesis several contributions related to the quantitative verification of systems. This discipline aims to evaluate functional and performance properties of a system. Such a verification requires two ingredients: a formal model to represent the system and a temporal logic to express the desired property. Then the evaluation is done with a statistical or numerical method. The spatial complexity of numerical methods which is proportional to the size of the state space of the model makes them impractical when the state space is very large. The method of stochastic comparison with censored Markov chains is one of the methods that reduces memory requirements by restricting the analysis to a subset of the states of the original Markov chain. In this thesis we provide new bounds that depend on the available information about the chain. We introduce a new quantitative temporal logic named Hybrid Automata Stochastic Logic (HASL), for the verification of discrete event stochastic processes (DESP). HASL employs Linear Hybrid Automata (LHA) to select prefixes of relevant execution paths of a DESP. LHA allows rather elaborate information to be collected on-the-fly during path selection, providing the user with a powerful mean to express sophisticated measures. In essence HASL provides a unifying verification framework where temporal reasoning is naturally blended with elaborate reward-based analysis. We have also developed COSMOS, a tool that implements statistical verification of HASL formulas over stochastic Petri nets. Flexible manufacturing systems (FMS) have often been modelized by Petri nets. However the modeler should have a good knowledge of this formalism. In order to facilitate such a modeling we propose a methodology of compositional modeling that is application oriented and does not require any knowledge of Petri nets by the modeler.

Cette thèse propose une approche de modélisation d'un processus adaptatif et itératif de collecte des données, ainsi qu'un outil de validation via des indicateurs d'efficacité opérationnelle de l'équipement. Une approche nommée "Tropos", établie grâce à la théorie de l'information, est donc développée pour modéliser et évaluer le processus de collecte de données. L'approche, originale, permet de synthétiser trois indicateurs qui caractérisent l'efficacité du processus de collecte : 1) utilité des données, 2) complexité du processus, 3) gain d'information par une activité élémentaire du processus. Un modèle original, basé sur les réseaux de Pétri stochastiques colorés couplé à la simulation Monte Carlo, est également proposé pour valider l'efficacité du processus de collecte de données. Ce modèle utilise comme données d'entrée les modèles des processus stochastiques de dégradation, de défaillance et de maintenance des composants de l'équipement. Les paramètres des modèles d'entrée sont supposés connus et extraits des données collectées. Les propriétés du modèle réseau de Pétri stochastique coloré permettent d'extraire les coupes minimales indispensables à l'évaluation de l'état et de l'efficacité opérationnelle de l'équipement. Elles permettent également de traiter les systèmes de structure k/n. L'effectivité de l'approche proposée est enfin illustrée sur un système de production d'énergie multi-source renouvelable, grâce à l'implémentation des algorithmes du modèle sous le logiciel Silab / This thesis proposes a modeling approach of an adaptive and iterative data collection process, and a validation tool via operational effectiveness features for equipment. An approach, named "Tropos", established based on the information theory, is developed to modeling and evaluating data collection processes. This is an original approach, which allows synthesizing three features that characterize the effectiveness of a data collection process: 1) data usefulness, 2) process complexity, 3) gain of information by a basic process activity. An original model, based on colored stochastic Petri nets coupled to the Monte Carlo simulation, has also been developed to validate the effectiveness of the data collection process. This model uses as input, stochastic process models of degradation, of failure and of maintenance of equipment components. The input parameters of the models are assumed to be known and obtained from the collected data. The properties of colored stochastic Petri net model are also used to derive the minimum cuts required to assess the equipment condition and operational effectiveness. These properties also allow to treating systems of k/n structures. The effectiveness of the proposed approach is finally illustrated on a multi-source renewable energy production system, by implementing the algorithms of the model under the Silab software environment

Aujourd'hui en France, l'évaluation de la performance de stratégies de sécurité à déployer pour mettre un bâtiment en sécurité vis-à-vis de l'incendie repose sur une étude d'ingénierie en sécurité incendie. Cette étude a pour objectif l'estimation du risque incendie pour différentes stratégies, et pour des scénarios d'incendies jugés pertinents. Pour parvenir à cette estimation, le Centre Scientifique et Technique du Bâtiment français (CSTB) a mis au point un outil de simulation appelé SCHEMA-SI. Cet outil utilise des réseaux de Petri prédicat-transition différentiels orientés objets et des simulations de Monte Carlo pour générer de multiples scénarios d'incendie. Ces scénarios sont ensuite utilisés pour évaluer le risque incendie encouru avec une stratégie de sécurité. La stratégie est alors jugée d'autant plus performante que le risque incendie est faible. L'objectif de la thèse consiste à contribuer au développement d'une méthode d'analyse de risque incendie utilisant l'outil de simulation SCHEMA-SI. La réflexion a débuté par la définition de ce que devrait être cette méthode. A ce stade, il est apparu que l'une des difficultés que la méthode doit surmonter est celle de la mise en donnés du problème par un groupe d'acteurs impliqués dans la sécurité incendie du bâtiment étudié. Pour résoudre cette difficulté, une méthode de modélisation spécifique a été construite. Cette méthode, baptisée ISI-Systema, repose sur deux fondements principaux : d'une part, un langage graphique de modélisation permettant au groupe d'acteurs de réfléchir à la mise en données du problème en s'appuyant sur une approche systémique ; d'autre part, une démarche de traduction des modèles graphiques obtenus avec le langage systémique en réseaux de Petri compatibles avec SCHEMA-SI.Enfin, une application pratique de cette méthode de modélisation est proposée. / Nowadays in France, building fire safety strategy performance analysis relies on a fire engineering study. This kind of study aims at calculating fire risk for several strategies and for fire scenarios judged as relevant. In order to achieve risk calculation, the French Scientific and technical Building Center (CSTB) has developed a simulation tool called SCHEMA-SI. This tool is based on object-oriented differentiai predicate-transition Petri nets and on Monte Carlo simulations and is built to generate a large number of fire scenarios. Obtained scenarios are hence used to evaluate fire risk related to the strategy to evaluate. The lower the fire risk is obtained, the more efficient the strategy is considered. This thesis aims at contributing to the development of a SCHEMA-SI based fire risk assessment method. This thesis starts by a definition of what this method should be. At this stage, it appears that one of the difficulties to overcome is the one of the problem definition by a group of fire safety concerned people. In arder to solve this difficulty, a modeling method has been developed. This method, so-called ISI-Systema, relies on two main basements: in on hand, on a graphic modeling language created to allow a group of people to think about the problem definition by using a systemic approach ; on the other hand, on a SCHEMA-SI compatible Petri net - graphic model translation procedure. At last, a case study is proposed.

Dans la première partie de cette thèse, nous présentons une implémentation du langage fp2 ayant pour modèle les réseaux de Petri. Fp2 est un langage de programmation parallèle base sur la réécriture de termes et les spécifications algébriques. Nous donnons une nouvelle sémantique a fp2, de la famille des sémantiques du vrai parallélisme, et prouvons la correction de cette sémantique par rapport a la sémantique interleaving du langage. Le modèle utilise, les réseaux de Petri, et la nouvelle sémantique donnée au langage permettent une représentation plus compacte de programmes complexes, évitant les problèmes d'explosion combinatoire rencontres avec les implémentations précédentes. Nous évaluons le gain de notre approche, et proposons plusieurs schémas d'interprétation du langage, bases sur cette nouvelle sémantique. La seconde partie de ce travail concerne la définition d'une nouvelle famille d'équivalences comportementales pour les réseaux de Petri. Alors que les équivalences proposées jusqu'alors sont définies entre les marquages, c'est-a-dire entre les états globaux du réseau, nous définissons une relation entre les places du réseau, reprenant une idée proposée par olderog. De nouvelles équivalences, les bisimulations de places, sont proposées a partir de cette définition. Un algorithme efficace (polynomial) permettant de calculer la plus grande bisimulation de places sur un réseau est propose. Nous montrons comment simplifier un réseau en le quotientant par cette plus grande bisimulation, obtenant ainsi un représentant canonique d'une classe d'équivalence de réseaux bisimilaires de places. L'étude de ces équivalences est ensuite étendue aux réseaux avec actions internes

La logique linéaire (LL) permet de prendre naturellement en compte la notion de ressource. Elle est ainsi très expressive : le plus petit fragment propositionnel est déjà NP-complet alors que le plus grand est indécidable car on peut y simuler les modèles de calculs usuels comme les machines à registres. La décidabilité du fragment multiplicatif exponentiel de LL (MELL) est un problème ouvert. Cette thèse établit la complétude de la sémantique des phases semi-linéaire pour le fragment de Horn de MELL. La prouvabilité dans ce dernier est équivalente à l'accessibilité dans les réseaux de Pétri. Ce résultat constitue une première étape vers l'éventuelle décidabilité de MELL (conjecture de Y.Lafont). Le chapitre suivant développe le codage du problème des circuits hamiltoniens où la notion de choix (qui est ici naturellement traduite par les connecteurs additifs) est gérée multiplicativement. Ce procédé pourrait être étendu à l'étude d'autres problèmes de théorie des graphes. On obtient ainsi une nouvelle preuve de la NP-complétude du fragment multiplicatif de la logique linéaire. C'est un travail réalisé en commun avec T.Krantz. Enfin, on donne un critère de correction quadratique pour les réseaux de preuves de la logique non-commutative de P.Ruet (qui contient la logique linéaire et la logique linéaire cyclique). Il permet de plus de traiter les réseaux de preuve avec coupures.

Le travail présenté dans le mémoire traite des problèmes liés au contrôle d'exécution des actions des robots mobiles autonomes. Une première partie présente l'architecture de contrôle globale et la compare à d'autres approches. On décrit les niveaux hiérarchiques qui la constituent et leurs rôles dans le fonctionnement du système. Le niveau inférieur, composé d'un ensemble de modules, rassemble les fonctions de perception, de modélisation et d'action du système. La seconde partie présente le niveau exécutif. L'exécutif doit suivre l'exécution des fonctions, résoudre les conflits entre modules, accomplir certaines actions réflexes et maintenir une information sur l'utilisation des ressources non partageables du robot. Il peut être vu comme un ensemble d'automates, qui interagissent et changent d'état selon les requêtes qui arrivent du niveau supérieur et les répliques qui proviennent des modules. La mise en oeuvre de l'exécutif utilise le système à base de règles KHEOPS. La compilation faite par KHEOPS permet, à partir d'un ensemble de variables d'entrée et de sortie et des règles qui les relient, d'obtenir un arbre de décision équivalent et de profondeur connue, ce qui garantit un temps d'exécution borné pour l'exécutif. La compilation permet aussi de garantir certaines propriétés logiques des automates mis en place. La troisième partie présente les relations entre le niveau fonctionnel (modules et exécutif) et la couche immédiatement supérieure, le niveau tache. Ce niveau est basé sur le système PRS, qui transforme des taches de haut niveau d'abstraction en procédures d'actions reconnues par le niveau fonctionnel et surveille leur exécution. Le mémoire présente une équivalence entre un sous-ensemble de PRS et les réseaux de Pétri colorés, ce qui permet de faire une vérification du niveau tache quand l'équivalence existe. Enfin, on présente quelques rés ultats de la mise en oeuvre expérimentale de ces travaux avec le robot Hilare 2.

Aujourd'hui, les ordinateurs et l'Internet sont partout dans le monde : dans chaque maison, domaine et plateforme. Dans ce contexte, le standard XML s'est établi comme un moyen insigne pour la représentation et l'échange efficaces des données. Les communications et les échanges d'informations entre utilisateurs, applications et systèmes d'information hétérogènes sont désormais réalisés moyennant XML afin de garantir l'interopérabilité des données. Le codage simple et robuste de XML, à base de données textuelles semi-structurées, a fait que ce standard a rapidement envahi les communications medias. Ces communications sont devenues inter-domaines, partant de l'informatique et s'intégrant dans les domaines médical, commercial, et social, etc. Par conséquent, et au vu du niveau croissant des données XML flottantes entre des utilisateurs non-experts (employés, scientifiques, etc.), que ce soit sur les messageries instantanées, réseaux sociaux, stockage de données ou autres, il devient incontournable de permettre aux utilisateurs non-experts de manipuler et contrôler leurs données (e.g., des parents qui souhaitent appliquer du contrôle parental sur les messageries instantanées de leur maison, un journaliste qui désire regrouper et filtrer des informations provenant de différents flux RSS, etc.). L'objectif principal de cette thèse est l'étude des manipulations des données XML par des utilisateurs non-experts. Quatre principales catégories ont été identifiées dans la littérature : i) les langages visuels orientés XML, ii) les Mashups, iii) les techniques de manipulation des données XML, et iv) les DFVPL (langages de programmation visuel à base de Dataflow), couvrant différentes pistes. Cependant, aucune d'entre elles ne fournit une solution complète. Dans ce travail de recherche, nous avons formellement défini un Framework de manipulation XML, intitulé XA2C (XML-oriented mAnipulAtion Compositions). XA2C représente un environnement de programmation visuel (e.g., Visual-Studio) pour un DFVPL orienté XML, intitulé XCDL (XML-oriented Composition Definition Language) qui constitue la contribution majeure de cette thèse. XCDL, basé sur les réseaux de Pétri colorés, permet aux non-experts de définir, d'arranger et de composer des opérations de manipulation orientées XML. Ces opérations peuvent être des simples sélections/projections de données, ainsi que des opérations plus complexes de modifications de données (insertion, suppression, tatouage, etc.). Le langage proposé traite les données XML à base de documents ou de fragments. En plus de la définition formelle (syntaxique et sémantique) du langage XCDL, XA2C introduit une architecture complète à base d'un compilateur et un environnement d'exécution dédiés. Afin de tester et d'évaluer notre approche théorique, nous avons développé un prototype, intitulé X-Man, avec un Framework d'évaluation pour les langages et outils visuels de programmation orientés XML. Une série d'études de cas et d'expérimentations a été réalisée afin d'évaluer la qualité d'usage de notre langage, et de le comparer aux solutions existantes. Les résultats obtenus soulignent la supériorité de note approche, notamment en termes de qualité d'interaction, de visualisation, et d'utilisation. Plusieurs pistes sont en cours d'exploration, telles que l'intégration des opérations plus complexes (opérateurs de contrôle, boucles, etc.), les compositions automatiques, et l'extension du langage pour gérer la spécificité des formats dérivés du standard XML (flux RSS, RDF, SMIL, etc.)

Considérons les systèmes à évènements discrets qui sont modélisables par des réseaux de Pétri du type "graphes d'évènements temporisés", Ils ont un comportement optimal (fonctionnement au plus tôt) qui peut-être calculé sans simulation par un système dynamique qui est linéaire dans l'algèbre des dïodes (max,+) ou (min,+). Le comportement asymptotique d'un tel système à évènements discrets est cyclique et les caractéristiques de ce cycle (période, délai, motif) sont analysables par un calcul de valeur propre sur la matrice de dynamique. À partir de cette formulation linéaire, une représentation externe (fonction de transfert) peut-être obtenue grâce à un calcul formel sur des séries à coefficients dans les dïodes, la fonction de transfert d'un tel système est rationnelle au sens des dïoides et est factorisable en une expression finie de polynômes.