Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems

In this paper, a deadlock prevention policy for flexible manufacturing systems (FMS) is proposed, which can obtain a maximally permissive liveness-enforcing Petri net supervisor while the number of control places is compressed. By using a vector covering approach, the sets of legal markings and first-met bad markings (FBM) are reduced to two small ones, i.e., the minimal covering set of legal markings and the minimal covered set of FBM. A maximally permissive control purpose can be achieved by designing control places such that all markings in the minimal covered set of FBM are forbidden and no marking in the minimal covering set of legal markings is forbidden. An integer linear programming problem is designed to minimize the number of control places under an assumption that a control place is associated with a P-semiflow. The resulting net has the minimal number of control places on the premise that the assumption holds, and possesses all permissive states of a plant. The only problem of the proposed method is its computational complexity that makes it inapplicable to large-scale Petri net models. An FMS example from the literature is presented to illustrate the proposed method.     

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.     

Universal petri net

A universal inhibitor Petri net executing an arbitrary given inhibitor Petri net is constructed. An inhibitor Petri net graph, its marking, and transition firing sequence are encoded as 10 scalar nonnegative integer variables and are represented by the corresponding places of the universal net. An algorithm using only these scalar variables and executing an arbitrary inhibitor net is developed based on the state equation and is encoded by the universal inhibitor Petri net. Subnets that implement arithmetic, comparison, and copy operations are employed.     

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     

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.     

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.     

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 resource-transition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching 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 a 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.     

On structural minimality of optimal supervisors for flexible manufacturing systems

This paper develops a place invariant based deadlock prevention method to obtain an optimal, i.e., maximally permissive, liveness-enforcing Petri net supervisor with a minimal supervisory structure that means the minimal number of control places. Maximal permissiveness can be achieved by designing place invariants that make all legal markings reachable while all first-met bad markings unreachable. An integer linear programming problem is formulated to compute all place invariants and its objective function minimizes the number of place invariants, aiming to yield a minimal supervisory structure. Importantly, we develop a technique to greatly improve the efficiency of the proposed method by reducing the number of constraints and variables in the integer linear programming problem under consideration. A number of examples from the literature are used to illustrate the proposed approaches.     

Design of liveness‐enforcing supervisors via transforming plant petri net models of FMS

This paper focuses on the deadlock prevention problems in a class of Petri nets, systems of simple sequential process with resources, S³PR for short. By structure analysis, we propose an approach that can transform a plant net model into a weighted S³PR (WS³PR) that is behaviorally equivalent to the plant model. The WS³PR is made to be live by properly reconfiguring its weight distribution such that its all strict minimal siphons are self‐max'‐controlled. The resulting WS³PR can serve as a liveness‐enforcing Petri net supervisor for the plant model after removing some idle and operation places. A live controlled system can be accordingly obtained by synchronizing a plant model and the places whose weights are regulated. This research shows that a small number of monitors is obtained, leading to more permissive behavior of the controlled system. Examples are used to demonstrate the proposed concepts and methods. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

标注Petri网中的最小初始标识估计

为获得制造系统初始化时的最小资源以实现最优资源分配,利用标注Petri网对系统进行建模,并研究标注Petri网的最小初始标识估计问题。给定一个标注Petri网,在不可观测变迁组成无环子网的情况下,基于动态规划提出一种新的最小初始标识估计算法。在观察到给定的标注序列后,放宽不可观测变迁发生个数的限制,并根据该算法构建节点的演化过程。当出现相同的发生数向量时,仅保留当前极小的初始标识估计,并通过节点的演化过程对极小初始标识估计的托肯总数进行对比。为验证算法的有效性,给出一个制造系统的标注Petri网模型实例,最终得到的最小初始标识为［1000］^T,且对应的变迁发生序列为t₁t₃t₄t₆,满足给定标注Petri网的结构要求。实验结果表明,与传统基于动态规划的算法相比,该算法获得的最小初始标识估计具有更小的托肯总数。     

