Search

National audience; We study the behaviour of Discrete Event Systems (DES) subjectto strong temporal constraints. We are more particularly interested in theformal verification of properties on the timed languages associated with theirexecutions. In this context, we focus on DES modelled using Time Petri Nets(TPN), an extension of classical Petri nets in which we can constrain the timeduring which transitions stay enabled.Our goal is to use and extend techniques borrowed from model-checkingin order to check properties related to the diagnosability of a system. To thisend, we study properties on the intersection of the timed languages of systems.Our approach is based on the definition of a new composition operator, thatwe call synchronous product, that constrain different transitions to fire at thesame time. This allows us to analyse the product of systems more directly,without the need to compute the intersection of their language at the level oftheir state spaces.Our main contribution is the definition of a new formal model, calledProduct TPN (PTPN), that includes our notion of synchronous product inits syntax. We show how to extend the notion of State Class Graphs toPTPN and use this construction to check the diagnosability of single faultson TPN. We also study the diagnosability of more complex behaviours, expressedusing patterns of events, and explore a restricted case of timed pattern.; Cette thèse porte sur l’étude des Systèmes à Événements Discrets(SED) soumis à des contraintes temporelles fortes, et plus précisément sur lavérification de propriétés liées aux langages associés à leurs exécutions. Dansce contexte, nous nous concentrons à l’étude des réseaux de Petri temporels(TPN) comme modèle pour la spécification des SED.L’objectif général est d’utiliser et d’étendre des méthodes issues du domainedu model-checking afin de répondre à des questions de diagnosticabilité.Pour ce faire, nous cherchons à vérifier des propriétés liées à l’intersectionentre les langages temporels (le comportement) de différent systèmes. Notreapproche repose sur la définition d’une nouvelle opération de produit synchroneentre TPN qui nous permet d’utiliser des techniques d’analyse plusdirectes. Ceci nous permet, en particulier, d’éviter de devoir calculer directementl’intersection entre langages au niveau des espaces d’état des systèmes.Notre contribution principale est la définition d’un nouveau modèle, lesProduct TPN (PTPN), qui internalise notre concept de produit synchroneentre transitions. Nous proposons une extension de la notion de graphes declasses au cas des PTPN et utilisons ce modèle pour vérifier la propriété dediagnosabilité sur les TPN dans le cas de fautes simples, mais également pourla diagnosticabilité de scénarios plus complexes, décrit sous la forme de motifs.

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.

This thesis proposes mathematical traffic models and control laws for metro lines with one junction. The models are based on the ones developed for linear metro lines (without junction) in [12, 14]. The train dynamics are described with a discrete event traffic model. Two time constraints are considered. The first one imposes lower bounds on the train run and dwell times. The second one fixes a lower bound on the safe separation time between two trains. A model of the train dynamics on the junction is proposed, as well as control laws for the train run and dwell times, as a function of the passenger travel demand. Most of these models are written as linear systems in the max-plus algebra (polynomial matrix algebra), which permits the characterization of the stationary regime, and the derivation of traffic phase diagrams., PhD thesis

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.

Various kinds of manufacturing systems can be modeled and analyzed by Timed EventGraphs (TEGs). These TEGs are a particular class of timed Discrete Event Systems (DESs), whose dynamic behavior is characterized only by synchronization and saturation phenomena. A major advantage of TEGs over many other timed DES models is that their earliest behavior can be described by linear equations in some tropical algebra structures called dioids. This has led to a broad theory for linear systems over dioids where many concepts of standard systems theory were introduced for TEGs. For instance, with the (max,+)-algebra linear state-space models for TEGs were established. These linear models provide an elegant way to do performance evaluation for TEGs. Moreover, based on transfer functions in dioids severalcontrol problems for TEGs were addressed. However, the properties of TEGs, and thus the systems which can be described by TEGs, are limited. To enrich these properties, two main extensions for TEGs were introduced. First,Weighted Timed Event Graphs (WTEGs) which, in contrast to ordinary TEGs, exhibit event-variant behaviors. InWTEGs integer weights are considered on the arcs whereas TEGs are restricted to unitary weights. For instance, these integer weights make it straightforward to model a cutting process in a production line. Second, a new kind of synchronization called partial synchronization (PS) was introduced forTEGs. PS is useful to model systems where specific events can only occur in a particular time window. For example, consider a crossroad controlled by a traffic light: the green phase of the traffic light provides a time window in which a vehicle is allowed to cross. Clearly, PS leads to time-variant behavior. As a consequence, WTEGs and TEGs under PS are not (max,+)-linear anymore.In this thesis, WTEGs and TEGs under PS are studied in a dioid structure. Based on these dioid models forWTEGs a decomposition of the dynamic behavior into an event-variant and an event-invariant part is proposed. Under some assumptions, it is shown that the eventvariant part is invertible. Hence, based on this model, optimal control and model reference control, which are well known for ordinary TEGs, are generalized to WTEGs. Similarly, a decomposition model is introduced for TEGs under PS in which the dynamic behavior is decomposed into a time-variant and time-invariant part. Again, under some assumptions, it is shown that the time-variant part is invertible. Subsequently, optimal control, as well as model reference control for TEGs under PS is addressed.; De nombreux systèmes de production peuvent être modélisés et analysés à l’aide de graphes d’événements temporisés (GET). Les GET forment une classe de systèmes à événements discrets temporisés (SEDT), dont la dynamique est définie uniquement par des phénomènes de synchronisation et de saturation. Un avantage majeur des GET par rapport à d’autres classes de SEDT est qu’ils admettent, sous certaines conditions, un modèle linéaire dans des espaces algébriques particuliers : les dioïdes. Ceci a conduit au développement d’une théorie des systèmes linéaires dans les dioïdes, grâce à laquelle de nombreux concepts de l’automatique classique ont été adaptés aux GET. Par exemple, l’algèbre (max,+) (i.e., le dioïde basé sur les opérations (max,+)) offre des techniques élégantes pour l’analyse et le contrôle de GET. Cependant, les conditions nécessaires pour modéliser un système à événements discrets par un GET sont très restrictives. Pour élargir la classe de systèmes concernés, deux extensions principales ont été développées. D’une part, les GET valués ont été introduits pour décrire des phénomènes d’assemblage et de séparation dans les systèmes de production. Cette extension se traduit par l’association de coefficients entiers aux arrêtes d’un graphe d’événements. Contrairement aux GET, ces systèmes ne sont pas invariants par rapport aux événements et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). D’autre part, la synchronisation partielle (PS) a été introduite pour modéliser des systèmes dans lesquels certains événements ne peuvent se produire que pendant des intervalles prédéfinis. Par exemple, dans une intersection réglée par un feu tricolore, une voiture peut traverser l’intersection lorsque le feu est vert. Contrairement aux GET, ces systèmes ne sont pas invariants dans le domaine temporel et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). Dans cette thèse, une modélisation des GET valués et des GET avec PS dans des dioïdes adaptés est présentée. A l’aide de ces dioïdes, une décompostion pour les GET valués (resp. GET avec PS) en un GET et une partie non-invariante dans le domaine des événements (resp. dans le domaine temporel) est introduite. Sous certaines conditions, la partie invariante est invertible. Dans ce cas, les modèles et contrôleurs pour le GET valué ou le GET sous PS peuvent être directement dérivés des modèles et contrôleurs obtenus pour le GET associé.

