Control Places of the Net (N_{1H}, M_{0})

## 1. Introduction

While competing for a finite number of resources in a flexible manufacturing system (FMS), e.g., robots and machines, each part has a particular operational flow that determines the order in which such resources are needed. However, such competition for shared resources by concurrent job processes can leadto a system deadlock. It occurs when parts are blocked waiting for shared resources held by others that will never be granted. Its related blocking phenomena often incur unnecessary overhead cost, e.g.,a long downtime and low utilization rate of some critical and expensive resources, possibly leading to a catastrophic outcome in some highly automated FMS. Therefore, an efficient deadlock control policy must be developed to ensure that deadlocks do not occur. Having received considerable attention in literature, deadlock is normally prevented by using an offlinecomputational mechanism to control the resource requestsin order to avert deadlocks. Fanti and Zhou^{1} introduce three fundamental methods (i.e. prevention, detection and avoidance) to solve the deadlock problems.Deadlock prevention aims to impose system constraints to prevent a deadlock. Importantly, deadlock prevention algorithms do notrequire run-time costs since the problems are solved in system design and planning stages. This study belongs to the deadlock prevention field.

Petri nets (PN)^{2} have been recognized as one of the most powerful formal methods for modeling FMS.The reason is that they are well suited to represent such FMS characteristics as precedence relations, concurrence, conflict and synchronization. Their analysis methods used for deadlock prevention in FMS include structural analysis and reachability graphs. Deadlock prevention and avoidance schemes have been developed for controlling FMS^{3-8} by using the former. In particular, deadlock prevention problems are solved using the concept of siphons^{3-6}. Li & Zhou propose an elementary siphon control policy (ESCP) to reduce the redundant siphons to obtain structurally simpler controllers^{9-10}. However, they cannot obtain optimal ones. Reachability graph methods are used to obtain the live system behavior^{11-14}. Without confining to a certain class of FMS, they can provide an optimal deadlock controller by adopting the theory of regions^{15}. The theory is originally developed for a transition system (TS). A state-based representation with arcs labeled with symbols from an alphabet of events in a TS can be mapped into a PN model. For an elementary TS (ETS) there exists a PN with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original TS.

Uzam^{12} follows the theory of regions^{15} to define a deadlock-zone (DZ) and deadlock-free zone (DFZ) for preventing deadlocks. Hence, the concept of DZ and DFZ is used to solve ESSPs. An optimal controller can be obtained but suffers from many redundant control places. Ghaffari*et al.*^{13} propose a unique interpretation of the theory of regions and define *M*_{F} (*forbidden marking*), *M*_{D} (*dangerous marking*), *M*_{L} (*legal marking*), and (the set of *marking*/*transition-separation instances* or MTSI). An optimal PN controller synthesis method for FMS is proposed based on both MTSI and the theory of regions. Unfortunately, redundant MTSIs cannot be entirely avoided for large FMS cases.

To reduce redundant control places, Li *et al.*^{16} adopt a combined algorithm based on siphon control and the theory of regions^{15}. Its advantage is that the number of separation instances is significantly reduced after some sets of elementary siphons of a system are controlled. However, it fails to determine all sets of MTSIs and its application seems limited to some special nets only.

Uzam and Zhou propose an iterative control policy of liveness enforcement for PNs based on the theory of regions^{17}. Less computation is required to obtain a controller. However, as indicated by Li et al^{18}, it requires the repeated calculation of reachability graphs. Piroddi *et al.* propose a combined selective siphons and critical markings in a reachability graph algorithm to obtain optimal controllers via iterations^{19}. They successfully identify the critical uncontrolled siphons and control them to make a deadlock-prone PN live. However, their algorithm also requires the repeated calculation of reachability graphs. Eventually, the controllers are not ordinary (i.e. they contain weighted arcs).

This work in this chapter aims to develop a computationally more efficient optimal deadlock control policy by using the theory of regions. It focuses on dead markings in a reachability graph. The concept of a crucial MTSI (CMTSI) is proposed to synthesize optimal controllers. The proposed method can reduce the computational burden of the MTSI method^{13} and redundant control places^{12-13}. The experimental results indicate that it is the most efficient policy amongall known ones^{12-13, 16}that can design optimal controllers.

Section 2 presents the basic definitions and properties of PNs and the theory of regions. Section 3 describes the proposed policy. Section 4 presents the experimental results. Section 5 gives the comparisons. Conclusions are made in Section 6.

## 2. Preliminaries

### 2.1. Petri nets^{2}

A Petri net (*PN*) is a 5-tuple *N =* (*P, T, F, W, M*_{0})where *P* is a finite set of places; *T* is a finite set of transitions, with *P* *T* ≠ *P* *T* =*F* *P*×*T*) (*T*×*P*) is the set of all directed arcs, *W*: (*P*×*T*) (*T*×*P*)→*N*is the weight function where *N*= { 0, 1, 2, …}, and *M*_{0}: *P* → *N*is the initial marking. A *PN* is said to be ordinary, denoted as (*P, T, F*), if *f* *F*, *W*(*f*) = 1. [*N*]^{+}(*p, t*) *= W*(*p, t*)is the input function that means the multiplicity of a directed arc from *p* to *t* if (*p*, *t*)*F*. [*N*]^{-}(*p, t*) *= W*(*t, p*)is the output function that means the multiplicity of a directed arc from *t* to *p* if (*t*, *p*)*F*. 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 PN structure *(P, T, F, W)* is denoted by *N*. A PN with a given initial marking is denoted by (*N, M*_{0}).

A PN is said to be pure if no place is both input and output places of the same transition. The so-called incidence matrix [*N*] of a pure Petri nets is defined as [*N*] = [*N*]^{-} [*N*]^{+}. A transition *t* is said to be enabled at marking *M*, if *p*•*t, M*(*p**) W*(p, t), or p is marked with at least W(p, t) tokens, as denoted by M[t>. A transition may fire if it is enabled. In an ordinary net, it is enabled iff p•t, M(p) 1. Firing t at M gives a new marking Msuch that pP, M(p) = M(p) – W(p, t) + W(t, p). It is denoted as M[t>M. M indicates the number of tokens in each place, which means the current state of the modeled system. When M_{n}can be reached from M_{0}by firing a sequence of transitions σ, this process is denoted by M [σ >M_{n} and satisfies the state equationM_{n} = M + [N]_{0}is denoted by R(N,M_{0}). Additionally, a definition of linearized reachability set (using the state equation) is defined as R(N,M_{0})={M: M = M_{0} +[N](•_{0}) - R(N,M_{0}) are called spurious ones (with respect to the state equation)^{20}. They may also be the solutions of the state equation but not reachable markings. In this work, ones just focus on the reachable markings.

A transition t is said to be live if for any MR(N,M_{0}), there exists a sequence of transitions whose firing leads to M’ that enables t.A PNis said to be live if all the transitions are live. A PNcontains a deadlock if there is a marking MR(N,M_{0}) at which no transition is enabled. Such a marking is called a dead marking.Deadlock situations are as a result of inappropriate resource allocation policies or exhaustive use of some or all resources. Liveness of a PN means that for each marking MR(N,M_{0}) reachable from M_{0}, it is finally possible to fire t, tT through some firing sequence.(N, M_{0})is said to be reversible, if MR(N,M_{0}), M_{0}R(N,M).Thus, in a reversible net it is always possible to go back to initial marking (state) M_{0}.A marking Mis said to be a home state, if for each marking MR(N,M_{0}), Mis reachable from M.Reversibility is a special case of the home state property, i.e. if the home state M= M_{0}, then the net is reversible.

### 2.2. Theory of regions and synthesis problem^{13}

The theory of regions is proposed for the synthesis of pure nets given a finite TS^{15}, which can be adopted to synthesize the liveness-enforcing net supervisor (LENS) for a plant model^{12-13}. For convenience, our method follows the interpretation of the theory of regions in^{13}.

First of all, let T be a set of transitions and G be a finite directed graph whose arcs are labeled by transitions in T. Assume that there exists a node v in G such that there exists a path from it to any node. The objective of the theory of regions is to find a pure PN (N, M_{0}), having T as its set of transitions and characterized by its incidence matrix [N](p, t) and its initial marking M_{0}, such that its reachability graph is G and the marking of node v is M_{0}. In the following, M denotes both a reachable marking and its corresponding node in G.

Consider any marking M in net (N, M_{0}). Because (N, M_{0}) is pure, Mcan be fully characterized by its corresponding incidence vector [N](p, )

M(p) = M(p) + [N](p, )

Consider now any oriented cycle of a reachability graph. Applying the state equation to a node in and summing them up give the following cycle equation:

where is an oriented cycle of G,

According to the definition of G, there exists an oriented path _{M}from M_{0} to M. Applying (1) along the path leads to M(p) = M_{0}(p) + [N](p,)_{0} to M. Under the cycle equations, the product [N](p,)

The above equation is called the reachability condition. Notably, (3) is necessary but not sufficient. Hence, spurious markings are beyond this paper.

It is clear that the cycle equations and reachability conditions hold for any place p. For each pair (M, t) such that M is a reachable marking of G and t is a transition not enabled at M, t should be prevented from happening by some place p. Since the net is pure, t is prevented from happening at M by a place p iff

The above equation (4) is called the event separation condition of (M, t). The set of all possible pairs (M, t) where M is a reachable marking and t is not enabled at M is called the setof event separation instances or marking/transitions-separation instances (MTSI)^{13}. Symbol is used to represent the set of MTSI in this paper. To solve the control problem, is identified. The corresponding control places can then be found to prevent the transitions of the controlled system from firing in order to keep all legal markings only.

## 3. Controller synthesis method

In this section, an efficient controller synthesis method is developed based on the theory of regions. Please note that all transitions of the PN models are regarded as controllable ones.

### 3.1. Supervisory control problem

It is assumed that a deadlock-prone PN model contains at least a dead marking in its reachability graph at which no transition is enabled. Its reachability graph contains dead and live zones. Consequently, this study attempts to propose a method to prevent the controlled systems from entering a dead zone/marking.

A dead marking cannot enable any transition and thus cannot go to any other markings. We can formally define the dead marking M_{D} as follows.

Definition 1: The set of dead markingsM_{D}= {MR(N, M_{0})| at M, no transition is enabled}.

Definition 2: A zone consisting of all dead markings is called a dead zone, denoted by Z_{D}.

Once a marking enters a dead zone, the system is dead. If there is no dead zone in a reachability graph, the system is called a live one.

The goal of the work is to control a deadlock-prone system such that it is live. All markings of a reachability graph can be divided into three groups: legal markings (M_{L}), quasi-dead markings (M_{Q}), and dead markings (M_{D}).

Definition 3: The set of quasi-dead markings M_{Q} = {MR(N, M_{0})| M must eventually evolve to a dead one regardless of transition firing sequences}.

Definition 4: A zone consisting of all quasi-dead markings is called a quasi-dead zone, denoted by Z_{Q}.

Definition 5: A zone consisting of all quasi-dead and dead markings, i.e., Z_{I} = Z_{D} Z_{Q}, is called an illegal zone.

Markings except quasi-dead and dead markings are legal ones. Once a legal marking is enforced into the illegal zone, the net will eventually become deadlock.

Definition 6: A zone consisting of all legal markings is called a legal zone,i.e., Z_{L} = R(N, M_{0}) - Z_{I}.

Ramadge and Wonham show that a system has the maximally permissive behavior if the system behavior equals Z_{L}^{21}. In other words, one must remove all the markings in illegal zone (i.e. quasi-dead and dead markings) from R(N, M_{0}) if one wants to obtain the maximally permissive behavior. Ghaffari et al. propose the MTSI method to achieve their deadlock prevention based on the theory of regions^{13}. However, the set of all MTSIs from the reachability graph must be identified. As a result, we can conclude that their method is computationally inefficient. A more efficient method is thus needed as described next.

### 3.2. Crucial MTSI (CMTSI)

Two types of CMTSIs are defined as follows.

Definition 7: Type I CMTSI: = {(M, t)|M M_{L}, t T, and MM_{D}, MM_{L}, and tT such that M [t>M and M [t>M}. Denote the set of all the dead markings related to as M'_{D}, i.e., M_{D} = {MM_{D} | (M, t) such that M [t M}. They are called type I deadlocks.

Definition 7 explains a legal marking that can evolve into a dead or legal zone as shown in Figure 1 through a single transition’s firing. For those dead markings that are not type I deadlocks, we need to introduce Type II CMTSI and deadlocks.

Definition 8: A zone consisting of all type I deadlocks (M'_{D}) is called type I dead zone, denoted by Z.

Definition 9: _{k} is defined as a transition firing sequence starting in a quasi-dead marking (M_{Q}) and ending in a deadlock marking in M_{D} where i = |σ_{k}| is the number of transitions in σ_{k}, called its length. Denote a firing sequence with the shortest length (i.e., smallest i) from any quasi-dead marking to M' as σ^{*}(M') given M'M_{D} –M'_{D}.

Definition 10: Type II CMTSI : = {(M, t)|MM_{L}, t T, and MM_{Q}, MM_{L}, MM_{D}, tT, and a firing sequence σ=σ^{*}(M) from Mto Msuch that M [t>M, M [t>M, and M [σ>M}. The set of dead markings associated with Type II CMTSI is denoted as M"_{D}, called type II deadlocks. M_{D} = {MM_{D} | (M, t) , MM_{Q} and a firing sequence from M to Msuch that M[tMand σ=σ^{*}(M)}.

Definition 11: A zone consisting of all type II deadlocks (M_{D}) is called type II dead zone, Z.

A Type II CMTSI contains a legal marking that cannot reach a dead marking with one single transition’s firing as shown in Figure 2. Given a dead marking in M"_{D},the shortest transition firing sequence needs to be found. The main reason is based on the fact that, for a dead marking, the length of the firing sequence from the initial marking to CMTSI is the longest path than those from the initial marking to MTSIs. Hence, the solutions of MTSIs will be totally covered by the solution of CMTSI. For example, as shown in Figure 3, σ^{*}is the shorter path since |σ^{*}| < |σ| (i.e. |σ^{*}| =1 and |σ| = 3).

Remark 1: A dead marking is always with its corresponding CMTSI. As a result, the corresponding CMTSI is of either Type I or II. Type I may be viewed as a special case of Type II CMTSI by defining ^{*} = 0 (no need to enter Z_{Q} but directly to Z_{D}). Type I CMTSI will be processed first in our proposed method. In the following, Theorems 1-3 will help readers to understand how to choose CMTSIs, which are with the same firing sequence of legal markings, from Types I and II.

Theorem 1: If a dead marking MM'_{D} is associated with two different CMTSIs, only one CMTSI needs to be controlled.

Proof: Assume that a dead marking M is with both CMTSIs {M_{i}, t_{m}} and {M_{j}, t_{n}} as shown in Figure 4. According to the state equation, M_{i} + [N](•t_{m}) = M_{j} + [N](•t_{n}) = M. Arranging the above equation, M_{0} + [N](•_{m}) = M_{0} + [N](•_{n}). According to (4), realizing either CMTSI, e.g., {M_{i}, t_{m}}, leads to M_{0} + [N](•_{m}) -1, which in turn implies M_{0} + [N](•_{n}) -1 and vice versa. Hence, only one CMTSI needs to be controlled.

Remark 2: Based on Theorem 1, if a dead marking MM'_{D} is associated with more than two CMTSIs, only one of them needs to be controlled.

Theorem 2: If a dead marking MM_{D}, is associated with two CMTSIs whose markings can reach a same quasi-dead marking M' via their respective single transition’s firing, only one CMTSI needs to be controlled.

Proof: Assume that a dead marking M is associated with Type II CMTSIs {M_{p}, t_{r}} and {M_{q}, t_{s}}. M_{p} and M_{q} reaches a quasi-dead markings M' via t_{r} and t_{s}’s firing, respectively as shown in Figure 5.

According to the state equation, M_{p} + [N](•t_{r}) + [N](•_{q} + [N](•t_{s}) + [N](•_{p} + [N](•t_{r}) =M_{q} + [N](•t_{s}). According to (4), realizing either CMTSI, e.g., {M_{p}, t_{r}}, leads to M_{0} + [N](•_{r}) -1, which in turn implies M_{0} + [N](•_{s}) -1 and vice versa. Hence, only one CMTSI needs to be controlled.

Theorem 3: A dead marking MM_{D}, is associated with two CMTSIs whose markings can reach two different quasi-dead markings M_{p} and M_{q} via two different single transitions’ firing. Both need to be controlled if [N](•

Proof: Assume that a dead marking M is associated with both Type II CMTSIs {M_{p}, t_{r}} and {M_{q}, t_{s}}. M_{p} and M_{q} reach two different quasi-dead markings M_{p} and M_{q} via t_{r} and t_{s}’s firing, respectively as shown in Figure 6.

According to the state equation, M_{p} + [N](•t_{r}) + [N](•_{q} + [N](•t_{s}) + [N](•_{D}. Arranging the above equation, M_{p} + [N](•_{q} + [N](•_{p}is not equal to M_{q}. And also according to the definition of the event separation condition equation, the first set of CMTSI {M_{p}, t_{r}} leads to the first event separation condition equation is M_{0} + [N](•_{r}) -1; and the second set of CMTSI {M_{q}, t_{s}} leads to the another event separation condition equation is M_{0} + [N](•_{s}) -1. Hence, one can infer that M_{p} and M_{q} are two different quasi-dead markings if [N](•

Definition 12: A legal marking MM_{L} can be led to a quasi-dead markingM_{q} via a single transition firing. M_{q}must eventually evolve to a dead one M_{d} (i.e. M_{d}M_{D}) after a sequence _{n} = t_{1}t_{2}…t_{n} fires. Denote the set of all the markings on the path from M_{q} to M_{d} as M_{q-d}.

Remark 3: Based on Theorem 3, both CMTSIs still need to be controlled even if M_{P}= M_{q} for the case shown in Figure 7.

Control places are then found after CMTSIs. They are used to keep all markings of the controlled system within the legal zone.

Theorem 4: ()

Here, Figure 8(a) taken from existing literatures^{22} is used todemonstrate how to identify two types of CMTSIs from its reachability graph (i.e. Figure 8(b)). Assume that all transitions of PN models are immediately in this case. Therefore, one can easy identify there are two dead markings M'_{D}(i.e. M_{2}) and M"_{D} (i.e. M_{15}) and four quasi-dead markings (i.e. M_{11}, M_{12}, M_{13} and M_{14}). Additionally, the markings M_{0}, M_{1}, M_{3}-M_{10} are the legal markings. Based on the mentioned above, there are two sets of CTMSIs in the reachability graph system due to the two dead markings in the system. As a result, one can infer that {M_{0}, t_{2}} belongs to type I CMTSI and {M_{7}, t_{1}} belongs to type II. In this Petri net system model, there are only one type I CMTSI and only one type II.

### 3.3. Procedure of deadlock prevention policy

Next, quasi-dead, dead, and legal markings are identified. Based on^{12-13}, the maximally permissive behavior means all of legal markings (M_{L}) and the number of reachability condition equations equals |M_{L}|. Additionally, all CMTSIs can be obtained such that the legal markings do not proceed into the illegal zone. The proposed deadlock prevention algorithm is constructed as Figure 9.

Theorem 5: The proposed deadlock prevention policy is more efficient than the method proposed by Ghaffari et al.^{13}

Proof: The theory of regions is used to prevent the system deadlocks by both our deadlock prevention policy and the conventional one. All MTSIs can be controlled by the two control policies. Since () , the use of CMTSI can more efficiently handle the synthesis problem than that of MTSI^{13}.

## 4. Experimentalresults

Two FMS examples are used to evaluate our deadlock prevention policy^{12-23}.

Example I: An FMS is shown in Figure 1012. This PN is a system of simple sequential processes with resources (S^{3}PR), denoted by (N_{1}, M_{0}). To do our deadlock prevention policy, R(N_{1}, M_{0}) of the PN system can be constructed as shown in Figure 11.

Two dead markings (i.e. M_{7} and M_{12}) can then be identified. Next, '_{1} = {(M_{3}, t_{5})} and '_{2} = {(M_{15}, t_{1})} are obtained. The event separation condition equations can be obtained through them as follows.

M_{7}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{1})+ [N](p_{c}, t_{2}) + [N](p_{c}, t_{5}) -1 (5)

M_{12}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{1})+2[N](p_{c}, t_{5}) +[N](p_{c}, t_{6}) -1 (6)

Two cycle equations are as follows.

[N](p_{c}, t_{1})+[N](p_{c}, t_{2}) + [N](p_{c}, t_{3})+ [N](p_{c}, t_{4}) = 0 (7)

[N](p_{c}, t_{5})+[N](p_{c}, t_{6}) + [N](p_{c}, t_{7}) + [N](p_{c}, t_{8}) = 0 (8)

After listing all reachability conditions, all legal markings can be determined. In detail, M_{0}-M_{6}, M_{8}, and M_{13}-M_{19} are legal. Hence, the following reachability conditions are obtained.

M_{0}(p_{c}) 0 (9)

M_{1}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{1}) 0 (10)

M_{2}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{1}) + [N](p_{c}, t_{2}) 0 (11)

M_{3}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{1})+ [N](p_{c}, t_{2}) 0 (12)

M_{4}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{1})+ [N](p_{c}, t_{2}) + [N](p_{c}, t_{3}) 0 (13)

M_{5}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{1})+ 2[N](p_{c}, t_{2}) + [N](p_{c}, t_{3}) 0 (14)

M_{6}(p_{c}) = M_{0}(p_{c}) + 3[N](p_{c}, t_{1})+ 2[N](p_{c}, t_{2}) + [N](p_{c}, t_{3}) 0 (15)

M_{8}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{1})+ [N](p_{c}, t_{2}) + [N](p_{c}, t_{3}) 0 (16)

M_{13}(p_{c}) = M_{0}(p_{c})+ [N](p_{c}, t_{5}) 0 (17)

M_{14}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{5}) + [N](p_{c}, t_{6}) 0 (18)

M_{15}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{5}) + [N](p_{c}, t_{6}) 0 (19)

M_{16}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{5}) + [N](p_{c}, t_{6}) + [N](p_{c}, t_{7}) 0 (20)

M_{17}(p_{c}) = M_{0}(p_{c}) + 2[N](p_{c}, t_{5}) + 2[N](p_{c}, t_{6}) + [N](p_{c}, t_{7}) 0 (21)

M_{18}(p_{c}) = M_{0}(p_{c}) + 3[N](p_{c}, t_{5}) + 2[N](p_{c}, t_{6}) + [N](p_{c}, t_{7}) 0 (22)

M_{19}(p_{c}) = M_{0}(p_{c}) + [N](p_{c}, t_{5}) + [N](p_{c}, t_{6}) + [N](p_{c}, t_{7}) 0 (23)

Furthermore, two optimal control places C_{P1} and C_{P2} can be obtained when (5) and (7)-(23) are solved. Their detailed information is: M_{0}(C_{P1}) = 1, t_{1}= t_{5}= -1, t_{2}= t_{6}= 1, t_{3}= t_{4}= t_{7}= t_{8} = 0; and M_{0}(C_{P2})=1, t_{2}= t_{5} = -1, t_{3} = t_{6}= 1, t_{1}= t_{4}= t_{7}= t_{8} = 0. By the same way, using (6) and (7)-(23),one can find two optimalcontrol places, C_{p3} and C_{p4}. M_{0}(C_{P3}) = 1, t_{1}= t_{6}= -1, t_{2}= t_{7} = 1, t_{3} = t_{4}= t_{5}= t_{8} = 0; and M_{0}(C_{P4}) = 1, t_{1} = t_{5}= -1, t_{2} = t_{6} = 1, t_{3}= t_{4}= t_{7} = t_{8}= 0. Notably, C_{P1} and C_{P4} are the same. Therefore, a redundant control place (C_{P4}) can be removed. As a result, the system net can be controlled with the three control places C_{P1}, C_{P2} and C_{P3}. The optimally controlled system net(N_{1H}, M_{0}) is obtained as shown in Table 1.

It is worthy to emphasize that the three control places are obtained by using two CMTSIs and 36 equations under our control policy. However, six MTSIs/ESSPs and 108 equations have to be solved in two existing literatures^{12, 24}.

Additional Control Places | M_{0}(Cpi) | (Cp) | (Cp) |

Cp_{1} | 1 | t_{2}, t_{6} | t_{1}, t_{5} |

Cp_{2} | 1 | t_{3}, t_{6} | t_{2}, t_{5} |

Cp_{3} | 1 | t_{2}, t_{7} | t_{1}, t_{6} |

Example II: This example is taken from^{23} and is used in^{12, 16, 24}. Here, the PN model of the system, denoted as (N_{2}, M_{0}), is shown in Figure 12.

To prevent deadlock, 282 reachable markings (M_{1} to M_{282}) are identified according to the software INA^{25}. 16 dead markings M_{9}, M_{19}, M_{70}, M_{71}, M_{76}, M_{77}, M_{78}, M_{83}, M_{84}, M_{94}, M_{99}, M_{100}, M_{105}, M_{106}, M_{112}, and M_{113} are then located. Next, 61 quasi-dead markings M_{6}, M_{7}, M_{8}, M_{14}, M_{15}, M_{16}, M_{17}, M_{18}, M_{25}, M_{48}, M_{66}, M_{67}, M_{68}, M_{69}, M_{72}, M_{73}, M_{74}, M_{75}, M_{79}, M_{80}, M_{81}, M_{82}, M_{87}, M_{101}, M_{102}, M_{103}, M_{104}, M_{108}, M_{109}, M_{110}, M_{111}, M_{124}, M_{130}, M_{135}, M_{136}, M_{141}, M_{142}, M_{143}, M_{150}, M_{162}, M_{198}, M_{203}, M_{204}, M_{210}, M_{250}, M_{251}, M_{257}, M_{258}, M_{259}, M_{260}, M_{261}, M_{262}, M_{263}, M_{265}, M_{269}, M_{270}, M_{272}, M_{273}, M_{274}, M_{277}, and M_{278} are found based on Definition 3 in this paper. Hence, the number of legal markings (i.e. 288 – (16 + 61) = 205) can be determined. Type I and II CMTSIs can be obtained as shown in Table 2. Notice that {(M_{56}, t_{9})} in M_{77} is a redundant one.

M(D | 'C | M(D | C |

M_{9} | {(M_{65}, t_{1})} | M_{19} | {(M_{56}, t_{1})} |

{(M_{56}, t_{9})} | |||

M_{70} | {(M_{43}, t_{9})} | M_{76} | {(M_{65}, t_{11})} |

M_{71} | {(M_{51}, t_{9})} | M_{77} | {(M_{56}, t_{9})} |

{(M_{56}, t_{11})} | |||

M_{78} | {(M_{171}, t_{9})} | M_{83} | {(M_{128}, t_{11})} |

M_{94} | {(M_{93}, t_{1})} | M_{84} | {(M_{60}, t_{9})} |

{(M_{60}, t_{11})} | |||

M_{99} | {(M_{98}, t_{1})} | M_{105} | {(M_{93}, t_{11})} |

M_{100} | {(M_{98}, t_{4})} | M_{106} | {(M_{98}, t_{11})} |

M_{112} | {(M_{122}, t_{11})} | ||

M_{113} | {(M_{96}, t_{11})} |

M(D | Event Separation Condition Equations |

M_{9} | M_{0} + 3t_{1} + t_{2} + t_{3} + 2t_{9 }+ t_{10} -1 |

M_{70} | M_{0} + 3t_{1} + t_{2} + 2t_{3} + 2t_{4}+ t_{6 }+ 2t_{9}+ t_{10 }-1 |

M_{0} + 3t_{1} + 2t_{2} + t_{3} + t_{4} + t_{5} + t_{6} + 2t_{9 }+ t_{10} -1 | |

M_{71} | M_{0} + 3t_{1} + t_{2} + 2t_{3} + t_{4} + t_{5} + t_{6} + 2t_{9 }+ t_{10} -1 |

M_{0} + 3t_{1} + 2t_{2} + t_{3} + 2t_{5} + t_{6} + 2t_{9 }+ t_{10 }-1 | |

M_{78} | M_{0} + 2t_{1} + t_{2} + t_{3} + t_{4} + t_{5} + t_{6} + 2t_{9} + t_{10 }-1 |

M_{0} + 2t_{1} + 2t_{2} + 2t_{5} + t_{6} + 2t_{9} + t_{10 }-1 | |

M_{0} + 2t_{1} + 2t_{3} + 2t_{4} + t_{6} + 2t_{9} + t_{10} -1 | |

M_{94} | M_{0} + 2t_{1} + t_{3} + 3t_{9} + 2t_{10} + t_{11} + t_{12} -1 |

M_{99} | M_{0} + 3t_{1} + 2t_{3} + t_{4} + t_{6} + 3t_{9} + 2t_{10}+ t_{11} + t_{12} -1 |

M_{0} + 3t_{1} + t_{2} + t_{3} + t_{5} + t_{6} + 3t_{9} + 2t_{10}+ t_{11} + t_{12} -1 |

Tables 3-4 show the event separation condition equations based on 18 CMTSIs. Here, the procedure of our method is introduced as follows. Due to the space limitation, we use only one example (i.e. dead marking M_{9}) to illustrate how to prevent legal markings from leading to dead one M_{9} by using a CMTSI. To do so, '_{C1} = {(M_{65}, t_{1})} can be located due to M_{9}. The event separation condition equation can then be identified as follows.

M_{9}(C_{P1}) = M_{0}(C_{P1}) + 3t_{1} + t_{2} + t_{3} + 2t_{9} + t_{10} -1 (24)

Next, three different cycle equations are:

t_{1} + t_{2} + t_{5} + t_{6} + t_{7} + t_{8} = 0 (25)

t_{1} + t_{3} + t_{4} + t_{6} + t_{7} + t_{8} = 0 (26)

t_{9} + t_{10} + t_{11} + t_{12} + t_{13} + t_{14} = 0 (27)

Finally, 205 reachability condition equations can be listed. They represent the sequence of all legal markings from the initial one. Moreover, control place C_{P1} can be computed, i.e., M_{0} (C_{P1}) = 2, C_{P1}= {t_{6}, t_{13}}, and C_{P1} = {t_{1}, t_{11}}. Similarly, other control places are obtained as shown in Tables 5-6.

M(D | Event Separation Condition Equations |

M_{19} | M_{0} + 4t_{1} + t_{2} + 2t_{3} + t_{4} + t_{6} + t_{9} + t_{10} -1 |

M_{0} + 4t_{1} + 2t_{2} + t_{3} + t_{5} + t_{6} + t_{9} + t_{10 }-1 | |

M_{0} + 3t_{1} + t_{2} + 2t_{3} + t_{4} + t_{6} + 2t_{9} + t_{10} -1 | |

M_{0} + 3t_{1} + 2t_{2} + 2t_{3} + t_{5} + t_{6} + 2t_{9} + t_{10 }-1 | |

M_{76} | M_{0} + 2t_{1} + t_{2} + t_{3} + 2t_{9} + t_{10} + t_{11} -1 |

M_{77} | M_{0} + 3t_{1} +t_{2} + 2t_{3} + t_{4}+t_{6}+t_{9}+t_{10}+t_{11} -1 |

M_{0} + 3t_{1} + 2t_{2} + t_{3}+t_{5} + t_{6}+t_{9}+t_{10}+t_{11} -1 | |

M_{83} | M_{0} + t_{1} + t_{2} + 2t_{9} + t_{10} + t_{11} -1 |

M_{84} | M_{0} + 2t_{1} + t_{2} + t_{3} + t_{4} + t_{6} + t_{9} + t_{10} + t_{11 }-1 |

M_{0} + 2t_{1} + 2t_{2} + t_{5} + t_{6} + t_{9} + t_{10} + t_{11} -1 | |

M_{0} + 3t_{1} +t_{2} + 2t_{3} + t_{4}+t_{6}+2t_{9}+t_{10} -1 | |

M_{0} + 3t_{1} + 2t_{2} + t_{3}+t_{5 }+ t_{6}+2t_{9}+t_{10} -1 | |

M_{105} | M_{0} + t_{1} + t_{3} + 3t_{9} + 2t_{10 }+ 2t_{11 }+ t_{12} -1 |

M_{106} | M_{0} + 2t_{1} + 2t_{3} + t_{4} + t_{6} + 3t_{9} + 2t_{10}+ 2t_{11 }+ t_{12 }-1 |

M_{0} + 2t_{1} + t_{2} + t_{3 }+ t_{5}+ t_{6} + 3t_{9} + 2t_{10 }+ 2t_{11}+ t_{12} -1 | |

M_{112} | M_{0} + 3t_{9} + 2t_{10} + 2t_{11}+ t_{12} -1 |

M_{113} | M_{0}+ t_{1} + t_{3}+ t_{4 }+ t_{6 }+ 3t_{9}+ 2t_{10 }+ 2t_{11 }+ t_{12 }-1 |

M_{0} + t_{1} + t_{2}+ t_{5 }+ t_{6}+ 3t_{9} + 2t_{10 }+ 2t_{11}+ t_{12 }-1 |

M(D | '_{C} | M_{0}(Cpi) | (Cpi) | (Cpi) |

M_{9} | {(M_{65}, t_{1})} | 2 | t_{6}, t_{13} | t_{1}, t_{11} |

M_{70} | {(M_{43}, t_{9})} | 3 | t_{6}, t_{11} | t_{2}, t_{4}, t_{9} |

3 | t_{5}, t_{7}, t_{11} | t_{2}, t_{6}, t_{9} | ||

3 | t_{7}, t_{11} | t_{4}, t_{5}, t_{9} | ||

M_{71} | {(M_{51}, t_{9})} | 3 | t_{7}, t_{11} | t_{4}, t_{5}, t_{9} |

M_{78} | {(M_{171}, t_{9})} | 3 | t_{7}, t_{11} | t_{4}, t_{5}, t_{9} |

M_{94} | {(M_{93}, t_{1})} | 2 | t_{6}, t_{13} | t_{1}, t_{11} |

M_{99} | {(M_{98}, t_{1})} | 4 | t_{7}, t_{11} | t_{1}, t_{9} |

M_{100} | {(M_{98}, t_{4})} | 3 | t_{7}, t_{11} | t_{4}, t5, t_{9} |

Finally, the controlled net is obtained by adding the six control places as shown in Table 7. It is live and maximally permissive with 205 reachable markings. However, 59 ESSPs and nine control places are required in^{12}. It hints that 59 sets of inequalities are needed in ^{12}, while only 18 sets of inequalities suffice using our algorithm. Hence, our policy is more efficient than that in ^{12}.

Li et al. solve this problem by using elementary siphons controlled policy (ESCP) and the theory of region ^{16}. A two-stage deadlock prevention method is used. First, ESCP is used to replace a siphon control method^{5}. Therefore, the number of dead markings is reduced. Second, the theory of regions is used to obtain the optimal solution. Three elementary siphons (i.e. S_{1} = {p_{2}, p_{5}, p_{13}, p_{15}, p_{18}}, S_{2}= {p_{5}, p_{13}, p_{14}, p_{15,}p_{18}} and S_{3} = {p_{2}, p_{7}, p_{11}, p_{13}, p_{16}p_{19}}) can be identified. As a result, three control places V_{S1}V_{S3} as shown in Table 8 are needed to handle three elementary siphons. Then a partially controlled PN system, denoted as (N_{2L1}, M_{0}), can be obtained after the first stage.

M(D | C | M_{0}(Cpi) | (Cpi) | (Cpi) |

M_{19} | {(M_{56}, t_{1})} | 2 | t_{6}, t_{13} | t_{1}, t_{11} |

4 | t_{7}, t_{11} | t_{1}, t_{9} | ||

{(M_{56}, t_{9})} | 3 | t_{5}, t_{7}, t_{11} | t_{2}, t_{6}, t_{9} | |

4 | t_{7}, t_{11} | t_{1}, t_{9} | ||

M_{76} | {(M_{65}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{77} | {(M_{56}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{83} | {(M_{128}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{84} | {(M_{60}, t_{9})} | 3 | t_{5}, t_{7}, t_{11} | t_{2}, t6, t_{9} |

{(M_{60}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} | |

M_{105} | {(M_{93}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{106} | {(M_{98}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{112} | {(M_{122}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

M_{113} | {(M_{96}, t_{11})} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

Additional Control Places | M_{0}(Cpi) | (Cpi) | (Cpi) |

Cp_{1} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

Cp_{2} | 2 | t_{6}, t_{13} | t_{1}, t_{11} |

Cp_{3} | 3 | t_{6}, t_{11} | t_{2}, t_{4},t_{9} |

Cp_{4} | 3 | t_{5}, t_{7}, t_{11} | t_{2}, t_{6},t_{9} |

Cp_{5} | 3 | t_{7}, t_{11} | t_{4}, t_{5},t_{9} |

Cp_{6} | 4 | t_{7}, t_{11} | t_{1}, t_{9} |

However, (N_{2L1}, M_{0}) has a dead marking. Figure 13 shows a partial reachability graph and the deadlock marking M_{57} is included. M_{57} is one of the 210 reachable markings (i.e. the reachable markings M_{1}-M_{210} as denoted in^{16}. In^{16}, 210 reachable markings are divided into two categories: legal and illegal zones. The illegal zone consists of quasi-dead markings (i.e. M_{54}, M_{55}, M_{56}and M_{60}) and a dead marking (i.e. M_{57}). Obviously, some legal markings (i.e. M_{43}, M_{44}, M_{47}, M_{48}, M_{49}, M_{53}, M_{59} and M_{74}) can enter the illegal zone (i.e. Z_{I} = Z_{Q}Z_{D}). One can realize that they use the theory of regions to prevent these legal markings from entering Z_{I}. Therefore, they must resolve 8 MTSIs (i.e. {(M_{43}, t_{9})}, {(M_{44}, t_{9})}, {(M_{47}, t_{9})}, {(M_{48}, t_{9})}, {(M_{49}, t_{9})}, {(M_{53}, t_{4})}, {(M_{59}, t_{1})}, {(M_{74}, t_{2})}) and many equations in this example. Then the additional three control places can be obtained as shown in Table 9. Eight MTSIs are needed. Hence, their control policy^{16} does not seem efficiently enough when the MTSI at the second stage is used to obtain control places.

To compare the efficiency of the deadlock prevention methods, the proposed one is examined in the system net (N_{2L1}, M_{0}). One can realize that M_{57} is the only deadlock marking in R(N_{2L1}, M_{0}). Based on our method, only the dead marking M_{57} needed to be controlled. Here, only one = {(M_{44}, t_{9})} is needed. Obviously, the involved necessary equations are much less than those of the conventional one. We can obtain the same controlled net as that in ^{16}. Hence, the proposed concept of CMTSIs can be used in their approach^{16} to improve its computational efficiency significantly as well.

Additional Control Places | M_{0}(Cpi) | (Cpi) | (Cpi) |

Vs_{1} | 1 | t_{5}, t_{13} | t_{2}, t_{11} |

Vs_{2} | 2 | t_{4}, t_{5}, t_{13} | t_{1}, t_{11} |

Vs_{3} | 3 | t_{7}, t_{11} | t_{4}, t_{5},t_{9} |

Additional Control Places | M_{0}(Cpi) | (Cpi) | (Cpi) |

Cp_{1} | 3 | t_{6}, t_{11} | t_{2}, t_{4},t_{9} |

Cp_{2} | 3 | t_{5}, t_{7}, t_{11} | t_{2}, t_{6},t_{9} |

Cp_{3} | 4 | t_{2}, t_{4}, t_{7}, t_{11} | t_{1},t_{6}, t_{9} |

## 5. Comparison with existing methods

One can attempt to make a comparison with the previous methods^{12, 16, 24} in terms of efficiency. The first one proposed by Uzam^{12}, called Algorithm U, is totally based on the theory of regions. It solves six ESSPs in Example I. Then three control places are added on the net such that the controlled net is live and reversible. As for Example II, it solves 59 MTSIs. Nine control places are obtained. However, theproposed deadlock prevention policy called Algorithm P solves only two and 18 CMTSIs in Examples I and II, respectively.

The other one is proposed by Li et al.^{16, 24} called Algorithm L in which only the theory of regions is used in Example I. Notice that both the controlled results of Algorithms L and U are the same in Example I. In Example II, usingAlgorithm L, eight MTSIs are solved and six control places arecomputed. However, under the two-stage control policy, only one set of MTSI is needed by using our new policy to obtain the controlled result that is as the same asAlgorithm L in Example II. Note that both the definitions of ESSP and MTSI are the same. Hence, ESSP and CMTSI can be regarded as MTSI for the comparison purpose. The detailed comparison results are given in Table 10. However, only 18 MTSIs among 59 MTSIs are needed by using Algorithm P.

Example | # of Places | # of Resource Places | MTSIU, L, P | Control PlacesU, L, P | Reachable Markings |

I | 11 | 3 | 6, 6, 2 | 3, 3, 3 | 15 |

II | 19 | 6 | 59, ,18 | 9, , 6 | 205 |

II (two stages) | , 8, 1 | , 6, 6 |

For Example II, eight MTSIs are required to obtain the six control places under Algorithm L. Hence, one can infer that its performance is better than that of Algorithm U. Only one set of CMTSI is needed to obtain the same control result by Algorithm P. As a result, one can conclude that our proposed policy is more efficient than the other two methods.

To examine and compare the efficiency of the proposed method with those in^{16,24} in a system with large reachability graphs, one can use eight different markings of p_{1}, p_{8}, p_{15}, p_{18}, and p_{19}: [6, 5, 1, 1, 1]^{T}, [7, 6, 2, 1, 1]^{T}, [7, 6, 1, 2, 1]^{T,} [7, 6, 1, 1, 2]^{T}, [9, 8, 2, 2, 2]^{T}, [12, 11, 3, 3, 3]^{T}, [15, 14, 4, 4, 4]^{T}, and [18, 17, 5, 5, 5]^{T}. Tables 11 and 12 show various parameters in the plant and partially controlled net models, where M (p_{15}), M (p_{18}), and M (p_{19}) vary; |R|, |M_{L}|, |R_{D}|^{U}, |R_{D}|^{L}, indicate the number of reachable markings (states), legal markings, and dead markings under Algorithms U and L, respectively. Additionally,MTSIs of Algorithms U,L, and P are symbolized by ||^{U}, ||^{L} and ||^{P}, respectively. The last column is r_{a} = ||^{P} /||^{U} in Table 11, and r_{b} = |^{P} /||^{L} in Table 12. Notably, Algorithm G^{13} can be regarded as Algorithm U in Table 11 since the number of MTSIs and ESSPs are the same. In table 11, here, N_{sep} represents the number of MTSIs, and the N_{sep}/U,N_{sep}/L and N_{sep}/P represent the number of MTSIs of Algorithms U,L, and P, respectively. Obviously, the number of ||^{U} in the plant model grows quickly from cases 1 to 8. For instance, when M (p_{15}) = M (p_{18}) = M (p_{19}) = 5, ||^{U} = 4311, meaning that one must solve 4311 MTSIs when AlgorithmU is used. However, since ||^{P} = 228, only 228 equations (MTSIs) need to be solved under Algorithm P. As a result, Algorithm P is more efficient than Algorithm U in a large system.

cases | |R| | |ML| | |RD|U | |(|U | |(|P | ra |

1 | 282 | 205 | 16 | 59 | 18 | 30.5% |

2 | 600 | 484 | 27 | 95 | 28 | 29.5% |

3 | 972 | 870 | 26 | 103 | 26 | 25.2% |

4 | 570 | 421 | 16 | 107 | 19 | 17.8% |

5 | 4011 | 3711 | 42 | 288 | 42 | 14.6% |

6 | 27152 | 26316 | 84 | 886 | 84 | 9.5% |

7 | 124110 | 122235 | 145 | 2115 | 145 | 6.9% |

8 | 440850 | 437190 | 228 | 4311 | 228 | 5.3% |

case | |R| | |ML| | |RD|L | |(|L | |(|P | rb |

1 | 282 | 205 | 1 | 8 | 1 | 12.5% |

2 | 600 | 484 | 1 | 8 | 1 | 12.5% |

3 | 972 | 870 | 6 | 10 | 6 | 60.0% |

4 | 570 | 421 | 1 | 8 | 1 | 12.5% |

5 | 4011 | 3711 | 9 | 15 | 9 | 60.0% |

6 | 27152 | 26316 | 28 | 48 | 28 | 58.3% |

7 | 124110 | 122235 | 60 | 105 | 60 | 57.1% |

8 | 440850 | 437190 | 108 | 192 | 108 | 56.3% |

In Table 12, the number of MTSIs calculated by Algorithm L can be controlled, but Algorithm Pis more efficient in these cases. For instance, when M (p_{15}) = M (p_{18}) = M (p_{19}) = 5, ||^{L} = 192, meaning that one still has to solve 192 MTSIs when Algorithm L is used. However, ||^{P} =108. Only 108 MTSIs need to be solved by using Algorithm P. Importantly, the computational cost can be reduced by using our proposed method when it is compared with those in^{12, 16}. In conclusion, Algorithm Pis more efficient in large reachability graph cases than those in^{12-13}.

## 6. Conclusion

The proposed policy can be implemented for FMSs based on the theory of regions and Petri nets, where the dead markings are identified in its reachability graph. The underlying notion of the prior work is that many inequalities (i.e. MTSIs) must be solvedto prevent legal markings from entering the illegal zone in the original PN model. One must generate all MTSIs in a reachability graph and require high computation. This work proposes and uses CMTSI to overcome the computational difficulty. The detail information is also obtained in existing literatures.^{26-29} The proposed method can reduce the number of inequalities and thus the computational cost very significantly since CMTSIs are much less than MTSIs in large models.Consequently, it is optimal with much better computational efficiency than those existing optimal policies^{12-13, 16}. More benchmark studies will be desired to establish such computational advantages of the proposed one over the prior ones. It should be noted that the problem is still NP-hard the same as other optimal policies due to the need to generate the reachability graph of a Petri net. The future research is thus much needed to overcome the computational inefficiency of all these methods.

## Acknowledgement

The author is grateful to Prof. Yi-Sheng Huang and Prof. MengChu Zhou whose comments and suggestions greatly helped me improve the presentation and quality of this work.