Search

National audience; Multi-robot systems multiply in our everyday life, for example in service robotics or industrial or agricultural assistance. To make these systems stand-alone and safe, it is essential to embed modules to automatically manage failures, that is, detecting anomalies, evaluating possible causes and deciding on an appropriate response ( Retry, replace the action, replace a component, etc.).The thesis aims at developing generic tools to construct an automatic fault management module, to analyze this module and to validate its behavior. The first ambition is to model the multi-robot system, the reasoning for making a diagnosis and the required safety properties. The work will then focus on the algorithms to construct the fault management module and analyze it. Finally, the tools developed will be validated by being applied to different real and simulated multi-robot scenarios.; Les systèmes multi-robots se multiplient dans notre quotidien, par exemple dans la robotique de service ou dans l'assistance industrielle ou agricole. Pour rendre ces systèmes autonomes et sûrs, il est indispensable d'embarquer des modules pour gérer automatiquement les pannes, c'est-à-dire la détection d'anomalies, l'évaluation des causes possibles et la décision d'une réaction appropriée (réessayer, remplacer l'action, remplacer un composant, etc).La thèse vise à développer des outils génériques pour construire un module de gestion automatique des pannes, pour analyser ce module et pour valider son comportement. La première ambition est de modéliser le système multi-robots, le raisonnement pour émettre un diagnostic et les propriétés de sûreté requises. Le travail portera ensuite sur les algorithmes pour construire le module de gestion des pannes et l'analyser.Finalement, les outils développés seront validés par l'application à différents scénarios multi-robots réels et simulés.

The main objective of this thesis is to propose an approach to consider perturbations in the context of a production scheduling problem. The proposed approach emphasizes the importance of evaluating the performance of a scheduling in a disturbed environment. Production scheduling is an important and common problem in the world of industry and scientific research. In order to propose scheduling solutions, the suggested methods propose optimal scheduling to minimize or maximize a defined criterion. This objective has certainly been adopted for several years but no longer fully meets the dynamics of production workshops. Taking perturbations into account is therefore a major issue in the scheduling problem. To address this issue, after an introduction and state of the art, we propose, in the main body of the manuscript, the definition of the performance and appropriate approach to deal with the impact of perturbations in scheduling. Robustness is then identified as a suitable performance to assess this impact. Furthermore, specifying robustness allows to identify a formal framework to specify the different robustness problems that scheduling must face. To address the problem of scheduling robustness, we propose an evaluation process based on discrete-event system models. More precisely, stochastic timed automata and statistical model-checking are used to measure the robustness of a perturbed schedule. The evolution of production systems and their flexibility and agility constraints require that the evaluation approach must also be flexible and adaptable. The process proposed in this thesis allows not only its adaptation to several production workshop problems but also to take into account real decision situations in an industrial context. To illustrate the feasibility and applicability of this process, the UppAal SMC tool is used., L’objectif principal de cette thèse est de proposer une approche permettant de considérer les perturbations dans le cadre d’un problème d’ordonnancement de la production. L’approche proposée permet de mettre l’accent sur l’importance de l’évaluation de la performance d’un ordonnancement dans un cadre perturbé. L’ordonnancement de la production est un problème important et commun au monde de l’industrie et de la recherche scientifique. Dans le but de proposer des solutions d’ordonnancement, les méthodes proposées proposent des ordonnancements optimaux permettant de minimiser ou maximiser un critère défini. Cet objectif est certes adopté depuis plusieurs années mais ne répond plus tout à fait à la dynamique des ateliers de production. La prise en compte des perturbations est donc un enjeu majeur dans la problématique de l’ordonnancement. Pour répondre à cet enjeu, nous proposons, de définir la performance et l’approche à adopter pour traiter l’impact des perturbations sur l’ordonnancement. La robustesse est alors identifiée comme étant une performance adaptée pour évaluer cet impact. Plus encore, spécifier la robustesse permet d’identifier un cadre formel pour spécifier les différents problèmes de robustesse auxquels l’ordonnancement doit faire face. Pour traiter le problème de la robustesse d’un ordonnancement, nous proposons un processus d’évaluation basé sur les modèles de systèmes à événements discrets. Plus précisément, les automates temporisés stochastiques et le model checking statistique sont utilisés afin de mesurer la robustesse d’un ordonnancement perturbé. L’évolution des systèmes de production et leurs contraintes de flexibilité et d’agilité exige que l’approche d’évaluation soit également flexible et adaptable. Le processus proposé dans le cadre de cette thèse permet non seulement de s’adapter à plusieurs problèmes d’atelier de production mais également à prendre en compte des situations de décisions réelles dans un contexte industriel.

Collisions and deadlocks are unwanted situations in many transport applications such as railway systems. Control synthesis methods can assure that a closed-loop system cannot lead to deadlock situations. Methods issued from the historical approach of Ramadge and Wonham allow dealing with this issue but encounter the problem of combinatorial explosion, that prevents its use on large systems. In the case of deadlock avoidance, the majority of approaches are based on the assumption of total controllability and observability. However, this assumption is not verified in all kinds of systems. This thesis proposes control synthesis methods that do not suffer from the combinatorial explosion. These methods are based on the formalism of Petri nets and uniquely concern classes of resource allocation systems. In a way to not resort to state exploration, these methods identify deadlock situations by resolving a mixed integer programming problem. These methods are then used for routing trains in a railway node. A systematic modeling approach of the trains' circulations in a railway node is developed. The model obtained is a Petri net for resources allocation system. To avoid collisions and deadlocks in the model, a control synthesis method, based on the theoretical background developed, is proposed; Les collisions et les blocages sont des situations que l'on souhaite éviter dans beaucoup d'application de transport. Les méthodes de synthèse de contrôleurs peuvent garantir qu'un système en boucle fermé ne puisse pas atteindre de telles situations. Les méthodes issues de l'approche historique de Ramadge et Wonham permettent de traiter cette problématique mais font face à l'explosion combinatoire, qui empêche leurs applications sur les systèmes de grandes tailles. Dans le cadre de l'évitement des blocages, la grande majorité des approches font l'hypothèse que le système est sous contrôlabilité et observabilité totales. Cependant, cette hypothèse n'est pas vérifiée pour tous les systèmes. Cette thèse propose des méthodes de synthèses de contrôleurs applicables sur des systèmes sous observabilité et contrôlabilité partielles sans souffrir de l'explosion combinatoire. Ces méthodes se basent sur le formalisme des Réseaux de Petri, et concernent uniquement des classes pour la modélisation de systèmes d'allocation de ressources. Pour ne pas avoir recours à l'exploration des états, ces méthodes identifient les situations de blocages grâce à la résolution d'un problème d'optimisation mixte en nombres entiers. Ces méthodes sont par la suite utilisées pour le routage des trains dans un nœud ferroviaire. Une méthode systématique de modélisation de la circulation des trains dans un nœud ferroviaire est proposée. Le modèle ainsi obtenu est un Réseau de Petri pour la modélisation des systèmes d'allocation de ressources. Pour éviter les collisions et les blocages au seins de ce modèle, une méthode de synthèse reposant sur les apports théoriques de cette thèse est appliquée

Collisions and deadlocks are unwanted situations in many transport applications such as railway systems. Control synthesis methods can assure that a closed-loop system cannot lead to deadlock situations. Methods issued from the historical approach of Ramadge and Wonham allow dealing with this issue but encounter the problem of combinatorial explosion, that prevents its use on large systems. In the case of deadlock avoidance, the majority of approaches are based on the assumption of total controllability and observability. However, this assumption is not verified in all kinds of systems. This thesis proposes control synthesis methods that do not suffer from the combinatorial explosion. These methods are based on the formalism of Petri nets and uniquely concern classes of resource allocation systems. In a way to not resort to state exploration, these methods identify deadlock situations by resolving a mixed integer programming problem. These methods are then used for routing trains in a railway node. A systematic modeling approach of the trains' circulations in a railway node is developed. The model obtained is a Petri net for resources allocation system. To avoid collisions and deadlocks in the model, a control synthesis method, based on the theoretical background developed, is proposed; Les collisions et les blocages sont des situations que l'on souhaite éviter dans beaucoup d'application de transport. Les méthodes de synthèse de contrôleurs peuvent garantir qu'un système en boucle fermé ne puisse pas atteindre de telles situations. Les méthodes issues de l'approche historique de Ramadge et Wonham permettent de traiter cette problématique mais font face à l'explosion combinatoire, qui empêche leurs applications sur les systèmes de grandes tailles. Dans le cadre de l'évitement des blocages, la grande majorité des approches font l'hypothèse que le système est sous contrôlabilité et observabilité totales. Cependant, cette hypothèse n'est pas vérifiée pour tous les systèmes. Cette thèse propose des méthodes de synthèses de contrôleurs applicables sur des systèmes sous observabilité et contrôlabilité partielles sans souffrir de l'explosion combinatoire. Ces méthodes se basent sur le formalisme des Réseaux de Petri, et concernent uniquement des classes pour la modélisation de systèmes d'allocation de ressources. Pour ne pas avoir recours à l'exploration des états, ces méthodes identifient les situations de blocages grâce à la résolution d'un problème d'optimisation mixte en nombres entiers. Ces méthodes sont par la suite utilisées pour le routage des trains dans un nœud ferroviaire. Une méthode systématique de modélisation de la circulation des trains dans un nœud ferroviaire est proposée. Le modèle ainsi obtenu est un Réseau de Petri pour la modélisation des systèmes d'allocation de ressources. Pour éviter les collisions et les blocages au seins de ce modèle, une méthode de synthèse reposant sur les apports théoriques de cette thèse est appliquée

International audience; Ce papier présente une étude relative au développement de systèmes de production intelligents dans le contexte de l'industrie manufacturière. Nous montrons que de tels systèmes doivent être agile, c'est-à-dire capable de s'adapter rapidement à des contextes changeant comme une production particulière ou une panne. Dans cette étude nous modélisons le système de commande de ces systèmes par une approche en couches et générique. Nous distinguons plusieurs classes de modèles permettant de gérer chacun différentes catégories de flexibilité. L'objectif essentiel de l'étude est de fournir une méthode rigoureuse et systématique permettant de modéliser et de vérifier de manière efficace ce type de système.

National audience; Chronicles are temporal patterns well-suited for an abstract representation of complex dynamic systems. Chronicle recognition algorithms allow the identification of chronicles in an on-line stream of data to be done and take adequate action in an quick and efficient manner. Chronicles are used in a vast array of applications such as medical field, internet networks, or industrial applications. Nevertheless, designing chronicles is not an easy task due to the sophistication and the increase of data generation capacity of modern systems. The chronicle discovery process try and tackle this problem by an automatic design of chronicles from data directly generated by the studied system. In this thesis, an innovative approach to the problem of chronicle discovery is introduced. This new approach lies of the identification of elementary chronicles and a reconstitution of complex chronicles from them. The algorithm introduced, called CDIRe (Chronicle Discovery by Identification and Reconstitution), allows the discovery of chronicles with few knowledge from the underlying system to be done.; Les chroniques sont des schémas temporels particulièrement bien adaptés pour une représentation de modèles complexes et dynamiques. Des algorithmes de reconnaissance de chroniques permettent d'identifier des chroniques dans un flux de données en ligne et de prendre des actions adéquates de manière rapide et efficace. Les chroniques peuvent être utilisées dans des domaines d'applications divers, tels que le domaine médical, les réseaux internets, ou encore des applications industrielles. Néanmoins, la construction des chroniques n'est pas chose aisée en raison de la complexification et de l'augmentation des capacités de génération de données des systèmes modernes. Le processus de découverte de chroniques a pour objectif de répondre à cette problématique en construisant de manière automatique des chroniques à partir des données directement générées par le système étudié. Dans ce mémoire de thèse, une approche innovante à la problématique de la découverte de chroniques est abordée. Cette nouvelle approche repose sur une identification de chroniques élémentaires et une reconstitution de chroniques plus complexes à partir de celles-ci. L'algorithme proposé, appelé CDIRe (Chronicle Discovery by Identification and Reconstitution), permet de découvrir des chroniques avec peu de connaissance sur le système sous-jacent.

The interest of this research project is focused on the design of a reconfigurable control based on temporal models for Complex Discrete Event Systems. The aim is to allow the pursuit of the system tasks in spite of faults that may impede the normal behavior of this system. With an adaptation of the online control which is developed offline. This reconfigurable control is necessarily based on knowledge of the services lost due to the occurrence of a symptom of failure. This knowledge is usually outcome of the diagnosis function which aims to locate and identify the cause of this failure., L'intérêt de ce projet de recherche se porte sur la conception d'une commande reconfigurable à base des modèles temporels pour la conduite des Systèmes à Événements Discrets Complexes. L'objectif est de permettre la poursuite des tâches du système en dépit des fautes pouvant entraver le bon fonctionnement de ce dernier. Tout en adaptant en ligne la commande élaborée hors ligne. Cette commande reconfigurable se base nécessairement sur une connaissance des services perdus suite à l'occurrence d'un symptôme de la défaillance. Cette connaissance est généralement issue de la fonction diagnostic qui a pour but de localiser puis d'identifier la cause de la défaillance.

Alarm systems play an important role for the safe and efficient operation of modern industrial plants. However, in most of industrial alarm systems, alarm flows cannot always be correctly managed by the operators as they often turn into alarm floods, sequences of numerous alarms occurring in a short period of time. To reduce the alarm flows, this report focuses on detection of redundant alarms that could be removed. This objective is met by, first, looking for frequent adjacency in the alarm log. To identify them, the frequent pattern mining algorithm AprioriAll is adapted. Another way to find potentially redundant alarms is to look for systematic predecessors. To discover them, dominations and mutual dependencies contained in the alarm log are identified. To ease this analysis, the discovered relations are depicted in the form of Petri nets.Both those methods are then tested against an industrial alarm log made available by General Electric. The results show that both methods allow a reduction of the alarm flow, with the biggest reduction being during alarm floods.; Les systèmes d'alarmes jouent un rôle critique dans la bonne exploitation des installations industrielles modernes. Cependant, dans la plupart de ces systèmes, les alarmes ne sont pas toujours traitées correctement par les opérateurs car il y a régulièrement beaucoup trop d’alarmes à gérer, notamment lors des avalanches d’alarmes. Pour réduire le flux d'alarmes, notre approche consiste à détecter des redondances entre alarmes qui pourraient être supprimées. Pour atteindre cet objectif, nous recherchons dans un premier temps les adjacences fréquentes entre les alarmes contenues dans un historique. Ceci est réalisé en adaptant l’algorithme de recherche de motifs fréquents AprioriAll. Nous explorons également une seconde méthode consistant à trouver des précédences systématiques. Pour les découvrir, nous identifions les relations de domination et de mutuelle dépendance contenues dans l’historique des alarmes. Pour faciliter l’analyse experte, les relations découvertes sont traduites sous la forme d’un réseau de Pétri.Ces deux méthodes sont ensuite confrontées à un historique d’alarmes industriel fourni par General Electric. Les résultats obtenus montrent que nos deux méthodes permettent une réduction globale du flux d'alarmes qui est plus importante durant les avalanches.

Alarm systems play an important role for the safe and efficient operation of modern industrial plants. However, in most of industrial alarm systems, alarm flows cannot always be correctly managed by the operators as they often turn into alarm floods, sequences of numerous alarms occurring in a short period of time. To reduce the alarm flows, this report focuses on detection of redundant alarms that could be removed. This objective is met by, first, looking for frequent adjacency in the alarm log. To identify them, the frequent pattern mining algorithm AprioriAll is adapted. Another way to find potentially redundant alarms is to look for systematic predecessors. To discover them, dominations and mutual dependencies contained in the alarm log are identified. To ease this analysis, the discovered relations are depicted in the form of Petri nets.Both those methods are then tested against an industrial alarm log made available by General Electric. The results show that both methods allow a reduction of the alarm flow, with the biggest reduction being during alarm floods.; Les systèmes d'alarmes jouent un rôle critique dans la bonne exploitation des installations industrielles modernes. Cependant, dans la plupart de ces systèmes, les alarmes ne sont pas toujours traitées correctement par les opérateurs car il y a régulièrement beaucoup trop d’alarmes à gérer, notamment lors des avalanches d’alarmes. Pour réduire le flux d'alarmes, notre approche consiste à détecter des redondances entre alarmes qui pourraient être supprimées. Pour atteindre cet objectif, nous recherchons dans un premier temps les adjacences fréquentes entre les alarmes contenues dans un historique. Ceci est réalisé en adaptant l’algorithme de recherche de motifs fréquents AprioriAll. Nous explorons également une seconde méthode consistant à trouver des précédences systématiques. Pour les découvrir, nous identifions les relations de domination et de mutuelle dépendance contenues dans l’historique des alarmes. Pour faciliter l’analyse experte, les relations découvertes sont traduites sous la forme d’un réseau de Pétri.Ces deux méthodes sont ensuite confrontées à un historique d’alarmes industriel fourni par General Electric. Les résultats obtenus montrent que nos deux méthodes permettent une réduction globale du flux d'alarmes qui est plus importante durant les avalanches.

This PhD thesis deals with the fault diagnosis of Discrete Event Systems (DES) for which the occurrence of events is constrained by temporal specifications. The domain of application is large and varied ranging from manufacturing systems to transportation systems, communication networks and information systems. The increasing complexity of these systems requires the development of effective and efficient monitoring methods to ensure their security, availability and the maintenance of their properties over the time. For that purpose, Partially Observed Stochastic Timed Petri Nets (POSTPN) are used to model the system and the different faults that may affect it. The study is particularly concerned with faults that result after the violation of temporal constraints. Our main contribution in this thesis is the relevant exploitation of the timed information for the fault diagnosis. In fact, a better use of these temporal informations allow to discern with precision the different behaviors that are consistent with the measurements. In addition, the probability of faults occurrence is evaluated according to the dates of collected measurements. Two approaches are developed : the first one is used for single faults and the second one for slow drifts in cyclical systems.; Cette thèse porte sur le diagnostic des défauts dans des Systèmes à Evènements Discrets (SED) pour lesquels l’occurrence des événements est soumise à des contraintes temporelles. Les domaines d’application potentiels sont nombreux et variés allant de la production manufacturière aux systèmes de transport en passant par les réseaux de communication et les systèmes d’information. La complexité croissante de ces systèmes nécessite l’élaboration de méthodes de surveillance de plus en plus efficaces et performantes pour garantir leur sécurité, leur disponibilité ainsi que le maintien de leurs propriétés dans le temps. Les réseaux de Petri Stochastiques Temporisés Partiellement Observés (RdPSTPO) sont utilisés pour modéliser le système ainsi que les défauts qui peuvent l’affecter. L’étude concerne particulièrement les défauts qui se traduisent par la violation des contraintes temporelles. Une exploitation pertinente des informations temporelles, en vue du diagnostic, constitue la contribution majeure de la thèse. En effet, une meilleure utilisation de ces informations permet de discerner avec précision les différents comportements qui expliquent les mesures. De plus, la probabilité d’occurrence des défauts est calculée en fonction des dates des mesures collectées. Deux approches sont développées : la première est dédiée aux défauts ponctuels et la seconde aux dérives lentes dans les systèmes cycliques.

Precision agriculture (PA) has grown strongly in recent decades with advances in locating methods and sensor and remote sensing technologies. The principle of the PA is to seek and implement the Right action at the Right time and in the Right place ("3R"), with the objective of improving the efficiency of agriculture according to the criteria of agriculture sustainable. We consider in this thesis the evaluation of the feasibility of agricultural operations with respect to the criteria set in a PA recommendation, using formal modeling and verification techniques.To model and verify these operations, a representation of temporal and spatial dynamics is necessary. The model-checking of timed automata systems with requests in temporal tree logic answers these needs. The spatial positions can be represented in an ad-hoc manner within the framework of these formalisms. Three examples of agricultural operations are considered in this thesis. The first relates to the computing of an optimal sequence of commands for a precision spraying in viticulture. The second concerns selective harvesting in viticulture. The last one is related to the verification of an agricultural robotics mission. We study in these examples the reachability of a target state for the operation, or the reachability with an optimal cost criterion.To overcome the combinatorial explosion problem encountered in the treated cases, a decomposition methodology for reachability model-checking has been developed. The experimental results with and without decomposition are presented for the 3 examples of operation studied. The decomposition methodology was applied to 2 of the 3 examples and the experimental results indicate its efficient.; L'agriculture de précision (AP) s'est fortement développée au cours des dernières décennies avec les progrès des technologies de localisation, des capteurs et des techniques de télédétection. Le principe de l'AP est de rechercher et mettre en oeuvre la Bonne action au Bon moment et au Bon endroit ("3B"), avec l'objectif d'améliorer l'efficience de l'agriculture suivant les critères d'une agriculture durable. Nous considérons dans cette thèse l'évaluation de la faisabilité d'opérations agricoles vis à vis de critères relevant de l'AP, en faisant appel à des techniques de modélisation et de vérification formelles.Pour modéliser et vérifier ces opérations, une représentation des dynamiques temporelles et spatiales est nécessaire. Le model-checking de systèmes d'automates temporisés avec des requêtes dans une logique temporelle arborescente répond à ces besoins, les positions spatiales pouvant être représentées de façon ad-hoc dans le cadre de ces formalismes. Trois exemples d'opérations agricoles sont considérés dans ce mémoire. La première est relative au calcul d'une séquence optimale de commandes pour une pulvérisation de précision en viticulture. La seconde concerne la récolte sélective en viticulture. La dernière est relative à la vérification d'une mission de robotique agricole. Nous étudions dans ces exemples l'atteignabilité d'un état cible pour l'opération, ou l'atteignabilité avec un critère de coût optimal.Pour pallier au problème d'explosion combinatoire rencontré dans les cas traités, une méthodologie de décomposition pour le model-checking d'atteignabilité a été développée. Les résultats expérimentaux avec et sans décomposition sont présentés pour les 3 exemples d'opération étudiés. La technique de décomposition est appliquée sur 2 des 3 exemples et les résultats expérimentaux montrent son efficacité.

Precision agriculture (PA) has grown strongly in recent decades with advances in locating methods and sensor and remote sensing technologies. The principle of the PA is to seek and implement the Right action at the Right time and in the Right place ("3R"), with the objective of improving the efficiency of agriculture according to the criteria of agriculture sustainable. We consider in this thesis the evaluation of the feasibility of agricultural operations with respect to the criteria set in a PA recommendation, using formal modeling and verification techniques.To model and verify these operations, a representation of temporal and spatial dynamics is necessary. The model-checking of timed automata systems with requests in temporal tree logic answers these needs. The spatial positions can be represented in an ad-hoc manner within the framework of these formalisms. Three examples of agricultural operations are considered in this thesis. The first relates to the computing of an optimal sequence of commands for a precision spraying in viticulture. The second concerns selective harvesting in viticulture. The last one is related to the verification of an agricultural robotics mission. We study in these examples the reachability of a target state for the operation, or the reachability with an optimal cost criterion.To overcome the combinatorial explosion problem encountered in the treated cases, a decomposition methodology for reachability model-checking has been developed. The experimental results with and without decomposition are presented for the 3 examples of operation studied. The decomposition methodology was applied to 2 of the 3 examples and the experimental results indicate its efficient.; L'agriculture de précision (AP) s'est fortement développée au cours des dernières décennies avec les progrès des technologies de localisation, des capteurs et des techniques de télédétection. Le principe de l'AP est de rechercher et mettre en oeuvre la Bonne action au Bon moment et au Bon endroit ("3B"), avec l'objectif d'améliorer l'efficience de l'agriculture suivant les critères d'une agriculture durable. Nous considérons dans cette thèse l'évaluation de la faisabilité d'opérations agricoles vis à vis de critères relevant de l'AP, en faisant appel à des techniques de modélisation et de vérification formelles.Pour modéliser et vérifier ces opérations, une représentation des dynamiques temporelles et spatiales est nécessaire. Le model-checking de systèmes d'automates temporisés avec des requêtes dans une logique temporelle arborescente répond à ces besoins, les positions spatiales pouvant être représentées de façon ad-hoc dans le cadre de ces formalismes. Trois exemples d'opérations agricoles sont considérés dans ce mémoire. La première est relative au calcul d'une séquence optimale de commandes pour une pulvérisation de précision en viticulture. La seconde concerne la récolte sélective en viticulture. La dernière est relative à la vérification d'une mission de robotique agricole. Nous étudions dans ces exemples l'atteignabilité d'un état cible pour l'opération, ou l'atteignabilité avec un critère de coût optimal.Pour pallier au problème d'explosion combinatoire rencontré dans les cas traités, une méthodologie de décomposition pour le model-checking d'atteignabilité a été développée. Les résultats expérimentaux avec et sans décomposition sont présentés pour les 3 exemples d'opération étudiés. La technique de décomposition est appliquée sur 2 des 3 exemples et les résultats expérimentaux montrent son efficacité.

Several formal methods of supervisory control of discrete events systems (DES), based on Petri nets (PN) have been developed. However, they are partially structural because of the need to construct the marking graph, which is an automaton, to determine the states forbidden by the specification. Some of those methods are limited to a particular class of Petri nets. Our work focused on the labeled Petri nets (LPN), which offers a better structure for defining the languages and automata. Among the based methods based on Petri nets, the invariant place method (simple and efficient) is the most used, although it does not guarantee in the general an optimal solution. In order to overcome this problem, we have developed a completely structural method, without construction of the marking graph for ordinary labeled Petri nets. It consists in determining in a way structural, admissible constraints for the invariant method place. It is based on the structural condition of controllability of closed loop SED LPN states, got by synchronous product of the process and specification LPN. In addition, we have proved that the structural condition of controllability, defined by the marking condition of entrance places of an uncontrollable synchronous transition, is equivalent to the condition of controllability defined by the languages of the LPN. This condition defines the equation of a separator hyperplan which ensures separation of the admissible states from the forbidden states in the SED. Constraints derived from hyperplane separator are admissible and can be simplified systematically. They provide a one-to-one link between the theory of supervisory control of Ramadge and Wonham and the calculation of maximum permissive controller by the invariant place method. Although for some complex structures (great scale), the maximum permissive solution cannot be guarantee directly; our approach gave the optimal controller in the real case studies considered., Plusieurs méthodes formelles de commande par supervision des systèmes à événements discrets (SED) basées sur les réseaux de Petri (RdP) ont été développées. Cependant, elles sont partiellement structurelles à cause de la nécessité de construire le graphe de marquage, qui est un automate, pour déterminer les états interdits par la spécification. Certaines de ces méthodes sont limitées à une classe particulière de RdP. Notre travail s'est focalisé en particulier sur le RdP synchronisé (RdPS), qui offre une meilleure structure pour définir les langages et les automates. Parmi les méthodes basées sur les RdP, la méthode des invariants (simple et efficace) est la plus utilisée bien qu’elle ne garantisse pas en général une solution de contrôle optimale. Pour pallier ce problème, nous avons développé une méthode complètement structurelle, sans construction du graphe de marquage, pour les RdPS ordinaires ou généralisés. Elle consiste à déterminer de manière structurelle les contraintes admissibles pour la méthode des invariants. Elle est basée sur la condition de contrôlabilité structurelle des états du RdPS du SED en boucle fermée, obtenu par produit synchrone des RdPS du procédé et de la spécification. En outre, nous avons prouvé que la condition de contrôlabilité structurelle, définie par la condition de marquage des places d’entrée d’une transition synchrone incontrôlable, est équivalente à la condition de contrôlabilité définie par les langages du RdPS. Cette condition définit l’équation d’un hyperplan séparateur qui assure la séparation des états admissibles des états interdits dans le SED. Les contraintes dérivées de d’hyperplan séparateur sont admissibles et peuvent être simplifiées systématiquement. Elles permettent de faire un lien biunivoque entre la théorie de commande par supervision de Ramadge et Wonham et la méthode des invariants pour le calcul d’un contrôleur optimal au sent maximal permissif. Même si pour certaines structures très complexes (à grande échelle), la solution maximale permissive ne peut être garantie directement, notre approche a donné le contrôleur optimal dans les études de cas réels considérés.

This PhD thesis deals with the fault diagnosis of Discrete Event Systems (DES) for which the occurrence of events is constrained by temporal specifications. The domain of application is large and varied ranging from manufacturing systems to transportation systems, communication networks and information systems. The increasing complexity of these systems requires the development of effective and efficient monitoring methods to ensure their security, availability and the maintenance of their properties over the time. For that purpose, Partially Observed Stochastic Timed Petri Nets (POSTPN) are used to model the system and the different faults that may affect it. The study is particularly concerned with faults that result after the violation of temporal constraints. Our main contribution in this thesis is the relevant exploitation of the timed information for the fault diagnosis. In fact, a better use of these temporal informations allow to discern with precision the different behaviors that are consistent with the measurements. In addition, the probability of faults occurrence is evaluated according to the dates of collected measurements. Two approaches are developed : the first one is used for single faults and the second one for slow drifts in cyclical systems., Cette thèse porte sur le diagnostic des défauts dans des Systèmes à Evènements Discrets (SED) pour lesquels l’occurrence des événements est soumise à des contraintes temporelles. Les domaines d’application potentiels sont nombreux et variés allant de la production manufacturière aux systèmes de transport en passant par les réseaux de communication et les systèmes d’information. La complexité croissante de ces systèmes nécessite l’élaboration de méthodes de surveillance de plus en plus efficaces et performantes pour garantir leur sécurité, leur disponibilité ainsi que le maintien de leurs propriétés dans le temps. Les réseaux de Petri Stochastiques Temporisés Partiellement Observés (RdPSTPO) sont utilisés pour modéliser le système ainsi que les défauts qui peuvent l’affecter. L’étude concerne particulièrement les défauts qui se traduisent par la violation des contraintes temporelles. Une exploitation pertinente des informations temporelles, en vue du diagnostic, constitue la contribution majeure de la thèse. En effet, une meilleure utilisation de ces informations permet de discerner avec précision les différents comportements qui expliquent les mesures. De plus, la probabilité d’occurrence des défauts est calculée en fonction des dates des mesures collectées. Deux approches sont développées : la première est dédiée aux défauts ponctuels et la seconde aux dérives lentes dans les systèmes cycliques.

Automated Production Systems (APS) represent an important class of industrial systems.They have become complex and susceptible to malfunctions, with significant negativeconsequences on productivity, production quality and security of property andpeople. The main challenge when using such systems is to implement systemic assistanceor diagnosis approaches in order to ensure their operating safety. Within this framework,we focus, in this thesis, on the online diagnosis of the APS equipped with sensors andactuators emitting binary signals. These systems can be considered as ‘Discrete EventSystems’ (DES).The effectiveness of an approach for diagnosing such systems is measured through gooddetection rate, isolation accuracy, false alarms number and the method implementationcomplexity. The objective of this work is, thus, to propose intelligent diagnosis solutionssatisfying the mentioned criteria without complete knowledge about the system’s internalfunctioning. The solutions, whose implementation is not expensive, are able to updatethemselves in real time in order to improve their performance.The introduced approach is based on a reasoning and learning methodology derivedfrom ‘Artificial Intelligence’ (AI) which is the ‘Case Based Reasoning’ (CBR). The originalityof our research work is observed in the following 4 aspects : (1) the developedapproach uses the CBR for the diagnosis of the APS with DES dynamics, (2) it suggestsa case representation format inspired by the ‘Causal Temporal Signatures’ (CTS) whichis able to adapt to the dynamic aspect of the systems to be monitored, (3) it exploitsdata acquired from a digital twin after its emulation in both normal and faulty modesto build an empirical knowledge called ’cases’ and finally (4) it presents a reasoning andlearning phase that allows not only the online diagnosis of the monitored system, but alsothe updating of the case base following the appearance of the new unknown behaviors., Les systèmes automatisés de production (SAP) représentent une classe importante desystèmes industriels qui sont devenus complexes et sensibles aux dysfonctionnements avecdes conséquences importantes sur la productivité, la qualité de production et la sécuritédes biens et des personnes. Un défi majeur est de mettre en oeuvre des approches systématiquesd’aide ou de diagnostic afin de garantir la sûreté de fonctionnement. Cette thèses’intéresse donc au diagnostic en ligne des comportements indésirables des SAP ayant descapteurs et des actionneurs délivrant des signaux binaires et dont la dynamique correspondà celle des systèmes à évènements discrets (SED).L’efficacité d’une approche de diagnostic au service de ce type de systèmes se mesure àtravers le taux de bonne détection de fautes, la précision d’isolation, le nombre de faussesalarmes et la complexité de mise en oeuvre de l’approche. L’objectif de ce travail est doncde concevoir des solutions de diagnostic intelligentes qui satisfont les critères mentionnéssans requérir la connaissance complète du fonctionnement interne du système, capablesde se mettre à jour en temps réel pour améliorer les performances et ayant un faible coûtde mise en oeuvre.L’approche proposée dans cette thèse est basée sur le Raisonnement à Partir de Cas(RàPC) qui est à la fois une méthodologie de raisonnement par analogie et une méthodologied’apprentissage issue du domaine de l’intelligence artificielle. L’originalité des travauxréside en finalité dans les quatre items suivants : (1) l’approche proposée utilise le RàPCpour le diagnostic des SAP ayant une dynamique de type SED, (2) elle propose un formatde représentation de cas inspiré du formalisme Signatures Temporelles Causales quis’adapte à l’aspect dynamique des systèmes à surveiller, (3) elle introduit une phase quicouplent simulation et mise en forme de données pour la transformation des données issuesdu système simulé après son émulation en mode normal et défaillant, et (4) elle présenteune phase de raisonnement et d’apprentissage qui permet non seulement le diagnostic enligne du système surveillé mais aussi la mise à jour de la base de cas suite à l’apparitionde nouveaux comportements inconnus.

Automated Production Systems (APS) represent an important class of industrial systems.They have become complex and susceptible to malfunctions, with significant negativeconsequences on productivity, production quality and security of property andpeople. The main challenge when using such systems is to implement systemic assistanceor diagnosis approaches in order to ensure their operating safety. Within this framework,we focus, in this thesis, on the online diagnosis of the APS equipped with sensors andactuators emitting binary signals. These systems can be considered as ‘Discrete EventSystems’ (DES).The effectiveness of an approach for diagnosing such systems is measured through gooddetection rate, isolation accuracy, false alarms number and the method implementationcomplexity. The objective of this work is, thus, to propose intelligent diagnosis solutionssatisfying the mentioned criteria without complete knowledge about the system’s internalfunctioning. The solutions, whose implementation is not expensive, are able to updatethemselves in real time in order to improve their performance.The introduced approach is based on a reasoning and learning methodology derivedfrom ‘Artificial Intelligence’ (AI) which is the ‘Case Based Reasoning’ (CBR). The originalityof our research work is observed in the following 4 aspects : (1) the developedapproach uses the CBR for the diagnosis of the APS with DES dynamics, (2) it suggestsa case representation format inspired by the ‘Causal Temporal Signatures’ (CTS) whichis able to adapt to the dynamic aspect of the systems to be monitored, (3) it exploitsdata acquired from a digital twin after its emulation in both normal and faulty modesto build an empirical knowledge called ’cases’ and finally (4) it presents a reasoning andlearning phase that allows not only the online diagnosis of the monitored system, but alsothe updating of the case base following the appearance of the new unknown behaviors., Les systèmes automatisés de production (SAP) représentent une classe importante desystèmes industriels qui sont devenus complexes et sensibles aux dysfonctionnements avecdes conséquences importantes sur la productivité, la qualité de production et la sécuritédes biens et des personnes. Un défi majeur est de mettre en oeuvre des approches systématiquesd’aide ou de diagnostic afin de garantir la sûreté de fonctionnement. Cette thèses’intéresse donc au diagnostic en ligne des comportements indésirables des SAP ayant descapteurs et des actionneurs délivrant des signaux binaires et dont la dynamique correspondà celle des systèmes à évènements discrets (SED).L’efficacité d’une approche de diagnostic au service de ce type de systèmes se mesure àtravers le taux de bonne détection de fautes, la précision d’isolation, le nombre de faussesalarmes et la complexité de mise en oeuvre de l’approche. L’objectif de ce travail est doncde concevoir des solutions de diagnostic intelligentes qui satisfont les critères mentionnéssans requérir la connaissance complète du fonctionnement interne du système, capablesde se mettre à jour en temps réel pour améliorer les performances et ayant un faible coûtde mise en oeuvre.L’approche proposée dans cette thèse est basée sur le Raisonnement à Partir de Cas(RàPC) qui est à la fois une méthodologie de raisonnement par analogie et une méthodologied’apprentissage issue du domaine de l’intelligence artificielle. L’originalité des travauxréside en finalité dans les quatre items suivants : (1) l’approche proposée utilise le RàPCpour le diagnostic des SAP ayant une dynamique de type SED, (2) elle propose un formatde représentation de cas inspiré du formalisme Signatures Temporelles Causales quis’adapte à l’aspect dynamique des systèmes à surveiller, (3) elle introduit une phase quicouplent simulation et mise en forme de données pour la transformation des données issuesdu système simulé après son émulation en mode normal et défaillant, et (4) elle présenteune phase de raisonnement et d’apprentissage qui permet non seulement le diagnostic enligne du système surveillé mais aussi la mise à jour de la base de cas suite à l’apparitionde nouveaux comportements inconnus.

Industrial Control Systems (ICSs) are infrastructures composed by several industrial devices connected to a network and used to control a physical system. They control electrical power grid (Smart Grid), production systems (e.g. chemical and manufacturing industries), transport (e.g. trains, aircrafts and autonomous vehicles), health and weapon systems. Designed to ensure productivity and respect safety in a non-malicious environment, the ICSs are, since the 21st century, increasingly vulnerable to attacks (e.g. Stuxnet, Industroyer, Triton) especially with the emergence of the industry 4.0. Several studies contributed to secure the ICS with approaches from the security field (e.g. cryptography, IDS) which do not take into account the behavior of the physical system and therefore the consequences of the malicious act. Thus, a security approach limited exclusively to the analysis of information exchanged by industrial network is not sufficient. Our approach creates a paradigm shift in detection mechanisms by integrating the behavioral modeling of the cyber-physical system.This thesis proposes detection mechanisms of attacks by locating detection closer to physical system. They analyze the data exchanged between the control system and the physical system, and filter the exchanges through deterministic models that represent the behavior of the physical system controlled by control laws. For this purpose, a design methodology has been proposed in which all actions are identified in order to instantly detect brutal attacks. To deal with other attacks, especially the more sneaky, such as sequential attacks, we propose a complementary detection strategy to estimate the occurrence of an attack before its consequences are destructive. To this end, we have developed the concepts of distance of a state identified as critical to which we have added a second mechanism called trajectory which leads to a temporal notion that characterize an intention to harm.As part of this thesis, the proposed approach combines two techniques oriented security (IDS probe) and safety (filter approach) to propose a detection strategy based on four mechanisms related to:•Context detection: based on the current state of the system, an order sent by the PLC can be blocked by the control filter if it leads to a critical state (brutal attack).•Combinatorial constraints (sequential attack): verified by the concepts of distance (risk indicator for the current state) and trajectory (indicator of the intention to harm by studying the evolution of the distance on a sequence).•Temporal constraints (temporal attack): verified by time windows on the appearance of events and an indicator monitoring the average duration of execution.•Over-solicitation monitoring mechanism: based on an indicator monitoring orders sent to the actuators to prevent premature ageing of the production equipment (attack on the equipment).The proposed approach has been applied to various simulation examples and an industrial platform where the detection strategy has shown its effectiveness against different scenarios corresponding to attacker profiles., Les systèmes de contrôle-commande industriels (Industrial Control System, ICS) sont des infrastructures constituées par un ensemble de calculateurs industriels reliés en réseau et permettant de contrôler un système physique. Ils assurent le pilotage de réseaux électriques (Smart Grid), de systèmes de production, de transports, de santé ou encore de systèmes d’armes. Pensés avant tout pour assurer productivité et respect de la mission dans un environnement non malveillant, les ICS sont, depuis le 21ème siècle, de plus en plus vulnérables aux attaques (Stuxnet, Industroyer, Triton, …) notamment avec l’arrivée de l’industrie 4.0. De nombreuses études ont contribué à sécuriser les ICS avec des approches issues du domaine de la sécurité (cryptographie, IDS, etc…) mais qui ne tiennent pas compte du comportement du système physique et donc des conséquences de l’acte de malveillance en lui-même. Ainsi, une sécurisation se limitant exclusivement à l’analyse des informations qui transitent sur un réseau industriel n’est pas suffisante. Notre approche amène un changement de paradigme dans les mécanismes de détection en y intégrant la modélisation du comportement du système cyber-physique.Cette thèse propose des mécanismes de détection d’attaques en se positionnant au plus proche de la physique. Ils analysent les données échangées entre le système de contrôle-commande et le système physique, et filtrent les échanges au travers de modèles déterministes qui représentent le comportement du système physique soumis à des lois de commande. A cet effet, une méthodologie de conception a été proposée dans laquelle l’ensemble des ordres est identifié afin de détecter les attaques brutales. Pour faire face aux autres attaques, en particulier celles plus sournoises, comme les attaques par séquences, nous proposons une stratégie de détection complémentaire permettant d’estimer l’occurrence d’une attaque avant que ses conséquences ne soient destructives. A cet effet, nous avons développé des concepts de distance d’un état caractérisé comme critique auquel nous avons adjoint un second mécanisme dit de trajectoire dans le temps permettant de caractériser une intention de nuire.L’approche proposée hybride ainsi deux techniques orientées sécurité (sonde IDS) et sûreté (approche filtre) pour proposer une stratégie de détection basée sur quatre mécanismes lié :•A la détection de contexte : basé sur l’état courant de l’ICS, un ordre émis par l’API peut être bloqué s’il conduit vers un état critique (attaque brutale).•Aux contraintes combinatoires (attaque par séquences) : vérifiées par les concepts de distance et de trajectoire (évolution de la distance).•Aux contraintes temporelles (attaque temporelle) : vérifiées par des fenêtres temporelles sur l’apparition d’évènements et d’indicateurs surveillant la durée moyenne d’exécution.•Aux sur-sollicitations basées sur un indicateur surveillant les commandes envoyées afin de prévenir un vieillissement prématuré (attaque sur les équipements).L’approche proposée a été appliquée sur différents exemples de simulation et sur une plateforme industrielle réelle où la stratégie de détection a montré son efficacité face à différents profils d’attaquant.

National audience; Diagnosing is a general reasoning task that aims at identifying the nature of a situation (misbehaviour, illness, problem,..) by interpreting output signs (observations, measurements, alarms). This type of reasoning can be applied in many social and economical domains. This defense will present a synthesis of the contributions for the development of diagnostic agents on a various type of systems (from statical logical-based systems till timed discrete event systems). The way such agents are involved in decision processes such as corrective and predictive maintenance will be also discussed.; Le diagnostic est un raisonnement général qui consiste à identifier la nature d'une situation (dysfonctionnement, maladie, problème...) par l'interprétation de signes extérieurs (observations, mesures, alarmes). Par sa nature, ce type de raisonnement peut s’appliquer à de nombreux domaines socio-économiques. Cette soutenance a pour objectif de présenter une synthèse des contributions à la mise en œuvre effective d’agents diagnostiqueurs sur des types de systèmes variés (allant des systèmes logiques statiques à des systèmes à événements discrets temporels) ainsi que de leur intégration dans des systèmes d’aide à la décision, notamment pour la maintenance corrective et prévisionnelle de systèmes.

National audience; Diagnosing is a general reasoning task that aims at identifying the nature of a situation (misbehaviour, illness, problem,..) by interpreting output signs (observations, measurements, alarms). This type of reasoning can be applied in many social and economical domains. This defense will present a synthesis of the contributions for the development of diagnostic agents on a various type of systems (from statical logical-based systems till timed discrete event systems). The way such agents are involved in decision processes such as corrective and predictive maintenance will be also discussed.; Le diagnostic est un raisonnement général qui consiste à identifier la nature d'une situation (dysfonctionnement, maladie, problème...) par l'interprétation de signes extérieurs (observations, mesures, alarmes). Par sa nature, ce type de raisonnement peut s’appliquer à de nombreux domaines socio-économiques. Cette soutenance a pour objectif de présenter une synthèse des contributions à la mise en œuvre effective d’agents diagnostiqueurs sur des types de systèmes variés (allant des systèmes logiques statiques à des systèmes à événements discrets temporels) ainsi que de leur intégration dans des systèmes d’aide à la décision, notamment pour la maintenance corrective et prévisionnelle de systèmes.

International audience; Dans ce papier, nous nous intéressons à la vérification de la diagnosticabilité par model-checking des Systèmes à Evénements Discrets (SED) modélisés à base d'automates à états finis. Nous proposons une méthode basée sur un algorithme permettant l'analyse de la diagnosticabilité du SED à partir de son modèle de base. Celui-ci constitue la donnée d'entrée de notre méthode. Une condition de la diagnosticabilité étant la présence d'un cycle indéterminé dans un système, nous proposons de rechercher l'ensemble des cycles puis de les analyser. Pour cela, notre méthodologie se découpe en 3 phases. Une phase de modélisation et instanciation de modèles, une phase de recherche de cycles et enfin une phase d'analyse de la non-diagnosticabilité. Nous illustrons notre approche autour d'une étude expérimentale.

International audience; Les systèmes de contrôle-commande industriels (Industrial Control Systems, ICS en anglais) sont de plus en plus présents dans notre vie quotidienne et intégrés à nos infrastructures critiques. A l'origine, les ICS ont été conçus pour assurer la productivité et garantir la sûreté des systèmes contrôlés. Toutefois, l'Histoire récente nous a démontré qu'ils étaient vulnérables à des attaques par vecteur numérique et que les architectures matérielles offraient des surfaces d'attaques importantes. A ces vulnérabilités, héritées principalement de l'introduction de technologies provenant de l'Information Technology (IT), deux types d'approches peuvent fournir des solutions intéressantes : celles basées sur la sûreté de fonctionnement (Operational Technology, OT) et celles basées sur la sécurité des systèmes d'information. L'approche proposée hybride deux types de solution : l'approche filtre et les IDS afin de détecter des intrusions dans les ICS pouvant amener le système dans des états critiques. La localisation des filtres est primordiale pour assurer la pertinence des mécanismes de détection. La notion de distance permettra de contrôler la distance aux états critiques et ainsi de prévenir des dérives vers ces états. Le concept de trajectoire permettra d'évaluer cette distance au cours du temps et de l'évolution du système. Dans une première section, nous présenterons les systèmes de contrôle-commande. Puis nous mettrons en avant les vulnérabilités et les surfaces d'attaque pouvant conduire à des cyberattaques. La troisième partie permettra d'expliquer l'approche proposée et de la positionner dans la littérature. Enfin, une partie expérimentale sera proposée où l'approche sera mise en œuvre en simulation sur un exemple inspiré d'un système industriel.

MSR 2017 - 11ème Colloque sur la Modélisation des Systèmes Réactifs, Marseille, FRANCE, 15-/11/2017 - 17/11/2017; Dans ce papier, nous nous intéressons à l'analyse de la diagnosticabilité des systèmes à évènements discrets modélisés par des automates à états finis. En particulier, une variante de l'approche diagnostiqueur initiée par Sampath et co. [1, 2] est présentée. Cette variante repose sur une nouvelle structure qui consiste à séparer explicitement les états normaux de ceux fautifs à l'intérieur de chaque noeud du diagnostiqueur. Une telle distinction permet de suivre séparément l'évolution des traces normales et fautives dans le diagnostiqueur. Différentes caractéristiques de la nouvelle structure sont ensuite exploitées pour (i) raffiner la condition nécessaire et suffisante de la diagnosticabilité [1], (ii) développer une nouvelle condition nécessaire vérifiable directement sur le diagnostiqueur sans revenir au modèle, (iii) proposer une version simplifiée de la condition nécessaire et suffisante, et enfin (iv ) développer une procédure systématique pour l'analyse de la diagnosticabilité basée sur un algorithme de vérification à la volée. L'évaluation de cette approche est faite à travers une série d'expérimentations et de comparaisons avec des approches classiques de référence

Colloque avec actes et comité de lecture. internationale.; International audience; Nous nous intéressons dans ce papier à la mise en œuvre d’une approche de conception de la commande distribuée des systèmes à événements discrets sur un système manufacturier. Il s’agit de trois stations de distribution, de test et de tri de pièces commandées par trois Automates Programmables Industriels (APIs). La commande distribuée est obtenue en se basant sur la modularité du système et sur la spécification des contraintes sous forme d’équations logiques dans l’algèbre de Boole afin d’éviter l’explosion combinatoire. Dans le but de garantir la flexibilité exigée dans les systèmes manufacturiers, deux modes de fonctionnement (local et global) sont garantis par la commande distribuée. Une méthode d’implantation des contrôleurs distribués en langage API est proposée.

National audience; L'objectif de l'identification comportementale d'un système séquentiel réactif est de construire, à partir d'une séquence observée d'événements d'entrées/sorties, un modèle capable d'exhiber a la fois les relations de causalités entre entrées et sorties (i.e. le comportement réactif ou observable) et les évolutions de l'état interne, (i.e. le comportement non-observable). Cette communication propose une méthode visant a découvrir la partie non observable du comportement à partir d'une séquence de tir. Le principe est de projeter la séquence sur des alphabets pour découvrir des motifs caractéristiques de relations de dépendances entre les transitions. Ces relations peuvent ensuite être converties en fragments structurels de Réseaux de Petri (places et liens orientés). La démarche d'identification est illustrée sur un système expérimental réel.

Le diagnostic des défauts (Fault Detection and Isolation) des systèmes industriels est défini comme l'opération permettant de détecter un défaut, de localiser son origine et de déterminer ses causes. L'intérêt pour le diagnostic des défaillances s'explique par la complexité croissante des systèmes industriels qui sont de plus en plus exigeants en termes de contraintes de sécurité, de fiabilité, de disponibilité et de performances (sureté de fonctionnement). En fait, la possibilité qu'un système tombe en panne croît malgré les précautions de manipulations, Par conséquent, un module de diagnostic est nécessaire pour empêcher la propagation de pannes et pour limiter leurs conséquences qui peuvent être catastrophiques au niveau économique mais aussi au niveau environnemental. Dans cet article, nous présentons les différentes méthodes de diagnostic de systèmes à évènements discrets (SED), avec une étude comparative selon plusieurs critères : l'outil de modélisation (les automates, réseaux de pétri...), la structure de la prise de décision (centralisée, décentralisée, distribuée) et le type de modélisation des défauts (à base d'événements, à base d'états et à base d'informations temporelles) ; dans le but de justifier que le diagnostic des défauts nécessite l'exploitation de toute l'information disponible afin de réaliser un modèle riche du procédé à diagnostiquer.

