A hybrid approach to supervisory control of discrete event systems coupling RW supervisors to Petri nets

In this paper a hybrid approach is proposed for supervisory control of discrete event systems (DES) subject to forbidden states. Assuming that an uncontrolled bounded Petri net (PN) model of a (plant) DES and a set of forbidden state specifications are given, the proposed approach computes a maximally permissive and nonblocking closed-loop hybrid model. The first step is to simplify the given PN model by means of PN reduction rules. The simplified model and the specifications are then represented as buffers, and supervisory control theory (SCT) is applied to obtain a Ramadge–Wonham (RW) supervisor in the form of an automaton. After reduction of the latter’s state size by a ‘control congruence’, the simplified RW supervisor is represented by a so-called auto-net and coupled to the given uncontrolled PN plant model by means of inhibitor arcs to represent the disabling actions. The plant model and supervisor auto-net run concurrently, synchronizing on shared events. This procedure provides a maximally permissive and nonblocking ‘hybrid’ (mixed PN/automaton) closed-loop controlled system. The method is straightforward logically, graphically, and technologically. Its applicability is shown by two examples, one of them a workcell from the PN control literature.     

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems

In a flexible manufacturing system (FMS) with multiple products, deadlocks can arise due to limited shared resources, such as machines, robots, buffers, fixtures etc. The development of efficient deadlock prevention policies, which can optimise the use of system resources, while preventing deadlocks from occurring, has long been an important issue to be addressed. In [1], an optimal deadlock prevention policy was proposed, based on the use of reachability graph (RG) analysis of the Petri net model (PNM) of a given FMS and the synthesis of a set of new net elements, namely places with initial marking and related arcs, to be added to the PNM, using the theory of regions. The policy proposed in [1] is optimal in the sense that it allows the maximal use of resources in the system according to the production requirements. For very big PNMs, the reachability graph of the PNMs becomes very large and the necessary computations to obtain an optimal deadlock prevention policy become more difficult. In this paper, we propose the use of the Petri net reduction approach to simplify very big PNMs so as to make necessary calculations easily in order to obtain an optimal deadlock prevention policy for FMSs. An example is provided for illustration.     

Comments on “deadlock prevention policy based on petri nets and siphons”

Some well-known decision problems can be regarded as special cases of the resource-constrained project-scheduling problem (RCPSP) with respect to the structure of their mathematical models. These decision models include assembly line balancing, job shop scheduling and some packing problems. Here, the differences and similarities of mathematical models of the multilevel capacitated lot-sizing problem (MLCLSP) and the RCPSP are shown, and it is concluded that the RCPSP is a special case of the MLCLSP. This theoretical result is complemented by an integrated, general model formulation that allows one to coordinate customer-specific orders and make-to-stock (lot size) production at the master (production) planning level.     

An Iterative Synthesis Approach to Petri Net-Based Deadlock Prevention Policy for Flexible Manufacturing Systems

This paper proposes an iterative synthesis approach to Petri net (PN)-based deadlock prevention policy for flexible manufacturing systems (FMS). Given the PN model (PNM) of an FMS prone to deadlock, the goal is to synthesize a live controlled PNM. Its use for FMS control guarantees its deadlock-free operation and high performance in terms of resource utilization and system throughput. The proposed method is an iterative approach. At each iteration, a first-met bad marking is singled out from the reachability graph of a given PNM. The objective is to prevent this marking from being reached via a place invariant of the PN. A well-established invariant-based control method is used to derive a control place. This process is carried out until the net model becomes live. The proposed method is generally applicable, easy to use, effective, and straightforward although its off-line computation is of exponential complexity. Two FMS are used to show its effectiveness and applicability     

Asynchronous implementation of discrete event controllers based on safe automation Petri nets

