Extended Elementary Siphons and Their Application to Liveness‐Enforcement of Generalized Petri Nets

As a significant structural object, siphons are extensively employed to implement a large number of deadlock prevention and liveness‐enforcing methods for flexible manufacturing systems modeled by Petri nets. By linear combinations, a set of elementary siphons is chosen from all strict minimal ones to be controlled and thus the structural complexity of a supervisor is greatly reduced. The concept of elementary siphons is originally proposed for ordinary Petri nets. When applied to generalized Petri nets, their selection and controllability require an additional study. In this work, the concept of augmented siphons is proposed to extend the application of the elementary ones to a class of generalized Petri nets, GLS³PR. Based on graph theory, a siphon extraction algorithm is developed to obtain all strict minimal siphons, from which augmented elementary ones are computed. In addition, the controllability conditions of dependent siphons are developed. Through fully investigating the net structure, especially weight information, the set of augmented elementary siphons is more compact and well suits for generalized Petri net models under consideration. Some examples are used to illustrate the proposed method.     

基于Petri网的柔性制造系统一种预防死锁方法

基于Petri网的结构特性分析,研究了FMS(柔性制造系统)一种预防死锁方法.提出了 Petri网的一种特殊拓扑结构--基本信标的概念.在Petri网中基本信标的集合是SMS(严格极 小信标)集合的一个真子集.尤其在大型Petri网系统中,基本信标的集合比SMS的集合要小得 多.对于Petri网的一个子类S3PR,只对每一个基本信标添加一个库所使其不被清空,就可实现 预防死锁,也就是说无须控制S3PR的所有SMS而达到无信标被清空的目的.此外,对于S3PR, 还提出了一种求取SMS和基本信标的方法.相对于现在普遍采用的控制所有SMS来预防死锁 的策略,其具三方面优势.1)只需控制少量的SMS即所谓的基本信标.相应地,添加少量的控制 库所和连接弧,就可得到无死锁或活的Petri网.2)不需要先行计算出极小信标的集合.3)明显 地,这种方法更适合大型Petri网系统.我们通过穿插在文中的一个例子来说明这些方法.     

柔性制造系统非阻塞监督控制器优化设计

针对一类含有并发执行装配过程的柔性制造系统G-systems,提出一种新的死锁预防策略保证该系统的非阻塞性,即在控制下,受控系统从任意可达状态都可以到达理想状态.首先对Petri网模型中基本信标实施控制,保证了基本信标的最大可控,然后通过线性规划算法求取所有从属信标满足可控性的条件,即获得基本信标的控制深度变量.与现有方法相比,该策略优点在于只需加入少量的控制库所,就可避免不必要的迭代过程;其次是提出控制器输出弧位置优化策略,得到了结构更为简单、许可行为更多的非阻塞Petri网控制器.     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

基于信标的柔性制造系统的优化死锁预防策略

针对柔性制造系统（FMS）中的死锁问题,根据矩阵理论给出了Petri网中基本信标的概念,进而提出一种基于基本信标和混合整数规划法（MIP）的死锁预防策略．该策略将最优基本信标作为控制对象,以混合整数规划法给出的系统无死锁条件为目标函数．不考虑从属信标受控条件便可在多项式时间内使系统受控．该控制策略的显著特点是以较低的计算复杂度实现整个系统受控,并使需要添加的控制库所和连接弧大大减少．控制实例证明了其有效性．     

基于Petri网的无死锁控制器设计

对柔性制造系统提出了一种新的死锁预防控制算法。运用区域理论对Petri网模型设计一个控制器,对控制器中所有严格极小信标求取控制库所与资源库所的代数式,保证了所有的严格极小信标受控。与现有方法相比,该策略不必考虑控制器结构,只需根据这些代数式分布控制器中的资源,就可以得到相应无死锁监督控制器。     

An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming

