This paper proposes an active fault diagnosis method to enforce the diagnosability of discrete event systems using labeled Petri nets by constructing a diagnostic supervisor. For a non-diagnosable net model, its diagnosability is viewed as a control specification and addressed by using supervisory control techniques. First, an event-based monitor and a Petri net structure, referred to as data isolation arcs, are introduced to apply control specifications for labeled Petri nets. Then, a diagnostic supervisor reachability graph is generated to estimate the current state of the diagnoser. By analyzing the diagnostic supervisor reachability graph, an integer linear programming model is formulated to design a diagnostic supervisor, which can prevent the system from entering into any indeterminate cycle only by observing the occurrence of events. Finally, by the obtained diagnostic supervisor, the resulting net model is shown to be diagnosable. Some examples are presented to demonstrate the proposed method. Note to Practitioners—Faults have a significant impact on the normal operation of a system, and timely detection and isolation are crucial to ensuring system stability and production efficiency. Nevertheless, in certain systems, the occurrence of faults cannot be determined by a finite number of observations. To address this problem, this work introduces an active fault diagnosis method in the framework of labeled Petri nets, aiming to enforce the diagnosability of a system. The diagnosability condition is treated as a control specification such that it is readily accessible for practitioners to construct a diagnostic supervisor with Petri nets by following a typical and traditional control paradigm, which ensures that the controlled system is diagnosable.

This paper focuses on the modeling and analysis of systems with various temporal behaviors in the framework of discrete event systems modeled with time-dependent Petri nets. While Petri nets have been extensively studied, few existing formalisms effectively represent the coordination and synchronization among temporal behaviors. To this end, we first introduce a dual-time Petri net that captures both state-driven and event-driven behaviors by integrating temporal attributes associated with places and transitions, respectively. To describe the dynamic evolution of systems, a structural representation of the state space, abstracted as an extended state class graph, is presented. This representation serves as a foundation for analyzing critical system properties. Moreover, we show the efficiency of the proposed method to address the complexity in temporal dynamics, offering a more powerful modeling capability and a more compact structure compared with the existing time-dependent Petri net models. Finally, a case study on a semiconductor manufacturing system is provided to illustrate the practical application of the established model and reported analysis methods.

In this article, we introduce a novel weighted digraph, namely, a resource requirement graph, to address deadlock problems in flexible manufacturing systems (FMSs) modeled with Petri nets. A liveness-enforcing supervisor consisting of recovery transitions designed to be enabled at pre-partial deadlocks is synthesized. First, a resource requirement graph is directly derived from a Petri net model of an FMS and is used to represent competition relations for shared resources by various processes. Subsequently, the notion of pre-partial deadlock, described as a set of linear inequalities, is introduced by analyzing a resource requirement graph. Then, an algorithm is presented to develop a supervisor consisting of recovery transitions that are only enabled at the identified pre-partial deadlocks. The controlled Petri net model of an FMS under the designed supervisor is shown to be live with all initial reachable markings retained. The method proposed in this article offers computational efficiency since the resource requirement graph is structurally compact compared to its counterpart net model. Finally, several examples are provided to demonstrate the developed techniques.

This article investigates the state estimation for a networked timed discrete event system, where a plant communicates with a supervisor via a multichannel network characterized by bounded delays and losses. To address delays and losses in observation channels, we augment the plant by integrating the dynamics of these channels, thus capturing the system’s open-loop behavior. To tackle delays and losses in control channels, we augment the supervisor by considering all control decisions with potential impact on the system’s behavior. By integrating the augmented plant and supervisor, we introduce a compensated system that enables the derivation of an over-approximation of the closed-loop system’s behavior. Ultimately, we devise an online over-approximation state estimation algorithm for the closed-loop system, to compute all possible system states under communication delays and losses. We provide a simulation example to illustrate the efficacy of the proposed method.

A deadlock prevention policy for discrete event systems (DESs) modeled as unbounded Petri nets (UPNs) is developed in this article. A reachability tree, an essential instrument, shows the evolution of UPNs is fundamental for the description and analysis of several characteristics, including liveness and reversibility. Deadlocks are an undesirable situation within the realm of DESs, particularly those represented by Petri nets. This article introduces a method implemented through integer linear programming for UPNs. We explore the modified reachability trees of UPNs from a new lens by defining two classes of circuits, and exploit an algorithm to engineer a supervisor that ensures liveness and maximum permissiveness. The proposed approach can supervise and control all deadlock nodes in a reachability tree such that the closed-loop unbounded net is live. Finally, several typical cases are shown to demonstrate the reported methods.

