Fault detection for discrete event systems using Petri nets with unobservable transitions

Published on Dec 12, 2005 in CDC (Conference on Decision and Control)
· DOI :10.1016/J.AUTOMATICA.2010.06.013
Alessandro Giua53
Estimated H-index: 53
(University of Cagliari),
Carla Seatzu36
Estimated H-index: 36
(University of Cagliari)
Sources
Abstract
In this paper we present an efficient approach for the fault detection of 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. We prove that the set of all possible firing sequences corresponding to a given observation can be described as follows. First a set of basis markings corresponding to the observation are computed together with the minimal set of transitions firings that justify them. Any other marking consistent with the observation must be reachable from a basis marking by firing only unobservable transitions. For the computation of the set of basis markings we propose a simple tabular algorithm and use it to determine a basis reachability tree that can be used as a diagnoser.
📖 Papers frequently viewed together
9,048 Citations
85 Citations
1,354 Citations
References22
Newest
This paper studies online fault detection and isolation of modular dynamic systems modeled as sets of place-bordered Petri nets. The common places among the set of Petri nets modeling a system capture coupling of various system components. The transitions are labeled by events, some of which are unobservable (i.e., not directly recorded by the sensors attached to the system). The events whose occurrence must be diagnosed have unobservable transition labels. These events model faults or other sig...
120 CitationsSource
#1George Jiroveanu (UGent: Ghent University)H-Index: 7
#2René Boel (UGent: Ghent University)H-Index: 22
Last. B. De SchutterH-Index: 33
view all 3 authors...
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 transit...
15 CitationsSource
#1G. Jiroveanu (UGent: Ghent University)H-Index: 1
#2R. K. Boel (UGent: Ghent University)H-Index: 1
This paper proposes an algorithm for the model based design of a distributed protocol for fault detection and diagnosis for very large systems. The overall process is modeled as different Time Petri Net (TPN) models (each one modeling a local process) that interact with each other via guarded transitions that becomes enabled only when certain conditions (expressed as predicates over the marking of some places) are satisfied (the guard is true). In order to use this broad class of time DES models...
61 CitationsSource
#1René Boel (UGent: Ghent University)H-Index: 22
#2George Jiroveanu (UGent: Ghent University)H-Index: 7
Abstract The occurrence of a fault usually influences immediately a (small) part of a large system, while the behavior in the rest of the system deteriorates only after some delay. Exploiting this, we propose in this paper a distributed diagnosis algorithm using a contextual analysis of Petri Nets. Using a backward reasoning technique we derive the minimal context (what must have happened) that explains the observed events. The method can tackle Petri Nets models with uncertain initial markings,...
30 CitationsSource
The paper studies failure diagnosis of discrete-event systems (DESs) with linear-time temporal logic (LTL) specifications. The LTL formulas are used for specifying failures in the system. The LTL-based specifications make the specification specifying process easier and more user-friendly than the formal language/automata-based specifications; and they can capture the failures representing the violation of both liveness and safety properties, whereas the prior formal language/automaton-based spec...
130 CitationsSource
#1Jan Lunze (RUB: Ruhr University Bochum)H-Index: 31
#2Jochen SchröderH-Index: 5
The paper describes a method for detecting and identifying faults that occur in the sensors or in the actuators of dynamical systems with discrete-valued inputs and outputs. The model used in the diagnosis is a stochastic automaton. The generalized observer scheme (GOS), which has been proposed for systems with continuous-variable inputs and outputs some years ago, are developed for discrete systems. This scheme solves the diagnostic problem as an observation problem, which is set up here for di...
90 CitationsSource
#1Alessandro Giua (University of Cagliari)H-Index: 53
#2Carla Seatzu (University of Cagliari)H-Index: 36
Last. D. CoronaH-Index: 8
view all 3 authors...
In this paper we deal with the problem of estimating the marking of a labeled Petri net system based on the observation of transitions labels. In particular, we assume that a certain number of transitions are labeled with the empty string /spl epsi/, while a different label taken from a given alphabet is assigned to all the other transitions. Transitions labeled with the empty string are called silent because their firing cannot be observed. Under some technical assumptions on the structure of t...
76 CitationsSource
#1René BoelH-Index: 4
#2George JiroveanuH-Index: 7
16 Citations
#1S. Hashtrudi Zad (Concordia University)H-Index: 6
#2Raymond H. KwongH-Index: 16
Last. W. M. WonhamH-Index: 74
view all 3 authors...
A state-based approach for online passive fault diagnosis in systems modeled as finite-state automata is presented. In this framework, the system and the diagnoser (the fault detection system) do not have to be initialized at the same time. Furthermore, no information about the state or even the condition (failure status) of the system before the initiation of diagnosis is required. The design of the fault detection system, in the worst case, has exponential complexity. A model reduction scheme ...
294 CitationsSource
#1Albert Benveniste (IRIA: French Institute for Research in Computer Science and Automation)H-Index: 8
#2Eric Fabre (IRIA: French Institute for Research in Computer Science and Automation)H-Index: 16
Last. Claude JardH-Index: 28
view all 4 authors...
In this paper, we consider the diagnosis of asynchronous discrete event systems. We follow a so-called true concurrency approach, in which no global state and no global time is available. Instead, we use only local states in combination with a partial order model of time. Our basic mathematical tool is that of net unfoldings originating from the Petri net research area. This study was motivated by the problem of event correlation in telecommunications network management.
260 CitationsSource
Cited By249
Newest
#1Hao Lan (Southwest Jiaotong University)H-Index: 3
#2Yin Tong (Southwest Jiaotong University)H-Index: 8
Last. Carla Seatzu (University of Cagliari)H-Index: 36
view all 3 authors...
Abstract null null Detectability describes the property of a system to uniquely determine, after a finite number of observations, the current and the subsequent states. Different notions of detectability have been proposed in the literature. In this paper, we formalize and analyze strong detectability and strong periodic detectability for systems that are modeled as labeled Petri nets with partial observation on their transitions. We provide three new approaches for the verification of such dete...
Source
#1Eeshan Deosthale (OSU: Ohio State University)H-Index: 3
#2Daniel Jung (Linköping University)H-Index: 8
Last. Qadeer Ahmed (OSU: Ohio State University)H-Index: 12
view all 3 authors...
Source
#1Ahmed Al-Ajeli (College of Information Technology)H-Index: 2
#2David Parker (University of Birmingham)H-Index: 72
Abstract null null We propose techniques for fault diagnosis in discrete-event systems modelled by labelled Petri nets, where fault events are modelled as unobservable transitions. The proposed approach combines an offline and an online algorithm. The offline algorithm constructs a diagnoser in the form of sets of inequalities that capture the legal, normal and faulty behaviour. To implement the offline algorithm, we adopt the Fourier–Motzkin method for elimination of variables from these sets o...
Source
#1Kuize Zhang (Technical University of Berlin)H-Index: 13
#2Jörg Raisch (Technical University of Berlin)H-Index: 29
In this paper, \emph{diagnosability} is characterized for a labeled max-plus automaton \mathcal{A}^{\mathcal{D}}over a dioid \mathcal{D}as a real-time system. In order to represent time elapsing, a special class of dioids called \emph{progressive} are considered, in which there is a total canonical order, there is at least one element greater than \textbf{1} the product of sufficiently many elements greater than \textbf{1}is arbitrarily large, and the cancellative law is satisfied. T...
#1Yihui Hu (Xidian University)H-Index: 1
#2Ziyue Ma (Xidian University)H-Index: 9
Last. Alessandro Giua (University of Cagliari)H-Index: 53
view all 4 authors...
Abstract null null In this article, we deal with the active diagnosis problem in labeled Petri nets by developing a supervisor for a plant such that the closed-loop system is diagnosable. Since control actions may introduce deadlocks even if an original plant is deadlock-free, we first generalize the classical notion of diagnosability in labeled Petri nets to the nets that may contain potential deadlocks. To avoid enumerating all reachable markings of a plant, we develop a structure called quies...
Source
Abstract null null This paper studies the marking diagnosability verification problem in labeled Petri nets. Marking diagnosability is a property implying the fact that a plant Petri net has ever reached a pre-defined set of faulty markings can be detected in a finite number of future steps. We first show that the conventional basis-reachability-graph-based methods cannot be used due to the existence of partially faulty basis markings. To overcome such a problem, we propose a transition partitio...
1 CitationsSource
2 CitationsSource
#1Ziyue Ma (Xidian University)H-Index: 9
#2Xiang Yin (SJTU: Shanghai Jiao Tong University)H-Index: 16
Last. Zhiwu Li (Xidian University)H-Index: 63
view all 3 authors...
This paper studies the marking prediction problem in labeled Petri nets. Marking prediction aims to recognize a priori that the plant will inevitably reach a given set of alert markings in finite future steps. Specifically, we require that a marking prediction procedure should have the following properties: (i) no missed alarm, i.e., an alarm can always be issued before reaching an alert marking; and (ii) no false alarm, i.e., once an alarm is issued, the plant will eventually reach an alert mar...
1 CitationsSource
#1Zhou He (Shaanxi University of Science and Technology)H-Index: 5
#2Ziyue Ma (Xidian University)H-Index: 9
Abstract This paper studies a performance safety enforcing problem in stochastic event graphs, a subclass of stochastic Petri net models. We assume that an intruder can attack part of the transitions to increase/decrease their firing rate such that the performance of the system violates a given safety interval. The difficulty in solving this problem is that the capability of the intruder, i.e., the number of transitions that can be simultaneously attacked, is limited. The control aim is to find ...
Source
#1Francesco Basile (UNISA: University of Salerno)H-Index: 20
#2Gianmaria De Tommasi (University of Naples Federico II)H-Index: 10
Last. Claudio Sterle (University of Naples Federico II)H-Index: 10
view all 3 authors...
Security of distributed control systems is affected by the presence of information leaks, which permit to external intruders to infer the state of the system itself. Noninterference deals with the absence of such leak paths in a dynamic system modeled as discrete-event system. For a system that presents information leaks, a supervisory control strategy to enforce noninterference is proposed in this article. The approach is based on the solution of optimization problems on a Petri net model of th...
2 CitationsSource