Computing systems have become more and more distributed and heterogeneous, making their manual administration difficult and error-prone. The Autonomic Computing approach has been proposed to overcome this issue, by automating the administration of computing systems with the help of control loops called autonomic managers. Many research works have investigated the automation of the administration functions of computing systems and today many autonomic managers are available. However the existing autonomic managers are mostly specialized in the management of few administration concerns. This makes necessary the coexistence of multiple autonomic managers for achieving a global system management. The coexistence of several managers make possible to address multiple concerns, yet requires coordination mechanisms to avoid incoherent management decisions. We investigate the use of control techniques for the design of coordination controllers, for which we exercise synchronous programming that provide formal semantics, and discrete controller synthesis to automate the construction of the controller. We follow a component-based approach, and explore modular discrete control allowing to break down the combinatorial complexity inherent to the state-space exploration technique. This improves scalability of the approach and allows constructing a hierarchical control. It also allows re-using complex managers in different contexts without modifying their control specifications. We build a component-based coordination of managers, with introspection, adaptivity and reconfiguration. This thesis details our methodology and presents case-studies. We evaluate and demonstrate the benefits of our approach by coordinating autonomic managers which address the management of availability, and the management of performance and resources optimization.; Les systèmes informatiques sont devenus de plus en plus distribués et hétérogènes, ce qui rend leur administration manuelle difficile et source d’erreurs. L’administration autonome a été proposée comme solution à ce problème. Elle consiste à automatiser l’administration des systèmes informatiques à l’aide de boucles de contrôle appelées gestionnaires autonomes. De nombreux travaux de recherche se sont intéressés à l’automatisation des fonctions d’administration de systèmes informatiques et aujourd’hui, beaucoup de gestionnaires autonomes sont disponibles. Toutefois, les gestionnaires autonomes existants sont, la plupart, spécialisés dans la gestion de quelques aspects d’administration. Cela rend nécessaire la coexistence de plusieurs gestionnaires autonomes pour atteindre une gestion globale des systèmes. La coexistence de plusieurs gestionnaires permet la gestion de plusieurs aspects, mais nécessite des mécanismes de coordination afin d’éviter des décisions incohérentes. Nous étudions l’utilisation de techniques de contrôle pour la conception de contrôleurs de coordination, nous utilisons la programmation synchrone qui fournit des méthodes formelles, et la synthèse de contrôleur discret pour automatiser la construction de contrôleur. Nous suivons une approche à base de composants, et utilisons le contrôle discret modulaire qui permet de décomposer la complexité combinatoire inhérente à la technique d’exploration d’espace d’états. Cela améliore le passage à l’échelle de notre approche et permet la construction d’un contrôle hiérarchique. Notre approche permet la réutilisation de gestionnaires complexes dans des contextes différents, sans modifier leurs spécifications de contrôle. Nous construisons une coordination de gestionnaires basée sur le modèle à composants offrant introspection, adaptabilité et reconfiguration. Cette thèse présente notre méthodologie et des études de cas. Nous évaluons et démontrons les avantages de notre approche par la coordination de gestionnaires autonomes dédiés à la gestion de la disponibilité, et à la gestion de la performance et l’optimisation de ressources.