This paper proposes an iterative approach to separate a set of admissible markings of a nonlinear constraint into a number of subsets. At each iteration, we find a maximal subset of admissible markings that are separated from inadmissible markings by linear constraints. Then, the union of all the obtained subsets constitutes the set of all admissible markings. For each subset of admissible markings, we obtain a set of conjunctive linear constraints. Accordingly, we can equivalently transform a given nonlinear constraint to be a set of disjunctive/conjunctive linear constraints, which can deal with the case that both admissible and inadmissible marking spaces of a nonlinear constraint cannot be separated by linear constraints from each other. Furthermore, we propose a method to design a Petri net supervisor for a derived set of disjunctive/conjunctive constraints. Some examples are used to demonstrate the proposed approach. Note to Practitioners—Linear constraints on Petri nets have been widely studied in the literature. However, not all control specifications can be represented as linear constraints. This paper proposes to enforce nonlinear constraints on Petri nets. A maximally permissive supervisor is designed to make the controlled net live with all admissible markings with respect to a given nonlinear constraint. Meanwhile, the structural complexity is also considered by compressing the number of control places in the supervisor. Experimental results show that the proposed approach can implement the control specifications represented by nonlinear constraints.

Deadlocks are a highly undesirable situation in flexible manufacturing systems (FMSs). This article presents a direct and novel method to detect such markings by constructing the resource flow graph of a Petri net that models an FMS and to recover such markings by adding a set of recovery transitions. First, an algorithm is developed to build a new kind of directed graph called the resource flow graph of a Petri net. Resource flow graphs can well represent the competition for shared resources by different processes. Second, based on the resource flow graph, loop graphs can be found. Furthermore, partial deadlock markings can be easily detected due to their relationship with loop graphs. Then, we propose an algorithm to design a set of recovery transitions for loop graphs that are enabled at partial deadlock markings. The proposed approach can detect partial deadlock markings without generating a complete reachability graph of a Petri net and the resulting net is deadlock-free with all reachable markings by adding the obtained recovery transitions. Finally, some widely used examples are provided to demonstrate the proposed approach.Note to Practitioners—The occurrence of deadlocks in an FMS tends to cause unnecessary productivity costs and even catastrophic results. In the framework of Petri nets, reachability graph analysis can usually obtain a maximally permissive supervisor of a plant. However, it is rather inefficient since it suffers from the state explosion problem. In this particular research, we develop an off-line deadlock detection and recovery policy by setting a group of virtual events that are not present in a physical model. The proposed approach is computationally efficient since it does not require to generate a reachability graph. It guarantees that the resulted system is deadlock-free with its all original reachable markings.

With integer linear programming problems (ILPPs) being formulated and solved, the existing approaches design optimal Petri-net supervisors via nonpure net structures, including self-loops and data inhibitor arcs. Nonpure net structures are powerful for control of Petri-net-modeled discrete-event systems. However, in the existing work, the formulated ILPPs contain a large number of constraints, which is computationally inefficient. In this article, we propose approaches that formulate ILPPs with fewer constraints such that the computational efficiency is significantly improved. To do so, in formulating ILPPs for optimal Petri-net controllers by using self-loops and data inhibitor arcs, we remove the reachability conditions for legal markings. By doing so, an obtained solution may result in some legal markings unreachable. To solve this problem, a novel technique is developed to design an optimal controller by modifying the initial marking and structure of the obtained supervisor. It is shown that, by the reduced ILPPs, one can find the same feasible solutions as that obtained by the existing work. Finally, the proposed approaches are demonstrated by examples.

State space techniques are one of the main approaches deployed for the analysis of concurrent systems. However, state space construction is stalled by a common phenomenon called the state explosion problem which makes it a tough task or even impossible when the state space computation demands prohibitive cost (time and memory). We limit general resource allocation systems (RASs) to a certain class whose state space can be hierarchically constructed, yet it comprises various enough types of real-world discrete event systems, such as automated manufacturing systems. This paper focuses on a class of RASs modeled with Petri nets (PNs), where, through pure algebraic operations, a novel method to compute the state spaces is proposed, which is motivated by the superposition property. Given a PN model of a system and a target resource configuration, we first propose a special initial marking called the initial basis marking and compute the corresponding reachability graph. Then, we increase the capacity of the resource places in an incremental way and generate the reachability graphs by taking advantage of the PN structure and the previously computed reachability graph until the capacity function of resources reaches the target resource configuration. A complete enumeration of reachable states can be obtained by a recursive scheme. Experimental studies also demonstrate the efficiency of the proposed approach in terms of computational cost and its high-potential to cope with the state-explosion problem.

