Capitolo 1 - INTRODUZIONE 8
1.1 Sistemi ad eventi discreti
La maggior parte degli sviluppi teorici e matematici della disciplina dei
Controlli Automatici, si riferisce ai sistemi a tempo continuo o discreto. Essi
sono caratterizzati da variabili di stato che sono funzioni del tempo (continuo o
discreto) e che assumono valori in un intervallo reale. Per questi sistemi sono
stati proposti vari modelli matematici (sistemi dinamici lineari tempo-invarianti,
equazioni alle differenze, sistemi DAE – Differential Algebric Equation, ecc.).
A volte, questi sistemi sono anche chiamati sistemi “guidati dal tempo”, o
con una locuzione inglese “time-driven” [1].
Al contrario, un sistema ad eventi discreti è un sistema “guidato dagli eventi”, o
“event-driven” [1]. Esso è caratterizzato da:
• variabili di stato che assumono valori discreti (cioè che assumono un numero
finito o numerabile di valori) o valori simbolici piuttosto che numerici;
• stati che cambiano in corrispondenza dell'occorrenza, ad intervalli irregolari e
tipicamente non conosciuti a priori, di eventi fisici, i quali possono anche
essere descritti in termini non numerici.
Tra gli esempi tipici di variabili di stato per un sistemi ad eventi discreti (o
DES, Discrete Event Systems) si può avere la condizione logica di una risorsa
(occupata/libera, ferma/in movimento, alta/bassa, piena/parzialmente
piena/vuota), oppure contatori d’unità di risorse allocate (posti liberi in un
magazzino) o di utilizzatori nell’attesa di utilizzo di una data risorsa. Esempi di
eventi sono la pressione di un pulsante, il superamento di una soglia di livello
massimo o minimo per un serbatoio, il guasto di un’unità di elaborazione in una
rete, l'occupazione di una risorsa.
In un’ottica sistemistica, gli eventi in un DES possono rappresentare
cambiamenti imposti tramite opportune variabili esogene (si parla quindi di
eventi in ingresso) oppure possono semplicemente accadere spontaneamente, e
rappresentare quindi il cambiamento interno di uno stato del DES (si parla
quindi di eventi in uscita).
È evidente che l'evoluzione di un DES è determinata da una particolare
occorrenza dei vari eventi in ingresso a partire da una certa condizione (o stato)
iniziale, il quale rappresenta a sua volta il risultato di una precedente evoluzione
del sistema.
Quindi, anche nei DES le variabili di stato riassumono quanto basta
l’evoluzione passata del sistema per poterne descrivere l’evoluzione futura. Per
questo motivo in letteratura si può trovare l'acronimo DEDS (Discrete Event
Dynamic Systems), in luogo di DES, per rilevare il carattere dinamico dei DES.
Capitolo 1 - INTRODUZIONE 9
1.2 Modelli per sistemi ad eventi discreti
E’ allora possibile, così come accade per i sistemi time driven, descrivere
la dinamica di un DES tracciando un diagramma sul quale si riporta il
movimento dello stato in funzione degli istanti di tempo in cui occorrono gli
eventi[1]. Nella Figura 1-1 è rappresentato un esempio di andamento di una
variabile di stato per un sistema che assume i valori a, b, c, d. In corrispondenza
degli istanti temporali in cui occorrono gli eventi indicati con e1, e2, e3, e4, si
hanno delle transizioni di stato.
Figura 1-1: evoluzione dinamica di un DES
Se gli istanti temporali in cui occorrono gli eventi, non sono importanti ai
fini dell’analisi di un DES, una modalità di rappresentazione alternativa
dell’evoluzione può essere semplicemente la sequenza degli eventi:
e1, e2, e3, e4, ..
se invece anche l’istante di tempo in cui occorre l’evento n-mo è
d’interesse, allora si può passare ad una rappresentazione delle coppie “evento-
tempo”:
(e1,t1), (e2,t2), (e3,t3), ….
Sebbene talvolta queste rappresentazioni possono risultare esaustive, può
essere richiesta un’analisi più accurata del sistema che si sta esaminando e che
queste soluzioni non riescono a fornire. Si pensi ad esempio di voler capire se in
un certo sistema di produzione sia presente una risorsa condivisa, l’utilizzo di
queste rappresentazioni certamente non aiuta a comprendere fino in fondo la
struttura interna del sistema.
Nasce quindi l’esigenza di rappresentare i DES attraverso modelli più
dettagliati con formalismi matematici non ambigui al fine di semplificare
l’analisi e la comprensione di questo tipo di sistemi.
a
b
c
d
t1 t2 t3 t4 tempo
stato
e1
e2
e3
e4
Capitolo 1 - INTRODUZIONE 10
Esistono diversi approcci per modellare un DES, ognuno dei quali descrive
bene alcuni aspetti caratteristici e meno altri. In generale però è possibile
suddividere tutti i modelli di DES in due classi distinte:
• modelli logici: modelli nei quali solo l'ordine degli eventi è rilevante
(ovvero, l'istante temporale nel quale avviene un evento non è significativo);
• modelli temporizzati: modelli nei quali non solo l'ordine degli eventi è
rilevante, ma anche l'istante temporale nel quale avviene un evento serve a
definire il comportamento dinamico del sistema;
Tipicamente, i modelli logici sono utilizzati per risolvere problemi di
sequenziamento, come accade per la gestione dell'accesso a risorse condivise o
nell'esecuzione di sequenze di lavorazione. I modelli temporizzati, invece,
possono essere utilizzati per la valutazione di prestazioni, come, ad esempio, per
la sintesi di sistemi di controllo per sistemi manifatturieri con lo scopo di
ottimizzare opportune cifre di merito (ad esempio, minimizzare il tempo di
produzione). Esempi tipici sono i sistemi di controllo in tempo reale, in cui le
temporizzazioni ed i ritardi d’elaborazione e trasmissione sono parametri di
progetto, in grado di influenzare non solo le prestazioni, ma anche la correttezza
stessa di un sistema di controllo.
Numerosi sono i modelli che sono stati sviluppati in letteratura per
descrivere i sistemi ad eventi discreti. Si vuole qui di seguito ricordarne alcuni
tra i più diffusi. Tra i modelli logici si trovano i modelli di tipo procedurale (con
struttura a transizione) e di tipo dichiarativo. Tra i primi, che si basano sulla
descrizione di come evolve il sistema (descrivono qual è lo stato prossimo a
partire da uno stato iniziale ed un evento in ingresso), i modelli più usati sono gli
automi a stati finiti, le reti di Petri, i Grafcet. I secondi si basano sulla
dichiarazione dei vincoli e delle caratteristiche generali di un DES, la cui
evoluzione è quindi il frutto della combinazione di un insieme di regole e
vincoli. Tra essi si ricordano l’algebra booleana e i linguaggi logici in generale.
Ai fini del controllo, i modelli più semplici da utilizzare sono quelli appartenenti
al primo gruppo perché permettono la descrizione, passo dopo passo,
dell’evoluzione di un DES, mentre i secondi, oltre a richiedere un’astrazione
maggiore da parte del progettista, necessitano di algoritmi molto complessi per
l’esame dell’insieme delle regole e vincoli che descrivono il comportamento di
un DES. Tra i modelli temporali, si ricorda la logica temporale, gli automi
temporizzati, le reti di Petri temporizzate, le reti di code e le catene di Markov. I
linguaggi di programmazione utilizzati, per definire programmi che realizzano
un sistema di controllo ad eventi, sono a tutti gli effetti dei modelli di DES. Tra
questi i più diffusi [3] sono i possibili linguaggi di programmazione per i PLC,
Programmable Logic Controller: il Sequential Function Charts, che deriva dal
Grafcet, i Ladder Diagram (diagrammi a contatti), i Function Block Diagrams
(diagrammi a blocchi funzionali), l’Instruction List (linguaggio di basso livello),
lo Structured Text (linguaggio di alto livello).
Capitolo 1 - INTRODUZIONE 11
1.3 Simulazione di sistemi ad eventi discreti
Da quanto detto si evince che, preliminare allo studio accurato di un DES,
come per qualsiasi sistema dinamico, è opportuno ottenere un modello del suo
comportamento. Non di rado capita però che la complessità del sistema reale che
si vuole studiare sia tale da rendere tutte le corrispondenti tipologie di modelli
citati nei paragrafi precedenti praticamente impossibili da risolvere
matematicamente. E’ in questi casi che tipicamente si fa ricorso alla
simulazione, per valutare numericamente il modello del sistema e stimare le
grandezze ritenute di interesse.
Con un programma di simulazione si riproduce, in un ambiente controllato,
il funzionamento di un sistema reale al fine di analizzare il suo comportamento
nelle diverse condizioni possibili. Per lo studio dell’evoluzione dinamica del
sistema, va comunque sviluppato un modello, che in questo ambito è
ovviamente un modello simulativo. Inoltre trattandosi di DES, anche i modelli
simulativi saranno di tipo particolare, rispetto ai modelli per la simulazione di
sistemi “guidati dal tempo”; infatti, in quest’ambito viene adottata la
simulazione “event driven” [1].
In generale, la simulazione si presta come strumento di ausilio sia per
l’analisi sia per la sintesi di sistemi dinamici; infatti consente non solo di
effettuare misure delle prestazioni di sistemi esistenti al variare delle
caratteristiche strutturali e/o prestazionali, ma anche di valutare i diversi
comportamenti di sistemi in fase di progetto al variare delle condizioni
operative. Si può dunque concludere che l’indiscussa utilità della simulazione si
concretizza nelle possibilità di [2]:
i. studiare e analizzare le interazioni tra le singole componenti di sistemi
comunque complessi;
ii. valutare l’impatto che avrebbero potenziali cambiamenti apportabili a un
sistema esistente prima di realizzarli;
iii. valutare le prestazioni che sistemi in fase di progetto avrebbero in differenti
condizioni di funzionamento;
iv. verificare eventuali risultati analitici già ottenuti con altre metodologie di
studio.
Capitolo 1 - INTRODUZIONE 12
1.4 Fasi di uno studio di simulazione
Lo studio di un sistema, si articola nei seguenti passi[2]:
- Formulazione del problema: è fondamentale che il problema da affrontare sia
enunciato nella forma corretta e consona agli obiettivi che lo studio intende
perseguire.
- Creazione del modello: non esistono regole generali per la creazione del
modello da simulare, questa fase si basa sulle abilità di astrarre gli aspetti
essenziali del problema che si vogliono focalizzare, arricchendo ed
elaborando il modello fino al raggiungimento di risultati soddisfacenti.
- Raccolta dei dati: questa fase è strettamente legata alla precedente in quanto
bisogna individuare i dati da raccogliere e da utilizzare come ingressi al
modello e che quindi dipendono dalla complessità di quest’ultimo.
- Traduzione del modello: è la fase in cui il modello viene tradotto in una
forma che l’elaboratore elettronico riesca a riconoscere ed interpretare.
- Verifica del modello (codificato): consiste nel verificare che il modello creato
e codificato funzioni correttamente.
- Validazione del modello: consiste nel determinare le discrepanze tra il
modello simulato e il sistema reale attivando un processo di miglioramenti e
affinamenti iterativi del modello stesso.
- Progetto degli esperimenti: in base al tipo di analisi da effettuare, in questa
fase vengono stabiliti che tipo di campagna simulativa si deve effettuare.
- Analisi dei risultati: le prove simulative, vengono analizzate per stimare le
prescelte misure di prestazione del sistema; sulla base delle analisi dei
risultati, si determina se sono necessarie altre prove simulative.
- Documentazione: produzione di tabelle/grafici riassuntivi a corredo delle
campagne di simulazione.
Nello Figura 1-2 è riportato un diagramma di flusso in cui si evidenzia le
fasi di studio che bisogna eseguire per una corretta simulazione di un sistema.
Capitolo 1 - INTRODUZIONE 13
Figura 1-2: Fasi di uno studio di simulazione
Formulazione del
problema
Creazione del
Modello
Raccolta dei
Dati
Traduzione
del Modello
Verifica?
Convalida?
Progetto degli
esperimenti
Analisi dei
risultati
Altre prove?
Documentazione
e risultati
SI
SI
SI
NO NO
NO
NO
Capitolo 1 - INTRODUZIONE 14
1.5 Schema simulativo “event driven” per DES
Uno strumento di simulazione con schema di avanzamento “event driven”
si compone dei seguenti elementi [1]:
- stato: struttura dati di memorizzazione dello stato;
- tempo: variabili di memorizzazione del tempo reale e del tempo simulato;
- lista degli eventi attivi : struttura dati di implementazione della lista ordinata
degli eventi attivi e dei loro tempi di occorrenza;
- registri di dati: variabili o liste di memorizzazione delle grandezze
necessarie per il calcolo delle uscite della simulazione (variabili endogene);
- procedura d’inizializzazione: inizializza variabili e registri; inizializza il
generatore di variabili stocastiche; inizializza la lista degli eventi attivi;
- procedura aggiornamento tempo;
- procedura aggiornamento stato;
- modulo di generazione di uscita e report;
- modulo principale: implementa il ciclo di avanzamento della simulazione e
coordina il programma di simulazione.
La lista degli eventi attivi ( LEA o Scheduled Event List - SEL) all’istante
t contiene tutti gli eventi schedulati che devono accadere nel futuro con i
corrispondenti tempi di occorrenza. Questa è ordinata per tempi d’occorrenza
degli eventi non decrescenti. La procedura di simulazione consiste nella
ripetizione iterativa dei seguenti passi[1][2]:
- Rimozione del primo elemento nella SEL (t1,e1);
- Aggiornamento del tempo di simulazione a t1;
- Aggiornamento dello stato del sistema a x'= f(x, e1) (f rappresenta la
transizione di stato relativa all’evento e1);
- Cancellazione dalla SEL di eventi resi non più ammissibili dall’evento e1;
- Aggiunta nella SEL di eventi resi ammissibili dall’evento e1;
- Ordinamento della SEL in ordine cronologico crescente.
La fase d’inizializzazione della SEL consiste nell’inserimento nella lista di
tutti gli eventi che possono essere schedulati a partire dalle condizioni iniziali
del sistema. La procedura di simulazione termina quando non ci sono più eventi
nella SEL, oppure quando si è raggiunto il tempo finale di simulazione.
L’implementazione della SEL deve essere eseguita garantendo la massima
efficienza delle operazioni d’inserimento di un elemento in lista, ricerca di un
elemento in lista, cancellazione di un elemento dalla lista, riordino della lista.
Nella Figura 1-3 è mostrata la sequenza dei passi sopra descritti.
Lo schema simulativo “event driven” evolve producendo una lista di
“fotografie” del sistema in istanti di tempo discreti. Tali istanti di tempo sono
gli istanti di occorrenza degli eventi. Quindi, ogni fotografia del sistema
contiene:
Capitolo 1 - INTRODUZIONE 15
- lo stato del sistema;
- una lista di tutti gli eventi già schedulati (lista eventi attivi);
- eventuali contatori progressivi per il calcolo delle statistiche (variabili
endogene).
Per quanto riguarda il tempo di simulazione, esistono tre diverse connotazioni
d’avanzamento:
- tempo reale: è il tempo dal punto di vista del sistema reale (è una variabile
continua);
- tempo simulato: è il tempo dal punto di vista del modello (avanza per
eventi);
- tempo di esecuzione: è il tempo dal punto di vista del processore, è il tempo
di esecuzione del programma “simulatore”.
Ovviamente il tempo aggiornato nel modello di simulazione della Figura 1-3 è il
tempo simulato, che avanza ad ogni occorrenza di evento.
Inizializzazione
Schedule Event List
eα1
eα2
eβ1
eα3
...
t2
...
t4
t3
t1
Stato x Istante t
• •
Aggiorna lo stato:
x'=f(x,e)
Aggiorna il
tempo t'=t1
x' t'
MODELLO
Ingresso
eventi esterni
Aggiungi i nuovi
(ek,t'+τk) e
riordina
x' t'
Figura 1-3: Modello di simulazione “event driven”
Capitolo 1 - INTRODUZIONE 16
1.6 Introduzione alle Reti di Petri
Come già si è avuto modo di dire, non esistono regole fondamentali per
ottenere il modello di un sistema DES, ma la scelta del tipo di modello da usare
è strettamente legata alle finalità richieste alla simulazione. Quindi anche il
modo di descrivere il modello stesso dipende dall’uso che se ne vuole fare; a tal
proposito, esistono diversi approcci al problema, ma in linea generale, si può
affermare che un sistema ad eventi discreti, può essere rappresentato con una
rete di Petri, un automa a stati finiti o una rete di code.
In questa Tesi si è deciso di utilizzare un approccio a Reti di Petri
sostanzialmente perché queste garantiscono una serie di vantaggi:
1. La rappresentazione grafica che ne deriva, risulta molto intuitiva e facilmente
comprensibile anche da persone “non esperte”, visto che i grafi che si
realizzano per le descrizioni, risultano molto spontanei ma allo stesso tempo
costituiscono uno strumento formale che non ammette nessuna forma di
ambiguità.
2. La proprietà fondamentale che distingue le Reti di Petri dai modelli con
automi a stati finiti è la cosiddetta rappresentazione locale dello stato,
secondo la quale, lo stato di un sottosistema è rappresentato da una parte
specifica del modello complessivo (ad esempio la marcatura di un certo
insieme di posti e transizioni) chiaramente individuabile. Ciò offre la
possibilità, innanzi tutto di apportare le eventuali modifiche al modello,
andando ad operare localmente su una parte del modello globale; in secondo
luogo, l’evoluzione dinamica della rete interessa localmente solo una parte
limitata del modello.
Capitolo 1 - INTRODUZIONE 17
1.6.1 Le Reti di Petri
Una Rete di Petri (PN) è un grafo bipartito orientato. I nodi del grafo di una
PN sono i posti e le transizioni; essi sono collegati da archi orientati pesati che
vanno dai posti alle transizioni e viceversa. Il posto è identificato graficamente
da un cerchio, mentre una transizione è invece identificata da un rettangolo. In
ogni posto è presente un numero k di gettoni (tokens), rappresentati da pallini
neri, che identificano lo stato locale della rete (marcatura di un posto). L'insieme
delle marcature dei posti determina la marcatura complessiva della rete.
Una transizione si dice abilitata quando tutti i posti a monte ad essa hanno
almeno un numero di gettoni pari al peso dell'arco corrispondente, se questo non
è riportato si intende unitario. Una transizione abilitata, può scattare (l'istante di
scatto è determinato dall'istante in cui si ha l'occorrenza di un evento ad essa
associato). Lo scatto di una transizione provoca la rimozione da ogni posto a
monte e l'aggiunta ad ogni posto a valle di un numero di gettoni pari al peso
degli archi collegati. La marcatura di tutti i posti che non siano né d’ingresso e
né d’uscita alla transizione rimane inalterata. La regola di scatto definisce quindi
un flusso di gettoni all'interno della rete. Tuttavia, è bene osservare che il
numero di gettoni non si conserva necessariamente durante lo scatto di una
transizione. Per chiarire meglio il funzionamento, si consideri l’esempio
riportato in Figura 1-4(a) che rappresenta due operazioni concorrenti attivate in
seguito alla presenza di un token nel posto p1 e sincronizzate dallo scatto della
transizione t4; secondo le regole descritte, essa sarà abilitata a scattare se nel
posto p3 sono presenti almeno due token e nel posto p5 almeno un token. Si
consideri invece la transizione t1 a partire dallo stato della rete in Figura 1-4(b).
Essa è abilitata a scattare data la presenza di un token nel posto p1, quindi, in
seguito allo scatto la rete si porterà nel nuovo stato rappresentato in Figura
1-4(c). Si noti infine che i token sono interpretabili sia come risorse materiali,
quali la presenza di un pallet, che logiche, come ad esempio gli ordini di
esecuzione di una certa operazione.
Figura 1-4: Esempio di una Rete di Petri
Capitolo 1 - INTRODUZIONE 18
1.6.2 Le Reti di Petri Colorate
Le Reti di Petri Colorate (CPN)[4][5], oltre ad avere i vantaggi delle reti di
Petri esposti nei paragrafi precedenti, offrono la possibilità di sintetizzare con un
modello compatto sistemi anche complessi, poiché consentono di associare al
token un tipo di dato (colorset). In ogni posto è ammesso che ci siano più gettoni
dello stesso colore (multi-set) e l’ordine, in generale non è importante; tuttavia,
in certi contesti (come ad esempio quando il posto in questione modella una
coda di missioni), può essere utile tenere presente che i tokens sono organizzati
in base all’ordine di arrivo nel posto.
Si descrive di seguito com’evolve la marcatura della rete, giacché rispetto
alle reti finora introdotte sono presenti delle novità sostanziali. Il problema
principale è dunque quello di come definire il concetto di transizione abilitata e
di come specificare la regola di scatto.
Per meglio chiarire tali aspetti, siccome per queste reti i gettoni sono delle
ennuple, bisogna tenere conto di:
- quali gettoni sottrarre dai posti in ingresso ad una transizione;
- quali gettoni aggiungere nei posti di uscita.
La scelta dei gettoni da eliminare è realizzata utilizzando delle funzioni
guardia in corrispondenza delle transizioni. Tali funzioni, determinano insieme
alle condizioni di abilitazione delle reti di Petri, la nuova condizione di
abilitazione. La guardia è una condizione logica da verificare e può valutare se
nei posti cui fa riferimento esiste un insieme di token aventi determinate
caratteristiche, espresse nella guardia stessa. Dunque affinché una transizione
risulti abilitata è necessario che siano soddisfatte le condizioni di abilitazione
valide per le reti di Petri ed in più sia soddisfatta la guardia. I tokens da
eliminare, in seguito allo scatto della transizione, saranno tra quelli che
soddisfano la guardia ed in particolare il loro numero per ogni posto a monte
della transizione, sarà indicato rispettivamente dal peso di ogni arco entrante
nella transizioni stessa. Nel caso in cui una transizione non abbia guardia, la sua
condizione di abilitazione è quella valida per le reti di Petri.
I gettoni che invece saranno accodati nei posti a valle saranno indicati dalle
funzioni d’arco presenti in corrispondenza degli archi uscenti da una transizione.
Volendo riprendere quanto appena detto in modo più formale, seguendo la
notazione descritta il letteratura[4], si dirà che:
un multi-set m è un insieme che può contenere occorrenze multiple di elementi
di un insieme non vuoto S. Formalmente, un multi-set è una funzione
m∈[S→N], dove N è un insieme di interi non negativi; essa è rappresentata
mediante le seguente somma formale:
Capitolo 1 - INTRODUZIONE 19
sm(s)
Ss
∑
∈
Con SMS si denota l’insieme di tutti i multi-set definiti sull’insieme S. Gli interi
non negativi {m(s)|s∈S} sono i coefficienti del multi-set e rappresentano il
numero di occorrenze dell’elemento s all’interno del multi-set. Le operazioni di
addizione, moltiplicazione per uno scalare e confronto di multi-set sono definite
come segue:
m1+ m2= )s(s)m(s)(m
Ss
21∑
∈
+
n*m= )sm(s)*(n
Ss
∑
∈
m1 ≤ m2 = (s)m(s)m:Ss 21 ≤∈∀
Il tipo di una variabile, v è denotato come Type(v); Type(expr) denota il tipo di
un’espressione, expr; Var(expr) denota l’insieme delle variabili contenute in
un’espressione expr. In aggiunta, si definisce binding di un insieme di variabili
V, la funzione che associa ad ogni variabile v∈V un elemento b(v) ∈Type(v);
expr<b> rappresenta il valore ottenuto valutando un’espressione, expr, nel
binding, b, cioè sostituendo ad ogni variabile v∈Var(expr) il valore
b(v)∈Type(v) determinato dal binding. Un’espressione senza variabili si dice
che è un’espressione chiusa.
Una CPN è una 9-pla CPN=(S,P,T,A,N,C,G,E,I)
dove:
S è un insieme non vuoto di tipi, chiamati colorset.
P è un insieme finito di posti rappresentati graficamente da cerchi.
T è un insieme finito di transizioni, che include transizioni istantanee
(rappresentate mediante rettangoli neri) e transizioni temporizzate (rappresentate
mediante rettangoli vuoti).
A è un insieme finito di archi tali che P∩ T= P ∩ A= T∩ A=∅ .
N è una funzione nodo: A → P×T ∪ T ×P.
C è una funzione colore: P → S.
G è una funzione guardia; essa è definita nell’insieme T e restituisce
un’espressione G(t) tale che ∀ a∈A:[Type(G(t))=B ∧ Type(Var(G(t))) ⊆S],
dove B è un tipo booleano.
E è una funzione espressione d’arco; essa è definita nell’insieme A e restituisce
un’espressione E(a) tale che ∀ a∈A:[Type(E(a))=C(p)MS ∧ Type(Var(E(a))) ⊆S]
dove p è un posto di N(a).
I è una funzione inizializzazione; essa è definita nell’insieme P e restituisce
l’espressione chiusa I(p) tale che ∀ p∈P:[Type(I(p))=C(p)MS].
Capitolo 1 - INTRODUZIONE 20
Al fine di definire il binding di una transizione t, occorre prima introdurre le
seguenti notazioni:
A(t)={a∈A|N(a) ∈ P×{t}∪ {t}× P};
Var(t)= {v|v∈Var(G(t)) ∨ ∃ a∈A(t):v∈Var(E(a))}.
Il binding di una transizione t è una funzione b(.) definita sull’insieme Var(t)
tale che ∀ v∈Var(t): b(v) ∈ Type(v) e G(t)<b>=1, cioè la funzione guardia è
vera. B(t) denota l’insieme di tutti i binding per la transizione t.
Un token è una coppia (p,c) dove p∈P e c∈C(p), mentre un binding element è
una coppia (t,b) dove t∈T e b∈B(t). L’insieme di tutti i token è denotato
mediante TE mentre l’insieme di tutti i binding element è denotato mediante BE.
Una marcatura è un multi-set su TE mentre uno step è un multi-set finito e non
vuoto su BE. L’insieme di tutte le marcature è denotato mediante il simbolo M,
mentre l’insieme di tutti gli step è denotato mediante Y.
Uno step Y è abilitato nella marcatura M se e solo se la seguente proprietà è
soddisfatta:
∀ p∈P: M(p)bt)E(p,
Yb)(t,
≤><∑
∈
.
Quando uno step è abilitato in una certa marcatura M1 esso può occorrere e, nel
caso in cui la transizione t scatti, la marcatura della rete cambia in accordo con
l’espressione:
.bp)E(t,)bt)E(p,(p)(M(p)M:Pp
Yb)(t,Yb)(t,
12 ∑∑
∈∈
><+><−=∈∀
La nuova marcatura M2 è detta raggiungibile da M1 e lo si denota mediante
M1[Y> M2.
Una CTPN è una CPN in cui ad ogni transizione è associato un ritardo di tempo,
che rappresenta il tempo richiesto perché la transizione completi lo scatto. Le
transizioni aventi ritardo nullo sono dette istantanee.
Nel seguito di questa tesi verranno utilizzate le seguenti notazioni:
Ogni token è una n-pla <t>=(c1, c2, …, cn), dove cj è un intero.
Un token decolorato è rappresentato come: (1).
Esempi di token: (1,0,300,-5), (0,5), (3), (-8), (0), (1).
Capitolo 1 - INTRODUZIONE 21
Il formato dei token può variare da un posto all’altro, ma all’interno di un
posto essi devono avere tutti lo stesso formato.
I token all’interno di ogni posto sono organizzati in una struttura ad array:
Pi = [ <t1>, <t2>, <t3>, …, <tn> ]
Esempio: Pi=[(1,2,0,3), (2,6,0,0), (1,2,0,3), (3,0,0,0)]
E’ ammesso che all’interno di un posto siano presenti più token dello stesso
colore; questo perché il posto è un contenitore di token (multi-set), in cui un
token di uno stesso colore può essere presente con cardinalità maggiore di uno.
Infine si riporta l’insieme delle possibili funzioni che si troveranno, nel seguito
in questa tesi, nelle espressioni d’arco:
Funzione PROIEZIONE:
pr(Pi, c1, c2, …, cn ). Definizione:
Per ogni token <t> del posto Pi,
costruisce un nuovo token formato dalle
componenti c1,c2, …, cn di <t>.
Esempio:
Se P1=[(1,3,5,1,1), (2,30,6,2,2)] allora:
pr(P1,1,2,3,4,5)=[(1,3,5,1,1),(2,30,6,2,2)];
pr(P1,2,4) =[(3,1), (30,2)];
pr(P1,2) =[(3), (30)].
Funzione CONCATENAZIONE:
conc(<t1>,<t2>, …, <tn>). Definizione:
Dati i token <t1>,<t2>,…,<tn>,
costruisce un nuovo token avente il
formato:
(<t1>,<t2>,…,<tn>)
Esempio:
Se P{1,14}=[(1,1,115,2)], allora:
conc(pr(P{1,14},1,2),(0),(-1)) = (1,1,0,-1).
Inoltre: conc((1))=(1).
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
