# One Novel and Optimal Deadlock Recovery Policy for Flexible Manufacturing Systems Using Iterative Control Transitions Strategy

Authors: Ter-Chan Row; Wei-Ming Syu; Yen-Liang Pan; Ching-Cheng Wang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper focuses on solving deadlock problems of flexible manufacturing systems (FMS) based on Petri nets theory. Precisely, one novel control transition technology is developed to solve FMS deadlock problem. This new proposed technology can not only identify the maximal saturated tokens of idle places in Petri net model (PNM) but also further reserve all original reachable markings whatever they are legal or illegal ones. In other words, once the saturated number of tokens in idle places is identified, the maximal markings of system reachability graph can then be checked. Two classical S3PR (the Systems of Simple Sequential Processes with Resources) examples are used to illustrate the proposed technology. Experimental results indicate that the proposed algorithm of control transition technology seems to be the best one among all existing algorithms.


---

## Body

## 1. Introduction

Nowadays, in a rapidly changing society, every factory tries to use robots to possess complicated manufacturing workings. Flexible manufacturing systems (FMS) [1] are therefore designed to process these workings. However, for FMS there could exist an undesired phenomenon while robots are scramble for the shared resources of one FMS. The kind of competition is called the deadlock state. Besides, in order to solve above deadlock problem, three technologies are proposed [2]. The first one is deadlock avoidance. It can immediately avoid a deadlock and do the next step. The next one is called deadlock detection. It can find all deadlocks and recover the blocks. Please note that the above two technologies are adopted in dynamic method. They could have the time-consuming problem. The last one belongs to static. It considers the whole deadlocks in a model and solves them in advance. This technology is called deadlock prevention. Papers [3–11] presented a deadlock prevention to maintain the optimal permissiveness.In deadlock prevention domain, Barkaoui and Abdallah firstly propose a deadlock prevention concept and method for a class of FMS called System of Simple Sequential Processes with Resources (S3PR) [12]. In the following, Ezpeletaet al. [1] also presented a particular Petri net model for this kind of FMS. They used siphons concept and tried to add control places and related arcs to ensure the liveness of the FMS model. However, permissive is not large enough in deadlock free situation.In the following, Huanget al. [3] presented a method called maximal siphons control technology to solve the deadlock problem. The proposed algorithm can extract the strict minimal siphon from maximal siphons such that all siphons are successfully avoided. The method seems to be better than [1] since its permissive markings are more than [1]. Besides, Huanget al. [4] proposed another algorithm named iterative approach with mixed integer programming (MIP) method to improve conventional maximal siphons so as to enhance the computational efficiency. However, the two kinds of siphon based methods are still not maximally permissive.On the other hand, Li and Zhou [5] proposed the elementary siphon concept to minimize the redundant siphons. The dependent siphons can then be controlled simultaneously once elementary siphons are controlled. Besides, Li and Zhou [6] clarified the elementary siphons and then simplified the number of control places. The permissiveness is also ameliorative. Liuet al. [7] introduced and proved a live Petri net controller can be established by adding a control place and related arcs to each strict minimal siphon in a controllable siphon basis. They presented a new novel deadlock prevention policy based on the concept of a controllable siphon basis. It is pity; the above deadlock prevention policies are still not maximally permissive. For all siphon control methods, refer to [14, 15].Besides, Uzam [8] and Uzam and Zhou [9] follow the theory of region to obtain the optimal permissiveness. They classified all reachable states into two zones, deadlock-zone and deadlock-free-zone. The deadlock-zone was composed of dead markings and crucial dead markings. Finally, using the algorithm was successful to avoid the crucial dead markings and to make the net live. However, redundant the event-state-separation-problems (ESSPs) cannot be entirely avoided for large FMS cases. Huang and Pan [16, 17] and Huanget al. [18] further develop a computationally more efficient optimal deadlock control policy to improve the computational efficiency of the conventional theory of region.Piroddiet al. [10] also proposed selective siphon control method for solving deadlock problems in deadlock prevention domain. The policy merged selective siphons and crucial markings. By every iteration, the redundant siphons will be controlled simultaneously once selective siphons are controlled. Its most advantage is maximally permissive markings which can still be held. However, its drawback is that reachability graph is needed to run in every iteration. Therefore, Panet al. [19] develop one computationally improved methodology to enhance its computational efficiency. For improving above shortcoming, Panet al. [11] further try to merge theory of regions and the selective siphons control method to achieve optimal control goal. This proposed method can identify all crucial markings in first reachability graph and use the theory of regions to check these crucial markings. Finally, selective siphons method is used to control all minimal siphons. Maximally permissive markings are surely still held. Preciously, reachability graph is just one time needed to run. At the same time, Panet al. [20] also use the selective siphons technology with the method in [18] to further enhance the computational time of traditional theory of regions.In siphon control domain, Chao and Pan [21] also proposed the uniform formulas for compound siphons, complementary siphons, and characteristic vectors to solve the deadlock problems of flexible manufacturing systems easily. This can simplify the computational efficiency.On the other hand, Huanget al. [13] firstly presented transition-based deadlock prevention policy to solve the deadlocks problem of FMS. However, there are three main drawbacks in [13]. Firstly, they cannot identify the exact number of tokens in idle places in advance. Besides, they need to check all reachable markings of FMS reachability graph to avoid getting live lock. Finally, their some controllers seem to be redundant. Therefore, in our previous work [22], we first propose all reachability graph and First Dead Marking (FDM) viewpoints based on control transition to improve the computational efficiency of [13]. The improved work [22] does overcome the disadvantage of [13]. It is a pity; its example is a small PNM.Zhang and Uzam [23] also adopted control transition method to solve the deadlocks of flexible manufacturing systems. They improved the computational efficiency of [13] since the redundant controller’s problem was overcome. However, they still cannot identify the correct saturated number of tokens of idle places in the process of seeking the maximal number of reachable markings.Recently, Chenet al. [24] also propose one deadlock policy to solve FMS deadlock problem using control transition concept. They define a minimal recovery transitions using iterative approach by an integer linear programming problem (ILPP) and objective functions. However, it is not an efficient method since ILPP is used to obtain proper supervisors.Based on above survey, one can know that how to solve deadlock problems of flexible manufacturing systems is a very difficult issue. Many experts make their most effort in the issue [1, 3, 5, 9, 10, 25–34]. Most important, how to keep systems maximally permissive is needed to concern.To focus the maximally live performance, this paper proposes one new, different, and simple control method based on control transition technology. It presents a very different and novel concept in solving deadlock problems. First of all, the number of saturated tokens in idle (source or sink) places must be identified. Then, the maximal markings of its reachability graph can then be checked. Further, control transitions can be obtained. Finally, the maximally permissive live markings can be present once the controllers are added it into PNM.The rest of this paper is as follows. Section2 presents the preliminaries about the Petri nets. Section 3 proposes a new deadlock prevention approach and proves it can be executed. Section 4 presents two examples to verify by our prevention policy. The last, Section 5 is the conclusion.


## 2.Preliminaries