This work proposes a novel structure in Petri nets, namely data inhibitor arcs, and their application to the optimal supervisory control of Petri nets. A data inhibitor arc is an arc from a place to a transition labeled with a set of integers. A transition is disabled by a data inhibitor arc if the number of tokens in the place is in the set of integers labeled on it. Its formal definitions and properties are given. Then, we propose a method to design an optimal Petri net supervisor with data inhibitor arcs to prevent a system from reaching illegal markings with respect to control specifications. Two techniques are developed to reduce the supervisor structure by compressing the number of control places. Finally, a number of examples are used to illustrate the proposed approaches and experimental results show that they can obtain optimal Petri net supervisors for the net models that cannot be optimally controlled by pure net supervisors. A significant result is that the proposed approach can always lead to an optimal supervisor with only one control place for bounded Petri nets on the premise that such a supervisor exists.

Supervisory control is usually considered as an external control mechanism to a system by controlling the occurrences of its controllable events. There exist Petri net models whose legal reachability spaces are nonconvex. In this case, they cannot be optimally controlled by the conjunctions of linear constraints. For Petri net models of flexible manufacturing systems, this work proposes a method to classify the legal markings into several subsets. Each subset is associated with a linear constraint that can forbid all first-met bad markings. Then, the disjunctions of the obtained constraints can make all legal markings reachable and forbid all first-met bad markings, i.e., the controlled net is live and maximally permissive. An integer linear programming model is formulated to minimize the number of the constraints. A supervisory structure is also proposed to implement the disjunctions of the constraints. Finally, examples are provided to illustrate the proposed method.

Some numerals inare found to be incorrect. Also,Definition 7inis unclear and should be stated as follows.

This paper presents a new Petri net structure, namely, an interval inhibitor arc, and its application to the optimal supervisory control of Petri nets. An interval inhibitor arc is an arc from a place to a transition labeled with an integer interval. The transition is disabled by the place if the number of tokens in the place is between the labeled interval. The formal definition and the firing rules of Petri nets with interval inhibitor arcs are developed. Then, an optimal Petri net supervisor based on the interval inhibitor arcs is designed to prevent a system from reaching illegal markings. Two techniques are developed to simplify the supervisory structure by compressing the number of control places. The proposed approaches are general since they can be applied to any bounded Petri net models. A marking reduction approach is also introduced if they are applied to Petri net models of flexible manufacturing systems. Finally, a number of examples are provided to demonstrate the proposed approaches and the experimental results show that they can obtain optimal Petri net supervisors for some net models that cannot be optimally controlled by pure net supervisors. Furthermore, the obtained supervisor is structurally simple.

Siphons play an important role in the development of deadlock control methods by using Petri nets. The number of siphons increases exponentially with respect to the size of a Petri net. This article presents a symbolic approach to the computation of minimal siphons in Petri nets by using binary decision diagrams (BDD). The siphons of a Petri net can be found via a set of logic conditions. The logic conditions are symbolically modeled by using Boolean algebras. The operations of Boolean algebras are implemented by BDD that are capable of representing large sets of siphons with small shared data structures. The proposed method first uses BDD to compute all siphons of a Petri net and then a binary relation is designed to extract all minimal siphons. Finally, by using a number of examples, the efficiency of the proposed method is verified through different-sized problems.

This paper illustrates that Petri nets with self-loops are more powerful than pure nets in modeling and control of flexible manufacturing systems. A self-loop in a Petri net cannot be mathematically represented by its incidence matrix. This paper presents a mathematical method to design a maximally permissive Petri net supervisor that is expressed by a set of control places with self-loops. A control place with a self-loop can be represented by a constraint and a self-loop associated with a transition whose firing may lead to an illegal marking. The constraint is designed to ensure that all legal markings are reachable and the self-loop is used to prevent the system from reaching illegal markings by disabling the transition at a specific marking. A marking-reduction approach is developed in order to cut down the considered markings, which can greatly decrease the computational overhead of the proposed method. An integer linear programming model is developed to compress the number of control places, aiming to reduce the structural complexity of the resulting supervisors. Finally, illustrative examples are used to validate the proposed method and to demonstrate that it can obtain an optimal supervisor for some cases that cannot be optimally controlled by pure net supervisors.

