Diagnosability and diagnosabilisation of time patterns in time Petri nets
Diagnosticabilité et diagnosticabilisation de motifs temporels dans les réseaux de Petri temporels
Résumé
Diagnosability is the property of a system to produce sufficient observations (via sensors) to differentiate nominal behaviour from faulty behaviour. It is possible for a diagnosable system to produce a certain diagnosis for a given fault, with the observable information returned by the system being different depending on whether or not a fault has occurred. Verifying such a property on a system is therefore an important step in the process of building fault detection and isolation algorithms. This problem has been studied extensively in atemporal Discrete Event Systems (DES) (STL, Petri nets, etc.) and in temporal DES models (timed automata, time Petri nets, etc.), both for simple faults (modelled by the occurrence of a single event) and for more complex behaviour called fault patterns.In this work we propose a method for analysing the diagnosability of time Petri nets for a new type of fault called a time pattern. Time patterns consist of the occurrence of different temporally constrained events. This method is based on an abstraction of the language prefixes of a time Petri net in the form of polyhedra, which constitutes the first contribution of this thesis.The second contribution of this work is a necessary and sufficient condition for diagnosability, which makes it possible to check whether a system is diagnosable for a temporal reason, and to provide structural explanations for non-diagnosability if necessary. This method is based on the analysis of the polyhedra of the abstraction presented, which are divided into different zones sharing common diagnosis properties. From this analysis of zones, a graph is synthesised grouping together the different sources of ambiguity in the different executions of the system under study.The final contribution of this work is a verification method for the time diagnosabilisation problem, which consists of parameterising the static intervals of the initial time Petri net and finding values for these parameters for which the net thus generated is diagnosable for the pattern under study. We propose a method for verifying this property that guarantees certain properties of the generated time Petri net. This verification method is based on the polyhedral abstraction mentioned above, and consists of constructing sets of linear constraints. The existence of a solution can then be verified using an SMT solver.
La diagnosticabilité est la propriété d'un système de produire suffisament d'observations (par l'intermédiaire de capteurs) pour différencier les comportements nominaux des comportements fautifs. Il est possible pour un système diagnosticable pour une faute (ou défaut) donnée de produire un diagnostic certain, les informations observables retournées par le système étant différentes selon si une faute a eu lieu ou non. Vérifier une telle propriété sur un système est donc une étape importante dans le processus de construction d'algorithmes de détection et d'isolation de telles fautes. Ce problème a fait l'objet de multiples études dans les Systèmes à Événements Discrets (SED) atemporels (STL, réseaux de Petri, etc.) et dans les modèles SED temporels (automates temporisés, réseaux de Petri temporels, etc.), que ce soit pour des fautes simples (modélisées par l'occurrence d'un unique événement) ou pour des comportements plus complexes appelés motifs de faute.Dans ce travail nous proposons une méthode d'analyse de diagnosticabilité de réseaux de Petri temporels pour un nouveau type de défaut appelé motif temporel. Les motifs temporels consistent en l'occurrence de différents événements contraints temporellement. Cette méthode se base sur une abstraction des préfixes du langage d'un réseau de Petri temporel sous forme de polyèdres qui constitue la première contribution de cette thèse.La seconde contribution de ce travail est une condition nécessaire et suffisante de diagnosticabilité, qui permet d'une part de vérifier si un système est diagnosticable pour un motif temporel, et de fournir des explications structurelles de non-diagnosticabilité le cas échéant. Cette méthode se base sur l'analyse des polyèdres de l'abstraction présentée, qui sont découpés en différentes zones partageant des propriétés de diagnostic communes. De cette analyse de zones est synthétisé un graphe regroupant les différentes sources d'ambiguïtés dans les différentes exécutions du système étudié.La dernière contribution de ce travail est une méthode de vérification pour le problème de diagnosticabilisation temporelle qui consiste à paramétriser les intervalles statiques du réseau de Petri temporel initial et de trouver des valeurs pour ces paramètres pour lesquelles le réseau ainsi généré soit diagnosticable pour le motif étudié. Nous proposons une méthode de vérification de cette propriété garantissant certaines propriétés sur le réseau de Petri engendré. Cette méthode de vérification se base sur l'abstraction polyédrique précédemment citée, et consiste en la construction d'ensembles de contraintes linéaires. La vérification de l'existence de solution peut être réalisée par la suite à l'aide d'un solveur SMT.
Origine : Version validée par le jury (STAR)