A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 9 Issue 2
Feb.  2022

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 7.847, Top 10% (SCI Q1)
    CiteScore: 13.0, Top 5% (Q1)
    Google Scholar h5-index: 64, TOP 7
Turn off MathJax
Article Contents
Dan You, Oussama Karoui and Shouguang 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: Dan You, Oussama Karoui and Shouguang 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

Computation of Minimal Siphons in Petri Nets Using Problem Partitioning Approaches

doi: 10.1109/JAS.2021.1004326
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
  • 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.

     

  • loading
  • [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 S4PR 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

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(4)  / Tables(1)

    Article Metrics

    Article views (1564) PDF downloads(50) Cited by()

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return