Computing systems have become more and more distributed and heterogeneous, making their manual administration difficult and error-prone. The Autonomic Computing approach has been proposed to overcome this issue, by automating the administration of computing systems with the help of control loops called autonomic managers. Many research works have investigated the automation of the administration functions of computing systems and today many autonomic managers are available. However the existing autonomic managers are mostly specialized in the management of few administration concerns. This makes necessary the coexistence of multiple autonomic managers for achieving a global system management. The coexistence of several managers make possible to address multiple concerns, yet requires coordination mechanisms to avoid incoherent management decisions. We investigate the use of control techniques for the design of coordination controllers, for which we exercise synchronous programming that provide formal semantics, and discrete controller synthesis to automate the construction of the controller. We follow a component-based approach, and explore modular discrete control allowing to break down the combinatorial complexity inherent to the state-space exploration technique. This improves scalability of the approach and allows constructing a hierarchical control. It also allows re-using complex managers in different contexts without modifying their control specifications. We build a component-based coordination of managers, with introspection, adaptivity and reconfiguration. This thesis details our methodology and presents case-studies. We evaluate and demonstrate the benefits of our approach by coordinating autonomic managers which address the management of availability, and the management of performance and resources optimization.; Les systèmes informatiques sont devenus de plus en plus distribués et hétérogènes, ce qui rend leur administration manuelle difficile et source d’erreurs. L’administration autonome a été proposée comme solution à ce problème. Elle consiste à automatiser l’administration des systèmes informatiques à l’aide de boucles de contrôle appelées gestionnaires autonomes. De nombreux travaux de recherche se sont intéressés à l’automatisation des fonctions d’administration de systèmes informatiques et aujourd’hui, beaucoup de gestionnaires autonomes sont disponibles. Toutefois, les gestionnaires autonomes existants sont, la plupart, spécialisés dans la gestion de quelques aspects d’administration. Cela rend nécessaire la coexistence de plusieurs gestionnaires autonomes pour atteindre une gestion globale des systèmes. La coexistence de plusieurs gestionnaires permet la gestion de plusieurs aspects, mais nécessite des mécanismes de coordination afin d’éviter des décisions incohérentes. Nous étudions l’utilisation de techniques de contrôle pour la conception de contrôleurs de coordination, nous utilisons la programmation synchrone qui fournit des méthodes formelles, et la synthèse de contrôleur discret pour automatiser la construction de contrôleur. Nous suivons une approche à base de composants, et utilisons le contrôle discret modulaire qui permet de décomposer la complexité combinatoire inhérente à la technique d’exploration d’espace d’états. Cela améliore le passage à l’échelle de notre approche et permet la construction d’un contrôle hiérarchique. Notre approche permet la réutilisation de gestionnaires complexes dans des contextes différents, sans modifier leurs spécifications de contrôle. Nous construisons une coordination de gestionnaires basée sur le modèle à composants offrant introspection, adaptabilité et reconfiguration. Cette thèse présente notre méthodologie et des études de cas. Nous évaluons et démontrons les avantages de notre approche par la coordination de gestionnaires autonomes dédiés à la gestion de la disponibilité, et à la gestion de la performance et l’optimisation de ressources.

