# Equivalent Transformation of Nonlinear Constraints to Linear Constraints in Petri Nets

Authors: YuFeng Chen; Abdulrahman Al-Ahmari; Chi Tin Hon; NaiQi Wu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper focuses on the enforcement of nonlinear constraints in Petri nets. An integer linear programming model is formulated to transform a nonlinear constraint to a minimal number of conjunctive linear constraints that have the same admissible marking space as the nonlinear one does in Petri nets. The obtained linear constraints can be easily enforced to be satisfied by a set of control places with a place invariant  based method. The control places make up a supervisor that can enforce the given nonlinear constraint. For a case that the admissible marking space decided by a nonlinear constraint is nonconvex, another integer linear programming model is developed to obtain a minimal number of constraints whose disjunctions are equivalent to the nonlinear constraint with respect to the reachable markings. Finally, a number of examples are provided to demonstrate the proposed approach.


---

## Body

## 1. Introduction

Petri nets [1] are a suitable tool to model and control discrete event systems (DESs) [2–9]. The control of a DES is to restrict its behavior to satisfy the desired control specifications, for example, state forbidding or liveness enforcement. Supervisory control [10, 11] is a well-known mechanism to enforce external constraints on a system to be controlled. In the framework of Petri nets, supervisory control is often represented by a set of control places such that only the desired behavior is allowed.Constraints associated with reachable states in a DES are a typical and important control specification in supervisory control theory of DESs [12, 13]. In Petri nets, control specifications are often formulated as linear constraints on the states of a system. Linear constraints in Petri nets, also called generalized mutual exclusion constraints (GMECs) [14], are an important concept in the supervisory control of DESs. A well-established approach to enforce a GMEC is to add a control place (monitor) to construct a place invariant (PI) [15, 16] in a Petri net. The PI-based approach has been widely studied by researchers and engineers. Yamalidou et al. [16] design control places to enforce a variety of GMECs. Iordache and Antsaklis [17, 18] propose an approach to implement the disjunctive GMECs. In [19], a good survey is presented on the design of control places by PI-based methods. Up to now, most of the work dealing with deadlocks by Petri nets is based on PIs [20–29].However, not all specifications can be represented as GMECs. In some cases, the specifications are given as a nonlinear constraint on a net model. In this case, the PI-based method fails to find a supervisor to enforce a nonlinear constraint. Therefore, this work deals with nonlinear constraints in Petri nets by finding a set of GMECs that are equivalent to a given nonlinear constraint. A nonlinear constraint is said to be equivalent to a set of GMECs if they allow the same behavior of a net model. Motivated by the work in [30–32], given a Petri net and a constraint, its reachability graph is divided into two parts: an admissible-zone (AZ) and a forbidden-zone (FZ), where the AZ contains all admissible markings, that is, those satisfying the constraint, and the FZ includes all forbidden markings, that is, those which do not satisfy the constraint. Then, we formulate the concept of border forbidden markings (BFMs) of a net model. A BFM is a forbidden marking that represents the very first entry from the AZ to the FZ. Thus, once all BFMs are forbidden, all forbidden markings are forbidden. Based on the reachability graph analysis, a set of GMECs can be found to forbid all BFMs but not admissible markings. In this sense, a nonlinear constraint is equivalent to a set of GMECs since they have the identical AZ.There are two types of admissible marking space to be considered: convex and nonconvex. Based on the equivalence of different constraints, we propose an approach to find a set of conjunctive GMECs that are equivalent to a given nonlinear constraint if its admissible marking space is convex. Meanwhile, an integer linear programming problem (ILPP) is formulated to minimize the number of computed GMECs. That is to say, given a nonlinear constraint, we can find a minimal number of conjunctive GMECs that, once enforced, achieve the same control purposes as specified by the nonlinear one. In the case that the admissible marking space decided by a nonlinear constraint is nonconvex but its BFMs space is convex, we formulate another ILPP to find a minimal number of disjunctive GMECs that are equivalent to it; that is, we can find a minimal number of disjunctive GMECs that are enforced to achieve the same control purpose as the nonlinear one.The rest of the paper is organized as follows. In Section2, some basics of Petri nets and the design of control places by PIs are recalled. Section 3 reports the concepts and properties of nonlinear constraints and defines the equivalence of constraints by means of reachability graph analysis. In Section 4, two ILPPs are formulated to obtain a minimal number of conjunctive GMECs and a minimal number of disjunctive GMECs, respectively, which are equivalent to a given nonlinear constraint. Examples are provided to demonstrate the proposed method in Section 5. Finally, we make conclusions in Section 6.


## 2. Preliminaries

This section recalls the basics of Petri nets [1] and the computation of control places by PIs [16].


### 2.1. Petri Nets

