Le test d’identification d’état d’un système à événement discret (SED) a pour but d’en identifier l’état final, lorsque son état initial est inconnu. Une solution classique à ce problème, en supposant que le SED n’ait pas de sorties observables, consiste à déterminer une séquences de synchronisation, c.à-d., une séquence d’événements d’entrée qui conduit le SED sur un état connu. Ce problème a été résolu dans les années 60’ à l’aide des automates. L’objectif principal de cette thèse est d’utiliser les réseaux de Petri (RdP) pour obtenir une résolution plus optimal de ce problème et pour une plus large classe de systèmes.Initialement, nous montrons que la méthode classique peut être aisément étendue aux RdP synchronisés. Pour cette classe de réseaux non-autonomes, toute transition est associée à un événement d’entrée.L’approche proposée est générale, dans la mesure où elle s’applique à des RdP bornés arbitraires. Cependant, elle engendre le problème d’explosion combinatoire du nombre d’états. Pour obtenir des meilleures solutions, nous considérons une classe spéciale de RdP : les graphes d’état (GdE). Pour ces réseaux, nous considérons d’abord les GdE fortement connexes et proposons des approches pour la construction de SS, qui exploitent les propriétés structurelles du réseau en évitant ainsi une énumération exhaustive de l’espace d’état. Ces résultats s’étendent aux GdE non fortement connexes et à tout RdP synchronisé composé de GdE. Enfin, nous considérons la classe des RdP non bornés et proposons des séquences qui synchronisent le marquage des places non bornées. Une boîte à outils fournit toutes les approches décrites et est appliquée à des différents bancs d’essai. / State-identification experiments are designed to identify the final state of a discrete event system (DES) when its initial state is unknown. A classical solution, assuming the DES has no observable outputs, consists in determining a synchronizing sequence (SS), i.e., a sequence of input events that drives the system to a known state. This problem was essentially solved in the 60’ using automata. The main objective of this thesis is to use Petri nets (PNs) for solving the state-identification problem more efficiently and for a wider class of systems.We start showing that the classical SS construction method based on automata can be easily applied to synchronized PNs, a class of non-autonomous nets where each transition is associated with an input event. The proposed approach is fairly general and it works for arbitrary bounded nets with a complexity that is polynomial with the size of the state space. However, it incurs in the state-space explosion problem.Looking for more efficient solutions, we begin by considering a subclass of PNs called state machines (SMs). We first consider strongly connected SMs and propose a framework for SS construction that exploits structural criteria, not requiring an exhaustive enumeration of the state space of the net. Results are further extended to larger classes of nets, namely non strongly connected SMs and nets containing SM subnets. Finally we consider the class of unbounded nets that describe infinite state systems: even in this case we are able to compute sequences to synchronize the marking of bounded places. A Matlab toolbox implementing all approaches previously described has been designed and applied to a series of benchmarks.