A Petri net model (PNM) is formed by five elements. The model will become actively according to the tokens firing. A PNM will be defined as follows.Definition 1 (see [1, 2, 35]).
N
=
(
P
,
T
,
F
,
W
,
M
0
), where
P is a finite, nonempty, and disjoint set of places which shows P
=
{
p
1
,
p
2
,
p
3
,
…
,
p
m
}
.
T is also a finite, nonempty, and disjoint set of transitions which shows T
=
{
t
1
,
t
2
,
t
3
,
…
,
t
m
}. The third element F is called the flow relation or the set of directed arcs with the arrows from places to transitions or from transitions to places. The characteristic of F is F
⊆
(
P
×
T
)
∪
(
T
×
P
). W
(
·
) is assigned the weight to an arc. Furthermore, the set of arcs in PNM are nonnegative integer. The net is called ordinary when the weight of arcs in PNM is all one. M
0 is named the initial marking combined with net system (
N
,
M
0
).
In a net system(
N
,
M
0
) and a node x
∈
P
∪
T, then the preset of node x is defined as ∙
x
=
{
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F
}. The postset of node x is defined as x
∙
=
{
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F
}.
A transitiont
∈
T is enabled at marking M by iff ∀
p
∈
∙
t and M
(
p
)
≥
W
(
p
,
t
) that will be denoted as M
t. Afterward enabled and firing a transition,M will get a new marking M
′. It indicates M
t
M
′. A marking M reaches to M
′ shown by M
σ
M
′ if there exists a firing sequence σ
=
t
1
t
2
t
3
…
t
n. The set of marking reachable from M in N is called a reachability set as R
(
N
,
M
) in net system (
N
,
M
0
). The net system (
N
,
M
0
) is live iff ∀
t
∈
T is enabled and dead iff ∃
t
∈
T is disabled.Definition 2 (see [35, 36]).
GivenS
∙
⊂
P, (resp., S
∙) denotes the set of transitions with at least one output (resp., input) place belonging to S. Formally, S
∙
=
∪
p
∈
s
p
∙ and S
∙
=
∪
p
∈
s
p
∙.S is called asiphon if S
∙
⊆
S
∙; i.e., any input transition of S is also an output transition of S. It is called atrap if S
∙
⊆
S
∙. A siphon (resp. trap) is said to beminimal if it does not contain other siphons (resp., traps).Definition 3 (see [1, 37–39]).
A S3PR is the union of a set from the two combined simple sequential processes with resources (S2PR) nets N
i
=
(
P
i
∪
{
p
i
0
}
∪
P
R
i
,
T
i
,
F
i
) by sharing common places, and the following statements are true.
(1)P
i and P
R
i are called operation and resource places of N
i, respectively. p
i
0 is called the process idle places.
(2)P
i
≠
ϕ; P
R
i
≠
ϕ; p
i
0
∉
P
i; (
P
i
∪
{
p
i
0
}
)
∩
P
R
i
=
ϕ; ∀
p
∈
P
i, ∀
t
∈
p
∙, ∀
t
′
∈
p
∙, ∃
r
p
∈
P
R
i, t
∙
∩
P
R
i
=
t
′
∙
∩
P
R
i
=
{
r
p
}; ∀
r
∈
P
R
i, r
∙
∙
∩
P
i
=
r
∙
∙
∩
P
i
≠
ϕ; ∀
r
∈
P
R
i,r
∙
∩
r
∙
=
ϕ; (
p
i
0
)
∙
∙
∩
P
R
i
=
(
p
i
0
)
∙
∙
∩
P
R
i
=
ϕ.
(3)N
i
′ is a strongly connected state machine, where N
i’=
(
P
i
∪
{
p
i
0
}
,
T
i
,
F
i
) is the resulting net after the places in P
R
i and related arcs are removed from N
i.
(4) Every circuit ofN
i
′ contains place p
i
0.
(5) Any twoN
i and N
j are composable if they share a set of common resource places. Every shared place must be a resource.
(6) The transitions of(
p
i
0
)
∙ and (
p
i
0
)
∙ are called source and sink transitions of S3PR, respectively.
(7) Forr
∈
P
R
,
H
(
r
)
=
(
r
∙
∙
)
∩
P
A is the set of operation places that use r and are called holders of r.
(8) Forp
∈
P
A, (
p
∙
∙
)
∩
P
R
=
{
r
p
} where resource place r
p is called the resource used by p.


## 3. One Novel Deadlock Prevention Policy

Since this paper tries to propose one novel deadlock recovery policy by adopting control transition method, in this section, the authors will present the important concept of the proposed policy and how it works. First of all, the number of saturated tokens in idle (e.g., source or sink) places should be identified. Secondly, the maximal number of markings in its reachability graph can then be checked and calculated. Further, control transitions can hence be obtained. Finally, the maximally permissive live markings can be present once the transition-based controllers are added to the deadlock prone PNM. In the following, the authors will show the detailed information as follows.


### 3.1. Saturated Number of Tokens in Idle Places

In this subsection, we will show how to identify the saturated number of tokens in PNM’s idle places. The first step is that one needs to pick all idle places and try to change the number of their tokens. Please note that the number is from small to large. Then, all reachable states will hence change due to the different number of tokens in idle places. Finally, the number of reachable states will reach one maximal number whatever the number of tokens increased in idle places. Under the situation, we call it the optimal number or saturated number of token in idle places. For example (please refer to Figure1), Table 1 shows the different number of tokens in two the idle places (i.e., p
1 and p
8). From the Table 1 we can see that the PNM reaches the maximal reachable states when (p
1
,
p
8) is (
2,2
). The experimental groups 15~16, 18~20, and 22~24 are just used to present that the maximal reachable states of the PNM are equal to 8. Further, the maximal reachable states are 8 whatever how large number of tokens is added or increased into the idle place. The set of (
2,2
) is what we want, it is the saturated number (or called optimal) of tokens in idle places of this PNM.Table 1
The variety of reachability states by different tokens in idle places of Figure1.
Experimental Group
(p
1
,
p
8)
Reachable States
Experimental Group
(p
1
,
p
8)
Reachable States
1
(1, 0)
3
13
(2, 1)
7
2
(2, 0)
4
14
(2,2)
8
3
(3, 0)
4
15
(2, 3)
8
4
(4, 0)
4
16
(2, 4)
8
5
(0, 1)
3
17
(3, 1)
7
6
(0, 2)
4
18
(3, 2)
8
7
(0, 3)
4
19
(3, 3)
8
8
(0, 4)
4
20
(3, 4)
8
9
(1,1)
6
21
(4, 1)
7
10
(1, 2)
7
22
(4, 2)
8
11
(1, 3)
7
23
(4, 3)
8
12
(1, 4)
7
24
(4, 4)
8Figure 1
Petri net model of two idle places.In the following, we demonstrate our algorithm by using above example. Please review the first example again; from Figure2, we can easily see that there exists one deadlock in its reachability graph. All information of reachable markings (states) is shown in Table 2 so that all readers can easily check them.Table 2
The detailed information of all reachable markings in Figure2.
Marking No.
Classification
Information of Markings
p
1
,
p
2
,
p
3
,
p
4
,
p
5
,
p
6
,
p
7
,
p
8
T
M
0
Initial Marking
2,0
,
1,0
,
0,1
,
0,2
T
M
1
Live marking
1,1
,
0,0
,
0,1
,
0,2
T
M
2
Live Marking
1,0
,
1,0
,
1,0
,
0,2
T
M
3
Live Marking
0,1
,
0,0
,
1,0
,
0,2
T
M
4
Dead Marking
1,1
,
0,0
,
0,0
,
1,1
T
M
5
Live Marking
2,0
,
1,0
,
0,0
,
1,1
T
M
6
Live Marking
2,0
,
0,1
,
0,1
,
0,1
T
M
7
Live Marking
2,0
,
0,1
,
0,0
,
1,0
TFigure 2
The reachability states of above simple PNM.


### 3.2. Identify the Control Transition