This paper presents a novel and computational deadlock prevention policy for a class of generalized Petri nets, namely G-systems, which allows multiple resource acquisitions and flexible routings with machining, assembly and disassembly operations. In this research, a mixed integer programming (MIP)-based deadlock detection technique is used to find an insufficiently marked minimal siphon from a maximal deadly marked siphon for generalized Petri nets. In addition, two-stage control method is employed for deadlock prevention in Petri net model. Such proposed method is an iterative approach consisting of two stages. The first one is called siphons control, which adds a control place to the original net for each insufficiently marked minimal siphon. The objective is to prevent minimal siphons from being insufficiently marked. The second one, called control-induced siphons control, is to add a control place to the augmented net with its output arcs connecting to source transitions, which assures that there is no new insufficiently marked siphon generated due to the addition of the monitors. Compared with the existing approaches, the proposed deadlock prevention policy can usually lead to a non-blocking supervisor with more permissive behavior and high computational efficiency for a sizeable plant model due to avoiding complete siphon enumeration. Finally, a practical flexible manufacturing system (FMS) example is utilized to illustrate the proposed method.     

On Siphon Computation for Deadlock Control in a Class of Petri Nets

As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.     

基于混合整数规划的非阻塞监督控制器设计

提出一种新的死锁控制策略, 保证含有并发执行装配过程的一类柔性制造系统(Flexible manufacturing system, FMS) G-system的非阻塞性, 即在控制下, 受控系统从任意可达状态都可到达理想状态. 首先对Petri网模型运用混合整数规划算法求取一个最大的死信标, 然后从最大的死信标中求取一个需要受控的极小信标, 并对其添加控制库所, 从而保证所有信标的最大可控. 和现有方法相比, 该策略避免了求取所有的信标, 且添加较少的控制库所即可获得结构简单、许可行为趋于最优的控制器.     

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming

This article develops a deadlock prevention policy for a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems. The analysis of such a system leads us to characterise the deadlock situations in terms of the insufficiently marked siphons in its generalised Petri-net model. The proposed policy is carried out in an iterative way. At each step a minimal siphon is derived from a maximal deadly marked siphon that is found by solving a mixed integer programming (MIP) problem. An algorithm is formalised that can efficiently compute such a minimal siphon from a maximal one. A monitor is added for a derived minimal siphon such that it is max-controlled if it is elementary with respect to the siphons that have been derived. The liveness of the controlled system is decided by the fact that no siphon can be derived due to the MIP solution. After a liveness-enforcing net supervisor computed without complete siphon enumeration, the output-arcs of the additional monitors are rearranged such that the monitors act while restricting the system less. Examples are presented to demonstrate the proposed method.     

Control of Elementary and Dependent Siphons in Petri Nets and Their Application

The importance of siphons is well recognized in the analysis and control of deadlocks in a Petri net. To minimize the number of siphons that have to be explicitly controlled, siphons in a net are divided in a net into elementary and dependent ones. The concepts of token-rich, token-poor, and equivalent siphons are newly presented. More general conditions under which a dependent siphon can be always marked are established. The existence of dependent siphons in a Petri net is investigated. An algorithm is developed to find the set of elementary siphons in a net system for deadlock control purposes. The application of the proposed elementary siphon concept to the existing deadlock control policies is discussed. A few different-sized manufacturing examples are used to demonstrate the advantages of elementary siphon-based policies. The significant value of the proposed theory via a particular deadlock control policy is shown. Finally, some interesting and open problems are discussed.     

Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems

A variety of important Petri net-based methods to prevent deadlocks arising in flexible manufacturing systems (FMS) are to add some control places and related arcs to strict minimal siphons (SMS) such that no siphon can be emptied. Since the number of minimal siphons grows in general exponentially with respect to a Petri net size, their disadvantages lie in that they often add too many additional places to the net, thereby making the resulting net model much more complex than the original one. This paper explores ways to minimize the new additions of places while achieving the same control purpose. It proposes for the first time the concept of elementary siphons that are a special class of siphons. The set of elementary siphons in a Petri net is generally a proper subset of the set of all SMS. Its smaller cardinality becomes evident in large Petri net models. This paper proves that by adding a control place for each elementary siphon to make sure that it is marked, deadlock can be successfully prevented. Compared with the existing methods, the new method requires a much smaller number of control places and, therefore, is suitable for large-scale Petri nets. An FMS example is used to illustrate the proposed concepts and policy, and show the significant advantage over the previous methods.     

Controllability of control and mixture weakly dependent siphons in S3PR

