Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilities the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reach their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For an general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.     

一类FMS的最佳活Petri网模型的综合

利用Petri网为一类柔性制造系统建模,并讨论避免系统死锁问题.通过Petri网模 型的结构分析,证明了系统产生死锁的一个充分必要条件.给出了避免死锁的最佳控制器,它 可以通过给系统的Petri网模型增加一些新的位置与相应的弧来实现.从而导出了这类制造 系统的最佳活Petri网模型.     

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.     

具有多项式时间复杂性的避免制造系统死锁控制策略

基于系统 Petri 网模型, 研究自动制造系统的避免死锁问题. 对不含中心资源的制造系统, 证明了它只包含安全和死锁两类可达状态. 通过一步向前看的方法, 给出了系统多项式时间复杂性的最佳避免死锁策略. 对一般系统定义了一种辅助 Petri 网. 利用辅助网的最佳避免死锁策略, 提出了综合一般制造系统多项式复杂性的避免死锁策略的方法.     

离散制造装配系统的活性控制

首次研究离散制造装配系统的活性控制问题.建立了系统的工件加工过程Petri网 模型.通过对系统Petri网模型的结构分析,提出了导致系统死锁的两类元素结构及活性特 征.对一类离散制造装配系统提出了避免死锁的Petri网控制器,这类控制器容易实现,对系 统的限制小,而且使得受控系统仍具Petri网模型.对一般离散制造装配系统提出了保证系统 活性的控制策略.     

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

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

离散制造装配系统的活性控制1)

首次研究离散制造装配系统的活性控制问题.建立了系统的工件加工过程Petri网模型.通过对系统Petri网模型的结构分析,提出了导致系统死锁的两类元素结构及活性特征.对一类离散制造装配系统提出了避免死锁的Petri网控制器,这类控制器容易实现,对系统的限制小,而且使得受控系统仍具Petri网模型.对一般离散制造装配系统提出了保证系统活性的控制策略.     

A deadlock prevention approach for flexible manufacturing systems with uncontrollable transitions in their Petri net models

Deadlocks are a highly undesired situation in a fully automated flexible manufacturing system, whose occurrences are tied to the existence of shared resources that are competed by different production processes. In the last two decades, a fair amount of research has been done on deadlock analysis and control for flexible manufacturing systems, leading to a variety of strategies in the literature. Petri nets are a promising mathematical tool to handle deadlock problems in flexible manufacturing systems. However, most deadlock control policies based on a Petri net formalism assume that all the transitions in a plant model are controllable. However, uncontrollability of events are a natural feature in a real‐world production system. This paper proposes a deadlock prevention policy for a class of Petri nets by considering the existence of uncontrollable transitions. Deadlocks are prevented by adding monitors to a plant Petri net model, whose addition does not inhibit the firings of uncontrollable transitions. Linear programming techniques are employed to find transitions to which a monitor points in order that a more permissive liveness‐enforcing Petri net supervisor can be found. A number of manufacturing examples are used to demonstrate the proposed methods. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems

Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.      

部分可控Petri网分布式死锁监控器设计

研究了部分可控Petri网柔性制造系统中的死锁避免的问题。为了保证死锁避免和资源最大允许利用,提出了基于分支定界法的Petri网死锁监控器的优化设计方法,采用多个子控制节点对全局状态建立分布式监控器,通过行为可行和分布可行对分布式监控器下合法状态空间进行检测,对最大行为可行子集建立线性规划模型求解最大分布可行合法状态集,得到分布式监控器下的最大合法状态子空间。最后,建立了柔性制造系统的部分可控Petri网模型,针对系统的死锁避免等多个行为特性要求,分别设计了集中式监控器和分布式监控器,分布式监控器能有效地避免死锁。     

Design of Optimal Petri Net Supervisors for Flexible Manufacturing Systems via Weighted Inhibitor Arcs

This paper develops an approach to the design of an optimal Petri net supervisor that enforces liveness to flexible manufacturing systems. The supervisor contains a set of observer places with weighted inhibitor arcs. An observer place with a weighted inhibitor arc is used to forbid a net from yielding an illegal marking by inhibiting the firing of a transition at a marking while ensuring that all legal markings are preserved. A marking reduction technique is presented to decrease the number of considered markings, which can dramatically lower the computational burden of the proposed approach. An integer linear program is presented to simplify the supervisory structure by minimizing the number of observer places. Finally, several examples are used to shed light on the proposed approach which can lead to an optimal supervisor for the net models that cannot be optimally controlled via pure Petri net supervisors.     

Maximally Permissive Petri Net Supervisors for Flexible Manufacturing Systems with Uncontrollable and Unobservable Transitions

This paper presents a deadlock prevention policy to obtain behaviorally optimal supervisors for flexible manufacturing systems with uncontrollable and unobservable transitions. The conditions of uncontrollability and unobservability of transitions are revealed in the sense of the implementation of a Petri net supervisor. Then, integer linear programming models are designed to obtain a Petri net supervisor such that all legal markings are reachable and the number of control places is reduced. We also show that a controllable transition can be unobservable and self‐loops can be used to disable the transition but do not observe its firing. Finally, examples are provided to illustrate the proposed approach.     

一种改进型的S4PR网活性条件

