E-mail: cabasino@diee.unica.it

http://www.diee.unica.it/~cabasino/info.html

Tutors:  A. Giua and C. Seatzu, Università di Cagliari

  ___________________________________________________________________________________________________________

Diagnosis and Identification of Discrete Event Systems using Petri Nets   ___________________________________________________________________________________________________________

Advisor: Prof.  A. Giua and C. Seatzu, Università di Cagliari

Summary of the thesis

This thesis deals with the problem of diagnosis (part II) and identification (part III) of discrete event systems using Petri nets.

The diagnosis problem consists of determining if and when the system has an anomalous behavior. In this thesis we present a fault detection approach for discrete event systems using Petri nets. We assume that some of the transitions of the net are unobservable, including all those transitions that model faulty behaviors. Our diagnosis approach is based on the notion of basis marking and justification, that allow us to characterize the set of markings that are consistent with the actual observation, and the set of unobservable transitions whose firing enable it. This approach applies to all net systems whose unobservable subnet is acyclic. If the net system is also bounded the proposed approach may be significantly simplified moving the most burdensome part of the procedure off-line, thanks to the construction of a graph, called the basis reachability graph. This approach can be applied also to Petri nets that are labeled ---i.e., PNs where two or more transitions can share the same label --- and where some transitions are unobservable. In this thesis is also presented the problem of diagnosability for bounded Petri nets. A system is said diagnosable if, after a fault has occurred, it is possible to detect its occurrence with a finite delay. Finally our procedure has been compared in terms of applicability and computational complexity with a well-know diagnosis procedure that uses automata.

The identification problem is the problem of determining a system able to provide an approximation for a given input-output signal. In the contest of Petri nets the observed behavior is the language of the net, namely the set of transitions sequences that can be fired starting from the initial marking. In this thesis a procedure to identify a Petri net system, given a finite language generated by it, is presented. First we consider the problem of identifying a free labeled Petri net system, i.e., all transition labels are distinct. The set of transitions and the number of places is assumed to be known, while the net structure and the initial marking are computed solving an integer programming problem. Then we extend this approach in several ways introducing additional information about the model (structural constraints, conservative components, stationary sequences) or about its initial marking. We also treat the problem of synthesizing a bounded net system starting from an automaton that generates its language. Finally, we show how the approach can also be generalized to the case of labeled Petri nets, where two or more transitions may share the same label. In particular, in this case we impose that the resulting net system is deterministic. In both cases the identification problem can still be solved via an integer programming problem. To reduce the computational complexity we also propose a technique that uses the linear programming. Another problem that we solved is the following: given an automaton that represents the coverability graph of a Petri net, determine a Petri net system whose coverability graph is isomorphic to the automaton. Finally, we present an approach for the fault model identification with Petri nets. In particular, we suppose to know the fault-free system and our goal is to identify the structure of the faulty system. First, we assume that the language of the faulty system is completely known. Secondly, we consider faults that are unobservable.

Keywords: discrete event systems, automata, Petri nets, diagnosis, diagnosability.

 

  _______________________________________