Deadlocks in a flexible manufacturing system modelled by Petri nets arise from insufficiently marked siphons. Monitors are added to control these siphons to avoid deadlocks rendering the system too complicated since the total number of monitors grows exponentially. Li and Zhou propose to add monitors only to elementary siphons while controlling the other (strongly or weakly) dependent siphons by adjusting control depth variables. To avoid generating new siphons, the control arcs are ended at source transitions of process nets. This disturbs the original model more and hence loses more live states. Negative terms in the controllability make the control policy for weakly dependent siphons rather conservative. We studied earlier on the controllability of strongly dependent siphons and proposed to add monitors in the order of basic, compound, control, partial mixture and full mixture (strongly dependent) siphons to reduce the number of mixed integer programming iterations and redundant monitors. This article further investigates the controllability of siphons derived from weakly 2-compound siphons. We discover that the controllability for weakly and strongly compound siphons is similar. It no longer holds for control and mixture siphons. Some control and mixture siphons, derived from strongly 2-compound siphons are not redundant – no longer so for those derived from weakly 2-compound siphons; that is all control and mixture siphons are redundant. They do not need to be the conservative one as proposed by Li and Zhou. Thus, we can adopt the maximally permissive control policy even though new siphons are generated.     

应用必需信标的Petri网死锁预防策略

本文提出了表征一个Petri网子类,即S4R网(system of sequential systems with shared resources)中死锁问题的必需信标的概念和一种将混合整数规划算法与必需信标控制相结合的死锁预防策略.在该策略的迭代过程中,混合整数规划算法发现被控的Petri网中是否存在最大的死标识信标,若存在,则通过库所分类和迭代式的信标提取,得到必需信标,添加相应的控制库所,满足必需信标的最大可控性,从而实现被控的Petri网活性的目的.理论分析和算例验证表明了该策略的正确性和有效性.     

基于变迁覆盖的制造系统死锁控制策略

基于系统Petri网模型,研究柔性制造系统的死锁控制问题.论文利用变迁覆盖为系统设计活性控制器.变迁覆盖是由一组极大完备资源变迁回路组成的集合,其变迁集覆盖了Petri网中所有极大完备资源变迁回路的变迁集.验证变迁覆盖的有效性,然后仅对有效变迁覆盖中的极大完备资源变迁回路添加控制位置,就得到系统的活性受控Petri网.这种受控Petri网包含的控制位置个数少,从而结构相对简单.最后通过一个例子说明了所提出的死锁控制策略的构成与特点.     

基于混合整数规划的一般Petri网死锁检测方法

信标的受控性是检测柔性制造系统(flexible manufacturing system,FMS)Petri网模型是否存在死锁的关键因素.对于普通Petri网,在任何可达标识下所有信标不被清空是检测网系统非死锁的充分条件.然而,该条件对于建模能力更强的一般Petri网并不适用,max可控性条件由此产生.研究证明,该条件对于一般Petri网的死锁检测过于严格了.虽然其后有很多研究者通过改进max可控性条件以求给出条件更宽松的一般Petri网非死锁的充分条件,但大部分的研究成果都仅仅局限于一种顺序资源共享分配系统Petri网模型S4PR(systems of sequential systems with shared resources)网.因此,本文在max可控性条件的基础上提出了新的名为max#可控的信标可控性条件,并在此条件的基础上实现了基于混合整数规划(mixed integer programming,MIP)的死锁检测方法.与现有研究成果相比,max#可控性条件更宽松,可适用于更多类型的一般网,为解决大规模柔性制造系统中死锁监督控制器的结构复杂性问题提供了有力的理论支撑.     

Extension of the lower bound of monitor solutions of maximally permissive supervisors to non-α net systems

Traditional region-based liveness-enforcing supervisors focus on (1) maximal permissiveness of not losing legal states, (2) structural simplicity of minimal number of monitors, and (3) fast computation. Lately, a number of similar approaches can achieve minimal configuration using efficient linear programming. However, it is unclear as to the relationship between the minimal configuration and the net structure. It is important to explore the structures involved for the fewest monitors required. Once the lower bound is achieved, further iteration to merge (or reduce the number of) monitors is not necessary. The minimal strongly connected resource subnet (i.e., all places are resources) that contains the set of resource places in a basic siphon is an elementary circuit. Earlier, we showed that the number of monitors required for liveness-enforcing and maximal permissiveness equals that of basic siphons for a subclass of Petri nets modelling manufacturing, called α systems. This paper extends this to systems more powerful than the α one so that the number of monitors in a minimal configuration remains to be lower bounded by that of basic siphons. This paper develops the theory behind and shows examples.     

