On Diagnosis of Violations of Constraints in Petri Net Models of Discrete Event Systems

Published on Nov 10, 2014 in ICTAI (International Conference on Tools with Artificial Intelligence)
· DOI :10.1109/ICTAI.2014.106
Behzad Bordbar21
Estimated H-index: 21
(University of Birmingham),
Ahmed Al-Ajeli2
Estimated H-index: 2
(University of Birmingham),
Mohammed Alodib5
Estimated H-index: 5
(Qassim University)
Sources
Abstract
Failure detection in partially observable model based Discrete Event Systems requires modelling failures as unobservable events within the system. Representing failures as events is not always realistic. For example, some classes of failure are in form of violations of constraints such as Service Level Agreement (SLA) and Quality of Service (QoS). These forms of failures do not represent events by themselves. They have to be modelled as additional events. Modifying the plant model is not always acceptable. Firstly, this may make the models large, causing extra computational complexity. Secondly, adding extra transitions is not always acceptable from engineers' perspective, because these constraints may change over the time leading to alternations of models every time these constraints are changed. To address this issue, this paper presents a new definition of diagnosability which extends the existing definition. In the new definition, a formalism has been introduced which captures failures as logical constraints instead of events. We show that starting from a Petri net, if the failure is expressed in Yen's logic, we can create a new Petri net with additional transitions, including transitions modelling failure, such that detection of violation of the constraint in the first Petri net is converted to diagnosis of failure in the second.
📖 Papers frequently viewed together
4 Citations
2013
2 Authors (Stefan Haar, Eric Fabre)
7 Citations
References16
Newest
#1Mohamed Faouzi Atig (CNRS: Centre national de la recherche scientifique)H-Index: 22
#2Peter Habermehl (CNRS: Centre national de la recherche scientifique)H-Index: 24
In [19], Yen defines a class of formulas for paths in Petri nets and claims that its satisfiability problem is EXPSPACE-complete. In this paper, we show that in fact the satisfiability problem for this class of formulas is as hard as the reachability problem for Petri nets. Moreover, we salvage almost all of Yen's results by defining a fragment of this class of formulas for which the satisfiability problem is EXPSPACE-complete by adapting his proof.
32 CitationsSource
#1George Jiroveanu (Transelectrica)H-Index: 3
#2René Boel (UGent: Ghent University)H-Index: 22
For a bounded Petri Net model the diagnosability property is usually checked via its regular language represented by the reachability graph RG. However, this is problematic because the computational complexity of the diagnosability test is polynomial in the cardinality of the state space of the model which is typically very large. This limitation can be overcome by using for the diagnosability test an ROF-automaton, with a state space significantly smaller than RG, that generates the same langua...
39 CitationsSource
Dec 1, 2009 in CDC (Conference on Decision and Control)
#1Maria Paola Cabasino (University of Cagliari)H-Index: 14
#2Alessandro Giua (University of Cagliari)H-Index: 53
Last. Carla Seatzu (University of Cagliari)H-Index: 36
view all 4 authors...
In this paper we consider the property of diagnosability for labeled unbounded Petri nets, namely Petri nets where the number of tokens in one or more places can grow indefinitely. We give necessary and sufficient conditions for diagnosability and we present a test to study diagnosability based on the analysis of the coverability graph of a particular net, called verifier net, that is built starting from the initial system. To the best of our knowledge, this is the first available test for diagn...
43 CitationsSource
Nov 9, 2009 in ECOWS (European Conference on Web Services)
#1Mohammed Alodib (University of Birmingham)H-Index: 5
#2Behzad Bordbar (University of Birmingham)H-Index: 21
This paper aims to present a method of creating architectures which allow monitoring occurrence of failure in Service oriented Architectures (SoA). The presented approach extends Discrete Event Systems techniques to produce a method of automated creation of Diagnoser Service which monitors interaction between the services to identify if a failure has happened and the type of failure. To do so, a formal representation of business processes is introduced, which allows modeling of Observable/Unobse...
20 CitationsSource
#1Mariagrazia DotoliH-Index: 29
#2Maria Pia FantiH-Index: 31
Last. Walter Ukovich (UniTS: University of Trieste)H-Index: 25
view all 4 authors...
The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an obser...
121 CitationsSource
#1George Jiroveanu (Transelectrica)H-Index: 3
#2René Boel (UGent: Ghent University)H-Index: 22
Last. Behzad Bordbar (University of Birmingham)H-Index: 21
view all 3 authors...
We consider a Petri Net model of the plant. The observation is given by a subset of transitions whose occurrence is always and immediately sensed by a monitoring agent. Other transitions not in this subset are silent (unobservable). Classical on-line monitoring techniques, which are based on the estimation of the current state of the plant and the detection of the occurrence of undesirable events (faults), are not suitable for models of large systems due to high spatial complexity (exponential i...
48 CitationsSource
#1Francesco BasileH-Index: 20
#2Pasquale ChiacchioH-Index: 27
Last. G. De TommasiH-Index: 23
view all 3 authors...
Sufficient conditions for diagnosability of DES modeled as Petri net are given in this paper. In proposed framework we refer to the concept of diagnosability given by Sampath et al. for finite state automata; as far as the fault events are concerned, they are modeled as unobservable transitions. The results here presented are based on the mathematical representation of PNs, and their complexity does not depend on the initial marking of the net. Hence the proposed approach does not suffer of the ...
15 CitationsSource
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
#1L. Ricker (MtA: Mount Allison University)H-Index: 1
#2Stéphane LafortuneH-Index: 60
Last. S. Gene (UM: University of Michigan)H-Index: 1
view all 3 authors...
The key features of the software tool DESUMA for the study of discrete event systems modeled by finite-state automata are highlighted. DESUMA is the tool resulting from the integration of the UMDES library of routines for the study of discrete event systems (developed at the University of Michigan) within the graphical environment for visualizing discrete event systems (developed at Mount Allison University)
45 CitationsSource
Dec 12, 2005 in CDC (Conference on Decision and Control)
#1Alessandro Giua (University of Cagliari)H-Index: 53
#2Carla Seatzu (University of Cagliari)H-Index: 36
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 j...
248 CitationsSource
Cited By3
Newest
#1Rino BošnjakH-Index: 2
#2Danko KezićH-Index: 2
Last. Zvonko KavranH-Index: 5
view all 4 authors...
Source
Dec 1, 2018 in CDC (Conference on Decision and Control)
#1Wenqing Wu (SJTU: Shanghai Jiao Tong University)H-Index: 1
#2Xiang Yin (SJTU: Shanghai Jiao Tong University)H-Index: 16
Last. Shaoyuan Li (SJTU: Shanghai Jiao Tong University)H-Index: 30
view all 3 authors...
We investigate the problem of decentralized fault prognosis of discrete-event systems modeled by unbounded labeled Petri nets. We assume that the system is monitored by a set of local agents (prognosers) with local observations so that they can predict the occurrence of fault in the system as a team. It is known in the literature that the notion of coprognosability provides the necessary and sufficient condition for the existence of a set of decentralized prognosers so that any fault can be pred...
2 CitationsSource
The problem of fault diagnosis under partial observation is a complex problem; and the challenge to solve this problem is to find a compromise between the space complexity and time complexity. The classic method to solve the problem is by constructing an automaton called a diagnoser. This method suffers from the state explosion problem which limits its application to large systems. In this thesis, the problem of fault diagnosis in partially observed discrete event systems is addressed. We assume...