- Source: Behavior of DEVS
The behavior of a given DEVS model is a set of sequences of timed events including null events, called event segments, which make the model move from one state to another within a set of legal states. To define it this way, the concept of a set of illegal state as well a set of legal states needs to be introduced.
In addition, since the behavior of a given DEVS model needs to define how the state transition change both when time is passed by and when an event occurs, it has been described by a much general formalism, called general system [ZPK00]. In this article, we use a sub-class of General System formalism, called timed event system instead.
Depending on how the total state and the external state transition function of a DEVS model are defined, there are two ways to define the behavior of a DEVS model using Timed Event System.
Since the behavior of a coupled DEVS model is defined as an atomic DEVS model, the behavior of coupled DEVS class is also defined by timed event system.
View 1: total states = states * elapsed times
Suppose that a DEVS model,
M
=<
X
,
Y
,
S
,
s
0
,
t
a
,
δ
e
x
t
,
δ
i
n
t
,
λ
>
{\displaystyle {\mathcal {M}}=
has
the external state transition
δ
e
x
t
:
Q
×
X
→
S
{\displaystyle \delta _{ext}:Q\times X\rightarrow S}
.
the total state set
Q
=
{
(
s
,
t
e
)
|
s
∈
S
,
t
e
∈
(
T
∩
[
0
,
t
a
(
s
)
]
)
}
{\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}
where
t
e
{\displaystyle t_{e}}
denotes elapsed time since last event and
T
=
[
0
,
∞
)
{\displaystyle \mathbb {T} =[0,\infty )}
denotes the set of non-negative real numbers, and
Then the DEVS model,
M
{\displaystyle {\mathcal {M}}}
is a Timed Event System
G
=<
Z
,
Q
,
Q
0
,
Q
A
,
Δ
>
{\displaystyle {\mathcal {G}}=
where
The event set
Z
=
X
∪
Y
ϕ
{\displaystyle Z=X\cup Y^{\phi }}
.
The state set
Q
=
Q
A
∪
Q
N
{\displaystyle Q=Q_{A}\cup Q_{N}}
where
Q
N
=
{
s
¯
∉
S
}
{\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}}
.
The set of initial states
Q
0
=
{
(
s
0
,
0
)
}
{\displaystyle \,Q_{0}=\{(s_{0},0)\}}
.
The set of accepting states
Q
A
=
M
.
Q
.
{\displaystyle Q_{A}={\mathcal {M}}.Q.}
The set of state trajectories
Δ
⊆
Q
×
Ω
Z
,
[
t
l
,
t
u
]
×
Q
{\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}
is defined for two different cases:
q
∈
Q
N
{\displaystyle q\in Q_{N}}
and
q
∈
Q
A
{\displaystyle q\in Q_{A}}
. For a non-accepting state
q
∈
Q
N
{\displaystyle q\in Q_{N}}
, there is no change together with any even segment
ω
∈
Ω
Z
,
[
t
l
,
t
u
]
{\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
so
(
q
,
ω
,
q
)
∈
Δ
.
{\displaystyle (q,\omega ,q)\in \Delta .}
For a total state
q
=
(
s
,
t
e
)
∈
Q
A
{\displaystyle q=(s,t_{e})\in Q_{A}}
at time
t
∈
T
{\displaystyle t\in \mathbb {T} }
and an event segment
ω
∈
Ω
Z
,
[
t
l
,
t
u
]
{\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
as follows.
If unit event segment
ω
{\displaystyle \omega }
is the null event segment, i.e.
ω
=
ϵ
[
t
,
t
+
d
t
]
{\displaystyle \omega =\epsilon _{[t,t+dt]}}
If unit event segment
ω
{\displaystyle \omega }
is a timed event
ω
=
(
x
,
t
)
{\displaystyle \omega =(x,t)}
where the event is an input event
x
∈
X
{\displaystyle x\in X}
,
If unit event segment
ω
{\displaystyle \omega }
is a timed event
ω
=
(
y
,
t
)
{\displaystyle \omega =(y,t)}
where the event is an output event or the unobservable event
y
∈
Y
ϕ
{\displaystyle y\in Y^{\phi }}
,
Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.
View 2: total states = states * lifespans * elapsed times
Suppose that a DEVS model,
M
=<
X
,
Y
,
S
,
s
0
,
t
a
,
δ
e
x
t
,
δ
i
n
t
,
λ
>
{\displaystyle {\mathcal {M}}=
has
the total state set
Q
=
{
(
s
,
t
s
,
t
e
)
|
s
∈
S
,
t
s
∈
T
∞
,
t
e
∈
(
T
∩
[
0
,
t
s
]
)
}
{\displaystyle Q=\{(s,t_{s},t_{e})|s\in S,t_{s}\in \mathbb {T} ^{\infty },t_{e}\in (\mathbb {T} \cap [0,t_{s}])\}}
where
t
s
{\displaystyle t_{s}}
denotes lifespan of state
s
{\displaystyle s}
,
t
e
{\displaystyle t_{e}}
denotes elapsed time since last
t
s
{\displaystyle t_{s}}
update, and
T
∞
=
[
0
,
∞
)
∪
{
∞
}
{\displaystyle \mathbb {T} ^{\infty }=[0,\infty )\cup \{\infty \}}
denotes the set of non-negative real numbers plus infinity,
the external state transition is
δ
e
x
t
:
Q
×
X
→
S
×
{
0
,
1
}
{\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}
.
Then the DEVS
Q
=
D
{\displaystyle Q={\mathcal {D}}}
is a timed event system
G
=<
Z
,
Q
,
Q
0
,
Q
A
,
Δ
>
{\displaystyle {\mathcal {G}}=
where
The event set
Z
=
X
∪
Y
ϕ
{\displaystyle Z=X\cup Y^{\phi }}
.
The state set
Q
=
Q
A
∪
Q
N
{\displaystyle Q=Q_{A}\cup Q_{N}}
where
Q
N
=
{
s
¯
∉
S
}
{\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}}
.
The set of initial states
Q
0
=
{
(
s
0
,
t
a
(
s
0
)
,
0
)
}
{\displaystyle \,Q_{0}=\{(s_{0},ta(s_{0}),0)\}}
.
The set of acceptance states
Q
A
=
M
.
Q
{\displaystyle Q_{A}={\mathcal {M}}.Q}
.
The set of state trajectories
Δ
⊆
Q
×
Ω
Z
,
[
t
l
,
t
u
]
×
Q
{\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}
is depending on two cases:
q
∈
Q
N
{\displaystyle q\in Q_{N}}
and
q
∈
Q
A
{\displaystyle q\in Q_{A}}
. For a non-accepting state
q
∈
Q
N
{\displaystyle q\in Q_{N}}
, there is no changes together with any segment
ω
∈
Ω
Z
,
[
t
l
,
t
u
]
{\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
so
(
q
,
ω
,
q
)
∈
Δ
.
{\displaystyle (q,\omega ,q)\in \Delta .}
For a total state
q
=
(
s
,
t
s
,
t
e
)
∈
Q
A
{\displaystyle q=(s,t_{s},t_{e})\in Q_{A}}
at time
t
∈
T
{\displaystyle t\in \mathbb {T} }
and an event segment
ω
∈
Ω
Z
,
[
t
l
,
t
u
]
{\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
as follows.
If unit event segment
ω
{\displaystyle \omega }
is the null event segment, i.e.
ω
=
ϵ
[
t
,
t
+
d
t
]
{\displaystyle \omega =\epsilon _{[t,t+dt]}}
If unit event segment
ω
{\displaystyle \omega }
is a timed event
ω
=
(
x
,
t
)
{\displaystyle \omega =(x,t)}
where the event is an input event
x
∈
X
{\displaystyle x\in X}
,
If unit event segment
ω
{\displaystyle \omega }
is a timed event
ω
=
(
y
,
t
)
{\displaystyle \omega =(y,t)}
where the event is an output event or the unobservable event
y
∈
Y
ϕ
{\displaystyle y\in Y^{\phi }}
,
Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.
Comparison of View1 and View2
= Features of View1
=View1 has been introduced by Zeigler [Zeigler84] in which given a total state
q
=
(
s
,
t
e
)
∈
Q
{\displaystyle q=(s,t_{e})\in Q}
and
where
σ
{\displaystyle \sigma }
is the remaining time [Zeigler84] [ZPK00]. In other words, the set of partial states is indeed
S
=
{
(
d
,
σ
)
|
d
∈
S
′
,
σ
∈
T
∞
}
{\displaystyle S=\{(d,\sigma )|d\in S',\sigma \in \mathbb {T} ^{\infty }\}}
where
S
′
{\displaystyle S'}
is a state set.
When a DEVS model receives an input event
x
∈
X
{\displaystyle x\in X}
, View1 resets the elapsed time
t
e
{\displaystyle t_{e}}
by zero, if the DEVS model needs to ignore
x
{\displaystyle x}
in terms of the lifespan control, modellers have to update the remaining time
in the external state transition function
δ
e
x
t
{\displaystyle \delta _{ext}}
that is the responsibility of the modellers.
Since the number of possible values of
σ
{\displaystyle \sigma }
is the same as the number of possible input events coming to the DEVS model, that is unlimited. As a result, the number of states
s
=
(
d
,
σ
)
∈
S
{\displaystyle s=(d,\sigma )\in S}
is also unlimited that is the reason why View2 has been proposed.
If we don't care the finite-vertex reachability graph of a DEVS model, View1 has an advantage of simplicity for treating the elapsed time
t
e
=
0
{\displaystyle t_{e}=0}
every time any input event arrives into the DEVS model. But disadvantage might be modelers of DEVS should know how to manage
σ
{\displaystyle \sigma }
as above, which is not explicitly explained in
δ
e
x
t
{\displaystyle \delta _{ext}}
itself but in
Δ
{\displaystyle \Delta }
.
= Features of View2
=View2 has been introduced by Hwang and Zeigler[HZ06][HZ07] in which given a total state
q
=
(
s
,
t
s
,
t
e
)
∈
Q
{\displaystyle q=(s,t_{s},t_{e})\in Q}
, the remaining time,
σ
{\displaystyle \sigma }
is computed as
When a DEVS model receives an input event
x
∈
X
{\displaystyle x\in X}
, View2 resets the elapsed time
t
e
{\displaystyle t_{e}}
by zero only if
δ
e
x
t
(
q
,
x
)
=
(
s
′
,
1
)
{\displaystyle \delta _{ext}(q,x)=(s',1)}
. If the DEVS model needs to ignore
x
{\displaystyle x}
in terms of the lifespan control, modellers can use
δ
e
x
t
(
q
,
x
)
=
(
s
′
,
0
)
{\displaystyle \delta _{ext}(q,x)=(s',0)}
.
Unlike View1, since the remaining time
σ
{\displaystyle \sigma }
is not component of
S
{\displaystyle S}
in nature, if the number of states, i.e.
|
S
|
{\displaystyle |S|}
is finite, we can draw a finite-vertex (as well as edge) state-transition diagram [HZ06][HZ07]. As a result, we can abstract behavior of such a DEVS-class network, for example SP-DEVS and FD-DEVS, as a finite-vertex graph, called reachability graph [HZ06][HZ07].
See also
DEVS
Behavior of Coupled DEVS
Simulation Algorithms for Atomic DEVS
Simulation Algorithms for Coupled DEVS
References
[Zeigler76] Bernard Zeigler (1976). Theory of Modeling and Simulation (first ed.). Wiley Interscience, New York.
[Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
[ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 978-0-12-778455-7.
[HZ06] M. H. Hwang and Bernard Zeigler, ``A Reachable Graph of Finite and Deterministic DEVS Networks``, Proceedings of 2006 DEVS Symposium, pp48-56, Huntsville, Alabama, USA, (Available at https://web.archive.org/web/20120726134045/http://www.acims.arizona.edu/ and http://moonho.hwang.googlepages.com/publications)
[HZ07] M.H. Hwang and Bernard Zeigler, ``Reachability Graph of Finite & Deterministic DEVS``, IEEE Transactions on Automation Science and Engineering, Volume 6, Issue 3, 2009, pp. 454–467, https://ieeexplore.ieee.org/document/5071137/;jsessionid=939E18A20B3B2411AA8CD012B44EE174?isnumber=5153598&arnumber=5071137&count=19&index=7
Kata Kunci Pencarian:
- Riot Games
- Behaviour Interactive
- Mesin finite-state
- Behavior of DEVS
- DEVS
- Behavior of coupled DEVS
- Simulation algorithms for atomic DEVS
- Everything is a file
- Timed event system
- Simulation algorithms for coupled DEVS
- Behavior-driven development
- Applied behavior analysis
- Open Roads