Les activités de recherche rentrent dans le spectre de la section 61 du CNU et ont pour domaine l’Automatique des Systèmes à Événements Discrets (SED). Elles sont conduites en vue d’accroître la sûreté de fonctionnement des systèmes automatisés comme ceux qu’il est possible de trouver dans le cadre de la production manufacturière, de la production d'énergie ou du transport. Une grande partie de ces recherches a concerné la conception sûre des systèmes de contrôle-commande à base d’Automates Programmables Industriels (API) et plus particulièrement les thématiques suivantes :- la vérification formelle de programmes de contrôle-commande,- la synthèse algébrique de programmes de contrôle-commande à partir de spécifications informelles,- le test de conformité d’un contrôleur logique vis-à-vis de sa spécification.D'autres recherches ont porté sur la formalisation des outils pour l’analyse de sûreté, utilisés dans le cadre de l’analyse prévisionnelle des risques d’un équipement ou d’une installation industrielle. Cette formalisation des outils utilisés en sûreté a été faite en examinant avec un point de vue SED une problématique qui ne l’était pas à son origine. Il a été étudié :- la modélisation algébrique des arbres de défaillances dynamiques,- l’analyse prévisionnelle des risques d’un point de vue qualitatif pour les systèmes réparables à partir de Boolean logic Driven Markov Processes (BDMPs),- l’analyse prévisionnelle des risques d’un point de vue quantitatif pour les systèmes réparables à l’aide de chaînes de Markov.D'une manière générale, ces activités de recherche ont pour objectif de proposer des apports formels ou méthodologiques à des outils de modélisation généralement issus de l’industrie tout en répondant à des besoins industriels déjà présents ou sur le point de le devenir.

