Fourier-Motzkin method for failure diagnosis in Petri Net models of discrete event systems

Published on May 1, 2016
· DOI :10.1109/WODES.2016.7497843
Ahmed Al-Ajeli2
Estimated H-index: 2
(University of Birmingham),
Behzad Bordbar21
Estimated H-index: 21
(University of Birmingham)
This paper presents a new technique for failure diagnosis in partially observable discrete event systems modelled as Petri nets. In this new technique we adopt Integer Fourier-Motzkin Elimination (IFME) method. We start with a Petri net and produce the state equations. The state equations are a set of integer valued inequalities in variables that represent number of firing of transitions. Occurrences of failure can also be expressed by inequalities. Then we extend the set of inequalities obtained from the state equations to two new sets. The first is created from adding the inequality for failure. The second is created from adding the negation of the inequality for failure. Applying the IFME method to the two resulting sets of inequalities, the variables corresponding to unobservable transitions will be eliminated. Then we prove that for acyclic Petri nets, the reduced set of inequalities after the elimination can be used to diagnose failures.
📖 Papers frequently viewed together
2 Authors (Ahmed Al-Ajeli, ..., David Parker)
1 Citations
20 Citations
131 Citations
#1Janan Zaytoon (URCA: University of Reims Champagne-Ardenne)H-Index: 16
#2Stéphane Lafortune (UM: University of Michigan)H-Index: 60
Fault diagnosis of Discrete Event Systems has become an active research area in recent years. The research activity in this area is driven by the needs of many different application domains such as manufacturing, process control, control systems, transportation, communication networks, software engineering, and others. The aim of this paper is to review the state-of the art of methods and techniques for fault diagnosis of Discrete Event Systems based on models that include faulty behaviour. Theo...
198 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
A novel approach to fault diagnosis of discrete event systems is presented in this paper. The standard approach is based on the offline computation of the set of fault events that may have occurred at each reachable state, providing a fast online diagnosis at a price of excessive memory requirements. A different approach is here adopted, which is based on the online computation of the set of possible fault events required to explain the last observed event. This is efficiently achieved by modell...
141 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
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
#1Edmund M. ClarkeH-Index: 103
#2Orna GrumbergH-Index: 50
Last. D. LongH-Index: 1
view all 3 authors...
7,135 Citations
#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,346 CitationsSource
#1William Pugh (UMD: University of Maryland, College Park)H-Index: 51
The Omega test is an integer programming algorithm that can determine whether a dependence exists between two array references, and if so, under what conditions. Conventional wisdom holds that integer programming techniques are far too expensive to be used for dependence analysis, except as a method of last resort for situations that cannot be decided by simpler methods. We present evidence that suggests this wisdom is wrong, and that the Omega test is competitive with approximate algorithms use...
717 CitationsSource
Cited By7
#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...
#1Pedro R.R. Paiva (UFRJ: Federal University of Rio de Janeiro)H-Index: 1
#2Braian Igreja de Freitas (UFRJ: Federal University of Rio de Janeiro)
Last. João Carlos Basilio (UFRJ: Federal University of Rio de Janeiro)H-Index: 17
view all 4 authors...
Abstract Detection of abnormality (or faults) occurrences is of paramount importance in smart manufacturing systems of Industry 4.0 since faults do not usually take the system immediately to a halt, and so, it can jeopardize an entire production. With that in mind, we propose here an online diagnoser based on the Petri model of either a specific machine or part of a smart manufacturing system that makes its decision regarding the fault occurrence by storing the sequence of observed events and, a...
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...
#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...
#1Ahmed Al-Ajeli (College of Information Technology)
#1Ahmed Al-Ajeli (College of Information Technology)H-Index: 2
Last. David Parker (University of Birmingham)H-Index: 72
view all 2 authors...
This paper presents a new approach for the fault diagnosis problem in partially observable discrete-event systems modelled with Petri nets. Our approach is based on the use of the Integer Fourier-Motzkin Elimination (IFME) method. The fault diagnosis problem is solved by first creating an initial set of inequalities from the state equation of a Petri net. The occurrence or absence of faults can also be expressed by inequalities. After adding these inequalities to the initial set, we apply the IF...
1 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...
#1Philippe Declerck (University of Angers)H-Index: 7
#2Amira Chouchane (University of Angers)H-Index: 2
Last. Patrice Bonhomme (CNRS: Centre national de la recherche scientifique)H-Index: 3
view all 3 authors...
The aim of the paper is the estimation of sequences in Timed Petri nets. We propose a general strategy composed of two phases: The first phase considers the logical aspect only and suggests candidate count vectors where the second one checks the existence of a relevant time sequence for a Timed Petri net and generate a subspace of time sequences for a given candidate vector.
2 CitationsSource