Supervisory Controller Design to Enforce Desired Properties in
Systems Modeled by Timed-arc Petri Nets
ALTUĞ İFTAR
Department of Electrical and Electronics Engineering
Eskişehir Technical University
26555 Eskişehir, TURKEY
Abstract: - Discrete-event systems which are modelled by timed-arc Petri nets are considered. A
supervisory controller design approach for such systems for enforcing some desired properties is
proposed. For the representation of the state of the system, the proposed design approach uses
stretching. The designed controller enforces ˆ
L-boundedness (for any given bound vector ˆ
L) and
reversibility simultaneously, whenever it is possible to design such a controller. Furthermore, ∆-liveness
is also enforced, where ∆is the largest possible subset of the set of transitions for which it is possible to
design such a controller. Furthermore, the designed controller is maximally permissive in the sense that
no transitions are disabled unnecessarily and the reachability set of the controlled system is the largest
possible set in which boundedness and reversibility can be enforced simultaneously. To demonstrate the
proposed approach, an example controller design is also presented for an automated manufacturing system.
Key-Words: - Discrete-event Systems, Timed-arc Petri Nets, Supervisory Controller Design, Boundedness,
Reversibility, Liveness, Manufacturing Systems, Automation
Received: April 28, 2023. Revised: February 26, 2024. Accepted: April 9, 2024. Published: May 29, 2024.
1 Introduction
Many discrete-event systems (DES) can be mod-
elled using Petri nets, [1], [2]. Early models of Petri
nets did not include the notion of time. However,
later it became apparent that this notion is needed
to appropriately model many DES, and timed
Petri nets (TPNs) were introduced to describe the
evolution of these systems throughout time, [3],
[4], [5], [6], [7], [8], [9]. A TPN, besides the basic
elements of an untimed Petri net, also includes
certain time-delays. In a Petri net time-delays can
be included in the transitions, [10], [11], [12], or in
the places, [13]. In a Petri net model, transitions
and places respectively represent the events and
the resources. Therefore, the time needed for an
event to occur may be represented by a time-
delay in the corresponding transition and the time
needed for a resource to become available may be
represented by a time-delay in the corresponding
place. Thus, when both events and resources may
require certain times, one may need a TPN model
where both the transitions and the places are
timed, [14]. However, as discussed in [15], even
this formalism may not be sucient. To overcome
this problem, rather than transitions and places,
time-delays can be included in the arcs, [16]. A
Petri net in which arcs are timed is called a timed-
arc Petri net (TAPN), [15].
The representation of the state of any dynamic
system is necessary in order to simulate it or to
design a controller for it. The marking vector is
sucient to represent the state of an untimed
Petri net. However, this is not sucient for a
TPN, [16]. To overcome this diculty, the method
of stretching was rst introduced for Petri nets in
which the transitions are timed, [17], and then
for Petri nets in which the places are timed, [18].
Petri nets in which both the transitions and places
are timed are then considered in [14]. Finally, the
method of stretching was introduced for TAPNs
in [15].
Supervisory control is needed for DES to avoid
undesirable behaviour, such as deadlock, [19], or
to enforce desirable behaviour, such as bounded-
ness, reversibility, and/or liveness, [20]. Controller
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
158
Volume 19, 2024
design to avoid deadlock for various types of
TPNs were considered in [10], [13], [15], and to
enforce some desirable properties were considered
in [21], [22], [23]. In the present work, we consider
supervisory controller design in TAPNs in order
to enforce boundedness, reversibility, and liveness.
As in previous works, we assume that a suitable
time unit can be found which divides (at least
approximately) all the process delays. This unit
is then taken as the unit of time and all the time-
delays are thus become an integer. Furthermore,
the time variable, denoted by t, is also taken as
integer and the initial time is assumed to be t= 0.
We present the necessary preliminaries in Sec-
tion 2. The proposed supervisory controller design
approach is presented in Section 3. An example
of an automated manufacturing system and con-
troller design for it are presented in Section 4.
Finally, some concluding remarks are included in
Section 5.
Throughout the paper, Zdenotes the set of
non-negative, and Z+denotes the set of positive
integers. For two vectors with the same dimension,
xand y,x≥y(x≤y) indicates that each
element of xis greater (less) than or equal to
the corresponding element of y. For a vector x,
xTdenotes its transpose. The number of elements
of a set Ωis denoted by |Ω|and its jth element
(j= 1, . . . , |Ω|) is denoted by [Ω]j.
2 Preliminaries
2.1 Timed-Arc Petri Nets
As presented in [15], A TAPN is a tuple H=
(Π,Θ, A, B, S0,DN,DO), where Πdenotes the
set of places, Θdenotes the set of transitions,
A: Π ×Θ→Zis the matrix which indicates
the weights of the arcs from places to transitions,
B: Π ×Θ→Zis the matrix which indicates
the weights of arcs from transitions to places (as
usual, a zero entry in Aor Bmeans there is no arc
between the corresponding place and transition),
S0: Π →Zindicates the initial number of
tokens at each place. DN:AN→Zindicates
the time-delays of the input arcs, where AN:=
{(π, θ)|A(π, θ)>0}is the set of input arcs, and
DO:AO→Z+indicates the time-delays of the
output arcs, where AO:= {(θ, π)|B(π, θ)>0}is
the set of output arcs. Note that, the time-delay of
an input arc may be zero or positive, however, the
time-delay of an output arc must be positive. This
is because, in a Petri net places usually correspond
to resources and transitions usually correspond to
events. While a resource may be readily available
for any event, the execution of any event always
takes some time.
A TAPN can be shown graphically as in Fig. 1.
In all the gures, circles correspond to places,
bars correspond to transitions, and the arrows
correspond to arcs. “w=. . .” next to an arc
species the weight of that arc and “τ=. . .”
species the time-delay of that arc. To simplify
graphics, however, a unity weight is not explicitly
shown. Similarly, a unit time-delay for an output
arc and a zero time-delay for an input arc are also
not explicitly shown. Finally, the tokens present
in a place at the initial time are shown by dots
inside the corresponding circle.
Therefore, for the TAPN shown in Fig. 1, we
have Π = {π1, π2, π3},Θ = {θ1, θ2, θ3},
A=
110
001
001
, B =
002
100
010
,
S0=200T,
AN={(π1, θ1),(π1, θ2),(π2, θ3),(π3, θ3)},AO=
{(θ1, π2),(θ2, π3),(θ3, π1)},DN={0,2,3,2}, and
DO={2,1,3}.
2.2 Arc Stretched Petri Nets
To simplify the representation of the state of a
TAPN, the method of arc stretching was rst
introduced in [15]. In this method, a so-called
arc stretched Petri net (ASPN) is dened for any
given TAPN. To construct the ASPN, let us rst
decompose ANand AOinto, respectively, A1
N
and A2
Nand A1
Oand A2
O, where A1
N:= {a∈
AN| DN(a) = 0},A2
N:= {a∈ AN| DN(a)≥1},
A1
O:= {a∈ AO| DO(a) = 1},A2
O:= {a∈
AO| DO(a)≥2}. Then, the ASPN is constructed
as follows:
I) for any a= (π, θ)∈ A2
N,
i) DN(a)new places πa
1,πa
2,. . .,πa
DN(a),
and DN(a)new transitions, θa
1,θa
2,. . .,
θa
DN(a), are dened.
ii) arc a, which goes from πto θ, now goes
from πto θa
1; the time-delay of abecomes
zero; its weight remains the same.
iii) DN(a)new input arcs, from πa
1to θa
2,
. . ., from πa
DN(a)−1to θa
DN(a), and from
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
159
Volume 19, 2024


