Stochastic Timed Automata (STA) |
|
DescriptionDefinitionExamplesReferences |
Description:
A Stochastic Timed Automaton (STA) is basically a state automaton consisting of states and events (together with transition function) but unlike traditional finite state automaton it incorporates a notion time. For this purpose it is equipped with a clock structure associated with an event set of an automaton. The clock structure in this model is used as an input. STA has two probabilistic features:
The clock structure determines through the event timing mechanism which event is going to occur and when. Also note that the number of states is allowed to be countably infinite. STA generates a stochastic state sequence {X0, X1, X2, …}. The stochastic process {X(t)} is reffered to as Generalized Semi-Markov Process (GSMP) without simultaneous events. Formal Definition (adopted from [1]):A Stochastic Timed Automaton (STA) is a six-tuple (E, X, Γ, p, p0, G) where E – is a finite set of events (here we mean event types) X – is a countable set of states Γ(x) – is a set of active events defined for all x ∈X, with Γ(x) a subset of E, p(x1; x, e) – is a state transition probability,
defined for all x, x1 ∈X, e∈E,
reflecting probability of going from state x to state x1 through
occurrence of an event e, and such
that p(x1; x, e)=0 for all e not in Γ(x). p0 –
is the pmf P[X0=x], x∈X, of
the initial state X0. G={Gi : i∈E}
– is a stochastic clock structure – a set of distribution functions. Note1: Actually Γ is
totally described by p, since(Γ(x) is just the
set of all e, s.t. p(x1; x, e) is not
zero for all x1 in X, but
it is included in the definition nevertheless for convenience. Note2: Another feature may be (and
usually is) incorporated in this formalism – clock rates that in general depend on states. We are not
considering this feature for now. Examples:
Consider the following STA: E = {a,b,c}, X = {0,1,2}, Γ(0) = {a,b,c}, Γ(1) = {a}, Γ(2) ={a,b}, p(1; 0, a)=0.9;
p(1; 0, c)=0.3; p(2; 0, b)=1; p(2; 1, a)=1; p(0; 2, b)=1;
p(1; 2, a)=1; G={Ga, Gb, Gc }. STA state transition represented by the following graph:
We can generate a sample path the following way:
Given the initial state 0 (obtained from p0),
we sample both Ga, Gb,
and Gc (since Γ(0) = {a,b,c}) Suppose the outcomes are 1.3, 2.0, and 5.5. We interpret
these as clock times for events a, b
and c. Since 1.3<2.0<5.5 the event to happen is a. Since p(1; 0,a)=0.9 we now have probability 0.9 of event a triggering a transition from state 0
to state1 at time 1. Suppose transition from state 0 to state 1 is fired.
Global clock is set to 1.3. Current state is 1. Γ(1) = {a} and we sample Ga
again (since event a was just triggered). Suppose we obtain time
2.5. Therefore event a
is triggered at time 1.3+2.5=3.7. Again since p(2;
1,a)=1 transition from state 1 to
state 2 is fired. Γ(2) = {a,b} and we need to choose between events a and b again. But here we do not need to sample Gb again since clock value 5.5 obtained from first sampling of Gb is still not reached, and event b has not happened yet. We just sample Ga then. Suppose we get 1.2. 3.7+1.2=4.9<5.5 and event a happens again triggering transition to state 1. We can proceed in the similar manner. References:
|
