Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844
Vol. V (2010), No. 4, pp. 447-457
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems
A. Aybar
Aydın Aybar
Anadolu University, Dept. of Electrical and Electronics Engineering
26555, Eskişehir, Turkey. E-mail: aaybar@anadolu.edu.tr
Abstract: A decentralized controller design approach is developed for the timed
discrete event systems which are modelled by timed automata in this work. An ap-
proach, called augmentation, is presented to obtain the new modelling method such
that each unit delay of any event represents a pair of new state and event. The aug-
mented automata model, obtained by using this approach, is considered to design a
decentralized controller. This controller design approach is developed such that the
local controller is designed for each subautomaton, obtained by using overlapping
decompositions and expansions and these controllers are then combined to obtain
a decentralized controller for the given timed automaton. The designed decentral-
ized controller guarantees the unreachability of a forbidden state in the considered
automaton.
Keywords: Discrete event systems, Automata, Time delays, Decentralized con-
troller.
1 Introduction
Although automata and Petri nets are known as common modelling methods for discrete event sys-
tems (see, [1]– [4]), these models were first presented without time notation. Since there exist time delays
in the dynamic systems, time notation is a necessity for the modelling methods of the discrete event sys-
tems [5,6]. Time notation was used for automata (see, [7]). In this timed automata model, a class of finite
state automata was extended with a set of clocks. The clocks were chosen as real values and timed event,
denoted by a pair of an event and its occurence time, were used to determine the reachability of any
state. Afterwards, the timed automata model was used by many works (for example, [8–10]). Moreover,
the basic supervisory controller approaches were presented for these timed systems, modelled by timed
automata (for example, [11–13]).
It is known that the computational complexity of a supervisory controller design depends on the
number of states and clocks for the timed automata model [10]. Moreover, the computational complexity
increases exponentially with the number of states of the untimed automata model [14] (also see, [15]).
Thus, a controller design for timed automata (especially, large scale automata have more number of
states and events), can be more complex. An approach, called augmentation, is first introduced for timed
automata in order to decrease the computational complexity, depending on the time and/or clock, of a
controller design.
This approach, based on [16, 17], is described such that each unit delay of any event represents a pair
of new state and event, and then these pairs are added to the original automaton. A new modelling model
is introduced such that the augmented automaton is obtained by adding the pairs of events and states,
corresponding to unit time delays, to the original automaton in this work. In [16, 17], the strecthing
approach was developed for timed Petri nets. In this developed approach, each delay, assigned to a
transition, denotes a pair of new place and transition. Using the similarity between automata and Petri
nets, we first develop the augmentation approach in this work. Although any event of automata can be
related to any transition of Petri net, there exist some differences between these models (for example, a
marking vector of Petri net is corresponding to a state of automaton).
Copyright c⃝ 2006-2010 by CCC Publications
448 A. Aybar
The augmented automaton is used to design a decentralized controller in this work. An algebraic
approach, which gives the state space representation for automata, is also developed to determine the
state vectors.
Our aim is a decentralized controller design which prevents the occurence of the forbidden states.
To facilitate the controller design, we use the approach of overlapping decompositions. The overlapping
decompositions approach was first introduced by [18] for the case of continuous-state systems (systems
described by differential or difference equations with continuous state variables). This approach was
then used for discrete event systems by ( [4, 14, 19, 20]).
2 Preliminaries
2.1 Mathematical Model
The timed automata model is represented by A(Q,Σ,C,q0,D). Here, Q is the set of states, Σ is the
set of events, C : Q × Q → Σ ∪{0} is the connection matrix, q0 is the initial state at the initial time, and D
is set of the time delays of the events such that de ∈ R+ is the time delay of the event e ∈ Σ , where R+ is
set of nonnegative real numbers.
The connection matrix is given as
C(qi,q j) :=
{
e, if qi is obtained when event e occurs at state q j
0, otherwise
, for qi,q j ∈ Q
C(qi,q j) = 0 denotes no connection between two states qi and q j. C(qi,q j) = e denotes a connection
between these states via e. It is assumed that the connection of between two states is done by only one
event.
In this work, the vector-matrix form is used to determine new state. The state vector at time τ is
denoted by S(τ)
S(τ) :=
{
ΛQ(q), if τ = Γ (q), for any q ∈ Q
Z, otherwise
Here, Γ (q) denotes the obtained time of state q (it is assumed that each event occurs immediately as it
becames possible), ΛQ : Q → {0,1}|Q|, ΛQ(q) := { 1, if q = [Q] j
0, otherwise
, j ∈ {1,..., |Q|} where, [Q] j denotes
the jth element of Q, and |Q| indicates the number of the elements of Q, τ denotes the global time, Z,
which is zeros vector, denotes that the occurence of the event e has not finished at τ or the considered
event can not occured at the given state.
The state equation is given as follows:
S(τ) = (C∨ S(τe))∧O(e,τe), e ∈ Σ (1)
It is assumed that the initial state S(τ0) = ΛQ̄(q0) and there exists an event e such that τe = Γ (q) for
q ∈ Q (there is one exception such that if there exists deadlock in the considered automaton, no event
can occur at deadlock state), where τe denotes the occurence time of the event e. Note that, ∨ and ∧ are
used respectively. Here,
• The event function is defined as O(e,τe) := e ⊙ ϕ(τ − τe − de), where, ϕ : R+ → {0,1}; ϕ(x) ={
1, if x ≥ 0
0, otherwise
.
• The operation ⊙ on the set Σ̈ := Σ ∪{0,1} is defined as 0⊙0 = 0, ek ⊙0 = 0, 0⊙ek = 0, 0⊙1 = 0,
1⊙0 = 0, 1⊙1 = 0, ek ⊙1 = ek, 1⊙ ek = ek, ek ⊙ ek = 0, ek ⊙ el = 0, el ⊙ ek = 0.
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems 449
• The operation ∨ on the matrices H ∈ Σ̈ |Q|×|Q| and R ∈ Σ̈ |Q|, F = H ∨ R, is defined as F(i) =∑|Q|
k=1 H(i,k)⊙ R(k), i ∈ {1,..., |Q|}.
• The operation ⊗ on the set Σ̈ is defined as 0 ⊗ 0 = 0, ei ⊗ 0 = 0, 0 ⊗ ei = 0, 0 ⊗ 1 = 0,
1 ⊗ 0 = 0, 1 ⊗ 1 = 1, ei ⊗ 1 = ei, 1 ⊗ ei = ei, ei ⊗ ei = 1, ei ⊗ e j = 0, e j ⊗ ei = 0.
• For F ∈ Σ̈ |Q| and e ∈ Σ , F ∧ e = [F(1)⊗ e ... F(|Q|)⊗ e]T .
In the given example automaton, shown in Fig. 1a, the set of states is Q = {q0,q1,q2,q3,q4}, the set
of events is Σ = {e1,e2,e3,e4,e5,e6,e7}, and the initial state is q0. The set of time delays, assigned to the
events, is given as de1 = de2 = de6 = 2 sec., de3 = 3 sec., de4 = de5 = de7 = 1 sec. Let the occurence time
of e3 be τe3 = 5 sec. and S(5) = ΛQ(q2) = [0 1 0 0 0]
T . The state vector is obtained as
S(τ) = (C∨ S(5))∧O(e3,5) =
0 0 0 e4 0
e1 0 0 0 0
0 e3 0 e5 0
0 e2 0 0 e6
e7 0 0 0 0
∨
0
1
0
0
0
∧(e3 ⊙ ϕ(τ −5−3))
=
0
0
e3 ⊙1
0
0
∧(e3 ⊙ ϕ(τ −5−3)) =
{
[0 0 1 0 0]T , if τ ≥ 8
[0 0 0 0 0]T , if 5 < τ < 8
q2 is obtained when the occurence of event e3 is completed (q2 is not yet obtained in time interval
between 5 sec. and 8 sec.). In this work, a new model is introduced in next section and used to design a
decentralized controller.
2.2 Overlapping Decompositions and Expansions
Overlapping decompositions and expansions [21] have been widely used to design decentralized
controllers for continuous-state systems. These concepts have also been used to design supervisory
controllers for discrete event systems modeled by Petri nets [19] and by automata [14]. To our best
knowledge, overlapping decompositions and expansions of discrete event systems modelled by automata
or formal languages have been first introduced in [14]. In the given approach, overlapping subautomata
of an automaton are first identified by examining the topological structure of the given automaton. These
subautomata are identified such that the only interconnection between the subautomata are through the
overlapping part, i.e., no event should connect two states in different subautomata, unless one of these
states is in the overlapping part of the two subautomata. As an example, the automaton (Fig. 1a) can be
decomposed into two subautomata as shown in Fig. 1b-1c ( [14]).
After an overlapping decomposition of the original automaton is obtained, the expansions of the
automaton is explained as follows [14]:
i) A state or an event in the overlapping part of n subautomata is repeated n times and each repeated
state/event is assigned to a different subautomaton.
ii) Two events are introduced between any two repeated states, such that when such an event occurs
the state changes from one repeated state to the other. Note that, a delay of each new event is
assigned to the biggest common divisor of time delays of the original automaton in this work.
iii) If the initial state is in the overlapping part of the original automaton, then the initial state of the
expanded automaton can be chosen as any one of the repeated states of the original initial state.
450 A. Aybar
Otherwise, the initial state of the expanded automaton is chosen as the initial state of the original
automaton.
4
7
6
4
7
6
subautomaton 1
subautomaton 2
4
7
6
a
a
a b
b
b
12
2
21
1
21
2
12
1
Figure 1. (a) Example automaton (b) Overlappingly decomposed automaton (c) Expanded automaton
As a result of this procedure, an expanded automaton, which consists of α disjoint subautomata, is
obtained from an original automaton which was decomposed into α overlapping subautomata.
The set of states of the expanded automaton is given by Q̃ := ∪αi=1Qi, where Qi is the set of states
of the ith subautomaton. The set of events of the expanded automaton is given by Σ̃ := Σ̆ ∪ Σ̀ . Here,
Σ̆ = ∪αi=1Σi, where Σi is the set of events of the ith subautomaton and Σ̀ is the set of additional events
introduced between the repeated states. As an example, the states q0, q3, and the event e4 are repeated,
and new events e112, e
1
21, e
2
12 and e
2
21 are added to the repeated states in the expanded automaton in Fig.
1a. Then, the time delay of these events is determined as one second.
3 New Model for Timed Automata
Although the usage of time in the mathematical model is a necessity for the real world system,
the computational complexity of time delay systems increases because of the defined all processes and
functions need more memories and time. We introduce the augmentation approach. Using this approach,
a new model is obtained for timed automata and called as the augmented automata, where each event has
only unit time delay.
The augmentation approach is defined such that time delays are represented by new states and events
in this work. The augmented automaton, ĀT (Q̄,Σ̄,C̄,q0), is introduced, where, C̄ : Q̄ × Q̄ → Σ̄ , Q̄ :=
Q ∪(
∪
e∈Σ
∆S(e)), and Σ̄ := Σ ∪(
∪
e∈Σ
∆E(e)) are given following items.
• The time delays of the events are scaled such that dse := de/λ , for e ∈ Σ and de ∈ D, where λ
indicates the biggest common divisor of time delays. Note that, the set of the scaled time delays
of the events is denoted by Ds. It is assumed that dse ≥ 1, for all e ∈ Σ in this work.
• For the event e ∈ Σ such that C(qi,q j) = e and dse = 1, the input connection from e to the state is
hold such as C̄(qi,q j) = C(qi,q j) = e for qi,q j ∈ Q. Note that, if C(qa,qb) = 0, then C̄(qa,qb) = 0.
• For the event e∗ ∈ Σ , and dse∗ > 1, δe∗ := d
s
e∗ −1 numbers new events and states are defined such as
f e
∗
1 , f
e∗
2 , ... , f
e∗
δe∗
, and pe
∗
1 , p
e∗
2 , ... , p
e∗
δe∗
. The sets are constructed by using these events and states
as ∆E(e∗) and ∆S(e∗), respectively.
• The pairs are constructed by using the new events and states for any event e∗ ∈ Σ , dse∗ > 1, such
that ( f e
∗
i , p
e∗
i ) for i ∈ {1,2,...,δe}. For C̄(qk,qn) = e
∗, the connections are described such as from
qn to f e
∗
1 , from f
e∗
1 to p
e∗
1 , from p
e∗
1 to f
e∗
2 , ... from f
e∗
δe∗
to qk. Hence, the new connection ma-
trix is constructed for the new automaton model such as C̄(pe
∗
1 ,qn) = f
e∗
1 , C̄(p
e∗
2 , p
e∗
1 ) = f
e∗
2 , ....,
C̄(qk, pe
∗
δe∗
) = ee
∗
δe∗
.
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems 451
As a result of the above procedure, we obtain the augmented automaton which has more events and
states but each event has only unit time delay.
We introduce the algebraic approach for the augmented automaton. Let S̄n be denote the present state
vector and S̄n+1 be denote the next state vector (for n ∈ {0,1,2,...}, S̄0 = ΛQ̄(q0) denotes the initial state
vector). The state equation is defined as follows:
S̄n+1 = (C̄∨ S̄n)∧ ē, ē ∈ Σ̄. (2)
It is possible to obtain pek as the current state. It shows that the occurence of the event e has not finished
yet and also the duration time is determined as k ∗ λ + τe for the event e. Compared to (1), the evaluation
of the above equation (2) is much simpler, since it does not require the time notation and the event
function O.
qq
q
q
p
e
e
e
e
e1
2
4
5
1
4
1
23
f
e1
11
pe3
1
pe3
2
f
e3
1
f
e3
2
pe2
1
f
e2
1
e
7
e
6
f
e6
1
pe6
1
q0
e
3
Figure 2. Augmented automaton
For example, we obtain the augmented automaton (Fig. 2.) for the given timed automata (Fig. 1a).
The set of states is Q̄ = {q0,q1,q2,q3,q4}∪{pe11 , pe21 , p
e3
1 , p
e3
2 , pe61 }, where, ∆S(e1) = {p
e1
1 }, ∆S(e2) = {p
e2
1 },
∆S(e3) = {p
e3
1 , p
e3
2 }, and ∆S(e6) = {pe61 }, the set of events is Σ̄ = {e1,e2,e3,e4,e5,e6}∪{ f e11 , f e21 , f
e3
1 , f
e3
2 , f e61 },
where ∆E(e1) = { f e11 }, ∆E(e2) = { f
e2
1 }, ∆E(e3) = { f
e3
1 , f
e3
2 }, and ∆E(e6) = { f e61 }, and the connection matrix
is given as
C̄ =
0 0 0 e4 0 0 0 0 0 0
0 0 0 0 0 f e11 0 0 0 0
0 0 0 e5 0 0 0 0 f
e3
2 0
0 0 0 0 0 0 f e21 0 0 f
e6
1
e7 0 0 0 0 0 0 0 0 0
e1 0 0 0 0 0 0 0 0 0
0 e2 0 0 0 0 0 0 0 0
0 e3 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 f
e3
1 0 0
0 0 0 0 e6 0 0 0 0 0
4 Decentralized Controller Design
A decentralized controller for the forbidden states avoidance is developed for the considered automa-
ton in this section.
4.1 Centralized Control
The centralized controller guarantees the unreachability of a forbidden state for the original automa-
ton (F denotes the set of the forbidden states). Now, we consider a centralized controller design for the
original augmented automaton (OAA).
452 A. Aybar
In the OAA, the set of forbidden states is taken as F̄ = F. It is possible that there exists a state which
only leads to any element of the set F̄. Thus, the set F̄ is extented by these sets and a new set, denoted by
Ḡ, is obtained by the following algorithm. This algorithm, called as F S, requests the set of the forbidden
states and the definition. Note that, this algorithm also finds the deadlock states, in which no event can
occur, and adds these deadlock states to the set Ḡ. In this work, each element of Ḡ is called as forbidden
state.
A controller for the OAA is defined as
K̄(S̄n,ē) = K̄(ΛQ̄(q),ē) =
{
0, if S̄n+1 ∈ Ḡv
1, otherwise
, ē ∈ Σ̄ (3)
where, S̄n = ΛQ̄(q), S̄n+1 = (C̄ ∨ S̄n) ∧ ē and Ḡv :=
∪
q∈Ḡ ΛQ̄(q) denotes the set of the state vectors,
corresponding to states of Ḡ. Note that, if q f is a forbidden state, q f ∈ Ḡ, then ΛQ̄(q f ) is called as
forbidden state vector, ΛQ̄(q f ) ∈ Ḡv. Once K̄(S̄n,ē) = 0 denotes disabling event ē ∈ Σ̄ , K̄(S̄n,ē) = 1
denotes enabling event ē. Then, this controller guarantees the unreachability of an element of Ḡ.
The OAA with the controller can be also called as controlled automaton, denoted by
ĀKT (Q̄,Σ̄,C̄,q0,K̄). The controlled state equation, which is obtained by adding this controller to the
equation (2), is given as follows:
S̄n+1 = (C̄∨ S̄n)∧(ē ⊗ K̄(S̄n,ē)), ē ∈ Σ̄ (4)
Thus, any element of of Ḡ does not occur in this controlled automaton.
Algorithm to construct the set Ḡ
Ḡ = FS(ĀT ,F̄)
Ḡ = F̄
Do Loop Construction
F̂ = /0
For i = 1 to |Q̄|
If [Q̄]i /∈ Ḡ Then
cnt = 0
For j = 1 to |Q̄|
If C̄( j,i) = 0 Or [Q̄] j ∈ Ḡ Then
cnt = cnt +1
If cnt = |Q̄| Then
F̂ ← F̂ ∪̂ {[Q̄] j}
End
End
End
End
End
If F̂ = /0 Then
Exit Loop Construction
End
Ḡ← Ḡ ∪̂ F̂
Loop Construction
Here, both ∪ and ∪̂ are used to denote the set union. L ∪̂ M is used, rather than L ∪ M, whenever it is
known apriori that L ∩ M = /0. To evaluate N = L ∪ M, the set C is first initialized as L; for each element
(from first to last), m, of M, it is then checked whether m ∈ L. If m /∈ L, then m is added to set N. To
evaluate N = L ∪̂ M, on the other hand, elements of L and of M are simply appended to form N.
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems 453
4.2 Decentralized Control
Now, we first consider to design a controller for each disjoint subautomaton. Then, a controller of the
expanded augmented automaton (EAA) is obtained by using these controllers of subautomata. Finally, a
decentralized controller is designed by using the controller of the EAA for the OAA.
It is known that the augmented subautomata are easily obtained by using overlapping decompositions
and expansions. Let ĀiT (Q̄i,Σ̄i,C̄i,qi0) be denote the i
th subautomaton. Now, some definitions and nota-
tion are given such that the EAA is denoted by ÃT (Q̃,Σ̃,C̃,q̃0), where, Q̃ := ∪αi=1Q̄i, Σ̃ := ∪αi=1Σ̄i ∪ Σ̀ ,
and the connection matrix can be easily determined by using new sets of states and events.
ΨQ̄ : Q̄ → Q̃, ΨQ̄(q) denotes the set of states in the EAA which corresponds to the state q in the
OAA and ΨΣ̄ : Σ̄ → Σ̃ , ΨΣ̄ (e) denotes the set of events in the EAA which corresponds to the event e in
the OAA. Also, we define Ψ −1Σ̄ : Σ̃ → Σ̄ and Ψ −1Q̄ : Q̃ → Q̄ such that e = Ψ −1Σ̄ (ẽ) ⇐⇒ ẽ ∈ ΨΣ̄ (e) and
q = Ψ −1
Q̄
(q̃) ⇐⇒ q̃ ∈ ΨQ̄(q).
The set of the forbidden states for the ith augmented subautomaton is obtained as F̄i := F̃∩ Q̄i, where
F̃ =
∪
q̄∈F̄ ΨQ̄(q̄). For the i
th subautomaton, Ḡi and Ḡiv are obtained by using the algorithm FS. Note that,
this algorithm needs the definition of the ith subautomaton, and the set F̄i.
It is possible to design a controller, K̄i for ĀiT , if the initial state of this subautomaton is not a for-
bidden state (qi0 /∈ Ḡi). Since this repeated state is used for the interconnection between the subautomata
(see, Section 2.2), it is assumed that any repeated state in the ith subautomaton is not element of Ḡi for
all i ∈ {1,...,α} (q̃ /∈ Ḡi for q̃ ∈ Q̃0i which denotes the set of repeated states in the i
th subautomaton).
The controller for the EAA is designed by using local controllers, K̄i for all i ∈ {1,...,α}, where α
denotes the number of subautomata,
K̃(ΛQ̃(q̃),ẽ) =
{
K̄i(ΛQ̄i(q̃),ẽ), if ẽ ∈ Σ̄i
1, otherwise
, q̃ ∈ Q̃ (5)
Note that, G̃ :=
∪
i∈{1,...,α} Ḡi. Consequently, the controlled state equation is obtained by adding this
controller to the state equation, for S̃n = ΛQ̃(q̃),
S̃n+1 = (C̃∨ S̃n)∧(ẽ ⊗ K̃(S̃n,ẽ)), ẽ ∈ Σ̃
Theorem 1: K̃ avoids the existence of the elements of G̃ in ÃKT .
Proof: Let q̃ ∈ Q̃ and ẽ ∈ Σ̃ . This state is also an element of any subautomaton, q̃ ∈ Q̄k, for k ∈ {1,...,α}.
i) If there is no relation between q̃ and ẽ, then K̃(ΛQ̃(q̃),ẽ) = 1 because of its definition (see, the
equation (5)). In this case, ẽ is not occured at q̃ and also this value of K̃ does not affect the
controlled state equation because of the definition of operation ⊗.
ii) If ẽ ∈ Σ̀ , then K̃(ΛQ̃(q̃),ẽ) = 1. In this case, the next state is also repeated state and not a forbidden
state (q̃o /∈ Ḡ j for q̃o ∈ Q̃0j , ∀ j ∈ {1,...,α}).
iii) If ẽ ∈ Σ̄k, then K̃(ΛQ̃(q̃),ẽ) = K̄k(ΛQ̄k (q̃),ẽ). Let the next state, q̃
+, be obtained by using ẽ from
q̃. If q̃+ ∈ Ḡk , then K̄k(ΛQ̄k (q̃),ẽ) = 0 and q̃
+ ∈ G̃ because of definition of G̃ [K̃(ΛQ̃(q̃),ẽ) = 0].
Otherwise, K̄k(ΛQ̄k (q̃),ẽ) = 1 and q̃
+ /∈ G̃ [K̃(ΛQ̃(q̃),ẽ) = 1]. Note that, K̃(ΛQ̃(q̃),ẽ) = 1 if there is
no relation between q̃ and ẽ. 2
We now obtain a controller, K̄, for the OAA, by using the controller, K̃, for the EAA as follows:
K̄(ΛQ̄(q̄),ē) = Π
q̃∈ΨQ̄(q̄)
Π
ẽ∈ΨΣ̄ (ē)
K̃(Λ̃ (q̃),ẽ), q̄ ∈ Q̄, ē ∈ Σ̄ (6)
454 A. Aybar
Furthermore, the controlled state equation is given as S̄n+1 = (C̄ ∨ S̄n) ∧ (ē ⊗ K̄(S̄n,ē)), ē ∈ Σ̄ , where,
S̄n = ΛQ̄(q̄), in the OAA.
Theorem 2: K̄ guarantees the unreachability of a forbidden state in ĀKT .
Proof: It is known that the sets Ḡ j for all j ∈ {1,...,α} and G̃ are determined. Any repeated event in the
EAA is only connected to the repeated states because of overlapping decomposition approach.
i) if q̄‡ ∈ Q̄, ΨQ̄(q̄
‡) = {q̄‡} and ē∗ ∈ Σ̄ , ΨΣ̄ (ē
∗) = {ē∗a,ē
∗
b,...,ē
∗
x}, then
K̄(ΛQ̄(q̄
‡),ē∗) = K̃(ΛQ̃(q̄
‡),ē∗a) .
K̃(ΛQ̃(q̄
‡),ē∗b). ... K̃(ΛQ̃(q̄
‡),ē∗x). Since any event, in the overlapping part, is only connected to the
states in the overlapping part, K̄(ΛQ̄(q̄
‡),ē∗) = 1.
ii) if q̄‡ ∈ Q̄, ΨQ̄(q̄
‡) = {q̄‡} and ē∗ ∈ Σ̄ , ΨΣ̄ (ē
∗) = {ē∗}, then q̄‡ and ē∗ are elements of subautomata.
Note that, K̄(ΛQ̄(q̄
‡),ē∗) = K̃(ΛQ̃(q̄
‡),ē∗) = 0 if q̄‡ and ē∗ are not in same automaton. If there
is a relation between q̄‡ and ē∗ in the jth subautomaton, then K̄(ΛQ̄(q̄
‡),ē∗) = K̃(ΛQ̃(q̄
‡),ē∗) =
K̄ j(ΛQ̄ j (q̄
‡),ē∗). In this case, if q̄u, which is obtained by using ē∗ from q̄‡, is an element of Ḡ j,
then K̄ j(ΛQ̄ j (q̄
‡),ē∗) = 0. Otherwise, K̄ j(ΛQ̄ j (q̄
‡),ē∗) = 1.
iii) If q̄‡ ∈ Q̄, ΨQ̄(q̄
‡) = {q̄‡a,q̄
‡
b,...,q̄
‡
y} and ē
∗ ∈ Σ̄ , ΨΣ̄ (ē
∗) = {ē∗}, then
K̄(ΛQ̄(q̄
‡),ē∗) = K̃(ΛQ̃(q̄
‡
a),ē
∗) . K̃(ΛQ̃(q̄
‡
b),ē
∗). .. .K̃(ΛQ̃(q̄
‡
y),ē
∗). If ē∗ is not connected to any
element of ΨQ̄(q̄
‡), then K̄(ΛQ̄(q̄
‡),ē∗) = 1 . 1 ... .1 = 1. Let q̄‡l and ē
∗ in the lth subautomaton
(the elements of ΨQ̄(q̄
‡) \ {q̄‡l } are in the other subautomata, K̃(ΛQ̃( ˙̄q),ē
∗) = 1, for ˙̄q ∈ ΨQ̄(q̄
‡) \
{q̄‡l }). In this case, K̄(ΛQ̄(q̄
‡),ē∗) = 1 .... 1 .K̄l(ΛQ̄l (q̄
‡
l ),ē
∗) .1 ...1 = K̄l(ΛQ̄l (q̄
‡
l ),ē
∗) is obtained.
Here, if ^̄q, which is obtained by using ē∗ from q̄‡l , is an element of G̃ then K̄l(ΛQ̄l (q̄
‡
l ),ē
∗) = 0
[K̄(ΛQ̄(q̄
‡),ē∗) = 0]. Otherwise, K̄l(ΛQ̄l (q̄
‡
l ),ē
∗) = 1 [K̄(ΛQ̄(q̄
‡),ē∗) = 1].
iv) If q̄‡ ∈ Q̄, ΨQ̄(q̄
‡) = {q̄‡a,q̄
‡
b,...,q̄
‡
y} and ē
∗ ∈ Σ̄ , ΨΣ̄ (ē
∗) = {ē∗a,ē
∗
b,...,ē
∗
x}, then K̄(ΛQ̄(q̄
‡),ē∗)
= 1 .... 1 = 1 since any repeated state is not element of G̃.
Note that, each element of Ḡ is also an element of G̃ because of overlapping decompositions and expan-
sions approach and q̄ ∈ Ḡ ⇒ q̄ ∈ Q j, for j ∈ {1,...,α}. Thus, q̄ is an element of Ḡ j and also q̄ ∈ G̃. This
decentralized controller prevents the forbidden states in ĀKT . 2
We can obtain a decentralized controller for the original automaton as follows:
K(ΛQ(q),e) = K̄(ΛQ̄(q),e), q ∈ Q, e ∈ Σ (7)
This controller is added to the state equation (1) and S(τ) = (C∨S(τe))∧(O(e,τe)⊗K(S(τe),e)), for e ∈
Σ is obtained. It is known that, although the forbidden states are elements of Q, the new states may be
elements of Ḡ. The controller of the OAA only disables the elements of Σ because of the connection of
the pairs new states and events (see, Section 4). Therefore, the occurence of any event, which is disabled
at any state by the controller (6), is disabled for the original automaton by the controller (7).
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems 455
5 Example
q
4
e
7
e
6
f
e6
1
pe6
1
qq
q
p
e
e
e
e
e1
2
4b
5
1
1
2
3b
f
e1
11
pe3
1
pe3
2
f
e3
1
f
e3
2
pe2
1
f
e2
1
q0b
e
3
q
e
4a
3a
q0a
12
2
21
1
21
2
12
1
Figure 3. Expanded automaton
In this section, we design a decentralized controller, which guarantees the forbidden states avoidance,
for the given timed automaton (Fig. 1a). The augmented automaton for this automaton is obtained as
Fig. 2. The EAA, shown in Fig. 3, is obtained by using overlapping decompositions and expansions.
For the original timed automaton, the set of forbidden states is given as F = {q2} and F̄ = F. Then,
F̃ =
∪
q̄∈F̄ ΨQ̄(q̄) = {q2}. Now, we consider two subautomata to design a decentralized controller.
In the first subautomaton, Ā1T (Q̄1,Σ̄1,C̄1,q10), the set of states is Q̄1 = {q0a,q3a,q4, p
e6
1 }, the set of
events is Σ̄1 = {e4,e6a,e7, f e61 }, and the initial state is q10 = q0a. In the second subautomaton,
Ā2T (Q̄2,Σ̄2,C̄2,q20), the set of states is Q̄2 = {q0b,q2,q3b, p
e1
1 , p
e2
1 , p
e3
1 , p
e3
2 }, the set of events is
Σ̄2 = {e1,e2,e3,e4b, f e11 , f
e2
1 , f
e3
1 , f
e3
2 }, and the initial state is q20 = q0b. The connection matrices are
C̄1 =
0 e4a 0 0
0 0 0 f e61
e7 0 0 0
0 0 e6 0
and C̄2 =
0 0 0 e4b 0 0 0 0
0 0 0 0 f e11 0 0 0
0 0 0 e5 0 0 0 f
e3
2
0 0 0 0 0 f e21 0 0
e1 0 0 0 0 0 0 0
0 e2 0 0 0 0 0 0
0 e3 0 0 0 0 0 0
0 0 0 0 0 0 f
e3
1 0
.
For each subautomaton, F̄i = F̃ ∩ Q̄i for i ∈ {1,2} is obtained such as F̄1 = /0 and F̄2 = {q2}. In
the subautomata, the set Ḡ1 = /0 is obtained by using the algorithm FS (note that, Ḡ1v = /0). Thus,
K̄1(ΛQ̄1(q0a),ē
+) = K̄1([1 0 0 0]T ,ē+) = 1 for all ē+ ∈ Σ̄1 and K̄1(ΛQ̄1(q̄
∗),ēx) = 1 for all q̄∗ ∈ Q̄1 and
ēx ∈ Σ̄1. The set Ḡ2 = {q2, p
e3
2 , p
e3
1 } is obtained by using the algorithm FS (note that,
Ḡ2v = {[0 1 0 0 0 0 0 0]
T ,[ 0 0 0 0 0 0 0 1]T , [ 0 0 0 0 0 0 1 0]T }). Thus, K̄2(ΛQ̄2(q1),e5) = 0, K̄2(ΛQ̄2(q3a),e3) =
0 and K̄2(ΛQ̄2(q̄
x),ē∗) = 1 for all q̄x ∈ Q̄2 \{q1,q3a} and ē∗ ∈ Σ̄2.
Using the equation (5), the controller is obtained for the EAA as K̃(ΛQ̃(q1),e5) =
K̄2(ΛQ̄2(q1),e5) = 0, K̃(ΛQ̃(q3b),e3) = K̄2(ΛQ̄2(q3b),e3) = 0, and K̃(ΛQ̃(q̃
‡),ẽc) = 1, ∀q̃‡ ∈ Q̃ \{q1,q3a},
∀ẽc ∈ Σ̃. It is known that S̃n = ΛQ̃(q1) = [0 1 0 0 0 0 0 0;0 0]
T , and ΛQ̄2(q1) = [0 1 0 0 0 0 0 0]
T .
Finally, a decentralized controller, which avoids the forbidden states, is designed by using (6). This
controller is given as
K̄(ΛQ̄(q1),e5) = K̃(ΛQ̃(q1),e5) = K̄2(ΛQ̄2(q1),e5) = 0, K̄(ΛQ̄(q3),e3) = K̃(ΛQ̃(q3a),e3) . K̃(ΛQ̃(q3b),e3) =
K̄1(ΛQ̄1(q3a),e3) . K̄2(ΛQ̄2(q3b),e3) = 1 . 0 = 0, and K̄(ΛQ̄(q
d),ew) = 1, ∀qd ∈ Q̄\{q1,q3}, ∀ew ∈ Σ̄. The
final result is given such that the occurence of e5 is disabled at the state q1 and the occurence of e3 is
456 A. Aybar
disabled at the state q3. Thus, decentralized controller avoids state q2. For the original timed automa-
ton, the controller is obtained as K(ΛQ(q3),e3) = 0, K(ΛQ(q1),e5) = 0, and K(ΛQ(qx),ez) = 1, ∀qx ∈
Q \{q1,q3}, ∀ez ∈ Σ .
Now, let us compare the results of centralized and decentralized controllers for the given automaton.
Both of these controllers disables the occurence of e5 the state q1 and the occurence of e3 at the state q3.
The most advantage is that the size of the connection matrix for each subautomaton is smaller then the
size of the connection matrix of the OAA.
6 Conclusion
A decentralized controller approach using overlapping decompositions for the timed discrete event
systems. An approach, called augmentation, is presented to obtain the new modelling method such that
each unit delay of any event represents a pair of new state and event. The augmented automaton is
constructed by adding the pairs of events and states to the original automaton in this work.
The decentralized controller design approach is presented to prevent the occurence of the forbidden
states. The augmented automaton is first decomposed overlappingly and expanded to obtain subau-
tomata. Then, a controller is designed for each disjoint subautomaton. These local controllers are then
combined to obtain a controller for the augmented automaton. Moreover, the state space representation
is used for timed and untimed automata by the given algebraic approach.
Since the clock or timer does not used to analyse for the augmented automaton, the first advantage is
that the computational complexity does not depend on clock for the timed automata. For the construction
of the augmented autonmaton, the new states and events are added to the original automaton, and then
the size of the connection matrix of the original automaton is smaller than the size of the connection
matrix of the augmented automaton. Although this seems to be a disadvantage, the connection matrices
of the augmented subautomata are only used to design the decentralized controller (i.e., the connection
matrix of the augmented automaton is not used for the decentralized controller design approach). The
size of the connection matrix of each subautomaton is an advantage for the decentralized approach (the
number of states and events of subautomata is less than original automaton, [14, 15]).
Although the effort needed to obtain a useful the overlapping decomposition, this can be not com-
parable to the controller design since the decomposition may, in most cases, be easily made. Further
research can also be undertaken to use this approach to design decentralized controllers for various ob-
jectives (for example, a controller can be designed such that this controller leads the given discrete event
systems to marked states).
Bibliography
[1] P. J. G. Ramadge and W. M. Wonham, “The control of discrete event systems,” Proceedings of the
IEEE, vol. 77, pp. 81–98, 1989.
[2] R. S. Sreenivas and B. H. Krogh, “On Petri net models of infinite state supervisors,” IEEE Trans-
actions on Automatic Control, vol. 37, pp. 274–277, 1992.
[3] A. Aybar and A. İftar, “Decentralized supervisory controller design to avoid deadlock in Petri nets,”
International Journal of Control, vol. 76, pp. 1285–1295, 2003.
[4] A. Aybar and A. İftar, “Decentralized supervisory controller design for discrete-event systems
using overlapping decompositions and expansions,” Dynamics of Continuous, Discrete and Impulse
Systems (Series B), vol. 11, pp. 553–568, 2004.
Decentralized Controller Design for Forbidden States Avoidance in
Timed Discrete Event Systems 457
[5] A. A. Desrochers and R. Y. Al-Jaar, Applications of Petri Nets in Manufacturing Systems, The
Institute of Electrical and Electronics Engineers Inc., New York, 1995.
[6] M. Zhou and F. DiCesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems,
Kluwer Academic, Norwell, MA, 1993.
[7] R. Alur and D. L. Dill, “A theory of timed automata,” Theoretical Computer Science, vol. 126, pp.
183–235, 1994.
[8] A. Gouin and J. Ferrier, “Temporal coherence of timed automata product,” in Proc. of the 1999
IEEE International Conference on Systems, Man, and Cybernetics, October 1999, pp. 176–181.
[9] J. Krakora, L. Waszniowski, P. Pisa, and Z. Hanzalek, “Timed automata approach to real time
distributed system verification,” in Proc. of the 2004 IEEE International Workshop on Factory
Communication Systems, September 2004, pp. 407–410.
[10] A. Khoumsi, “A supervisory control method for ensuring the comformance of real-time discrete
event systems,” Discrete Event Dynamic Systems: Theory and Applications, vol. 15, pp. 397–431,
2005.
[11] B. A. Bradin and W. M. Wonham, “Supervisory control of timed discrete–event systems,” IEEE
Transactions on Automatic Control, vol. 39, pp. 329–342, 1994.
[12] F. Lin and W. M. Wonham, “Supervisory control of timed discrete–event systems under partial
observation,” IEEE Transactions on Automatic Control, vol. 40, pp. 558–562, 1995.
[13] I. Açıksöz, “Time step approach for timed automata model (in turkish),” M.S. thesis, Anadolu
University, Eskişehir, Turkey, June 2006.
[14] A. Aybar and A. İftar, “Overlapping decompositions of large–scale discrete–event systems,” in
Proceeding CD-ROM of The 15th IFAC World Congress, Barcelona, Spain, July 2002.
[15] K. Rudie and W. M. Wonham, “Think globally, act locally: decentralized supervisory control,”
IEEE Transactions on Automatic Control, vol. 37, pp. 1692–1708, 1992.
[16] A. Aybar and A. İftar, “Supervisory controller design for timed Petri nets,” in Proceedings of the
IEEE International Conference on System of Systems Engineering, Los Angeles, CA, U.S.A., Apr.
2006, pp. 59–64.
[17] A. Aybar and A. İftar, “Deadlock avoidance controller design for timed Petri nets using stretching,”
IEEE Systems Journal, vol. 2, pp. 178–188, 2008.
[18] M. Ikeda and D. D. Šiljak, “Overlapping decompositions, expansions, and contractions of dynamic
systems,” Large Scale Systems, vol. 1, pp. 29–38, 1980.
[19] A. Aybar and A. İftar, “Overlapping decompositions and expansions of Petri nets,” IEEE Transac-
tions on Automatic Control, vol. 47, pp. 511–515, 2002.
[20] A. Aybar, A. İftar, and H. Apaydın-Özkan, “Centralized and decentralized supervisory controller
design to enforce boundedness, liveness, and reversibility in Petri nets,” International Journal of
Control, vol. 78, pp. 537–553, 2005.
[21] M. Ikeda and D. D. Šiljak, “Overlapping decentralized control with input, state, and output inclu-
sion,” Control Theory and Advanced Technology, vol. 2, pp. 155–172, 1986.