Reti di Petri:
sviluppo di un toolbox di
simulazione, controllo ed
analisi a macromoduli
Candidato :
Giuseppe Circhetta
Relatori :
Chiar.mo Prof. Aldo Balestrino
Chiar.mo Prof. Andrea Caiti
A cosa servono
Le reti di Petri sono un potente strumento per formalizzare la
descrizione di sistemi. I punti di forza sono dati dalle caratteristiche
di astrazione e generalità che permettono la modellistica di molti
problemi quali:
•
•
•
•
•
•
•
•
protocolli di comunicazione
sistemi fault-tolerant
architetture multiprocessori
data flow
sistemi di controllo
catene di montaggio
macchine a stati
altre attività nelle industrie
Come sono fatte
Una rete di Petri è un grafo orientato bipartito, l’insieme dei suoi
nodi può essere diviso in due sottoinsiemi e gli archi sono sempre
diretti dai nodi di un sottoinsieme ai nodi dell’altro.
I nodi possono essere di due tipi:
Posti o tappe (“places”)
Transizioni (“transitions”)
Gli archi uniscono posti a transizioni o transizioni a posti:
In questo caso il posto è
detto di ingresso
dato che è in
entrata alla transizione
Invece in questo
caso il
posto è detto di
uscita
Regola di scatto
Ad ogni posto può essere associato un numero intero di marche o
“token” rappresentato da uno o più pallini.
Per fare questo viene introdotta una funzione marcatura M della rete e
si dice che il “place” p è marcato con M(p) o che contiene M(p) “token”.
Al place può essere associata una capacità indicante il numero di “token”
che può contenere. Inoltre ad un arco può essere associato un peso che
stabilisce il numero di token che devono essere prelevati per attivare la
transizione. Ad esempio:
Solo se c’è almeno un
token viene attivata
questa strada
(un peso unitario
non viene indicato)
2
Solo se ci sono almeno
due token viene
attivata questa strada
Definizione formale
Una rete può essere rappresentata da due insiemi e da due funzioni:
N = (P, T, Pre, Post)
dove:
•P è l’insieme degli m posti
•T è l’insieme delle n transizioni
•Pre è la funzione di pre-incidenza
•Post è funzione di post-incidenza
Matrice di
incidenza
Abilitazione
Una transizione t è abilitata dalla marcatura M se e solo se:
2
Insieme dei posti in
ingresso alla
transizione
Effetti dello scatto
Marcatura
iniziale
2
[1 2 0]’
3
Nuova
marcatura
[0 0 3]’
Per ogni
transizione
abilitata
Archi inibitori
Esiste la possibilità di inibire una transizione dall’esterno:
Arco inibitore
la transizione non scatta se il posto a monte dell’arco inibitore ha un token
(o quanti ne indica il peso dell’arco ). Si parla in questo caso di reti di Petri
estese.
E’ stato dimostrato che le reti di Petri estese hanno capacità espressiva
pari alla macchina di Turing.
Raggiungibilità
Per descrivere tutte le possibili marcature che possono essere ottenute
mediante una sequenza di scatti, a partire da una marcatura iniziale,
bisogna definire l’insieme di raggiungibilità e l’albero di raggiungibilità.
Prima di definire l’insieme di raggiungibilità è opportuno dare il concetto
di raggiungibilità in un passo: data una rete marcata e due
marcature M e M’, si dice che M’ è raggiungibile in passo da M, se esiste
una transizione t che scattando da come risultato la marcatura M’.
Insieme di raggiungibilità
L’insieme di raggiungibiltà Rn(M) di una rete marcata è il più piccolo
insieme di marcature tale che se M’ è raggiungibile in un passo da M e
se M’’ è raggiungibile in un passo da M’ , allora anche M’’ appartiene a
tale insieme.
Proprietà analitiche
Le proprietà analitiche sono di due tipi:
1. Comportamentali;
2. Strutturali;
Dipendono dalla
marcatura iniziale
Dipendono solo dalla
struttura della rete
Entrambi i tipi sono importanti per lo studio ed il progetto di un
sistema modellato con una rete di Petri ma richiedono un certo
sforzo computazionale.
Un esempio di
modellazione con RP
Un esempio di
modellazione : AGV
Un esempio di
modellazione : linea
di produzione 1
Un esempio di
modellazione : linea
di produzione 2
Un esempio di
modellazione :
modello completo
Cella 1
AGV
Cella 2
Schema generale di
controllo ed analisi
proposto
Vantaggi della
suddivisione in blocchi
•Alleggerimento computazionale;
•Facilità di assemblaggio;
•Comprensione della funzione di un singolo modulo;
•Caratterizzazione di una RP secondo la Teoria dei Sistemi classica.
Pntool:
un simulatore a macromoduli
Pntool:
principali caratteristiche
•Portabilità;
•Supporto delle reti di Petri estese;
•Assemblaggio della rete a moduli predefiniti tipo Simulink;
•Analisi modulare;
•Possibilità di simulazioni Monte Carlo(supporto per
temporizzazioni stocastiche);
•Supporto per la creazione di librerie;
•Analisi statistica;
•Strumenti di controllo integrati;
Pntool:
principali comandi
Risultati delle simulazioni
•L’uso del simulatore nell’assemblaggio di sistemi complessi si è
dimostrato essere più semplice ed immediato rispetto ai molti altri
simulatori presenti(freeware e commerciali )
•La presenza di una libreria preassemblata permette un uso
immediato con la possibilità di assemblare moduli complessi a
partire da moduli semplici
•Il parallelismo con Simulink® ne aiuta l’integrazione con Matlab®
Pntool:
Futuri possibili sviluppi
•Supporto per reti di Petri continue
•Ampliamento della libreria
•Analisi prestazionale(calcolo del tempo di attraversamento)
•Automatizzazione della sintesi del le strutture di controllo
•Simulazione distribuita su più calcolatori