On commoner's liveness theorem and supervisory policies that enforce liveness in free-choice Petri nets

A Petri net (PN) (Peterson, 1981; Reisig, 1985) is said to be live if it is possible to fire any transition from every reachable marking, although not necessarily immediately. A free-choice Petri net FCPN) is a PN, where every arch from a place to a transition is either the unique output arc from that place or it is the unique input arc to the transition. Commoner's Liveness Theorem (cf. Hack, 1972, Ch. 4; Reisig, 1985, Section 7.2) states that a FCPN is live if and only if every siphon contains a marked trap at the initial marking. A siphon (trap) is a collection of places P such that . We concern ourselves with marking-dependent supervisory policies that can prevent the firing of a transition. We characterize supervisory policies that enforce liveness in non-live FCPNs using observations that strongly parallel Commoner's Liveness Theorem. We use this characterization to establish the existence of supervisory policies that enforce liveness in a Class of FCPNs called independent, increasing free-choice petri nets (II-FCPNs).     

Robust control reconfiguration of resource allocation systems with Petri nets and integer programming

Supervisory control reconfiguration can handle the uncertainties including resource failures and task changes in discrete event systems. It was not addressed to exploit the robustness of closed-loop systems to accommodate some uncertainties in the prior studies. Such exploitation can cost-efficiently achieve reconfigurability and flexibility for real systems. This paper presents a robust reconfiguration method based on Petri nets (PNs) and integer programming for supervisory control of resource allocation systems (RASs) subject to varying resource allocation relationships. An allocation relationship is seen as a control specification while the execution processes requiring resources as an uncontrolled plant. First, a robust reconfiguration mechanism is proposed. It includes updating the P$P$-invariant-based supervisor and evolving the state of the closed-loop system. The latter adapts to the control specification changes by the self-regulation of the closed-loop system’s state. Next, two novel integer programming models for control reconfiguration are proposed, called a reconfiguration model with acceptability and reconfiguration one with specification correction. Since both models integrate the firability condition of transitions, no additional efforts are required for the state reachability analysis. Finally, a hospital emergency service system is used as an example to illustrate them.     

Some observations on supervisory policies that enforce liveness in partially controlled Free-Choice Petri nets

Every arc from a place to a transition in a Free-Choice Petri net (FCPN) is either the unique output arc of the place, or, the unique input arc to the transition [M.H.T. Hack, Analysis of production schemata by Petri nets, Master’s thesis, Massachusetts Institute of Technology, February 1972; W. Reisig, Petri Nets, Springer-Verlag, Berlin, 1985; T. Murata, Petri nets: properties, analysis and applications, Proc. IEEE 77 (4) (1989) 541–580]. We consider FCPNs that are not live [J.L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; W. Reisig, Petri Nets, Springer-Verlag, Berlin, 1985; T. Murata, Petri nets: properties, analysis and applications, Proc. IEEE 77 (4) (1989) 541–580], and we investigate the existence of supervisory policies that can enforce liveness in partially controlled FCPNs. The external agent, or supervisor, can only prevent the firing of some (i.e. not all) transitions in a partially controlled FCPN.

We first present an observation on supervisory policies that enforce liveness in partially-controlled FCPNs. Using this observation, we solve the supervisory synthesis problem for the family of c hoice-controlled FCPNs, defined in this paper. We then identify a new, sub-class of partially-controlled FCPNs that posses an easily-characterized (and easily-enforced) supervisory policy that enforces liveness.     

Integrated design of optimal supervisors for the enforcement of static and behavioral specifications in Petri net models