Maximally permissive supervisor synthesis based on a new constraint transformation method

The method is proposed to design the maximally permissive and efficient supervisor for enforcing linear constraints, in which the weights of places are not negative, on ordinary Petri nets with uncontrollable transitions. First, the weakly admissible linear constraint is introduced. Second, a method is proposed to design the monitor place for enforcing a weakly admissible linear constraint on Petri nets. Third, a theorem proving that a linear constraint can be equivalently transformed at an uncontrollable transition into a disjunction of new constraints is proposed. Fourth, using this theorem, an algorithm is presented to equivalently transform a linear constraint, each place weight of which is not negative, into a disjunction of weakly admissible ones. Lastly, the supervisor, which consists of the plant net and a set of monitor places, is designed for the weakly admissible linear constraints calculated by the above algorithm.     

Suboptimal time management of discrete event systems with uncontrollable events modeled by Petri nets

Preventing systems from entering to forbidden states is a crucial issue in discrete event systems control. Adding supervisors to the system is a common method to avoid entering to forbidden states. In discrete event systems modeled by Petri net adding a supervisor could be done by means of control places. Since, the time is not considered in designing this supervisor, in presence of uncontrollable transitions adding control places can lead to increase the operation time of the system modeled by timed Petri net. Because, the firing of some transitions is prevented when it is not necessary. So, to design a more efficient controller, we will be required to use time information of the system component. Therefore, in this paper, a method for optimizing the time behavior of a supervised timed Petri net will be proposed. To obtain an efficient operation, some timed places as timer will be added to the net. The time of this timer places is calculated to permit firing of some controllable transitions in order to enter into some weakly forbidden states while entering to forbidden states is prevented. This concept leads to increase the speed of system as well as obtain an acceptable operation. This method can be applied for all systems modeled by Petri nets. The efficiency of proposed approach will be discussed and validated with a case study.     

Possibilistic Petri nets

This paper presents the possibilistic Petri net model which combines possibility logic with Petri nets with objects. The main feature of this model is to allow one to reason about the aspects of uncertainty and change in dynamic discrete event systems. The paper presents relevant concepts of Petri nets with objects and possibility logic and how imprecision and vagueness are introduced in the marking of a Petri net with objects. The marking of a net is imprecise, or in a more general way, fuzzy, in order to represent an ill-known knowledge about a system state. A new marking updating according to the fuzzy marking such defined is also discussed. An example of shop door monitoring is presented that illustrates our approach.     

Marking Optimization of Weighted Marked Graphs

Cyclic manufacturing systems can be modeled by marked graphs, which are an elementary class of Petri nets. To model systems with bulk services and arrivals and to reduce the size of the model, weighted marked graphs can be used. An important step when designing these systems is the definition of the number of manufacturing resources to be used in order to reach a given productivity. In terms of timed Petri nets, this is known as the marking optimization problem and consists of reaching a given average cycle time while minimizing a linear combination of markings. In this paper, a necessary and sufficient condition to obtain a feasible solution of the marking optimization problem of weighted marked graphs with deterministic times is established. A fast heuristic solution, based on an iterative process and using simulation, is given. An example and an application to manufacturing systems are presented.     

Synthesis of supervisors enforcing general linear constraints in Petri nets

Efficient techniques exist for the design of supervisors enforcing constraints consisting of linear marking inequalities. This note shows that without losing the benefits of the prior techniques, the class of constraints can be generalized to linear constraints containing marking terms, firing vector terms, and Parikh vector terms. We show that this extended class of constraints is more expressive. Furthermore, we show that the extended constraints can describe any supervisor consisting of control places arbitrarily connected to the transitions of a plant Petri net (PN). The supervisor design procedure we propose is as follows. For PNs without uncontrollable and unobservable transitions, a direct method for the design of a PN supervisor that is least restrictive is given. For PNs with uncontrollable and/or unobservable transitions, we reduce the problem to the design of supervisors enforcing linear marking inequalities.     

