In this paper, a general approach is proposed for the computation of a liveness enforcing supervisor for the Petri net model of a flexible manufacturing system (FMS) prone to deadlocks. The proposed method is applicable to a lot of PN classes. A global sink/source place (GP) is used temporarily in the design steps and is finally removed when the liveness of the system is achieved. The aim is to obtain an easy to design deadlock prevention policy for PN models of FMSs that ensures liveness with optimal or near optimal permissiveness while maintaining the necessary computations simple.
Flexible manufacturing systems (FMS) are widely used by manufacturers. In an
FMS, in order to finish pre-established operations, different processes compete for the
limited number of shared resources such as buffers, fixtures, robots, automated guided
vehicles (AGV), and other material-handling devices. Thus, this competition may
result in deadlocks, a highly undesirable situation in which some processes keep
waiting indefinitely for the other processes to release resources. Recently, a lot of work
has been done to deal with the deadlock problem in FMSs [
Petri nets are widely used for the modeling of FMS due to their ability to easily
detect the good behavior of a system like boundedness and deadlock-freeness [
The rest of this paper is organized as follows. Some basic Petri net definitions used in this paper are briefly reviewed in Section 2. A general synthesis approach for liveness enforcement in Petri net models of FMS is proposed in section 3. An illustrative example is given in section 4, to show the applicability of the proposed method. Finally, some conclusions and directions for further research are provided in section 5. 2
In this paper, Petri nets are used to model the flow of products in an FMS. Petri nets as a mathematical tool have a number of properties. When interpreted in the context of modeled manufacturing system, these properties allow one to identify the presence or absence of the functional properties of the system. In this section, some definitions and concepts which are related to this paper are briefly reviewed.
A Petri net is a five-tuple, PN = (P, T, F, W, M0) where: P = {p1, p2, …, pm} is a finite set of places, where m > 0; T = {t1, t2, …, tn} is a finite set of transitions, where n > 0, with P T and P T ; F ( P T ) ( T P ) is the set of all directed arcs, where P T N is the input function that defines the set of directed arcs from P to T, and T P N is the output function that defines the set of directed arcs from T to P, where N = {0, 1, 2, …} is a set of non-negative integers, W: F N is the weight function. M0: P N is the initial marking. The set of input (resp., output) transitions of a place p is denoted by p (resp., p). Similarly, the set of input (resp., output) places of a transition t is denoted by t (resp., t). A Petri net structure (P, T, F, W) without any specific initial marking is denoted by G. A Petri net with the given initial marking is denoted by (G, M0). A transition t is said to be enabled or firable if each input place p t is marked with at least w(p,t) tokens, where w(p,t) is the weight of the arc from p to t. A transition may fire if it is enabled. The firing of an enabled transition t removes w(p,t) tokens from each input place p t, and adds w(t,p) tokens to each output place p t, where w(t,p) is the weight of the arc from t to p. This process is denoted by M [t > M’. The marking M of a Petri net indicates the number of tokens in each place, which represents the current state of the modelled system. When a marking M’ is reached from a marking M by firing a sequence of transitions = t0t1t2…tk, this process is then denoted by M [ > M’. The set of all reachable markings for a Petri net with initial marking M0 is denoted by RM(G,M0).
A pair of a place p and a transition t is called a self-loop if both p t and p t hold. A Petri net is said to be pure if it has no self-loops. A Petri net is said to be ordinary if the weight of each arc is 1. A Petri net G is called k-bounded, or simply bounded if for every reachable marking M RM(G,M0), the number of tokens in any place p, p P, is not greater than a finite number k, i.e. M(p) k. A place p is called k-bounded, if the number of tokens in it is not greater than k. A Petri net G is called safe, if it is 1-bounded. A 1-bounded place p is called a safe place. Places are frequently used to represent buffers, tools, pallets, and AGVs in manufacturing systems. Boundedness is used to identify the existence of overflows in the modelled system. When a place models an operation, its safeness guarantees that the controller will not attempt to initiate an on-going process. A transition t is said to be live if for any M RM(G,M0), there exists a sequence of transitions firable from M which contains t. A Petri net G is said to be live if all the transitions are live. A Petri net G contains a deadlock if there is a marking M RM(G,M0) at which no transition is enabled. Such a marking is called a dead marking. Deadlock situations are a result of inappropriate resource allocation policies or exhaustive use of some or all resources. Liveness of a Petri net means that for each marking M RM(G,M0) reachable from M0, it is finally possible to fire any transition t, t T, in the Petri net through some firing sequence. This means that a live Petri net guarantees deadlock-free operations, no matter what firing sequence is chosen, i.e. if a Petri net is live, then it has no deadlock. A Petri net (G, M0) is said to be reversible, if for each marking M RM(G,M0), M0 is reachable from M. Thus, in a reversible net it is always possible to go back to initial marking (state) M0. Many systems are required to return from the failure states to the preceding correct states. Thus the reversibility property is important to manufacturing system error recovery. This property also guarantees cyclic behavior for all repetitive manufacturing systems. Moreover, if a net contains a deadlock, then it is not reversible. A marking M’ is said to be a home state, if for each marking M RM(G,M0), M’ is reachable from M. Reversibility is a special case of the home state property, i.e. if the home state M’ = M0, then the net is reversible. 3
In this section, a general method is proposed for the computation of a liveness enforcing supervisor for a given Petri net model (PNM) of an FMS prone to deadlocks. There are usually three groups of the places in a PNM of an FMS: resource places (PR), activity places (PA) and sink/source places (PS/S). Resource places represent either shared or non-shared resources and initially there are tokens in these places representing the number of available resources. Activity places represent an action to process a part in a production sequence by a resource (machine, robot, etc.) and initially there are no tokens in these places. Initially, tokens deposited in sink/source places represent the maximal possible number of concurrent activities that can take place in a production sequence. In cyclic models a sink place is also a source place and vice versa.
The proposed method is applicable to a lot of Petri net classes currently available in
the related literature. All computed monitors have ordinary arcs due to the proposed
method. The algorithm provided below is used to compute the control places
(monitors) based on the PNM. In the monitor computation steps of the proposed algorithm, a
global sink/source place (GP) is used to make the necessary computation easily in an
iterative way. The input transitions of the GP are input transitions of all sink/source
places PS/S. Likewise output transitions of the GP are output transitions of all
sink/source places PS/S. At each iteration, the reachability graph (RG) of the related net
is computed. If the net is not live, then the RG is divided into a dead zone (DZ) and a
live zone (LZ). The former may contain deadlock states (markings), and states which
are inevitable lead to deadlocks or livelocks. The latter constitutes remaining good
states of the RG representing the optimal system behavior. The control policy is based
on the exclusion of the DZ from the RG, while making sure that every state within the
LZ can still be reached. All states in the DZ are considered as bad markings (BM).
From a BM, only the markings of activity places are considered. Then, the objective is
to prevent the marking of the subset of the activity places of the BM from being
reached. Therefore, the marking of the subset of the activity places is characterized as a
place invariant (PI) of the PNM. In the PI relating to a BM, the sum of tokens within
the subset of the activity places has to be at most one token less than their current value
within the BM in order not to reach the BM. A PI can be implemented by a control
place with its related arcs and initial marking. Here the simplified version [
Algorithm: Synthesis of Liveness Enforcing Supervisor for Petri Net Models Input: A Petri net model (PNM) of an FMS prone to deadlocks Output: Liveness enforcing supervisor for the PNM Step 1. Define input and output transitions of all sink/source places PS/S. Add a global sink/source place (GP) to the PNM. Thus a new net system denoted as NB = PNM + GP is obtained, where B N = {1, 2, …}.
Step 2. for (B = 1; B ≤ K; B ++) /* B is the number of tokens in GP and K is the sum of initial tokens in all sink/source places PS/S */ { 2.B.1. Compute the reachability graph RGB of NB.
If NB is live, Then consider net NB with B:=B+1, i.e., go to step 2.B.1).
Else define the LZB and DZB of RGB. 2.B.2. Define a PI for each bad marking (BM) within DZB, from the subset of marked activity places of BM. 2.B.3. method.
Compute a monitor C for each PI using the simplified invariant-based control
2.B.4. If the number of monitors computed for NB is greater than 1, then carry out
the redundancy test by using the method proposed in [
end of Algorithm. 4
In order to show the applicability of the proposed synthesis approach, in this
section an example is considered. Fig. 1 shows an L-S3PR net taken from [
Step 1. Input transitions of sink/source places p1 and p6 are ˙ p1= {t1} and ˙ p6 = {t10}. Likewise output transitions of p1 and p6 are p1˙ = {t5} and p6˙ = {t6}. Therefore input and output transitions of the GP are ˙ GP = {t1, t10} and GP˙ = {t5, t6}. When the GP is added within the PNM, a new net structure NB = PNM + GP is obtained as shown in Fig. 2.
5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 t5 p5 t4 p4 t3 p3 t2 p2 t1 5
p1
Step 2.1.1. (B = 1). When one token is deposited in the GP, the net N1 shown in Fig. 3 is obtained.
Step 2.2.2. The markings of the activity places of BM1 are shown in Table 1. Step 2.2.3. In order to enforce PI1, monitor C1 is computed as shown in Table 2.
It is verified that the controlled model N2 shown in Fig. 5 is live with 34 good states. This is the optimal live behavior for the controlled N2.
Step 2.3.1. (B:= B+1 = 3). The net N3, shown in Fig. 6, is obtained by increasing the number of tokens in the GP within the controlled N2.
5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 3 GP p14 p13 p12 p11 t10 p10 t9 p9 t8 p8 t7 p7 t6 p6 5 t4 t9
C1 t5 t8
The net N3 is not live. There are 73 states within the RG3 of N3. DZ3 includes 3 bad states BM1, BM2 and BM3, and LZ3 contains 70 good states.
Step 2.3.2. The markings of the activity places of BM2, BM3 and BM4 are shown in Table 3.
In order not to reach BM2, BM3 and BM4 the following place invariants are established respectively: PI2 = μ3 + μ7 ≤ 2, PI3 = μ4 + μ8 ≤ 2, PI4 = μ5 + μ8 ≤ 2.
Step 2.3.3. Monitors C2, C3 and C4 are computed in order to enforce PI2, PI3 and PI4 as shown in Table 4.
Step 2.3.4. The redundancy test shows that computed monitors C2, C3 and C4 are all necessary.
Step 2.3.5. When C2, C3 and C4 are augmented in the uncontrolled model N3, the controlled N3 is obtained as follows: N3:= N3 + C2 + C3 + C4 and is shown in Fig. 7. 5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 3 GP p14 p13 p12 p11 t10 p10 t9 p9 t8 p8 t7 p7 t6 p6 5 t4 t9 t2 t7 t3 t8 t4
C1 C2 C3 C4 t5 t8 t3 t8 t7
Figure 7. The controlled N3 (N3:= N3 + C2 + C3 + C4).
It is verified that the controlled model N3 shown in Fig. 7 is live with 70 good states. This is the optimal live behavior for the controlled N3.
Step 2.4.1. (B:= B+1 = 4). The net N4, shown in Fig. 8, is obtained by increasing the number of tokens in the GP within the controlled N3.
5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 C2 C3 C4 t8 t3 t7 t5 t7
The net N4 is not live. There are 91 states within the RG4 of N4. DZ4 includes 3 bad states BM5, BM6 and BM7 and LZ4 contains 88 good states.
Step 2.4.2. The markings of the activity places of BM5, BM6 and BM7 are shown in Table 5.
Step 2.4.3. Monitors C5, C6 and C7 are computed in order to enforce PI5, PI6 and PI7 as shown in Table 6.
Step 2.4.4. The redundancy test shows that computed monitors C5, C6 and C7 are all necessary.
Step 2.4.5. When C5, C6 and C7 are augmented in the uncontrolled model N4, the controlled N4 is obtained as follows: N4 := N4 + C5 + C6 + C7 and is shown in Fig. 9. 5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 4 GP p14 p13 p12 p11 t10 p10 t9 p9 t8 p8 t7 p7 t6 p6 5 t4 t9 t2 t7 t3 t8 t4
C1 C2 C3 C4 t5 t8 t3
C5 C6 C7 t3 t5 t6 t5 t6
It is verified that the controlled model N4 shown in Fig. 9 is live with 88 good states.
Step 2.5.1. (B:= B+1 = 5). The net N5, shown in Fig. 10, is obtained by increasing the number of tokens in the GP within the controlled N4.
5 p1 t5 p5 t4 p4 t3 p3 t2 p2 t1 C2 C3 C4 t8 t3 t7 t5 t7 t2 t4 t8 t2 t8 t3 t8
C5 C6 C7 t3 t5 t6 t5 t6
The net N5 is live with 92 good states. This is the optimal solution for both the N5 and the original uncontrolled PNM.
Step 3. The live controlled PNM shown in Fig. 11 is obtained by augmenting seven monitors, computed in step 2 and provided in Table 7, into the uncontrolled model PNM shown in Fig. 1. It is live with 92 good states. The liveness enforcing procedure applied for the PNM is provided in Table 8. In this table the last column shows the number of unreachable states. As the elements of this column are all zero this indicates that there are no good states lost due to included monitors. t9 t2 t7 t3 t8 t4 t8 C2 C3 C4
C5 C6 C7 t3 t5 t6 t5 t6 B In this paper, a general method is proposed to obtain an optimal or a near optimal solution for the synthesis of liveness enforcing supervisors in flexible manufacturing systems modeled with Petri nets. The applicability of the proposed approach is shown by means of an example from the literature. The method is easy to use and provides very high behavioral permissiveness. The proposed method is applicable as is to a lot of Petri net classes currently available in the literature without modifications. Therefore further publications will be provided to show the applicability of the proposed method to different classes of Petri nets. Further research will also be conducted to improve the behavioral permissiveness of the proposed approach for generalized Petri net models such as S4R or S4PR.
This work was supported by the research grant of the Scientific and Technological Research Council of Turkey (Türkiye Bilimsel ve Teknolojik Araştırma Kurumu) under the project number TÜBİTAK-112M229, and the Science and Technology Development Fund, MSAR, under Grant No. 066/2012/A2, and National Natural Science Foundation of China under Grant No. 61374068