article

On K-diagnosability of Petri nets via integer linear programming

Authors:

G. De TommasiAuthors Info & Claims

Automatica (Journal of IFAC), Volume 48, Issue 9

Pages 2047 - 2058

https://doi.org/10.1016/j.automatica.2012.06.039

Published: 01 September 2012 Publication History

Abstract

This paper deals with the problem of diagnosability of a fault after the firing of a finite number events (i.e., K-diagnosability). This problem corresponds to diagnosability of a fault within a finite delay in the context of discrete event systems. The main contribution of this paper is a necessary and sufficient condition for K-diagnosability of bounded nets. The proposed approach exploits the mathematical representation of Petri nets and the Integer Linear Programming optimization tool. In particular no specific assumptions are made on the structure of the net induced by the unobservable transitions, since the proposed approach permits to detect also the undiagnosability due to the presence of unobservable cycles.

References

[1]

Basile, F., Chiacchio, P., & De Tommasi, G. (2008). Sufficient conditions for diagnosability of Petri nets. In Proc. of the 9th international workshop on discrete event systems, WODES'08. Göteborg, Sweden. May (pp. 436-442).

[2]

An efficient approach for online diagnosis of discrete event systems. IEEE Transactions on Automatic Control. v54 i4. 748-759.

[3]

Basile, F., Chiacchio, P., & De Tommasi, G. (2009b). Online diagnosis of discrete events systems based on Petri nets and integer linear programming. In Proc. 2nd IFAC workshop on dependable control of discrete systems, DCDS'09. Bari, Italy. June (pp. 111-116).

[4]

Boel, R. K., & Jiroveanu, G. (2004). Contextual distributed diagnosis for very large systems. In 16th int. symp. on mathematical theory of networks and systems. Leuven, Belgium. July.

[5]

Cabasino, M. P., Giua, A., Lafortune, S., & Seatzu, C. (2009a). Diagnosability analysis of unbounded Petri nets. In Proc. of the 48th IEEE conf. on decision and control. Shangai, China. December (pp. 1267-1272).

[6]

Cabasino, M. P., Giua, A., & Seatzu, C. (2009b). Diagnosability analysis of bounded Petri nets. In Proc. of the 48th IEEE conf. on decision and control. Shangai, China. December (pp. 1254-1260).

[7]

Fault detection for discrete event systems using Petri nets with unobservable transitions. Automatica. v46 i9. 1531-1539.

[8]

Introduction to discrete event systems. Springer.

[9]

Cassez, F., Tripakis, S., & Altisen, K. (2007). Sensor minimization problems with static or dynamic observers for fault diagnosis. In 7th Int. conf. application of concurrency to system design. Bratislava, Slovak Republic. July.

Digital Library

[10]

Diagnosing PN-based models with partial observable transitions. International Journal of Computer Integrated Manufacturing. v18 i2-3. 158-169.

[11]

Coordinated decentralized protocols for failure diagnosis of discrete event systems. Discrete Event Dynamic Systems. v10 i1. 33-86.

[12]

Reduction of constraints for controller synthesis based on safe Petri nets. Automatica. v44 i7. 1697-1706.

[13]

Fault detection of discrete event systems by Petri nets and integer linear programming. Automatica. v45 i11. 2665-2672.

[14]

García Vallés, F. (1999). Contributions to the structural and symbolic analysis of place/transition nets with applications to flexible manufacturing systems and asynchronous circuits. Ph.D. Thesis. Universidad de Zaragoza.

[15]

GLPK, (2008). GNU linear programming kit. http://www.gnu.org/software/glpk/.

[16]

Graph theoretic bound on number of A.C.I.M. for random transformation. Proceedings of the American Mathematical Society. v116 i2. 401-410.

[17]

Modeling and control of discrete event dynamic systems. Springer, London, UK.

[18]

The diagnosability of Petri net models using minimal explanations. IEEE Transactions on Automatic Control. v55 i7. 1663-1668.

[19]

Diagnosis of DES with Petri net models. IEEE Transactions on Automation Science and Engineering. v4 i1. 114-118.

[20]

State observation and diagnosis of discrete-event systems described by stochastic automata. Discrete Event Dynamic Systems. v11 i4. 319-369.

[21]

Petri nets: properties, analysis and applications. Proceedings of the IEEE. v77 i4. 541-580.

[22]

Netlab, (2011). http://www.irt.rwth-aachen.de/en/fuer-studierende/downloads/petri-net-tool-netlab/.

[23]

Safe diagnosability for fault-tolerant supervision of discrete-event systems. Automatica. v41 i8. 1335-1347.

[24]

Diagnosability of discrete event systems. IEEE Transactions on Automatic Control. v40 i9. 1555-1575.

[25]

Failure diagnosis using discrete-event models. IEEE Transactions on Control Systems Technology. v4 i2. 105-124.

[26]

Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In: Lectures notes in computer science, Vol. 616. Springer-Verlag. pp. 309-373.

[27]

Liveness and home states in equal conflict systems. In: Proceedings of the 14th international conference on application and theory of Petri nets, Springer-Verlag, London, UK. pp. 415-432.

[28]

Online fault diagnosis of discrete event systems. A Petri net-based approach. IEEE Transactions on Automation Science and Engineering. v4 i1. 31-39.

[29]

Ushio, T., Onishi, L., & Okuda, K. (1998). Fault detection based on Petri net models with faulty behaviors. In Proc. of the 1998 IEEE conf. on systems, man, and cybernetics. San Diego, CA, USA. October (pp. 113-118).

[30]

Wen, Y., Li, C., & Jeng, M. (2005). A polynomial algorithm for checking diagnosability of Petri nets. In Proc. of the 2005 IEEE conf. on systems, man, and cybernetics, SMC'05. Vol. 3. October (pp. 2542-2547).

[31]

Algebraic approaches for fault identification in discrete-event systems. IEEE Transactions on Automatic Control. v50 i12. 2048-2053.

[32]

Fault diagnosis in discrete-event systems: framework and model reduction. IEEE Transactions on Automatic Control. v48 i7. 1199-1212.

[33]

Diagnosis in discrete-event systems: incorporating timing information. IEEE Transactions on Automatic Control. v50 i7. 1010-1015.

Cited By

Declerck P(2024)Offline analysis of the relaxed upper boundedness for online estimation ofoptimal event sequences in Partially Observable Petri NetsDiscrete Event Dynamic Systems10.1007/s10626-024-00396-034:2(351-374)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10626-024-00396-0
Zhang MAlfieri AMatta A(2024)Generation of mathematical programming representations for discrete event simulation models of timed petri netsDiscrete Event Dynamic Systems10.1007/s10626-023-00387-734:1(1-19)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10626-023-00387-7
Declerck P(2021)Counter approach for the estimation of optimal sequences in Partially Observable Untimed Petri NetsDiscrete Event Dynamic Systems10.1007/s10626-021-00341-531:4(489-512)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10626-021-00341-5
Show More Cited By

Recommendations

Diagnosability of Petri nets with observation graphs

This paper addresses the problem of diagnosability for dynamic discrete event systems modeled with bounded or unbounded Petri nets that are deadlock-free and monitored with sensor configurations with marking and event measurements. The proposed method ...
K-diagnosability analysis of bounded and unbounded Petri nets using linear optimization
Abstract
We propose an algebraic approach to investigate K-diagnosability of partially observed labeled Petri nets which can be either bounded or unbounded. Namely, a necessary and sufficient condition for K-diagnosability is established based ...
Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming

This article develops a deadlock prevention policy for a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems. The analysis of such a system leads us to characterise the deadlock situations in terms of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier Ltd © 2012.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 September 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Declerck P(2024)Offline analysis of the relaxed upper boundedness for online estimation ofoptimal event sequences in Partially Observable Petri NetsDiscrete Event Dynamic Systems10.1007/s10626-024-00396-034:2(351-374)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10626-024-00396-0
Zhang MAlfieri AMatta A(2024)Generation of mathematical programming representations for discrete event simulation models of timed petri netsDiscrete Event Dynamic Systems10.1007/s10626-023-00387-734:1(1-19)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10626-023-00387-7
Declerck P(2021)Counter approach for the estimation of optimal sequences in Partially Observable Untimed Petri NetsDiscrete Event Dynamic Systems10.1007/s10626-021-00341-531:4(489-512)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10626-021-00341-5
Boussif AGhazel MKlai K(2021)A semi‐symbolic diagnoser for fault diagnosis of bounded labeled petri netsAsian Journal of Control10.1002/asjc.225923:2(648-660)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1002/asjc.2259
Lefebvre DHadjicostis C(2020)Privacy and safety analysis of timed stochastic discrete event systems using Markovian trajectory-observersDiscrete Event Dynamic Systems10.1007/s10626-019-00307-830:3(413-440)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s10626-019-00307-8
Hu YMa ZLi Z(2019)Active Diagnosis of Petri Nets Using Q-Diagnoser2019 IEEE 15th International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2019.8842930(203-208)Online publication date: 22-Aug-2019
https://dl.acm.org/doi/10.1109/COASE.2019.8842930
(2018)Fault diagnosis of discrete-event systems based on the symbolic observation graphInternational Journal of Critical Computer-Based Systems10.5555/3302636.33026388:2(141-168)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3302636.3302638
Li BKhlif-Bouassida MToguyéni A(2018)On–The–Fly Diagnosability Analysis of Bounded and Unbounded Labeled Petri Nets Using Verifier NetsInternational Journal of Applied Mathematics and Computer Science10.2478/amcs-2018-001928:2(269-281)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.2478/amcs-2018-0019
(2018)Diagnosability analysis and fault diagnosis of P-time labelled Petri netsInternational Journal of Critical Computer-Based Systems10.1504/IJCCBS.2018.0918568:1(78-103)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJCCBS.2018.091856
Ran NHao JHe ZSeatzu C(2018)Diagnosability analysis of bounded Petri nets2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA.2018.8502652(1145-1148)Online publication date: 4-Sep-2018
https://dl.acm.org/doi/10.1109/ETFA.2018.8502652
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents