Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Gianmaria De Tommasi » 5.Automi temporizzati stocastici e catene di Markov


Sommario della lezione

  • Automi temporizzati stocastici;
  • Catene di Markov.

Automi temporizzati stocastici

Struttura di temporizzazione stocastica

Dato un insieme di eventi E la struttura di temporizzazione stocastica associata ad E è l’insieme

\Psi=\bigl\{\Psi_e\ :\ e\in E\bigr\}

i cui elementi \Psi_e sono funzioni di densità di probabilità definite in \mathbb{R}_+\cup\bigl\{0\bigr\}.

Mediante le funzioni \Psi_e vengono estratti i valori delle variabili aleatorie che costituiscono i ritardi di attivazione \theta_{e\,,k}, con e\in E e k\in\mathbb{N}.

Automi temporizzati stocastici (segue)

Esempi di funzioni \Psi_e

In figura 1: \Psi_e con distribuzione uniforme.
In figura 2: \Psi_e con distribuzione normale.

Figura 1.

Figura 1.

Figura 2.

Figura 2.


Automi temporizzati stocastici (segue)

Definizione di Automa Temporizzato Stocastico

Un automa temporizzato stocastico è un 6-pla:

G_s=\Bigl(X\,,E\,,f\,,\Gamma\,,x_0\,,\Psi\Bigr)

Dove la 5-pla \Bigl(X\,,E\,,f\,,\Gamma\,,x_0\Bigr) è un automa logico e \Psi è un struttura di temporizzazione stocastica.

Automi temporizzati stocastici (segue)

Evoluzione temporale di un automa temporizzato stocastico

L’evoluzione di un automa temporizzato stocastico si determina sfruttando la relazione

e=\arg\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\}

per determinare il prossimo evento.

I tempi residui si aggiornano estraendo un nuovo campione mediante le funzioni \Psi_e.

Automi temporizzati stocastici (segue)

Osservazioni

Per gli automi temporizzati stocastici:

  • la sequenza di stati \bigl\{x(\tau)\bigr\} è un processo stocastico;
  • ogni realizzazione del processo stocastico \bigl\{x(\tau)\bigr\} è una traettoria x(\cdot) nello spazio di stato;
  • per un fissato istante \tau, x(\tau) è una variabile aleatoria.

Automi temporizzati stocastici (segue)

Processi di Semi-Markov Generalizzati

Il processo stocastico \bigl\{x(\tau)\bigr\} generato da un automa temporizzato stocastico G_s è chiamato processo di Semi-Markov generalizzato (GSMP).

Automi temporizzati stocastici (segue)

Processo di Markov

Un processo stocastico \bigl\{x(\tau)\bigr\} con spazio di stato X è un processo di Markov se

Pr\bigl\{x(\tau+d\tau)=x_j\ |\ x_{[\tau_0\,,\tau]}\bigr\} = Pr\bigl\{x(\tau+d\tau)=x_j\ |\ x(\tau)=x_i\bigr\}

Un processo markoviano è senza memoria → lo stato rappresenta tutta la storia passata del processo.

Automi temporizzati stocastici (segue)

Processi di Markov e GSMP

Per un processo di Markov (stazionario) si può scrivere:

Pr\bigl\{x(\tau+d\tau)=x_j\ |\ x(\tau)=x_i\bigr\}=\lambda_{ij}d\tau

Anche per i GSMP non è necessario conoscere tutta la storia passata del processo. Infatti per un GSMP (stazionario) vale

Pr\bigl\{x(\tau+d\tau)=x_j\ |\ x(\tau)=x_i\bigr\}=\lambda_{ij}(\varphi_{e_1}\,,\varphi_{e_2}\,,\ldots\,,\varphi_{e_n})d\tau

Dove \varphi_{e_k} sono i tempi di attivazione degli eventi. e\in\Gamma\bigl(x_i\bigr)

Automi temporizzati stocastici (segue)

Processi di Markov e GSMP

Se un GSMP ha ritardi di attivazione che sono variabili aleatorie con distribuzione esponenziale, cioè

\Psi_e(\theta)=\lambda_{ij}e^{-\lambda_{ij}\theta}

allora il GSMP è un processo di Markov.

Catene di Markov

Quando lo spazio di stato di un processo stocastico Markoviano è discreto (finito oppure infinito) il processo si dice catena di Markov.

Catene di Markov (segue)

Catene di Markov a tempo continuo

Un processo stocastico \bigl\{x(\tau)\bigr\} con spazio di stato discreto X (finito oppure infinito) è detto catena di Markov a tempo continuo (CMTC).

se \forall\ \tau_h\in\mathbb{R}_+\cup\bigl\{0\bigr\}\,, h=0\,,1\,,\ldots\,,k+1

