1. bookVolume 31 (2021): Issue 4 (December 2021)
    Advanced Machine Learning Techniques in Data Analysis (special section, pp. 549-611), Maciej Kusy, Rafał Scherer, and Adam Krzyżak (Eds.)
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

Analysis of safeness in a Petri net-based specification of the control part of cyber-physical systems

Published Online: 30 Dec 2021
Page range: 647 - 657
Received: 27 Apr 2021
Accepted: 04 Sep 2021
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
Abstract

The paper proposes an algorithm for safeness verification of a Petri net-based specification of the control part of cyber-physical systems. The method involves a linear algebra technique and is based on the computation of the state machine cover of a Petri net. Contrary to the well-known methods, the presented idea does not require obtaining all sequential components, nor the computation of all reachable states in the system. The efficiency and effectiveness of the proposed method have been verified experimentally with a set of 243 test modules (Petri net-based systems). The results of experiments show high efficiency of the proposed method since a solution has been found even for such nets where popular techniques are not able to analyze the safeness of the system. Finally, the presented algorithm is explained in detail using a real-life case-study example of the control part of a cyber-physical system.

Keywords

Aalst, W.M.P., Wil, Hee, K. and Kees (2004). Workflow Management—Models, Methods and Systems, MIT Press, Cambridge. Search in Google Scholar

Aalst, W.v.d. (2016). Process Mining: Data Science in Action, 2nd Edn, Springer, Berlin. Search in Google Scholar

Badouel, E., Bernardinello, L. and Darondeau, P. (1995). Polynomial algorithms for the synthesis of bounded nets, in P.D. Mosses et al. (Eds), TAPSOFT’95: Theory and Practice of Software Development, Springer, Berlin, pp. 364–378.10.1007/3-540-59293-8_207 Search in Google Scholar

Barkalov, A., Titarenko, L. and Mielcarek, K. (2018). Hardware reduction for lut–based mealy FSMs, International Journal of Applied Mathematics and Computer Science 28(3): 595–607, DOI: 10.2478/amcs-2018-0046.10.2478/amcs-2018-0046 Search in Google Scholar

Best, E., Devillers, R. and Koutny, M. (2001). Petri Net Algebra, Springer, Berlin.10.1007/978-3-662-04457-5 Search in Google Scholar

Best, E. and Wimmel, H. (2000). Reducing k-safe Petri nets to pomset-equivalent 1-safe petri nets, in M. Nielsen and D. Simpson (Eds), Application and Theory of Petri Nets 2000, Springer, Berlin, pp. 63–82.10.1007/3-540-44988-4_6 Search in Google Scholar

Carmona, J., Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L. and Yakovlev, A. (2008). A symbolic algorithm for the synthesis of bounded Petri nets, in K.M. van Hee and R. Valk (Eds), Applications and Theory of Petri Nets, Springer, Berlin, pp. 92–111.10.1007/978-3-540-68746-7_10 Search in Google Scholar

Chen, C., Liu, Z., Wan, S., Luan, J. and Pei, Q. (2020). Traffic flow prediction based on deep learning in internet of vehicles, IEEE Transactions on Intelligent Transportation Systems 22(6): 3776–3789.10.1109/TITS.2020.3025856 Search in Google Scholar

Cheng, A., Esparza, J. and Palsberg, J. (1995). Complexity results for 1-safe nets, Theoretical Computer Science 147(1–2): 117–136.10.1016/0304-3975(94)00231-7 Search in Google Scholar

Clempner, J. (2014). An analytical method for well-formed workflow/Petri net verification of classical soundness, International Journal of Applied Mathematics and Computer Science 24(4): 931–939, DOI: 10.2478/amcs-2014-0068.10.2478/amcs-2014-0068 Search in Google Scholar

Cortadella, J., Kishinevsky, M., Lavagno, L. and Yakovlev, A. (1998). Deriving Petri nets from finite transition systems, IEEE Transactions on Computers 47(8): 859–882.10.1109/12.707587 Search in Google Scholar

Dey, N., Ashour, A.S., Shi, F., Fong, S.J. and Tavares, J.M.R.S. (2018). Medical cyber-physical systems: A survey, Journal of Medical Systems 42(4) 1–13, Article no. 74. Search in Google Scholar

