# Supervisor Reconfiguration for Deadlock Prevention by Resources Reallocation

Authors: Miao Liu; Shouguang Wang; Zhiwu Li
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Analysis and control of deadlocks play an important role in the design and operation of automated flexible manufacturing systems (FMSs). In FMS, deadlocks are highly undesirable situations, which always cause unnecessary cost. The design problem of an optimal supervisor is in general NP-hard. A computationally efficient method often ends up with a suboptimal one. This paper develops a deadlock prevention policy based on resources reallocation and supervisor reconfiguration. First, given a plant model, we reallocate the marking of each resource place to be one, obtaining a net model whose reachable states are much less than that of the original one. In this case, we find a controlled system for it by using the theory of regions. Next, the markings of the resource places in the controlled system are restored to their original ones. Without changing the structure of the obtained controlled system, we compute the markings of the monitors gradually, which can be realized by two algorithms proposed in this paper. Finally, we decide a marking for each monitor such that it makes the controlled system live with nearly optimal permissive behavior. Two FMS examples are used to illustrate the application of the proposed method and show its superior efficiency.


---

## Body

## 1. Introduction

Traditional mass production systems can hardly cope with intensive competition in market and rapid variation in requirements. Hence, automated flexible manufacturing systems (FMSs) arise, aiming to offer a novel production mode with a small batch and multiple product types. The analysis and control of such systems have become the hot topics in the field of manufacturing systems. Petri nets [1] are a graph-based mathematical formalism suitable to describe, model, and analyze the behavior of automated flexible manufacturing systems.Due to the existence of shared resources, an FMS may contain deadlocks. Based on Petri nets, researchers have developed many policies to deal with the deadlock problem [2–6] in FMS. Generally, there are mainly two analysis techniques to deal with deadlock prevention in FMS: structure [7–11] and reachability graph analysis [12–16]. The former always obtains a deadlock prevention policy through special structural objects of a Petri net such as siphons and resource-transition circuits. This method can usually obtain a computationally efficient liveness-enforcing supervisor in general but at the same time restrict a system such that a portion of permissive behavior is excluded. For the latter, the reachability graph can completely reflect the behavior of a system. Though a very highly or even maximally permissive liveness-enforcing supervisor can always be obtained, its computation is very expensive.As stated, reachability graph analysis [17] is an important technique for deadlock controll; however, it always suffers from a state explosion problem. This is due to the fact that it is impossible to achieve the enumeration of all or a part of reachable markings in practice. Based on this technique, an optimal or suboptimal supervisor with highly behavioral permissiveness can always be obtained for a small system. In [18], Uzam and Zhou develop an iterative approach to design an optimal or suboptimal supervisor. This method is easy to use if the reachable space of a system is small but cannot guarantee the optimality of the supervisor.The theory of regions developed in [19] can be used as an effective approach to find an optimal liveness-enforcing Petri net supervisor if such a supervisor exists. However, it suffers from computational and structural complexity problems. The work in [20] proposes a vector covering approach to improve the computation efficiency of the work in [19].A siphon-based deadlock prevention policy is a typical application of structure analysis techniques of Petri nets. Although not optimal and even overly restrictive, this approach is computationally tractable and allows its supervisor to be reused when a system experiences new job instances [2, 21–28]. Recent effective and computationally efficient deadlock prevention policies are proposed by Piroddi et al. in [29, 30].Nowadays, the distribution of resources in an FMS may change frequently and dynamically due to fluctuant customer demands. Such changes mean different production or service requirements for the providers. Therefore, the supervisory control system has to reconfigure rapidly in response to the changes in its physical entity and the control specifications by modifying or adjusting its plant model and controller. Once the resource configurations are changed, the supervisors are updated accordingly. Recently, the study in [31] proposes a novel deadlock prevention policy based on reconfiguration of Petri net supervisors. The method presented in [31] is near optimal, but its performance needs to be further improved.Motivated by existing work, this paper presents an effective and computationally efficient method to design nearly optimal control places based on resources reallocation and supervisor reconfiguration. The main idea of the method is stated as follows.(i)
The proposed method works on the premise of a class of ordinary Petri net(N,M0) with N=(P0∪PA∪PR,T,F), where for all  i∈{1,2,…,n}, P0=∪i=1n{pi0} is called a set of idle process places, PA=∪i=1nPAi is called a set of activity places, and PR=∪i=1nPRi is called a set of resource places.(ii)
We first reallocate the initial marking of each resource place in(N,M0) to be one, obtaining a model (N1,M1) where N1=N, for all  p∈P0∪PA, M1(p)=M0(p), and forallr∈PR, M1(r)=1. In this case, we can design monitors by using the theory of regions and find a controlled system (N1c,M1c) for (N1,M1) with N1c=(P0∪PA∪PR∪PV,T1c,F1c), where forallp∈P0∪PA∪PR, M1c(p)=M1(p), for all  i∈{1,2,…,n}, PV=∪i=1nPVi is called a set of control places.(iii)
Then, the markings of the resource places in(N1c,M1c) are restored to their original ones, obtaining a controlled system (Nc,Mc) with Nc=N1c, where for all  p∈P0∪PA∪PR, Mc(p)=M0(p), and for all  v∈PV, Mc(v)=M1c(v).(iv)
Without changing the structure of the controlled system(Nc,Mc), we compute the markings of the monitors gradually. Finally, we decide a marking for each monitor such that forallp∈P0∪PA∪PR, Mc(p)=M0(p), and for all  v∈PV, Mc(v) makes the controlled system (Nc,Mc) live, where (Nc,Mc) is a controlled system for (N,M0) with Nc=N1c.The rest of this paper is organized as follows. Section2 briefly reviews preliminaries used in this paper. Section 3 formulates the considered problem through a motivation example. Section 4 presents a deadlock prevention policy that is formalized by Algorithm 2. Two FMS examples are given in Section 5, showing the superiority of the proposed method. A comparison between the proposed method and a previous one is made in Section 6. Finally, Section 7 concludes this paper.


## 2. Preliminaries

### 2.1. Basics of Petri Nets