According to the definitions as follows, control transitions can be calculated and obtained in one PNM.Definition 4.
A Petri netN is with an initial marked M
0; the set of all reachable markings for the Petri net N is denoted by R
(
N
,
M
0
).Definition 5 (see [40]: reversibility).
(1) A Petri netN has a home state M
h for an initial state M
0 if for every reachable state M
∈
R
(
N
,
M
0
), a firing sequence σ
i exists such that M
σ
i
M
h.
(2) A Petri netN is reversible for an initial state M
0 if M
0 is a home state.Definition 6 (dead marking).
M
d is a dead marking and is defined as follows:(1)
M
d
=
M
∣
∀
M
∈
R
N
,
M
0
,
∄
t
∈
T
,
∋
M
tDefinition 7 (reachability tree).
Reachability tree is called reachability graph (RG) or reachability states (RS). A Petri netN with an initial marking M
0 is called a Petri net system (
N
,
M
0
). The reachability graph of (
N
,
M
0
) is defined as follows:(2)
∀
t
∈
T
,
∃
t
,
s
.
t
.
M
i
t
M
j
⇒
∪
M
i
t
M
j
w
h
e
r
e
M
i
,
M
j
,
a
n
d
t
∈
R
N
,
M
0The reachability graph is represented as R
(
N
,
M
0).Definition 8 (a transitiont is enabled and firing).
A transitiont is enabled ∀
p
∈
P
∧
p
∈
t
∙
∧
M
(
p
)
≥
W
(
p
,
t
). One can show that, as M
t, the next step is firing. A transition t is firing if a new marking M
′ yields. One can denote M
t
M
′.Definition 9 (control transition).
A Petri net with a dead markingM
d, ∀
M
d
∈
R
(
N
,
M
0
), M
∈
R
(
N
,
M
0
), M
d
⊂
M, ∃
t
c
∉
T, s.t. M
d
t
c
M. t
c is called a control transition.Definition 10 (saturated number of tokens in idle places (SNTIP)).
∃
min
⁡
(
n
) in a P
i
d such that the RG is maximal.
∑
P
i
d
(
m
i
n
(
n
)
) are obtained the maximal RG. Then, ∑
P
i
d
(
m
i
n
(
n
)
) are called SNTIP.
n is a token number in an idle place. n
=
0,1
,
2,3
,
….
P
i
d is an idle place.Theorem 11.
A deadlocked Petri net (S3PR), ∀
M
d
∈
R
(
N
,
M
0
), ∃
t
c
∉
T, such that M
d can reach to M
0 and M
d, becomes live.Proof.
It is well known that the state equation isM
k
=
M
k
-
1
+
A
T
u
k, k
=
1,2
,
3
,
… [41]. Here, we change the state equation to M
k
-
1
=
M
k
-
A
T
u
k then M
k
-
1
=
M
k
+
A
T
(
-
u
k
). Let -
u
k
=
y
k. Obtaining the new state equation is M
k
-
1
=
M
k
+
A
T
y
k
k
=
1,2
,
3
,
…. One expands and pluses by every series. The result is M
0
=
M
k
+
A
T
Σ
y
k. Assume M
k
=
M
d and x
=
Σ
y
k, then M
0
-
M
d
=
A
T
x, which can be written M
0
-
M
d
=
Δ
M. This means A
T
x
=
Δ
M. When Δ
M
=
0, then A
T
x
=
0 is a homogenous equation. ∃
x such that M
0
=
M
d
+
A
T
x. Based on [42], ones know A
T
x
=
O
(
t
,
p
)
-
I
(
t
,
p
). It means ∃
t
c (t
c
=
O
(
t
,
p
)
-
I
(
t
,
p
)) such that M
d can reach M
0. We can infer that M
0 is reachable from M
d.
To obtain the equation ofM
0
=
M
k
+
A
T
Σ
y
k, one has the following:(3)
M
0
=
M
1
+
A
T
y
1
(4)
M
1
=
M
2
+
A
T
y
2
(5)
M
2
=
M
3
+
A
T
y
3
(6)
⋮
k
-
2
M
k
-
2
=
M
k
-
1
+
A
T
y
k
-
1
k
-
1
M
k
-
1
=
M
k
+
A
T
y
k
Equations (3) + (4) + (5)…k
-
2 + k
-
1 are equal to M
0
=
M
k
+
A
T
Σ
y
k
◊.The example of Figure1 is present to obey Theorem 11 and obtain a control transition in the next section.


### 3.3. The Flow Steps of Our Deadlock Prevention Policy

The deadlock recovery policy and its steps are shown in Table3.Table 3
The flow step of our novel deadlock recovery policy.
Maximally Permissive Deadlock Recovery Policy
(i) Input: one deadlock S3PR PNM.
(1) Identify the saturated number of tokens in idle places.
(2) Identify the crucial dead markings from reachability graph.
(3) Calculate all control transitions.
(4) Add all control transitions into original PNM.
(ii) Output: one live S3PR PNM.In the following, we want to calculate the optimal control transitions so that they can be added to one deadlock PNM and live it. Please notice that the controller is calculated by initial marking (M
0
=
2,0
,
1,0
,
0,1
,
0,2
T) and the dead marking (M
4
=
1,1
,
0,0
,
0,0
,
1,1
T) based on Theorem 11. The firing count vector x
=
-
2
,
-
1
,
-
1,0
,
0
,
-
1
T and the transpose of incidence matrix A
T are as follows:(7)
A
T
=
-
1
0
1
0
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
0
1
0
-
1The equation of M
0
=
M
d
+
A
T
x is shown as follows:(8)
2
0
1
0
0
1
0
2
=
1
1
0
0
0
0
1
1
+
-
1
0
1
0
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
0
1
0
-
1
-
2
-
1
-
1
0
0
-
1Therefore, according to our proposed algorithm, the all output places of the control transition areO
(
t
7
)
=
p
1
+
p
3
+
p
6
+
p
8, and the all input places of the control transition are I
(
t
7
)
=
p
2
+
p
7. The detailed information of the controller is shown in Figure 3. The PNM is deadlock free when we added the controller to initial deadlock PNM. The detailed information is shown in Figure 4.Figure 3
The Petri net model with control transition.Figure 4
The reachability states of Figure3.


## 3.1. Saturated Number of Tokens in Idle Places

In this subsection, we will show how to identify the saturated number of tokens in PNM’s idle places. The first step is that one needs to pick all idle places and try to change the number of their tokens. Please note that the number is from small to large. Then, all reachable states will hence change due to the different number of tokens in idle places. Finally, the number of reachable states will reach one maximal number whatever the number of tokens increased in idle places. Under the situation, we call it the optimal number or saturated number of token in idle places. For example (please refer to Figure1), Table 1 shows the different number of tokens in two the idle places (i.e., p
1 and p
8). From the Table 1 we can see that the PNM reaches the maximal reachable states when (p
1
,
p
8) is (
2,2
). The experimental groups 15~16, 18~20, and 22~24 are just used to present that the maximal reachable states of the PNM are equal to 8. Further, the maximal reachable states are 8 whatever how large number of tokens is added or increased into the idle place. The set of (
2,2
) is what we want, it is the saturated number (or called optimal) of tokens in idle places of this PNM.Table 1
The variety of reachability states by different tokens in idle places of Figure1.
Experimental Group
(p
1
,
p
8)
Reachable States
Experimental Group
(p
1
,
p
8)
Reachable States
1
(1, 0)
3
13
(2, 1)
7
2
(2, 0)
4
14
(2,2)
8
3
(3, 0)
4
15
(2, 3)
8
4
(4, 0)
4
16
(2, 4)
8
5
(0, 1)
3
17
(3, 1)
7
6
(0, 2)
4
18
(3, 2)
8
7
(0, 3)
4
19
(3, 3)
8
8
(0, 4)
4
20
(3, 4)
8
9
(1,1)
6
21
(4, 1)
7
10
(1, 2)
7
22
(4, 2)
8
11
(1, 3)
7
23
(4, 3)
8
12
(1, 4)
7
24
(4, 4)
8Figure 1
Petri net model of two idle places.In the following, we demonstrate our algorithm by using above example. Please review the first example again; from Figure2, we can easily see that there exists one deadlock in its reachability graph. All information of reachable markings (states) is shown in Table 2 so that all readers can easily check them.Table 2
The detailed information of all reachable markings in Figure2.
Marking No.
Classification
Information of Markings
p
1
,
p
2
,
p
3
,
p
4
,
p
5
,
p
6
,
p
7
,
p
8
T
M
0
Initial Marking
2,0
,
1,0
,
0,1
,
0,2
T
M
1
Live marking
1,1
,
0,0
,
0,1
,
0,2
T
M
2
Live Marking
1,0
,
1,0
,
1,0
,
0,2
T
M
3
Live Marking
0,1
,
0,0
,
1,0
,
0,2
T
M
4
Dead Marking
1,1
,
0,0
,
0,0
,
1,1
T
M
5
Live Marking
2,0
,
1,0
,
0,0
,
1,1
T
M
6
Live Marking
2,0
,
0,1
,
0,1
,
0,1
T
M
7
Live Marking
2,0
,
0,1
,
0,0
,
1,0
TFigure 2
The reachability states of above simple PNM.


