基于Petri网可达性和结构的最大许可控制器设计

doi:10.12052/gdutxb.190038

摘要/Abstract

摘要： 自动化制造系统属于资源分配系统，在运行过程中容易陷入死锁状态.为自动化制造系统设计控制器，达到避免死锁之目的.另外，良好的受控系统应具有最大许可行为.为了便于实现，控制器通常由线性约束综合表达.在现有的工作中，基于可达性分析，将处理对象缩减为一个小集合，仅包含少数可达非法标识.然后，对每标识构造一个混合整数线性规划问题并求解.由于求解整数规划固有NP-hard特征，该策略计算开销巨大.本文研究死锁的预防控制器设计.在可达图分析的基础上，结合标识的结构特点，对非法标记识别分类，建立代数条件，构造线性约束，确保其行为最大许可性.进而，设计多项式算法，使得计算复杂度显著降低.对特定的Petri网，采用结构分析，获得最大许可的受控系统.另外，对于那些结构分析中未能处理的标识，提出了线性规划解决方案.结果表明，对于所考虑的Petri网子类，避免了求解混合整数线性规划问题，本方案在计算复杂性方面具有明显的优势.最后通过两个实例验证了该方法的有效性.

关键词: 自动化制造系统, Petri网, 死锁预防, 最大许可

Abstract: Automated manufacturing systems belonging to resource allocation are prone to deadlock during operation. Controllers need to be designed for automated manufacturing systems to avoid deadlocks. Further, the controlled system should have the maximal permissive behavior. For ease of implementation, the controllers are typically expressed in a comprehensive manner by linear constraints. In the existing work, based on the reachability analysis, the markings to be forbidden are reduced to a small set, and only a few reachable illegal markings are included. Then, construct a mixed integer linear programming problem for each marking and solve it. This strategy is computationally expensive due to the inherent NP-hard feature of integer programming. This paper studies the design of the prevention controllers for deadlocks. On the basis of the reachable graph analysis, combined with the structural characteristics of the identified markings, the illegal marking recognition is classified, the algebraic condition is established, and the linear constraint is constructed to ensure the maximal permissiveness of the behavior. Furthermore, the polynomial algorithm is designed such that the computational complexity is significantly reduced. For some specific Petri net, structural analysis is used to obtain the maximally permissively controlled system. In addition, for those markings that could not be processed via the structural analysis, a linear programming solution was proposed. The results show that, for the Petri net subclass considered, the problem of solving mixed integer linear programming is avoided. This scheme has obvious advantages in sense of computational complexity. Finally, the effectiveness of the method is verified by two examples.

Key words: automated manufacturing system, Petri net, deadlock prevention, maximal permissiveness

中图分类号:

TP301

陈鹤峰, 伍乃骐. 基于Petri网可达性和结构的最大许可控制器设计[J]. 广东工业大学学报, 2019, 36(04): 1-9.

Chen He-feng, Wu Nai-qi. Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net[J]. Journal of Guangdong University of Technology, 2019, 36(04): 1-9.

参考文献