Structuring Acyclic Petri Nets for Reachability Analysis and Control

The incidence matrices—from places to transitions and vice versa—of an acyclic Petri net can obtain a block-triangular structure by reordering their rows and columns. This allows the efficient solution of some reachability problems for acyclic Petri nets. This result is further used in supervisory control of Petri nets; supervisors for Petri nets with uncontrollable transitions are constructed by extending the method of Yamalidou et al. (1996) to Petri nets where transitions can be executed simultaneously. A large class of Petri nets with uncontrollable transitions is given for which the maximally permissive supervisor can be realized by a Petri net. The original specification is algorithmically transformed—by using the results for acyclic Petri nets—into a new specification to take the presence of uncontrollable transitions into account. The supervisor is obtained by simple matrix multiplications and no linear integer programs need to be solved. Furthermore, a class of Petri nets is given for which the supervisor can be realized by extending the enabling rule with OR-logic.     

Determination of path identifiers for reliability analysis of a broadcasting network using Petri nets

A Petri net approach for determination of the sets of path identifiers for reliability analysis of a broadcasting network is presented. The firing concept of Petri nets is exploited to give a Petri net interpretation to certain properties of the network. The dynamic behaviour of the system under study is represented in the form of token movements within the model. The various entities of Petri nets are assigned an appropriate interpretation for studying the behaviour of the system at different levels. Corresponding to the source node and each of the terminal nodes, a vector, representing the state of the Petri net interpreted model, is defined by assuming a token initially at the source place and finally at one of the terminal places. The reachability and marking concepts are then used to determine all success states of the system. The developed algorithm has been coded into FORTRAN-77 and the complete package is available. The proposed technique is extremely simple as it uses only vector additions on the columns of the place-to-transition incident matrix.     

Parametric Transformation of Timed Weighted Marked Graphs: Applications in Optimal Resource Allocation

Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights)on edges,the performance analysis and resource optimization of such graphs represent a challenging problem.In this paper,we develop an approach to transform a timed weighted marked graph whose initial marking is not given,into an equivalent parametric timed marked graph where the edges have unitary weights.In order to explore an optimal resource allocation policy for a system,an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net.Finally,we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach.Simulation analysis shows that the developed approach is superior to the heuristic approach.     

Comments on “An Iterative Synthesis Approach to Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems”

In the above paper, it proposes a deadlock prevention policy for a flexible manufacturing system (FMS), which needs the complete state enumeration of the FMS that is modeled with Petri nets. The reachability graph of a Petri-net model is divided into two parts: the live zone (LZ) and the deadlock zone (DZ). The states in the LZ of the reachability graph of a Petri net constitute the legal behavior of the net from the viewpoint of deadlock prevention. The concept of first-met bad markings is proposed. A first-met bad marking is a node in DZ, whose father nodes are in LZ. The deadlock prevention policy is used in an iterative way. At each iteration, a first-met bad marking is identified from the reachability graph of a Petri net to be controlled. The reachability of a first-met bad marking is prohibited by adding a monitor, establishing a marking invariance relationship between the additional monitor and the activity places that are marked under the first-met bad marking. To achieve this, without a formal proof, [Lemma 1] is developed as shown in this article.     

Synthesis of Controllers of Processes Modeled as Colored Petri Nets

This paper presents an adaptation of a supervisory control theory and a supervisor synthesis problem to a class of colored Petri nets. More specifically, the forbidden state control problem with full observation, in which a discrete-event system is modeled as a colored Petri net with a symmetry specification, is investigated. This problem is decidable if the colored Petri net has finite color sets and bounded places. A new algorithm for deriving a controller is presented in detail with a proof of correctness. Unlike conventional algorithms that explore the entire reachable set of states, our algorithm avoids an exhaustive search of the state space by exploiting a symmetry specification. It performs particularly well when applied to large but structured processes with similar components. Furthermore, this approach leads to a representation of controllers which are smaller than those obtained with automaton-based approaches.