## 3.2. Identify the Control Transition

According to the definitions as follows, control transitions can be calculated and obtained in one PNM.Definition 4.
A Petri netN is with an initial marked M
0; the set of all reachable markings for the Petri net N is denoted by R
(
N
,
M
0
).Definition 5 (see [40]: reversibility).
(1) A Petri netN has a home state M
h for an initial state M
0 if for every reachable state M
∈
R
(
N
,
M
0
), a firing sequence σ
i exists such that M
σ
i
M
h.
(2) A Petri netN is reversible for an initial state M
0 if M
0 is a home state.Definition 6 (dead marking).
M
d is a dead marking and is defined as follows:(1)
M
d
=
M
∣
∀
M
∈
R
N
,
M
0
,
∄
t
∈
T
,
∋
M
tDefinition 7 (reachability tree).
Reachability tree is called reachability graph (RG) or reachability states (RS). A Petri netN with an initial marking M
0 is called a Petri net system (
N
,
M
0
). The reachability graph of (
N
,
M
0
) is defined as follows:(2)
∀
t
∈
T
,
∃
t
,
s
.
t
.
M
i
t
M
j
⇒
∪
M
i
t
M
j
w
h
e
r
e
M
i
,
M
j
,
a
n
d
t
∈
R
N
,
M
0The reachability graph is represented as R
(
N
,
M
0).Definition 8 (a transitiont is enabled and firing).
A transitiont is enabled ∀
p
∈
P
∧
p
∈
t
∙
∧
M
(
p
)
≥
W
(
p
,
t
). One can show that, as M
t, the next step is firing. A transition t is firing if a new marking M
′ yields. One can denote M
t
M
′.Definition 9 (control transition).
A Petri net with a dead markingM
d, ∀
M
d
∈
R
(
N
,
M
0
), M
∈
R
(
N
,
M
0
), M
d
⊂
M, ∃
t
c
∉
T, s.t. M
d
t
c
M. t
c is called a control transition.Definition 10 (saturated number of tokens in idle places (SNTIP)).
∃
min
⁡
(
n
) in a P
i
d such that the RG is maximal.
∑
P
i
d
(
m
i
n
(
n
)
) are obtained the maximal RG. Then, ∑
P
i
d
(
m
i
n
(
n
)
) are called SNTIP.
n is a token number in an idle place. n
=
0,1
,
2,3
,
….
P
i
d is an idle place.Theorem 11.
A deadlocked Petri net (S3PR), ∀
M
d
∈
R
(
N
,
M
0
), ∃
t
c
∉
T, such that M
d can reach to M
0 and M
d, becomes live.Proof.
It is well known that the state equation isM
k
=
M
k
-
1
+
A
T
u
k, k
=
1,2
,
3
,
… [41]. Here, we change the state equation to M
k
-
1
=
M
k
-
A
T
u
k then M
k
-
1
=
M
k
+
A
T
(
-
u
k
). Let -
u
k
=
y
k. Obtaining the new state equation is M
k
-
1
=
M
k
+
A
T
y
k
k
=
1,2
,
3
,
…. One expands and pluses by every series. The result is M
0
=
M
k
+
A
T
Σ
y
k. Assume M
k
=
M
d and x
=
Σ
y
k, then M
0
-
M
d
=
A
T
x, which can be written M
0
-
M
d
=
Δ
M. This means A
T
x
=
Δ
M. When Δ
M
=
0, then A
T
x
=
0 is a homogenous equation. ∃
x such that M
0
=
M
d
+
A
T
x. Based on [42], ones know A
T
x
=
O
(
t
,
p
)
-
I
(
t
,
p
). It means ∃
t
c (t
c
=
O
(
t
,
p
)
-
I
(
t
,
p
)) such that M
d can reach M
0. We can infer that M
0 is reachable from M
d.
To obtain the equation ofM
0
=
M
k
+
A
T
Σ
y
k, one has the following:(3)
M
0
=
M
1
+
A
T
y
1
(4)
M
1
=
M
2
+
A
T
y
2
(5)
M
2
=
M
3
+
A
T
y
3
(6)
⋮
k
-
2
M
k
-
2
=
M
k
-
1
+
A
T
y
k
-
1
k
-
1
M
k
-
1
=
M
k
+
A
T
y
k
Equations (3) + (4) + (5)…k
-
2 + k
-
1 are equal to M
0
=
M
k
+
A
T
Σ
y
k
◊.The example of Figure1 is present to obey Theorem 11 and obtain a control transition in the next section.


## 3.3. The Flow Steps of Our Deadlock Prevention Policy

The deadlock recovery policy and its steps are shown in Table3.Table 3
The flow step of our novel deadlock recovery policy.
Maximally Permissive Deadlock Recovery Policy
(i) Input: one deadlock S3PR PNM.
(1) Identify the saturated number of tokens in idle places.
(2) Identify the crucial dead markings from reachability graph.
(3) Calculate all control transitions.
(4) Add all control transitions into original PNM.
(ii) Output: one live S3PR PNM.In the following, we want to calculate the optimal control transitions so that they can be added to one deadlock PNM and live it. Please notice that the controller is calculated by initial marking (M
0
=
2,0
,
1,0
,
0,1
,
0,2
T) and the dead marking (M
4
=
1,1
,
0,0
,
0,0
,
1,1
T) based on Theorem 11. The firing count vector x
=
-
2
,
-
1
,
-
1,0
,
0
,
-
1
T and the transpose of incidence matrix A
T are as follows:(7)
A
T
=
-
1
0
1
0
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
0
1
0
-
1The equation of M
0
=
M
d
+
A
T
x is shown as follows:(8)
2
0
1
0
0
1
0
2
=
1
1
0
0
0
0
1
1
+
-
1
0
1
0
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
1
-
1
0
0
0
0
-
1
1
0
1
-
1
0
0
0
0
-
1
1
0
0
0
1
0
-
1
-
2
-
1
-
1
0
0
-
1Therefore, according to our proposed algorithm, the all output places of the control transition areO
(
t
7
)
=
p
1
+
p
3
+
p
6
+
p
8, and the all input places of the control transition are I
(
t
7
)
=
p
2
+
p
7. The detailed information of the controller is shown in Figure 3. The PNM is deadlock free when we added the controller to initial deadlock PNM. The detailed information is shown in Figure 4.Figure 3
The Petri net model with control transition.Figure 4
The reachability states of Figure3.


## 4. Examples and Comparisons

In this section, we want to evaluate our proposed deadlock prevention and make some comparisons with existing literature. Two classical examples are used to illustrate the proposed algorithm. The first example is one simple PNM. For easy tracing, we present the detailed information step by step. Please note that there are at least two dead markings in the two PNMs. In other words, some deadlock markings are redundant. Therefore, we not only want to identify the optimal number of tokens in its idle places, but also identify its crucial dead markings so that we can use them to calculate final controllers. For easy checking, the two PNM used TINA to run their reachability graph.


### 4.1. The Simple Petri Net Model [13]

