Fault Diagnosis for Time Petri Nets

Published on Jul 10, 2006
· DOI :10.1109/WODES.2006.1678448
George Jiroveanu7
Estimated H-index: 7
(UGent: Ghent University),
René Boel22
Estimated H-index: 22
(UGent: Ghent University),
B. De Schutter33
Estimated H-index: 33
This paper presents an on-line algorithm for fault diagnosis of time Petri net (TPN) models. The plant observation is given by a subset of transitions whose occurrence is always reported while the faults are represented by unobservable transitions. The model-based diagnosis uses the TPN model to derive the legal traces that obey the received observation and then checks whether fault events occurred or not. To avoid the consideration of all the interleavings of the unobservable concurrent transitions, the plant analysis is based on partial orders (unfoldings). The legal plant behavior is obtained as a set of configurations. The set of legal traces in the TPN is obtained solving a system of (max,+)-linear inequalities called the characteristic system of a configuration. We present two methods to derive the entire set of solutions of a characteristic system, one based on extended linear complementarity problem and the second one based on constraint propagation that exploits the partial order relation between the events in the configuration
📖 Papers frequently viewed together
1,354 Citations
10 Citations
1 Citations
#1George JiroveanuH-Index: 1
10 Citations
#1Thomas Chatain (École normale supérieure de Cachan)H-Index: 8
#2Claude Jard (École normale supérieure de Cachan)H-Index: 28
Monitoring real-time concurrent systems is a challenging task. In this paper we formulate (model-based) supervision by means of hidden state history reconstruction, from event (e.g. alarm) observations. We follow a so-called true concurrency approach using time Petri nets: the model defines explicitly the causal and concurrency relations between the observable events, produced by the system under supervision on different points of observation, and constrained by time aspects. The problem is to c...
38 CitationsSource
#1Eric Fabre (IRIA: French Institute for Research in Computer Science and Automation)H-Index: 16
#2Albert Benveniste (IRIA: French Institute for Research in Computer Science and Automation)H-Index: 55
Last. Claude Jard (École normale supérieure de Cachan)H-Index: 28
view all 4 authors...
In this paper we study the diagnosis of distributed asynchronous systems with concurrency. Diagnosis is performed by a peer-to-peer distributed architecture of supervisors. Our approach relies on Petri net unfoldings and event structures, as means to manipulate trajectories of systems with concurrency. This article is an extended version of the paper with same title, which appeared as a plenary address in the Proceedings of CONCUR?2003.
100 CitationsSource
#1Tuomas Aura (TKK: Helsinki University of Technology)H-Index: 27
#2Johan Lilius (TKK: Helsinki University of Technology)H-Index: 18
The objective of this work is to give Merlin's time Petri nets a partial order semantics based on the nonsequential process semantics for untimed net systems.
36 CitationsSource
#1Bart De Schutter (Katholieke Universiteit Leuven)H-Index: 56
#2Bart De Moor (Katholieke Universiteit Leuven)H-Index: 91
In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We show that the ELCP can be viewed as a kind of unifying framework for the LCP and its various generalizations. We study the general solution set of an ELCP and we develop an algorithm to find all its solutions. We also show that the general ELCP is an NP-hard problem.
93 CitationsSource
#1Meera Sampath (UM: University of Michigan)H-Index: 8
#2Raja Sengupta (UM: University of Michigan)H-Index: 57
Last. Demosthenis Teneketzis (UM: University of Michigan)H-Index: 43
view all 5 authors...
Fault detection and isolation is a crucial and challenging task in the automatic control of large complex systems. We propose a discrete-event system (DES) approach to the problem of failure diagnosis. We introduce two related notions of diagnosability of DES's in the framework of formal languages and compare diagnosability with the related notions of observability and invertibility. We present a systematic procedure for detection and isolation of failure events using diagnosers and provide nece...
1,354 CitationsSource
#1Edmund M. Clarke (CMU: Carnegie Mellon University)H-Index: 103
#2Kenneth L. McMillan (Cadence Design Systems)H-Index: 60
Last. Vassili Hartonas-Garmhausen (CMU: Carnegie Mellon University)H-Index: 4
view all 4 authors...
Symbolic model checking is a powerful formal specification and verification method that has been applied successfully in several industrial designs. Using symbolic model checking techniques it is possible to verify industrial-size finite state systems. State spaces with up to 1030 states can be exhaustively searched in minutes. Models with more than 10120 states have been verified using special techniques.
2,938 Citations
#1Bernard BerthomieuH-Index: 16
#2Miguel MenascheH-Index: 2
244 Citations
Cited By15
The unfolding technique of Petri net can characterize the real concurrency and alleviate the state space explosion problem. Thus, it is greatly suitable to analyze/check some potential errors in concurrent systems. During the unfolding process of a Petri net, the calculations of configurations, cuts, and cut-off events are the key factors for the unfolding efficiency. However, most of the unfolding methods do not specify a highly efficient calculations on them. In this paper, we reveal some recu...
#1Liang Li (Xidian University)H-Index: 1
#2Francesco Basile (UNISA: University of Salerno)H-Index: 20
Last. Zhiwu Li (Xidian University)H-Index: 63
view all 3 authors...
This paper deals with the enforcement of Generalized Mutual Exclusion Constraints (GMECs) on Time Petri nets (TPNs) with uncontrollable transitions by restricting the firing intervals of controllable transitions. Existing approaches do not exploit the timing information and consequently the system permissiveness is limited. The key idea behind the proposed approach is the online computation of a graph representing a reduced portion of the state space of a TPN system, and precisely the states tha...
18 CitationsSource
May 1, 2017 in ICNSC (International Conference on Networking, Sensing and Control)
This article concerns faults detection and isolation for timed stochastic discrete event systems modeled with partially observed Timed Petri nets and temporal constraints. Events occur according to arbitrary probability density functions. The models include the sensors used to measure the events and markings and also the temporal constraints to be satisfied by the system operations. These temporal constraints are defined according to tolerance intervals specified for each transition. A fault is ...
#1Mohamed Ghazel (university of lille)H-Index: 10
#2Baisi Liu (university of lille)H-Index: 6
This paper aims to develop a suite of customizable Petri net benchmarks to deal with various issues pertaining to fault diagnosis in discrete event systems. As reported in previous studies, the existing benchmarks generally characterize some of the numerous issues concerning fault diagnosis. This satisfies a specific case study, whereas it may constitute a barrier when performing comparative analysis between different approaches. In order to bridge this gap, we propose to develop a suite of benc...
6 CitationsSource
#1Xu WangH-Index: 4
#2Cristian MahuleaH-Index: 19
Last. Manuel SilvaH-Index: 56
view all 3 authors...
This paper proposes an online approach for fault diagnosis of timed discrete event systems modeled by Time Petri Net (TPN). The set of transitions is partitioned into two subsets containing observable and unobservable transitions, respectively. Faults correspond to a subset of unobservable transitions. In accordance with most of the literature on discrete event systems, we define three diagnosis states, namely normal, faulty and uncertain states, respectively. The proposed approach uses a fault ...
17 CitationsSource
#1Baisi LiuH-Index: 1
This PhD thesis deals with fault diagnosis of DES in both untimed and timed contexts using Petri net models. Some on-the-fly and incremental techniques are developed to reduce the state explosion problem while analyzing diagnosability. In the untimed context, an algebraic representation for labeled Petri net (LPN) is developed to feature the system behavior. The diagnosability of LPN models is tackled by analyzing a series of K-diagnosability problems, where K is increased progressively. Two mod...
7 Citations
#1Philippe Declerck (University of Angers)H-Index: 7
#2Abdelhak Guezzi (University of Angers)H-Index: 4
This paper presents an estimation approach for Time Event Graphs such as P-Time Event Graphs and Time Stream Event Graphs. It is assumed that the nominal behavior is known and that transitions are partitioned as observable and unobservable transitions. The technique is applied to the detection of changes which are (possibly small) finite variations of dynamic models compared to this nominal behavior. The detected changes provide indications that can be used in future maintenance operations. Usin...
9 CitationsSource
#1Xu WangH-Index: 4
#2Cristian MahuleaH-Index: 19
Last. Manuel SilvaH-Index: 56
view all 3 authors...
This paper proposes an online approach for the fault diagnosis for time discrete event systems, which are modeled by time Petri net. The observation is given by a subset of transitions whose occurrence is always observable. Faults correspond to a subset of the transitions whose firing are not observable. According to the most of the literature on discrete event systems, we define three fault states, namely N, F and U, corresponding to normal, fault and uncertain states, respectively. The propose...
10 CitationsSource
#1René Boel (UGent: Ghent University)H-Index: 22
#2George Jiroveanu (Transelectrica)H-Index: 3
In this chapter we extend the results presented in Chapter 14 and Chapter 15 by assuming that the Petri Net models include also information on the time delay between satisfying an enabling condition (tokens entering a place) and executing a transition. We address the diagnosis problem for Time Petri Net models and illustrate how this task can be performed based either on the construction of the state class graph or based on time processes.
6 CitationsSource
#1Baisi Liu (École centrale de Lille)H-Index: 2
#2Mohamed Ghazel (École centrale de Lille)H-Index: 10
Last. Armand ToguyeniH-Index: 12
view all 3 authors...
Cet article s’interesse a la diagnosticabilite des systemes a evenements discrets temporises. Le formalisme de modelisation utilise est le reseau de Petri T-temporel et labellise (RdP-LT). C’est une extension des RdP temporels pour laquelle a chaque transition est associe un evenement qui peut etre observable ou non. Nous proposons une approche pour verifier la diagnosticabilite et nous fournissons une solution pour calculer le delai minimum delta pour garantir cette diagnosticabilite. L’analyse...
3 CitationsSource