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

Gianmaria De Tommasi » 4.Automi deterministici temporizzati


Sommario della lezione

  • SED temporizzati;
  • Automi temporizzati deterministici;
  • Evoluzione temporale di un automa temporizzato deterministico.

Sistemi ad Eventi Discreti Temporizzati

Sequenze temporizzate

Quando si passa allo studio dei SED temporizzati il comportamento del sistema è caratterizzato dalle sequenze temporizzate di eventi

s = \bigl\{(e_1\,,\tau_1)\,,(e_2\,,\tau_2)\,,\ldots\,,(e_n\,,\tau_n)\,,\ldots\bigr\}
con
e_i evento i-mo
\tau_i istante di occorrenza dell’evento i-mo

Sistemi ad Eventi Discreti Temporizzati (segue)

Struttura di temporizzazione

Per poter associare ad ogni evento l’istante temporale di occorrenza è necessario aggiungere al modello di automa logico una struttura di temporizzazione.

Sistemi ad Eventi Discreti Temporizzati (segue)

Ritardo di attivazione

Il ritardo di attivazione è l’intervallo di tempo che intercorre tra l’abilitazione di un evento e la sua occorrenza.

I ritardi di attivazione possono essere noti (modello temporizzato deterministico) oppure caratterizzati da una funzione di distribuzione di probabilità (modello temporizzato stocastico).

Sistemi ad Eventi Discreti Temporizzati (segue)

Tempo di attivazione e tempo residuo

Si consideri il generico istante di tempo \tau e il generico evento e. Se \tau_k e \tau_{k+1} sono rispettivamente gli istanti di abilitazione e occorrenza di e, si indica con

\varphi_e(\tau) il tempo di attivazione;
o_e(\tau) il tempo residuo (o clock);
\theta_e il ritardo di attivazione.


Sistemi ad Eventi Discreti Temporizzati (segue)

Struttura di temporizzazione deterministica

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

\Theta=\bigl\{\Theta_e\ :\ e\in E\bigr\}

i cui elementi \Theta_e sono le sequenze:

\Theta_e=\bigl\{\theta_{e\,,1}\,,\theta_{e\,,2}\,,\ldots\bigr\}

con e\in E, \theta_{e\,,k}\in\mathbb{R}_+\cup\bigl\{0\bigr\}, k\in\mathbb{N}.

\theta_{e\,,k} è il k-mo ritardo di attivazione dell’evento e.

Sistemi ad Eventi Discreti Temporizzati (segue)

Contatore di attivazione

Dato un evento e, il contatore di attivazione \nu_e indica il numero di volte che l’evento e è stato attivato a partire dall’istante iniziale.

Se all’istante \tau' avviene la transizione tra gli stati x_k e x_{k+1}, allora

\mathrm{se}\ e\in\Gamma\bigl(x_{k+1}\bigr)\Rightarrow\nu'_e=\left\{\begin{array}{ll}\nu_e+1 & \mathrm{se}\ e\ \mathrm{e'\ occorso\ oppure\ se}\ e\notin\Gamma\bigl(x_k\bigr)\\ \nu_e&\mathrm{altrimenti}\end{array}\right.

I valori iniziali \nu_e sono:
\nu_e=1 se e\in\Gamma\bigl(x_0\bigr)
\nu_e=0 altrimenti

Automi temporizzati deterministici

Definizione di Automa Temporizzato Deterministico

Un automa temporizzato (deterministico) è un 6-pla:

G_d=\Bigl(X\,,E\,,f\,,\Gamma\,,x_0\,,\Theta\Bigr)

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

Automi temporizzati deterministici (segue)

Osservazioni

Un automa temporizzato genera un sequenza di stati sulla base della sequenza di accadimento degli eventi seguendo l’equazione

x'=f\bigl(x\,,e'\bigr)

con x' stato prossimo e e'\in\Gamma\bigl(x\bigr)

La sequenza di eventi che occorrono è determinata sulla base dei valori correnti dei loro clock (tempi residui) secondo la relazione

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

dove o_e(\tau) rappresenta il valore corrente del clock associato all’evento e.

Automi temporizzati deterministici (segue)

Aggiornamento dei tempi residui (clock)

Se o'_e è il valore di o_e quando si raggiunge lo stato x' allora

\mathrm{se}\ e\in\Gamma\bigl(x'\bigr)\Rightarrow o'_e=\left\{\begin{array}{ll}o_e-o^\ast & \mathrm{se}\ e\neq e'\ \mathrm{e}\ e\in\Gamma\bigl(x\bigr)\\ \theta_{e\,,\nu_e+1}&\mathrm{altrimenti}\end{array}\right.

con o^\ast=\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\}. o^\ast indica il tempo in cui è avvenuta la transizione da x a x'.

Le condizioni iniziali per i clock sono
o_e =\theta_{e\,,1} se e\in\Gamma\bigl(x_0\bigr)
o_e=\mathrm{indefinito} altrimenti

Evoluzione di un automa temporizzato

Evoluzione temporale di un automa temporizzato

Supponiamo che l’automa temporizzato G_d si trovi nello stato x all’istante \tau

  1. Individuare o^\ast mediante la relazione o^\ast=\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\};
  2. Determinare il prossimo evento come evento associato a o^\ast, cio e'=\arg\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\};
  3. Determinare il prossimo stato come x' =f\bigl(x\,,e'\bigr);
  4. Determinare il tempo di occorrenza di e' come \tau'=\tau+o^\ast;
  5. Calcolare i nuovi valori di o'_e e \nu'_e per tutti gli eventi;
  6. Ritornare al passo 1.

I materiali di supporto della lezione

Paragrafo 3.1 (fino a pagina 77) da Di Febbraro-Giua.

Esempi 3.4 e 3.5.

  • 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