Step 1 (identify the optimal number of tokens in idle places).
In this step, we firstly used one famous software TINA [43] to check the optimal number of tokens in idle places. Table 4 shows the variety of reachable states by changing different number of tokens in idle places of Figure 5. Please notice that the maximal number of tokens in p
0 is equal to 3 when the number of tokens in p
7 is set to zero. Similarly, the maximal number of tokens in p
7 is 2 when the number of tokens in p
0 is set to zero. The third group and the sixth group in Table 4 show the optimal number of tokens in its idle places, respectively. It is obvious that in sixteenth group when (
p
0
,
p
7
) is equal to (3,2) the idle places have the optimal number of tokens. (
p
0
,
p
7
)
=
(
3,2
) is the saturated number of tokens because the reachable states of this PNM are in its maximal value even one gives more tokens in (
p
0
,
p
7
). The maximal number of reachable markings is checked once the optimal number of tokens in one’s idle places is identified. The seventeenth and the eighteenth groups in Table 4 show the above description.Table 4
The variety of reachability states by different tokens in idle places of Figure5.
Set No.
(p
0
,
p
7)
Reachable States
Set No.
(p
0
,
p
7)
Reachable States
1
(1, 0)
5
10
(1, 2)
19
2
(2, 0)
10
11
(1, 3)
19
3
(3, 0)
11
12
(2, 1)
28
4
(4, 0)
11
13
(2, 2)
32
5
(0, 1)
4
14
(2, 3)
32
6
(0, 2)
5
15
(3, 1)
30
7
(0, 3)
5
16
(3, 2)
34
8
(0, 4)
5
17
(3, 3)
34
9
(1, 1)
16
18
(4, 3)
34Figure 5
One simple Petri net model [13].Step 2 (identify the crucial dead markings from reachability graph).
In this PNM, there are 34 reachable markings in total including 6 dead markings when the idle places are in saturation (please refer to Figure6). Based on TINA, the detailed information of the 6 dead markings is M
5
=
(
p
1
,
p
2
,
p
3
,
2
p
7
,
p
11
), M
14
=
(
p
1
,
p
2
,
p
3
,
p
7
,
p
9), M
22
=
(
3
p
0
,
p
5
,
p
6
,
p
8
,
p
9
), M
24
=
(
2
p
0
,
p
2
,
p
6
,
p
8
,
p
9
), M
26
=
(
p
0
,
p
2
,
p
3
,
p
8
,
p
9
), and M
28
=
(
2
p
0
,
p
3
,
p
5
,
p
8
,
p
9
), respectively. However, the 6 dead markings could be dependent. In other words, controllers could be redundant although the PNM also can be deadlock free when all controllers are added to above PNM. Therefore, one needs to identify crucial dead markings so as to obtain all independent controllers. By using the proposed algorithm, we can obtain 2 crucial dead markings, (p
1
+
p
2
+
p
3
+
p
11) and (p
5
+
p
6
+
p
8
+
p
9), respectively. The detailed information is shown in Table 5.Table 5
Two crucial control transitions.
No.
Property ofCrucial Dead Markings
I(t
c
i)
O(t
c
i)
Identified in WhichIdle Places
1
p
1 + p
2 + p
3 + p
11
I(t
c
1) = p
1 + p
2 + p
3
O(t
c
1) = 3
p
0 + p
5 + p
6 + p
12
(3, 0)
2
p
5 + p
6 + p
8 + p
9
I(t
c
2) = p
8 + p
9
O(t
c
2) = 2
p
7 + p
11 + p
12
(0, 2)Figure 6
The reachability graph of Figure5.Step 3 (calculate all control transitions).
According to the state equation (i.e.,M
0
-
M
d
=
O
(
t
,
p
)
–
I
(
t
,
p
)), two sets of control transitions can then be obtained. The detailed information of them is (1) I
(
t
c
1
)
=
p
1
+
p
2
+
p
3, O
(
t
c
1
)
=
3
p
0
+
p
5
+
p
6
+
p
12 and (2) I
(
t
c
2
)
=
p
8
+
p
9, O
(
t
c
2
)
=
2
p
7
+
p
11
+
p
12 also shown in Table 5.Step 4 (add all control transitions into original PNM).
The PNM is deadlock free when the two sets of control transitions are put into the original PNM. Besides, the number of its final reachable live markings is still 34. The proposed deadlock prevention policy not only solves the deadlock problem of the PNM of Figure5 but also holds all reachable markings even they are dead markings in the beginning. Its deadlock free reachability graph is shown in Figure 7. Please notice that the contents of six markingsM
15t,M
16t,M
20t,M
21t,M
24t, andM
25t are different from the initial markings.Figure 7
Its deadlock free reachability graph of Figure5.


### 4.2. Another Classical Complex PNM

