Christian Carafa
A.A. 2003/2004
6
Amburgo, nell’allora Germania Ovest, per un corso avanzato sulla teoria generale
delle reti di processi e sistemi.
Il primo convegno europeo sulle applicazioni e sulla teoria delle reti di Petri fu
tenuto nel 1980 a Strasburgo, in Francia. Da questo momento in poi ogni anno
furono organizzati convegni in differenti locazioni in Europa.
Nel luglio del 1985, venne iniziata un’altra serie di convegni internazionali.
Questa nuova serie poneva enfasi sulle reti temporizzate e stocastiche e sulle loro
applicazioni. Il primo di questi convegni si tenne in Italia, a Torino.
Dal 1985 in poi, fra i vari modelli ad eventi discreti, le reti di Petri hanno
assunto un’importanza predominante a causa di vari fattori:
ƒ Le RP sono un formalismo grafico e matematico allo stesso tempo. Essendo
un formalismo grafico sono di facile comprensione, possono essere usate
come strumento di aiuto visuale in fase di progetto e di specifica,
consentono al progettista e all'operatore di un sistema di parlare lo stesso
linguaggio. Essendo un formalismo matematico, consentono di applicare una
vasta gamma di tecniche di analisi (ad esempio basate sull'algebra lineare)
allo studio di proprietà di interesse.
ƒ Permettono di dare una rappresentazione compatta di sistemi con un grande
spazio di stato. Infatti non richiedono di rappresentare esplicitamente tutti i
valori possibili dello stato di un sistema, ma solo le regole che governano la
sua evoluzione. Spesso una struttura di rete finita può essere usata per
descrivere sistemi che hanno un numero infinito di stati.
ƒ Permettono di rappresentare esplicitamente il concetto di concorrenza, cioè
di attività che possono venire svolte parallelamente.
ƒ Consentono una rappresentazione modulare; cioè, se un sistema è composto
da più sottosistemi che interagiscono fra loro, è generalmente possibile
rappresentare ciascun sottosistema come una semplice sottorete e poi,
mediante operatori di rete, unire le varie sottoreti per ottenere il modello del
sistema complessivo.
Con il termine "rete di Petri" si indica dunque una ampia classe di modelli ad eventi
discreti. È tuttavia possibile associare a questi modelli una struttura di
temporizzazione all’evoluzione della rete per definire varie classi di modelli
temporizzati, sia deterministici che stocastici.
Christian Carafa
A.A. 2003/2004
7
Se da una parte la semplicità di comprensione e di uso delle reti di Petri ha
determinato negli anni un interesse sempre maggiore nei loro riguardi, dall’altra la
difficoltà e la complessità nell’assemblare il modello di un processo reale di
dimensioni significative, come ad esempio una catena di montaggio con relativi
robot che assemblano parti prelevate da AGV, rendono spesso difficile la
modellistica, la connessione e non ultima la comprensione del sistema globale.
Infatti se un modulo, ovvero una sottorete, risulta composta da qualche posto e da
qualche transizione, non è raro che l’intero sistema sia composto da alcune decine
tra posti e transizioni con una conseguente perdita di leggibilità e distinzione
funzionale all’interno dello schema di assemblaggio nonché di difficoltà nella
validazione del modello.
Fortunatamente, in questi ultimi anni, in aiuto ai progettisti sono nati diversi
software di ausilio i quali permettono di disegnare, testare nonché simulare il
modello del sistema da loro realizzato. Il panorama software è oggi ampio ma non
unificato; infatti i software di simulazione si differenziano per le loro funzionalità,
ma nessuno di questi si può dire completo per quanto riguarda lo studio e l’analisi
dei modelli con reti di Petri.
Lo scopo di questa tesi è dunque proprio quello di determinare quali sono i
requisiti che un software di simulazione deve avere per poter affrontare lo studio e
l’analisi delle reti di Petri. Una volta determinati tali requisiti si è passati alla
valutazione di alcuni software, stilando delle schede tecniche per ognuno di essi
così da fornire una panoramica sulle potenzialità di tali simulatori.
Per raggiungere tale obiettivo, viene descritto dapprima il modello di rete di
Petri più semplice, detto rete posto/transizione (o rete P/T), che non consente di
rappresentare la temporizzazione degli eventi ma solo l'ordine con cui essi si
verificano. In seguito verranno introdotte anche le reti di Petri temporizzate,
deterministiche o stocastiche. Successivamente affronteremo il problema della
simulazione dei sistemi ad eventi discreti definendo la procedura da seguire per
realizzare un software di simulazione. Infine, sulla base di queste informazioni
verranno elencati i requisiti che un software di simulazione di reti di Petri deve
avere e verranno riportati i risultati sulla valutazione di alcuni software.
In conclusione verranno introdotti i metodi diretti di progettazione con le reti di
Petri ed un esempio pratico di progettazione di un sistema di assemblaggio.
Christian Carafa
A.A. 2003/2004
8
Capitolo Primo
Le Reti di Petri
1.1 Definizione di rete e sistema di rete
In questo capitolo viene definita la struttura algebrica e grafica delle reti
posto/transizione (P/T). Aggiungendo a tale struttura una marcatura si ottiene una
rete marcata (o sistema di rete), cioè un sistema ad eventi discreti, di cui si
studieranno le leggi che governano l'evoluzione dinamica.
1.1.1 Struttura delle reti posto/transizione
Una rete P/T è un grafo bipartito orientato e pesato. I due tipi di vertici sono
detti: posti (rappresentati da cerchi) e transizioni (rappresentate da barre o da
rettangoli).
Una rete posto/transizione (rete P/T ) è una struttura N = (P,T,Pre,Post) dove:
• P = {p
1
,p
2
, … , p
m
} è l'insieme degli m posti.
• T = {t
1
,t
2
, … , t
n
} è l'insieme delle n transizioni.
• Pre : P x T → N è la funzione di pre-incidenza che specifica gli archi diretti
dai posti alle transizioni (detti archi "pre") e viene rappresentata mediante
una matrice m x n. Più esattamente, Pre(p,t) indica quanti archi vanno dal
posto p alla transizione t.
• Post : P x T → N è funzione di post-incidenza che specifica gli archi diretti
dalle transizioni ai posti (detti archi "post") e viene rappresentata
mediante una matrice m x n. Più esattamente, Post(p,t) indica quanti archi
vanno dalla transizione t al posto p.
Si suppone che P∩T = ∅ (cioè posti e transizioni sono insiemi disgiunti) e che
P∪T ≠ ∅ (cioè la rete è costituita da almeno un posto o da una transizione).
Christian Carafa
A.A. 2003/2004
9
Le matrici Pre e Post sono delle matrici di interi non negativi. Si denota Pre(•,t)
la colonna della matrice Pre relativa alla transizione t, e Pre(p,•) la riga della
matrice Pre relativa al posto p. La stessa notazione vale per la matrice Post.
L'informazione sulla struttura di rete contenuta nelle matrici Pre e Post può
essere compattata in un'unica matrice, detta di incidenza.
Data una rete N = (P,T,Pre,Post), con m posti e n transizioni, la matrice di
incidenza C : P x T → Z è la matrice m x n definita come: C = Post - Pre cioè il
generico elemento di C vale C(p,t) = Post(p,t) - Pre(p,t).
Dunque la matrice di incidenza è una matrice di interi. Un elemento negativo è
associato a un arco "pre" (da posto a transizione), mentre un elemento positivo è
associato a un arco "post" (da transizione a posto).
Nel compattare le due matrici Pre e Post, spesso la matrice di incidenza perde
qualche informazione sulla struttura della rete. Ad esempio, nella rete in Figura 1.1
tra il posto p
1
e la transizione t
1
vi è sia un arco "pre" che un arco "post"; si dice
che p
1
e t
1
costituiscono un cappio, cioè un ciclo orientato nel grafo della rete
costituito da una sola transizione e da un solo posto. In questo caso la somma
algebrica di Pre e Post determina un elemento C(p
1
,t
1
) = O, cioè dall'esame della
sola C non è possibile rilevare che vi sono archi tra questi due vertici. Una rete
senza cappi è detta, pura.
Figura 1.1 – Una rete di Petri Posto/Transizione
Infine, data un transizione t ∈ T si definiscono i seguenti insiemi di posti:
ƒ
•
t = {p ∈ P | Pre(p,t) > 0}: è l'insieme dei posti in ingresso a t,
ƒ t
•
= {p ∈ P | Post{p,t) > 0}: è l'insieme dei posti in uscita da t;
dato un posto p ∈ P si definiscono i seguenti insiemi di transizioni:
ƒ
•
p = {t ∈ T | Post(p,t) > 0}: è l'insieme delle transizioni in ingresso a p,
Christian Carafa
A.A. 2003/2004
10
ƒ p
•
= {t ∈ T | Pre(p,t) > 0}: è l'insieme delle transizioni in uscita da p.
1.1.2 Marcatura e sistema di rete
Mediante la marcatura è, possibile definire lo stato di una rete P/T.
Una marcatura è una funzione M : P → N che assegna a ogni posto un numero
intero non negativo di marche (o token).
Graficamente le marche vengono rappresentate con pallini neri dentro i posti, come
in figura 1.2, dove il posto p
1
contiene un token.
Fig. 1.2 – Marcatura iniziale di una rete
Una rete N con una marcatura iniziale M
0
è detta una rete marcata o sistema di
rete, e viene indicata come {N,Mo}. Si è soliti indicare una marcatura come un
vettore colonna con m componenti (tanti quanti sono i posti).
Con riferimento alla figura 1.2 la marcatura iniziale M
0
si rappresenta con il
seguente vettore colonna: M = [ 1 0 0 0 ]
T
.
1.1.3 Abilitazione e scatto
Una transizione t è abilitata dalla marcatura M se M ≥ Pre(·,t) cioè se ogni posto
p ∈ P della rete contiene un numero di marche pari o superiore a Pre(p,t). Per
indicare che t e abilitata da M si scrive M[t’⟩. Per indicare che t' non è abilitata da M
si scrive ¬M[t’⟩.
Dall'ispezione visiva di una rete marcata è facile rendersi conto se una
transizione t è abilitata occorre che ogni posto in ingresso alla transizione, cioè ogni
posto p∈
•
t, abbia un numero di marche pari o superiore agli archi "pre" che vanno
dal posto alla transizione.
Una transizione che non possiede archi in ingresso, come la transizione t in figura
Christian Carafa
A.A. 2003/2004
11
Figura 1.3, è detta transizione sorgente. Una transizione sorgente t è sempre
abilitata, poiché, essendo in tal caso Pre(·,t) = O, la condizione M ≥ Pre(·,t) è
soddisfatta per ogni marcatura M.
Fig. 1.3 – Una transizione senza archi in ingresso
Una transizione t abilitata da una marcatura M può scattare un numero di
marche pari ad M. Lo scatto di t rimuove Pre{p,t) marche da ogni posto p∈P e
aggiunge Post(p,t) in ogni posto p∈P, determinando una nuova marcatura M'.
Cioè vale M' = M-Pre(·,t)+Post{·,t) = M+C(·,t).
Per indicare che lo scatto di t da M determina la marcatura M' sì scrive M[t}M'.
Una sequenza di transizioni σ = t
j1
t
j2
··· t
jr
∈ T* è abilitata da una marcatura M
se la transizione t
j1
è abilitata da M e il suo scatto porta a M
1
= M + C(·,t
j1
); la
transizione t
j2
, è abilitata da M
1
e il suo scatto porta a M
2
= M
1
+ C(·,t
j2
); ecc.
Una sequenza abilitata σ viene anche detta sequenza di scatto e a essa corrisponde
la traiettoria: M[t
j1
⟩ M
1
[t
j2
⟩ ... M
r
.
Per indicare che la sequenza σ è abilitata da M si scrive M[σ⟩. Per indicare che lo
scatto di σ da M determina la marcatura M' si scrive M[σ⟩M'.
La sequenza vuota ε (cioè la sequenza di lunghezza zero) è abilitata da ogni
marcatura M e vale M[ε⟩M.
Ad esempio, nella rete in Figura 1.2 una possibile sequenza di transizioni
abilitata dalla marcatura iniziale è σ = (t
1
t
1
t
2
t
3
), il cui scatto porta alla marcatura
M' =[011 O]
T
.
A una rete marcata ⟨N,M
o
⟩ è possibile associare una ben precisa dinamica, data
dall’insieme di tutte le sequenze di transizioni che possono scattare a partire dalla
marcatura iniziale.
Il comportamento (o linguaggio) di una rete marcata ⟨N,M
0
⟩ è l'insieme delle
sequenze di scatto abilitate dalla marcatura iniziale, cioè l'insieme
L(N,M
0
) = {σ ∈ T* | M
0
[σ⟩}
Una marcatura M è raggiungibile in ⟨N,M
0
⟩ se esiste una sequenza di scatto σ tale
che M
0
[σ⟩M. L'insieme di raggiungibilità di una rete marcata ⟨N,M
0
⟩ è l'insieme delle
marcature che possono venir raggiunte a partire dalla marcatura iniziale, cioè
l'insieme R(N,Mo) = {M ∈ N
m
| ∃ σ ∈ L(N,M
0
) : M
0
[σ⟩M}.
Si noti che nella precedente definizione si considera anche la sequenza vuota, che
Christian Carafa
A.A. 2003/2004
12
non contiene alcuna transizione.
Si osservi inoltre che una duplice semantica (cioè significato) è associata alla
marcatura di una rete: da un lato, la marcatura indica lo stato in cui si trova il
sistema; dall'altro, essa specifica quali attività possono venire eseguite, cioè quali
sono le transizioni abilitate. Dallo scatto delle transizioni dipende invece il
comportamento dinamico di una rete marcata.
1.1.4 Equazione di stato e proprietà dinamiche elementari
La definizione di calcolo della marcatura raggiunta per effetto dello scatto di una
transizione mediante una semplice equazione matriciale, può essere estesa a una
sequenza di transizioni σ. Per prima cosa si definisce il vettore di scatto associato
ad una sequenza.
Data una rete N con insieme di transizioni T = {t
1
,t
2
,…,t
n
} e una sequenza di
transizioni σ ∈ T*, si definisce vettore caratteristico di σ (o anche vettore di scatto
associato a σ) il vettore σ ∈ ℵ
m
, la cui generica componente σ
i
, = |σ|
ti
indica quante
volte la transizione t, compare in σ.
Definizione di Equazione di stato. Sia ⟨N,Mo⟩ una rete marcata e sia C la sua
matrice di incidenza. Se M è raggiungibile da M
0
scattando la sequenza di
transizioni σ vale allora: M = M
0
+ C·σ.
Si consideri, ad esempio, la rete marcata in Figura 1.2 la cui matrice di incidenza è
già stata calcolata. Può facilmente verificarsi che la marcatura M' = [0 1 1 0]
T
,
raggiungibile dalla marcatura iniziale M
0
=[1 0 0 0]
T
eseguendo la sequenza σ = t
1
t
1
t
2
t
3
, soddisfa l’equazione
σ⋅+= CMM
0
'
−
+
=
0
1
1
1
0
0
0
1
0
1
1
0
E’ ora utile introdurre il concetto di conflitto.
Due transizioni t e t’ sono in conflitto strutturale se
•
t ∩
•
t’ ≠ 0, cioè se esiste un
posto da cui partono sia un arco verso t che un arco verso t'.
Christian Carafa
A.A. 2003/2004
13
Data una marcatura M, si dice ancora che tali transizioni t e t' sono in conflitto ef-
fettivo se M ≥ Pre(·,t) e M ≥ Pre(·,t') ma M non è maggiore di Pre(·,t) + Pre(·,t'),
cioè se sia l'una che l'altra sono abilitate da M, ma tale marcatura non contiene un
numero sufficiente di marche per consentire lo scatto di entrambe le transizioni.
Ad esempio, nella rete in Figura 1.2 le transizioni t
1
e t
2
sono in conflitto strutturale.
1.2 Modellazione con reti di Petri
In questo paragrafo, si presenteranno dapprima alcune strutture elementari di reti
P/T e le semantiche a esse associate. Verrà inoltre presentato un esempio in cui le
reti di Petri vengono usate per rappresentare sistemi tratti da vari campi applicativi:
protocolli di comunicazione, elaborazione di flussi di dati, sistemi operativi, processi
produttivi, sistemi di trasporto.
1.2.1 Strutture elementari
In un sistema ad eventi discreti, l'ordine con cui si verificano i vari eventi può
essere soggetto a vincoli di varia natura. In un modello RP, ciò corrisponde a porre
dei vincoli sull'ordine con cui scattano le transizioni. È possibile, a questo proposito,
individuare quattro principali strutture.
ƒ Sequenzialità. Gli eventi si succedono in un ben determinato ordine.
In Figura 1.4(a) l'evento e
2
può verificarsi solo dopo che si è verificato e
1
mentre, l'evento e
3
può verificarsi solo dopo che si è verificato e
2
.
ƒ Parallelismo (o concorrenza strutturale).Gli eventi possono verificarsi
senza alcun ordine prefissato. In Figura 1.4(b), dopo che scatta la
transizione par begin (parallel begin) gli eventi e
1
, e
2
ed e
3
sono
simultaneamente abilitati. La struttura del parallelismo è tale che i tre eventi
non sono in conflitto strutturale e possono verificarsi in un qualunque ordine,
poiché il verificarsi di un qualunque evento non modifica lo stato di
abilitazione degli altri. La transizione par begin crea una ramificazione (fork)
nel flusso degli eventi.
ƒ Sincronizzazione. Più eventi paralleli devono essersi verificati per poter
procedere. In Figura 1.4(c), gli eventi e
1
, e
2
ed e
3
possono verificarsi
parallelamente ma la transizione par end (parallel end) non può scattare se
Christian Carafa
A.A. 2003/2004
14
essi non si sono tutti verificati. La transizione par end crea una confluenza
(join) nel flusso degli eventi.
ƒ Scelta (o conflitto strutturale). Un solo evento tra i tanti possibili può
verificarsi. In Figura 1.4(d), uno solo tra gli eventi e
1
, e
2
. ed e
3
può
verificarsi, perché lo scatto di una qualunque transizione disabilita le altre. Si
noti che la struttura della scelta è caratterizzata da un posto in ingresso a
più transizioni che determina un conflitto strutturale.
Figura 1.4 - Strutture elementari di reti di Petri: (a) sequenzialità;
(b) parallelismo; (c) sincronizzazione; (d) scelta.
Alle strutture elementari qui viste è anche spesso possibile associare una semantica
duale, in cui si tiene conto non tanto dell'ordine con cui scattano le transizioni,
quanto piuttosto delle variazioni delle marcature. In questo caso, le marche
rappresentano delle risorse disponibili, è possibile individuare tre principali
strutture.
ƒ Smontaggio. Un insieme di parti viene separato in parti elementari. In
Figura 1.5(a) la rete marcata rappresenta l'operazione con cui un'automobile
viene smontata, ottenendo quattro ruote e un telaio. La transizione è simile
al par begin visto precedentemente.
Christian Carafa
A.A. 2003/2004
15
Figura 1.5 - Strutture elementari di reti di Petri: (a) smontaggio;
(b) montaggio; (c) mutua esclusione
ƒ Montaggio. Più parti elementari si uniscono per formare un insieme. In
Figura 1.5(b), la rete marcata descrive sinteticamente con quali ingredienti
si prepara una nota salsa. La transizione è simile al par end visto
precedentemente.
ƒ Mutua esclusione. Una risorsa (o un insieme di risorse) è disponibile, ma
mentre essa viene impegnata per una data operazione non è utilizzabile per
altre operazioni. In Figura 1.5(c), un solo robot è disponibile per caricare
parti su due macchine. Quando il posto robot è marcato il robot è
disponibile, mentre se è marcato il posto carica m
2
oppure carica m
1
il robot
è impegnato nella corrispondente operazione. Se dalla situazione in figura
scatta la transizione t
1
, si inizia il caricamento della prima macchina e il
posto robot si svuota, dunque la transizione t
3
, il cui scatto corrisponde
all'impegno del robot per il caricamento della seconda macchina, è di-
sabilitata fino a che lo scatto di t
2
, non riporti la marca nel posto robot.
Similmente, dalla situazione in figura lo scatto di t
3
disabilita t
1
sino allo
scatto successivo di t
4
. La struttura è simile alla "scelta" vista in Figura
1.4(d).
1.2.2 Esempio di Modellazione
Uno dei campi applicativi in cui le reti di Petri hanno grande importanza è quello
di processi produttivi o manufacturing (sono stati pubblicati su questo argomento
Christian Carafa
A.A. 2003/2004
16
diversi libri).
Quando le RP vengono usate come modelli di sistemi produttivi, i posti della rete
possono rappresentare lo stato di una risorsa (macchine, parti da lavorare, robot,
nastri trasportatori) oppure una data operazione. Una marca in un posto che
rappresenta una risorsa indica che la risorsa è disponibile, mentre se il posto è
vuoto la risorsa non è disponibile. Una marca in un posto che rappresenta una
operazione indica che l'operazione è in corso di esecuzione, mentre se il posto è
vuoto l'operazione non è in corso di esecuzione. Il numero di marche in un posto
può anche essere maggiore di uno, per indicare quante unità di risorsa sono
disponibili, oppure su quante unità viene eseguita l'operazione. Una transizione
rappresenta l'inizio o la fine di una operazione, oppure l'evento associato al cambio
di stato di una risorsa.
Alcuni modelli di sistemi elementari sono mostrati in Figura 1.6(a)-(d).
Figura 1.6 - Rete di Petri di alcuni processi produttivi: (a) una macchina non affidabile; (b) un magazzino
di capacita, infinita; (c) un magazzino di capacità finita; (d) un magazzino multiclasse; (e) una cella di
manifattura.
ƒ In Figura 1.6(a) è descritto il modello di una macchina non affidabile. Le
transizioni hanno il seguente significato: t
1
rappresenta l'inizio di una
Christian Carafa
A.A. 2003/2004
17
lavorazione, t
2
, la fine di una lavorazione, t
3
un guasto, t
4
una riparazione. I
posti hanno il seguente significato: p
1
è marcato se la macchina è ferma, p
2
è marcato se la macchina è in lavorazione, p
3
è marcato se la macchina è
guasta. Per rappresentare una macchina multiservente non occorre
modificare tale struttura di rete ma è sufficiente assegnare alla rete tante
marche quanti sono i serventi; in tal caso il numero di marche nel posto p
1
indica quanti serventi sono fermi, il numero di marche nel posto p
2
indica
quanti serventi sono in lavorazione e il numero di marche nel posto p
3
indica
quanti serventi sono guasti.
ƒ In Figura 1.6(b) è descritto il modello di un magazzino di capacità infinita. La
transizione t
1
rappresenta il deposito di un prodotto, t
2
il prelievo. Il numero
di marche nel posto p indica il numero di prodotti contenuto nel deposito:
nella marcatura iniziale in figura il posto p non è marcato e il deposito è
vuoto.
ƒ In Figura 1.6(c) è descritto il modello di un magazzino di capacità finita.
Rispetto al modello precedente è stato introdotto il posto p' la cui marcatura
indica il numero di locazioni libere nel deposito. Dunque, assumendo che
ogni prodotto occupi una locazione, lo scatto di t
1
non solo fa aumentare di
una unità il numero di prodotti contenuti nel deposito (cresce la marcatura
del posto p) ma riduce anche di una unità il numero di locazioni libere
(diminuisce la marcatura del posto p').
ƒ In Figura 1.6(d) è descritto il modello di un magazzino multiclasse (due
classi di prodotti) di capacità finita (k locazioni). La marcatura del posto p'
indica ancora il numero di locazioni libere nel deposito, mentre la marcatura
dei posti p
1
e p
2
indica, rispettivamente, il numero di prodotti di classe 1 e di
classe 2 contenuti nel deposito. La transizione t
1
(t
3
) rappresenta il deposito
di un prodotto di classe 1 (classe 2), mentre t
2
(t
4
) rappresenta il prelievo di
un prodotto di classe 1 (classe 2). Si è assunto che ogni prodotto di classe 1
occupi una locazione, e che ogni prodotto di classe 2 occupi due locazioni.
ƒ Infine, in Figura 1.6(e) è descritto un modello più complesso relativo a una
cella di manifattura dove si lavorano parti composite P
ab
. La cella consiste di
una singola macchina utensile. Una parte composita viene smontata in due
parti elementari Pa e P
b
, che vengono una alla volta lavorate dalla macchina.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