On systematic methods to remove redundant monitors from liveness-enforcing net supervisors

Petri nets based deadlock prevention for flexible manufacturing systems has received much attention over the past decade, primarily due to the seminal work of Ezpeleta et al. in 1995. A Petri net based deadlock prevention mechanism is usually implemented by adding monitors or control places to a plant Petri net model such that liveness can be enforced. The significance of this methodology lies in that both a plant model and its supervisor are in a same formalism-Petri nets. Due to the inherent complexity of Petri nets, in theory, the number of additional monitors that have to been added to achieve liveness-enforcement purpose for an uncontrolled plant model is exponential with respect to the size of the model. This paper first proposes a systematic method to minimize the number of additional monitors in a liveness-enforcing Petri net supervisor such that the resultant net system has the same permissive behavior while liveness can still be preserved. Furthermore, for the liveness-enforcing Petri net supervisors of flexible manufacturing systems, which have some particular property, an algorithm is developed such that more permissive liveness-enforcing Petri net supervisors can be obtained after liveness-restrictive monitor removal. Compared with the existing techniques of eliminating redundant monitors in the literature, the complete state enumeration of a supervisor is avoided, which implies the high computational efficiency of the methods in this paper. Flexible manufacturing examples are used to demonstrate the proposed approaches.     

Structure of weakly 2-dependent siphons

Deadlocks arising from insufficiently marked siphons in flexible manufacturing systems can be controlled by adding monitors to each siphon – too many for large systems. Li and Zhou add monitors to elementary siphons only while controlling the rest of (called dependent) siphons by adjusting control depth variables of elementary siphons. Only a linear number of monitors are required. The control of weakly dependent siphons (WDSs) is rather conservative since only positive terms were considered. The structure for strongly dependent siphons (SDSs) has been studied earlier. Based on this structure, the optimal sequence of adding monitors has been discovered earlier. Better controllability has been discovered to achieve faster and more permissive control. The results have been extended earlier to S³PGR² (systems of simple sequential processes with general resource requirements). This paper explores the structures for WDSs, which, as found in this paper, involve elementary resource circuits interconnecting at more than (for SDSs, exactly) one resource place. This saves the time to compute compound siphons, their complementary sets and T-characteristic vectors. Also it allows us (1) to improve the controllability of WDSs and control siphons and (2) to avoid the time to find independent vectors for elementary siphons. We propose a sufficient and necessary test for adjusting control depth variables in S³PR (systems of simple sequential processes with resources) to avoid the sufficient-only time-consuming linear integer programming test (LIP) (Nondeterministic Polynomial (NP) time complete problem) required previously for some cases.     

Design of liveness-enforcing supervisors with simpler structures for deadlock-free operations in flexible manufacturing systems using necessary siphons

Siphons can be used to characterize deadlock states and solve deadlock problems in Petri nets that model flexible manufacturing systems. This paper presents an iterative siphon-based control (ISC) deadlock prevention policy for Petri nets via the combination of mixed integer programming (MIP) and the concept of necessary siphons (NSs). At each iteration in this ISC policy, a maximal deadly marked siphon that is closely related to deadlocks in a Petri net can be conveniently found by an MIP-based deadlock detection method. Then the places in it are classified and an NS is derived from the classified places. For each NS found, depending on its complementary set, the proposed policy adds a proper control place (CP) to make it marked (max-controlled). Moreover, during the ISC procedure, a test for redundant NSs is carried out under a certain condition in order to avoid the addition of the corresponding CPs. The siphon control process proceeds iteratively until the controlled system is live. Compared with the existing approaches, the proposed policy usually leads to a structurally simple liveness-enforcing supervisor by adding as few CPs as possible and achieves better control results. Some examples are introduced to illustrate the proposed approach.