In the following, we want to show that the proposed deadlock prevention policy can be used to solve a complex PNM shown in Figure8 [1]. In this PNM, it is composed of three robots named R
1, R
2, and R
3, denoted by p
20, p
21, and p
22, four machines named M
1, M
2, M
3, and M
4 denoted by p
23, p
24, p
25 and p
26, respectively. Finally, three idle places (I
1/O
1, I
2/O
2, and I
3/O
3) are given named p
1, p
14, and p
5, respectively. The others in this model are operation places. Further, there are 26750 reachable markings and 120 dead markings when its idle places are in saturation. Therefore, we want to show that our control policy can not only recover all 120 dead markings of the complex PNM but reserve all original 26750 reachable markings.Figure 8
One classical complex S3PR system [1].According to our deadlock prevention policy, the optimal number of tokens in each idle place areM
0
(
p
1
)
=
3, M
0
(
p
5
)
=
11 and M
0
(
p
14
)
=
7 in this PNM. And 20 crucial dead markings in total are identified and are shown in Table 6. Please notice that the original dead markings are 120. In our deadlock prevention policy, we can identify the 20 deadlock markings and use them to calculate and obtain 20 controllers.Table 6
The 20 sets of crucial dead markings of Figure8.
No.
Idle Places (p
1
,
p
5
,
p
14)
Crucial Dead Markings
1
(
3,0
,
0
)
p
2
+
2
p
3
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26
2
(
1,1
,
2
)
p
1
+
p
12
+
2
p
18
+
p
20
+
p
22
+
2
p
23
+
2
p
24
+
2
p
25
3
(
1,2
,
1
)
p
1
+
2
p
11
+
p
17
+
p
20
+
p
22
+
2
p
23
+
2
p
24
+
2
p
26
4
(
1,2
,
2
)
p
1
+
p
12
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
24
+
2
p
25
5
(
1,2
,
3
)
p
2
+
2
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
6
(
1,2
,
3
)
p
3
+
p
8
+
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
7
(
1,3
,
1
)
p
1
+
p
12
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
24
+
2
p
25
8
(
1,3
,
2
)
p
2
+
2
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
9
(
1,3
,
2
)
p
3
+
p
8
+
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
10
(
1,3
,
3
)
p
1
+
p
6
+
2
p
7
+
2
p
16
+
p
17
+
p
22
+
2
p
24
+
2
p
26
11
(
1,3
,
3
)
p
1
+
p
8
+
2
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
12
(
1,4
,
1
)
p
3
+
p
8
+
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
13
(
1,4
,
1
)
p
2
+
2
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
14
(
1,4
,
2
)
p
1
+
p
6
+
2
p
7
+
p
11
+
p
16
+
p
17
+
p
22
+
2
p
24
+
2
p
26
15
(
1,4
,
2
)
p
1
+
p
8
+
2
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
16
(
1,5
,
1
)
p
1
+
p
8
+
2
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
17
(
2,1
,
0
)
2
p
3
+
p
8
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26
18
(
2,1
,
3
)
p
2
+
p
3
+
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
19
(
2,2
,
2
)
p
2
+
p
3
+
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
20
(
2,3
,
1
)
p
2
+
p
3
+
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25First of all, please refer to Table6; the first crucial dead marking (i.e., p
2
+
2
p
3
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26) is identified when the three idle places are in M
0(p
1) = 3, M
0(p
5) = 0, and M
0(p
14) = 0, respectively. And then, its relative controller (I(t
c21) = p
2 + 2
p
3 andO(t
c21) = 3
p
1 + p
21 + 2p
24) can be calculated and obtained (i.e., the first set in Table 7). Eight dependent dead markings (M
1, M
2, M
45, M
55, M
66, M
80, M
93, andM
105 are checked in saturated situation based on TINA) also become live simultaneously (please refer to No. 1 in Table 8). Please notice that all markings presented in Table 9 are identified initially by the famous software TINA. Due to the space limitation of this paper, we just show the marking number in Table 8. For further detailed information, please refer to all data by using TINA. Anyway, 120 dead markings will reduce to 112. Surely, the total number of all reachable markings still is 26750. Keep doing the same process and step by step, 112 dead markings eventually become live. In sum, our deadlock prevention policy based on control transition live all reachable markings.Table 7
The 20 crucial control transitions of Figure8.
No.
In formation of Crucial control Transitions
1
O
(
t
c
21
)
=
(
3
p
1
+
p
21
+
2
p
24
)
I
(
t
c
21
)
=
(
p
2
+
2
p
3)
2
O
(
t
c
22
)
=
(
p
5
+
2
p
14
+
p
21
+
2
p
26
)
I
(
t
c
22
)
=
(
p
12
+
2
p
18
)
3
O
(
t
c
23
)
=
(
2
p
5
+
p
14
+
p
21
+
2
p
25
)
I
(
t
c
23
)
=
(
2
p
11
+
p
17
)
4
O
(
t
c
24
)
=
(
2
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
26
)
I
(
t
c
24
)
=
(
p
12
+
p
13
+
p
18
+
p
19
)
5
O
(
t
c
25
)
=
(
p
1
+
2
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
25
)
=
(
p
2
+
2
p
9
+
2
p
18
+
p
19
)
6
O
(
t
c
26
)
=
(
p
1
+
2
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
26
)
=
(
p
3
+
p
8
+
p
9
+
2
p
18
+
p
19
)
7
O
(
t
c
27
)
=
(
3
p
5
+
p
14
+
p
21
+
p
22
+
2
p
26
)
I
(
t
c
27
)
=
(
p
12
+
2
p
13
+
p
19
)
8
O
(
t
c
28
)
=
(
p
1
+
3
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
28
)
=
(
p
2
+
2
p
9
+
p
13
+
p
18
+
p
19
)
9
O
(
t
c
29
)
=
(
p
1
+
3
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
29
)
=
(
p
3
+
p
8
+
p
9
+
p
13
+
p
18
+
p
19
)
10
O
(
t
c
30
)
=
(
3
p
5
+
3
p
14
+
p
20
+
p
21
+
2
p
23
+
2
p
25
)
I
(
t
c
30
)
=
(
p
6
+
2
p
7
+
2
p
16
+
p
17
)
11
O
(
t
c
31
)
=
(
3
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
31
)
=
(
p
8
+
2
p
9
+
2
p
18
+
p
19
)
12
O
(
t
c
32
)
=
(
p
1
+
4
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
32
)
=
(
p
3
+
p
8
+
p
9
+
2
p
13
+
p
19
)
13
O
(
t
c
33
)
=
(
p
1
+
4
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
33
)
=
(
p
2
+
2
p
9
+
2
p
13
+
p
19
)
14
O
(
t
c
34
)
=
(
4
p
5
+
2
p
14
+
p
20
+
p
21
+
2
p
23
+
2
p
25
)
I
(
t
c
34
)
=
(
p
6
+
2
p
7
+
p
11
+
p
16
+
p
17
)
15
O
(
t
c
35
)
=
(
4
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
35
)
=
(
p
8
+
2
p
9
+
p
13
+
p
18
+
p
19
)
16
O
(
t
c
36
)
=
(
5
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
36
)
=
(
p
8
+
2
p
9
+
2
p
13
+
p
19
)
17
O
(
t
c
37
)
=
(
2
p
1
+
p
5
+
p
21
+
2
p
24
)
I
(
t
c
37
)
=
(
2
p
3
+
p
8
)
18
O
(
t
c
38
)
=
(
2
p
1
+
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
38
)
=
(
p
2
+
p
3
+
p
9
+
2
p
18
+
p
19
)
19
O
(
t
c
39
)
=
(
2
p
1
+
2
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
39
)
=
(
p
2
+
p
3
+
p
9
+
p
13
+
p
18
+
p
19
)
20
O
(
t
c
40
)
=
(
2
p
1
+
3
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
40
)
=
(
p
2
+
p
3
+
p
9
+
2
p
13
+
p
19
)Table 8
The 20 dependent dead markings checked in saturated situation based on TINA of Table6.
No.
Dependent Deadlock Markings
The Number of Deadlock Markings
After Relative controllers are added
into PNM
1
M
1, M
2, M
45, M
55, M
66, M
80, M
93, M
105
112
2
M
6, M
7, M
14, M
15, M
21, M
22, M
31, M
32, M
33, M
34, M
78, M
79
100
3
M
24, M
26, M
27, M
28, M
29, M
30, M
47, M
48, M
51, M
52, M
53, M
58
88
4
M
42, M
43, M
50, M
54, M
56, M
57, M
60, M
92,M
117, M
118, M
119, M
120
76
5
M
17, M
23, M
73
73
6
M
12, M
13, M
71
70
7
M
96, M
99, M
100, M
101, M
102, M
104, M
108, M
111, M
112, M
113, M
114, M
116
58
8
M
38, M
44, M
87
55
9
M
49, M
65, M
85
52
10
M
67, M
69, M
70, M
72, M
74, M
76, M
81, M
83, M
84, M
86, M
88, M
90
40
11
M
19, M
20, M
75
37
12
M
95, M
107
35
13
M
97, M
109
33
14
M
3, M
8, M
10, M
11, M
16, M
18, M
36, M
37, M
39, M
61, M
63, M
64
21
15
M
40, M
41, M
89
18
16
M
98, M
110
16
17
M
4, M
5, M
59, M
62, M
77, M
91, M
103, M
115
8
18
M
9, M
25, M
68
5
19
M
35, M
46, M
82
2
20
M
94, M
106
0Table 9
Comparison with existing literature.
Ezpeleta et al. (1995) [1]
Huang et al (2001) [3]
Li & Zhou (2004) [5]
Uzam & Zhou (2006) [34]
Chao (2009b) [26]
Piroddi et al. (2008) [10]
Chen et al (2011) [27]
Chen et al (2012) [28]
Hong et al. (2015) [29]
Row et al. [This paper]
No.C
P
18
16
5
19
7
13
17
6
9
0
No.C
T
0
0
0
0
0
0
0
0
0
20
No.R
L
6287
12656
15999
21562
21585
21581
21581
21581
20444
26750
%R
23.5%
47.3%
59.8%
80.6%
80.7%
80.7%
80.7%
80.7%
94.7%
100%


### 4.3. Comparison with Existing Researches

In this subsection, we make some comparisons with existing literature based on the classical complex PNM. Please note that the “No.C
P” represents the number of control places, “No. C
T” represents the number of control transitions, “No. R
L” represents the number of live reachable markings, and “% R” represents the recover percent relative to original 26750 markings. From Table 9, it is obvious that our algorithm is the only algorithm which can achieve 100 % maximally permissive markings among all published researches.


## 4.1. The Simple Petri Net Model [13]

Step 1 (identify the optimal number of tokens in idle places).
In this step, we firstly used one famous software TINA [43] to check the optimal number of tokens in idle places. Table 4 shows the variety of reachable states by changing different number of tokens in idle places of Figure 5. Please notice that the maximal number of tokens in p
0 is equal to 3 when the number of tokens in p
7 is set to zero. Similarly, the maximal number of tokens in p
7 is 2 when the number of tokens in p
0 is set to zero. The third group and the sixth group in Table 4 show the optimal number of tokens in its idle places, respectively. It is obvious that in sixteenth group when (
p
0
,
p
7
) is equal to (3,2) the idle places have the optimal number of tokens. (
p
0
,
p
7
)
=
(
3,2
) is the saturated number of tokens because the reachable states of this PNM are in its maximal value even one gives more tokens in (
p
0
,
p
7
). The maximal number of reachable markings is checked once the optimal number of tokens in one’s idle places is identified. The seventeenth and the eighteenth groups in Table 4 show the above description.Table 4
The variety of reachability states by different tokens in idle places of Figure5.
Set No.
(p
0
,
p
7)
Reachable States
Set No.
(p
0
,
p
7)
Reachable States
1
(1, 0)
5
10
(1, 2)
19
2
(2, 0)
10
11
(1, 3)
19
3
(3, 0)
11
12
(2, 1)
28
4
(4, 0)
11
13
(2, 2)
32
5
(0, 1)
4
14
(2, 3)
32
6
(0, 2)
5
15
(3, 1)
30
7
(0, 3)
5
16
(3, 2)
34
8
(0, 4)
5
17
(3, 3)
34
9
(1, 1)
16
18
(4, 3)
34Figure 5
One simple Petri net model [13].Step 2 (identify the crucial dead markings from reachability graph).
In this PNM, there are 34 reachable markings in total including 6 dead markings when the idle places are in saturation (please refer to Figure6). Based on TINA, the detailed information of the 6 dead markings is M
5
=
(
p
1
,
p
2
,
p
3
,
2
p
7
,
p
11
), M
14
=
(
p
1
,
p
2
,
p
3
,
p
7
,
p
9), M
22
=
(
3
p
0
,
p
5
,
p
6
,
p
8
,
p
9
), M
24
=
(
2
p
0
,
p
2
,
p
6
,
p
8
,
p
9
), M
26
=
(
p
0
,
p
2
,
p
3
,
p
8
,
p
9
), and M
28
=
(
2
p
0
,
p
3
,
p
5
,
p
8
,
p
9
), respectively. However, the 6 dead markings could be dependent. In other words, controllers could be redundant although the PNM also can be deadlock free when all controllers are added to above PNM. Therefore, one needs to identify crucial dead markings so as to obtain all independent controllers. By using the proposed algorithm, we can obtain 2 crucial dead markings, (p
1
+
p
2
+
p
3
+
p
11) and (p
5
+
p
6
+
p
8
+
p
9), respectively. The detailed information is shown in Table 5.Table 5
Two crucial control transitions.
No.
Property ofCrucial Dead Markings
I(t
c
i)
O(t
c
i)
Identified in WhichIdle Places
1
p
1 + p
2 + p
3 + p
11
I(t
c
1) = p
1 + p
2 + p
3
O(t
c
1) = 3
p
0 + p
5 + p
6 + p
12
(3, 0)
2
p
5 + p
6 + p
8 + p
9
I(t
c
2) = p
8 + p
9
O(t
c
2) = 2
p
7 + p
11 + p
12
(0, 2)Figure 6
The reachability graph of Figure5.Step 3 (calculate all control transitions).
According to the state equation (i.e.,M
0
-
M
d
=
O
(
t
,
p
)
–
I
(
t
,
p
)), two sets of control transitions can then be obtained. The detailed information of them is (1) I
(
t
c
1
)
=
p
1
+
p
2
+
p
3, O
(
t
c
1
)
=
3
p
0
+
p
5
+
p
6
+
p
12 and (2) I
(
t
c
2
)
=
p
8
+
p
9, O
(
t
c
2
)
=
2
p
7
+
p
11
+
p
12 also shown in Table 5.Step 4 (add all control transitions into original PNM).
The PNM is deadlock free when the two sets of control transitions are put into the original PNM. Besides, the number of its final reachable live markings is still 34. The proposed deadlock prevention policy not only solves the deadlock problem of the PNM of Figure5 but also holds all reachable markings even they are dead markings in the beginning. Its deadlock free reachability graph is shown in Figure 7. Please notice that the contents of six markingsM
15t,M
16t,M
20t,M
21t,M
24t, andM
25t are different from the initial markings.Figure 7
Its deadlock free reachability graph of Figure5.


## 4.2. Another Classical Complex PNM