• •
?


?
@@@
@R
?


?
?
π1
θ1
π2
θ2
π3
θ3
τ= 2
τ= 3
τ= 2
τ= 2
τ= 3
w= 2
Fig. 1. Example TAPN.
πa
DN(a)to θ, are dened each having unit
weight and zero time-delay.
iv) DN(a)new output arcs, from θa
1to πa
1,
. . ., from θa
DN(a)−1to πa
DN(a)−1, and from
θa
DN(a)to πa
DN(a), are dened each having
unit weight and unit time-delay.
II) for any a= (θ, π)∈ A2
O,
i) DO(a)−1new places πa
1,πa
2,. . .,
πa
DO(a)−1, and DO(a)−1new transitions,
θa
1,θa
2,. . .,θa
DO(a)−1, are dened.
ii) arc a, which goes from θto π, now goes
from θa
DO(a)−1to π; the time-delay of a
becomes unity; its weight remains the
same.
iii) DO(a)−1new input arcs, from πa
1to θa
1,
from πa
2to θa
2,. . ., and from πa
DO(a)−1to
θa
DO(a)−1, are dened each having unit
weight and zero time-delay.
iv) DO(a)−1new output arcs, from θto πa
1,
from θa
1to πa
2,. . ., and from θa
DO(a)−2to
πa
DO(a)−1, are dened each having unit
weight and unit time-delay.
Usig the above procedure, for the TAPN shown
in Fig. 1, the ASPN shown in Fig. 2 is constructed.
In the ASPN, ring of θa
1, for any a= (π, θ)∈ A2
N,
is equivalent to the ring of θ. Furthermore, θa
2,
. . .,θa
DN(a), and θres immediately as it becomes
enabled. Moreover, for any a= (θ, π)∈ A2
O,
θa
1,θa
2,. . .,θa
DO(a)−1also res immediately as it
becomes enabled. We let ˜
Θdenote the set of those
transitions which are to re immediately as they