Petri net (PN) supervisory control is often performed through a sequential procedure that introduces additional constraint layers over an initial unconstrained PN model, using generalized mutual exclusion constraints (GMECs) implemented as monitor places. This is typical, e.g., in the context of flexible manufacturing systems, where the initial model represents the production sequences and the constraints are used to express static specifications, such as job limitations or the usage of resources, and behavioral ones, as liveness, controllability, etc. This sequential procedure may yield a redundant model, that is not easily reduced a posteriori. Also, it is difficult to ensure maximal permissivity with respect to multiple behavioral specifications. This paper, building on recent results regarding optimal supervisor design with branch & bound methods, proposes an integrated modeling approach that can be used to derive a minimal supervisor guaranteeing the attainment of an arbitrary set of static and behavioral specifications in a maximally permissive way. Among behavioral specifications, deadlock-freeness, liveness, reversibility and behavioral controllability are considered in the paper. The supervisor comes in the form of a simple set of GMECs or of a disjunction of sets of GMECs. Some examples emphasize the potential model size reductions that can be achieved.     

Fault detection for discrete event systems using Petri nets with unobservable transitions

In this paper we present a fault detection approach for discrete event systems using Petri nets. We assume that some of the transitions of the net are unobservable, including all those transitions that model faulty behaviors. Our diagnosis approach is based on the notions of basis marking and justification, that allow us to characterize the set of markings that are consistent with the actual observation, and the set of unobservable transitions whose firing enable it. This approach applies to all net systems whose unobservable subnet is acyclic. If the net system is also bounded the proposed approach may be significantly simplified by moving the most burdensome part of the procedure off-line, thanks to the construction of a graph, called the basis reachability graph.     

Petri网上的禁止状态监控器综合

给出了Petri网上广义互斥约束的最大允许监控器综合方法,其中该监控问题满足两个条件：正权值禁止库所的影响子网是状态机;负权值禁止库所的输入和输出变迁均只有一个输入库所.首先得到了监控器存在的充分和必要条件;其次构造了约束等价转换的方法,该方法可将存在不可控变迁的监控问题简化为相当于变迁全部可控的监控问题.最后通过一个例子说明了该方法的可行性.     

Decentralised control of continuous Petri nets

This paper focuses on decentralised control of systems modelled by continuous Petri nets, in which a target marking control problem is discussed. In some previous works, an efficient ON/OFF strategy-based minimum-time controller was developed. Nevertheless, the convergence is only proved for subclasses like Choice-Free nets. For a general net, the pre-conditions of applying the ON/OFF strategy are not given; therefore, the application scope of the method is unclear. In this work, we provide two sufficient conditions of applying the ON/OFF strategy-based controller to general nets. Furthermore, an extended algorithm for general nets is proposed, in which control laws are computed based on some limited information, without knowing the detailed structure of subsystems.     

Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems

In this paper an approach to on-line diagnosis of discrete event systems based on labeled Petri nets is presented. The approach is based on the notion of basis markings and justifications and it can be applied both to bounded and unbounded Petri nets whose unobservable subnet is acyclic. Moreover it is shown that, in the case of bounded Petri nets, the most burdensome part of the procedure may be moved off-line, computing a particular graph called Basis Reachability Graph.Finally, the effectiveness of the proposed procedure is analyzed applying a MATLAB diagnosis toolbox we developed to a manufacturing example taken from the literature.     

Multi-level hierarchical interface-based supervisory control

Hierarchical Interface-Based Supervisory Control employs interfaces that allow properties of a monolithic system to be verified through local analysis. By avoiding the need to verify properties globally, significant computational savings can be achieved. In this paper we provide local requirements for a multi-level architecture employing command-pair type interfaces. This multi-level architecture allows for a greater reduction in complexity and improved reconfigurability over the two-level case that has been previously studied since it allows the global system to be partitioned into smaller modules. This paper also provides results for synthesizing supervisors in the multi-level architecture that are locally maximally permissive with respect to a given specification and set of interfaces.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Bisimilarity enforcing supervisory control for deterministic specifications

This paper studies the supervisory control of nondeterministic discrete event systems to achieve a bisimulation equivalence between the controlled system and the deterministic specification. In particular, a necessary and sufficient condition is given for the existence of a bisimilarity enforcing supervisor, and a polynomial algorithm is developed to verify such a condition. When the existence condition holds, a bisimilarity enforcing supervisor is constructed. Otherwise, two methods are provided for synthesizing supremal feasible sub-specifications.     