In the context of the CERN Large Hadron Collider (LHC), a large number of control systems have been built based on industrial control and SCADA solutions. Beyond the complexity of these systems, a large number of sensors and actuators are controlled which make the monitoring and diagnostic of these equipment a continuous and real challenge for human operators. Even with the existing SCADA monitoring tools, critical situations prompt alarms avalanches in the supervision that makes diagnostic more difficult. This thesis proposes a decision support methodology based on the use of historical data. Past faults signatures represented by alarm lists are compared with the alarm list of the fault to diagnose using pattern matching methods. Two approaches are considered. In the first one, the order of appearance is not taken into account, the alarm lists are then represented by a binary vector and compared to each other thanks to an original weighted distance. Every alarm is weighted according to its ability to represent correctly every past faults. The second approach takes into account the alarms order and uses a symbolic sequence to represent the faults. The comparison between the sequences is then made by an adapted version of the Needleman and Wunsch algorithm widely used in Bio-Informatic. The two methods are tested on artificial data and on simulated data extracted from a very realistic simulator of one of the CERN system. Both methods show good results., Au CERN (Organisation européenne pour la recherche nucléaire), le contrôle et la supervision du plus grand accélérateur du monde, le LHC (Large Hadron Collider), sont basés sur des solutions industrielles (SCADA). Le LHC est composé de sous-systèmes disposant d’un grand nombre de capteurs et d’actionneurs qui rendent la surveillance de ces équipements un véritable défi pour les opérateurs. Même avec les solutions SCADA actuelles, l’occurrence d’un défaut déclenche de véritables avalanches d’alarmes, rendant le diagnostic de ces systèmes très difficile. Cette thèse propose une méthodologie d’aide au diagnostic à partir de données historiques du système. Les signatures des défauts déjà rencontrés et représentés par les listes d’alarmes qu’ils ont déclenchés sont comparées à la liste d’alarmes du défaut à diagnostiquer. Deux approches sont considérées. Dans la première, l’ordre d’apparition des alarmes n’est pas pris en compte et les listes d’alarmes sont représentées par un vecteur binaire. La comparaison se fait à l’aide d’une distance pondérée. Le poids de chaque alarme est évalué en fonction de son aptitude à caractériser chaque défaut. La seconde approche prend en compte l’ordre d’apparition des alarmes, les listes d’alarmes sont alors représentées sous forme de séquences symboliques. La comparaison entre ces deux séquences se fait à l’aide d’un algorithme dérivé de l’algorithme de Needleman et Wunsch utilisé dans le domaine de la Bio-Informatique. Les deux approches sont testées sur des données artificielles ainsi que sur des données extraites d’un simulateur très réaliste d’un des systèmes du LHC et montrent de bons résultats.