[1] LI Z W, WU N Q, ZHOU M C. Deadlock control of automated manufacturing systems based on Petri nets-A literature review[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2012, 42(4):437-462
[2] EVELIOTIS S A. Real-time management of resource allocation system:A disceret event systems appproach[M]. New York:Springer, 2006.
[3] WU N Q, ZHOU M C, LI Z W. Resource-oriented Petri net for deadlock avoidance in flexible assembly systems[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2008, 38(1):56-69
[4] WU N Q. System modeling and control with resource-oriented Petri nets[M]. CRC Press, Taylor & Francis Group, 2009.
[5] EZPELETA J, COLOM J M, MARTINEZ J. A Petri net based deadlock prevention policy for flexible manufacturing systems[J]. IEEE Transactions on Robotics and Automation, 1995, 11(2):173-184
[6] LI Z W, ZHOU M C. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 2004, 34(1):38-51
[7] CHEN H F, WW N Q, LI Z W, et al. On a maximally permissive deadlock prevention policy for automated manufacturing systems by using resource-oriented Petri nets[J]. ISA Transactions, in press, 2018
[8] CHEN H F, WU N Q, ZHOU M C. A novel method for deadlock prevention of AMS by using resource-oriented Petri nets[J]. Information Sciences, 2016, 363:178-189
[9] CHEN H F, WU N Q, LI Z W, et al. Liveness of disjunctive and strict single-type automated manufacturing system:An ROPN approach[J]. IEEE Access, 2019, 7:17760-17771
[10] NAZEEM A, REVELIOTIS S, WANG Y, et al. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory:the linear case[J]. IEEE Transactions on Automatic Control, 2011, 56(8):1818-1833
[11] REVELIOTIS S, NAZEEM, A. Deadlock avoidance policies for automated manufacturing systems using finite state automata. in Formal Methods in Manufacturing[M], CRC Press/Taylor & Francis, 2014.
[12] CHEN Y F, LI Z W, KHALIGUI M, et al. Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems[J]. Automatica, 2011, 47(5):1028-1034
[13] CHEN H F, WU N Q, ZHOU M C. Resource-oriented Petri net-based approach to deadlock prevention of AMSs[C]//In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, HongKong:IEEE, 2015.
[14] LAWLEY M, REVELIOTIS S. Deadlock avoidance for sequential resource allocation systems:Hard and easy cases[J]. International Journal of Flexible Manufacturing Systems, 2001, 13(4):385-404
[15] BARKAOUI K, ABDALLAH I B. A deadlock prevention method for a class of FMS[J]. IEEE International Conference on Systems, Man and Cybernetics, 1995, 5:4119-4124
[16] REVELIOTIS S, LAWLEY M, FERREIRA P. Structural control of large-scale flexibly automated manufacturing systems[M]//Cornelius T L. Computer-aided design, engineering and manufacturing. Boca Raton:CRC Press, 2000.
[17] NAZEEM A, REVELIOTIS S. Optimal linear separation of the safe and unsafe subspaces of sequential resource allocation systems as a set-covering problem:Algorithmic procedures and geometric insights[J]. Siam Journal on Control and Optimization, 2013, 51(2):1707-1726
[18] NAZEEM A, REVELIOTIS S. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory:The nonlinear case[J]. IEEE Transactions on Automatic Control, 2012, 57(7):1670-1684
[19] 石聪聪, 刘富春. 模糊离散事件系统基于模式的故障诊断[J]. 广东工业大学学报, 2019, 36(1):35-41 SHI C C, LIU F C. A pattern-based failure diagnosis of fuzzy discrete-event systems[J]. Journal of Guangdong University of Technology, 2019, 36(1):35-41
[20] 叶彬彬, 刘富春. 随机离散事件系统的故障预测[J]. 广东工业大学学报, 2018, 35(6):83-89 YE B B, LIU F C. Failure predictability of stochastic discrete event systems[J]. Journal of Guangdong University of Technology, 2018, 35(6):83-89
[21] MURATA T. Petri nets:Properties, analysis, and applications[J]. Proceedings of the IEEE, 1989, 77(4):541-580
[22] WU N Q, ZHOU M C. Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(2):446-454
[23] BAI L P, WU N Q, LI Z W, et al. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology[J]. IEEE Transactions on Systems Man and Cybernetics Systems, 2016, 46(10):1456-1467
[24] UZAM M. An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions[J]. International Journal of Advanced Manufacturing Technology, 2002, 19(3):192-208
[25] CHEN Y F, LI Z W. On structural minimality of optimal supervisors for flexible manufacturing systems[J]. Automatica, 2012, 48(10):2647-2656

相关文章 15

[1]	张锐, 吕俊. 基于分离结果信噪比估计与自适应调频网络的单通道语音分离技术[J]. 广东工业大学学报, 2023, 40(02): 45-54.
[2]	刘冬宁, 王子奇, 曾艳姣, 文福燕, 王洋. 基于复合编码特征LSTM的基因甲基化位点预测方法[J]. 广东工业大学学报, 2023, 40(01): 1-9.
[3]	徐伟锋, 蔡述庭, 熊晓明. 基于深度特征的单目视觉惯导里程计[J]. 广东工业大学学报, 2023, 40(01): 56-60,76.
[4]	刘冬宁, 郑楚楚. 冷却时间约束多对多任务分配及其优化[J]. 广东工业大学学报, 2021, 38(05): 10-15.
[5]	张巍, 仝茹, 吴诗珏, 王子奇, 滕少华. 基于KD45闭包的群组角色指派研究[J]. 广东工业大学学报, 2021, 38(04): 26-34.
[6]	吕舒园, 刘富春, 赵锐, 邓秀勤, 崔洪刚. 分布式离散事件系统的模式故障预测研究[J]. 广东工业大学学报, 2021, 38(01): 54-63.
[7]	郝志峰, 黎伊婷, 蔡瑞初, 曾艳, 乔杰. 基于因果模型的社交网络用户购物行为研究[J]. 广东工业大学学报, 2020, 37(03): 1-8.
[8]	洪英汉, 郝志峰, 麦桂珍, 陈平华. 基于低阶条件独立测试的因果网络结构学习方法[J]. 广东工业大学学报, 2019, 36(05): 14-19.
[9]	雷瑞生, 凌永权. 基于改进的多时间尺度特征排列熵的心率变异性分析研究[J]. 广东工业大学学报, 2019, 36(03): 32-38.
[10]	石聪聪, 刘富春. 模糊离散事件系统基于模式的故障诊断[J]. 广东工业大学学报, 2019, 36(01): 35-41.
[11]	黄田安, 程良伦, 黄思猛. 制造物联网生产过程工序流波动分析方法研究[J]. 广东工业大学学报, 2019, 36(01): 57-62.
[12]	刘冬宁, 刘统武, 宋静静, 侯艳. 面向基站代维人员分工协作优化的多重指派研究[J]. 广东工业大学学报, 2018, 35(06): 69-76.
[13]	叶彬彬, 刘富春. 随机离散事件系统的故障预测[J]. 广东工业大学学报, 2018, 35(06): 83-89.
[14]	郑三强, 韩晓卓. 多因素制约下的SIR传染病模型的元胞自动机仿真模拟研究[J]. 广东工业大学学报, 2018, 35(05): 51-59.
[15]	周怡璐, 王振友, 李叶紫, 李锋. MOEA/D聚合函数的二次泛化及其优化性能分析[J]. 广东工业大学学报, 2018, 35(04): 37-44.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed