×

zbMATH — the first resource for mathematics

On-line monitoring of large Petri net models under partial observation. (English) Zbl 1171.93356
Summary: 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 is 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.

MSC:
93C65 Discrete event control/observation systems
93A15 Large-scale systems
93B07 Observability
90C35 Programming involving graphs or networks
Software:
visualSTATE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdulla PA, Iyer SP, Nylen A (2000) On unfolding unbounded Petri Nets. Computer Aided Verification, LNCS, vol 1855. Springer
[2] Baroni P, Lamperti G (1999) Diagnosis of large active systems. Artif Intell 101(1):135–183 · Zbl 0996.68209
[3] Benvensite A, Fabre E, Haar S, Jard C (2003) Diagnosis of asynchronous discrete event systems, a net unfolding approach. IEEE Trans Automat Contr 48(5):182–187 · Zbl 1364.93452
[4] Boel RK, Jiroveanu G (2003) Petri Nets model-based fault section detection and diagnosis in electrical power networks. In: Proceedings of the 6th IPEC conference, Singapore
[5] Boel RK, Jiroveanu G (2004) Distributed contextual diagnosis for very large systems. In: Proceedings of the 7th workshop on discrete event systems (WODES’04), Reims, France
[6] Boufaied A, Subias A, Combacau M (2002) Chronicle modeling by Petri Nets for distributed detection of process failures. In: Proceedings of the IEEE conference on systems, management and cybernetics, Hammamet, Tunisie
[7] Cardoso J, Kunzle LA, Valette R (1995) Petri Net based reasoning for the diagnosis of dynamic discrete event systems. In: Proceedings of the 6th international fuzzy systems association world congress, July, pp 333–336
[8] Cordier M-O, Grastien A (2007) Exploiting independence in a decentralised and incremental approach of diagnosis. In: Proceedings of IJCAI 2007, Hyderabad, India, pp 292–297
[9] Corona D, Giua A, Seatzu C (2004) Marking estimation of Petri Nets with silent transitions. In: Proceedings of IEEE 43rd int. conf. on decision and control, Atlantis, The Bahamas, December · Zbl 1071.93028
[10] Delzanno G, Raskin J-F, Van Begin L (2004) Covering sharing trees: a compact data structure for parameterized verification. Softw Tools Technol Trans 5(2):268–297 · Zbl 02243220
[11] Dickson LE (1913) Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Am J Math 35:413–422 · JFM 44.0220.02
[12] Fabre E, Benvensite A, Haar S, Jard C (2005) Distributed monitoring of concurrent and asynchronous systems. J Discrete Event Dyn Syst 15(1):33–84, March · Zbl 1077.68059
[13] Finkel A, Raskin J-F, Samuelidis M, Van Begin L (2002) Monotonic extensions of Petri Nets: forward and backward search revisited. Electron Notes Theoret Comput Sci 68(6) · Zbl 1270.68214
[14] Genc S, Lafortune S (2003) Distributed diagnosis for DES using Petri Nets. In: Proceedings of the conference on applications and theory of Petri Nets (ATPN’03), Eindhoven, The Nederlands · Zbl 1274.68234
[15] Giua A, Seatzu C (2005) Fault detection for discrete event systems using Petri Nets with unobservable transitions. In: Proceedings of the conference on decision and control (CDC-ECC’05), Sevilla, Spain, December, pp 6323–6328
[16] Hadjicostis CN, Verghese GC (1999) Monitoring discrete event systems using Petri Net embeddings. Application and theory of Petri Nets–LNCS, vol 1639. Springer, pp 188–207 · Zbl 0934.93046
[17] Hadjicostis CN, Verghese G (2000) Power systems monitoring based on relay and circuit breaker. In: IEE proceedings on generation, transmission and distribution, vol 147, pp 299–303
[18] Haar S, Benveniste A, Fabre E, Jard C (2003) Partial order diagnosability of discrete event systems using Petri Net unfolding. In: Proceedings of the 42th IEEE conference on decision and control (CDC’03), HI, USA · Zbl 1274.68221
[19] Holloway LE, Ashley J (2002) Diagnosis of condition systems using causal structure. In: Proceedings of the American control conference, Alaska, USA
[20] Holloway LE, Chand S (1996) Distributed fault monitoring in manufacturing systems using concurrent discrete-event observations. Integr Comput-Aided Eng 3:244–254
[21] Jiang S, Kumar R (2004) Failure diagnosis of discrete event systems with linear-time temporal logic specifications. IEEE Trans Automat Control 49 · Zbl 1365.93294
[22] Jiroveanu G (2006) Fault diagnosis for large Petri Nets. PhD thesis, Ghent University, Gent, Belgium · Zbl 1098.93024
[23] Jiroveanu G, Boel RK (2004) Contextual analysis of Petri Nets for distributed applications. In: Proceedings of MTNS’04 conference, Leuven, Belgium
[24] Kurine J, Koutsoukos X, Su R, Wonham WM (2002) Distributed diagnosis for qualitative systems. In: Proceedings of the workshop on discrete event systems (WODES’02), Zaragoza, Spain
[25] Lin F (1994) Diagnosability of discrete event systems and its application. Discret Event Dyn Syst 4:197–212 · Zbl 0800.93030
[26] Mancel C, Lopez P, Riviére N, Valette R (2002) Relationships between Petri Nets and constraint graphs: application to manufacturing. In: Proceedings of the 15th IFAC triennial world congress
[27] Marchand H, Boivineau O, Lafortune S (2000) Optimal control of discrete event systems under partial observation. Technical report, INRIA Rennes · Zbl 0964.93066
[28] Murata T (1989) Petri Nets: properties, analysis and applications. Proceedings IEEE 77(4):541–580, April
[29] Nielsen JL, Andersen HR, Hulgaard H, Behrmann G, Kristoffersen K, Larsen KG (1998) Verification of large state/event systems using compositionality and dependency analysis. In: Proceedings of the international conference on tools and algorithms for construction and analysis, pp 201–216
[30] Ozveren CM, Willsky AS (1990) Observability of discrete event systems. IEEE Trans Automat Control 35(7):797–806 · Zbl 0709.68030
[31] Pencolé Y, Cordier M-O, Rozé, L (2001) Incremental decentralized diagnosis approach for the supervision of a telecommunication network. In: Proceedings of the workshop on principles of diagnosis (DX’01), Italy
[32] Portinale L, Anglano C (1994) B–W analysis: a backward reachability analysis for diagnostic problem solving suitable to parallel implementation. In: Proceedings of the 15th int. conference on application and theory of Petri Nets, LNCS, vol 815, Zaragoza, Spain, pp 39–58
[33] Sampath M, Sengupta R, Lafortune S, Sinnamohideen S, Teneketzis D (1995) Diagnosability of discrete event systems. IEEE Trans Automat Control 40(9):1555–1575 · Zbl 0839.93072
[34] Srinivasan VS, Jafari MA (1994) Fault detection/monitoring using timed Petri Nets. IEEE Trans Syst Manag Cybern 23(4):1155–1162
[35] Yang CL, Onamoto H, Yokoyama A, Sekine Y (1992) Expert system for fault section estimation of power systems using time sequence information. Int J Electric Power Energy Syst 14(2/3): 225–232
[36] Zad SH, Kwong RH, Wonham WM (2003) Fault diagnosis in discrete-event systems: framework and model reduction. IEEE Trans Automat Control 48(7) · Zbl 1364.93464
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.