• •
?


?
?


?
?


?
?


?
?


?
@@@
@R
?


?
?


?
?


?
?


?
?


?
6


6
6


6
?
π1
θ1
π(θ1,π2)
1
θ(θ1,π2)
1
π2
θ(π2,θ3)
1
π(π2,θ3)
1
θ(π2,θ3)
2
π(π2,θ3)
2
θ(π2,θ3)
3
π(π2,θ3)
3
θ3
θ(π1,θ2)
1
π(π1,θ2)
1
θ(π1,θ2)
2
π(π1,θ2)
2
θ2
π3
θ(π3,θ3)
1
π(π3,θ3)
1
θ(π3,θ3)
2
π(π3,θ3)
2
π(θ3,π1)
1
θ(θ3,π1)
1
π(θ3,π1)
2
θ(θ3,π1)
2
w= 2
Fig. 2. ASPN for the Example TAPN.
become enabled. The number of tokens initially
present in a place in the original Petri net is not
changed, but the initial number of tokens in any
one of the newly introduced places is dened as
zero.
The ASPN is a tuple ˆ
H= ( ˆ
Π,ˆ
Θ,˜
Θ,ˆ
A, ˆ
B, ˆ
S0),
where ˆ
Πconsist of all the places in Πand
the places which are introduced by the above
procedure; ˆ
Θ, consist of all the transitions in Θ
and the transitions which are introduced by the
above procedure; ˜
Θ⊂ˆ
Θis the set of transitions
which are to re immediately as they become
enabled. The elements of the input matrix, ˆ
A,
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
160
Volume 19, 2024
are given as
ˆ
A(π, θ) =
A(π, θ),if π∈Π
1,if π=πa
land θ=θa
l+1 for
some a∈ A2
Nwith
DN(a)≥2and
l= 1, . . . , DN(a)−1
1,if π=πa
DN(a)and θ=˜
θ
for some a= (˜π, ˜
θ)∈ A2
N
1,if π=πa
land θ=θa
lfor
some a∈ A2
Oand
l= 1, . . . , DO(a)−1
0,otherwise
and the elements of the output matrix, ˆ
B, are
given as
ˆ
B(π, θ) =
B(π, θ),if (θ, π)∈ A1
O
B(π, ˜
θ),if π∈Πand θ=θa
DO(a)−1
for some a= (˜
θ, π)∈ A2
O
1,if π=πa
1and θ=˜
θ
for some a= (˜
θ, ˜π)∈ A2
O
1,if π=πa
l+1 and θ=θa
lfor
some a∈ A2
Owith
DO(a)≥3and
l= 1, . . . , DO(a)−2
1,if π=πa
land θ=θa
lfor
some a∈ A2
Nand
l= 1, . . . , DN(a)
0,otherwise
Finally, the initial marking vector, ˆ
S0, is given as
ˆ
S0(π) = S0(π),if π∈Π
0,otherwise
Note that, since all the input arcs of ASPN have
zero time-delay and all the output arcs have
unit time-delay, there is no need for any explicit
information about the time-delays in ˆ
H.
In general, the number of places, transitions,
and arcs of the ASPN is more than the number of
places, transitions, and arcs of the original TAPN.
However, the state of the ASPN at any time t∈
Zis solely and uniquely given by the marking
vector ˆ
S(t)at time t. Also, the state of the original
TAPN can be dened using the state of the ASPN.
Furthermore, starting with ˆ
S(0) = ˆ
S0, the state
of the ASPN evolves according to the equation
ˆ
S(t+ 1) = ˆ
S(t) +
θ∈f(t)ˆ
B(θ)−ˆ
A(θ)(1)
where f(t)denotes the set of transitions that re
at time tand ˆ
A(θ)and ˆ
B(θ)denote the columns
of respectively ˆ
Aand ˆ
B, that correspond to the
transition θ. The set of transitions f(t), however,
can re at time t, only if f(t)∈ E(ˆ
S(t)), where
E(σ) :=
f⊂ˆ
Θ|σ≥
θ∈f
ˆ
A(θ)
.(2)
is the set of sets of simultaneously enabled transi-
tions at state σ. Furthermore, the set of enabled
transitions at state σis given as:
ϵ(σ) := θ∈ˆ
Θ|σ≥ˆ
A(θ).(3)
2.3 Boundedness, Reversibility, and Liveness
The set of all reachable states. Σ(H), of a
TAPN Hfrom its initial state S0is called as its
reachability set. As mentioned above, it is rather
complicated to describe the state of a TAPN,
which makes the description of its reachability
set also complicated. However, the state of the
ASPN ˆ
H, can simply be described by its marking
vector. Thus, the reachability set, Σ( ˆ
H), of the
ASPN ˆ
Hcan easily be described as the set of all
the markings ˆ
S, such that there exists a sequence
of enabled transitions which lead from the initial
marking ˆ
S0to ˆ
S. Moreover, there is a one-to-one
correspondence between the states of ˆ
Hand of
H, thus, between Σ( ˆ
H)and Σ(H), [15].
Most desirable properties for a system mod-
elled by a TAPN are boundedness, reversibility,
and liveness. For a bound vector L: Π →Z, a
TAPN His said to be L-bounded if S(π)≤L(π),
∀π∈Π, for all markings Scorresponding to every
state in Σ(H).His said to be bounded if it is
L-bounded for some bounded L.His said to
be reversible if for every state S∈Σ(H), there
exists a sequence of enabled transitions which lead
from Sto the initial state. θ∈Θis said to be
live if for every state S∈Σ(H), there exists a
sequence of enabled transitions which lead from
Sto S′∈Σ(H)such that θis enabled at S′. For
∆⊂Θ,His said to be ∆-live if every θ∈∆is
live. Finally, His said to be live if it is Θ-live.
3 Supervisory Controller Design
A supervisory controller design approach is pre-
sented in this section in order to enforce bound-
edness, reversibility and liveness in a system mod-
elled by a TAPN. Our approach is to rst design a
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
161
Volume 19, 2024
controller for the ASPN, since it is much easier to
represent the state of the TAPN using its ASPN.
Once a controller which enforces boundedness,
reversibility and liveness in the ASPN ˆ
His ob-
tained, this controller also enforces boundedness,
reversibility and liveness in the original TAPN
H, since, due to the one-to-one correspondence
between the states of the ASPN ˆ
Hand of the
original TAPN H,
•His bounded if and only if ˆ
His bounded.
•His reversible if and only if ˆ
His reversible.
•His live if and only if ˆ
His live.
In order to design a controller for the ASPN,
we rst determine its bounded reachability set,
ΣB, for a given bound vector ˆ
L:ˆ
Π→Z.ΣBis
the largest subset of Σ( ˆ
H)such that any ˆ
S∈ΣB
is bounded by ˆ
L(i.e., ˆ
S(π)≤ˆ
L(π),∀π∈ˆ
Π)
and can be reached from ˆ
S0by passing through
only states which are bounded by ˆ
L. We note
that, for any Petri net, ΣBalways has nitely
many elements, even though Σ( ˆ
H)may have
innitely many elements for an unbounded Petri
net, [20]. Algorithm 1, which is borrowed from
[23], constructs ΣB. The inputs to this algorithm
are the ASPN denition ˆ
Hand the bound vector
ˆ
L. The function ˜
E(σ), used in Algorithm 1,
returns the set of sets of simultaneously enabled
transitions at state σ, excluding those sets which
do not include any enabled transition which must
re immediately as it becomes enabled (thus any
θ∈˜
Θalways res immediately as it becomes
enabled). Thus:
˜
E(σ) := E(σ)\f∈ E(σ)|θ /∈f
for some θ∈ϵ(σ)∩˜
Θ,(4)
where E(·)is given by (2) and ϵ(·)is given by (3).
Furthermore, the function
ν(σ, f) := σ+
θ∈fˆ
B(θ)−ˆ
A(θ)(5)
returns the next state, as given by (1), when f
res at σ. If ˆ
S0(π)>ˆ
L(π), for some π∈ˆ
Π,
i.e., if ˆ
His not ˆ
L-bounded at the initial time,
Algorithm 1 returns an empty set for ΣB. In this
case, no controller can enforce ˆ
L-boundedness.
Following the construction of ΣB(assuming
ΣB=∅), Algorithm 2, which is also borrowed
Algorithm 1 : Algorithm to construct ΣB
Inputs: ˆ
H= ( ˆ
Π,ˆ
Θ,˜
Θ,ˆ
A, ˆ
B, ˆ
S0)and ˆ
L
Output: ΣB
if ˆ
S0≤ˆ
Lthen
ΣB= Σ1={ˆ
S0}
loop
Σ2=∅
for j= 1 to |Σ1|do
σ= [Σ1]j
Φ = ˜
E(σ)
for k= 1 to |Φ|do
ϕ= [Φ]k,ˆσ=ν(σ, ϕ)
if ˆσ /∈(Σ2∪ΣB)and ˆσ≤ˆ
Lthen
Σ2←Σ2∪ {ˆσ}
end if
end for
end for
if Σ2== ∅then
exit loop
end if
ΣB←ΣB∪Σ2
Σ1= Σ2
end loop
else
ΣB=∅
end if
return ΣB
from [23], constructs the bounded reversible reach-
ability set, ΣS.ΣSis the largest subset of ΣB
such that for any ˆ
S∈ΣSeither ˆ
S=ˆ
S0or ˆ
S
can be reached from ˆ
S0and ˆ
S0can be reached
from ˆ
Swithout passing through any markings
outside ΣS. The inputs to Algorithm 2 are the
ASPN denition ˆ
Hand the bounded reachability
set ΣB, as constructed by Algorithm 1. Besides
ΣS, this algorithm also returns the set of all live
transitions, ˆ
∆. Here, functions ˜
Eand νare as in
Algorithm 1 and the function ϵ(σ), which is given
by (3), returns the set of enabled transitions at
state σ.
To enforce ˆ
L-boundedness and reversibility
simultaneously for the ASPN, a controller must
keep the state of the ASPN within the bounded
reversible reachability set, ΣS. Such a controller
can be described as:
γ(σ, f) := 1,if ν(σ, f)∈ΣS
0,otherwise ,(6)
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
162
Volume 19, 2024
Algorithm 2 : Algorithm to determine ΣSand ˆ
∆
Inputs: ˆ
H= ( ˆ
Π,ˆ
Θ,˜
Θ,ˆ
A, ˆ
B, ˆ
S0)and ΣB
Outputs: ΣSand ˆ
∆
ΣX= ΣB,ˆ
∆ = ∅
Start: Σ′= ΣX\ { ˆ
S0},ΣS={ˆ
S0}
loop
Σ = Σ′,F lg = 0
for j= 1 to |Σ|do
¯σ= [Σ]j,Φ = ˜
E(¯σ)
for k= 1 to |Φ|do
ϕ= [Φ]k,ˆσ=ν(¯σ, ϕ)
if ˆσ∈ΣSthen
ΣS←ΣS∪ {¯σ},Σ′←Σ′\ {¯σ},
F lg = 1, go to Break
end if
end for
Break: continue
end for
if F lg == 0 then
exit loop
end if
end loop
if ΣS== {ˆ
S0}then
go to Finish
end if
ΣR=∅,Σa={ˆ
S0}
loop
Σb=∅,ΣR←ΣR∪Σa
for j= 1 to |Σa|do
¯σ= [Σa]j,Φ = ˜
E(¯σ)
for k= 1 to |Φ|do
ϕ= [Φ]k,ˆσ=ν(¯σ, ϕ)
if ˆσ∈ΣSand ˆσ /∈ΣR∪Σbthen
Σb←Σb∪ {ˆσ}
end if
end for
end for
if Σb== ∅then
exit loop
end if
Σa= Σb
end loop
if ΣS= ΣRthen
ΣX= ΣR, go to Start
end if
for j= 1 to |ΣS|do
¯σ= [ΣS]j,∆1=ϵ(¯σ)
for k= 1 to |∆1|do
θ= [∆1]k
if ν(¯σ, {θ})∈ΣSthen
ˆ
∆←ˆ
∆∪ {θ}
end if
end for
end for
Finish: return ΣS,ˆ
∆
for any σ∈ΣSand for any f∈˜
E(σ). Here, the
controller (6) disables the ring of fat state σ
if γ(σ, f)=0and does not disable the ring of
fat state σif γ(σ, f)=1. This controller also
enforces ˆ
∆-liveness, where ˆ
∆is as returned by
Algorithm 2. Thus, if ˆ
∆ = ˆ
Θ, then controller (6)
enforces ˆ
L-boundedness, reversibility, and liveness
simultaneously. Otherwise, ˆ
∆is the largest subset
of ˆ
Θsuch that a controller exists which enforces ˆ
L-
boundedness, reversibility, and ˆ
∆-liveness simul-
taneously.
4 Example
We consider an automated manufacturing system
example which is a modied version of the ex-
ample presented in [14]. The system consists of
three machines and three stores. Machines 1 and
2 obtain parts put on one of the two transporters
at store 1, work on them and send them to stores
2 and 3, respectively. Machine 3 obtain one part
from store 2 and one part from store 3, produce
the nal product and return the transporters to
store 1. Machine 1 can receive a part from store
1 with no time-delay. It can deliver its product to
store 2 in two time units. Machine 2 can receive
a part from store 1 within two time units and
can deliver its product to store 3 in one time
unit. Machine 3 needs 3 time units to receive a
product from store 2 and 2 time units to receive
a product from store 3. It can deliver the end
product and return both transporters to store 1
in 3 time units.
A TAPN model of this system is shown in
Fig. 1, where π1,π2, and π3, represent stores
1, 2, and 3, respectively, and θ1,θ2, and θ3,
represent processing by the machines 1, 2, and 3,
respectively. The ASPN for this TAPN is shown
in Fig. 2.
Our aim is to design a controller to enforce ˆ
L-
boundedness for ˆ
L(π)=2,∀π∈ˆ
Π, reversibility,
and liveness simultaneously. Algorithm 1 returns
the bounded reachability set, ΣB, which consists
of 62 states (including the initial state ˆ
S0=σ0).
Algorithm 2 then eliminates 24 of these states,
since it is not possible to reach to ˆ
S0from any
one of these states. The remaining 38 states,
which form the bounded reversible reachability
set ΣS, are shown in Table 1, where the or-
dering of the places is as follows: π1,π(θ1,π2)
1,
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
163
Volume 19, 2024
Table 1. Bounded reversible reachability set, ΣS.
σ0=[2000000000000]T
σ1=[1100000000000]T
σ2=[1000001000000]T
σ3=[0100001000000]T
σ4=[1010000000000]T
σ6=[0010001000000]T
σ7=[1000000100000]T
σ8=[0100000100000]T
σ10 =[0010000100000]T
σ11 =[1001000000000]T
σ13 =[0001001000000]T
σ16 =[0001000100000]T
σ17 =[1000000010000]T
σ18 =[0100000010000]T
σ20 =[0010000010000]T
σ22 =[0001000010000]T
σ23 =[1000100000000]T
σ25 =[0000101000000]T
σ27 =[0000100100000]T
σ29 =[0000100010000]T
σ30 =[1000000001000]T
σ31 =[0100000001000]T
σ33 =[0010000001000]T
σ35 =[0001000001000]T
σ38 =[0000100001000]T
σ39 =[1000010000000]T
σ41 =[0000011000000]T
σ43 =[0000010100000]T
σ45 =[0000010010000]T
σ47 =[0000010001000]T
σ48 =[1000000000100]T
σ49 =[0100000000100]T
σ51 =[0010000000100]T
σ53 =[0001000000100]T
σ55 =[0000100000100]T
σ57 =[0000010000100]T
σ60 =[0000000000010]T
σ61 =[0000000000001]T
π2,π(π2,θ3)
1,π(π2,θ3)
2,π(π2,θ3)
3,π(π1,θ2)
1,π(π1,θ2)
2,π3,
π(π3,θ3)
1,π(π3,θ3)
2,π(θ3,π1)
1,π(θ3,π1)
2. Algorithm 2 also
returns ˆ
∆ = ˆ
Θ, which means that as long as the
states are restricted to ΣS, all the transitions are
live.
The controller described by (6) then disables
θ1at states σ1,σ4,σ11,σ23, and σ39 and disables
θ(π1,θ2)
1at states σ2,σ7,σ17,σ30, and σ48, since
ring θ1at states σ1,σ4,σ11,σ23, or σ39 or ring
θ(π1,θ2)
1at states σ2,σ7,σ17,σ30, or σ48 leads to
a state not in ΣS. Since ring θ1in the ASPN is
equivalent to ring θ1in the original TAPN and
ring θ(π1,θ2)
1in the ASPN is equivalent to ring θ2
in the original TAPN, a controller which disables
θ1at states σ1,σ4,σ11,σ23, and σ39 and disables
θ2at states σ2,σ7,σ17,σ30, and σ48, enforces
boundedness, reversibility and liveness simultane-
ously in the original TAPN. This controller also
avoids deadlock, since deadlock can not occur in
a live Petri net, [24].
5 Conclusions
Supervisory controller design to enforce some de-
sired properties, namely boundedness, reversibil-
ity, and liveness in DES modelled by TAPNs has
been considered. Since it is very complicated to
represent the state of a TAPN, the approach of
stretching has been used to obtain the ASPN
of the given TAPN. Since it is much easier to
represent the state of the ASPN and there is a one-
to-one corresponce between the states of the two
Petri nets, an approach to design a controller rst
for the ASPN and then obtain a controller for the
original TAPN is proposed. Algorithms to design
such a controller have been presented. These
algorithms terminate in nite time. Algorithm 1’s
computational complexity is proportional to the
size of the bounded reachability set, ΣB. Algo-
rithm 2’s computational complexity is no more
than the square of the size of ΣB. Therefore, the
computational complexity of the overall design
approach is no more than the square of the size
of ΣB.
For a given bound vector ˆ
L, the designed
controller, (6), enforces ˆ
L-boundedness and re-
versibility simultaneously, whenever it is pos-
sible to design such a controller. Furthermore,
the designed controller also enforces ∆-liveness,
where ∆is the largest possible such subset of
Θ. Thus, boundedness, reversibility, and liveness
are enforced simultaneously whenever possible.
Furthermore, the designed controller is maximally
permissive in the sense that no transitions are
disabled unnecessarily and the reachability set of
the controlled system is the largest possible set
in which boundedness and reversibility can be
enforced simultaneously.
We have used the so-called behavioral ap-
proach, [24], [25], in the controller design. Al-
though behavioral approach is more tedious than
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
164
Volume 19, 2024
the so-called structural approach, [26], [27], it
can guarantee the design of maximally permissive
controllers; whereas the structural approach, in
general, produces conservative controllers, [26].
DES are getting more complicated each day,
[28], [29]. Some of such systems are so complicated
that it may not be possible to design a central-
ized controller for them. Therefore, as a future
study, the present approach can be extended to
decentralized supervisory controller design, which
would be possible along the lines of [30].
References
[1] M. Zhou and F. DiCesare, Petri Net Synthesis for
Discrete Event Control of Manufacturing Systems.
Norwell, MA: Kluwer Academic Publishers, 1993.
[2] J. Proth and X. Xie, Petri Nets: A Tool for Design
and Management of Manufacturing Systems. West
Sussex: John Wiley & Sons, 1996.
[3] F. D. J. Bowden, “A brief survey and synthesis of
the roles of time in Petri nets,” Mathematical and
Computer Modelling, vol. 31, pp. 55–68, 2000.
[4] J. Wang, Timed Petri Nets: Theory and Application.
Boston, MA: Kluwer Academic, 1998.
[5] W. M. Zuberek, “Timed Petri nets in modeling
and analysis of cluster tools,” IEEE Transactions on
Robotics and Automation, vol. 17, pp. 562–575, 2001.
[6] L. Popova-Zeugmann, Time and Petri Nets. New
York: Springer, 2013.
[7] L. Liang, F. Basile, and Z. Li, “A reduced computa-
tion of state space to enforce GMECs and deadlock-
freeness on TPN systems,” in IFAC PapersOnLine
53-4, pp. 166–172, 2020.
[8] S. Akshay, L. Helouet, and R. Phawade, “Combining
free choice and time in Petri nets,” Journal of Logical
and Algebraic Methods in Programming, vol. 101,
2020.
[9] D. Lefebvre and C. Daoui, “Control design for
bounded partially controlled TPNs using timed ex-
tended reachability graphs and MDP,” IEEE Trans-
actions on Systems, Man, and Cybernetics, vol. 50,
no. 6, pp. 2273–2283, 2020.
[10] A. Aybar, et.al., “Deadlock avoidance controller de-
sign for timed Petri nets using stretching,” IEEE
Systems Journal, vol. 2, pp. 178–188, 2008.
[11] G. J. Tsinarakis, N. C. Tsourveloudis, and K. P.
Valavanis, “Modeling, analysis, synthesis, and per-
formance evaluation of multioperational production
systems with hybrid timed Petri nets,” IEEE Trans.
on Automation Science and Engineering, vol. 3, no. 1,
pp. 29–46, 2006.
[12] M. Vatani and A. Doustmohammadi, “Decomposition
of rst-order hybrid Petri nets for hierarchical control
of manufacturing systems,” Journal of Manufacturing
Systems, vol. 35, pp. 206–214, 2015.
[13] A. Aybar, et.al., “Supervisory controller design
for timed-place Petri nets,” Kybernetika, vol. 48,
pp. 1114–1135, 2012.
[14] A. İftar, “Supervisory control of manufacturing sys-
tems modeled by timed Petri nets,” in Proceedings
of the 12th IFAC Workshop on Intelligent Manufac-
turing Systems, (Austin, TX, U.S.A.), pp. 128–132,
Dec. 2016.
[15] A. Aybar, et.al., “Supervisory control of discrete-
event systems modeled by timed-arc Petri nets,” in
Proceedings of the European Control Conference,
(Saint Petersburg, Russia), pp. 656–661, May 2020.
[16] C. Lakos and L. Petrucci, “Modular state space ex-
ploration for timed Petri nets,” International Journal
on Software Tools for Technology Transfer, vol. 9,
pp. 393–411, 2007.
[17] A. Aybar, et.al., “Supervisory controller design for
timed Petri nets,” in Proceedings of the IEEE In-
ternational Conference on System of Systems Engi-
neering, (Los Angeles, CA, U.S.A.), pp. 59–64, Apr.
2006.
[18] A. Aybar, et.al., “Representation of the state of
timed-place Petri nets using stretching,” in Proceed-
ings of the 4th IFAC Workshop on Discrete-Event
System Design, (Playa de Gandia, Spain), pp. 79–84,
Oct. 2009.
[19] Z. W. Li, M. C. Zhou, and N. Q. Wu, “A survey and
comparison of Petri net-based deadlock prevention
policies for exible manufacturing systems,” IEEE
Transactions on Systems, Man, and Cybernetics–Part
C, vol. 38, pp. 173–188, 2008.
[20] A. Aybar, et.al., “Centralized and decentralized su-
pervisory controller design to enforce boundedness,
liveness, and reversibility in Petri nets,” International
Journal of Control, vol. 78, pp. 537–553, 2005.
[21] A. Aybar, et.al., “Supervisory controller design to en-
force some basic properties in timed-transition Petri
nets using stretching,” Nonlinear Analysis: Hybrid
Systems, vol. 6, pp. 712–729, 2012.
[22] A. Aybar, et.al., “Supervisory controller design to
enforce basic properties in timed-place Petri nets,”
in Preprints of the 6th IFAC Conference on Man-
agement and Control of Production and Logistics,
(Fortaleza, Brazil), pp. 486–492, Sept. 2013.
[23] A. İftar, “Supervisory controller design to enforce
boundedness, reversibility and liveness in systems
modeled by timed Petri nets,” WSEAS Transactions
on Systems, vol. 22, pp. 745–751, 2023.
[24] R. S. Sreenivas, “On the existence of supervisory poli-
cies that enforce liveness in discrete-event dynamic
systems modelled by controlled Petri nets,” IEEE
Transactions on Automatic Control, vol. 42, pp. 928–
945, 1997.
[25] H. Boucheneb, A. Alger, and G. Berthelot, “Towards
a simplied building of time Petri nets reachability
graph,” in Proceedings of the 5th International Work-
shop on Petri Nets and Performance Models, (Reims,
France), pp. 46–55, May 1993.
[26] M. V. Iordache and P. J. Antsaklis, “Design
of T-liveness enforcing supervisors in Petri nets,”
IEEE Transactions on Automatic Control, vol. 48,
pp. 1962–1974, 2003.
[27] Z. W. Li and M. C. Zhou, “Elemetary siphons of Petri
nets and their application to deadlock prevention in
exible manufacturing systems,” IEEE Transactions
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
165
Volume 19, 2024
on Systems, Man, and Cybernetics–Part A, vol. 34,
pp. 38–51, 2004.
[28] E. J. Davison, A. G. Aghdam, and D. E. Miller,
Decentralized Control of Large-Scale Systems. New
York: Springer, 2020.
[29] M. Kordestani, A. A. Safavi, and M. Saif, “Recent
survey of large-scale systems: Architectures, con-
troller strategies, and industrial applications,” IEEE
Systems Journal, vol. 15, pp. 5440–5453, Dec. 2021.
[30] A. Aybar, et.al., “Overlapping decompositions and
expansions of Petri nets,” IEEE Transactions on
Automatic Control, vol. 47, pp. 511–515, 2002.
Contribution of Individual Authors to
the Creation of a Scientic Article
(Ghostwriting Policy)
The author contributed in the present research,
at all stages from the formulation of the problem
to the nal ndings and solution.
Sources of Funding
This work has been supported by the Scientic
Research Projects Commission of Eskişehir Tech-
nical University.
Conicts of Interest
The author has no conicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International , CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/
deed.en_US
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
DOI: 10.37394/23203.2024.19.17
Altuğ I
ftar
E-ISSN: 2224-2856
166
Volume 19, 2024