Various kinds of manufacturing systems can be modeled and analyzed by Timed Event Graphs (TEGs). These TEGs are a particular class of timed Discrete Event Systems (DESs), whose dynamic behavior is characterized only by synchronization and saturation phenomena. A major advantage of TEGs over many other timed DES models is that their earliest behavior can be described by linear equations in some tropical algebra structures called dioids. This has led to a broad theory for linear systems over dioids where many concepts of standard systems theory were introduced for TEGs. For instance, with the (max,+)-algebra linear state-space models for TEGs were established. These linear models provide an elegant way to do performance evaluation for TEGs. Moreover, based on transfer functions in dioids several control problems for TEGs were addressed. However, the properties of TEGs, and thus the systems which can be described by TEGs, are limited. To enrich these properties, two main extensions for TEGs were introduced. First, Weighted Timed Event Graphs (WTEGs) which, in contrast to ordinary TEGs, exhibit event-variant behaviors. In WTEGs integer weights are considered on the arcs whereas TEGs are restricted to unitary weights. For instance, these integer weights make it straightforward to model a cutting process in a production line. Second, a new kind of synchronization called partial synchronization (PS) was introduced for TEGs. PS is useful to model systems where specific events can only occur in a particular time window. For example, consider a crossroad controlled by a traffic light: the green phase of the traffic light provides a time window in which a vehicle is allowed to cross. Clearly, PS leads to time-variant behavior. As a consequence, WTEGs and TEGs under PS are not (max,+)-linear anymore. In this thesis, WTEGs and TEGs under PS are studied in a dioid structure. Based on these dioid models for WTEGs a decomposition of the dynamic behavior into an event-variant and an event-invariant part is proposed. Under some assumptions, it is shown that the event-variant part is "invertible". Hence, based on this model, optimal control and model reference control, which are well known for ordinary TEGs, are generalized to WTEGs. Similarly, a decomposition model is introduced for TEGs under PS in which the dynamic behavior is decomposed into a time-variant and time-invariant part. Again, under some assumptions, it is shown that the time-variant part is invertible. Subsequently, optimal control, as well as model reference control for TEGs under PS is addressed., Viele Produktions- und Fertigungsanlagen können mit Hilfe von Synchronisationsgraphen modelliert und analysiert werden. Diese Synchronisationsgraphen sind eine spezielle Klasse der zeitbehafteten Ereignisdiskreten Systemen, deren dynamisches Verhalten nur durch Synchronisations- und Sättigungsphänomene gekennzeichnet ist. Ein Vorteil dieser Synchronisationsgraphen gegenüber vielen anderen Modellen besteht darin, dass ihr schnellstes Verhalten durch lineare Gleichungen in einigen „tropischen“ Algebren, den sogenannten Dioiden, beschrieben werden kann. Dies hat zu der Entwicklung einer umfangreichen Theorie für lineare Systeme in Dioiden geführt, wobei viele Konzepte aus der Standard Systemtheorie auf Synchronisationsgraphen übertragen wurden. Zum Beispiel die (max,+) Algebra biete elegante Analyseverfahren und Reglerentwurfsverfahren für Synchronisationsgraphen. Allerdings ist die Systemklasse, die mit Hilfe von Synchronisationsgraphen beschrieben werden kann, eingeschränkt. Zum Beispiel lassen sich Fertigungsanlagen mit Gruppierungs- oder Vereinzelungsschritten nicht mit Synchronisationsgraphen modellieren. Daher wurden einige Erweiterungen für Synchronisationsgraphen eingeführt. Zum einen wurden die Kanten von Synchronisationsgraphen mit ganzzahligen Gewichten erweitert. Diese gewichteten Synchronisationsgraphen weisen im Gegensatz zu gewöhnlichen Synchronisationsgraphen ereignisvariantes Verhalten auf und ermöglichen es nun Gruppierungs oder Vereinzelungsschritte zu beschreiben. Des Weiteren wurde eine neue Art der Synchronisation namens partieller Synchronisation (PS) eingeführt. Diese PS ist nützlich für die Modellierung von zeitvarianten Systemen, bei denen bestimmte Ereignisse nur in einem bestimmten Zeitfenster auftreten können. Ein solches Verhalten tritt zum Beispiel an einer Kreuzung mit Ampelsteuerung auf, die Grünphase der Ampeln beschreibt das Zeitfenster, in dem ein Fahrzeug die Kreuzung überqueren darf. Aufgrund ihres ereignisvarianten bzw. zeitvarianten Verhalten können gewichteten Synchronisationsgraphen sowie Synchronisationsgraphen unter PS nicht mehr mit linearen Gleichungen in der (max,+) Algebra beschrieben werden. In dieser Arbeit werden gewichteten Synchronisationsgraphen und Synchronisationsgraphen unter PS in Dioiden modelliert. Basierend auf dieser Modellierung wird eine Zerlegung des dynamischen Verhaltens von gewichteten Synchronisationsgraphen in einen ereignisvarianten und einen ereignisinvarianten Teil vorgestellt. Analog wird für Synchronisationsgraphen unter PS gezeigt, dass ihr dynamisches Verhalten in einem zeitvarianten und zeitinvarianten Teil zerlegt werden kann. Unter speziellen Voraussetzungen wird gezeigt, dass dieser ereignisvarianten bzw. zeitvarianten Teile „invertierbar“ ist. Dies ermöglicht die Übertragung von etablierten Analyse- und Regelungsentwurfsverfahren von gewöhnlichen Synchronisationsgraphen auf die allgemeineren Klassen der gewichteten Synchronisationsgraphen und Synchronisationsgraphen unter PS., De nombreux systèmes de production peuvent être modélisés et analysés à l’aide de graphes d’événements temporisés (GET). Les GET forment une classe de systèmes à événements discrets temporisés (SEDT), dont la dynamique est définie uniquement par des phénomènes de synchronisation et de saturation. Un avantage majeur des GET par rapport à d’autres classes de SEDT est qu’ils admettent, sous certaines conditions, un modèle linéaire dans des espaces algébriques particuliers : les dioïdes. Ceci a conduit au développement d’une théorie des systèmes linéaires dans les dioïdes, grâce à laquelle de nombreux concepts de l’automatique classique ont été adaptés aux GET. Par exemple, l’algèbre (max,+) (i.e., le dioïde basé sur les opérations (max,+)) offre des techniques élégantes pour l’analyse et le contrôle de GET. Cependant, les conditions nécessaires pour modéliser un système à événements discrets par un GET sont très restrictives. Pour élargir la classe de systèmes concernés, deux extensions principales ont été développées. D’une part, les GET valués ont été introduits pour décrire des phénomènes d’assemblage et de séparation dans les systèmes de production. Cette extension se traduit par l’association de coefficients entiers aux arrêtes d’un graphe d’événements. Contrairement aux GET, ces systèmes ne sont pas invariants par rapport aux événements et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). D’autre part, la synchronisation partielle (PS) a été introduite pour modéliser des systèmes dans lesquels certains événements ne peuvent se produire que pendant des intervalles prédéfinis. Par exemple, dans une intersection réglée par un feu tricolore, une voiture peut traverser l’intersection lorsque le feu est vert. Contrairement aux GET, ces systèmes ne sont pas invariants dans le domaine temporel et ne peuvent donc pas être décrits par des équations linéaires dans l’algèbre (max,+). Dans cette thèse, une modélisation des GET valués et des GET avec PS dans des dioïdes adaptés est présentée. A l’aide de ces dioïdes, une décompostion pour les GET valués (resp. GET avec PS) en un GET et une partie non-invariante dans le domaine des événements (resp. dans le domaine temporel) est introduite. Sous certaines conditions, la partie invariante est "invertible". Dans ce cas, les modèles et contrôleurs pour le GET valué ou le GET sous PS peuvent être directement dérivés des modèles et contrôleurs obtenus pour le GET associé.

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é.

