Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net

Chen He-feng; Wu Nai-qi

doi:10.12052/gdutxb.190038

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net

更新时间：2026-05-27

- Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net
- Vol. 36, Issue 4, Pages: 1-9(2019)
- 作者机构：
  
  广东工业大学　机电工程学院,广东,广州,510006
- 作者简介：
- 基金信息：
- DOI：10.12052/gdutxb.190038
  CLC： TP301
- Online First：18 June 2019，
  
  Published：2019
- 稿件说明：
移动端阅览
陈鹤峰, 伍乃骐. 基于Petri网可达性和结构的最大许可控制器设计[J]. 广东工业大学学报, 2019, 36(4): 1-9.

Chen He-feng, Wu Nai-qi. Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net[J]. 2019, 36(4): 1-9.
陈鹤峰, 伍乃骐. 基于Petri网可达性和结构的最大许可控制器设计[J]. 广东工业大学学报, 2019, 36(4): 1-9. DOI： 10.12052/gdutxb.190038.

Chen He-feng, Wu Nai-qi. Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net[J]. 2019, 36(4): 1-9. DOI： 10.12052/gdutxb.190038.

摘要

自动化制造系统属于资源分配系统，在运行过程中容易陷入死锁状态. 为自动化制造系统设计控制器

达到避免死锁之目的. 另外

良好的受控系统应具有最大许可行为. 为了便于实现

控制器通常由线性约束综合表达. 在现有的工作中

基于可达性分析

将处理对象缩减为一个小集合

仅包含少数可达非法标识. 然后

对每标识构造一个混合整数线性规划问题并求解. 由于求解整数规划固有NP-hard特征

该策略计算开销巨大. 本文研究死锁的预防控制器设计. 在可达图分析的基础上

结合标识的结构特点

对非法标记识别分类

建立代数条件

构造线性约束

确保其行为最大许可性. 进而

设计多项式算法

使得计算复杂度显著降低. 对特定的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.

关键词

Keywords

references

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.

EVELIOTIS S A. Real-time management of resource allocation system: A disceret event systems appproach[M]. New York: Springer, 2006.

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.

WU N Q. System modeling and control with resource-oriented Petri nets[M]. CRC Press, Taylor Francis Group, 2009.

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.

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.

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.

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.

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.

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.

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.

CHEN Y F, LI Z W, KHALIGUI M, et al . Design of a maximally pe rmissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems [J ] . Automatica, 2011, 47(5): 1028-1034.

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.

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.

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.

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.

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.

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.

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.

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.

MURATA T. Petri nets: Properties, analysis, and applications [J]. Proceedings of the IEEE, 1989, 77(4): 541-580.

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.

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 Transact ions on Systems Man and Cybernetics Systems, 2016, 46(10): 1456-1467.

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.

CHEN Y F, LI Z W. On structural minimality of optimal supervisors for flexible manufacturing systems [J]. Automatica, 2012, 48(10): 2647-2656.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Fault Predictability of Stochastic Discrete Event Systems Based on Probabilistic Labeled Petri Nets

Similarity Measure for String Sequences in Weighted Petri Net

Robust Design for Artificial Noise-assisted UAV Terahertz Secure Communication

Bimodal Iterative Cross-attention Fusion Ensemble Framework

SCA-YOLO: Real-time Target Detection Based on Deformable Convolution and Context-aware Attention

Related Author

Cheng Yan

Liu Fuchun

Hu Ying-cheng

Xing Ma-li

Wu Yuan-qing

Related Institution

School of Computer Science and Technology, Guangdong University of Technology

School of Automation, Guangdong University of Technology

AI问答

⁰