In this paper, a new method is proposed for digital hardware implementation of Petri net-based specifications. The purpose of this paper is to introduce a new discrete event control system paradigm, where the control system is modeled with extended Petri nets and implemented as an asynchronous controller using circuit elements. The applicability of the proposed method is demonstrated by an asynchronous implementation of a Petri net-based discrete event control system (DECS) for an experimental manufacturing system using a Xilinx field programmable gate array (FPGA). Unlike microprocessor, microcontroller or programmable logic controller (PLC)-based software implementations or hardware-based synchronous implementations, the implementation method used in this paper is asynchronous and based on hardware offering very high speed to control fast plants at low cost. This paper is expected to serve as a guideline to show how to obtain very high speed, concurrent and asynchronous Petri net-based controllers.     

Comments on “Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources”

As reported by Hu and Li (International Journal of Advanced Manufacturing Technology 40:566-571, 2009), in order to design liveness-enforcing supervisors for automated manufacturing systems (AMS), a deadlock prevention policy was proposed based on the exhausted resources. The proposed policy exploits a special structure of Petri nets for the liveness of a specific system. In order to show the applicability of this method, two examples were considered. One of the examples involves an AMS with a large-state space. Unfortunately, the liveness-enforcing supervisor containing seven monitors (control places) computed as reported by Hu and Li (International Journal of Advanced Manufacturing Technology 40:566-571, 2009) to enforce liveness on this system does not provide a live behaviour. This paper reports this fact.     

A general technique for the PLC-Based implementation of RW supervisors with time delay functions

The Supervisory Control Theory (SCT) introduced by Ramadge–Wonham (RW) is a general theory to design supervisors (controllers) for discrete event systems. Although over the two decades SCT has received wide attention in academia, industrial applications are very few, due to the fact that there is a discrepancy between the abstract RW supervisor and its physical implementation. In this paper, an easy to use, general and practical technique is proposed for the PLC-based implementation of RW supervisors with time delay functions. The applicability of the proposed method is demonstrated by means of a PLC-based real-time control of an experimental manufacturing system.     

A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems

In this paper a divide-and-conquer-method for the synthesis of liveness enforcing supervisors (LES) for flexible manufacturing systems (FMS) is proposed. Given the Petri net model (PNM) of an FMS prone to deadlocks, it aims to synthesize a live controlled Petri net system. For complex systems, the use of reachability graph (RG) based deadlock prevention methods is a challenging problem, as the RG of a PNM easily becomes unmanageable. To obtain the LESs from a large PNM is usually intractable. In this paper, to ease this problem the PNM of a system is divided into small connected subnets. Each connected subnet prone to deadlocks is then used to compute the LES for the original PNM. Starting from the simplest subnet prone to deadlocks to make the subnet live, monitors (control places) are computed. The RG of each subnet is considered and split into a dead-zone (DZ) and a live-zone. All states in the DZ are prevented from being reached by means of a well-established invariant-based control method. Next, the computation of monitors is followed for bigger subnets. Previously computed monitors are included within the bigger subnets based on a criterion. This process keeps the DZ of the bigger subnets smaller compared with the original uncontrolled subnets. When all subnets are live we obtain a set of monitors that are included within the PNM to obtain a partially controlled PNM (pCPNM). A new set of monitors is also computed for the pCPNM. Finally, a live controlled Petri net system is obtained. The proposed method is generally applicable, easy to use, effective and straightforward although its off-line computation is of exponential complexity in theory. Its use for FMS control guarantees deadlock-free operation and high performance in terms of resource utilization and system throughput. Two FMS deadlock problems from the literature are used to illustrate the applicability and the effectiveness of the proposed method.     

Synthesis of feedback control elements for discrete event systems using Petri net models and theory of regions

This paper describes a method for constructing a Petri-net-based controller for a discrete event system (DES) modelled by a Petri net. Assuming that an uncontrolled Petri net model of the DES and a set of forbidden state specifications are given, feedback control elements, i.e. a set of places and related transitions, with initial marking, are computed using the theory of regions, which is a formal synthesis technique for deriving Petri nets from automaton-based models. When feedback control elements are added to the uncontrolled Petri net model, the controlled (closed-loop) Petri net model of the system is obtained. The controlled Petri net model obtained is maximally permissive while guaranteeing that forbidden states do not occur. The proposed method is computationally efficient and does not suffer from the state explosion problem. Two examples are provided to show the applicability of the proposed method.