Behavioral permissiveness is one of the well-accepted criteria for evaluating the performance of a liveness-enforcing Petri net supervisor. However, a maximally permissive liveness-enforcing pure net supervisor does not always exist for any Petri net. This paper focuses on the nonexistence of maximally permissive liveness-enforcing pure net supervisors for a subclass of Petri nets. It shows that if a net contains a siphon that cannot be optimally controlled by a P-invariant, the net does not have a maximally permissive liveness-enforcing pure net supervisor. For a class of Petri nets that can model flexible manufacturing systems, sufficient conditions are proposed to decide whether there exists a siphon that cannot be optimally controlled. This paper also shows that a Petri net system does not have a maximally permissive liveness-enforcing pure net supervisor if it contains some special reachable markings.

Presents corrections to the second paragraph of Section V-B in the above titled paper (ibid., vol. 8, no. 2, pp. 374-393, Apr. 2011).

This paper presents two iterative deadlock prevention policies for flexible manufacturing systems (FMSs). Both can find a maximally permissive liveness-enforcing supervisor with a small number of control places. A vector covering approach is used to obtain a minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBMs), which are much smaller than the sets of legal markings and FBMs, respectively. At each iteration, by solving an integer linear programming problem (ILPP), a place invariant (PI) associated with a control place is designed to forbid as many FBMs as possible, and no markings in the minimal covering set of legal markings are forbidden. The objective function of the ILPP maximizes the number of FBMs that are forbidden by the PI. Then, the forbidden FBMs by the PI are removed from the minimal covered set of FBMs. This process is carried out until all FBMs are forbidden. Two ILPP design techniques are developed for the control policies. Though the proposed methods cannot in general guarantee the minimality of the supervisory structure, they reduce the overall computational time greatly, which is shown by numerical studies. Finally, a number of FMS examples from the literature are presented to illustrate the proposed methods.

This paper develops a place invariant based deadlock prevention method to obtain an optimal Petri net supervisor by considering its implemental cost. A supervisor is expressed by control places and the arcs connecting control places to transitions. We assign an implemental cost for each control place and arc. Maximally permissiveness can be achieved by designing place invariants that make all legal markings reachable while all first-met bad marking unreachable. By solving an integer linear programming problem (ILPP), a set of optimal control places are obtained and the objective function is used to minimize the implemental cost of the final supervisor. A vector covering approach is used to reduce the number of constraints and variables in the ILPP, aiming to reduce the computational overhead of the proposed method. Finally, a number of examples are used to illustrate the proposed approach.

Given a set of forbidden states in a plant model, an optimal Petri net supervisor is developed. The optimality is twofold. First, it provides a minimal supervisory control structure in the sense of the number of monitors that are used to prevent the occurrences of the forbidden states in a plant model. A monitor is designed by associating a P-semiflow with other places in the plant. Second, the supervisor is maximally permissive, i.e., no admissible state is excluded. If a maximally permissive supervisor does not exist, a most permissive supervisor can be similarly designed. A partial reachability graph of a plant is generated by considering the given forbidden states, from which first-met bad markings are then identified. Integer linear programming problems are employed to offer monitor solutions to ensure that the first-met bad markings are not reachable. Generalized mutual exclusion constraints are considered in this work.

Deadlock prevention plays an important role in the modeling and control of flexible manufacturing systems (FMS). This paper presents a novel and computationally efficient method to design optimal control places, and an iteration approach that only computes the reachability graph of a plant Petri net model once in order to obtain a maximally permissive liveness-enforcing supervisor for an FMS. By using a vector covering approach, a minimal covering set of legal markings and a minimal covered set of first-met bad markings (FBM) are computed. At each iteration, an FBM from the minimal covered set is selected. By solving an integer linear programming problem, a place invariant is designed to prevent the FBM from being reached and no marking in the minimal covering set of legal markings is forbidden. This process is carried out until no FBM can be reached. In order to make the considered problem computationally tractable, binary decision diagrams (BDD) are used to compute the sets of legal markings and FBM, and solve the vector covering problem to get a minimal covering set of legal markings and a minimal covered set of FBM. Finally, a number of FMS examples are presented to illustrate the proposed approaches.