Cette thèse porte sur le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri labellisés (RdP-L). Les problèmes de diagnostic monolithique et de diagnostic modulaire sont abordés. Des contributions sont proposées pour résoudre les problèmes d'explosion combinatoire et de complexité de calcul. Dans le cadre de l'analyse de la diagnosticabilité monolithique, certaines règles de réduction sont proposées comme un complément pour la plupart des techniques existantes de l'analyse de la diagnosticabilité, qui simplifient le modèle RdP-L tout en préservant sa propriété de diagnosticabilité. Pour un RdP-L sauf et vivant, une nouvelle condition suffisante pour la diagnosticabilité est proposée. Pour un RdR-L borné et non bloquant après l'occurrence d'une faute, l'analyse à-la-volée est améliorée en utilisant la notion d'explications minimales qui permettent de compacter l'espace d'état ; et en utilisant des T-semiflots pour trouver rapidement un cycle indéterminé. Une analyse à-la-volée utilisant Verifier Nets (VN) est proposée pour analyser à la fois les RdP-L bornés et non-bornés, ce qui permet d'obtenir un compromis entre efficacité du calcul et limitation des explosions combinatoires. Dans le cadre de l'analyse de la diagnosticabilité modulaire, une nouvelle approche est proposée pour les RdP-Ls décomposés. Les règles de réduction, qui préservent la propriété de la diagnosticabilité modulaire, sont appliquées pour simplifier le modèle initial. La diagnosticabilité locale est analysée en construisant le VN et le Graphe d'Accessibilité Modifié (MAG) du modèle local. La diagnosticabilité modulaire est vérifiée en construisant la composition parallèle du MAG et des graphes d'accessibilités d'autres modules du système. La complexité de calcul est inférieure à celles des autre approches dans la littérature. D'autre part, l'explosion combinatoire est également réduite en utilisant la technique de ε-réduction / This thesis deals with fault diagnosis of discrete event systems modeled by labeled Petri nets (LPN). The monolithic diagnosability and modular diagnosability issues are addressed. The contributions are proposed to reduce the combinatorial explosion and the computational complexity problems. Regarding monolithic diagnosability analysis, some reduction rules are proposed as a complement for most diagnosability techniques, which simplify the LPN model and preserve the diagnosability property. For a safe and live LPN, a new sufficient condition for diagnosability is proposed. For a bounded LPN that does not deadlock after a fault, the on-the-fly diagnosability analysis is improved by using minimal explanations to compact the state space; and by using T-invariants, to find quickly an indeterminate cycle. An on-the-fly diagnosability analysis using Verifier Nets (VN) is proposed to analyze both bounded and unbounded LPN, which achieves a compromise between computation efficiency and combinatorial explosion limitation. Regarding modular diagnosability analysis, a new approach is proposed for decomposed LPNs model. Reduction rules, that preserve the modular diagnosability property, are applied to simplify the model. The local diagnosability is analyzed by building the VN and the Modified Reachability Graph (MRG) of the local model. The modular diagnosability is verified by building the parallel composition of the MRG and the reachability graphs of other modules of the system. We prove in this study that the computational complexity of our approach is lower than existing approaches of literature. The combinatorial explosion is also reduced by using the ε -reduction technique.

Avec l'évolution de la technologie, l'homme a procédé à la conception de systèmes de plus en plus complexes mais aussi de plus en plus sensibles aux défauts qui peuvent les affecter. Une procédure de diagnostic contribuant au bon déroulement du processus est ainsi nécessaire. Dans ce contexte, le but de cette thèse est le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri Étiquetés (RdPE) partiellement observables. Sous l'hypothèse que chaque défaut est modélisé par le tir d'une transition non observable, deux approches de diagnostic à base d'estimation d'état sont développées. Une première approche composée de deux étapes consiste à estimer l'ensemble des marquages de base sur un horizon élémentaire glissant. La première étape consiste à déterminer un ensemble de vecteurs candidats à partir d'une approche algébrique. La deuxième étape consiste à éliminer les solutions candidates calculées qui ne sont pas associées à une trajectoire possible du RdPE. Comme l'ensemble des marquages de base pourra aussi être important, une deuxième approche de diagnostic évitera cet écueil en n'estimant pas les marquages. Une technique de relaxation des problèmes de Programmation Linéaire en Nombres Entiers (PLNE) sur un horizon fuyant est utilisée afin d'avoir un diagnostic en temps polynomial. / With the evolution of technology, humans have made available systems increasingly complex but also increasingly sensitive to faults that may affect it. A diagnostic procedure which contributes to the smooth running of the process is thus necessary. In this context, the aim of this thesis is the diagnosis of discrete event systems modeled by partially observed Labeled Petri Nets (LPNs). Under the assumption that each defect is modeled by the firing of an unobservable transition, two diagnostic approaches based on state estimation are developed. A first approach is to estimate the set of basis markings on a sliding elementary horizon. This approach is carried out in two steps. The first step is to determine a set of candidate vectors from an algebraic approach. The second step is to eliminate the calculated candidate solutions that are not associated with a possible trajectory of the LPN. As the set of basis markings can also be huge, a second diagnostic approach will avoid this pitfall by not estimating the markings. A relaxation technique of Integer Linear Programming (ILP) problems on a receding horizon is used to have a diagnosis in polynomial time.