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.     

A generalization of state avoidance policies for controlled Petrinets

This paper presents a generalization of forbidden state control synthesis methods for a broad class of controlled Petri nets (CtlPN). An algebra is defined for characterizing the interaction of paths in the Petri net. Given a specification of a forbidden marking set, the net structure is analyzed to determine an algebraic expression to represent the specification. For any net marking (state), evaluation of the expression will indicate whether forbidden markings are reachable and whether control is necessary. The expression is then used for determining the maximally permissive feedback control law     

Deadlock-free Supervisor Design for Robotic Manufacturing Cells With Uncontrollable and Unobservable Events

In this paper,a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism.First,a Petri net for the deadlock control of such systems is defined.Its admissible markings and first-met inadmissible markings(FIMs)are introduced.Next,place invariants are designed via an integer linear program(ILP)to survive all admissible markings and prohibit all FIMs,keeping the underlying system from reaching deadlocks,livelocks,bad markings,and the markings that may evolve into them by firing uncontrollable transitions.ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition.In addition,the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs.The condition under which the supervisor is maximally permissive in behavior is given.Finally,experimental results with the proposed method and existing ones are given to show its effectiveness.     

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.     

离散事件系统的协调反馈控制

本文探讨以Ｐｅｔｒｉ网为模型的离散事件系统（ＤＥＳ）的某种禁止状态避免问题，提出了以Ｐｅｔｒｉ网Ｎ为基网，设计具有外部输入位置Ｐｅｔｒｉ网（ＰＮＩＰ），对Ｎ进行协调反馈控制的方法。由Ｎ现行状态反馈决定的ＰＮＩＰ的控制状态，既保证Ｎ避免禁止状态，又使Ｎ具有最大自由度。     

Net structure and control logic synthesis of controlled Petri nets

Control logic synthesis of discrete-event systems is considered in the setting of controlled Petri nets. The problem is to find a control policy that restricts the behavior of a controlled Petri net so that a collection of forbidden state conditions is satisfied. S-decreases are introduced as a tool for the control synthesis. The S-decreases are weight vectors defined on the places of a net such that the weighted sum of tokens in the net never increases with any transition firing. On the basis of S-decreases, the authors propose an efficient method for the synthesis of the maximally permissive state feedback control polity for a class of controlled Petri nets whose uncontrolled subnets are forward and backward conflict-free nets. This method upgrades all integer linear programming-based methods for which one only requires to solve the much simpler linear programming problems to determine maximally permissive controls     

Controller Synthesis with Highly Simplified Linear Constraints

This paper deals with the problem of forbidden states in safe Petri nets to obtain a maximally permissive controller. To prevent the system from entering the forbidden states, assigning some constraints to them is possible. The constraints can be enforced on the system using control places. When the number of forbidden states is large, a large number of constraints should be assigned to them. This results in a large number of control places being added to the model of the system, which causes a complicated model. Some methods have been proposed to reduce the number of constraints. Nevertheless, they do not always give the best results. In this paper, two ideas are offered to reduce the number of constraints, giving a more simplified controller.     

Control of Safe Ordinary Petri Nets Using Unfolding

In this paper we deal with the problem of controlling a safe place/transition net so as to avoid a set of forbidden markings . We say that a given set of markings has property REACH if it is closed under the reachability operator. We assume that all transitions of the net are controllable and that the set of forbidden markings has the property REACH. The technique of unfolding is used to design a maximally permissive supervisor to solve this control problem. The supervisor takes the form of a set of control places to be added to the unfolding of the original net. The approach is also extended to the problem of preventing a larger set of impending forbidden marking. This is a superset of the forbidden markings that also includes all those markings from which—unless the supervisor blocks the plant—a marking in is inevitably reached in a finite number of steps. Finally, we consider the particular case in which the control objective is that of designing a maximally permissive supervisor for deadlock avoidance and we show that in this particular case our procedure can be efficiently implemented by means of linear algebraic techniques. Submitted to Discrete Event Dynamic Systems. A preliminary version of this paper titled “Control of safe ordinary Petri nets with marking specifications using unfolding,” was published in the Proc. IFAC WODES'04: 7th Work. on Discrete Event Systems (Reims, France), September 2004. Contact author is Alessandro Giua.     

Solving the Problem of Forbidden States in Discrete Event Systems: A Novel Systematic Method for Reducing the Number of Control Places

This paper deals with the problem of forbidden states in Discrete Event Systems modelled by non‐safe Petri Nets. To avoid these states, some Generalized Mutual Exclusion Constraints can be assigned to them. These constraints limit the weight sum of tokens in some places and can be enforced on the system using control places. When the number of these constraints is large, a large number of control places should be added to the system. In this paper, a method is presented to assign the small number of constraints to forbidden states using some states which cover the forbidden states. So, a small number of control places are added to the system leading to obtaining a maximally permissive controller.     

On the lower bound of monitor solutions of maximally permissive supervisors for a subclass α-S3PR of flexible manufacturing systems

