4_Automi_Temporizzati

4. Automi temporizzati
Il comportamento dei sistemi ad eventi temporizzati
non è definito semplicemente da una sequenza di
eventi o di valori dello stato, ma a questi bisogna
associare una temporizzazione.
Esistono diversi formalismi:
• automi temporizzati
• catene di Markov
• reti di code
• reti di Petri temporizzate
• algebra max-plus
• simulazione ad eventi discreti
1
Automi: modello logico
Definizione: Un automa finito deterministico (AFD) è
una 5-upla G=(X,E,,x0,Xm) dove:
• X è un insieme finito di stati;
• E è un insieme finito di eventi (alfabeto);
•  : X  E  X è la funzione di transizione;
• x0  X è lo stato iniziale;
• Xm  X è l’insieme di stati finali.
(x,e) è lo stato raggiunto quando si verifica
l’evento e a partire dallo stato x.
2
d
Esempio:
a
x0: stato
iniziale e
finale

x0
x1
x2
a
x1
x0
b
x2
d
b
c
x1
c
x2
x0: m. spenta
c
d
x1: m. accesa
a: accensione
x2
x0
x0
x2: in avviamento
b: predisposizione
c: lavorazione
Possibile evoluzione:
a
b
d: spegnimento
c
x0  x1  x2  x2  x2
w = abcc parola
3
• Ad ogni AFD è possibile associare un
linguaggio generato e un linguaggio
accettato (o marcato)
• Le proprietà fondamentali degli automi sono:
- la raggiungibilità
- la reversibilità
- la vivezza
• Esiste poi un altro modello di SED che può
essere visto come una
generalizzazione degli AFD, ossia gli
automi finiti non deterministici (AFN)
4
Esempio di
AFN:
a
x0
b
Vi sono:
x3

b
a
x1
a
a
b
x2
b
a
x4
• transizioni etichettate con la parola vuota 
• più transizioni uscenti dallo stesso nodo e aventi
la stessa etichetta
5
Automi temporizzati
Quando si studiano i sistemi temporizzati non si
specifica più l’insieme degli stati finali Xm.
Un automa viene definito come una 4-upla G=(X,E,,x0)
È necessario definire una struttura di temporizzazione
Per ogni evento si specifica il ritardo di attivazione
(intervallo di tempo in cui l’evento deve rimanere
abilitato prima di potersi verificare). Questo può
essere deterministico o stocastico.
automi temporizzati
deterministici
stocastici
6
Automi temporizzati deterministici
Ad ogni evento e è associato:
• un insieme ordinato di numeri reali non negativi e =
{e,1, e,2, … } dove e,k rappresenta il k-esimo
ritardo di attivazione di e;
• un contatore di attivazione e che indica il numero di
volte in cui e è stato attivato e che permette di
individuare in maniera univoca il ritardo di
attivazione attuale del generico evento e.
In ogni istante di tempo t possiamo
scrivere la seguente relazione
7
e(t) + oe(t) = e
• e(t): tempo di attivazione di e
• oe(t): orologio o tempo residuo
• e:
ritardo di attivazione attuale di e
tk
t
e(t)
tk+1
oe(t)
e
istante di tempo in cui e è
stato abilitato l’ultima volta
istante in cui è
previsto il prossimo
accadimento di e
8
Definizione formale: Un automa temporizzato
deterministico è una 5-upla Gd=(X,E,,x0,) dove
G=(X,E,,x0) è definito come visto prima e  è la
struttura deterministica di orologio.
L’evoluzione temporale di un automa deterministico
temporizzato dipende dalla particolare politica di
aggiornamento dell’orologio
memoria di
abilitazione
memoria
totale
9
Memoria di abilitazione: l’orologio associato ad
un evento viene aggiornato ogni volta che esso
viene abilitato una nuova volta.
Non si distingue il fatto che un evento sia stato
disabilitato perché si è verificato, dal caso in cui
è divenuto tale da non potersi verificare.
Nel sistema rimane traccia solo del numero di
volte in cui ogni evento è stato abilitato.
10
Memoria totale: prevede che ogni volta che un
evento viene disabilitato senza essersi verificato,
si tenga comunque traccia del tempo in cui è
rimasto abilitato.
Nel sistema rimane traccia sia del numero di
volte in cui ogni evento è stato abilitato sia di
quanto tempo tale evento è rimasto abilitato.
11
Esempio: supponiamo che il generico evento e
rappresenti l’esecuzione di una certa lavorazione da
parte di un robot.
Il ritardo ad esso associato rappresenta quindi il tempo
richiesto per tale lavorazione.
Nel caso di memoria di abilitazione stiamo
implicitamente supponendo che la lavorazione può
venire completata solo se eseguita consecutivamente
per un tempo pari al ritardo di attivazione attuale.
Nel caso di abilitazione totale stiamo invece
ammettendo che la lavorazione possa essere eseguita in
intervalli di tempo disgiunti, purché complessivamente
duri un tempo pari al suo ritardo attuale di abilitazione.
12
Evoluzione temporale (memoria di abilitazione)
1. All’istante iniziale si assuma:
e = 1, oe= e,1 se e  A(x0);
e = 0 e oe indefinito se e  A(x0);
dove A(x) indica in generale l’insieme
degli eventi abilitati dallo stato x.
2. Si determini a quale evento, tra quelli
abilitati corrisponde il tempo residuo
inferiore:
o*  min oe 
eA(x)
Sia
e' arg min oe 
eA(x)
13
3. Una volta trascorso un tempo pari a o*, si verifica
l’evento e’ portando il sistema in un
nuovo stato x’ :
x' δ(x, e')
4. Si aggiornano i valori degli orologi e dei ritardi di
attivazione come segue:
o  o *
 e
