Computation of Minimal Siphons in Petri Nets Using Problem Partitioning Approaches

Dan You; Oussama Karoui; Shouguang Wang

doi:10.1109/JAS.2021.1004326

Volume 9 Issue 2

Feb. 2022

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2022 > 9(2): 329-338

D. You, O. Karoui, and S. G. Wang, “Computation of minimal siphons in Petri nets using problem partitioning approaches,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 2, pp. 329–338, Feb. 2022. doi: 10.1109/JAS.2021.1004326

Citation:

D. You, O. Karoui, and S. G. Wang, “Computation of minimal siphons in Petri nets using problem partitioning approaches,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 2, pp. 329–338, Feb. 2022. doi: 10.1109/JAS.2021.1004326

Citation:

PDF( 1227 KB)

Computation of Minimal Siphons in Petri Nets Using Problem Partitioning Approaches

doi: 10.1109/JAS.2021.1004326

School of Information and Electronic Engineering (Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018, China

Funds: This is an extended version of our previous paper that was presented in IEEE Conference on Decision and Control. Compared with the conference paper, the main differences of this paper lie in: Formal proofs of all the theoretical results, complexity analysis of the proposed method, and more detailed explanations of the proposed method. This work was supported in part by the Zhejiang Natural Science Foundation (LQ20F020009), the Zhejiang Provincial Key Laboratory of New Network Standards and Technologies (2013E10012), and the Public Technology Research Plan of Zhejiang Province (LGJ21F030001)

More Information

Author Bio:
Dan You (Member, IEEE) received the B.S. and M.S. degrees from the School of Information and Electronic Engineering, Zhejiang Gongshang University, China, in 2014 and 2017, respectively, and the Ph.D. degree from the Department of Electrical and the Electronic Engineering, the University of Cagliari, Italy, in 2021. She is currently a Member of the Discrete-Event System Group, School of Information and Electronic Engineering, Zhejiang Gongshang University. Her research interests include supervisory control of discrete event systems, fault prediction, and deadlock control and siphon computation in Petri nets

Oussama Karoui (Associate Member, IEEE) received the B.S. and M.S. degrees in computer networks and telecommunications from the National Institute of Applied Sciences and Technology, Tunis, Tunisia, in 2012 and 2015, respectively, and the Ph.D. degree in computer technology and application from Macau University of Science and Technology, Macau, China, in 2018. He joined the School of Information and Electronic Engineering (Sussex AI Institute) at Zhejiang Gongshang University, Hangzhou, China, in 2019. His current research interests include modeling, control and scheduling of discrete event systems, intelligent transportation systems, mobile robotics, and machine learning

Shouguang Wang (Senior Member, IEEE) received the B.S. degree in computer science from the Changsha University of Science and Technology, Changsha, China, in 2000, and the Ph.D. degree in electrical engineering from Zhejiang University, Hangzhou, China, in 2005. He joined Zhejiang Gongshang University in 2005, where he is currently a Professor with the School of Information and Electronic Engineering, the Director of the Discrete-Event Systems Group, and the Dean of System modeling and Control Research Institute, Zhejiang Gongshang University. He is currently an Associate Editor of IEEE Access and IEEE/CAA Journal of Automatica Sinica. He was a Visiting Professor with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, from 2011 to 2012. He is a Visiting Professor with the Electrical and Electronic Engineering Department, University of Cagliari, Cagliari, Italy, from 2014 to 2015. He was the Dean of the Department of Measuring and Control Technology and Instrument in Zhejiang Gongshang University from 2011 to 2014. His research interests include supervisory control of discrete event systems and siphon computation in Petri nets
Corresponding author: Oussama Karoui, e-mail: rtkaroui@gmail.com
Received Date: 2021-04-16
Revised Date: 2021-05-28
Accepted Date: 2021-06-22

Available Online: 2021-07-14

Abstract

Abstract

A large amount of research has shown the vitality of siphon enumeration in the analysis and control of deadlocks in various resource-allocation systems modeled by Petri nets (PNs). In this paper, we propose an algorithm for the enumeration of minimal siphons in PN based on problem decomposition. The proposed algorithm is an improved version of the global partitioning minimal-siphon enumeration (GPMSE) proposed by Cordone et al. (2005) in IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, which is widely used in the literature to compute minimal siphons. The experimental results show that the proposed algorithm consumes lower computational time and memory compared with GPMSE, which becomes more evident when the size of the handled net grows.
- Petri nets (PNs),
- problem decomposition,
- resource-allocation systems,
- siphons

FullText(HTML)

References(35)

References

[1]	A. Giua and M. Silva, “Petri nets and automatic control: A historical perspective,” Annual Reviews in Control, vol. 45, pp. 223–239, 2018. doi: 10.1016/j.arcontrol.2018.04.006
[2]	K. Y. Xing, M. C. Zhou, F. Wang, H. Liu, and F. Tian, “Resource-transition circuits and siphons for deadlock control of automated manufacturing systems,” IEEE Trans. Syst. Man Cybern. Part A, vol. 41, no. 1, pp. 74–84, 2011. doi: 10.1109/TSMCA.2010.2048898
[3]	X. Wang and H. Hu, “A robust control approach to automated manufacturing systems allowing multi-type and multi-quantity of resources with Petri nets”, IEEE Trans. Syst., Man, Cybern., Syst., to be published, DOI: 10.1109/TSMC.2018.2852946.
[4]	M. Uzam, G. Gelen, and T. L. Saleh, “Think-globally-act-locally approach with weighted arcs to the synthesis of a liveness-enforcing supervisor for generalized Petri nets modeling FMSs,” Inf. Sci., vol. 363, pp. 235–260, 2016. doi: 10.1016/j.ins.2015.09.010
[5]	Q. Zeng, C. Liu, H. Duan, and M. Zhou, “Resource conflict checking and resolution controller design for cross-organization emergency response,” IEEE Trans. Systems,Man and Cybernetics:Systems, vol. 50, no. 10, pp. 3685–3700, 2020. doi: 10.1109/TSMC.2019.2906335
[6]	Q. Zeng, C. Liu, and H. Duan, “Resource conflict detection and removal strategy for nondeterministic emergency response processes using Petri nets,” Enterprise Information Systems, vol. 10, no. 7, pp. 729–750, 2016. doi: 10.1080/17517575.2014.986215
[7]	G. Y. Liu and K. Barkaoui, “A survey of siphons in Petri nets,” Inf. Sci., vol. 363, pp. 198–220, 2015.
[8]	S. Wang, W. Duo, X. Guo, X. Jiang, D. You, K. Barkaoui and M. Zhou, “Computation of an emptiable minimal siphon in a subclass of Petri nets using mixed-integer programming,” IEEE/CAA Journal of Automatica Sinica, vol. 8, no. 1, pp. 219–226, 2021.
[9]	D. You, S. Wang, and M. Zhou, “Computation of strict minimal siphons in a class of Petri nets based on problem decomposition,” Inf. Sci., vol. 409–410, pp. 87–100, Oct. 2017.
[10]	M. Gan, S. Wang, Z. Ding, M. Zhou, and W. Wu, “An improved mixed-integer programming method to compute emptiable minimal siphons in S3PR nets,” IEEE Trans. Control Systems Technology, vol. 26, no. 6, pp. 2135–2140, 2017.
[11]	Y. Hou, K. Barkaoui, “Deadlock analysis and control based on Petri nets: A siphon approach review,” Advances in Mechanical Engineering, vol. 9, no. 5, pp. 1–30, 2017.
[12]	S. G. Wang, C. Y. Wang, M. C. Zhou, and Z. W. Li, “A method to compute strict minimal siphons in S3PR based on loop resource subsets,” IEEE Trans. Syst.,Man,Cybern.,A,Syst.,Humans, vol. 42, no. 1, pp. 226–237, 2012. doi: 10.1109/TSMCA.2011.2159590
[13]	S. G. Wang, C. Y. Wang, M. C. Zhou, “Controllability conditions of resultant siphons in a class of Petri nets,” IEEE Trans. Syst. Man Cybern. Part A, vol. 42, no. 5, pp. 1206–1215, 2012. doi: 10.1109/TSMCA.2011.2170419
[14]	S. Tanimoto, M. Yamauchi, and T. Watanabe, “Finding minimal siphons in general Petri nets,” IEICE Trans. Fundam., vol. E79-A, no. 11, pp. 1817–1824, 1996.
[15]	B. Huang, M. Zhou, C. Wang, A. Abusorrah, and Y. Al-Turki, “Deadlock-free supervisor design for robotic manufacturing cells with uncontrollable and unobservable events,” IEEE/CAA Journal of Automatica Sinica, vol. 8, no. 3, pp. 597–605, 2020.
[16]	J. Luo, Z. Liu, S. Wang, and K. Xing, “Robust Deadlock Avoidance Policy for Automated Manufacturing System With Multiple Unreliable Resources,” IEEE/CAA Journal of Automatica Sinica, vol. 7, no. 3, pp. 812–821, 2020. doi: 10.1109/JAS.2020.1003096
[17]	O. Karoui, Y. Chen, Z. Li, N. Wu and M. Khalgui, “On hierarchical construction of the state space of an automated manufacturing system modeled with Petri nets,” IEEE Trans. Systems,Man,and Cybernetics:Systems, vol. 50, no. 10, pp. 3613–3627, Oct. 2020. doi: 10.1109/TSMC.2018.2854158
[18]	J. Ezpeleta, J.M. Colom, J. Martinez, “A Petri net based deadlock prevention policy for flexible manufacturing systems,” IEEE Trans. on Robot. Autom., vol. 11, no. 2, pp. 173–184, 1995. doi: 10.1109/70.370500
[19]	C. F. Zhong, Z. W. Li, & Barkaoui, K., “Monitor design for siphon control in S4R nets: from structure analysis points of view,” Int. J. Innovative Comput.,Inf. Control, vol. 7, no. 12, pp. 6677–6690, 2011.
[20]	D. You, S. Wang, W. Dai, W. Wu, and Y. Jia, “An approach for enumerating minimal siphons in a subclass of Petri nets,” IEEE Access, vol. 12, no. 6, pp. 4255–4265, 2018.
[21]	S. Wang, D. You, and M. Zhou, “A necessary and sufficient condition for a resource subset to generate a strict minimal siphon in S4PR,” IEEE Trans. Autom. Control, vol. 62, no. 8, pp. 4173–4179, Aug. 2017. doi: 10.1109/TAC.2017.2677859
[22]	Q. Zhuang, W. Dai, S. Wang, and F. Ning, “Deadlock prevention policy for S4PR nets based on siphon,” IEEE Access, vol. 6, pp. 50648–50658, 2018. doi: 10.1109/ACCESS.2018.2868981
[23]	F. Tricas and J. Ezpeleta, “Computing minimal siphons in Petri net models of resource allocation systems: A parallel solution,” IEEE Trans. Systems,Man,and Cybernetics,Part A:Systems and Humans, vol. 36, no. 3, pp. 532–539, 2006. doi: 10.1109/TSMCA.2005.855751
[24]	A. R. Wang, Z. W. Li, J. Y. Jia, and M. C. Zhou, “An effective algorithm to find elementary siphons in a class of Petri nets,” IEEE Trans. Systems,Man and Cybernetics,Part A, vol. 39, no. 4, pp. 912–923, Jul. 2009. doi: 10.1109/TSMCA.2009.2019880
[25]	Z. W. Li and M. C. Zhou, “On siphon computation for deadlock control in a class of Petri nets,” IEEE Trans. Syst.,Man,Cybern.,A,Syst.,Humans, vol. 38, no. 3, pp. 667–679, 2008. doi: 10.1109/TSMCA.2008.918605
[26]	E. E. Cano, C. A. Rovetto, J. M. Colom, “An algorithm to compute the minimal siphons in S⁴PR nets,” Discrete Event Dynamic Systems, vol. 22, no. 4, pp. 403–428, 2012. doi: 10.1007/s10626-012-0132-4
[27]	F. Tricas, J. M. Colom, and J. J. Merelo, “Using the incidence matrix in an evolutionary algorithm for computing minimal siphons in Petri net models,” In Proc. 18th Int. Conf. System Theory, Control and Computing, Sinaia, Romania, 2014, pp. 645–651.
[28]	F. Tricas, J. M. Colom, and J. J. Merelo, “Computing minimal siphons in Petri net models of resource allocation systems: An evolutionary approach,” In Proc. Int. Workshop on Petri Nets and Software Engineering (PNSE’14), Tunis, 2014, Tunisia, pp. 307–322.
[29]	L. Piroddi, R. Cordone, and I. Fumagalli, “Combined siphon and marking generation for deadlock prevention in Petri nets,” IEEE Trans. Systems,Man,and Cybernetics,Part A:Systems and Humans, vol. 39, no. 3, pp. 650–661, 2009. doi: 10.1109/TSMCA.2009.2013189
[30]	P. H. Starke, “INA: Integrated net analyzer,” 1992. [Online]. Available: http://www2.informatik.huberlin.de/~starke/ina.html.
[31]	X. Han, Z. Chen, Z. Liu and Q. Zhang, “Calculation of siphons and minimal siphons in Petri nets based on semi-tensor product of matrices,” IEEE Trans. Systems,Man,and Cybernetics:Systems, vol. 47, no. 3, pp. 531–536, 2017. doi: 10.1109/TSMC.2015.2507162
[32]	R. Cordone, L. Ferrarini, and L. Piroddi, “Enumeration algorithms for minimal siphons in Petri nets based on place constraints,” IEEE Trans. Syst.,Man,Cybern.,A,Syst.,Humans, vol. 35, no. 6, pp. 844–854, Nov. 2005. doi: 10.1109/TSMCA.2005.853504
[33]	T. Murata, “Petri nets: Properties, analysis and applications”, in Proc IEEE, 1989, vol. 77, no. 4, pp. 541–580.
[34]	“The tools for GPMSE, GPMSE with the depth-first search, and IGPMSE”, 2015. [Online]. Available: https://www.dropbox.com/s/7cpho1ka35gpq3i/Tools.zip?dl=0
[35]	C. Chen and H. S. Hu, “Liveness-enforcing supervision in AMS-oriented HAMGs: An approach based on new characterization of siphons using Petri nets,” IEEE Trans. Autom. Control, vol. 63, no. 7, pp. 1987–2002, Jul. 2018. doi: 10.1109/TAC.2017.2758842

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(4) / Tables(1)

Get Citation

PDF

XML

Article Metrics

Article views (1721) PDF downloads(82)

Highlights

an algorithm based on problem partitioning is proposed for the enumeration of minimal siphons in a Petri net
the proposed algorithm is an improved version of the global partitioning minimal-siphon enumeration (GPMSE) proposed by Cordone et al. (2005) in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
the proposed algorithm behaves better than GPMSE in both computational time and memory consumption

Computation of Minimal Siphons in Petri Nets Using Problem Partitioning Approaches

doi: 10.1109/JAS.2021.1004326

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content