Pr\bigl\{x(\tau_{k+1})=x_{k+1}\ |\ x(\tau_k)=x_k\,,x(\tau_{k-1})=x_{k-1}\,,\ldots\,,x(\tau_0)=x_0\bigr\}=

=Pr\bigl\{x(\tau_{k+1})=x_{k+1}\ |\ x(\tau_k)=x_k\bigr\}

Catene di Markov (segue)

Catene di Markov a tempo discreto

Un processo stocastico\bigl\{x(\tau)\bigr\} con spazio di stato discreto X(finito oppure infinito) è detto CATENA DI MARKOV A TEMPO DISCRETO (CMTD) se le transizioni possono verificarsi solo in istanti discreti (tipicamente multipli di un periodo di campionamento T) e vale la proprietà
Pr\bigl\{x(k+1)=x_{k+1}\ |\ x(k)=x_k\,,x(k-1)=x_{k-1}\,,\ldots\,,x(0)=x_0\bigr\}=Pr\bigl\{x(k+1)=x_{k+1}\ |\ x(k)=x_k\bigr\}

per ogni k\in\mathbb{N}.

Catene di Markov (segue)

Osservazioni

Nelle catene di Markov a tempo discreto (CMTD) si ha che

Pr\bigl\{x(k+1)=x_j\ |\ x(k)=x_i\bigr\}=p_{ij}(k) \forall\ x_i\,,x_j\in X\ e k\in\mathbb{N}

e che

\sum_{x_j\in X}p_{ij}(k)=1\,, \forall\ x_i\in X e k\in\mathbb{N}

Catene di Markov (segue)

Catene di Markov a tempo discreto

Una CMTD può essere caratterizzata dalla 3-pla

\Bigl(X\,,P(k)\,,\pi(0)\Bigr)

dove:

X è lo spazio di stato
P(k)=\bigl[p_{ij}(k)\bigr]\,,k\in\mathbb{N}\,, x_i\,,x_j\in X è la matrice di probabilità di transizione (ad un passo)
\pi(0)=Pr\bigl\{x(0)=x_i\bigr\}\,,\x_i\in X è il vettore con le probabilità iniziali.

Catene di Markov (segue)

Evoluzione “dinamica” della probabilità in una CMTD

Data una CMTD, se l’i-mo elemento del vettore \pi(k) indica la probabilità che lo stato all’istante k assuma il valore x_i allora vale

\pi(k+1)=\pi(k)P(k)\,, k\in\mathbb{N}

Catene di Markov (segue)

Rappresentazione grafica delle catene di Markov

Così come per gli automi, anche alle catene di Markov è possibile associare una rappresentazione grafica chiamata diagramma delle transizioni.

Esempio di diagramma delle transizioni per una catena di Markov.

Esempio di diagramma delle transizioni per una catena di Markov.


Catene di Markov (segue)

Esempio 1/3

Modello di macchina operatrice

E=\bigl\{in\,,fi\,,ro\,,ri\bigr\}

in = inizio lavorazione
fi = fine lavorazione
ro = guasto della macchina
ri = riparazione avvenuta

X=\bigl\{F\,,L\,,G\bigr\}

Automa logico che modella una macchina operatrice non affidabile .

Automa logico che modella una macchina operatrice non affidabile .


Catene di Markov (segue)

Esempio 2/3

  • Associando all’automa logico la struttura di temporizzazione deterministica \Theta=\bigl\{\Theta_{in}\,,\Theta_{fi}\,,\Theta_{ro}\,,\Theta_{ri}\bigr\} si ottiene una automa temporizzato deterministico.
  • Associando all’automa logico la struttura di temporizzazione stocastica \Psi=\bigl\{\Psi_{in}\,,\Psi_{fi}\,,\Psi_{ro}\,,\Psi_{ri}\bigr\}, con tutte le \Psi_{\ast} funzioni di distribuzione esponenziale allora \bigl\{x(\tau)\bigr\} diventa un processo markoviano. Essendo X discreto il processo è una catena di Markov. Se le transizioni di stato avvengono a istanti k\in\mathbb{N} allora si tratta di un CMTD.

Catene di Markov (segue)

Esempio 3/3

P=\left[\begin{array}{ccc}1-i & i & 0\\ f& 1-f-g & g\\r& 0 & 1-r\end{array}\right]

La matrice P non dipende dal tempo k → il processo è stazionario

Diagramma delle transizioni per la macchina operatrice non affidabile .

Diagramma delle transizioni per la macchina operatrice non affidabile .


Catene di Markov (segue)

Esempio 3/3 (segue)

La matrice P non dipende dal tempo k → il processo è stazionario

Se x(0)=F sempre, allora si pone \pi(0)=\bigl[1\ 0\ 0\bigr]

I materiali di supporto della lezione

Capitolo 3 (da pagina 77 a pagina 86) da Di Febbraro-Giua.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion