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

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

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

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.