研究了顺序资源共享分配系统的建模模型S4PR (Systems of sequential systems with shared resources)网的活性问题. 已有的研究成果表明, 一个S4PR网在所有信标都满足max, max'或max"-controlled 时能保持活性, 但现有的活性条件对信标的限制严格且不适用于某些网系统, 本文提出了一类名为max*-controlled的改进型条件, 并证明了当一个S4PR网的所有信标都满足max*-controlled条件时, 网系统能保持活性. 与现有的其他条件相比, 新的活性条件更加宽松, 为设计更高允许度的死锁预防或者活性保持监控器提供了理论支撑.     

Fault-tolerant deadlock avoidance algorithm for assembly processes

Unreliable resources pose challenges in design of deadlock avoidance algorithms as resources failures have negative impacts on scheduled production activities and may bring the system to dead states or deadlocks. This paper focuses on the development of a suboptimal polynomial complexity deadlock avoidance algorithm that can operate in the presence of unreliable resources for assembly processes. We formulate a fault-tolerant deadlock avoidance controller synthesis problem for assembly processes based on controlled assembly Petri net (CAPN), a class of Petri nets (PNs) that can model such characteristics as multiple resources and subassembly parts requirement in assembly production processes. The proposed fault-tolerant deadlock avoidance algorithm consists of a nominal algorithm to avoid deadlocks for nominal system state and an exception handling algorithm to deal with resources failures. We analyze the fault-tolerant property of the nominal deadlock avoidance algorithm based on resource unavailability models. Resource unavailability is modeled as loss of tokens in nominal Petri Net models to model unavailability of resources in the course of time-consuming recovery procedures. We define three types of token loss to model 1) resource failures in a single operation, 2) resource failures in multiple operations of a production process and 3) resource failures in multiple operations of multiple production processes. For each type of token loss, we establish sufficient conditions that guarantee the liveness of a CAPN after some tokens are removed. An algorithm is proposed to conduct feasibility analysis by searching for recovery control sequences and to keep as many types of production processes as possible continue production so that the impacts on existing production activities can be reduced.     

Necessary and sufficient liveness condition of GS3PR Petri nets

Structural analysis is one of the most important and efficient methods to investigate the behaviour of Petri nets. Liveness is a significant behavioural property of Petri nets. Siphons, as structural objects of a Petri net, are closely related to its liveness. Many deadlock control policies for flexible manufacturing systems (FMS) modelled by Petri nets are implemented via siphon control. Most of the existing methods design liveness-enforcing supervisors by adding control places for siphons based on their controllability conditions. To compute a liveness-enforcing supervisor with as much as permissive behaviour, it is both theoretically and practically significant to find an exact controllability condition for siphons. However, the existing conditions, max, max′, and max″-controllability of siphons are all overly restrictive and generally sufficient only. This paper develops a new condition called max*-controllability of the siphons in generalised systems of simple sequential processes with resources (GS³PR), which are a net subclass that can model many real-world automated manufacturing systems. We show that a GS³PR is live if all its strict minimal siphons (SMS) are max*-controlled. Compared with the existing conditions, i.e., max-, max′-, and max″-controllability of siphons, max*-controllability of the SMS is not only sufficient but also necessary. An example is used to illustrate the proposed method.     

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     

NECESSARY AND SUFFICIENT CONDITIONS FOR DEADLOCKS IN FLEXIBLE MANUFACTURING SYSTEMS BASED ON A DIGRAPH MODEL

As typical discrete event systems, flexible manufacturing systems have been extensively studied in such aspects as modeling, control and performance analysis. One important topic in the study of such systems is the deadlock detection, prevention and avoidance. In the past decade, two major modeling formalisms, i.e., Petri nets and digraphs, have been adopted for developing deadlock control policies for flexible manufacturing systems. In this paper, the concepts of slack, knot, order and effective free space of circuits in the digraph are established and used to concisely and precisely quantify the sufficient conditions for a system state to be live. Necessary conditions for this liveness is quantified for a special class of system states ‐ called evaluation states. The significance of the result is that the conditions are true for avoiding both primary deadlocks and impending deadlocks that are arbitrary steps away from a primary one, whereas only second level deadlocks have been studied in the literature. Examples are provided to illustrate the method.     

Deadlock avoidance policy for Petri-net modeling of flexiblemanufacturing systems with shared resources

Multiple products through a flexible manufacturing system (FMS) with limited resources can lead to deadlock. In this paper, the authors study the problem of deadlock avoidance by using the Petri net (PN) model for FMSs and introducing the concept of deadlock structure. The necessary and sufficient conditions to prevent deadlock are characterized. The authors use a state feedback restriction policy which prevents some enabled transitions from firing for avoiding deadlock in the system. In particular, when the number of any key kind of resources is greater than one, this policy is minimally restrictive and allows the maximal use of resources in the system. The authors present the PN realization of these restriction policies when the closed-loop system can be modeled by a live PN. The restriction policies can be easily implemented. An example is provided for illustration     

Synthesis of liveness enforcing supervisor for automated manufacturing systems using insufficiently marked siphons

A liveness enforcing supervisor synthesis technique is presented for Petri net modeling automated manufacturing systems. The insufficiently marked siphons are deployed to characterize the deadlock situations in an incidence matrix based way, which makes possible the study of the modeled systems from both structural and algebraic perspectives. The approach generates at each step a generalized mutual exclusion constraint which contains only markings for which liveness can be enforced. To avoid the explicit enumeration of all the set of strict minimal siphons, a set of mathematical programming formulations are established to implement the derivation of insufficiently marked siphons from the PT-transformation of the plant system. Further, a generalized elementary siphon control approach is involved such that the final supervisor can be structurally simplified. Several examples are used to illustrate these results.     

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.