Dideban, A. and Alla, H. (2008). Reduction of constraints for controller synthesis based on safe Petri Nets, Automatica 44(7): 1697–1706.10.1016/j.automatica.2007.10.031 Search in Google Scholar

Du, N., Hu, H. and Zhou, M. (2020). Robust deadlock avoidance and control of automated manufacturing systems with assembly operations using Petri nets, IEEE Transactions on Automation Science and Engineering 17(4): 1961–1975.10.1109/TASE.2020.2983672 Search in Google Scholar

Esparza, J., Ledesma-Garza, R., Majumdar, R., Meyer, P. and Niksic, F. (2014). An SMT-based approach to coverability analysis, in A. Biere and R. Bloem (Eds), Computer Aided Verification, Springer, Cham, pp. 603–619.10.1007/978-3-319-08867-9_40 Search in Google Scholar

Fabre, E. (2006). On the construction of pullbacks for safe Petri nets, in S. Donatelli and P. S. Thiagarajan (Eds), Petri Nets and Other Models of Concurrency, ICATPN 2006, Springer, Berlin, pp. 166–180.10.1007/11767589_10 Search in Google Scholar

Feng, Y., Xing, K., Zhou, M., Wang, X. and Liu, H. (2020). Robust deadlock prevention for automated manufacturing systems with unreliable resources by using general Petri nets, IEEE Transactions on Systems, Man, and Cybernetics: Systems 50(10): 3515–3527.10.1109/TSMC.2018.2884316 Search in Google Scholar

Finkbeiner, B., Gieseking, M., Hecking-Harbusch, J. and Olderog, E.-R. (2020). AdamMC: A model checker for Petri nets with transits against flow-LTL, in S.K. Lahiri and C. Wang (Eds), Computer Aided Verification, Springer, Cham, pp. 64–76.10.1007/978-3-030-53291-8_5 Search in Google Scholar

Girault, C. and Valk, R. (2003). Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, Springer, Berlin.10.1007/978-3-662-05324-9 Search in Google Scholar

Giua, A. and Xie, X. (2005). Control of safe ordinary Petri nets using unfolding, Discrete Event Dynamic Systems 15(4): 349–373.10.1007/s10626-005-4057-z Search in Google Scholar

Guo, H., Man, K.L., Ren, Q., Huang, Q., Hahanov, V., Litvinova, E. and Chumachenko, S. (2017). FPGA implementation of VLC communication technology, 31st International Conference on Advanced Information Networking and Applications Workshops (WAINA), Taipei, Taiwan, pp. 586–590. Search in Google Scholar

Guo, Y., Hu, X., Hu, B., Cheng, J., Zhou, M. and Kwok, R.Y.K. (2018). Mobile cyber physical systems: Current challenges and future networking applications, IEEE Access 6: 12360–12368.10.1109/ACCESS.2017.2782881 Search in Google Scholar

Hahanov, V., Hussein, M.A.A., Hahanova, A. and Man, K.L. (2016). Cyber physical computing, 2016 IEEE East-West Design Test Symposium (EWDTS), Yerevan, Armenia, pp. 1–8. Search in Google Scholar

Huang, B., Zhou, M., Wang, C., Abusorrah, A. and Al-Turki, Y. (2021). Deadlock-free supervisor design for robotic manufacturing cells with uncontrollable and unobservable events, IEEE/CAA Journal of Automatica Sinica 8(3): 597–605.10.1109/JAS.2020.1003207 Search in Google Scholar

Huang, D., Deng, Z., Wan, S., Mi, B. and Liu, Y. (2018). Identification and prediction of urban traffic congestion via cyber-physical link optimization, IEEE Access 6: 63268–63278.10.1109/ACCESS.2018.2875239 Search in Google Scholar

Jasiul, B., Szpyrka, M. and Śliwa, J. (2015). Formal specification of malware models in the form of colored Petri nets, in J.J.J.H. Park et al. (Eds), Computer Science and Its Applications, Springer, Berlin, pp. 475–482.10.1007/978-3-662-45402-2_71 Search in Google Scholar

Jiang, Z., Li, Z., Wu, N. and Zhou, M. (2018). A Petri net approach to fault diagnosis and restoration for power transmission systems to avoid the output interruption of substations, IEEE Systems Journal 12(3): 2566–2576.10.1109/JSYST.2017.2682185 Search in Google Scholar