On-line fault detection in discrete event systems by Petri nets and integer linear programming

The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an observable transition and employs an algorithm based on the definition and solution of some integer linear programming problems to decide whether the system behaviour is normal or exhibits some possible faults. The results characterize the properties that the PN modelling the system fault behaviour has to fulfill in order to reduce the on-line computational effort.     

一类受控Petri网的控制器设计

通过挖掘Petri网的内在的结构特性, 获得了一种新的解决禁止状态避免问题的控制器设计方法. 这种设计方法适用于一类具有特殊结构的受控Petri网 (即所有前向路径子网是状态机 )的状态反馈控制器设计. 在非并发的假设条件下, 所综合的控制器是最大允许.     

Gradient-based controllers for timed continuous Petri nets

This paper is about control design for timed continuous Petri nets that are described as piecewise affine systems. In this context, the marking vector is considered as the state space vector, weighted marking of place subsets are defined as the model outputs and the model inputs correspond to multiplicative control actions that slow down the firing rate of some controllable transitions. Structural and functional sensitivity of the outputs with respect to the inputs are discussed in terms of Petri nets. Then, gradient-based controllers (GBC) are developed in order to adapt the control actions of the controllable transitions according to desired trajectories of the outputs.     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.     

The fundamental closed-form solution of control-related states of kth order S3PR system with left-side non-sharing resource places of Petri nets

Due to the state explosion problem, it has been unimaginable to enumerate reachable states for Petri nets. Chao broke the barrier earlier by developing the very first closed-form solution of the number of reachable and other states for marked graphs and the kth order system. Instead of using first-met bad marking, we propose ‘the moment to launch resource allocation’ (MLR) as a partial deadlock avoidance policy for a large, real-time dynamic resource allocation system. Presently, we can use the future deadlock ratio of the current state as the indicator of MLR due to which the ratio can be obtained real-time by a closed-form formula. This paper progresses the application of an MLR concept one step further on Gen-Left kth order systems (one non-sharing resource place in any position of the left-side process), which is also the most fundamental asymmetric net structure, by the construction of the system's closed-form solution of the control-related states (reachable, forbidden, live and deadlock states) with a formula depending on the parameters of k and the location of the non-sharing resource. Here, we kick off a new era of real-time, dynamic resource allocation decisions by constructing a generalisation formula of kth order systems (Gen-Left) with r^* on the left side but at arbitrary locations.     

Event‐driven model predictive control of timed hybrid Petri nets

Hybrid Petri nets represent a powerful modeling formalism that offers the possibility of integrating, in a natural way, continuous and discrete dynamics in a single net model. Usual control approaches for hybrid nets can be divided into discrete‐time and continuous‐time approaches. Continuous‐time approaches are usually more precise, but can be computationally prohibitive. Discrete‐time approaches are less complex, but can entail mode‐mismatch errors due to fixed time discretization. This work proposes an optimization‐based event‐driven control approach that applies on continuous time models and where the control actions change when discrete events occur. Such an approach is computationally feasible for systems of interest in practice and avoids mode‐mismatch errors. In order to handle modelling errors and exogenous disturbances, the proposed approach is implemented in a closed‐loop strategy based on event‐driven model predictive control. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

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.     

Identification of the unobservable behaviour of industrial automation systems by Petri nets

This paper addresses the problem of identifying the model of the unobservable behaviour of discrete event systems in the industrial automation sector. Assuming that the fault-free system structure and dynamics are known, the paper proposes an algorithm that monitors the system on-line, storing the occurred observable event sequence and the corresponding reached states. At each event observation, the algorithm checks whether some unobservable events have occurred on the basis of the knowledge of the Petri net (PN) modelling the nominal system behaviour and the knowledge of the current PN marking. By defining and solving some integer linear programming problems, the algorithm decides whether it is necessary to introduce some unobservable (silent) transitions in the PN model and provides a PN structure that is consistent with the observed event string. A case study describing an industrial automation system shows the efficiency and the applicability of the proposed algorithm.