oe '  θe, υ 1
e
o
 e
se e  e' e e  A(x), e  A(x')
se e  e' o e  A(x), e  A(x')
altrimenti
υ  1 se e'  e o e  A(x), e  A(x')
υe '   e
altrimenti
υe
5. Si torni al passo 2. Si pone x=x’.
14
Evoluzione temporale (memoria totale)
L’algoritmo per il calcolo dell’evoluzione temporale
differisce da quello relativo alla politica di
abilitazione per il solo aggiornamento del valore di
orologio al passo 4 :
oe  o *

oe '  θe, υ 1
e
o
 e
se e  e' e e  A(x)
se e  e'
altrimenti
15
Esempio
Si veda l’esercitazione n2.
Osservazione: Ovviamente può succedere che
arg min oe 
eA(x)
non sia unico. Perché l’evoluzione sia deterministica è
necessario definire una priorità tra gli eventi.
16
Automi temporizzati stocastici
Gli orologi non sono noti come sequenze di numeri
reali, ma sono variabili aleatorie di cui si conoscono le
funzioni di distribuzione.
Definizione: La struttura di orologio stocastica
associata all’insieme degli eventi E è l’insieme di
funzioni di distribuzione  = {e : eE} dove e è la
funzione di distribuzione di probabilità da cui vengono
estratti i valori delle v.a. che costituiscono i ritardi di
attivazione e,k.
Definizione: Un automa temporizzato stocastico è una
5-upla Gs=(X,E,,x0,) dove G=(X,E,,x0) è definito
come visto prima e  = {e : eE} è la struttura
stocastica di orologio.
17
Proprietà: la sequenza di stati che si ottiene
dall’evoluzione di un automa stocastico è un
processo processo semi- markoviano
generalizzato (PSMG)
Proprietà: nel caso in cui i ritardi di attivazione
degli eventi sono v.a. a distribuzione esponenziale,
la sequenza degli stati che si ottiene
dall’evoluzione del corrispondente automa
stocastico è un processo stocastico markoviano.
18