A generalized Petri net (structure) [7] is a four-tuple N=(P,T,F,W), where P and T are finite, nonempty, and disjoint sets. P is a set of places and T is a set of transitions with P∪T≠∅ and P∩T=∅. F⊆(P×T)∪(T×P) is called a flow relation of a net, represented by arcs with arrows from places to transitions or from transitions to places. W:(P×T)∪(T×P)→ℕ is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T and ℕ={0,1,2,…}. If W(x,y)=1, for all  (x,y)∈F, the net is called an ordinary Petri net.A transitiont∈T is enabled at a marking M if for all  p∈•t, M(p)≥W(p,t). This fact is denoted as M[t〉. Firing it yields a new marking M′ such that forallp∈P, M′(p)=M(p)-W(p,t)+W(t,p), as denoted by M[t〉M′. M′ is called an immediately reachable marking from M. Marking M′′ is said to be reachable from M if there exists a sequence of transitions σ=t0t1…tn and markings M1,M2,…, and Mn such that M[t0〉M1[t1〉M2…Mn[tn〉M′′ holds. The set of markings reachable from M in N is called the reachability set of Petri net (N,M) and denoted as R(N,M). [N] is called the incidence matrix of N. It is a |P|×|T| integer matrix with [N](p,t)=W(t,p)-W(p,t).AP-vector is a column vector I:P→ℤ index by P and a T-vector is a column vector J:T→ℤ index by T, where ℤ is the set of integers. I is a P-invariant if I≠0 and IT[N]=0T. A P-invariant I is said to be a P-semiflow if every element of I is nonnegative.A nonempty setS⊆P is a siphon if •S⊆S•. A siphon is minimal if there is no siphon contained in it as a proper subset. A minimal siphon that does not contain the support of any P-invariant is called a strict minimal siphon (SMS).A siphonS is said to be max-marked at M∈R(N,M0) if ∃p∈S such that M(p)≥maxp•, where maxp•=max{W(p,t)∣t∈p•}. S is max-controlled if it is max-marked at any reachable marking. (N,M0) satisfies the maximal controlled-siphon (cs) property if each minimal siphon of N is max-controlled [33]. Siphon S is called uncontrolled in (N,M0) if ∃M∈R(N,M0), for all  t∈S•, t is dead at M.A markingM of a Petri net N is a mapping from P to ℕ. M(p) denotes the number of tokens in place p. A place p is marked at a marking M if M(p)>0. A subnet S⊆P is marked at a marking M if at least one place in S is marked at M. The sum of tokens of all places in S is denoted by M(S), that is, M(S)=∑p∈S‍M(p). S is said to be empty at M if M(S)=0. (N,M0) is called a net system or marked net and M0 is called an initial marking of N.Markings and vectors are usually represented via using a multiset. As a result, vectorM is denoted by ∑p∈P‍M(p)p. For instance, a marking that puts two tokens in place p1 and three tokens in place p3 only in a net with P={p1-p6} is denoted as M=2p1+3p3 instead of (2,0,3,0,0,0)T.Letx∈P∪T be a node of net N=(P,T,F,W). The preset of x is defined as •x={y∈P∪T∣(y,x)∈F}. While the postset of x is defined as x•={y∈P∪T∣(x,y)∈F}. Furthermore, we have x••=∪y∈x•y• and ••x=∪y∈•x•y.Given a Petri net(N,M0), t∈T is live at M0 if for all  M∈R(N,M0), ∃M′∈R(N,M), M′[t〉. (N,M0) is live if forallt∈T, t is live at M0. (N,M0) is dead at M0 if ∄t∈T, M0[t〉. (N,M0) is deadlock-free if for all  M∈R(N,M0), ∃t∈T, M[t〉.With respect to the concepts of supervisors and controlled systems, the reader is referred to [14]. A supervisor is said to be optimal if its resulting controlled system covers all safe states of a plant and every reachable state in the controlled system is a safe state of the plant. Such a controlled system is said to be optimal.


### 2.2. M-Nets

This paper considers a class of manufacturing-oriented Petri nets, M-nets [31]. It is a generalization of the existing net classes that can model FMS. In this paper, we just focus on the research of ordinary M-nets, a type of M-nets.Definition 1.
An M-net denoted by(N,M0) satisfies the following statements:(1)
N=◯i=1nNi=(P0∪PA∪PR,T,F,W) is composed of n nets N1,N2,…, and Nn, where for all  i∈ℕn, ℕn={1,2,…,n}, Ni=({pi0}∪PAi∪PRi,Ti,Fi,Wi) is called a subnet of N.(2)
P0=∪i=1n{pi0} is called a set of idle process places with pi0≠pj0, for all  i,j∈ℕn, i≠j; PA=∪i=1nPAi is called a set of activity places with PAi∩PAj=∅, for all i,j∈ℕn, i≠j; and PR=∪i=1nPRi is called a set of activity places.(3)
For alli,j∈ℕn, i≠j, Ti∩Tj=∅.(4)
For allr∈PR, it is associated with a minimal P-semiflow Ir such that Ir(r)=1, for all  p∈PA, Ir(p)≥0, and forallp∈P0, Ir(p)=0.(5)
For allp∈PA, p is associated with a minimal P-semiflow Ip, where ∥Ip∥⊆PA.(6)
(Ni,M0i) is quasi-live, bounded, and conservative.(7)
(Ni′,M0i′) with Ni′=({pi0}∪PAi,Ti,Fi′,Wi′) is live, bounded, and reversible, where Ni′ is the resulting net from removing resource places in (Ni,M0i).(8)
Let(Ni,M0i)(i=1,2) be two subnets with Ni=({pi0}∪PAi∪PRi,Ti,Fi,Wi). Their composition denoted by (N12,M12) with N12=N1∘N2=(P120∪PA12∪PR12,T12,F12,W12) is defined as follows:
(i)
P120={p10}∪{p20}={p10,p20}, PA12=PA1∪PA2, and PR12=PR1∪PR2,(ii)
T12=T1∪T2,(iii)
F12=F1∪F2,(iv)
forallf∈F1, W(f)=W1(f) and forallf∈F2, W(f)=W2(f),(v)
for allp∈{p10}∪PA1, M12(p)=M01(p); forallp∈{p20}∪PA2, M12(p)=M02(p); forallr∈PR1∖PR2, M12(r)=M01(r); forallr∈PR2∖PR1, M12(r)=M02(r); and for all  r∈PR1∩PR2, M12(r)=max{M01(r),M02(r)}.(9)
The netN resulting from the composition of n subnets N1,N2,…, and Nn is defined as follows: if n=1, then N=N1; if n>1, then N=◯i=1nNi=(◯i=1n-1Ni)∘Nn.(10)
Forallp∈P0, M0(p)>0; forallp∈PA, M0(p)=0; and forallr∈PR, M0(r)≥max{Ir(p)∣p∈∥Ir∥}. Such a marking is said to be an admissible initial marking.(11)
An uncontrolled siphon in(N,M0) contains at least one resource place and one activity place but no idle process place.(12)
(N,M0) is live if no siphon is uncontrolled.(13)
If(N,M0) is not live, liveness can be enforced by adding monitors whose addition leads to a controlled system.(14)
Let(Nc,M0c) be a controlled system for (N,M0). (Nc,M0c) is live if it is ordinary and no siphon is unmarked. (Nc,M0c) is live if it is generalized and satisfies the controlled-siphon (cs) property.(15)
LetPV be the set of monitors in (Nc,M0c). For all  v∈PV, there exists a minimal P-semiflow Iv such that Iv(v)=1 and for all  p∈∥Iv∥∖{v}, p∈PA.
In order to make Definition1 clear, an example is given in Appendix A. It is easy to find that M-nets are more general than almost all manufacturing-oriented Petri nets, for example, the ones in [2, 22, 24, 32].


### 2.3. An MIP-Based Deadlock Detection Method

In this paper, by using a technique that is called the mixed integer programming (MIP) approach proposed in [32], siphons that cause deadlocks can be detected. Let (N,M0) be an ordinary net with N=(P,T,F) and S the maximal empty siphon at M, that is, forallp∉S, M(p)>0. Finding S in N is the solution of a mixed integer programming problem. For all  p∉S, let vp=1 and for all  t∉S•, let zt=1.It is easy to see that anyp with vp=1 and any t with zt=1 are removed from the net. Since S is a siphon, we have that for all  t∈p•, vp=0 implies zt=0 and for all  p∈t•, zt=1 implies the truth of vp=1. This leads to
(1)zt≥∑p∈•t‍vp-|•t|+1,∀t∈T(2)vp≥zt,∀(t,p)∈F(3)vp,zt∈{0,1}.For a structurally bounded net, we have(4)vp≥M(p)SB(p),∀p∈P,
where SB(p)=max{M(p)∣M=M0+[N]Y,M≥0,Y≥0} is the structural bound of place p. Therefore, the maximal siphon unmarked at a given marking M can be determined by the following MIP problem and there exist siphons unmarked at M iff GMIP<|P| [32]:
(5)GMIP=Minimize∑p∈P‍vp
s.t. constraints (1)–(4) and
(6)M=M0+[N]Y,M≥0,Y≥0,
where [N] is the incidence matrix and M and Y are vectors of real numbers. Relation M=M0+[N]Y is usually called the state equation.Theorem 2 (see [32]).
Let(N,M0) be a Petri net with N=(P,T,F). There is no emptiable siphon if GMIP=|P|.Corollary 3.
Let(N,M0) be an ordinary M-net with N=(P,T,F). There is no emptiable siphon if GMIP=|P|.The proof of Corollary3 is given in Appendix B.Theorem 4.
Let(N,M0) be an ordinary M-net with N=(P,T,F). Then (N,M0) is live if GMIP=|P|.The proof of Theorem4 is given in Appendix B.


## 2.1. Basics of Petri Nets

A generalized Petri net (structure) [7] is a four-tuple N=(P,T,F,W), where P and T are finite, nonempty, and disjoint sets. P is a set of places and T is a set of transitions with P∪T≠∅ and P∩T=∅. F⊆(P×T)∪(T×P) is called a flow relation of a net, represented by arcs with arrows from places to transitions or from transitions to places. W:(P×T)∪(T×P)→ℕ is a mapping that assigns a weight to an arc: W(x,y)>0 if (x,y)∈F, and W(x,y)=0 otherwise, where x,y∈P∪T and ℕ={0,1,2,…}. If W(x,y)=1, for all  (x,y)∈F, the net is called an ordinary Petri net.A transitiont∈T is enabled at a marking M if for all  p∈•t, M(p)≥W(p,t). This fact is denoted as M[t〉. Firing it yields a new marking M′ such that forallp∈P, M′(p)=M(p)-W(p,t)+W(t,p), as denoted by M[t〉M′. M′ is called an immediately reachable marking from M. Marking M′′ is said to be reachable from M if there exists a sequence of transitions σ=t0t1…tn and markings M1,M2,…, and Mn such that M[t0〉M1[t1〉M2…Mn[tn〉M′′ holds. The set of markings reachable from M in N is called the reachability set of Petri net (N,M) and denoted as R(N,M). [N] is called the incidence matrix of N. It is a |P|×|T| integer matrix with [N](p,t)=W(t,p)-W(p,t).AP-vector is a column vector I:P→ℤ index by P and a T-vector is a column vector J:T→ℤ index by T, where ℤ is the set of integers. I is a P-invariant if I≠0 and IT[N]=0T. A P-invariant I is said to be a P-semiflow if every element of I is nonnegative.A nonempty setS⊆P is a siphon if •S⊆S•. A siphon is minimal if there is no siphon contained in it as a proper subset. A minimal siphon that does not contain the support of any P-invariant is called a strict minimal siphon (SMS).A siphonS is said to be max-marked at M∈R(N,M0) if ∃p∈S such that M(p)≥maxp•, where maxp•=max{W(p,t)∣t∈p•}. S is max-controlled if it is max-marked at any reachable marking. (N,M0) satisfies the maximal controlled-siphon (cs) property if each minimal siphon of N is max-controlled [33]. Siphon S is called uncontrolled in (N,M0) if ∃M∈R(N,M0), for all  t∈S•, t is dead at M.A markingM of a Petri net N is a mapping from P to ℕ. M(p) denotes the number of tokens in place p. A place p is marked at a marking M if M(p)>0. A subnet S⊆P is marked at a marking M if at least one place in S is marked at M. The sum of tokens of all places in S is denoted by M(S), that is, M(S)=∑p∈S‍M(p). S is said to be empty at M if M(S)=0. (N,M0) is called a net system or marked net and M0 is called an initial marking of N.Markings and vectors are usually represented via using a multiset. As a result, vectorM is denoted by ∑p∈P‍M(p)p. For instance, a marking that puts two tokens in place p1 and three tokens in place p3 only in a net with P={p1-p6} is denoted as M=2p1+3p3 instead of (2,0,3,0,0,0)T.Letx∈P∪T be a node of net N=(P,T,F,W). The preset of x is defined as •x={y∈P∪T∣(y,x)∈F}. While the postset of x is defined as x•={y∈P∪T∣(x,y)∈F}. Furthermore, we have x••=∪y∈x•y• and ••x=∪y∈•x•y.Given a Petri net(N,M0), t∈T is live at M0 if for all  M∈R(N,M0), ∃M′∈R(N,M), M′[t〉. (N,M0) is live if forallt∈T, t is live at M0. (N,M0) is dead at M0 if ∄t∈T, M0[t〉. (N,M0) is deadlock-free if for all  M∈R(N,M0), ∃t∈T, M[t〉.With respect to the concepts of supervisors and controlled systems, the reader is referred to [14]. A supervisor is said to be optimal if its resulting controlled system covers all safe states of a plant and every reachable state in the controlled system is a safe state of the plant. Such a controlled system is said to be optimal.


## 2.2. M-Nets

This paper considers a class of manufacturing-oriented Petri nets, M-nets [31]. It is a generalization of the existing net classes that can model FMS. In this paper, we just focus on the research of ordinary M-nets, a type of M-nets.Definition 1.
An M-net denoted by(N,M0) satisfies the following statements:(1)
N=◯i=1nNi=(P0∪PA∪PR,T,F,W) is composed of n nets N1,N2,…, and Nn, where for all  i∈ℕn, ℕn={1,2,…,n}, Ni=({pi0}∪PAi∪PRi,Ti,Fi,Wi) is called a subnet of N.(2)
P0=∪i=1n{pi0} is called a set of idle process places with pi0≠pj0, for all  i,j∈ℕn, i≠j; PA=∪i=1nPAi is called a set of activity places with PAi∩PAj=∅, for all i,j∈ℕn, i≠j; and PR=∪i=1nPRi is called a set of activity places.(3)
For alli,j∈ℕn, i≠j, Ti∩Tj=∅.(4)
For allr∈PR, it is associated with a minimal P-semiflow Ir such that Ir(r)=1, for all  p∈PA, Ir(p)≥0, and forallp∈P0, Ir(p)=0.(5)
For allp∈PA, p is associated with a minimal P-semiflow Ip, where ∥Ip∥⊆PA.(6)
(Ni,M0i) is quasi-live, bounded, and conservative.(7)
(Ni′,M0i′) with Ni′=({pi0}∪PAi,Ti,Fi′,Wi′) is live, bounded, and reversible, where Ni′ is the resulting net from removing resource places in (Ni,M0i).(8)
Let(Ni,M0i)(i=1,2) be two subnets with Ni=({pi0}∪PAi∪PRi,Ti,Fi,Wi). Their composition denoted by (N12,M12) with N12=N1∘N2=(P120∪PA12∪PR12,T12,F12,W12) is defined as follows:
(i)
P120={p10}∪{p20}={p10,p20}, PA12=PA1∪PA2, and PR12=PR1∪PR2,(ii)
T12=T1∪T2,(iii)
F12=F1∪F2,(iv)
forallf∈F1, W(f)=W1(f) and forallf∈F2, W(f)=W2(f),(v)
for allp∈{p10}∪PA1, M12(p)=M01(p); forallp∈{p20}∪PA2, M12(p)=M02(p); forallr∈PR1∖PR2, M12(r)=M01(r); forallr∈PR2∖PR1, M12(r)=M02(r); and for all  r∈PR1∩PR2, M12(r)=max{M01(r),M02(r)}.(9)
The netN resulting from the composition of n subnets N1,N2,…, and Nn is defined as follows: if n=1, then N=N1; if n>1, then N=◯i=1nNi=(◯i=1n-1Ni)∘Nn.(10)
Forallp∈P0, M0(p)>0; forallp∈PA, M0(p)=0; and forallr∈PR, M0(r)≥max{Ir(p)∣p∈∥Ir∥}. Such a marking is said to be an admissible initial marking.(11)
An uncontrolled siphon in(N,M0) contains at least one resource place and one activity place but no idle process place.(12)
(N,M0) is live if no siphon is uncontrolled.(13)
If(N,M0) is not live, liveness can be enforced by adding monitors whose addition leads to a controlled system.(14)
Let(Nc,M0c) be a controlled system for (N,M0). (Nc,M0c) is live if it is ordinary and no siphon is unmarked. (Nc,M0c) is live if it is generalized and satisfies the controlled-siphon (cs) property.(15)
LetPV be the set of monitors in (Nc,M0c). For all  v∈PV, there exists a minimal P-semiflow Iv such that Iv(v)=1 and for all  p∈∥Iv∥∖{v}, p∈PA.
In order to make Definition1 clear, an example is given in Appendix A. It is easy to find that M-nets are more general than almost all manufacturing-oriented Petri nets, for example, the ones in [2, 22, 24, 32].


## 2.3. An MIP-Based Deadlock Detection Method

In this paper, by using a technique that is called the mixed integer programming (MIP) approach proposed in [32], siphons that cause deadlocks can be detected. Let (N,M0) be an ordinary net with N=(P,T,F) and S the maximal empty siphon at M, that is, forallp∉S, M(p)>0. Finding S in N is the solution of a mixed integer programming problem. For all  p∉S, let vp=1 and for all  t∉S•, let zt=1.It is easy to see that anyp with vp=1 and any t with zt=1 are removed from the net. Since S is a siphon, we have that for all  t∈p•, vp=0 implies zt=0 and for all  p∈t•, zt=1 implies the truth of vp=1. This leads to
(1)zt≥∑p∈•t‍vp-|•t|+1,∀t∈T(2)vp≥zt,∀(t,p)∈F(3)vp,zt∈{0,1}.For a structurally bounded net, we have(4)vp≥M(p)SB(p),∀p∈P,
where SB(p)=max{M(p)∣M=M0+[N]Y,M≥0,Y≥0} is the structural bound of place p. Therefore, the maximal siphon unmarked at a given marking M can be determined by the following MIP problem and there exist siphons unmarked at M iff GMIP<|P| [32]:
(5)GMIP=Minimize∑p∈P‍vp
s.t. constraints (1)–(4) and
(6)M=M0+[N]Y,M≥0,Y≥0,
where [N] is the incidence matrix and M and Y are vectors of real numbers. Relation M=M0+[N]Y is usually called the state equation.Theorem 2 (see [32]).
Let(N,M0) be a Petri net with N=(P,T,F). There is no emptiable siphon if GMIP=|P|.Corollary 3.
Let(N,M0) be an ordinary M-net with N=(P,T,F). There is no emptiable siphon if GMIP=|P|.The proof of Corollary3 is given in Appendix B.Theorem 4.
Let(N,M0) be an ordinary M-net with N=(P,T,F). Then (N,M0) is live if GMIP=|P|.The proof of Theorem4 is given in Appendix B.


## 3. Structure Design of a Petri Net Supervisor

Now, let us go briefly through the processes by using the theory of regions to design a supervisor for a Petri net model. One first needs to generate its reachability graph. Then, the set of marking/transition separation instances should be found, whose number is in theory exponential with respect to the net size and the initial marking. Finally, for each instance, a monitor should be found by solving a linear programming problem in which the number of constraints is approximately equal to that of nodes in the reachability graph. For such a method, the size of a reachability graph is rather sensitive to the size and the initial marking of a net. These facts make it infeasible for the theory of regions to be applied to real-world problems.With the purpose of formulating the proposed method even more clearly, we design Algorithm1 to find a controlled system (N1c,M1c) for (N1,M1) that can be obtained by reallocating the marking of each resource place in (N,M0) to be one, with N1c=(P0∪PA∪PR∪PV,T,F1c,W1c).Algorithm 1:Structure design of a controlled system for (N,M0).
Input: an ordinary M-net (N,M0) with N=(P0∪PA∪PR,T,F,W)
Output: (N1c,M1c)
begin {
N
1
:
=
N
∀
p
∈
P
0
∪
P
A, M1(p):=M0(p)
∀
r
∈
P
R, M1(r):=1
if  {there exists an optimal controlled system for (N1,M1)}   then
design a controlled system(N1c,M1c) for (N1,M1) by the theory of regions
else
design a controlled system(N1c,M1c) for (N1,M1) by the method in [18]
end if
∀
p
∈
P
0
∪
P
A
∪
P
R, M1c(p):=M1(p)
N
1
c
:
=
(
P
0
∪
P
A
∪
P
R
∪
P
V
,
T
,
F
1
c
,
W
1
c
)
if   {(N1c,M1c) is an ordinary controlled system}   then
output(N1c,M1c)
else
exit and stop the algorithm
end if
output(N1c,M1c)
} end of the algorithmAlgorithm 2:Controlled system design for (N,M0).
Input: an ordinary M-net (N,M0) with N=(P0∪PA∪PR,T,F,W)
Output: controlled system (Nc,Mc)
begin {
design a controlled system(N1c,M1c) for (N1,M1) by Algorithm 1, then
N
c
:
=
N
1
c
∀
v
∈
P
V, Mc(v):=M1c(v)
∀
p
∈
P
0
∪
P
A
∪
P
R, Mc(p):=M0(p)
P
i
:
=
(
•
•
H
(
v
i
)
)
∩
P
R, i∈{1,2,…,n}
∀
p
∈
P
i, Mc(vi):=∑p∈Pi‍M(p)-1, i∈{1,2,…,n}
μ
→
:
=
[
M
c
(
v
1
)
,
M
c
(
v
2
)
,
…
,
M
c
(
v
j
)
,
…
,
M
c
(
v
n
)
]
T, j∈{1,2,…,n}
While   {μ→ makes (Nc,Mc) not live, which can be decided by the MIP-based deadlock detection
method in [32]}  do
for  j=1 to n  do
Mc(vj)--;
end for
end while
l
→
:
=
μ
→      /*l→ denotes the marking vector
[
M
l
c
(
v
1
)
,
M
l
c
(
v
2
)
,
…
,
M
l
c
(
v
j
)
,
…
,
M
l
c
(
v
n
)
]
T
,
j
∈
{
1,2
,
…
,
n
}
*
/
for   j=1 to n   do
Mc(vj)++;
end for
h
→
:
=
μ
→      /*h→ denotes the marking vector
[
M
h
c
(
v
1
)
,
M
h
c
(
v
2
)
,
…
,
M
h
c
(
v
j
)
,
…
,
M
h
c
(
v
n
)
]
T
,
j
∈
{
1,2
,
…
,
n
}
*
/
while (1) do
for   j=1 to n   do
if   (Mhc(vj)==Mlc(vj))
Mhc(vj):=Mc(vj);
else
Mhc(vj)--;
break;
end if
end for
if   {h→ makes (Nc,Mc) live, which can be decided by the MIP-based deadlock detection
method in [32]}do
break;
end if
end while
μ
→
:
=
h
→
∀
p
∈
P
0
∪
P
A
∪
P
R, Mc(p):=M0(p)
N
c
:
=
N
1
c
output(Nc,Mc)
} end of the algorithmProposition 5.
Let(N1c,M1c) be the resulting net from adding monitors to an ordinary M-net (N1,M1) by using Algorithm 1. Then (N1c,M1c) is ordinary and live.The proof of Proposition5 is given in Appendix B.In order to illustrate Algorithm1, consider a small example from [31]. Figures 1(a) and 1(b) show an ordinary M-net (N,M0) and its corresponding reachability graph with eight reachable states, respectively. Now by applying Algorithm 1 to (N,M0), a plant mode (N1,M1) can be obtained, as shown in Figure 1(c). It has the same topology structure as (N,M0) in Figure 1(a) but its resource places have a small initial marking with M(p5)=1 and M(p6)=1. Its reachability graph is shown in Figure 1(d) with five reachable states. Figure 1(e) shows a controlled system (N1c,M1c) for (N1,M1), which can be obtained by using the theory of regions [15, 19].(a) A plant model(N,M0), (b) the reachability graph of (N,M0), (c) a modified model (N1,M1), (d) the reachability graph of (N1,M1), and (e) a controlled system (N1c,M1c) for (N1,M1).
(a)
(b)
(c)
(d)
(e)The principal objective of reallocating the marking of each resource place to be one is that it is more tractable by using the theory of regions to design a controlled system for(N1,M1) than that for (N,M0). We can see that the reachable states of (N1,M1) are five that are less than that of (N,M0) whose reachable states are eight. One can image the heavy computation if the theory of regions is applied to such a net shown in Figure 1(a), with an initial marking M0=100p1+80p2+50p3 having more than 8×104 states. Algorithm 1 considers (N1,M1), as shown in Figure 1(c), which has five reachable markings only. Therefore, it is easier for us to find a supervisor for (N1,M1) than that for (N,M0). Then, a controlled system (N1c,M1c) for (N1,M1) can be obtained by using the theory of regions, as shown in Figure 1(e).In this section, we propose a method to realize the structure design of a controlled system which can be obtained by Algorithm1. That is to say, the structure of the supervisors has been found, based on which a deadlock prevention policy will be presented in the next section.


## 4. Deadlock Prevention Policy

This section proposes a deadlock prevention policy that can be carried out through the following Algorithm2. In the previous section, a controlled system (N1c,M1c) can be obtained for (N1,M1) with N1c=(P0∪PA∪PR∪PV,T,F1c,W1c) and N1=(P0∪PA∪PR,T,F,W). In this section, we can find a controlled system (Nc,Mc) for (N,M0) by restoring the markings of the resource places in (N1c,M1c) to their original ones and then computing a marking for each monitor. That is to say, even if the initial marking of the plant model changes, the structure of the controlled system obtained previously can be reused. This implies that we only need to compute the marking of each monitor in the controlled system when the markings of the resource places change.Now, let us consider the relationship between the activity places, the monitors, and the resource places. First, we can find that the tokens that will flow into the activity places can not be greater than that of their holding resource places. Similarly, the tokens in the monitor should be less than that of the resource places which the monitor's activity places hold. That can be expressed by  the following: for alli∈{1,2,…,n}, vi∈PV, H(vi) is the set of the activity places  controlled by  vi, and for all  p∈H(vi), p is called the monitor's activity place. Pi=(••H(vi))∩PR, for all  p∈Pi, Mc(vi)≤∑p∈Pi‍M(p)-1. Then, an upper limit value for each marking with respect to the monitors v1,v2,…, and vn can be obtained. Finally, we decide a marking for each monitor such that it makes the controlled system live which can be decided by the MIP-based deadlock detection method in [32]. Consequently, Algorithm 2 is designed to formulate the proposed method. Let (Nc,Mc) denote a controlled system for (N,M0), which has the same net structure as (N1c,M1c) with Nc=(P0∪PA∪PR∪PV,T,F1c,W1c).Theorem 6.
Let(Nc,Mc) be a controlled system for an ordinary M-net (N,M0) by using Algorithm 2. Then (Nc,Mc) is live.The proof of Theorem6 is given in Appendix B.We briefly explain Algorithm2 as follows. First, a controlled system (N1c,M1c) for (N1,M1) can be obtained by using Algorithm 1 in the previous section. Next, the markings of the resource places in (N1c,M1c) are restored to their original ones. Then, we compute an upper limit value for the marking of each monitor and denote it by μ→:=[Mc(v1),Mc(v2),…,Mc(vj),…,Mc(vn)]T, j∈{1,2,…,n}. If the marking vector μ→ makes the controlled system live, we stop the algorithm and the marking vector μ→ is the result we want to obtain. If the marking vector μ→ makes the controlled system not live, then each marking in μ→ decreases by one; repeat this step until it makes the controlled system live and denote it by l→=[Mlc(v1),Mlc(v2),…,Mlc(vj),…,Mlc(vn)]T,j∈{1,2,…,n}. Then, each marking in l→ increases by one that can be denoted by h→=[Mhc(v1),Mhc(v2),…,Mlh(vj),…,Mhc(vn)]T,j∈{1,2,…,n}. That is to say, we obtain a new higher limit value vector h→ and a lower limit value vector l→ for the marking of each monitor. Finally, by using Algorithm 2, we decide a marking for each monitor such that for all  p∈P0∪PA∪PR, Mc(p)=M0(p), and forallv∈PV, Mc(v) makes the controlled system live which can be decided by the MIP-based deadlock detection method proposed in [32].For example, a controlled system(Nc,Mc) can be obtained for the net in Figure 1(a) by utilizing Algorithm 2, as shown in Figure 2. In the previous section, a controlled system (N1c,M1c) has been obtained, as shown in Figure 1(e). Then, we can find a controlled system (Nc,Mc) for (N,M0) by restoring the markings of the resource places in (N1c,M1c) to their original ones with M(p5)=2 and M(p6)=1, and then an upper limit value for the marking of the monitor pc can be computed. We can find that the activity places controlled by pc are p2 and p3. Therefore, H(pc)={p2,p3}, {p5,p6}=(••H(pc))∩PR. Then, we can obtain that M(pc)≤M(p5)+M(p6)-1 implies that M(pc)≤2. As shown in Figure 2, the controlled system is live with M(pc)=2, which can be decided by the MIP-based deadlock detection method in [32]. Consequently, the marking M(pc)=2 is the one that we want to obtain.Figure 2
A controlled system(Nc,Mc) for (N,M0).Given a plant model(N,M0), we reallocate the marking of each resource place to be one, obtaining a net model (N1,M1). By using Algorithm 1, a controlled system (N1c,M1c) for (N1,M1) can be obtained. Then, the markings of the resource places in (N1c,M1c) are restored to their original ones. On the premise of not changing the structure of the controlled system, we compute the marking of each monitor by Algorithm 2. That is to say, even if the initial markings of the plant model change, the structure of the controlled system obtained previously can be reused. This implies that we only need to compute the marking of each monitor in the controlled system without changing the supervisor's structure. Figure 3 shows the flowchart of the proposed deadlock control strategy.Figure 3
Flowchart of the deadlock prevention policy.


## 5. Experimental Studies

In order to show the advantage of the proposed method, this section provides two typical examples that are taken from [31]. The computational results indicate that the proposed deadlock prevention policy is nearly optimal and superior to the one in [31].An FMS consists of two robots R1 and R2 and three machines M1–M3. Its model is shown in Figure4(a). It is an ordinary M-net, where p1 and p10 are idle places, p11-p15 are resource places, and the others are activity places. As shown in Figure 4(b), (N1c,M1c) is the controlled system for the net (N1,M1) with the initial marking of each resource place being one.(a) An ordinary M-net(N,M0) and (b) controlled system (N1c,M1c).
(a)
(b)To illustrate Algorithm2, consider (N1c,M1c) shown in Figure 4(b). The activity places p4 and p9 are controlled by v1 and hold the resource places p12 and p14, respectively. That can be expressed by the following: H(v1)={p4,p9}, {p12,p14}=(••H(v1))∩{p11,p12,p13,p14,p15}. Based on Algorithm 2, the marking of the monitor v1 should be less than the total markings of the resource places p12 and p14. That can be expressed by an inequality:
(7)M(v1)≤(M(p12)+M(p14))-1.
Much the same can be applied to monitors v2 and v3. The inequalities can be obtained as follows:
(8)M(v2)≤(M(p12)+M(p13))-1,M(v3)≤(M(p13)+M(p14))-1.Now, the net under initial marking4p1+4p10+2p11+2p12+2p13+2p14+2p15 is used to demonstrate the proposed method. From (7) and (8), the results can be obtained as follows:
(9)M(v1)≤2+2-1=3,M(v2)≤2+2-1=3,M(v3)≤2+2-1=3.Therefore, we can obtain an upper limit value for the marking of each monitor and denote it byμ→=[Mc(v1),Mc(v2),Mc(v3)]T=[3,3,3]T. Then, we find that the marking vector μ→ makes the controlled system live which can be decided by the MIP-based deadlock detection method proposed in [32]. Therefore, the marking vector [Mc(v1),Mc(v2),Mc(v3)]T=[3,3,3]T is the result we want to obtain. It can be verified that the controlled model in Figure 4(b) under initial marking 4p1+4p10+2p11+2p12+2p13+2p14+2p15 with M(v1)=3,M(v2)=3, and M(v3)=3 obtained by the proposed method is live with 1032 reachable states. Compared the proposed method with the one in [31] with 941 states, it can be clearly seen that we have achieved a better result, what we call a near-optimal result.Compared with the method in [31], the superiority of the proposed policy can be verified. Table 1 shows the permissive behavior of the controlled systems under different initial markings, where the markings of the monitors are decided by Algorithm 2. In this table, Bp is the number of reachable states of (N,M0), BL represents the number of states that an optimal controlled system for (N,M0) has, Bc indicates the number of states of the controlled system (Nc,Mc), and Bc/BL implies the optimality degree. In order to make a comparative analysis of the proposed method and the one in [31], let Li’s denotes the results in [31]. For economy of space, the detailed computational steps are omitted. From this table, we conclude that the proposed method for this example is near optimal and superior to the one in [31].Table 1
Behavior permissiveness of the proposed deadlock prevention policy.
p
1
,
p
10
,
p
11
–
p
15
v
1
,
v
2
,
v
3
/
L
i
B
p
B
L
B
c
/
Li
′
s
B
c
/
B
L
/
Li
′
s
(
1)3,3,1,1,1,1,1
[
1,1
,
1
]
T
/
[
1,1
,
1
]
T
73
54
54/54
100
%
/
100
%
(
2
)
4,4
,
2,2
,
2,2
,
2
[
3,3
,
3
]
T
/
[
3,3
,
2
]
T
1093
1047
1032/941
94.419
%
/
89.876
%
(
3
)
5,5
,
3,3
,
3,3
,
3
[
5,5
,
5
]
T
/
[
5,5
,
3
]
T
5767
5705
5680/5151
99.562
%
/
90.290
%
(
4
)
6,6
,
4,4
,
4,4
,
4
[
7,7
,
7
]
T
/
[
7,7
,
3
]
T
20324
20263
20234/18517
99.857
%
/
91.383
%
(
5
)
7,7
,
5,5
,
5,5
,
5
[
9,9
,
9
]
T
/
[
9,9
,
5
]
T
57450
57390
57360/52995
99.948
%
/
92.342
%
(
6
)
8,8
,
6,6
,
6,6
,
6
[
11,11,11
]
T
/
[
11,11,6
]
T
140703
140643
140613/13100
99.977
%
/
93.144
%
(
7
)
9,9
,
7,7
,
7,7
,
7
[
13,13,13
]
T
/
[
13,13,7
]
T
310783
310723
310693/292363
99.990
%
/
93.770
%
(
8
)
10,10,8
,
8,8
,
8,8
[
15,15,15
]
T
/
[
15,15,8
]
T
634173
634113
634083/597853
99.995
%
/
94.282
%
(
9
)
11,11,9
,
9,9
,
9,9
[
17,17,17
]
T
/
[
17,17,9
]
T
1214679
1214619
1214589/1150189
99.998
%
/
94.695
%


(
10
)
12,12,10,10,10
,
10,10
[
19,19,19
]
T
/
[
19,19,10
]
T
2208445
2208385
2208355/2098887
99.990
%
/
95.042
%The second FMS is shown in Figure5(a). It has two robots R1 and R2, each of which can hold one product at a time. The cell also contains four machines M1–M4, and each of them can hold one part. Parts enter FMS through two automatic loading buffers I1 and I2 and leave it through two unloading ones O1 and O2. The robots deal with the movements of parts. Two part types P1 and P2 are produced. Their respective production routes are shown in Figure 5(b).(a) Layout of an FMS and (b) routes of part types P1 and P2.
(a)
(b)Figure6(a) shows its net model that is an ordinary M-net in which P0={p1,p8}, PR={p15,p16,p17,p18,p19}, and the others are activity places. The controlled system of such a plant model is shown in Figure 6(b), which can be obtained by the theory of regions [15].(a) Petri net model of an FMS and (b) structure of the controlled system.
(a)
(b)Consider the model shown in Figure6(b). The monitor v1 controls the activity places p3, p11, and p12. The set of their corresponding resource places is {p15,p18}. Therefore, the markings of the monitor v1 should be less than the total markings of the resource places p15 and p18. That can be expressed by an inequality:
(10)M(v1)≤(M(p15)+M(p18))-1.The same situation can be applied to monitorsv2, v3, v4, v5, and v6. The inequalities can be obtained as follows:
(11)M(v2)≤(M(p14)+M(p15)+M(p18))-1,M(v3)≤(M(p16)+M(p17)+M(p18)+M(p19))-1,M(v4)≤(M(p15)+M(p17)+M(p18)+M(p19))-1M(v5)≤(M(p15)+M(p16)+M(p17)+M(p18)+M(p19))-1,M(v6)≤(M(p14)+M(p15)+M(p16)+M(p17)+M(p18)+M(p19))-1.By exploiting Algorithm2, the markings for the monitors can be obtained, as shown in Table 2. For economy of space, the computational steps for the system are not shown in detail. Table 2 shows the performance of the controlled systems under different initial markings. From this table, it is verified that the proposed method for this example is nearly optimal and may even achieve optimality. It is obviously superior to the method in [31].Table 2
Behavior permissiveness of the proposed deadlock prevention policy.
p
1
,
p
8
,
p
14
–
p
19
v
1
,
v
2
,
v
3
,
v
4
,
v
5
,
v
6
B
p
B
L
B
c
/
Li
′
s
B
c
/
B
L
/
Li
′
s
(
1
)
3,3
,
1,3
,
1,2
,
3,2
[
5,6
,
7,9
,
10,11
]
T
2946
2945
2945/2842
100
%
/
96.500
%
(
2
)
3,4
,
1,4
,
1,1
,
3,3
[
6,7
,
7,10,11,12
]
T
5235
5234
5234/4730
100
%
/
90.388
%
(
3
)
4,4
,
1,5
,
1,1
,
2,4
[
6,7
,
7,12,13,14
]
T
6877
6868
6868/6861
100
%
/
99.898
%
(
4
)
4,5
,
1,5
,
2,2
,
4,5
[
8,9
,
12,15,17,18
]
T
31759
31758
37758/29129
100
%
/
91.722
%
(
5
)
5,5
,
1,6
,
1,1
,
3,5
[
8,9
,
9,14,15,16
]
T
28243
28233
28233/28177
100
%
/
99.802
%
(
6
)
5,6
,
1,7
,
1,6
,
3,1
[
9,10,10,16,17,18
]
T
24448
24438
24438/24384
100
%
/
99.779
%
(
7
)
6,6
,
3,7
,
3,3
,
5,7
[
11,14,17,21,24,27
]
T
298725
298724
298724/290187
100
%
/
97.142
%


## 6.   Comparision of Computational Efficiency

The deadlock prevention method proposed in [31] needs to calculate all SMS in the controlled system and infer algebraic inequalities. An improved method of avoiding this problem is presented in this paper, which is simple and practicable. To illustrate the application of the proposed method, two FMS examples are used in this paper. A comparison between the proposed method and the one in [31] is shown in Tables 1 and 2. The superiority of the proposed one is obvious. For a class of FMS considering resource allocation, this paper proposes a deadlock prevention policy by resources reallocation and supervisor reconfiguration, which can make a good tradeoff between optimality and computational tractability for a class of ordinary Petri nets.


## 7.   Conclusion

The deadlock prevention policy is a static strategy that imposes restrictions on the interactions among resources and processes such that resource requests that may lead to deadlocks are prevented. Behavioral permissiveness is very important in designing a liveness-enforcing supervisor for a system to be controlled. An optimal liveness-enforcing supervisor can lead to high utilization of system resources. This paper proposes a deadlock prevention policy by resources reallocation and supervisor reconfiguration. Given a plant model, we first reallocate the marking of each resource place to be one, and then find a controlled system by using Algorithm1. Next, the markings of the resource places in the controlled system are restored to their original ones. Without changing the structure of the controlled system, we compute the markings of the monitors. Finally, we decide a marking for each monitor such that it makes the controlled system live which can be realized by Algorithms 2 proposed in this paper. For a fixed net structure with different initial marking, the theory of regions is used once only. That is to say, the supervisory control system can be reconfigured rapidly in response to the changes in the initial markings of the plant model. Two FMS examples are used to illustrate the application of the proposed method and show its superior efficiency.However, the proposed method suffers from the computational complexity problem due to the theory of regions. In theory, it suffers from the exponential complexity. Future efforts will be made to a near-optimal supervisor with low computational costs. In addition, the proposed method is applicable to ordinary M-nets only. Therefore, our future work will extend this method to more general classes of Petri nets, for example, the ones in [34, 35].



---

*Source: 315894-2013-04-03.xml*