Recently, a novel and computationally efficient method – based on a vector covering approach – to design optimal control places and an iteration approach that computes the reachability graph to obtain a maximally permissive liveness enforcing supervisor for FMS (flexible manufacturing systems) have been reported. However, it is unclear as to the relationship between the structure of the net and the minimal number of monitors required. This paper develops a theory to show that the minimal number of monitors required cannot be less than that of basic siphons in α-S³PR (systems of simple sequential processes with resources). This confirms that two of the three controlled systems by Chen et al. are of a minimal monitor configuration since they belong to α-S³PR and their number in each example equals that of basic siphons.     

Supervisory control based on minimal cuts and Petri net sub-controllers coordination

This paper addresses the synthesis of Petri net (PN) controller for the forbidden state transition problem with a new utilisation of the theory of regions. Moreover, as any method of control synthesis based on a reachability graph, the theory of regions suffers from the combinatorial explosion problem. The proposed work minimises the number of equations in the linear system of theory of regions and therefore one can reduce the computation time. In this paper, two different approaches are proposed to select minimal cuts in the reachability graph in order to synthesise a PN controller. Thanks to a switch from one cut to another, one can activate and deactivate the corresponding?PNcontroller. An application is implemented in a flexible manufacturing system to illustrate the present method. Finally, comparison with previous works with experimental results in obtaining a maximally permissive controller is presented.     

一类受控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.     

Supervisor synthesis for discrete event systems under partial observation and arbitrary forbidden state specifications

In this paper, we consider the forbidden state problem in discrete event systems modeled by partially observed and partially controlled Petri nets. Assuming that the reverse net of the uncontrollable subnet of the Petri net is structurally bounded, we compute a set of weakly forbidden markings from which forbidden markings can be reached by firing a sequence of uncontrollable/unobservable transitions. We then use reduced consistent markings to represent the set of consistent markings for Petri nets with structurally bounded unobservable subnets. We determine the control policy by checking if the firing of a certain controllable transition will lead to a subsequent reduced consistent marking that belongs to the set of weakly forbidden markings; if so, we disable the corresponding controllable transition. This approach is shown to be minimally restrictive in the sense that it only disables behavior that can potentially lead to a forbidden marking. The setting in this paper generalizes previous work by studying supervisory control for partially observed and partially controlled Petri nets with a general labeling function and a finite number of arbitrary forbidden states. In contrast, most previous work focuses on either labeling functions that assign a unique label to each observable transition or forbidden states that are represented using linear inequalities. More importantly, we demonstrate that, in general, the separation between observation and control (as considered in previous work) may not hold in our setting.     

Suboptimal supervisory control of Petri nets in presence of uncontrollable transitions via monitor places

This paper deals with the problem of enforcing generalized mutual exclusion constraints (GMEC) on place/transition nets with uncontrollable transitions. An efficient control synthesis technique, which has been proposed in the literature, enforces GMEC constraints by introducing monitor places to create suitable place invariants. The method has been shown to be maximally permissive and to give a unique control structure in the case that the set of legal markings is controllable. This paper investigates on and formally shows that the class of controllers obtained by this technique may not have a supremal element for uncontrollable specifications. Moreover, it is shown that the family of monitor places enforcing an uncontrollable specification can be parameterized with respect to the solution of a linear system of equation. An algorithm to obtain such parameterization is presented here.     

Reduction of the supervisory control problem for Petri nets

The authors prove a reduction theorem for the supervisory control problem for general Petri nets with general legal sets. To design control laws guaranteeing that the marking stays within the legal set, it suffices to consider a sub-Petri net of the full model. This extends existing design algorithms, allows to prove an important property of maximally permissive control laws and limits the number of events which need to be observed     

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

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

基于GMEC转换算法的Petri网结构控制器综合方法

针对含不可控变迁Petri网系统禁止状态控制器设计问题,提出了一种基于矩阵变换和整数线性规划的结构控制器综合方法。该方法的关键是对代表系统合法状态的广义互斥约束(generalized mutual exclusion constraint, GMEC)进行转换。首先,根据Petri网系统的关联矩阵,将库所集分为无关库所集、不可控库所集和补足库所集。其次,通过对非允许GMEC中补足库所的权值和不可控库所的权值进行处理,并运用整数线性规划将非允许GMEC转换为允许GMEC。在允许GMEC的基础上,根据库所不变量原理设计出Petri网系统的结构控制器。最后,以某零件加工系统为例验证了所提方法的泛用性和高效性,为实际智能制造系统的监督控制器设计提供有效参考方案。     

Reduction of constraints for controller synthesis based on safe Petri Nets

In this paper, we present an efficient method based on safe Petri Nets to construct a controller. A set of linear constraints allows forbidding the reachability of specific states. The number of these so-called forbidden states, and consequently the number of constraints, are large and lead to a large number of control places. A systematic method to reduce the size and the number of constraints for safe Petri Nets is offered. By using a method based on Petri Net invariants, maximal permissive controllers are determined.     

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.