The automation degree of railway control systems is constantly increasing. Railway industry needs the enhanced level of safety and reliability guarantee to replace the drivers by Automatic Train Control (ATC) systems. However, the system complexity is also heavily increased by the integration of automatic functions, which has caused the difficulty to analyze these systems.Different modeling methods can be used to build the system models at the appropriate level of abstraction. Formal modeling methods and formal verification methods can provide crucial support to ensure safety and reliability properties. Petri Nets are a suitable tool for modeling and verifying critical systems such as automatic train control systems. In this thesis, we use more specifically Colored Petri Nets (CPNs) to exploit modularity and hierarchization for the modeling and verification of a large-scale system.; Le degré d'automatisation des systèmes de contrôle ferroviaire est en constante augmentation. Les industriels ferroviaires ont besoin d'un niveau accru de sécurité et de fiabilité pour remplacer les conducteurs par des systèmes de contrôle automatique des trains (ATC). Cependant, la complexité du système est également fortement augmentée par l'intégration des fonctions automatiques, ce qui rend difficile l'analyse de ces systèmes.Différentes méthodes de modélisation peuvent être utilisées pour construire les modèles du système au niveau d'abstraction approprié. Les méthodes de modélisation formelles et les méthodes de vérification formelles fournissent un cadre crucial pour assurer les propriétés de sécurité et de fiabilité. Les Réseaux de Petri constituent un outil formel approprié à la modélisation et à la vérification de systèmes critiques comme les systèmes de contrôle automatique du ferroviaire. Dans cette thèse, nous utilisons plus particulièrement les réseaux de Pétri colorés (CPNs) de Jensen pour exploiter la modularité et la hiérarchisation pour la modélisation et la vérification d’un système de grande taille

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

In this thesis, we analyze the dynamics of discrete event systems with synchronization and priorities, by the means of Petri nets and queueing networks.We apply this to the performance evaluation of an emergency call center.Our original motivation is practical. During the period of this work, a new emergency call center became operative in Paris area, handling emergency calls to police and firemen.The new organization includes a two-level call treatment. A first level of operators answers calls, identifies urgent calls and handles (numerous) non-urgent calls.Second level operators are specialists (policemen or firemen) and handle emergency demands.When a call is identified at level 1 as extremely urgent, the operator stays in line with the call until a level 2 operator answers. The call has priority for level 2 operators.A consequence of this procedure is that, when level 2 operators are busy, level 1 operators wait with extremely urgent calls, and the capacity of level 1 diminishes.We are interested in the performance evaluation of various systems corresponding to this general description, in stressed situations.We propose three different models addressing this kind of systems.The first two are timed Petri net models.We enrich the classical free choice Petri nets by allowing conflict situations in which the routing is solved by priorities.The main difficulty in this situation is that the operator of the dynamics becomes non monotone.In a first model, we consider discrete dynamics for this class of Petri nets, with constant holding times on places.We prove that the counter variables of an execution of the Petri net are solutions of a piecewise linear system with delays.As far as we know, this proof is new, even for the class of free choice nets, which is a subclass of ours.We investigate the stationary regimes of the dynamics, and characterize the affine ones as solutions of a piecewise linear system, which can be seen as a system over a tropical (min-plus) semifield of germs.Numerical experiments show that, however, convergence does not always holds towards these affine stationary regimes.The second model is a ``continuization'' of the previous one. For the same class of Petri nets, we propose dynamics expressed by differential equations, so that the tokens and time events become continue.For this differential system with discontinuous righthandside, we establish the existence and uniqueness of the solution.By using differential equations, we aim at obtaining a simpler model in which discrete time pathologies disappear. We show that the stationary regimes are the same as the stationary regimes of the discrete time dynamics.Numerical experiments tend to show that, in this setting, convergence effectively holds.We also model the emergency call center described above as a queueing system, taking into account the randomness of the different call center variables.For this system, we prove that, under an appropriate scaling, the dynamics converges to a fluid limit which corresponds to the differential equations of our Petri net model.This provides support for the second model.Stochastic calculus for Poisson processes, generalized Skorokhod formulations and coupling arguments are the main tools used to establish this convergence.Hence, our three models of an identical emergency call center yield the same schematic asymptotic behavior, expressed as a piecewise linear system of the parameters, and describing the different congestion phases of the system.In a second part of this thesis, simulations are carried out and analyzed, taking into account the many subtleties of our case study (for example, we construct probability distributions based on real data analysis).The simulations confirm the schematic behavior described by our mathematical models.We also address the complex interactions coming from the heterogeneous nature of level 2., Dans cette thèse, nous analysons la dynamique de systèmes à événements discrets avec synchronisation et priorités, au moyen de réseaux de Petri et de réseaux de files d'attente.Nous appliquons cela à l'évaluation de performance d'un centre d'appels d'urgence.Notre motivation de départ est pratique. Pendant la durée de ce travail, un nouveau centre d'appels d'urgence a été mis en place pour l'agglomération parisienne, traitant les appels pour la police et les pompiers.La nouvelle organisation traite les appels en deux niveaux.Un premier niveau d'opérateurs répond aux appels, identifie les appels urgents et traite les appels non urgents.Les opérateurs de second niveau sont spécialistes (policiers ou pompiers) et traitent les demandes d'intervention.Quand un appel est identifié au niveau 1 comme très urgent, l'opérateur reste en ligne avec l'appelant jusqu'à ce qu'un opérateur de niveau 2 réponde. De plus, l'appel est prioritaire.Une conséquence de cette procédure est que, lorsqu'aucun opérateur de niveau 2 n'est disponible, les opérateurs de niveau 1 attendent avec ces appels très urgents, et la capacité du niveau 1 diminue.Nous nous intéressons à l'évaluation de performance de divers systèmes correspondant à cette description générale, dans des situations de saturation.Nous proposons trois modèles différents pour traiter ce type de systèmes.Les deux premiers sont des modèles de réseaux de Petri temporisés.Nous enrichissons les classiques réseaux de Petri à choix libres en autorisant des situations de conflit où le routage est résolu par des priorités.La principale difficulté est alors que l'opérateur de la dynamique n'est plus monotone.Dans un premier modèle, nous proposons une dynamique discrète pour cette classe de réseaux de Petri, avec des temps de séjour constants sur les places.Nous prouvons que les variables compteurs d'une exécution du réseau sont les solutions d'un système affine par morceaux, avec retards.Nous étudions les régimes stationnaires de cette dynamique, et caractérisons les régimes affines comme solutoins d'un système affine par morceaux, qui peut être vu comme un système sur le semi-corps de germes tropical (min plus).Les applications numériques montrent cependant que la convergence ne se fait pas toujours vers ces régimes stationnaires affines.Le second modèle est une transformation continue du précédent. Pour la même classe de réseaux de Petri, nous proposons une dynamique sous forme d'équations différentielles discontinues.Nous établissons l'existence et l'unicité de la solution.L'objectif de cette modélisation est d'obtenir un système plus simple dans lequel les pathologies du temps discret disparaissent. Nous montrons que les régimes stationaires sont les mêmes que ceux de la dynamique discrète. Les simulations numériques semblent montrer que la convergence s'obtient effectivement dans ce cas.Nous modélisons aussi le centre d'appels d'urgence comme un réseau de files d'attente, prenant ainsi en compte le caractère aléatoire des différentes variables du centre d'appel.Pour ce système, nous prouvons que la dynamique, après une transformation d'échelle, converge vers une limite fluide, qui correspond au système d'équations différentielles précédent.Cela conforte notre seconde modélisation.Les principaux outils de la preuve de convergence sont le calcul stochastique pour les processus de Poisson, les formulations de Skorokhod généralisées, ou encore des arguments de couplage.Ainsi, nos trois modèles d'un même centre d'appels d'urgence définissent un même comportement asymptotique schématique, décrivant différentes phases de congestion du centre.Dans une seconde partie de cette thèse, nous analysons des simulations poussées, prenant en compte les nombreux détails de notre étude de cas. Les simulations confirment le comportement schématique prédit par nos modèles mathématiques. Nous discutons aussi des interactions complexes provenant de la nature hétérogène du niveau 2.

