Synchronous Product of Time Petri Nets and its Applications to Fault-Diagnosis
Produit Synchrone de Réseaux de Petri temporel et ses Applications au Diagnostic de Fautes
Résumé
We study the behavior of Discrete Event Systems (DES) subjectto strong temporal constraints. We are more particularly interested inthe formal verification of properties on the timed languagesassociated with their executions. In this context, we focus on DESmodelled using Time Petri Nets (TPN), an extension of classicalPetri nets in which we can constrain the time during whichtransitions stay enabled.Our goal is to use and extend techniques borrowed frommodel-checking in order to check properties related to thediagnosability of a system. To this end, we study propertieson the intersection of the timed languages of systems. Ourapproach is based on the definition of a new composition operator,that we call synchronous product, that constrain differenttransitions to fire at the same time. This allows us to analyse theproduct of systems more directly, without the need to compute theintersection of their language at the level of their state spaces.Our main contribution is the definition of a new formal model, calledProduct TPN (PTPN), that includes our notion of synchronousproduct in its syntax. We show how to extend the notion ofState Class Graphs to PTPN and use this construction to checkthe diagnosability of single faults on TPN. We also study thediagnosability of more complex behaviors, expressed using patternsof events, and explore a restricted case of timed pattern.A software called TWINA was created in the context of this thesis. Twina is a tool for analyzing the "product" of two Time Petri Nets (TPN), with possibly inhibitor and read arcs. Its main objective is to compute a usable representation of the intersection of two net languages; meaning the intersection of the (timed) languages obtained from the executions of two TPN, in which transitions with the same labels are fired at the same date.The tool is based on a new extension of the State Class Graph construction, the method used in the TINA (TIme petri Net Analyzer) toolbox. Like for TINA, this tool is maintained by the Verification of Time Critical Systems (VERTICS) group, which develops new verification methods and tools for checking properties of critical systems having strong temporal and timing requirements. TWINA is mainly used to conduct experiment on our new model, the PTPN.
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 la vérification de propriétés liées aux langages associés à leurs exécutions. Dans ce 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 domaine du model-checking afin de répondre à des questions de diagnosticabilité. Pour ce faire, nous cherchons à vérifier des propriétés liées à l'intersection entre les langages temporels (le comportement) de différent systèmes. Notre approche repose sur la définition d'une nouvelle opération de produit synchrone entre TPN qui nous permet d'utiliser des techniques d'analyse plusdirectes. Ceci nous permet, en particulier, d'éviter de devoir calculer directement l'intersection entre langages au niveau des espaces d'état des systèmes.Notre contribution principale est la définition d'un nouveau modèle, les Product TPN (PTPN), qui internalise notre concept de produit synchrone entre transitions. Nous proposons une extension de la notion de graphes de classes au cas des PTPN et utilisons ce modèle pour vérifier la propriété de diagnosabilité sur les TPN dans le cas de fautes simples, mais également pour la diagnosticabilité de scénarios plus complexes, décrit sous la forme de motifs.Un logiciel appelé TWINA a été créé dans le cadre de cette thèse. Twina est un outil d'analyse du « produit » de deux Time Petri Nets (TPN), avec éventuellement des arcs inhibiteurs et read. Son objectif principal est de calculer une représentation utilisable de l'intersection de deux langages de réseau ; c'est-à-dire l'intersection des langues (temporisées) obtenues à partir des exécutions de deux TPN, dans lesquelles des transitions avec les mêmes labels sont déclenchées à la même date.L'outil est basé sur une nouvelle extension de la construction State Class Graph, la méthode utilisée dans la boîte à outils TINA (TIME Petri Net Analyzer). Comme pour TINA, cet outil est maintenu par le groupe Verification of Time Critical Systems (VERTICS), qui développe de nouvelles méthodes et outils de vérification pour vérifier les propriétés des systèmes critiques ayant de fortes exigences temporelles et temporelles. TWINA est principalement utilisé pour expérimenter notre nouveau modèle, le PTPN.
Origine : Version validée par le jury (STAR)