On-Line Monitoring of Large Petri Net Models Under Partial Observation

Published on Sep 1, 2008in Discrete Event Dynamic Systems0.932
· DOI :10.1007/S10626-007-0036-X
George Jiroveanu3
Estimated H-index: 3
René Boel22
Estimated H-index: 22
(UGent: Ghent University),
Behzad Bordbar21
Estimated H-index: 21
(University of Birmingham)
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 in the size of the entire model). In this paper we propose a method based on the explanation of plant observation. A legal trace minimally explains the observation if it includes all unobservable transitions whose firing is needed to enable the observed transitions. To do so, starting from an observable transition, using backward search techniques, a set of minimal explanations is derived, which are sufficient for detecting whether a fault event must have occurred for sure in the plant or not. The technique also allows production of a set of basis markings for the estimation of the current state of the plant. The set of all possible current markings can then be characterized as the unobservable reach of these basis markings. The computational complexity of the algorithm depends on the size of the largest connected subnet which includes only unobservable transitions. This allows monitoring of plants of any size in which there is no large unobservable subnet. We also illustrate the applicability of the method for the monitoring of a class of infinite state systems, unbounded Petri Nets with unobservable trap circuits, and we show how this can be useful for distributed implementations.
📖 Papers frequently viewed together
2005CDC: Conference on Decision and Control
249 Citations
1,354 Citations
120 Citations
Jan 6, 2007 in IJCAI (International Joint Conference on Artificial Intelligence)
#1Marie-Odile Cordier (University of Rennes)H-Index: 21
#2Alban GrastienH-Index: 15
It is well-known that the size of the model is a bottleneck when using model-based approaches to diagnose complex systems. To answer this problem, decentralised/distributed approaches have been proposed. Another problem, which is far less considered, is the size of the diagnosis itself. However, it can be huge enough, especially in the case of on-line monitoring and when dealing with uncertain observations. We define two independence properties (state and transition-independence) and show their ...
29 Citations
#1George JiroveanuH-Index: 1
10 Citations
Dec 12, 2005 in CDC (Conference on Decision and Control)
#1G. Jiroveanu (UGent: Ghent University)H-Index: 1
#2René Boel (UGent: Ghent University)H-Index: 22
In this paper we consider the case of a large plant comprising different local sites. At each site, a local diagnoser must provide the diagnosis of the site based on the local plant model (a Petri Net), the local observation and the information exchanged with its neighbors. The communication between the local diagnosers is not event-driven and the interactions between the local sites (modeled as common places) are considered unobservable (tokens can enter and exit unobservably the local Petri Ne...
6 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...
249 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
#1Alessandro Giua (University of Cagliari)H-Index: 53
#2Daniele Corona (University of Cagliari)H-Index: 6
Last. Carla Seatzu (University of Cagliari)H-Index: 36
view all 3 authors...
In this paper we deal with the problem of estimating the marking of a labeled Petri net with nondeterministic transitions. In particular, we consider the case in which nondeterminism is due to the presence of transitions that share the same label and that can be simultaneously enabled. Under the assumption that: the structure of the net is known, the initial marking is known, the transition labels can be observed, the nondeterministic transitions are contact-free, we present a technique for char...
41 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
#1Giorgio DelzannoH-Index: 24
#2Jean-François Raskin (ULB: Université libre de Bruxelles)H-Index: 46
Last. Laurent Van Begin (ULB: Université libre de Bruxelles)H-Index: 14
view all 3 authors...
The control state reachability problem is decidable for well-structured infinite-state systems like (Lossy) Petri Nets, Vector Addition Systems, and broadcast protocols. An abstract algorithm that solves the problem is the backward reachability algorithm of [1, 21 ]. The algorithm computes the closure of the predecessor operator with respect to a given upward-closed set of target states. When applied to this class of verification problems, symbolic model checkers based on constraints like [7, 26...
31 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
Cited By48
#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...
#1Yi Wang (Xidian University)
#2Yuting Li (MUST: Macau University of Science and Technology)H-Index: 2
Last. Zhiwu Li (MUST: Macau University of Science and Technology)H-Index: 63
view all 5 authors...
Abstract Resilience is a critical criterion to evaluate a networked system including discrete-event systems (DESs). This research touches upon the supervisory control problem of a DES modeled with labeled Petri nets under malicious attacks. Attacks on a system can be categorized into actuator attacks and sensor attacks. The former may cause an actuator to fail to execute the commands issued from a supervisor that enforces a specification. The latter may attack a sensor to corrupt an observation ...
In this paper, we consider the on-line estimation of optimal current subsequences in Partially Observable Untimed Petri Nets. Applying the counter approach classically used in max-plus algebra for Timed Petri nets, the idea is to exploit the assumption of a non immediate consumption of the tokens for each place which introduces an order of precedence between events. The approach can estimate a global price depending on the costs and gains provided by the tasks. The estimation of optimal sequence...
#1Gianfranco LampertiH-Index: 13
#2Marina ZanellaH-Index: 11
Last. Xiangfu ZhaoH-Index: 7
view all 3 authors...
#1Yan Yang (Xidian University)H-Index: 3
#2Hesuan Hu (NTU: Nanyang Technological University)H-Index: 25
The development of efficient solutions for deadlock problem in large-scale automated manufacturing systems (AMSs) is an issue of increasing interest in the scientific community, largely because of the nonapplicability of most existing approaches as AMS grows in size. Furthermore, much of these approaches is focused on systems with either assembly operations or flexible routes, implying that generalizing these existing results to more complex systems is difficult. As a result, we initiate on the ...
10 CitationsSource
#1Atef Khedher ('ENS Paris': École Normale Supérieure)
#2Kamal BenOthman ('ENS Paris': École Normale Supérieure)
In this paper, a particular state model allowing describing the system evolution in time is proposed. This state model contains two inequalities describing the evolution in time of the system state and input. The system simulation is based on the resolution of this state model. After that, a state estimator is proposed in order to estimate the whole system state and inputs. The state model and the observer are both proposed following count and dater approaches successively. In this work, the con...
#1Touhiduzzaman (PNNL: Pacific Northwest National Laboratory)H-Index: 3
#2Adam Hahn (WSU: Washington State University)H-Index: 14
Last. Saeed Lotfifard (WSU: Washington State University)H-Index: 18
view all 3 authors...
Substation automation systems (SAS) are known to be vulnerable to cyber attacks due to the weaknesses of security features (e.g., encryption, authenticity). These issues were demonstrated by the recent Ukranian cyber attack event on 2016. The security mechanisms located at the SAS need to identify cyberattacks and faults occur in protection operations distributively in efficient manner. This work presents a novel distributed cyberattack diagnosis solution (DCDS) for the SAS, based on the backwar...
#1Qi ZhangH-Index: 2
#2Carla SeatzuH-Index: 36
Last. Alessandro GiuaH-Index: 53
view all 4 authors...
The problem of cyber attacks with bounded sensor reading edits for partially-observed discrete event systems is considered. An operator observes a plant through an observation mask that does not allow him to detect the occurrence of certain events (silent events). The observation is corrupted by an attacker who can insert and erase some sensor readings. The operator observes the system evolution in order to validate if a state in a given set of unsafe states is reached. The attacker corrupts the...
2 Citations
#1Sohag Kabir (University of Hull)H-Index: 15
#2Yiannis Papadopoulos (University of Hull)H-Index: 27
System safety, reliability and risk analysis are important tasks that are performed throughout the system life-cycle to ensure the dependability of safety-critical systems. Probabilistic risk assessment (PRA) approaches are comprehensive, structured and logical methods widely used for this purpose. PRA approaches include, but not limited to, Fault Tree Analysis (FTA), Failure Mode and Effects Analysis (FMEA), and Event Tree Analysis (ETA). Growing complexity of modern systems and their capabilit...
74 CitationsSource