Complex systems are omnipresent in our lives, but subject to failures that it is important to detect or predict. Discrete event system (DES) modeling is a natural way to represent and study such systems. Thus a system can be described by a set of states such that its current state is obtained after firing a sequence of events. These events are predefined in a finite set and can be fired spontaneously in the system. Not all these events are observable/measurable and some of them are considered faulty, thus they model an abnormal change between two system states.The diagnosis process in DES aims at determining with certainty if the system is currently in a faulty state or in a normal one, i.e., if an abnormal change of a system state has occurred or not. To this end, a system observer has only the sequence of observable events to decide the current status of the system state. However this state might be currently ambiguous (normal or faulty) according to the available observations. Moreover it can be permanently ambiguous! The possibility to disambiguate it using a finite number of observations is called the diagnosability of a faulty event occurrence. The fault is diagnosable if all its occurrences are diagnosable and the system is diagnosable if all its faults are diagnosable. Similarly, the possibility to predict a future occurrence of a fault using its preceding observable events is called the predictability of a faulty event occurrence. Both problems of diagnosability and predictability can be generalized to study the diagnosability or the predictability of a pattern of events, i.e., an extension-closed language represented by a finite state machine. This thesis considers in its first part the problems of checking event diagnosability, event predictability and pattern diagnosability in centralized and distributed (with observable or unobservable synchronous communication events) discrete event systems, using SAT solvers. Thus we have encoded them as SAT problems, studied incremental SAT variants and provided experimental results that prove the scalability and flexibility of this approach. In the second part, we have introduced the diagnosability planning problem. This problem consists in finding a plan of actions (intentional/designful predefined events) that ensures, when applied on a set of potential current system states called a current belief state, to drive the system in a diagnosable belief state from which it can be left to run freely (without control actions). This problem can arise after an external intervention on the system, like the application of a repair plan after a fault detection.Thus this approach can ensure the possibility to detect the system further faults. We analyzed this problem, proved its PSpace-completeness and proposed three methods to find the intended plan that we compared on a benchmark created for this purpose.; Les systèmes complexes sont omniprésents dans nos vies, mais sujet à des pannes qu’il est important de détecter ou de prédire. Leur modélisation comme des systèmes à événements discrets (SED) est un moyen naturel de les représenter pour les étudier. Ainsi, un système peut être décrit par un ensemble d'états tels que son état actuel est obtenu après avoir déclenché une séquence d'événements. Ces événements sont prédéfinis dans un ensemble fini et peuvent être déclenchés spontanément dans le système. Tous ces événements ne sont pas observables / mesurables et certains d'entre eux sont considérés comme fautifs, donc ils modélisent un changement anormal entre deux états du système.Le processus de diagnostic de SED a pour but de déterminer avec certitude si le système est actuellement dans un état défectueux ou dans un état normal, c'est-à-dire si un changement anormal d'un état du système s'est produit ou non. À cette fin, un observateur de système ne dispose que de la séquence d'événements observables pour décider le diagnostic de l'état actuel du système. Cependant, cet état peut être ambigu (normal ou défectueux) en fonction des observations disponibles. En outre, il peut être définitivement ambigu ! La possibilité de le désambiguïser en utilisant un nombre fini d'observations est appelée la diagnosticabilité d'une occurrence d'événement fautif. La faute est diagnosticable si toutes ses occurrences le sont et le système est diagnosticable si toutes ses fautes le sont. De même, la possibilité de prédire une occurrence future d'une faute en utilisant les événements observables la précédant est appelée la prédictabilité d'un événement fautif. Les deux problèmes de la diagnosticabilité et de la prédictabilité d'un événement peuvent être généralisés pour étudier celles d'un motif d’événements, soit un langage clos par extension représenté par une machine à états finis.Cette thèse considère dans sa première partie les problèmes de vérification de la diagnosticabilité et de la prédictabilité d'un événements fautif et de la diagnosticabilité d'un motif d'événements dans les systèmes à événements discrets centralisés et distribués (avec des événements de communication synchrone observables ou non), à l'aide de solveurs SAT. Ainsi, nous les avons encodés comme des problèmes SAT, avons étudié des variantes incrémentales et fourni des résultats expérimentaux qui prouvent le passage à l’échelle et la flexibilité de cette approche. Dans la deuxième partie, nous avons introduit le problème de la planification de la diagnosticabilité. Ce problème consiste à trouver un plan d'actions (une séquence d'événements intentionnels prédéfinis à la conception) qui garantit, lorsqu'il est appliqué à un ensemble donné d'états potentiels du système actuel appelé état courant de croyances, de conduire le système dans un état de croyances diagnosticable d’où on peut le laisser s'exécuter librement (sans les actions de contrôle). Ce problème peut survenir après une intervention externe sur le système, comme par exemple l'application d'un plan de réparation après la détection d'une faute. Ainsi, cette approche peut garantir la possibilité de détecter d'autres futures fautes du système. Nous avons analysé ce problème et prouvé qu’il est PSpace-complet puis nous avons proposé trois méthodes pour engendrer un plan diagnosticable, que nous avons comparées sur un banc d’essais créé à cette fin.

Complex systems are omnipresent in our lives, but subject to failures that it is important to detect or predict. Discrete event system (DES) modeling is a natural way to represent and study such systems. Thus a system can be described by a set of states such that its current state is obtained after firing a sequence of events. These events are predefined in a finite set and can be fired spontaneously in the system. Not all these events are observable (measurable) and some of them are considered faulty, thus they model an abnormal change between two system states. The diagnosis process in DES aims at determining with certainty if the system is currently in a faulty state or in a normal one, i.e., if an abnormal change of a system state has occurred or not. To this end, a system observer has only the sequence of observable events to decide the current status of the system state. However this state might be currently ambiguous (normal or faulty) according to the available observations. Moreover it can be permanently ambiguous! The possibility to disambiguate it using a finite number of observations is called the diagnosability of a faulty event occurrence. The fault is diagnosable if all its occurrences are diagnosable and the system is diagnosable if all its faults are diagnosable. Similarly, the possibility to predict a future occurrence of a fault using its preceding observable events is called the predictability of a faulty event occurrence. Both problems of diagnosability and predictability can be generalized to study the diagnosability or the predictability of a pattern of events, i.e., an extension-closed language represented by a finite state machine.This thesis considers in its first part the problems of checking event diagnosability, event predictability and pattern diagnosability in centralized and distributed (with observable or unobservable synchronous communication events) discrete event systems, using SAT solvers. Thus we have encoded them as SAT problems, studied incremental SAT variants and provided experimental results that prove the scalability and flexibility of this approach. In the second part, we have introduced the diagnosability planning problem. This problem consists in finding a plan of actions (intentional/designful predefined events) that ensures, when applied on a set of potential current system states (called a current belief state), to drive the system in a diagnosable belief state from which it can be left to run freely (without control actions). This problem can arise after an external intervention on the system, like the application of a repair plan after a fault detection.Thus this approach can ensure the possibility to detect the system further faults. We analyzed this problem, proved its PSpace-completeness and proposed three methods to find the intended plan that we compared on a benchmark created for this purpose.; Les systèmes complexes sont omniprésents dans nos vies, mais sujet à des pannes qu’il est important de détecter ou de prédire. Leur modélisation comme des systèmes à événements discrets (SED) est un moyen naturel de les représenter pour les étudier. Ainsi, un système peut être décrit par un ensemble d'états tels que son état actuel est obtenu après avoir déclenché une séquence d'événements. Ces événements sont prédéfinis dans un ensemble fini et peuvent être déclenchés spontanément dans le système. Tous ces événements ne sont pas observables / mesurables et certains d'entre eux sont considérés comme fautifs, donc ils modélisent un changement anormal entre deux états du système. Le processus de diagnostic de SED a pour but de déterminer avec certitude si le système est actuellement dans un état défectueux ou dans un état normal, c'est-à-dire si un changement anormal d'un état du système s'est produit ou non. À cette fin, un observateur de système ne dispose que de la séquence d'événements observables pour décider le diagnostic de l'état actuel du système. Cependant, cet état peut être ambigu (normal ou défectueux) en fonction des observations disponibles. En outre, il peut être définitivement ambigu ! La possibilité de le désambiguïser en utilisant un nombre fini d'observations est appelée la diagnosticabilité d'une occurrence d'événement fautif. La faute est diagnosticable si toutes ses occurrences le sont et le système est diagnosticable si toutes ses fautes le sont. De même, la possibilité de prédire une occurrence future d'une faute en utilisant les événements observables la précédant est appelée la prédictabilité d'un événement fautif. Les deux problèmes de la diagnosticabilité et de la prédictabilité d'un événement peuvent être généralisés pour étudier celles d'un motif d’événements, soit un langage clos par extension représenté par une machine à états finis. Cette thèse considère dans sa première partie les problèmes de vérification de la diagnosticabilité et de la prédictabilité d'un événement fautif et de la diagnosticabilité d'un motif d'événements dans les systèmes à événements discrets centralisés et distribués (avec des événements de communication synchrone observables ou non), à l'aide de solveurs SAT. Ainsi, nous les avons encodés comme des problèmes SAT, avons étudié des variantes incrémentales et fourni des résultats expérimentaux qui prouvent le passage à l’échelle et la flexibilité de cette approche. Dans la deuxième partie, nous avons introduit le problème de la planification de la diagnosticabilité. Ce problème consiste à trouver un plan d'actions (une séquence d'événements intentionnels prédéfinis à la conception) qui garantit, lorsqu'il est appliqué à un ensemble donné d'états potentiels du système actuel appelé état courant de croyances, de conduire le système dans un état de croyances diagnosticable d’où on peut le laisser s'exécuter librement (sans les actions de contrôle). Ce problème peut survenir après une intervention externe sur le système, comme par exemple l'application d'un plan de réparation après la détection d'une faute. Ainsi, cette approche peut garantir la possibilité de détecter d'autres futures fautes du système. Nous avons analysé ce problème et prouvé qu’il est PSpace-complet puis nous avons proposé trois méthodes pour engendrer un plan diagnosticable, que nous avons comparées sur un banc d’essais créé à cette fin.

This PhD thesis deals with fault diagnosis of discrete-event systems modeled as finite state automata with some extensions to bounded Petri net models. The developed contributions can be classified regarding two pioneering approaches from the literature: the diagnoser-based technique and the twin-plant based technique. Regarding the diagnoser-based technique, we propose a new diagnoser variant with some interesting features that allow us to reformulate a necessary and sufficient condition for diagnosability of permanent faults and propose a systematic procedure for checking such a condition without building any intermediate model. An on-the-fly algorithm, for simultaneously constructing the diagnoser and verifying diagnosability is then developed. The established diagnoser is then extended to deal with fault diagnosis of intermittent faults. A Hybrid version (in the sense of combining enumerative and symbolic representations) of our diagnoser is also established in order to deal with fault diagnosis of labeled bounded Petri nets. The developed approaches are implemented in dedicated tools and evaluated through benchmarks with respect to the reference approaches in the domain.Regarding twin-plant based technique, our contribution consists in elaborating a model-checking framework that extends the Cimatti's work for the actual verification of various diagnosability concepts pertaining to permanent and intermittent failures based on the twin-plant structure. The main idea is to reformulate and express the diagnosability issues as temporal logics and then to tackle them using the model-checking engines.; L'objet de cette thèse porte sur le diagnostic des systèmes à évènements discrets modélisés par des automates à états finis, avec une extension vers les réseaux de Petri bornés et étiquetés. Les différentes contributions de ce travail peuvent être présentées selon deux volets, au regard des approches pionnières existantes dans la littérature: le diagnostic à base de diagnostiqueur, et le diagnostic à base de twin-plant. Sur le premier volet, i.e., le diagnostic à base de diagnostiqueur, nous proposons une variante du diagnostiqueur avec une nouvelle structure qui nous permet de: (i) formuler une nouvelle condition nécessaire et suffisante pour l'analyse de la diagnosticabilité des fautes permanentes, (ii) développer une procédure systématique pour l'analyse de la diagnosticabilité (iii) établir un algorithme à-la-volée pour construire le diagnostiqueur et analyser la diagnosticabilité en parallèle. Une extension de notre diagnostiqueur pour traiter des fautes intermittentes. Une version hybride de notre diagnostiqueur, pour analyser la diagnosticabilité des réseaux de Petri bornés et étiquetés. Sur le deuxième volet, i.e., le diagnostic à base de twin-plant, nous proposons de nouvelles techniques pour l'analyse de diagnosticabilité de fautes permanentes et intermittentes dans le cadre de vérification par model-checking. Ainsi, la performance des techniques de model-checking et des outils associés peut être exploitée pour traiter des questions de diagnostic.

This work is in the context of the theory of linear Systems in the dioids. The initial motivation of this study was to contribute to the analysis and control of max-plus linear systems, specifically using a geometric approach. The contribution of this thesis focuses on two issues. The first part is dedicated to study of the relationship between the concepts of controlled invariance and dynamic state feedback controlled invariance in a semi-ring. This relationship allows us to show the equivalence of these two concepts. The second part relates to a new problem in the theory of max-plus linear systems, it is the synthesis, with a geometric approach, of a static state feedback control law, in order to satisfy a set of specifications that apply to the state space of the system. This is specifically to control of discrete event systems described by a linear model in max-plus. We define and characterize the set of admissible initial conditions, which are the cause of non-decreasing solutions. Temporal restrictions on the system state space are described by the semi-module defined by the image of the Kleene star of the matrix associated with time restrictions. The geometric properties of this semi-module are studied. Sufficient conditions for the existence of a causal control law by static feedback are presented. Calculating causal control laws is also presented. To illustrate the application of this approach, two control problems are presented.; Le travail présenté s'inscrit dans le contexte de la théorie des systèmes linéaires dans les dioïdes. La motivation initiale de cette étude a été de contribuer à l'analyse et la commande de systèmes linéaires dans max-plus en utilisant spécifiquement une approche géométrique. La contribution de cette thèse est centrée sur deux problèmes. La première partie est dédiée à l'étude de la relation entre les notions d'invariance contrôlée et d'invariance contrôlée par retour d'état dynamique dans un semi-anneau. Cette relation permet de montrer l'équivalence de ces deux notions. La deuxième partie concerne un problème original dans la théorie des systèmes linéaires dans max-plus, il s'agit de la synthèse d'une loi de commande par retour d'état, qui permette de satisfaire un ensemble de spécifications exprimées sous la forme de restrictions sur l'état du système, avec une approche géométrique. Il s'agit plus précisément de commander des systèmes à événements discrets décrits par un modèle linéaire dans max-plus. Nous définissons et caractérisons l'ensemble des conditions initiales admissibles, lesquelles sont à l'origine de solutions non décroissantes. Les restrictions temporelles imposées à l'espace d'état du système sont décrites par le semi-module défini par l'image de l'étoile de Kleene de la matrice associée aux restrictions temporelles. Les propriétés géométriques de ce semi-module permettant de garantir que l'évolution du système en boucle fermée satisfasse les restrictions sont étudiées. Des conditions suffisantes concernant l'existence d'une loi de commande causale par retour d'état statique sont présentées. Le calcul des lois de commande causales est également présenté. Pour illustrer l'application de cette approche, deux problèmes de commande sont présentés.

This PhD thesis deals with fault diagnosis of discrete-event systems modeled as finite state automata with some extensions to bounded Petri net models. The developed contributions can be classified regarding two pioneering approaches from the literature: the diagnoser-based technique and the twin-plant based technique. Regarding the diagnoser-based technique, we propose a new diagnoser variant with some interesting features that allow us to reformulate a necessary and sufficient condition for diagnosability of permanent faults and propose a systematic procedure for checking such a condition without building any intermediate model. An on-the-fly algorithm, for simultaneously constructing the diagnoser and verifying diagnosability is then developed. The established diagnoser is then extended to deal with fault diagnosis of intermittent faults. A Hybrid version (in the sense of combining enumerative and symbolic representations) of our diagnoser is also established in order to deal with fault diagnosis of labeled bounded Petri nets. The developed approaches are implemented in dedicated tools and evaluated through benchmarks with respect to the reference approaches in the domain.Regarding twin-plant based technique, our contribution consists in elaborating a model-checking framework that extends the Cimatti's work for the actual verification of various diagnosability concepts pertaining to permanent and intermittent failures based on the twin-plant structure. The main idea is to reformulate and express the diagnosability issues as temporal logics and then to tackle them using the model-checking engines., L'objet de cette thèse porte sur le diagnostic des systèmes à évènements discrets modélisés par des automates à états finis, avec une extension vers les réseaux de Petri bornés et étiquetés. Les différentes contributions de ce travail peuvent être présentées selon deux volets, au regard des approches pionnières existantes dans la littérature: le diagnostic à base de diagnostiqueur, et le diagnostic à base de twin-plant. Sur le premier volet, i.e., le diagnostic à base de diagnostiqueur, nous proposons une variante du diagnostiqueur avec une nouvelle structure qui nous permet de: (i) formuler une nouvelle condition nécessaire et suffisante pour l'analyse de la diagnosticabilité des fautes permanentes, (ii) développer une procédure systématique pour l'analyse de la diagnosticabilité (iii) établir un algorithme à-la-volée pour construire le diagnostiqueur et analyser la diagnosticabilité en parallèle. Une extension de notre diagnostiqueur pour traiter des fautes intermittentes. Une version hybride de notre diagnostiqueur, pour analyser la diagnosticabilité des réseaux de Petri bornés et étiquetés. Sur le deuxième volet, i.e., le diagnostic à base de twin-plant, nous proposons de nouvelles techniques pour l'analyse de diagnosticabilité de fautes permanentes et intermittentes dans le cadre de vérification par model-checking. Ainsi, la performance des techniques de model-checking et des outils associés peut être exploitée pour traiter des questions de diagnostic.

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.

International audience; This paper presents a random generator of discrete event systems that are by construction k-diagnosable. The aim of this generator is to provide an almost infinite set of diagnosable systems for creating benchmarks. The goal of such benchmarks is to provide a solid set of examples to test and compare algorithms that solve many problems around diagnosable discrete event systems.

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 uncertain contexts in which recent WSN embedded applications evolve have bigimpact on these applications. Traditionally, the objective of availability generally doubleshardware and functional redundancy; it means that the overhead is doubled in term ofenergy and cost. Besides, wireless node system is powered by limited battery; hencepower consumption parameter is only set to a number of components and functionalitiesat minimum resources. However, due to the technology reduction, process variabilityconducts to increase the possibility of failures. In order to guarantee an acceptablequality of service for the users, and on the operating lifetime of the system, it should carrystudies at the upper phases involving both dependability and consumption constraints.This thesis aims to propose novel design for wireless sensor networks, in order to reduceenergy consumption and to increase network dependability., Le contexte incertain dans lequel évoluent les applications embarquées influencefortement ces dernières. L'objectif de disponibilité induit généralement une forteredondance matérielle et fonctionnelle. A l'inverse, le paramètre de consommation prôneun nombre et un fonctionnement à minima des ressources. Avec la réduction de latechnologie, la variabilité des procédés de fabrication induit la possibilité accrue dedéfaillances. De façon à garantir une qualité de service acceptable par l'utilisateur, et cesur la totalité de la durée de vie du circuit, il convient de mener des études associant dèsles phases amont les deux paramètres sûreté de fonctionnement et consommation. Cettethèse a pour objectif de proposer une nouvelle conception pour les réseaux de capteurssans fil, afin de réduire consommation d'énergie et d'augmenter la fiabilité du réseau.

In den meisten Industrieländern ist die Lebenserwartung in den letzten Jahrzehnten fortlaufend gestiegen und wird höchstwahrscheinlich noch weiter steigen. Dieser Anstieg führt zu neuen Herausforderungen hinsichtlich der Autonomie und Unabhängigkeit von älteren Menschen. Die Entwicklung von intelligenten Wohnungen ist ein Weg diesen Herausforderungen zu begegnen und es den Menschen zu ermöglichen länger in einer sicheren und komfortablen Umgebung zu leben. Dazu stattet man solcheWohnungen mit Sensoren, Aktoren sowie einem Controller aus. Dies erm öglicht es, in Abhängigkeit vom Verhalten der Bewohner, dieWohnumgebung so zu beein_ussen, dass sich Sicherheit, Gesundheit und Komfort verbessern. Ansätze, die dies zum Ziel haben, basieren meistens auf Methoden, die es ermöglichen Menschen innerhalb ihrer Wohnung in Echtzeit zu lokalisieren. In dieser Dissertation wird daher ein neuer Ansatz für eine modellbasierte Lokalisierung einer a priori unbekannten Anzahl von Bewohnern vorgestellt. Dieser Ansatz fuÿt auf der Theorie, den Paradigmen und den Werkzeugen aus dem Gebiet der ereignisdiskreten Systeme. Es werden endliche Automaten eingesetzt, um die von den Sensoren erfassbaren Bewohnerbewegungen zu modellieren. Verschiedene Verfahren zur Erzeugung solcher Automaten werden gezeigt. Basierend auf diesen Modellen warden Algorithmen de_niert, mittels derer die Bewohner wirksam lokalisiert werden können. Abschlieÿend werden Methoden vorgeschlagen, die dazu dienen die Relevanz der Sensorinstrumentierung für die Lokalisierung zu bewerten. Die entwickelten Verfahren werden in der Dissertation durchgehend anhand von Fallbeispielen erläutert. Der gesamte Ansatz wurde implementiert und erprobt., Life expectancy has continuously increased in most countries over the last decades and will probably continue to increase in the future. This leads to new challenges relative to the autonomy and the independence of elderly. The development of Smart Homes is a direction to face these challenges and to enable people to live longer in a safe and comfortable environment. Making a home smart consists in placing sensors, actuators and a controller in the house in order to take into account the behavior of their inhabitants and to act on their environment to improve their safety, health and comfort. Most of these approaches are based on the real-time indoor Location Tracking of the inhabitants. In this thesis, a whole new approach for model-based Location Tracking of an a priori unknown number of inhabitants is proposed. This approach is based on Discrete Event Systems paradigms, theory and tools. The usage of Finite Automata (FA) to model the detectable motion of the inhabitants as well as different methods to create such FA models have been developed. Based on these models, algorithms to perform efficient Location Tracking are defined. Finally, several approaches aiming at evaluating the relevance of the instrumentation of a Smart Home with the objective of Location Tracking are proposed. The approach has also been fully implemented and tested. Throughout the thesis, the different contributions are illustrated on case studies., L'espérance de vie a augmenté dans les dernières décennies et devrait continuer à croître dans les prochaines années. Cette augmentation entraîne de nouveaux défis concernant l'autonomie et l'indépendance des personnes âgées. Le développement d'habitats intelligents est une piste pour répondre à ces défis et permettre aux personnes de vivre plus longtemps dans un environnement sûr et confortable. Rendre un habitat intelligent consiste à y installer des capteurs, des actionneurs et un contrôleur afin de pouvoir prendre en compte le comportement de ses habitants et agir sur leur environnement, pour améliorer leur sécurité, leur santé et leur confort. La plupart de ces approches s'appuient sur la localisation en temps réel des habitants dans leur habitat. Dans cette thèse, une nouvelle approche complète permettant la localisation d'un nombre a priori inconnu d'habitants basée sur le modèle est proposée. Cette approche tire parti des paradigmes, de la théorie et des outils des Systèmes à Événements Discrets. L'utilisation des automates à états finis pour modéliser le mouvement détectable des habitants ainsi que des méthodes permettant de construire ces modèles ont été développées. A partir de ces modèles automates finis, plusieurs algorithmes permettant de localiser de manière efficace les habitants ont été définis. Enfin, plusieurs approches pour l'évaluation des performances de l'instrumentation d'un habitat intelligent pour un objectif de localisation ont été proposées. La méthode a également été totalement implémentée et mise à l'épreuve. Tout au long de cette thèse, les différentes contributions sont illustrées à l'aide de cas d'étude.

In den meisten Industrieländern ist die Lebenserwartung in den letzten Jahrzehnten fortlaufend gestiegen und wird höchstwahrscheinlich noch weiter steigen. Dieser Anstieg führt zu neuen Herausforderungen hinsichtlich der Autonomie und Unabhängigkeit von älteren Menschen. Die Entwicklung von intelligenten Wohnungen ist ein Weg diesen Herausforderungen zu begegnen und es den Menschen zu ermöglichen länger in einer sicheren und komfortablen Umgebung zu leben. Dazu stattet man solcheWohnungen mit Sensoren, Aktoren sowie einem Controller aus. Dies erm öglicht es, in Abhängigkeit vom Verhalten der Bewohner, dieWohnumgebung so zu beein_ussen, dass sich Sicherheit, Gesundheit und Komfort verbessern. Ansätze, die dies zum Ziel haben, basieren meistens auf Methoden, die es ermöglichen Menschen innerhalb ihrer Wohnung in Echtzeit zu lokalisieren. In dieser Dissertation wird daher ein neuer Ansatz für eine modellbasierte Lokalisierung einer a priori unbekannten Anzahl von Bewohnern vorgestellt. Dieser Ansatz fuÿt auf der Theorie, den Paradigmen und den Werkzeugen aus dem Gebiet der ereignisdiskreten Systeme. Es werden endliche Automaten eingesetzt, um die von den Sensoren erfassbaren Bewohnerbewegungen zu modellieren. Verschiedene Verfahren zur Erzeugung solcher Automaten werden gezeigt. Basierend auf diesen Modellen warden Algorithmen de_niert, mittels derer die Bewohner wirksam lokalisiert werden können. Abschlieÿend werden Methoden vorgeschlagen, die dazu dienen die Relevanz der Sensorinstrumentierung für die Lokalisierung zu bewerten. Die entwickelten Verfahren werden in der Dissertation durchgehend anhand von Fallbeispielen erläutert. Der gesamte Ansatz wurde implementiert und erprobt., Life expectancy has continuously increased in most countries over the last decades and will probably continue to increase in the future. This leads to new challenges relative to the autonomy and the independence of elderly. The development of Smart Homes is a direction to face these challenges and to enable people to live longer in a safe and comfortable environment. Making a home smart consists in placing sensors, actuators and a controller in the house in order to take into account the behavior of their inhabitants and to act on their environment to improve their safety, health and comfort. Most of these approaches are based on the real-time indoor Location Tracking of the inhabitants. In this thesis, a whole new approach for model-based Location Tracking of an a priori unknown number of inhabitants is proposed. This approach is based on Discrete Event Systems paradigms, theory and tools. The usage of Finite Automata (FA) to model the detectable motion of the inhabitants as well as different methods to create such FA models have been developed. Based on these models, algorithms to perform efficient Location Tracking are defined. Finally, several approaches aiming at evaluating the relevance of the instrumentation of a Smart Home with the objective of Location Tracking are proposed. The approach has also been fully implemented and tested. Throughout the thesis, the different contributions are illustrated on case studies., L'espérance de vie a augmenté dans les dernières décennies et devrait continuer à croître dans les prochaines années. Cette augmentation entraîne de nouveaux défis concernant l'autonomie et l'indépendance des personnes âgées. Le développement d'habitats intelligents est une piste pour répondre à ces défis et permettre aux personnes de vivre plus longtemps dans un environnement sûr et confortable. Rendre un habitat intelligent consiste à y installer des capteurs, des actionneurs et un contrôleur afin de pouvoir prendre en compte le comportement de ses habitants et agir sur leur environnement, pour améliorer leur sécurité, leur santé et leur confort. La plupart de ces approches s'appuient sur la localisation en temps réel des habitants dans leur habitat. Dans cette thèse, une nouvelle approche complète permettant la localisation d'un nombre a priori inconnu d'habitants basée sur le modèle est proposée. Cette approche tire parti des paradigmes, de la théorie et des outils des Systèmes à Événements Discrets. L'utilisation des automates à états finis pour modéliser le mouvement détectable des habitants ainsi que des méthodes permettant de construire ces modèles ont été développées. A partir de ces modèles automates finis, plusieurs algorithmes permettant de localiser de manière efficace les habitants ont été définis. Enfin, plusieurs approches pour l'évaluation des performances de l'instrumentation d'un habitat intelligent pour un objectif de localisation ont été proposées. La méthode a également été totalement implémentée et mise à l'épreuve. Tout au long de cette thèse, les différentes contributions sont illustrées à l'aide de cas d'étude.

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; 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é.

Automated planning is a field of artificial intelligence that aims at proposing methods to chose and order sets of actions with the objective of reaching a given goal. A sequence of actions solving a planning problem is usually called a plan. In many cases, one does not only have to find a plan but an optimal one. This notion of optimality can be defined by assigning costs to actions. An optimal plan is then a plan minimizing the sum of the costs of its actions. Planning problems are standardly solved using algorithms such as A* that search for minimum cost paths in graphs. In this thesis we focus on a particular approach to planning called factored planning or modular planning. The idea is to consider a decomposition of a planning problem into almost independent sub-problems (or components). One then searches for plans into each component and try to assemble these local plans into a global plan for the original planning problem. The main interest of this approach is that, for some classes of planning problems, the components considered can be planning problems much simpler to solve than the original one. First, we present a study of the use of some message passing algorithms for factored planning. In this case the components of a problem are represented by weighted automata. This allows to handle all plans of a sub-problems, and permits to perform factored cost-optimal planning. Achieving cost-optimality of plans was not possible with previous factored planning methods. This approach is then extended by using approximate resolution techniques ("turbo" algorithms) and by proposing another representation of components for handling actions which read-only in some components. Then we describe another approach to factored planning: a distributed version of the famous A* algorithm. Each component is managed by an agent which is responsible for finding a local plan in it. For that, she uses information about her own component, but also information about the rest of the problem, transmitted by the other agents. The main difference between this approach and the previous one is that it is not only modular but also distributed.; La planification est un domaine de l'intelligence artificielle qui a pour but de proposer des méthodes permettant d'automatiser la recherche et l'ordonnancement d'ensembles d'actions afin d'atteindre un objectif donné. Un ensemble ordonné d'actions solution d'un problème de planification est appelé un plan. Parfois, les actions disponibles peuvent avoir un coût - on souhaite alors trouver des plans minimisant la somme des coûts des actions les constituant. Ceci correspond en fait à la recherche d'un chemin de coût minimal dans un graphe, et est donc traditionnellement résolu en utilisant des algorithmes tels que A*. Dans cette thèse, nous nous intéressons à une approche particulière de la planification, dite factorisée ou modulaire. Il s'agit de décomposer un problème en plusieurs sous-problèmes (généralement appelés composants) le plus indépendants possibles, et d'assembler des plans pour ces sous-problèmes en un plan pour le problème d'origine. L'intérêt de cette approche est que, pour certaines classes de problèmes de planification, les composants peuvent être bien plus simples à résoudre que le problème initial. Dans un premier temps, nous présentons une méthode de planification factorisée basée sur l'utilisation d'algorithmes dits à passage de messages. Une représentation des composants sous forme d'automates à poids nous permet de capturer l'ensemble des plans d'un sous-problème, et donc de trouver des plans de coût minimal, ce que ne permettaient pas les approches précédentes de la planification factorisée. Cette première méthode est ensuite étendue~: en utilisant des algorithmes dits « turbos », permettant une résolution approchée des problèmes considérés, puis en proposant une représentation différente des sous-problèmes, afin de prendre en compte le fait que certaines actions ne font que lire dans un composant. Ensuite, nous proposons une autre approche de la planification factorisée, basée sur une version distribuée de l'algorithme A*. Dans chaque composant, un agent réalise la recherche d'un plan local en utilisant sa connaissance du sous-problème qu'il traite, ainsi que des informations transmises par les autres agents. La principale différence entre cette méthode et la précédente est qu'il s'agit d'une approche distribuée de la planification modulaire.