A Survey of Reachability Trees of Unbounded Petri Nets
-
摘要: Petri网自提出以来得到了学术界和工业界的广泛关注. Petri网系统的可达性是最基本性质之一.系统的其他相关性质都可以通过可达性进行分析.利用等价的有限可达树来研究无界Petri网可达性,依然是一个开放性问题.该研究可以追溯到40年前,但由于问题本身的复杂性和难度太大,直到最近20年,经过国内外诸多学者的不懈努力,才逐渐取得了一些阶段性的成果和部分突破.本文回顾了近40年来国内外学者为彻底解决该问题作出的贡献.重点对4种开创性的研究成果展开讨论,分别为有限可达树、扩展可达树、改进可达树及新型改进可达树.探讨了今后无界Petri网可达性问题的研究方向.Abstract: In recent years both industry and academia have paid much attention to the theory and applications of Petri nets. Reachability is a basic property of a Petri net, and many properties can be analyzed via it. However, analyzing the reachability problem of unbounded Petri nets by finite reachability trees has been an open problem since the inception of Petri nets. Researchers began to study the problem of reachability trees over 40 years ago. However, they made only limited progress over the last 20 years due to its complexity and difficulty. We present an overview of some important contributions toward its solution. The focuses are on four novel finite reachability trees: finite reachability tree(FRT), augmented reachability tree(ART), modified reachability tree(MRT) and new modified reachailbity tree(NMRT). The paper concludes with a discussion of directions for future research of the reachability problem of unbounded Petri nets.
-
Key words:
- Unbounded Petri nets /
- reachability tree /
- reachability problem /
- discrete event system
-
[1] Petri C A. Kommunikation Mit Automater [Ph.D. dissertation], Insitiut fur Instrumentelle Mathematik Schriften des ⅡM Nr.z, Germany. 1962. [2] [2] Bourdeaud'huy T, Hanafi S, Yim P. Solving the Petri Nets Reachability Problem Using the Logical Abstraction Technique and Mathematical Programming. Berlin:Springer, 2004. 112-126 [3] [3] Finkel A. The Minimal Coverability Graph for Petri Nets. Berlin:Springer Berlin Heidelberg, 1993. 210-243 [4] [4] Hrz B, Zhou M C. Modeling and Control of Discrete-Event Dynamic Systems:With Petri Nets and Other Tools. Berlin:Springer, 2007. [5] [5] Keller R M. Vector Replacement Systems:A Formalism for Modeling Asynchronous Systems. Princeton:Department of Electrical Engineering Computer Sciences Laboratory Princeton University, 1972. [6] [6] Li Z W, Zhou M C. Deadlock Resolution in Automated Manufacturing Systems:A Novel Petri Net Approach. Berlin:Springer, 2009. [7] [7] Wang S G, Wang C Y, Yu Y P. On the existence of complementary-place supervisors that enforce the liveness in S3PR. In:Proceedings of the 2010 International Conference on Mechatronics and Automation. Xi'an, China:IEEE, 2010. 1624-1628 [8] [8] Wang S G, Wang C Y, Zhou M C. Controllability conditions of resultant siphons in a class of petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2012, 42(5):1206-1215 [9] [9] Wang S G, Wang C Y, Zhou M C, Li Z W. A method to compute strict minimal siphons in S3PR based on loop resource subsets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2012, 42(1):226-237 [10] Wang Y H, Jiang B, Jiao L. Property checking for 1-place-unbounded petri nets. In:Proceedings of the 2010 IEEE International Symposium on Theoretical Aspects of Software Engineering(TASE). Taipei, China:IEEE, 2010. 117-125 [11] Yuan Chong-Yi. The Principle and Application of Petri Nets. Beijing:Electronic Industry Press, 2005.(袁祟义. Petri 网原理与应用. 北京:电子工业出版社, 2005.) [12] Bellettini C, Carlo L, Capra L. Reachability analysis of time basic Petri nets:a time coverage approach. In:Proceedings of the 2011 International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. Timisoara, Romania:IEEE, 2011. 110-117 [13] Ferrarini L. On the reachability and reversibility problems in a class of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(10):1474-1482 [14] Fanti M P, Zhou M C. Deadlock control methods in automated manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2004, 34(1):5-22 [15] Jeng M D, Peng M Y. On the liveness problem of 1-place-unbounded Petri nets. In:Proceedings of the 1997 International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation. Orlando, FL:IEEE, 1997. 3221-3226 [16] Jeng M D, Peng M Y. Augmented reachability trees for 1-place-unbounded generalized Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 1999, 29(2):173-183 [17] Jones N D, Landweber L H, Edmund L Y. Complexity of some problems in Petri nets. Theoretical Computer Science, 1977, 4(3):277-299 [18] Mayr E W. An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 1984, 13(3):441-460 [19] Murata T. Petri nets:properties, analysis and applications. Proceedings of the IEEE, 1989, 77(4):541-580 [20] Ru Y, Hadjicostis C N. Reachability analysis for a class of Petri nets. In:Proceedings of the 48th IEEE Conference on Decision and Control. Shanghai, China:IEEE, 2009. 1261-1266 [21] Wang J, Deng Y, Xu G. Reachability analysis of real-time systems using time Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2000, 30(5):725-736 [22] Wu N Q. Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 1999, 29(2):192-204 [23] Wu N Q, Bai L, Chu C. Modeling and conflict detection of crude oil operations for refinery process based on controlled colored timed Petri net. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2007, 37(4):461-472 [24] Wu Zhe-Hui, Jiang Chang-Jun. Conversion algorithm of bounded Petri nets. Journal of Software, 1992, 3(1):23-29(吴哲辉, 蒋昌俊. 有界 Petri 网的可达图到网图的转换算法. 软件学报, 1992, 3(1):23-29) [25] Bourdeaud'huy T, Hanafi S, Yim P. Mathematical programming approach to the Petri nets reachability problem. European Journal of Operational Research, 2007, 177(1):176-197 [26] Jiang Chang-Jun, Wu Zhe-Hui. Labeled reachability tree of Petri nets. Journal of Software, 1993, 4(6):22-28(蒋昌俊, 吴哲辉. Petri 网的标注可达树. 软件学报, 1993, 4(6):22-28) [27] Karp R M, Miller R E. Parallel program schemata. Journal of Computer and System Sciences, 1969, 3(2):147-195 [28] Li J Q, Fan Y S, Zhou M C. Performance modeling and analysis of workflow. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2004, 34(2):229-242 [29] Kultz R M, Knzle L A, Silva F. Applying Hm Heuristics in Petri Nets Reachability Problem. Berlin:Springer, 2010. 163-173 [30] Taoka S, Watanabe T. Heuristic algorithms for the marking construction problem of Petri nets. In:Proceedings of the 2010 International Symposium on Circuits and Systems(ISCAS). Paris, France:IEEE, 2010. 1344-1347 [31] Takahashi K, Ono I, Satoh H, Kobayashi S. An efficient genetic algorithm for reachability problems. In:Proceedings of the 30th International Conference on System Sciences. Wailea, HI, USA:IEEE, 1997. 89-98 [32] Yeh W J, Young M. Compositional reachability analysis using process algebra. In:Proceedings of the 1991 ACM Transactions on the Symposium on Testing, Analysis, and Verification. New York, USA:IEEE, 1991. 49-59 [33] Notomi M, Murata T. Hierarchical reachability graph of bounded Petri nets for concurrent-software analysis. IEEE Transactions on Software Engineering, 1994, 20(5):325-336 [34] Ahmad F, Huang H J, Wang X L, Anwer W. A technique for generating the reduced reachability graph of Petri net models. In:Proceedings of the 2008 IEEE International Conference on Systems, Man, and Cybernetics. Singapore:IEEE, 2008. 3636-3641 [35] Schmidt K. Parameterized reachability trees for algebraic Petri nets. Application and Theory of Petri Nets. Berlin:Springer, 1995. 392-411 [36] Peterson J L. Petri Net Theory and the Modeling of Systems. NJ:Prentice-Hall, 1981. [37] Wang F Y. A modified reachability tree for Petri nets. In:Proceedings of the 1991 International Conference on Systems, Man, and Cybernetics. Charlottesville, VA:IEEE, 1991. 329-334 [38] Wang F Y, Gao Y Q, Zhou M C. A modified reachability tree approach to analysis of unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2004, 34(1):303-308 [39] Wang S G, Zhou M C, Li Z W, Wang C Y. A new modified reachability tree approach and its applications to unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2013, 43(4):932-940 [40] Zhou M C. Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems:a Petri net approach. IEEE Transactions on Semiconductor Manufacturing, 1998, 11(3):333-357 [41] Wong H M, Zhou M C. Automated generation of modified reachability trees for Petri nets. In:Proceedings of the 1992 Regional Control Conference. Brooklyn, NY, 1992. 119-121 [42] Ru Y, Wu W, Hadjicostis C N. Comments on a modified reachability tree approach to analysis of unbounded petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2006, 36(5):1210-1210 [43] Ding Z J, Jiang C J, Zhou M C. Deadlock checking for one-place unbounded Petri nets based on modified reachability trees. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2008, 38(3):881-883 [44] Wang S G, Gan M D, Zhou M C. Macro liveness graph and liveness of -independent unbounded nets. Science China Information Sciences, 2015, 58(3):1-10 [45] Li Zhi-Wu, Wang An-Rong. A Petri net based deadlock pre-vention approach for exible manufacturing systems. Acta Automatica Sinica, 2003, 29(5):733-740(李志武, 王安荣. 基于Petri 网的柔性制造系统一种预防死锁方法. 自动化学报, 2003, 29(5):733-740) [46] Xing Ke-Yi, Tian Feng, Yang Xiao-Jun, Hu Bao-Sheng. Polynomial-complexity deadlock avoidance policies for automated manufacturing systems. Acta Automatica Sinica, 2007, 33(8):893-896(邢科义, 田锋, 杨小军, 胡保生. 具有多项式时间复杂性的避免制造系统死锁控制策略. 自动化学报, 2007, 33(8):893-896) [47] Fu Jian-Feng, Dong Li-Da, Xu Shan-Shan, Zhu Dan, Zhu Cheng-Cheng. An improved liveness condition for S4PR nets. Acta Automatica Sinica, 2013, 39(9):1439-1446(傅健丰, 董利达, 徐姗姗, 朱丹, 朱承丞. 一种改进型的S4PR 网活性条件. 自动化学报, 2013, 39(9):1439-1446) [48] Florin G, Natkin S. Generalization of queueing network product form solutions to stochastic Petri nets. IEEE Transactions on Software Engineering, 1991, 17(2):99-107 [49] Wang Y, Ding Z J. Analysis for one-place unbounded Petri nets based on modified reachability trees. In:Proceedings of the 2010 International Conference on Networking, Sensing and Control(ICNSC). Beijing, China:IEEE, 2012. 107-111 [50] Chen Y, Li Z, Zhou M C. Optimal supervisory control of flexible manufacturing systems by Petri nets:a set classification approach. IEEE Transactions on Automation Science and Engineering, 2014, 11(2):549-563 [51] Chen Y, Li Z, Zhou M C. Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, 2012, 42(3):615-629 [52] Ding Z H, Zhou M C, Wang S G. Ordinary differential equation based deadlock detection. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2014, 44(10):1435-1454 [53] Ding Z H, Zhou Y, Zhou M C. A polynomial algorithm to performance analysis of concurrent systems via Petri nets and ordinary differential equations. IEEE Transactions on Automation Science and Engineering, 2015, 12(1):295-308 [54] Huang Y S, Pan Y L, Zhou M C. Computationally improved optimal deadlock control policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, 2012, 42(2):404-415 [55] Li Z, Zhou M C, Jeng M D. A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE Transactions on Automation Science and Engineering, 2008, 5(1):182-188 [56] Uzam M, Zhou M C. An iterative synthesis approach to Petri netbased deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 2007, 37(3):362-371 [57] Uzam M, Zhou M C. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. International Journal of Production Research, 2006, 44(10):1987-2030 [58] Chen Y F, Li Z W, Khalgui M, Mosbahi O. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE Transactions on Automation Science and Engineering, 2011, 8(2):374-393 [59] Chen Y F, Li Z W. Design of a maximally permissive livenessenforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica, 2011, 47(5):1028-1034 [60] Chen Y F, Li Z W, Al-Ahmari A. Nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2013, 43(2):252-265 [61] Xing K, Han L, Zhou M C. Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE Transactions on Systems, Man, and Cybernetics:Part B, 2012, 42(3):603-615 [62] Xiong H H, Zhou M C. Scheduling of semiconductor test facility via Petri nets and hybrid heuristic search. IEEE Transactions on Semiconductor Manufacturing, 1998, 11(3):384-393 [63] Luo J C, Xing K Y, Zhou M C, Li X L, Wang X N. Deadlock-free scheduling of automated manufacturing systems via Petri nets and hybrid heuristic search. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2015, 45(3):530-541 [64] Huang B, Zhu H, Zhang G, Lu X. On further reduction of constraints in nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2015, 45(3):542-543
点击查看大图
计量
- 文章访问数: 2281
- HTML全文浏览量: 96
- PDF下载量: 1770
- 被引次数: 0