Kaid, H., Al-Ahmari, A., Li, Z. and Davidrajuh, R. (2020). Automatic supervisory controller for deadlock control in reconfigurable manufacturing systems with dynamic changes, Applied Sciences 10(15): 1–34, Article no. 5270. Search in Google Scholar

Karatkevich, A. (2007). Dynamic Analysis of Petri Net-Based Discrete Systems, Springer, Berlin. Search in Google Scholar

Koh, I. and DiCesare, F. (1990). Transformation methods for generalized Petri nets and their applications to flexible manufacturing systems, Rensselaer’s 2nd International Conference on Computer Integrated Manufacturing, Troy, USA, pp. 364–371. Search in Google Scholar

Lee, E.A. and Seshia, S.A. (2016). Introduction to Embedded Systems: A Cyber-Physical Systems Approach, 2nd Edn, MIT Press, Cambridge. Search in Google Scholar

Li, B., Khlif-Bouassida, M. and Toguyéni, A. (2018). On-the-fly diagnosability analysis of bounded and unbounded labeled Petri nets using verifier nets, International Journal of Applied Mathematics and Computer Science 28(2): 269–281, DOI: 10.2478/amcs-2018-0019.10.2478/amcs-2018-0019 Search in Google Scholar

Lizarraga, A., Begovich, O. and Ramírez, A. (2020). Fault diagnosis for a three-wheel omidirectional vehicle: A geometric approach, 17th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE), Mexico City, USA, pp. 1–6. Search in Google Scholar

Luo, J., Liu, Z., Wang, S. and Xing, K. (2020). Robust deadlock avoidance policy for automated manufacturing system with multiple unreliable resources, IEEE/CAA Journal of Auto-matica Sinica 7(3): 812–821.10.1109/JAS.2020.1003096 Search in Google Scholar

Martínez, J. and Silva, M. (1982). A simple and fast algorithm to obtain all invariants of a generalised Petri net, in C. Girault and W. Reisig (Eds), Application and Theory of Petri Nets, Springer, Berlin, pp. 301–310.10.1007/978-3-642-68353-4_47 Search in Google Scholar

Murata, T. (1989). Petri nets: Properties, analysis and applications, Proceedings of the IEEE 77(4): 541–580.10.1109/5.24143 Search in Google Scholar

Pan, L., Yang, B., Jiang, J. and Zhou, M. (2020). A time Petri Net with relaxed mixed semantics for schedulability analysis of flexible manufacturing systems, IEEE Access 8: 46480–46492.10.1109/ACCESS.2020.2978101 Search in Google Scholar

Rajkumar, R.R., Lee, I., Sha, L. and Stankovic, J. (2010). Cyber-physical systems: The next computing revolution, 47th Design Automation Conference, DAC’10, Anaheim, USA, p. 731. Search in Google Scholar

Ramirez-Trevino, A., Ruiz-Beltran, E., Rivera-Rangel, I. and Lopez-Mellado, E. (2007). Online fault diagnosis of discrete event systems: A Petri net-based approach, IEEE Transactions on Automation Science and Engineering 4(1): 31–39.10.1109/TASE.2006.872120 Search in Google Scholar

Ran, N., Hao, J., He, Z. and Seatzu, C. (2018a). Diagnosability analysis of bounded Petri nets, IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA), Turin, Italy, Vol. 1, pp. 1145–1148.10.1109/ETFA.2018.8502652 Search in Google Scholar

Ran, N., Su, H., Giua, A. and Seatzu, C. (2018b). Codiagnosability analysis of bounded Petri nets, IEEE Transactions on Automatic Control 63(4): 1192–1199.10.1109/TAC.2017.2742659 Search in Google Scholar

Ran, N., Su, H. and Wang, S. (2017). An improved approach to test diagnosability of bounded petri nets, IEEE/CAA Journal of Automatica Sinica 4(2): 297–303.10.1109/JAS.2017.7510406 Search in Google Scholar

Shih, C.-S., Chou, J.-J., Reijers, N. and Kuo, T.-W. (2016). Designing CPS/IoT applications for smart buildings and cities, IET Cyber-Physical Systems: Theory Applications 1(1): 3–12.10.1049/iet-cps.2016.0025 Search in Google Scholar

Szpyrka, M. and Jasiul, B. (2017). Evaluation of cyber security and modelling of risk propagation with Petri nets, Symmetry 9(3): 32.10.3390/sym9030032 Search in Google Scholar