In the following, we want to show that the proposed deadlock prevention policy can be used to solve a complex PNM shown in Figure8 [1]. In this PNM, it is composed of three robots named R
1, R
2, and R
3, denoted by p
20, p
21, and p
22, four machines named M
1, M
2, M
3, and M
4 denoted by p
23, p
24, p
25 and p
26, respectively. Finally, three idle places (I
1/O
1, I
2/O
2, and I
3/O
3) are given named p
1, p
14, and p
5, respectively. The others in this model are operation places. Further, there are 26750 reachable markings and 120 dead markings when its idle places are in saturation. Therefore, we want to show that our control policy can not only recover all 120 dead markings of the complex PNM but reserve all original 26750 reachable markings.Figure 8
One classical complex S3PR system [1].According to our deadlock prevention policy, the optimal number of tokens in each idle place areM
0
(
p
1
)
=
3, M
0
(
p
5
)
=
11 and M
0
(
p
14
)
=
7 in this PNM. And 20 crucial dead markings in total are identified and are shown in Table 6. Please notice that the original dead markings are 120. In our deadlock prevention policy, we can identify the 20 deadlock markings and use them to calculate and obtain 20 controllers.Table 6
The 20 sets of crucial dead markings of Figure8.
No.
Idle Places (p
1
,
p
5
,
p
14)
Crucial Dead Markings
1
(
3,0
,
0
)
p
2
+
2
p
3
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26
2
(
1,1
,
2
)
p
1
+
p
12
+
2
p
18
+
p
20
+
p
22
+
2
p
23
+
2
p
24
+
2
p
25
3
(
1,2
,
1
)
p
1
+
2
p
11
+
p
17
+
p
20
+
p
22
+
2
p
23
+
2
p
24
+
2
p
26
4
(
1,2
,
2
)
p
1
+
p
12
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
24
+
2
p
25
5
(
1,2
,
3
)
p
2
+
2
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
6
(
1,2
,
3
)
p
3
+
p
8
+
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
7
(
1,3
,
1
)
p
1
+
p
12
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
24
+
2
p
25
8
(
1,3
,
2
)
p
2
+
2
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
9
(
1,3
,
2
)
p
3
+
p
8
+
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
10
(
1,3
,
3
)
p
1
+
p
6
+
2
p
7
+
2
p
16
+
p
17
+
p
22
+
2
p
24
+
2
p
26
11
(
1,3
,
3
)
p
1
+
p
8
+
2
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
12
(
1,4
,
1
)
p
3
+
p
8
+
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
13
(
1,4
,
1
)
p
2
+
2
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
14
(
1,4
,
2
)
p
1
+
p
6
+
2
p
7
+
p
11
+
p
16
+
p
17
+
p
22
+
2
p
24
+
2
p
26
15
(
1,4
,
2
)
p
1
+
p
8
+
2
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
16
(
1,5
,
1
)
p
1
+
p
8
+
2
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25
17
(
2,1
,
0
)
2
p
3
+
p
8
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26
18
(
2,1
,
3
)
p
2
+
p
3
+
p
9
+
2
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
19
(
2,2
,
2
)
p
2
+
p
3
+
p
9
+
p
13
+
p
18
+
p
19
+
p
20
+
2
p
23
+
2
p
25
20
(
2,3
,
1
)
p
2
+
p
3
+
p
9
+
2
p
13
+
p
19
+
p
20
+
2
p
23
+
2
p
25First of all, please refer to Table6; the first crucial dead marking (i.e., p
2
+
2
p
3
+
p
20
+
p
22
+
2
p
23
+
2
p
25
+
2
p
26) is identified when the three idle places are in M
0(p
1) = 3, M
0(p
5) = 0, and M
0(p
14) = 0, respectively. And then, its relative controller (I(t
c21) = p
2 + 2
p
3 andO(t
c21) = 3
p
1 + p
21 + 2p
24) can be calculated and obtained (i.e., the first set in Table 7). Eight dependent dead markings (M
1, M
2, M
45, M
55, M
66, M
80, M
93, andM
105 are checked in saturated situation based on TINA) also become live simultaneously (please refer to No. 1 in Table 8). Please notice that all markings presented in Table 9 are identified initially by the famous software TINA. Due to the space limitation of this paper, we just show the marking number in Table 8. For further detailed information, please refer to all data by using TINA. Anyway, 120 dead markings will reduce to 112. Surely, the total number of all reachable markings still is 26750. Keep doing the same process and step by step, 112 dead markings eventually become live. In sum, our deadlock prevention policy based on control transition live all reachable markings.Table 7
The 20 crucial control transitions of Figure8.
No.
In formation of Crucial control Transitions
1
O
(
t
c
21
)
=
(
3
p
1
+
p
21
+
2
p
24
)
I
(
t
c
21
)
=
(
p
2
+
2
p
3)
2
O
(
t
c
22
)
=
(
p
5
+
2
p
14
+
p
21
+
2
p
26
)
I
(
t
c
22
)
=
(
p
12
+
2
p
18
)
3
O
(
t
c
23
)
=
(
2
p
5
+
p
14
+
p
21
+
2
p
25
)
I
(
t
c
23
)
=
(
2
p
11
+
p
17
)
4
O
(
t
c
24
)
=
(
2
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
26
)
I
(
t
c
24
)
=
(
p
12
+
p
13
+
p
18
+
p
19
)
5
O
(
t
c
25
)
=
(
p
1
+
2
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
25
)
=
(
p
2
+
2
p
9
+
2
p
18
+
p
19
)
6
O
(
t
c
26
)
=
(
p
1
+
2
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
26
)
=
(
p
3
+
p
8
+
p
9
+
2
p
18
+
p
19
)
7
O
(
t
c
27
)
=
(
3
p
5
+
p
14
+
p
21
+
p
22
+
2
p
26
)
I
(
t
c
27
)
=
(
p
12
+
2
p
13
+
p
19
)
8
O
(
t
c
28
)
=
(
p
1
+
3
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
28
)
=
(
p
2
+
2
p
9
+
p
13
+
p
18
+
p
19
)
9
O
(
t
c
29
)
=
(
p
1
+
3
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
29
)
=
(
p
3
+
p
8
+
p
9
+
p
13
+
p
18
+
p
19
)
10
O
(
t
c
30
)
=
(
3
p
5
+
3
p
14
+
p
20
+
p
21
+
2
p
23
+
2
p
25
)
I
(
t
c
30
)
=
(
p
6
+
2
p
7
+
2
p
16
+
p
17
)
11
O
(
t
c
31
)
=
(
3
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
31
)
=
(
p
8
+
2
p
9
+
2
p
18
+
p
19
)
12
O
(
t
c
32
)
=
(
p
1
+
4
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
32
)
=
(
p
3
+
p
8
+
p
9
+
2
p
13
+
p
19
)
13
O
(
t
c
33
)
=
(
p
1
+
4
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
33
)
=
(
p
2
+
2
p
9
+
2
p
13
+
p
19
)
14
O
(
t
c
34
)
=
(
4
p
5
+
2
p
14
+
p
20
+
p
21
+
2
p
23
+
2
p
25
)
I
(
t
c
34
)
=
(
p
6
+
2
p
7
+
p
11
+
p
16
+
p
17
)
15
O
(
t
c
35
)
=
(
4
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
35
)
=
(
p
8
+
2
p
9
+
p
13
+
p
18
+
p
19
)
16
O
(
t
c
36
)
=
(
5
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
36
)
=
(
p
8
+
2
p
9
+
2
p
13
+
p
19
)
17
O
(
t
c
37
)
=
(
2
p
1
+
p
5
+
p
21
+
2
p
24
)
I
(
t
c
37
)
=
(
2
p
3
+
p
8
)
18
O
(
t
c
38
)
=
(
2
p
1
+
p
5
+
3
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
38
)
=
(
p
2
+
p
3
+
p
9
+
2
p
18
+
p
19
)
19
O
(
t
c
39
)
=
(
2
p
1
+
2
p
5
+
2
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
39
)
=
(
p
2
+
p
3
+
p
9
+
p
13
+
p
18
+
p
19
)
20
O
(
t
c
40
)
=
(
2
p
1
+
3
p
5
+
p
14
+
p
21
+
p
22
+
2
p
24
+
2
p
26
)
I
(
t
c
40
)
=
(
p
2
+
p
3
+
p
9
+
2
p
13
+
p
19
)Table 8
The 20 dependent dead markings checked in saturated situation based on TINA of Table6.
No.
Dependent Deadlock Markings
The Number of Deadlock Markings
After Relative controllers are added
into PNM
1
M
1, M
2, M
45, M
55, M
66, M
80, M
93, M
105
112
2
M
6, M
7, M
14, M
15, M
21, M
22, M
31, M
32, M
33, M
34, M
78, M
79
100
3
M
24, M
26, M
27, M
28, M
29, M
30, M
47, M
48, M
51, M
52, M
53, M
58
88
4
M
42, M
43, M
50, M
54, M
56, M
57, M
60, M
92,M
117, M
118, M
119, M
120
76
5
M
17, M
23, M
73
73
6
M
12, M
13, M
71
70
7
M
96, M
99, M
100, M
101, M
102, M
104, M
108, M
111, M
112, M
113, M
114, M
116
58
8
M
38, M
44, M
87
55
9
M
49, M
65, M
85
52
10
M
67, M
69, M
70, M
72, M
74, M
76, M
81, M
83, M
84, M
86, M
88, M
90
40
11
M
19, M
20, M
75
37
12
M
95, M
107
35
13
M
97, M
109
33
14
M
3, M
8, M
10, M
11, M
16, M
18, M
36, M
37, M
39, M
61, M
63, M
64
21
15
M
40, M
41, M
89
18
16
M
98, M
110
16
17
M
4, M
5, M
59, M
62, M
77, M
91, M
103, M
115
8
18
M
9, M
25, M
68
5
19
M
35, M
46, M
82
2
20
M
94, M
106
0Table 9
Comparison with existing literature.
Ezpeleta et al. (1995) [1]
Huang et al (2001) [3]
Li & Zhou (2004) [5]
Uzam & Zhou (2006) [34]
Chao (2009b) [26]
Piroddi et al. (2008) [10]
Chen et al (2011) [27]
Chen et al (2012) [28]
Hong et al. (2015) [29]
Row et al. [This paper]
No.C
P
18
16
5
19
7
13
17
6
9
0
No.C
T
0
0
0
0
0
0
0
0
0
20
No.R
L
6287
12656
15999
21562
21585
21581
21581
21581
20444
26750
%R
23.5%
47.3%
59.8%
80.6%
80.7%
80.7%
80.7%
80.7%
94.7%
100%


## 4.3. Comparison with Existing Researches

In this subsection, we make some comparisons with existing literature based on the classical complex PNM. Please note that the “No.C
P” represents the number of control places, “No. C
T” represents the number of control transitions, “No. R
L” represents the number of live reachable markings, and “% R” represents the recover percent relative to original 26750 markings. From Table 9, it is obvious that our algorithm is the only algorithm which can achieve 100 % maximally permissive markings among all published researches.


## 5. Conclusions

In this paper, we successfully propose one novel iterative method to obtain maximally permissive states based on control transitions. Generally, “maximal permissive” means the number of legal markings in an original deadlock PNM. Further, it does not include the initial illegal markings. For example, they just can obtain 21581 maximally permissive markings in the second example of Section4. However, our proposed algorithm does obtain the real 26750 maximally permissive markings. In other words, our deadlock prevention recovers one deadlock PNM. In our approach, we do not consider any controllability of siphons. We just focus on crucial dead markings. All markings are live and reachable once these crucial markings are controlled. Our approach is now suitable to all S3PR model. The future work is to reduce the computing time (i.e., reduce running the number of reachability graph or reduce the number of controllers) and extends the method applying for more general models in Petri net.



---

*Source: 4847072-2019-03-27.xml*