The work presented in this thesis deals with the modeling of discrete event systems using (max,+) automata, that is automata with weights in the socalled (max,+) algebra. We propose alternative representations for (max,+) automata. These representations approximate the dynamics of (max,+) automata, since only their extremal behaviors are described, but they are expected to make possible to solve important problems with reasonable complexity. More precisely, recursive equations are defined over (max,+) and (min,+) algebras to describe worst case and optimal case behaviors of (max,+) automata. It is shown that several pertinent performance indicators can be easily derived or approximated from these representations with a low computation complexity. Another contribution is to define inputs which model exogenous influences on their dynamic evolution, and a new approach for the control of (max,+) automata is proposed.; Les travaux abordés dans cette thèse concernent la modélisation des systèmes à événements discrets à l'aide d'automates à multiplicités dans l'algèbre (max,+), appelés automates (max,+). Nous proposons des représentations alternatives pour les automates (max,+). Celles-ci traduisent l'évolution des automates de façon approximative, car seuls leurs comportements extrémaux sont décrits, mais il est escompté de pouvoir résoudre à l'aide de celles-ci des problèmes importants avec une complexité raisonnable. Plus exactement, des équations récursives ont été définies dans l'algèbre (max,+) et l'algèbre (min,+) afin de décrire les comportements pire-cas et meilleur-cas des automates (max,+). Il est montré que ces représentations permettent d'évaluer les performances de systèmes avec une faible complexité de calcul. L'influence d'une entrée exogène peut être prise en compte dans ces représentations et on obtient alors un modèle analogue aux équations d'état standard pour les systèmes non-autonomes dans l'algèbre (max,+). Cette caractéristique permet l'adaptation de lois de commande développées pour les systèmes (max,+) linéaires aux systèmes à événements discrets appréhendés à l'aide d'automates (max,+).

International audience; Cet article traite de la synthèse d'un observateur d'état pour des systèmes temps réels modélisés à l'aide des réseaux de Petri p-temporels. La méthode développée permet d'estimer le marquage d'un réseau de Petri p-temporel en présence d'informations partielles sur le système. En effet, les transitions du modèle sont partitionnées en transitions observables (dont le tir peut être détecté par un agent externe) et en transitions non observables. L'approche ne nécessite pas la prise en compte d'hypothèse restrictive sur la structure du réseau étudié. De plus, bien que le temps soit pris en compte le problème d'explosion combinatoire de l'espace des états est évité - la construction du graphe des classes d'état n'étant pas nécessaire car la méthode s'appuie sur le réseau autonome sous-jacent au modèle p-temporel considéré.

Avionics systems become more and more complex. With the improvment of computing possibilities, new architectures based on resources sharing are growing up. Perform diagnosis of a system is no longer a trivial operation. The challenge is to develop efficient techniques of diagnosis while optimizing capabilities of monitoring required.This thesis give a model-based characterization of a system under diagnosis, and proposes techniques to assess diagnostic performances, as well as its monitoring ones (with respect to these diagnostic performances). The industrial context of this thesis brings other constraints, and in particular the need to handle the size of avionics systems to analyze. That thesis then examines the applicability of the introduced techniques to this particular context, and proposes an adaptation.; Les systèmes avioniques s'étoffent et se complexifient de plus en plus. Avec l'augmentation des capacités de calcul, de nouvelles architectures basées sur le partage de ressources émergent. Effectuer le diagnostic d'un système n'est désormais plus une opération anodine. L'enjeu actuel est donc de mettre en place des techniques de diagnostic performantes tout en optimisant les capacités de monitoring nécessaires.Ce mémoire donne une caractérisation basée modèle d'un système sous diagnostic, puis propose des techniques pour en évaluer les performances de diagnostic, ainsi que celles de son monitoring (relativement à ces performances). Le contexte industriel dans lequel s'inscrit cette thèse amène d'autres contraintes, notamment la prise en compte de la taille des systèmes avioniques à analyser. Cette thèse étudie alors l'applicabilité des techniques introduites dans ce contexte et en propose une adaptation.