White, A., Karimoddini, A. and Karimadini, M. (2020). Resilient fault diagnosis under imperfect observations—A need for Industry 4.0 era, IEEE/CAA Journal of Automatica Sinica 7(5): 1279–1288. Search in Google Scholar

Wiśniewski, R. (2017). Prototyping of Concurrent Control Systems Implemented in FPGA Devices, Springer, Cham.10.1007/978-3-319-45811-3 Search in Google Scholar

Wiśniewski, R., Barkalov, A., Titarenko, L. and Halang, W. (2011). Design of microprogrammed controllers to be implemented in FPGAs, International Journal of Applied Mathematics and Computer Science 21(2): 401–412, DOI: 10.2478/v10006-011-0030-1.10.2478/v10006-011-0030-1 Search in Google Scholar

Wiśniewski, R., Bazydło, G., Szcześniak, P. and Wojnakowski, M. (2019a). Petri net-based specification of cyber-physical systems oriented to control direct matrix converters with space vector modulation, IEEE Access 7: 23407–23420.10.1109/ACCESS.2019.2899316 Search in Google Scholar

Wiśniewski, R., Karatkevich, A., Adamski, M., Costa, A. and Gomes, L. (2018). Prototyping of concurrent control systems with application of Petri nets and comparability graphs, IEEE Transactions on Control Systems Technology 26(2): 575–586.10.1109/TCST.2017.2692204 Search in Google Scholar

Wisniewski, R., Grobelna, I. and Karatkevich, A. (2020). Determinism in cyber-physical systems specified by interpreted Petri nets, Sensors 20(19): 1–22, Article no. 5565. Search in Google Scholar

Wiśniewski, R., Wiśniewska, M. and Jarnut, M. (2019b). C-exact hypergraphs in concurrency and sequentiality analyses of cyber-physical systems specified by safe Petri nets, IEEE Access 7: 13510–13522.10.1109/ACCESS.2019.2893284 Search in Google Scholar

Xia, C. and Li, C. (2021). Property preservation of Petri synthesis net based representation for embedded systems, IEEE/CAA Journal of Automatica Sinica 8(4): 905–915.10.1109/JAS.2020.1003003 Search in Google Scholar

Yang, F., Wu, N., Qiao, Y., Zhou, M., Su, R. and Qu, T. (2018). Petri net-based efficient determination of optimal schedules for transport-dominant single-arm multi-cluster tools, IEEE Access 6: 355–365.10.1109/ACCESS.2017.2763778 Search in Google Scholar

Zaitsev, D.A. (2006). Compositional analysis of Petri nets, Cybernetics and Systems Analysis 42(1): 126–136.10.1007/s10559-006-0044-0 Search in Google Scholar

Zaitsev, D.A. (2016). Sleptsov nets run fast, IEEE Transactions on Systems, Man, and Cybernetics: Systems 46(5): 682–693.10.1109/TSMC.2015.2444414 Search in Google Scholar

Zaitsev, D.A., Shmeleva, T.R. and Groote, J.F. (2019). Verification of hypertorus communication grids by infinite Petri nets and process algebra, IEEE/CAA Journal of Auto-matica Sinica 6(3): 733–742.10.1109/JAS.2019.1911486 Search in Google Scholar

Zhang, Y., Qiu, M., Tsai, C.-W., Hassan, M.M. and Alamri, A. (2017). Health-CPS: Healthcare cyber-physical system assisted by cloud and big data, IEEE Systems Journal 11(1): 88–95.10.1109/JSYST.2015.2460747 Search in Google Scholar

Zhou, M. and Wu, N. (2009). System Modeling and Control with Resource-Oriented Petri Nets, 1st Edn, CRC Press, Boca Raton. Search in Google Scholar

Zhu, Q., Zhou, M., Qiao, Y. and Wu, N. (2018). Petri net modeling and scheduling of a close-down process for time-constrained single-arm cluster tools, IEEE Transactions on Systems, Man, and Cybernetics: Systems 48(3): 389–400.10.1109/TSMC.2016.2598303 Search in Google Scholar

Zurawski, R. and Zhou, M. (1994). Petri nets and industrial applications: A tutorial, IEEE Transactions on Industrial Electronics 41(6): 567–583.10.1109/41.334574 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo