安全Petri网事件分离状态的BDD算法

doi:10.3969/j.issn.1001-2400.2010.01.021

J4 ›› 2010, Vol. 37 ›› Issue (1): 119-124+141.doi: 10.3969/j.issn.1001-2400.2010.01.021

安全Petri网事件分离状态的BDD算法

陈玉峰;李志武

(西安电子科技大学机电工程学院，陕西西安 710071)

收稿日期:2008-12-10 出版日期:2010-02-20 发布日期:2010-03-29
通讯作者: 陈玉峰
作者简介:陈玉峰(1983-)，男，西安电子科技大学博士研究生，E-mail: chyf01@163.com．
基金资助:
国家自然科学基金资助项目(60773001);教育部高等学校博士点基金资助项目(20070701013);国家高科技发展规划863计划资助项目(2008AA04Z109)

Computation of marking/transition separation instances for safe Petri nets using BDD

CHEN Yu-feng;LI Zhi-wu

(School of Mechano-electronic Engineering, Xidian Univ., Xi'an 710071， China)

Received:2008-12-10 Online:2010-02-20 Published:2010-03-29
Contact: CHEN Yu-feng

摘要/Abstract

摘要：

基于区域法可以获得最佳的活性控制器，但由于要计算网的可达状态集而导致状态爆炸问题．提出一种应用二值决策图(BDD)计算安全Petri网事件分离状态的算法．用布尔代数对Petri网的结构和行为进行描述，用BDD实现布尔代数运算． BDD共享的数据结构能以较小的空间表示较大可达集并能对其进行高效的运算，从而节省了存储空间，减少了运算时间．最后用著名的哲学家就餐问题的Petri网模型对该算法进行仿真．仿真结果说明，使用BDD计算复杂Petri网的合法状态集、危险节点、坏点和计算事件分离状态具有很高效率．

关键词: Petri网, 二值决策图, 事件分离状态

Abstract:

Based on the theory of regions, an optimal liveness-enforcing Petri net supervisory can be obtained. However, the set of reachable states is required, which usually leads to the state explosion problem. This paper presents a symbolic approach to the computation of marking/transition separation instances for safe Petri nets by using BDD (Binary Decision Diagrams). In this paper, the structure and behavior of a Petri net are symbolically modeled by using Boolean algebra. Boolean algebra operations are implemented by BDD which are capable of representing large sets of reachable states with small shared data structures and enable the efficient manipulation of those sets. Therefore, the cost of computation and memory usage can be efficiently reduced. Finally, using the model of the well-known dining philosophers problem, we verify the efficiency of calculating the set of legal states, dangerous states, bad states and the marking/transition separation instances through different-sized problems.

Key words: Petri nets, binary decision diagrams(BDD), marking/transition separation instances

陈玉峰;李志武. 安全Petri网事件分离状态的BDD算法[J]. J4, 2010, 37(1): 119-124+141.

CHEN Yu-feng;LI Zhi-wu. Computation of marking/transition separation instances for safe Petri nets using BDD[J]. J4, 2010, 37(1): 119-124+141.

参考文献

［1］Ezpeleta J, Colom J M, Martinez J. A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems［J］. IEEE Trans on Robotics and Automation, 1995, 11(2): 173-184.
［2］Li Zhiwu, Zhou Mengchu. Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems［J］. IEEE Trans on Systems, Man, and Cybernetics, Part A, 2004, 34(1): 38-51.
［3］Li Zhiwu, Zhou Mengchu. Clarifications on the Definitions of Elementary Siphons of Petri Nets［J］. IEEE Trans on Systems, Man, and Cybernetics, Part A, 2006, 36(6): 1227-1229.
［4］Li Zhiwu, Hu Hesuan, Wang Anrong. Design of Liveness-enforcing Supervisors for Flexible Manufacturing Systems Using Petri nets［J］. IEEE Trans on Systems, Man, and Cybernetics, Part C, 2007, 37(4): 517-526.
［5］Li Zhiwu, Zhou Mengchu. Two-stage Method for Synthesizing Liveness-enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets［J］. IEEE Trans on Industrial Informatics, 2006, 2(4): 313-325.
［6］闫明明, 李志武, 钟春富. S³PR网的一种死锁预防策略［J］. 西安电子科技大学学报, 2008, 35(2), 330-333.
Yan Mingming, Li Zhiwu, Zhong Chunfu. Deadlock Prevention Policy for a Class of Petri Nets S³PR［J］. Journal of Xidian University, 2008, 35(2): 330-333.
［7］Ghaffari A, Rezg N, Xie X L. Design of a Live and Maximally Permissive Petri Net Controller Using the Theory of Regions［J］. IEEE Trans on Robotics and Automation, 2003, 19(1): 137-142.
［8］Pastor E, Cortadella J, Roig O, et al. Petri Net Analysis Using Boolean Manipulation［C］//Lecture Notes in Computer Science: 815. London: Springer-Verlag, 1994: 416-435.
［9］Pastor E, Cortadella J. Symbolic Analysis of Bounded Petri Nets［J］. IEEE Trans on Computers, 2001, 50(5), 432-448.
［10］Miner A S, Ciardo G. Efficient Reachability Set Generation and Storage Using Decision Diagrams［C］//Lecture Notes in Computer Science: 1639. London: Springer-Verlag, 1999: 6-25.
［11］Andersen H R. An Introduction to Binary Decision Diagrams［R］. Denmark: Advanced Algorithms E97, Department of Information Technology, Technical University of Denmark, 1997.
［12］Brant R E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams［J］. ACM Computing Surveys, 1992, 24(3): 293-318.

[1]	王祺;陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2): 69-74.
[2]	马子玥;童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6): 68-73.
[3]	蒋忠远;张秀艳;马子玥. 智能电网中电能存储系统的容量优化[J]. J4, 2015, 42(6): 106-112.
[4]	张秀艳;钟春富;贾建援. S³PR网的可达标识集算法[J]. J4, 2015, 42(5): 105-109.
[5]	张丽;赵良煦;王寿光;汪成英. 针对α网的最优线性约束转换方法[J]. J4, 2015, 42(5): 183-187+212.
[6]	陈晓亮;蒋忠远;叶剑虹 . 工作流网的混或检测和预防策略 [J]. J4, 2015, 42(2): 77-83.
[7]	朱承丞;董利达. 一种多线程软件并发漏洞检测方法 [J]. J4, 2015, 42(2): 167-173+212.
[8]	尤丹;刘苗;吴文慧;王寿光. S³PR网的严格极小信标计算方法[J]. J4, 2014, 41(4): 193-197+204.
[9]	洪良. S³PR网可达标识数的一种有效估算方法[J]. J4, 2014, 41(3): 169-173.
[10]	李晔;王映辉;于振华. 信息物理融合系统的面向对象Petri网建模[J]. J4, 2014, 41(2): 165-171.
[11]	王祺;王安荣;蒲绪强. 制造系统Petri网特殊标识求解算法[J]. J4, 2013, 40(6): 85-91.
[12]	张曼;段振华. 工作流网合成规则及其在流程设计中的应用[J]. J4, 2012, 39(2): 200-206.
[13]	郭金维;李志武. 一种时延Petri网的死锁预防方法[J]. J4, 2009, 36(5): 902-908.
[14]	朱森;李志武. 双航母编队C³I系统Petri网建模与分析研究[J]. J4, 2009, 36(4): 661-668.
[15]	王安荣;李志武. 基本信标计算的一种快速算法[J]. J4, 2008, 35(4): 632-638.

安全Petri网事件分离状态的BDD算法

Computation of marking/transition separation instances for safe Petri nets using BDD

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10