A Petri net is a four-tupleN
=
(
P
,
T
,
F
,
W
) where P and T are finite and nonempty sets. P is a set of places and T is a set of transitions with P
∩
T
=
∅. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. W
:
(
P
×
T
)
∪
(
T
×
P
)
→
N is a mapping that assigns a weight to an arc: W
(
x
,
y
)
>
0 if (
x
,
y
)
∈
F and W
(
x
,
y
)
=
0, otherwise, where (
x
,
y
)
∈
(
P
×
T
)
∪
(
T
×
P
) and N is the set of nonnegative integers. •
x
=
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F is called the preset of x and x
•
=
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F is called the postset of x. A marking is a mapping M
:
P
→
N. M
(
p
) denotes the number of tokens in place p. For the sake of an expedient description, a compact multiset formalism ∑
i
=
1
n
‍
M
(
p
i
)
p
i is used to represent marking M, where n is the number of places. The pair (
N
,
M
0
) is called a marked Petri net or a net system. A net is pure (self-loop free) if, ∀
(
x
,
y
)
∈
(
P
×
T
)
∪
(
T
×
P
), W
(
x
,
y
)
>
0 implies W
(
y
,
x
)
=
0. The incidence matrix [
N
] of a net N is a P
×
T integer matrix with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
).A transitiont
∈
T is enabled at marking M if, ∀
p
∈
•
t, M
(
p
)
≥
W
(
p
,
t
). This fact is denoted as M
[
t
〉. Once an enabled transition t fires, it yields a new marking M
′, denoted as M
[
t
〉
M
′, where M
′
(
p
)
=
M
(
p
)
-
W
(
p
,
t
)
+
W
(
t
,
p
). The set of reachable markings of net N with initial marking M
0 is denoted by R
(
N
,
M
0
). It can be graphically expressed by a reachability graph, denoted as G
(
N
,
M
0
). It is a directed graph whose nodes are markings in R
(
N
,
M
0
) and arcs are labeled by the fired transitions.Let(
N
,
M
0
) be a net system with N
=
(
P
,
T
,
F
,
W
). A transition t
∈
T is live if, ∀
M
∈
R
(
N
,
M
0
), ∃
M
′
∈
R
(
N
,
M
), M
′
[
t
〉. (
N
,
M
0
) is live if, ∀
t
∈
T, t is live. It is dead if ∄
t
∈
T, M
0
[
t
〉.AP-vector is a column vector I
:
P
→
Z indexed by P and a T-vector is a column vector J
:
T
→
Z indexed by T, where Z is the set of integers. P-vector I is called a P-invariant (place invariant, PI for short) if I
≠
0 and I
T
[
N
]
=
0
T. A P-invariant I is said to be a P-semiflow if I
≥
0. Let I be a PI of (
N
,
M
0
). Then, ∀
M
∈
R
(
N
,
M
0
), we have I
T
M
=
I
T
M
0.


### 2.2.  Control Place for GMECs

Let[
N
] be the incidence matrix of a plant with n places and m transitions and [
N
c
] the incidence matrix of the control places. In what follows, we briefly recall the computation of control places by PIs [16].Definition 1.
A generalized mutual exclusion constraint (GMEC) is a pair(
l
,
β
) where l
∈
Z
n and β
∈
N. A GMEC defines a set of admissible markings: (1)
M
l
,
β
=
M
∈
N
n
∣
l
T
·
M
≤
β
.Letl
i be the ith component of l. Then a GMEC (
l
,
β
) can be represented as(2)
∑
i
=
1
n
l
i
·
μ
i
≤
β
,where μ
i denotes the marking of place p
i. This inequality constraint can be transformed into an equality by introducing a nonnegative slack variable μ
s as(3)
∑
i
=
1
n
l
i
·
μ
i
+
μ
s
=
β
,where μ
s represents the marking of control place p
s that is usually called a monitor. A set of GMECs can be grouped into a matrix form as follows:(4)
L
·
μ
→
p
≤
b
→
,where μ
→
p is the marking vector of the Petri net model, L is an n
c
×
n nonnegative integer matrix, b
→ is an n
c
×
1 nonnegative integer vector, and n
c is the number of GMECs. By introducing a nonnegative slack vector μ
c, these inequality constraints can be transformed into equalities:(5)
L
·
μ
→
p
+
μ
→
c
=
b
→
,where μ
→
c is an n
c
×
1 vector representing the marking of the control places. According to PI equation I
T
[
N
]
=
0
T, the supervisor [
N
c
] can be computed as follows:(6)
N
c
=
-
L
·
N
.Equation (5) is also true at the initial marking μ
→
0 of a net. Thus, the initial marking μ
→
c
0 of the supervisor can be computed as follows:(7)
μ
→
c
0
=
b
→
-
L
·
μ
→
0
.


## 2.1. Petri Nets

A Petri net is a four-tupleN
=
(
P
,
T
,
F
,
W
) where P and T are finite and nonempty sets. P is a set of places and T is a set of transitions with P
∩
T
=
∅. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. W
:
(
P
×
T
)
∪
(
T
×
P
)
→
N is a mapping that assigns a weight to an arc: W
(
x
,
y
)
>
0 if (
x
,
y
)
∈
F and W
(
x
,
y
)
=
0, otherwise, where (
x
,
y
)
∈
(
P
×
T
)
∪
(
T
×
P
) and N is the set of nonnegative integers. •
x
=
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F is called the preset of x and x
•
=
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F is called the postset of x. A marking is a mapping M
:
P
→
N. M
(
p
) denotes the number of tokens in place p. For the sake of an expedient description, a compact multiset formalism ∑
i
=
1
n
‍
M
(
p
i
)
p
i is used to represent marking M, where n is the number of places. The pair (
N
,
M
0
) is called a marked Petri net or a net system. A net is pure (self-loop free) if, ∀
(
x
,
y
)
∈
(
P
×
T
)
∪
(
T
×
P
), W
(
x
,
y
)
>
0 implies W
(
y
,
x
)
=
0. The incidence matrix [
N
] of a net N is a P
×
T integer matrix with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
).A transitiont
∈
T is enabled at marking M if, ∀
p
∈
•
t, M
(
p
)
≥
W
(
p
,
t
). This fact is denoted as M
[
t
〉. Once an enabled transition t fires, it yields a new marking M
′, denoted as M
[
t
〉
M
′, where M
′
(
p
)
=
M
(
p
)
-
W
(
p
,
t
)
+
W
(
t
,
p
). The set of reachable markings of net N with initial marking M
0 is denoted by R
(
N
,
M
0
). It can be graphically expressed by a reachability graph, denoted as G
(
N
,
M
0
). It is a directed graph whose nodes are markings in R
(
N
,
M
0
) and arcs are labeled by the fired transitions.Let(
N
,
M
0
) be a net system with N
=
(
P
,
T
,
F
,
W
). A transition t
∈
T is live if, ∀
M
∈
R
(
N
,
M
0
), ∃
M
′
∈
R
(
N
,
M
), M
′
[
t
〉. (
N
,
M
0
) is live if, ∀
t
∈
T, t is live. It is dead if ∄
t
∈
T, M
0
[
t
〉.AP-vector is a column vector I
:
P
→
Z indexed by P and a T-vector is a column vector J
:
T
→
Z indexed by T, where Z is the set of integers. P-vector I is called a P-invariant (place invariant, PI for short) if I
≠
0 and I
T
[
N
]
=
0
T. A P-invariant I is said to be a P-semiflow if I
≥
0. Let I be a PI of (
N
,
M
0
). Then, ∀
M
∈
R
(
N
,
M
0
), we have I
T
M
=
I
T
M
0.


## 2.2.  Control Place for GMECs

Let[
N
] be the incidence matrix of a plant with n places and m transitions and [
N
c
] the incidence matrix of the control places. In what follows, we briefly recall the computation of control places by PIs [16].Definition 1.
A generalized mutual exclusion constraint (GMEC) is a pair(
l
,
β
) where l
∈
Z
n and β
∈
N. A GMEC defines a set of admissible markings: (1)
M
l
,
β
=
M
∈
N
n
∣
l
T
·
M
≤
β
.Letl
i be the ith component of l. Then a GMEC (
l
,
β
) can be represented as(2)
∑
i
=
1
n
l
i
·
μ
i
≤
β
,where μ
i denotes the marking of place p
i. This inequality constraint can be transformed into an equality by introducing a nonnegative slack variable μ
s as(3)
∑
i
=
1
n
l
i
·
μ
i
+
μ
s
=
β
,where μ
s represents the marking of control place p
s that is usually called a monitor. A set of GMECs can be grouped into a matrix form as follows:(4)
L
·
μ
→
p
≤
b
→
,where μ
→
p is the marking vector of the Petri net model, L is an n
c
×
n nonnegative integer matrix, b
→ is an n
c
×
1 nonnegative integer vector, and n
c is the number of GMECs. By introducing a nonnegative slack vector μ
c, these inequality constraints can be transformed into equalities:(5)
L
·
μ
→
p
+
μ
→
c
=
b
→
,where μ
→
c is an n
c
×
1 vector representing the marking of the control places. According to PI equation I
T
[
N
]
=
0
T, the supervisor [
N
c
] can be computed as follows:(6)
N
c
=
-
L
·
N
.Equation (5) is also true at the initial marking μ
→
0 of a net. Thus, the initial marking μ
→
c
0 of the supervisor can be computed as follows:(7)
μ
→
c
0
=
b
→
-
L
·
μ
→
0
.


## 3. Generalizations of Nonlinear Constraints

In this section, we present basic concepts of nonlinear constraints in Petri nets in the sense of reachability graph analysis. We focus on the general definitions of nonlinear constraints since the linear case can always be considered as a special case of nonlinear constraints.Letc be a constraint that restricts the tokens in a subset of places in a Petri net model (
N
,
M
0
). In this work, the constraints are only marking dependent while no firing functions of transitions are considered.Definition 2.
A constraintc on a net (
N
,
M
0
) defines a function F
c
:
R
(
N
,
M
0
)
→
0,1 such that F
c
(
M
)
=
1 if M satisfies c, otherwise F
c
(
M
)
=
0, where M
∈
R
(
N
,
M
0
).A constraintc classifies the reachable markings of a net into two groups: admissible ones that satisfy c and forbidden ones that do not satisfy c, as defined below.Definition 3.
Letc be a constraint on a Petri net model (
N
,
M
0
). A marking M
∈
R
(
N
,
M
0
) is said to be admissible with respect to c if F
c
(
M
)
=
1. The set of admissible markings with respect to c is denoted by M
c. A reachable marking M of (
N
,
M
0
) is said to be forbidden with respect to c if F
c
(
M
)
=
0. The set of forbidden markings with respect to c is denoted by M
c
¯.A supervisor is maximally permissive, or optimal, if it can always disable any transition whose firing leads to a forbidden marking. In this sense, a maximally permissive supervisor for a constraintc should keep all admissible markings with respect to c in the controlled system and exclude the reachability of any forbidden marking decided by c.Given a constraint on a Petri net model(
N
,
M
0
), we assume that its initial marking always satisfies the constraint. Then, the reachability graph of (
N
,
M
0
) can be classified into two parts: an admissible-zone (AZ) and a forbidden-zone (FZ). The AZ includes all admissible markings with respect to c, from which the initial marking is reachable, and the FZ contains all forbidden markings with respect to c. A border forbidden marking (BFM) with respective to c is a marking in the FZ that is the direct successor of some marking in the AZ. Mathematically, the set M
B of BFMs is defined as follows.Definition 4.
Letc be a constraint on (
N
,
M
0
). The set of BFMs is defined as M
B
=
M
∣
∀
M
∈
M
c
¯
,
∃
M
′
∈
M
c
,
∃
t
∈
T
,
s
.
t
.
M
′
t
M.If all BFMs cannot be reached, their successors cannot be reached. Thus, there is no need to compute the whole reachability graph of a net system. Definition4 motivates us to generate a part of the reachability graph, that is, M
c and M
B. An algorithm to compute the two sets is presented in Algorithm 1.Algorithm 1:Computation of the set of admissible markings and the set of BFMs.
Input: A Bounded Petri net(
N
,
M
0
) and a constraint c
Output: The setM
c of admissible markings and the set M
B of BFMs
(1)M
c
:
=
M
′
:
=
M
0. /∗
M
′ denotes the set of markings whose successors are not computed. ∗/
(2)while
M
′
≠
∅
do
∀
M
∈
M
′, remove M from M
′, that is, M
′
:
=
M
′
-
M.
for each
transition t enabled at M
do
M
′
:
=
M
+
[
N
]
(
⋅
,
t
).
if
F
c
(
M
′
)
=
0 and M
′
∉
M
B
then
M
B
:
=
M
B
∪
M
′ and M
′
:
=
M
′
∪
M
′.
elseif
F
c
(
M
′
)
=
1 and M
′
∉
M
c
M
c
:
=
M
c
∪
M
′ and M
′
:
=
M
′
∪
M
′.
endif
endwhile
(3) OutputM
c and M
B.
(4) End.Algorithm1 can find all admissible markings and BFMs without generating the whole reachability graph of a net. Next, the equivalence between two constraints is defined by means of reachability graph analysis.Definition 5.
LetC
=
c
1
∧
c
2
∧
,
…
,
∧
c
n
c be a set of conjunctive constraints on a Petri net model (
N
,
M
0
). A reachable marking M of (
N
,
M
0
) is said to be admissible with respect to C if, ∀
c
i
∈
C
,
F
c
i
(
M
)
=
1. The set of admissible markings with respective to C is denoted by M
C. A reachable marking M of (
N
,
M
0
) is said to be forbidden with respect to C if ∃
c
i
∈
C
,
F
c
i
(
M
)
=
0. The set of forbidden markings with respective to C is denoted by M
C
¯.Similarly, we have the following definition for the setC of disjunctive constraints; that is, C
=
c
1
∨
c
2
∨
,
…
,
∨
c
n
c.Definition 6.
LetC
=
c
1
∨
c
2
∨
,
…
,
∨
c
n
c be a set of disjunctive constraints on a Petri net model (
N
,
M
0
). A reachable marking M of (
N
,
M
0
) is said to be admissible with respect to C if ∃
c
i
∈
C, F
c
i
(
M
)
=
1. The set of admissible markings with respect to C is denoted by M
C. A reachable marking M of (
N
,
M
0
) is said to be forbidden with respect to C if, ∀
c
i
∈
C, F
c
i
(
M
)
=
0. The set of forbidden markings with respect to C is denoted by M
C
¯.By Definitions5 and 6, we can define the equivalence between the sets of constraints. In the following, C
i
(
i
=
1,2
) can be a set of conjunctive or disjunctive constraints.Definition 7.
LetC
1 and C
2 be two sets of constraints on (
N
,
M
0
). C
1 and C
2 are said to be equivalent with respect to (
N
,
M
0
) if M
C
1
=
M
C
2.Since a GMEC can be directly enforced through a control place by the PI-based method [16], Definition 7 motivates us to develop an approach to replace a nonlinear constraint by a set of GMECs. That is to say, given a nonlinear constraint, we can possibly find a set of linear constraints that achieve the same control purposes by the reachability graph analysis.


## 4. From Nonlinear Constraints to GMECs

In the case that the admissible marking space decided by a nonlinear constraint is convex, this constraint can be transformed into a set of conjunctive GMECs that have the same admissible marking space as the nonlinear one. That is to say, a nonlinear constraint is equivalent to a set of GMECs from the viewpoint of constraint enforcement purposes. Similarly, if the admissible marking space decided by a nonlinear constraint is nonconvex but its BFMs space is convex, it can be transformed into a set of disjunctive GMECs.


### 4.1. The Minimal Number of Conjunctive Constraints

A set of conjunctive GMECs can be easily enforced by a set of control places using the method presented in Section2.2. In this section, we first transform a nonlinear constraint into a set of conjunctive GMECs. In the following, N
B denotes k
∣
M
k
∈
M
B.Suppose that there is a nonlinear constraintc on a Petri net (
N
,
M
0
) with n places and m transitions. A set of conjunctive GMECs on (
N
,
M
0
), which is equivalent to c, can be expressed as(8)
⋀
j
=
1
n
c
∑
i
=
1
n
l
j
,
i
·
μ
i
≤
β
j
,where n
c is the number of the constraints, l
j
,
i’s are integers, and β
j is a nonnegative integer.Letc
j denote the jth constraint; that is, c
j
:
=
∑
i
=
1
n
‍
l
j
,
i
·
μ
i
≤
β
j. All admissible markings with respect to c, whose set is denoted by M
c, should be reachable. Thus, we have(9)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
M
l
∈
M
c
.A BFMM
k
∈
M
B decided by c is forbidden by c
j if(10)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
.Now, we introduce a set of variablesf
j
,
k’s (k
∈
N
B) to represent the relation between c
j and M
k in M
B. Then, (10) is modified to be(11)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,where Q is a positive integer constant that must be big enough and f
j
,
k
∈
{
0,1
} is a binary variable. In (11), f
j
,
k
=
1 indicates that M
k is forbidden by c
j and f
j
,
k
=
0 implies that M
k cannot be forbidden by c
j. For c
j, all constraints in the type of (11) for BFMs in M
B are grouped as:(12)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,
∀
M
k
∈
M
B
.In fact, the number of constraints, for example,n
c, to be computed is much less than that of the elements in M
B. Therefore, we can formulate an ILPP to find the minimal number of constraints. Now, by introducing variable h
j
∈
{
0,1
}  (
j
=
1,2
,
…
,
n
c
) for c
j, we have the following constraint(13)
f
j
,
k
≤
h
j
,
∀
k
∈
N
B
,where h
j
=
1 implies that c
j is selected and otherwise h
j
=
0. Equation (13) means that if c
j is not selected, it cannot forbid any BFM. For a BFM M
k, we also have(14)
∑
j
=
1
n
c
f
j
,
k
≥
1
.Equation (14) ensures that any BFM M
k in M
B must be forbidden by at least one constraint.As a result, we have the following ILPP to obtain the minimal number of conjunctive constraints, which is denoted as the minimal number of conjunctive constraints problem (MNCCP) as follows(15)
min
⁡
h
=
∑
k
=
1
n
c
h
j
(16)
subject  to
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
(17)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
(18)
f
j
,
k
≤
h
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
k
∈
N
B
(19)
∑
j
=
1
n
c
f
j
,
k
≥
1
,
∀
k
∈
N
B
(20)
l
j
,
i
∈
Z
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
i
∈
1,2
,
…
,
n
f
j
,
k
∈
0,1
,
∀
k
∈
N
B
,
∀
j
∈
1,2
,
…
,
n
c
h
j
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
β
j
∈
0,1
,
2
,
…
,
∀
j
∈
1,2
,
…
,
n
c
.The objective functionh is used to minimize the number of constraints to be computed. Denote its optimal solution as h
∗. If MNCCP has an optimal solution, we can claim that the given constraint is equivalent to the minimal number h
∗ of linear constraints, as stated below.Theorem 8.
Given a Petri net model(
N
,
M
0
) and a nonlinear constraint c on it, if MNCCP has an optimal solution h
∗, then one can obtain the minimal number h
∗ of conjunctive GMECs that are equivalent to c with respect to (
N
,
M
0
).Proof.
By (16), each computed constraint does not forbid any admissible marking. By (17) and (19), every BFM is forbidden by at least one constraint. Thus, all forbidden markings are accordingly forbidden. Equation (18) ensures that only the selected constraints are used to forbid BFMs. In addition, the objective function ensures that the minimal number of constraints is selected. Since h represents the number of the selected constraints, the minimal number equals the optimal solution h
∗. In summary, the conclusion holds.For MNCCP, we need to set a proper initial value forn
c. In the worst case, we need to design a constraint for each BFM. Thus, we have 1
≤
n
c
≤
M
B. Suppose that MNCCP has an optimal solution with the minimal number of constraints and it is denoted as n
c
∗. If n
c is too small, that is, n
c
<
n
c
∗, MNCCP has no solution. In this case, we can increase n
c and solve MNCCP again. Therefore, the proper range for n
c is from n
c
∗ to M
B. If MNCCP has no solution for n
c
=
M
B, the proposed ILPP fails to find a set of conjunctive constraints that are equivalent to the given constraint. The closer the given n
c is to n
c
∗, the more efficient MNCCP becomes since it has less constraints and variables. Table 1 shows the number of constraints and variables in MNCCP.Table 1
The number of constraints and variables in MNCCP.
Constraint
Number of constraints
Variable
Number of variables
(16)
n
c
⋅
M
c
l
j
,
i
n
c
⋅
P
(17)
n
c
⋅
M
B
f
j
,
k
n
c
⋅
M
B
(18)
n
c
⋅
M
B
h
j
n
c
(19)
M
B
β
j
n
c
Total
n
c
⋅
M
c
+
2
M
B
+
M
B
Total
n
c
⋅
P
+
M
B
+
2


### 4.2. The Minimal Number of Disjunctive Constraints

If the admissible marking space with respect to a nonlinear constraintc is nonconvex, we cannot find a set of GMECs whose conjunctions are equivalent to c. However, if its BFMs space is convex, it is possible to find a set of GMECs whose disjunctions are equivalent to c. In the following, N
c denotes l
∣
M
l
∈
M
c. The disjunctions of GMECs can be written as(21)
⋁
j
=
1
n
c
∑
i
=
1
n
l
j
,
i
·
μ
i
≤
β
j
.Equation (21) indicates that at least one of the constraints must be satisfied. Hence, a marking is reachable if it satisfies at least one of the constraints. Any marking M
l
∈
M
c must be reachable. Therefore, we have(22)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
M
l
∈
M
c
,
∃
j
∈
1,2
,
…
,
n
c
.Equation (22) cannot be directly considered as a constraint for an ILPP. Hence, we introduce a set of binary variables f
j
,
l’s (
f
j
,
l
∈
{
0,1
}
) to represent the relation between each marking M
l and the jth constraint. In particular, f
j
,
l
=
1 indicates that M
l satisfies the jth constraint and f
j
,
l
=
0 implies that M
l does not satisfy the jth constraint. Then, (22) is rewritten as(23)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
Q
·
1
-
f
j
,
l
+
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
,where Q is a positive constant that must be big enough. For (23), if f
j
,
l
=
1, it becomes ∑
i
=
1
n
‍
l
j
,
i
·
M
l
(
p
i
)
≤
β
j. If f
j
,
l
=
0, it is ∑
i
=
1
n
‍
l
j
,
i
·
M
l
(
p
i
)
≤
Q
+
β
j, implying that this constraint does not restrict l
j
,
i’s and β
j. Since M
l must satisfy at least one constraint, we have(24)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
j
∈
1,2
,
…
,
n
c
.A marking is forbidden if it is forbidden by every constraint. Any markingM
k
∈
M
B must be forbidden. Therefore, we have(25)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
.We do not know how many constraints are needed. In the worst case, each admissible marking inM
c is associated with a constraint. That is to say, 1
≤
n
c
≤
M
c. In fact, the number of constraints to be computed is much less than the cardinality of M
c. Suppose that there are n
c constraints initially. Next, we select the minimal number of constraints from the n
c constraints. A variable h
j
(
h
j
∈
{
0,1
}, j
∈
1,2
,
…
,
n
c
) is introduced for the jth constraint and we have the following facts:(26)
f
j
,
l
≤
h
j
,
∀
l
∈
N
c
,
∀
j
∈
1,2
,
…
,
n
c
,where h
j
=
1 implies that the jth constraint is selected and h
j
=
0 indicates that the jth constraint is redundant and thus there is no need to add it as a constraint in (21). Equation (26) means that if the jth constraint is not selected, no admissible marking necessarily satisfies it. For any admissible marking M
l, we also have(27)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
l
∈
N
c
.Equation (27) ensures that any admissible marking M
l in M
c must satisfy at least one constraint.Finally, we formulate the following ILPP to find the minimal number of disjunctive GMECs that are equivalent to the given constraintc, which is denoted as the minimal number of disjunctive constraints problem (MNDCP).MNDCP is shown as follows:(28)
min
⁡
h
=
∑
j
=
1
n
c
h
j
(29)
subject  to
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
(30)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
Q
·
1
-
f
j
,
l
+
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
(31)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
l
∈
N
c
(32)
f
j
,
l
≤
h
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
l
∈
N
c
(33)
l
j
,
i
∈
Z
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
i
∈
1,2
,
…
,
n
f
j
,
l
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
l
∈
N
c
h
j
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
β
j
∈
0,1
,
2
,
…
,
∀
j
∈
1,2
,
…
,
n
c
.The objective functionh is used to minimize the number of constraints that are selected. Denote its optimal value by h
∗. If MNDCP has an optimal solution, then we can find the minimal number h
∗ of disjunctive GMECs that are equivalent to the give nonlinear constraint, as stated below.Theorem 9.
Given a Petri net model(
N
,
M
0
) and a nonlinear constraint c, if MNDCP has an optimal solution h
∗, then we can obtain the minimal number h
∗ of disjunctive GMECs that are equivalent to c with respect to (
N
,
M
0
).Proof.
Equation (29) ensures that every obtained constraint can forbid all BFMs in M
B. Thus, no forbidden marking is reachable. According to (30) and (31), every marking in M
c satisfies at least one obtained constraint. Hence, the disjunctions of all obtained constraints, that is, (21), can make all admissible markings reachable. Finally, the objective function ensures that the minimal number of constraints is selected, that is, the optimal solution h
∗. In summary, the conclusion holds.Similar to MNCCP, we also need to set a proper initial value forn
c in MNDCP. In the worst case, we need to design a constraint for each admissible marking. Thus, we have 1
≤
n
c
≤
M
c. Suppose that MNDCP has an optimal solution with the minimal number of constraints. We denote the minimal number as n
c
∗. If n
c is too small, that is, n
c
<
n
c
∗, MNDCP has no solution. In this case, we can increase n
c and solve MNDCP again. Therefore, the proper range for n
c is from n
c
∗ to M
c. If MNDCP has no solution for n
c
=
M
c, the proposed ILPP fails to find a set of disjunctive constraints that are equivalent to the given constraint. The closer the given n
c is to n
c
∗, the more efficient the MNDCP becomes since it has less constraints and variables.As stated previously, the computational time for finding an optimal solution of an ILPP greatly depends on the number of the constraints and variables in it. Therefore, we provide the numbers of constraint and variables in MNDCP in Table2.Table 2
The numbers of constraints and variables in MNDCP.
Constraint
Number of constraints
Variable
Number of variables
(29)
n
c
⋅
M
B
l
j
,
i
n
c
⋅
P
A
(30)
n
c
⋅
M
c
f
j
,
l
n
c
⋅
M
c
(31)
M
c
h
j
n
c
(32)
n
c
⋅
M
c
β
j
n
c
Total
n
c
⋅
M
B
+
2
M
c
+
M
c
Total
n
c
⋅
P
A
+
M
c
+
2The disjunctions of GMECs cannot be directly implemented by designing a control place for each constraint by the PI-based method. However, one can find some existing approaches in [17, 18] that deal with disjunctive constraints in the framework of supervisory control. In this work, we do not recall it due to the limited space.


## 4.1. The Minimal Number of Conjunctive Constraints

A set of conjunctive GMECs can be easily enforced by a set of control places using the method presented in Section2.2. In this section, we first transform a nonlinear constraint into a set of conjunctive GMECs. In the following, N
B denotes k
∣
M
k
∈
M
B.Suppose that there is a nonlinear constraintc on a Petri net (
N
,
M
0
) with n places and m transitions. A set of conjunctive GMECs on (
N
,
M
0
), which is equivalent to c, can be expressed as(8)
⋀
j
=
1
n
c
∑
i
=
1
n
l
j
,
i
·
μ
i
≤
β
j
,where n
c is the number of the constraints, l
j
,
i’s are integers, and β
j is a nonnegative integer.Letc
j denote the jth constraint; that is, c
j
:
=
∑
i
=
1
n
‍
l
j
,
i
·
μ
i
≤
β
j. All admissible markings with respect to c, whose set is denoted by M
c, should be reachable. Thus, we have(9)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
M
l
∈
M
c
.A BFMM
k
∈
M
B decided by c is forbidden by c
j if(10)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
.Now, we introduce a set of variablesf
j
,
k’s (k
∈
N
B) to represent the relation between c
j and M
k in M
B. Then, (10) is modified to be(11)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,where Q is a positive integer constant that must be big enough and f
j
,
k
∈
{
0,1
} is a binary variable. In (11), f
j
,
k
=
1 indicates that M
k is forbidden by c
j and f
j
,
k
=
0 implies that M
k cannot be forbidden by c
j. For c
j, all constraints in the type of (11) for BFMs in M
B are grouped as:(12)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,
∀
M
k
∈
M
B
.In fact, the number of constraints, for example,n
c, to be computed is much less than that of the elements in M
B. Therefore, we can formulate an ILPP to find the minimal number of constraints. Now, by introducing variable h
j
∈
{
0,1
}  (
j
=
1,2
,
…
,
n
c
) for c
j, we have the following constraint(13)
f
j
,
k
≤
h
j
,
∀
k
∈
N
B
,where h
j
=
1 implies that c
j is selected and otherwise h
j
=
0. Equation (13) means that if c
j is not selected, it cannot forbid any BFM. For a BFM M
k, we also have(14)
∑
j
=
1
n
c
f
j
,
k
≥
1
.Equation (14) ensures that any BFM M
k in M
B must be forbidden by at least one constraint.As a result, we have the following ILPP to obtain the minimal number of conjunctive constraints, which is denoted as the minimal number of conjunctive constraints problem (MNCCP) as follows(15)
min
⁡
h
=
∑
k
=
1
n
c
h
j
(16)
subject  to
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
(17)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
-
Q
·
1
-
f
j
,
k
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
(18)
f
j
,
k
≤
h
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
k
∈
N
B
(19)
∑
j
=
1
n
c
f
j
,
k
≥
1
,
∀
k
∈
N
B
(20)
l
j
,
i
∈
Z
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
i
∈
1,2
,
…
,
n
f
j
,
k
∈
0,1
,
∀
k
∈
N
B
,
∀
j
∈
1,2
,
…
,
n
c
h
j
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
β
j
∈
0,1
,
2
,
…
,
∀
j
∈
1,2
,
…
,
n
c
.The objective functionh is used to minimize the number of constraints to be computed. Denote its optimal solution as h
∗. If MNCCP has an optimal solution, we can claim that the given constraint is equivalent to the minimal number h
∗ of linear constraints, as stated below.Theorem 8.
Given a Petri net model(
N
,
M
0
) and a nonlinear constraint c on it, if MNCCP has an optimal solution h
∗, then one can obtain the minimal number h
∗ of conjunctive GMECs that are equivalent to c with respect to (
N
,
M
0
).Proof.
By (16), each computed constraint does not forbid any admissible marking. By (17) and (19), every BFM is forbidden by at least one constraint. Thus, all forbidden markings are accordingly forbidden. Equation (18) ensures that only the selected constraints are used to forbid BFMs. In addition, the objective function ensures that the minimal number of constraints is selected. Since h represents the number of the selected constraints, the minimal number equals the optimal solution h
∗. In summary, the conclusion holds.For MNCCP, we need to set a proper initial value forn
c. In the worst case, we need to design a constraint for each BFM. Thus, we have 1
≤
n
c
≤
M
B. Suppose that MNCCP has an optimal solution with the minimal number of constraints and it is denoted as n
c
∗. If n
c is too small, that is, n
c
<
n
c
∗, MNCCP has no solution. In this case, we can increase n
c and solve MNCCP again. Therefore, the proper range for n
c is from n
c
∗ to M
B. If MNCCP has no solution for n
c
=
M
B, the proposed ILPP fails to find a set of conjunctive constraints that are equivalent to the given constraint. The closer the given n
c is to n
c
∗, the more efficient MNCCP becomes since it has less constraints and variables. Table 1 shows the number of constraints and variables in MNCCP.Table 1
The number of constraints and variables in MNCCP.
Constraint
Number of constraints
Variable
Number of variables
(16)
n
c
⋅
M
c
l
j
,
i
n
c
⋅
P
(17)
n
c
⋅
M
B
f
j
,
k
n
c
⋅
M
B
(18)
n
c
⋅
M
B
h
j
n
c
(19)
M
B
β
j
n
c
Total
n
c
⋅
M
c
+
2
M
B
+
M
B
Total
n
c
⋅
P
+
M
B
+
2


## 4.2. The Minimal Number of Disjunctive Constraints

If the admissible marking space with respect to a nonlinear constraintc is nonconvex, we cannot find a set of GMECs whose conjunctions are equivalent to c. However, if its BFMs space is convex, it is possible to find a set of GMECs whose disjunctions are equivalent to c. In the following, N
c denotes l
∣
M
l
∈
M
c. The disjunctions of GMECs can be written as(21)
⋁
j
=
1
n
c
∑
i
=
1
n
l
j
,
i
·
μ
i
≤
β
j
.Equation (21) indicates that at least one of the constraints must be satisfied. Hence, a marking is reachable if it satisfies at least one of the constraints. Any marking M
l
∈
M
c must be reachable. Therefore, we have(22)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
β
j
,
∀
M
l
∈
M
c
,
∃
j
∈
1,2
,
…
,
n
c
.Equation (22) cannot be directly considered as a constraint for an ILPP. Hence, we introduce a set of binary variables f
j
,
l’s (
f
j
,
l
∈
{
0,1
}
) to represent the relation between each marking M
l and the jth constraint. In particular, f
j
,
l
=
1 indicates that M
l satisfies the jth constraint and f
j
,
l
=
0 implies that M
l does not satisfy the jth constraint. Then, (22) is rewritten as(23)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
Q
·
1
-
f
j
,
l
+
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
,where Q is a positive constant that must be big enough. For (23), if f
j
,
l
=
1, it becomes ∑
i
=
1
n
‍
l
j
,
i
·
M
l
(
p
i
)
≤
β
j. If f
j
,
l
=
0, it is ∑
i
=
1
n
‍
l
j
,
i
·
M
l
(
p
i
)
≤
Q
+
β
j, implying that this constraint does not restrict l
j
,
i’s and β
j. Since M
l must satisfy at least one constraint, we have(24)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
j
∈
1,2
,
…
,
n
c
.A marking is forbidden if it is forbidden by every constraint. Any markingM
k
∈
M
B must be forbidden. Therefore, we have(25)
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
.We do not know how many constraints are needed. In the worst case, each admissible marking inM
c is associated with a constraint. That is to say, 1
≤
n
c
≤
M
c. In fact, the number of constraints to be computed is much less than the cardinality of M
c. Suppose that there are n
c constraints initially. Next, we select the minimal number of constraints from the n
c constraints. A variable h
j
(
h
j
∈
{
0,1
}, j
∈
1,2
,
…
,
n
c
) is introduced for the jth constraint and we have the following facts:(26)
f
j
,
l
≤
h
j
,
∀
l
∈
N
c
,
∀
j
∈
1,2
,
…
,
n
c
,where h
j
=
1 implies that the jth constraint is selected and h
j
=
0 indicates that the jth constraint is redundant and thus there is no need to add it as a constraint in (21). Equation (26) means that if the jth constraint is not selected, no admissible marking necessarily satisfies it. For any admissible marking M
l, we also have(27)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
l
∈
N
c
.Equation (27) ensures that any admissible marking M
l in M
c must satisfy at least one constraint.Finally, we formulate the following ILPP to find the minimal number of disjunctive GMECs that are equivalent to the given constraintc, which is denoted as the minimal number of disjunctive constraints problem (MNDCP).MNDCP is shown as follows:(28)
min
⁡
h
=
∑
j
=
1
n
c
h
j
(29)
subject  to
∑
i
=
1
n
l
j
,
i
·
M
k
p
i
≥
β
j
+
1
,
∀
M
k
∈
M
B
,
∀
j
∈
1,2
,
…
,
n
c
(30)
∑
i
=
1
n
l
j
,
i
·
M
l
p
i
≤
Q
·
1
-
f
j
,
l
+
β
j
,
∀
M
l
∈
M
c
,
∀
j
∈
1,2
,
…
,
n
c
(31)
∑
j
=
1
n
c
f
j
,
l
≥
1
,
∀
l
∈
N
c
(32)
f
j
,
l
≤
h
j
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
l
∈
N
c
(33)
l
j
,
i
∈
Z
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
i
∈
1,2
,
…
,
n
f
j
,
l
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
,
∀
l
∈
N
c
h
j
∈
0,1
,
∀
j
∈
1,2
,
…
,
n
c
β
j
∈
0,1
,
2
,
…
,
∀
j
∈
1,2
,
…
,
n
c
.The objective functionh is used to minimize the number of constraints that are selected. Denote its optimal value by h
∗. If MNDCP has an optimal solution, then we can find the minimal number h
∗ of disjunctive GMECs that are equivalent to the give nonlinear constraint, as stated below.Theorem 9.
Given a Petri net model(
N
,
M
0
) and a nonlinear constraint c, if MNDCP has an optimal solution h
∗, then we can obtain the minimal number h
∗ of disjunctive GMECs that are equivalent to c with respect to (
N
,
M
0
).Proof.
Equation (29) ensures that every obtained constraint can forbid all BFMs in M
B. Thus, no forbidden marking is reachable. According to (30) and (31), every marking in M
c satisfies at least one obtained constraint. Hence, the disjunctions of all obtained constraints, that is, (21), can make all admissible markings reachable. Finally, the objective function ensures that the minimal number of constraints is selected, that is, the optimal solution h
∗. In summary, the conclusion holds.Similar to MNCCP, we also need to set a proper initial value forn
c in MNDCP. In the worst case, we need to design a constraint for each admissible marking. Thus, we have 1
≤
n
c
≤
M
c. Suppose that MNDCP has an optimal solution with the minimal number of constraints. We denote the minimal number as n
c
∗. If n
c is too small, that is, n
c
<
n
c
∗, MNDCP has no solution. In this case, we can increase n
c and solve MNDCP again. Therefore, the proper range for n
c is from n
c
∗ to M
c. If MNDCP has no solution for n
c
=
M
c, the proposed ILPP fails to find a set of disjunctive constraints that are equivalent to the given constraint. The closer the given n
c is to n
c
∗, the more efficient the MNDCP becomes since it has less constraints and variables.As stated previously, the computational time for finding an optimal solution of an ILPP greatly depends on the number of the constraints and variables in it. Therefore, we provide the numbers of constraint and variables in MNDCP in Table2.Table 2
The numbers of constraints and variables in MNDCP.
Constraint
Number of constraints
Variable
Number of variables
(29)
n
c
⋅
M
B
l
j
,
i
n
c
⋅
P
A
(30)
n
c
⋅
M
c
f
j
,
l
n
c
⋅
M
c
(31)
M
c
h
j
n
c
(32)
n
c
⋅
M
c
β
j
n
c
Total
n
c
⋅
M
B
+
2
M
c
+
M
c
Total
n
c
⋅
P
A
+
M
c
+
2The disjunctions of GMECs cannot be directly implemented by designing a control place for each constraint by the PI-based method. However, one can find some existing approaches in [17, 18] that deal with disjunctive constraints in the framework of supervisory control. In this work, we do not recall it due to the limited space.


## 5. Examples for Nonlinear Constraints

In this section, a number of nonlinear constraints are considered to demonstrate the proposed approach.Example 1.
We consider a simple constraint to illustrate the proposed approach:(34)
μ
1
·
μ
1
+
μ
2
≤
4
.The admissible markings are shown in Table 3 and the set of BFMs is M
B
=
5
p
2
,
p
1
+
4
p
2
,
2
p
1
+
3
p
2
,
2
p
1
+
2
p
2
,
2
p
1
+
p
2
,
3
p
1. Its reachability space is shown in Figure 1(a). Then, we formulate an MNCCP for (34). Solving the MNCCP, we can obtain an optimal solution with two GMECs 3
μ
1
+
μ
2
≤
6 and μ
2
≤
4. The two GMECs are shown as two lines in Figure 1(a). It can be seen that the conjunctions of the two GMECs have the same admissible marking space as (34). That is to say, (34) is equivalent to the two GMECs. Two control places p
s
1 and p
s
2 are designed for the two constraints, respectively, as shown in Figure 1(b). It can be verified that the controlled net in Figure 1(b) is live with the 10 admissible markings as shown in Table 3.Table 3
Admissible markings for (34).
i
M
i
(
p
1
)
M
i
(
p
2
)
M
i
(
p
s
)
0
0
0
4
1
0
1
3
2
0
2
2
3
0
3
1
4
0
4
0
5
1
0
3
6
1
1
2
7
1
2
1
8
1
3
0
9
2
0
0Figure 1
(a) The reachability space forμ
1
⋅
μ
1
+
μ
2
≤
4 and (b) a supervisor obtained by equivalent GMECs.
(a)
(b)Example 2.
Consider nonlinear constraints:μ
1
·
μ
1
+
μ
2
≤
5, μ
1
·
μ
1
+
μ
2
≤
9, (
μ
1
-
2
)
·
(
μ
1
-
2
)
+
μ
2
≤
4, μ
1
·
μ
1
+
μ
2
·
μ
2
≤
16, and μ
1
-
2
+
μ
2
≤
4. The reachability spaces of the nonlinear constraints are shown in Figure 2, where the lines in each figure represent the equivalent GMECs. Table 4 provides the results, where the first column indicates the figures showing the reachability spaces of nonlinear constraints, the second column represents the nonlinear constraints, and the third column provides the minimal number of equivalent conjunctive GMECs.Table 4
Equivalent constraints for classical nonlinear constraints.
Figure
Nonlinear constraint
Equivalent GMECs
Figure1(a)
μ
1
⋅
μ
1
+
μ
2
≤
4
∧
3
μ
1
+
μ
2
≤
6
μ
2
≤
4
Figure2(a)
μ
1
⋅
μ
1
+
μ
2
≤
5
∧
3
μ
1
+
μ
2
≤
6
μ
2
≤
5
Figure2(b)
μ
1
⋅
μ
1
+
μ
2
≤
9
∧
5
μ
1
+
μ
2
≤
15
μ
1
+
μ
2
≤
9
Figure2(c)
μ
1
-
2
⋅
μ
1
-
2
+
μ
2
≤
4
∧
3
μ
1
-
μ
2
≤
12
-
3
μ
1
+
μ
2
≤
0
μ
2
≤
4
Figure2(d)
μ
1
⋅
μ
1
+
μ
2
⋅
μ
2
≤
16
∧
μ
1
+
2
μ
2
≤
8
2
μ
1
+
μ
2
≤
8
Figure2(e)
μ
1
-
2
+
μ
2
≤
4
∧
-
μ
1
+
μ
2
≤
2
μ
1
+
μ
2
≤
6Figure 2
Reachability spaces for classical nonlinear constraints.
(a)
μ
1
⋅
μ
1
+
μ
2
≤
5
(b)
μ
1
⋅
μ
1
+
μ
2
≤
9
(c)
(
μ
1
-
2
)
⋅
(
μ
1
-
2
)
+
μ
2
≤
4
(d)
μ
1
⋅
μ
1
+
μ
2
⋅
μ
2
≤
16
(e)
μ
1
-
2
+
μ
2
≤
4Figure 3
Reachability spaces for two nonlinear constraints.
(a)
max
⁡
(
μ
1
,
μ
2
)
+
μ
2
≤
4
(b)
min
⁡
(
μ
1
,
μ
2
)
+
μ
2
≤
4Example 3.
We show the results for two constraintsc
1: max
⁡
(
μ
1
,
μ
2
)
+
μ
2
≤
4 and c
2: min
⁡
(
μ
1
,
μ
2
)
+
μ
2
≤
4. It can be seen that the admissible marking space with respect to c
1 is convex but that with respect to c
2 is nonconvex. In this case, we can find a set of conjunctive GMECs that are equivalent to c
1 and a set of disjunctive GMECs that are equivalent to c
2. The results are shown in Table 5.Table 5
Equivalent constraints for two nonlinear constraints.
Figure
Nonlinear constraint
Equivalent GMECs
Figure3(a)
max
⁡
μ
1
,
μ
2
+
μ
2
≤
4
∧
μ
1
+
μ
2
≤
4
μ
2
≤
2
Figure3(b)
min
⁡
μ
1
,
μ
2
+
μ
2
≤
4
∨
μ
1
+
μ
2
≤
4
μ
2
≤
2Example 4.
A flexible manufacturing system is shown in Figure4(a). It consists of robot R that can hold one part at a time, two machines M
1 and M
2, each of which can process one part at a time, two loading buffers I
1 and I
2, and two unloading buffers O
1 and O
2. Two part types are considered in the system: P
1 and P
2. The production sequences are shown in Figure 4(b). The Petri net model of the system is depicted in Figure 5(a). The model has 20 reachable markings. Suppose that the control specification (deadlock control) can be represented as a nonlinear constraint c: (
μ
2
+
μ
3
+
2
)
2
+
(
μ
5
+
μ
6
+
2
)
2
≤
17. Then, there are 15 admissible markings and five BFMs. We formulate an MNCCP for c. By solving the MNCCP, we can obtain an optimal solution with two GMECs 2
μ
2
+
μ
5
+
μ
6
≤
2 and μ
3
+
μ
5
≤
1. Two control places p
s
1 and p
s
2 are designed for the two GMECs, respectively, as shown in Figure 5(b). It can be verified that the controlled net in Figure 5(b) is live with the 15 admissible markings. That is to say, the nonlinear constraint c is equivalent to the two GMECs.Figure 4
(a) A flexible manufacturing system and (b) its production sequences.
(a)
(b)Figure 5
(a) A Petri net model and (b) the controlled net model.
(a)
(b)


## 6. Conclusions

This paper deals with the enforcement of the nonlinear constraints on Petri nets. Two ILPPs are proposed, one is to obtain the minimal number of GMECs whose conjunctions are equivalent to a given nonlinear constraint if its admissible markings space is convex and the other is to obtain the minimal number of GMECs whose disjunctions are equivalent to a given nonlinear constraint if its admissible markings space is nonconvex but its forbidden markings space is convex. The two ILPPs require to generate all the admissible markings and BFMs for a given constraint, which are not efficient for large-sized problems. In the future, we will focus on the computational efficiency.



---

*Source: 640917-2015-09-16.xml*