International audience; This paper presents an approach to solve the problem of K-diagnosability of bounded labeled Petri nets (PNs). We first introduce extended incidence matrix, marking-eventing and extended state equation, which make it possible to record the number of event occurrences for any mar- king reachable from the initial one. Based on the proposed conceptions, we give a mathematical representation for labeled PNs to check diagnosability, and describe K-diagnosability problem of partially observed PNs. Then we propose a recursive algorithm for testing K-diagnosability of PNs, without construction of marking graph or diagnoser.; Dans cet article, nous présentons une approche qui permet de résoudre le problème de la K-diagnosticabilité des réseaux de Petri (RdP) synchronisés et bornés. Tout d'abord, nous introduisons deux nouveaux concepts : la matrice d'incidence étendue qui intègre les informations relatives aux affectations des événements aux transitions, et le marquage étendu ainsi que l'équation d'état étendue, qui permet de transcrire le nombre d'occurrences de chaque événement depuis l'état initial, jusqu'à un certain marquage étendu cible. Sur la base de ces concepts, nous élaborons un nouvel algorithme d'analyse, à la volée, de la K-diagnosticabilité des RdP synchronisés partiellement observables. L'algorithme développé se base sur des procédures récursives et ne nécessite pas une construction a priori du graphe de marquage ni d'un diagnostiqueur.

National audience; Dans cet article nous présentons une approche d'identification passive et de type boîte noire pour les Systèmes à Evénements Discrets (SED), constitués d'un contrôleur et d'un procédé interagissant en boucle fermée. Cette approche permet de construire de manière systématique un réseau de Petri interprété (RdPI) qui modélise le comportement du SED, à partir de la seule observation des signaux échangés entre contrôleur et procédé. Dans un premier temps, nous montrons pourquoi les approches d'identification existantes sont encore mal adaptées à la prise en compte des contraintes physiques et technologiques des systèmes à identifier. Par la suite nous développons notre approche, qui se caractérise par la génération d'un RdPI qui exprime directement par sa structure les comportements caractéristiques des SED, comme les parallélismes, les alternatives ou les partages de ressources.

A manufacturing system may be represented by Discrete Event System (DES). Apart from planning (where people work with ratios of products fabricated per week or per day), any modelling could be based on the concepts of event and activities. An event corresponds to a state change. An activity is a black-box summarizing what is occurring between two events. When using Petri Nets, events are associated with transitions, and activities with places. Our work proposes a supervisory synthesis for Discrete Event System modelled by a class of Petri Net called Marked Graph. The objective of this synthesis is to build a control law that enforces the system to respect a set of given specifications. To model these specifications, we propose new mathematical formulas called Marking Exclusion Constraint (MEC). This model is our first contribution. The Second main contribution of my thesis is to synthesize a computationally efficient technique to build a supervisor that enforces the system to respect the constraints by avoiding a set of forbidden states modelled by MEC specifications. We extend this synthesis technique to solve the problem in the presence of uncontrollable events and unobservable events. Sometimes in order to study the performance aspects, we must take in consideration the time data. Thus we address control synthesis for Timed Discrete Event Systems under MEC specifications by using Timed Petri Nets, Un Système de production peut être représenté par les systèmes à événements discrets. En dehors de la planification (où les gens travaillent avec des ratios de produits fabriqués par semaine ou par jour), la modélisation pourrait être basée sur les concepts d'événement et d'activités. Un événement correspond à un changement d'état. Une activité est une boîte noire d'encapsulation de ce qui se passe entre deux événements. En utilisant les réseaux de Petri (RdP), les événements sont représentés par les transitions, et les activités par les lieux. Notre travail propose une synthèse de commande par supervision pour les systèmes d'événements discrets modélisés par une classe de réseaux de Petri appelé graphe d'événements. L'objective de cette thèse est de concevoir un superviseur capable d'aider à améliorer la performance de système et de protéger le système en respectant des spécifications données par le fabricant ou le client selon les besoins et les conditions de travail. Pour modéliser ces spécifications, nous avons proposé un nouveau modèle mathématique de contrainte, appelé Contrainte d'Exclusion de Marquage (CEM). La deuxième contribution principale de ma thèse est de synthétiser une technique efficace et simple pour construire un superviseur qui impose le système de respecter des contraintes en évitant l'ensemble des états interdits modélisé par CEM. Nous avons également développé cette synthèse pour résoudre le problème d'existence des événements incontrôlables et des événements inobservables. Parfois, afin d'étudier les aspects liés à la performance, nous devons prendre le temps en considération. Donc, nous avons résolu aussi le problème des événements temporisé en utilisant RdP temporisés soumis à CEM

National audience; Les Boolean Driven Markov Processes (BDMP) ont été conçus par EDF pour conduire des analyses prédictives de sûreté de systèmes critiques. Tout comme pour les arbres de défaillance, la construction d'un BDMP consiste à décrire les combinaisons de panne des composants d'un système qui conduisent à sa défaillance. Une fois ce modèle établi, la recherche de toutes les séquences de pannes élémentaires qui conduisent à la défaillance globale du système est un problème complexe qui nécessite d'explorer l'espace d'état, le plus souvent de très grande taille, qui est sous-jacent au BDMP. Pour déterminer de manière systématique et exhaustive ces scénarios de défaillance, nous utilisons une approche basée sur la théorie des langages et des automates fi nis. Nous proposons dans ce papier un algorithme qui permet de calculer un automate fini "équivalent" à un BDMP, dans le sens où l'ensemble des scénarios de pannes et réparations du BDMP coïncide avec les mots du langage généré par l'automate.

This thesis deals with uncertain (min,+)-linear systems contained in intervals, the bounds of which are known. First, as exact computations - sum, inf-convolution, Kleene star/subadditive closure - are often memory consuming and time costly, some approached computations are introduced through inclusion functions. The obtained results are particular intervals called container. The upper bound of a container is the greatest element of the equivalence class of the approached system modulo the Legendre-Fenchel transform. The lower bound of the container is a lower bound of this class, and so of the approached system. The convex characteristics of these bounds provide algorithms of linear or quasi-linear complexity for the computations. Second, the control of uncertain (min,+)-linear systems is studied. These uncertainties can appear after computations realized over the containers introduced above, or when uncertain or variable parameters are present during the modelings. Some existing control structures (precompensator, feedback) are applied over these uncertain systems and the following problems are treated: Window Flow Control problem, reduction of the uncertainty at the output of the system controlled by a precompensator, computation of a neutral precompensator which delays the input without damage the transfer of the system alone., Cette thèse se situe dans le contexte des systèmes (min,+)-linéaires incertains, contenus dans des intervalles dont seules les bornes sont connues. Dans un premier temps, puisque les calculs exacts - somme, inf-convolution, étoile de Kleene/clôture sous-additive - sont souvent coûteux en espace mémoire et en temps de calculs, des calculs approchés sont proposés à travers des fonctions d'inclusion. Les résultats obtenus sont des intervalles particuliers appelés conteneurs. La borne supérieure d'un conteneur est l'élément le plus grand de la classe d'équivalence du système approché selon la transformée de Legendre-Fenchel. La borne inférieure représente un minorant de cette classe d'équivalence et ainsi du système exact. Les caractéristiques de convexité de ces bornes permettent d'obtenir des algorithmes de calculs de complexité linéaire et quasi-linéaire. Dans un second temps, la commande des systèmes (min,+)-linéaires incertains est étudiée. Ces incertitudes peuvent apparaître suite aux calculs effectués sur les conteneurs proposés ci-dessus, mais également lorsque des paramètres incertains ou variables sont présents lors des modélisations. Des structures de contrôles existantes (précompensateur, retour de sortie) sont appliquées à ces systèmes incertains et les problèmes suivants sont ainsi traités : problème du Window Flow Control, réduction de l'incertitude en sortie du système contrôlé par un précompensateur, calcul d'un précompensateur neutre ralentissant les entrées sans dégrader la dynamique du système seul.

6 pages; National audience; Dans ce papier, trois méthodes de diagnostic des Systèmes à Événements Discrets sont évaluées. Les approches considérées sont toutes basées sur des modèles : l'approche par diagnostiqueur, l'approche par templates et l'approche par résidus. En appliquant ces trois approches à un même système automatisé, leurs performances et limites en terme de complexité de mise en œuvre, détection et isolation des fautes et génération de fausses alarmes sont analysées.

National audience; Ce papier traite de la conception et de la réalisation d'un système de pilotage en ligne de véhicules autoguidés (dits AGV). Ce système assure à la fois la sûreté du processus et l'optimisation de critères de performance. La sécurité de fonctionnement, en l'occurence l'évitement de collisions et de blocages entre AGV, est réalisée à l'aide de la théorie de la supervision de Ramadge et Wonham. On superpose à ce premier niveau de commande, un module de routage des AGV. Les tronçons de circuit devant être empruntés sont choisis de façon à optimiser un certain critère de coût. L'architecture proposée est mise en oeuvre sur l'exemple d'une flotte d'AGV. Le système d'AGV est émulé avec Arena et interfacé avec les modules du système de pilotage. Cette mise en oeuvre valide les concepts proposés.

A general goal of systems biology is to acquire a detailed understanding of the dynamics of living systems by relating functional properties of whole systems with the interactions of their constituents. Often this goal is tackled through computer simulation. A number of different formalisms are currently used to construct numerical representations of biological systems, and a certain wealth of models is proposed using ad hoc methods. There arises an interesting question of to what extent these models can be reused and composed, together or in a larger framework. In this thesis, we propose BioRica as a means to circumvent the difficulty of incorporating disparate approaches in the same modeling study. BioRica is an extension of the AltaRica specification language to describe hierarchical non-deterministic General Semi-Markov processes. We first extend the syntax and automata semantics of AltaRica in order to account for stochastic labeling. We then provide a semantics to BioRica programs in terms of stochastic transition systems, that are transition systems with stochastic labeling. We then develop numerical methods to symbolically compute the probability of a given finite path in a stochastic transition systems. We then define algorithms and rules to compile a BioRica system into a stand alone C++ simulator that simulates the underlying stochastic process. We also present language extensions that enables the modeler to include into a BioRica hierarchical systems nodes that use numerical libraries (e.g. Mathematica, Matlab, GSL). Such nodes can be used to perform numerical integration or flux balance analysis during discrete event simulation. We then consider the problem of using models with uncertain parameter values. Quantitative models in Systems Biology depend on a large number of free parameters, whose values completely determine behavior of models. Some range of parameter values produce similar system dynamics, making it possible to define general trends for trajectories of the system (e.g. oscillating behavior) for some parameter values. In this work, we defined an automata-based formalism to describe the qualitative behavior of systems’ dynamics. Qualitative behaviors are represented by finite transition systems whose states contain predicate valuation and whose transitions are labeled by probabilistic delays. We provide algorithms to automatically build such automata representation by using random sampling over the parameter space and algorithms to compare and cluster the resulting qualitative transition system. Finally, we validate our approach by studying a rejuvenation effect in yeasts cells population by using a hierarchical population model defined in BioRica. Models of ageing for yeast cells aim to provide insight into the general biological processes of ageing. For this study, we used the BioRica framework to generate a hierarchical simulation tool that allows dynamic creation of entities during simulation. The predictions of our hierarchical mathematical model has been validated experimentally by the micro-biology laboratory of Gothenburg, Les travaux effectués durant cette thèse portent sur la spécification, l'analyse et l'application de systèmes a événements discrets pour la modélisation de processus biologiques stochastiques en biologie des systèmes. Le point de départ de cette thèse est le langage de modélisation AltaRica, que nous étendons afin de permettre de décrire des événements temporisés selon des distributions de probabilités quelconques (dégénérées, discrètes et continues). Nous définissons ensuite la sémantique de ce langage en terme d'automates de mode stochastiques et présentons trois opérations de compositions permettant de modéliser des systèmes hiérarchiques avec événements synchronisés et partage de valeurs via un mécanisme de connexion. Nous donnons ensuite au automates de mode stochastiques une sémantique en termes de systèmes de transitions dont les transitions sont étiquetées par des distributions de probabilités et des probabilités de transitions instantanées. Nous caractérisons ensuite 6 sous classes de ces systèmes de transitions et donnons pour chacune de ces classes un algorithme de simulation ainsi qu'une mesure de probabilité sur les chemins finis. Nous montrons que pour certaines de ces classes, notre sémantique est conforme avec les mesures de probabilité de chemin usuellement associées aux chaînes de Markov a temps discret, a temps continu et aux processus semi-Markoviens généralisés. Nous abordons ensuite le problème de la réutilisation de modèles continus existant dans un système discret. Nous donnons une méthode d'abstraction permettant de représenter un ensemble de trajectoires bornées ou non d'un modèle continu sous forme d'un système de transition stochastique fini. A travers des exemples tirés de la littérature, nous montrons que notre abstraction préserve les propriétés "qualitatives" (par exemple oscillations, hystérie) des modèles continus et qu'une comparaison entre trajectoires basée sur leurs représentations en termes de systèmes de transitions permet de regrouper les trajectoires en fonction de comportements qualitatifs plus fins que ceux permis par la théorie des bifurcations. Finalement, nous étudions a l'aide de ces modèles des processus liés a la division cellulaire chez les levures. En particulier, nous définissons un modèle pour le vieillissement cellulaire dans une population de levure où le comportement individuel d'une cellule est régi par une équation différentielle ordinaire et où le processus de division est régi par un système de transition. Nous montrons a l'aide de ce modèle que la survie d'une population de levure de type Schizosaccharomyces Pombe, qui se divisent par une fission médiane, n'est possible que grâce a un mécanisme de distribution non symétrique des dégâts oxydatifs entre la progéniture et la cellule souche. Cette hypothèse fut validée expérimentalement lors d'une collaboration avec le laboratoire de micro-biologie de Göteborg.

This thesis presents an approach to monitoring the controlled discrete events systems. The study is limited to the interruptible faults : intermittent and permanent. To increase the availability of a system, it is crucial to reduce the unnecessary interruptions. For that, the acceptable behavior of these systems is introduced. This behavior presents a tolerance to the intermittent faults. An approach of the construction of monitoring system is presented. We model, firstly, the behavior of the systems by a stopwatch automaton. Secondly, we apply to this automaton a synthesis procedure. This procedure is based on the forward and backward reachability analysis of the stopwatch automaton. A new model called Post- and Pre-initialized stopwatch Petri nets is also presented. This model is used to model the behavior of systems subjected to the interrupting faults. The implementation of our monitoring approach is done by using a Programmable Logic Controller. The monitoring system is translated structurally into a SFC program., Ce mémoire de thèse prèsente une approche pour la surveillance des systèmes à événements discrets commandés. L'étude se restreint aux défauts interruptibles : intermittents et permanents. Le comportement acceptable de ces systèmes est introduit afin d'accroître la disponibilité des systèmes commandés. Ce comportement présente une tolérance aux défauts intermittents. Une démarche de construction du système de surveillance est présentée. Nous modélisons, dans un premier temps, le comportement du système sujet aux défauts interruptibles par un automateà chronomètres. Nous appliquons, dans un deuxième temps, une procédure de synthèse à cet automate. Cette procédure est basée aux opérateurs d'analyse en avant et en arriérer de l'automate. Un nouveau modèle appelé réseaux de Petri à chronomètres post- et Pré-initialisés est également présenté. Ce modèle général du RdP a été utilisé, dans le cadre de ce mémoire, pour modéliser le comportement des systèmes sujets aux défauts interruptibles. L'implémentation de notre méthode de surveillance se fait par un automate programmable industriel. Pour ce faire, le système de surveillance étant sous la forme d'un automate àchronomètres est traduit structurellement en programme SFC.

This thesis presents an approach to monitoring the controlled discrete events systems. The study is limited to the interruptible faults : intermittent and permanent. To increase the availability of a system, it is crucial to reduce the unnecessary interruptions. For that, the acceptable behavior of these systems is introduced. This behavior presents a tolerance to the intermittent faults. An approach of the construction of monitoring system is presented. We model, firstly, the behavior of the systems by a stopwatch automaton. Secondly, we apply to this automaton a synthesis procedure. This procedure is based on the forward and backward reachability analysis of the stopwatch automaton. A new model called Post- and Pre-initialized stopwatch Petri nets is also presented. This model is used to model the behavior of systems subjected to the interrupting faults. The implementation of our monitoring approach is done by using a Programmable Logic Controller. The monitoring system is translated structurally into a SFC program.; Ce mémoire de thèse prèsente une approche pour la surveillance des systèmes à événements discrets commandés. L'étude se restreint aux défauts interruptibles : intermittents et permanents. Le comportement acceptable de ces systèmes est introduit afin d'accroître la disponibilité des systèmes commandés. Ce comportement présente une tolérance aux défauts intermittents. Une démarche de construction du système de surveillance est présentée. Nous modélisons, dans un premier temps, le comportement du système sujet aux défauts interruptibles par un automateà chronomètres. Nous appliquons, dans un deuxième temps, une procédure de synthèse à cet automate. Cette procédure est basée aux opérateurs d'analyse en avant et en arriérer de l'automate. Un nouveau modèle appelé réseaux de Petri à chronomètres post- et Pré-initialisés est également présenté. Ce modèle général du RdP a été utilisé, dans le cadre de ce mémoire, pour modéliser le comportement des systèmes sujets aux défauts interruptibles. L'implémentation de notre méthode de surveillance se fait par un automate programmable industriel. Pour ce faire, le système de surveillance étant sous la forme d'un automate àchronomètres est traduit structurellement en programme SFC.

International audience; Cet article s'intéresse au problème de la validation formelle de propriétés temporelles quantitatives et paramétrées pour les systèmes à évènements discrets. Le model checking est une technique d'analyse exhaustive de l'espace des états d'un système modélisé dans un lange formel. Il permet la vérification de propriétés de logique temporelle quantitative. Cependant, l'introduction de paramètres entraine une complexité trop grande de l'analyse, en particulier sur un modèle exprimé en réseaux de Petri temporels. Cet article propose donc une méthode alternative et présente un outil : LPT (Little Parametric Tool) permettant la validation d'une borne temporelle paramétrée. Avec LPT, le modèle du système est analysé et la valeur de la borne maximale est recherchée par l'outil.

International audience; Suite à nos travaux sur la synthèse de la commande basée sur la théorie de Ramadge et Wonham, nous proposons une approche de validation de la commande hors ligne. Cette approche nécessite la modélisation de la partie opérative et des contraintes de sécurité et de vivacité, appliquées au système. Nous proposons de modéliser la partie opérative par une méthode à base de règles d'occurrence et de précédence et d'utiliser des équations logiques pour les contraintes pour pallier les problèmes de méthodologie de conception de modèles et d'explosion combinatoire. La démarche de validation de la commande permet de détecter les éventuels blocages ou les contraintes non respectées et d'aider le concepteur à apporter les modifications nécessaires. Pour illustrer ces concepts, nous proposons de les éprouver sur un exemple de tri de caisses.

6 pages; International audience; La méthode de synthèse présentée dans cette communication a été développée pour concevoir automatiquement des contrôleurs logiques. Nous montrons comment utiliser cette approche dans le cas particulier où un concepteur cherche à obtenir un contrôleur à partir d'un modèle générique. L'instanciation du modèle est obtenue par synthèse algébrique. Pour illustrer cette approche,l'exemple d'une chaîne de production, dont le modèle générique du contrôleur est donné par un RdPI, est utilisé.

This thesis proposes a consistency-based detection and diagnosis method for discrete event systems. The method takes into account the possibility of errors within the models that are used as a reference of the correct behaviour of the system. The detection step is carried out by consistency verification between the observed behaviour and the one described in the system models. Since the models may be incorrect, detected inconsistencies can either correspond to failures of the process or to modelling errors. To distinguish between these two cases, it is necessary to determine the joint sub-models. Each observation brings useful information for the configuration identification between models. The on-line identification is based on a search in a graph that exhaustively describes the possible configurations of the models. Finally, the diagnosis principle consists in restoring the consistency with the observations by modifying the models.; Cette thèse propose une méthode de détection et diagnostic basée cohérence pour les systèmes à événements discrets. La méthode prend en compte la possibilité d'erreurs dans les modèles utilisés comme référence du bon comportement du système. La détection est réalisée par la vérification de cohérence entre le comportement observé et le comportement décrit par les modèles du système. Dans la mesure où les modèles utilisés ne sont pas exempts d'erreurs, la perte de cohérence détectée peut correspondre à une réelle défaillance au niveau du procédé ou à une erreur dans les modèles. Pour distinguer ces deux cas, il est nécessaire de déterminer les sous-modèles communs. Chaque observation émanant du procédé apporte une information utile pour l'identification de la ou des types de configuration entre les modèles. L'identification est réalisée en ligne et repose sur le parcours d'un graphe décrivant exhaustivement l'ensemble des configurations des modèles. Enfin, le rétablissement de la cohérence avec les observations par modification des modèles constitue le principe du diagnostic

We present a synthesis method for the control of discrte event systems (DES). This method is an alternative to the supervisory contol theory (SCT). The method uses a control specification described in natural language and finishes with the implantation of control functions calculated in a logic controller, such as the Programmable Logic Controller (PLC)., Nous présentons une méthode de synthèse de la commande d'un système à événements discrets (SED). Cette méthode est une alternative à la technique de synthèse de la commande supervisée. La méthode part d'une spécification de la commande décrite en langage naturel et va jusqu'à l'implantation des fonctions de commande calculées dans un contrôleur logique, tel que l'Automate Programmable Industriel 'API).

We present a synthesis method for the control of discrte event systems (DES). This method is an alternative to the supervisory contol theory (SCT). The method uses a control specification described in natural language and finishes with the implantation of control functions calculated in a logic controller, such as the Programmable Logic Controller (PLC)., Nous présentons une méthode de synthèse de la commande d'un système à événements discrets (SED). Cette méthode est une alternative à la technique de synthèse de la commande supervisée. La méthode part d'une spécification de la commande décrite en langage naturel et va jusqu'à l'implantation des fonctions de commande calculées dans un contrôleur logique, tel que l'Automate Programmable Industriel 'API).