Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMAZIONE II
INTRODUZIONE ALLE RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA DEL NUCLEO TEMATICO
•
•
•
INTRODUZIONE ALLE RETI DI PETRI
EVOLUZIONE DINAMICA DI UNA RETI DI PETRI
STRUTTURE FONDAMENTALI DI UNA RETE DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
INTRODUZIONE
ALLE RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
CENNI STORICI
La teoria delle RETI DI PETRI fu sviluppata da Carl Adam Petri
(1926-2010) nel 1962.
•
•
•
•
Nel 1954 consegue la laurea in matematica presso l'Università di
Hannover.
Lavora dal 1959 al 1962 all'Università di Bonn come professore
associato.
Nel 1962 ottiene il PhD presso la Technische Universität
Darmstadt con una tesi dal titolo "Kommunikation mit Automaten"
(Comunicazione con gli automi), nella quale introduce la teoria
sulle reti di Petri
Nel 1988 è diventato professore onorario all'Università di
Amburgo.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Germania
Lipsia
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
DEFINIZIONE
Dicesi GRAFO DI PETRI 𝑁 la seguente quadrupla:
𝑁 = 𝑃, 𝑇, 𝐴, 𝜔
Dove:
𝑃 = 𝑝1 , 𝑝2 , … , 𝑝 𝑃
INSIEME DEI POSTI
𝑇 = 𝑡1 , 𝑡2 , … , 𝑡 𝑇
INSIEME DELLE TRANSIZIONI
𝐴⊆ 𝑃×𝑇 ⋃ 𝑇×𝑃
INSIEME DEGLI ARCHI ORIENTATI (RELAZIONE DI FLUSSO)
𝜔 ∶ 𝑃×𝑇 ⋃ 𝑇×𝑃 → ℕ
FUNZIONE DI PESO DEGLI ARCHI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
PROPRIETÀ
1. L’insieme dei posti 𝑃 è finito e non vuoto:
0 < 𝑃 < +∞
2. L’insieme delle transizioni 𝑇 è finito e non vuoto:
0 < 𝑇 < +∞
3. L’insieme dei posti e l’insieme delle transizioni sono disgiunti:
𝑃∩𝑇 =∅
4. Dalle proprietà (1) e (2) consegue che:
𝑃∪𝑇 ≠∅
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
RAPPRESENTAZIONE GRAFICA
• Ogni posto 𝑝𝑖 𝜖 𝑃 viene rappresentato graficamente da un cerchio;
p1
•
p2
…
p|P|
Ogni transizione 𝑡𝑗 𝜖 𝑇 viene rappresentata graficamente da una barra;
…
t1
t2
t|T|
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
RAPPRESENTAZIONE GRAFICA
• Ogni arco orientato 𝑎 𝜖 𝐴 ⊆ 𝑃 × 𝑇 ⋃ 𝑇 × 𝑃 viene rappresentato graficamente da
una freccia che può partire da un posto e arrivare in una transizione, oppure partire
da una transizione e arrivare ad un posto.
pi
pi
tj
tj
•
Per come è definito, l’insieme degli archi orientati NON contiene archi orientati che
partono da un posto ed arrivano in un posto.
•
Per come è definito, l’insieme degli archi orientati NON contiene archi orientati che
partono da una transizione ed arrivano in una transizione.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
DEFINIZIONE
Dato un grafo di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔 , si definiscono insieme dei posti in ingresso
I 𝑡𝑗 ed insieme dei posti in uscita O 𝑡𝑗 di una transizione 𝑡𝑗 𝜖 𝑇 i seguenti insiemi:
𝐼 𝑡𝑗 = 𝑝𝑖 𝜖𝑃 | 𝑝𝑖 , 𝑡𝑗 𝜖𝐴 ⊆ 𝑃
INSIEME DEI POSTI IN INGRESSO
𝑂 𝑡𝑗 = 𝑝𝑖 𝜖𝑃 | 𝑡𝑗 , 𝑝𝑖 𝜖𝐴 ⊆ 𝑃
INSIEME DEI POSTI IN USCITA
I 𝑡𝑗
O 𝑡𝑗
tj
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
GRAFO DI PETRI
RAPPRESENTAZIONE GRAFICA
• La funzione di peso degli archi 𝜔 associa un valore naturale non nullo ad ogni
arco orientato del grafo di Petri che viene rappresentato mediante una etichetta.
1
pi
3
pi
tj
tj
•
•
Se una etichetta è omessa, per convenzione il peso associato all’arco orientato
assume valore unitario.
Se un arco non è definito, la funzione di peso associa un valore nullo.
𝜔 𝑝𝑖 , 𝑡𝑗 𝜖 ℕ \ 0 ∀ 𝑝𝑖 , 𝑡𝑗
𝜔 𝑝𝑖 , 𝑡𝑗 = 0 ∀ 𝑝𝑖 , 𝑡𝑗
∉ 𝐴
∈ 𝐴
𝜔 𝑡𝑗 , 𝑝𝑖 𝜖 ℕ \ 0 ∀ 𝑡𝑗 , 𝑝𝑖
𝜔 𝑡𝑗 , 𝑝𝑖 = 0 ∀ 𝑡𝑗 , 𝑝𝑖
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
∉ 𝐴
∈ 𝐴
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI MARCATURA
DEFINIZIONE
Dato un grafo di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔 , si definisce FUNZIONE DI MARCATURA (o
MARKING) dei posti una funzione 𝑥 che associa a ogni posto 𝑝𝑖 𝜖 𝑃 un numero naturale.
𝑥∶𝑃 → ℕ
FUNZIONE DI MARCATURA
OSSERVAZIONE
Dato un grafo di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔 , la funzione di marcatura 𝑥 restituisce come
risultato un vettore colonna x detto marcatura:
𝑥 𝑝1
𝑥 𝑝2
x=
⋮
𝑥 𝑝𝑃
MARCATURA
in cui l’elemento 𝑥 𝑝𝑖 𝜖 ℕ indica l’attuale stato del posto 𝑝𝑖 𝜖 𝑃.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI MARCATURA
RAPPRESENTAZIONE GRAFICA
La funzione di marcatura 𝑥 ∶ 𝑃 → ℕ associa ad ogni posto un numero naturale non
negativo. Tale numero è rappresentato graficamente da pallini, anche detti gettoni o
token.
𝑥 𝑝𝑖 = 3
𝜔 𝑝𝑖 ; 𝑡𝑗
pi
tj
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETE DI PETRI
DEFINIZIONE
Un grafo di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔 a cui è associata una funzione di marcatura 𝑥 ∶ 𝑃 → ℕ è
detto RETE DI PETRI (o PETRI NET). Pertanto una rete di petri 𝑁 è una quintupla:
𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x
RETE DI PETRI
Dove:
𝑃 = 𝑝1 , 𝑝2 , … , 𝑝 𝑃
INSIEME DEI POSTI
𝑇 = 𝑡1 , 𝑡2 , … , 𝑡 𝑇
INSIEME DELLE TRANSIZIONI
𝐴⊆ 𝑃×𝑇 ⋃ 𝑇×𝑃
INSIEME DEGLI ARCHI ORIENTATI
𝜔 ∶ 𝐴 → ℕ \ {0}
FUNZIONE DI PESO DEGLI ARCHI
x 𝜖ℕ𝑃
MARCATURA
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STATO DELLA RETE DI PETRI
OSSERVAZIONE
La marcatura x di una rete di Petri rappresenta lo stato attuale della rete di Petri ed è
rappresentato dal numero di gettoni 𝑥 𝑝𝑖 𝜖 ℕ dei posti 𝑝𝑖 𝜖 𝑃 .
𝑥 𝑝1
𝑥 𝑝2
x=
⋮
𝑥 𝑝𝑃
MARCATURA
OSSERVAZIONE
Nonostante il numero di gettoni per ogni posto sia un numero intero finito, lo spazio di
stato di una rete di Petri ha cardinalità potenzialmente infinita, infatti:
x𝜖𝑋 ⊆ ℕ𝑃
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI vs DISCRETE EVENT SYSTEM
OSSERVAZIONE
• Una rete di Petri composta da un numero finito di posti e transizioni può
trovarsi in un numero potenzialmente infinito di stati.
• Un sistema ad eventi discreti ha necessariamente un numero finito di stati.
OSSERVAZIONE
• In una rete di Petri il concetto di stato è distribuito nei vari posti.
• In un sistema ad eventi discreti il concetto di stato è centralizzato in un’unica
entità.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE DINAMICA
DI UNA RETE DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x l’evoluzione da uno stato x ad uno stato
successivo x′ richiede l’occorrenza di un EVENTO che determini una evoluzione.
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x una transizione 𝑡𝑗 𝜖 𝑇 dicesi ABILITATA se il
numero di token contenuto in ogni posto in ingresso è maggiore o uguale del peso
dell’arco che collega il posto alla transizione. Ovvero se:
𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑗
∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑗
TRANSIZIONE ABILITATA
•
Quando una transizione è abilitata, l’evento ad essa legato può occorrere.
•
Quando una transazione 𝑡𝑗 𝜖 𝑇 presenta un insieme dei posti di ingresso vuoto 𝐼 𝑡𝑗 =
∅ la transizione è sempre attiva e può avvenire incondizionatamente.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE
ESEMPIO
Data la rete di Petri in figura:
3
t1
p2
t2
p3
2
p1
•
•
La transizione 𝑡1 è sempre abilitata in quanto 𝐼 𝑡1 = ∅
La transizione 𝑡2 non è abilitata in quanto 𝑥 𝑝1 = 0 < 𝜔 𝑝1 , 𝑡2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE
Quando una transizione è abilitata, l’evento ad essa legato può occorrere e scatenare una
EVOLUZIONE nella rete di Petri, ovvero un CAMBIO DI STATO.
Dato che lo stato, in una rete di Petri, coincide con un vettore di MARCATURA, un
cambio di stato di una rete di Petri coincide con la variazione del numero di token
nei posti.
REGOLA DI EVOLUZIONE
Data una rete di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x in cui una transizione 𝑡𝑗 𝜖 𝑇 è abilitata,
l’evoluzione consiste nel:
1. Eliminare dai posti in ingresso alla transizione un numero di token pari al peso
dell’arco che collega ogni posto in ingresso alla transizione.
2. Aggiungere ai posti in uscita alla transizione un numero di token pari al peso
dell’arco che collega la transizione ad ogni posto in uscita.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE
SCATTO DI UNA TRANSIZIONE
Data la rete di Petri in figura:
3
t1
p2
t2
p3
2
p1
•
La transizione 𝑡2 è abilitata in quanto entrambi i posti in ingresso hanno un token.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
EVOLUZIONE
SCATTO DI UNA TRANSIZIONE
Data la rete di Petri in figura:
3
3
t1
p2
t2
2
p1
•
•
p3
scatto
t1
p2
t2
p3
2
p1
La transizione 𝑡2 è abilitata in quanto entrambi i posti in ingresso hanno un token.
Lo scatto della transizione 𝑡2 comporta la perdita di un token ad entrambi i posti in
ingresso (𝑝1 e 𝑝2 ) e l’acquisizione di 2 token al posto 𝑝2 e di 3 token al posto 𝑝3 .
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI TRANSIZIONE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x si definisce funzione di transizione dello stato
della rete di Petri:
𝑓 ∶ ℕ𝑃 ×𝑇 → ℕ𝑃
quella funzione che associa ad ogni coppia stato (marcatura x ∈ ℕ 𝑃 ) – transizione
(𝑡𝑗 ∈ 𝑇 𝑃 ) un nuovo stato (marcatura x′ ∈ ℕ 𝑃 ).
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x uno scatto della transizione 𝑡𝑗 è tale che:
x ′ = 𝑓 x, 𝑡𝑗
↔ 𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑗
∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑗
dove la marcatura di arrivo è un vettore colonna composto da 𝑃 elementi:
x ′ = 𝑥′ 𝑝1
𝑥′ 𝑝2
⋯ 𝑥′ 𝑝 𝑃
𝑇
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI TRANSIZIONE
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x ed uno scatto della transizione 𝑡𝑗 :
x ′ = 𝑓 x, 𝑡𝑗
gli elementi della marcatura di arrivo saranno pari a:
𝑥 𝑝1 − 𝜔 𝑝1 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝1
x′ =
𝑥 𝑝2 − 𝜔 𝑝2 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝2
⋮
𝑥 𝑝 𝑃 − 𝜔 𝑝 𝑃 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝 𝑃
Token aggiunti ai posti in uscita
Token sottratti ai posti in ingresso
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI TRANSIZIONE
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x ed uno scatto della transizione 𝑡𝑗 :
x ′ = 𝑓 x, 𝑡𝑗
gli elementi della marcatura di arrivo saranno pari a:
𝑥 𝑝1 − 𝜔 𝑝1 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝1
x′ =
𝑥 𝑝2 − 𝜔 𝑝2 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝2
⋮
𝑥 𝑝 𝑃 − 𝜔 𝑝 𝑃 ; 𝑡𝑗 + 𝜔 𝑡𝑗 ; 𝑝 𝑃
Si ha generazione di token se:
𝑃
𝑃
𝜔 𝑝𝑖 ; 𝑡𝑗 <
𝑖=1
Si ha distruzione di token se:
𝑃
𝜔 𝑡𝑗 ; 𝑝𝑖
𝑖=1
𝑃
𝜔 𝑝𝑖 ; 𝑡𝑗 >
𝑖=1
𝜔 𝑡𝑗 ; 𝑝𝑖
𝑖=1
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x si definisce MATRICE DI INGRESSO (I) la
matrice di dimensioni 𝑃 × 𝑇 riportante i pesi degli archi che collegano i posti alle
transizioni:
𝑰=
𝜔 𝑝1 ; 𝑡1
𝜔 𝑝2 ; 𝑡1
⋮
𝜔 𝑝 𝑃 ; 𝑡1
𝜔 𝑝1 ; 𝑡2
𝜔 𝑝2 ; 𝑡2
⋮
𝜔 𝑝 𝑃 ; 𝑡2
⋯
𝜔 𝑝1 ; 𝑡 𝑇
⋯ 𝜔 𝑝2 ; 𝑡 𝑇
⋱
⋮
⋯ 𝜔 𝑝𝑃 ;𝑡 𝑇
Si definisce MATRICE DI USCITA (O) la matrice di dimensioni 𝑇 × 𝑃 riportante i pesi
degli archi che collegano le transizioni ai posti:
𝑶=
𝜔 𝑡1 ; 𝑝1
𝜔 𝑡1 ; 𝑝2
⋮
𝜔 𝑡1 ; 𝑝 𝑃
𝜔 𝑡2 ; 𝑝1
𝜔 𝑡2 ; 𝑝2
⋮
𝜔 𝑡2 ; 𝑝 𝑃
⋯
𝜔 𝑡 𝑇 ; 𝑝1
⋯ 𝜔 𝑡 𝑇 ; 𝑝2
⋱
⋮
⋯ 𝜔 𝑡 𝑇 ;𝑝𝑃
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x la condizione di abilitazione di una transizione
𝑡𝑗 𝜖 𝑇 è definita come:
𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑗
∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑗
TRANSIZIONE ABILITATA
Utilizzando la matrice di ingresso la condizione di abilitazione di una transizione 𝑡𝑗 𝜖 𝑇 può
essere riscritta in forma concisa:
x ≥ 𝐼𝑗
TRANSIZIONE ABILITATA
Dove 𝐼𝑗 è la j-esima colonna della matrice di ingresso 𝑰 :
𝑥 𝑝1
𝑥 𝑝2
x=
⋮
𝑥 𝑝𝑃
𝜔 𝑝1 , 𝑡𝑗
≥ 𝜔 𝑝2 , 𝑡𝑗
⋮
𝜔 𝑝 𝑃 , 𝑡𝑗
= 𝐼𝑗
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , ipotizzando che la condizione di abilitazione di
una transizione 𝑡𝑗 𝜖 𝑇 sia verificata:
x ≥ 𝐼𝑗
TRANSIZIONE ABILITATA
Lo scatto della transizione 𝑡𝑗 dalla marcatura x porta la rete di Petri nella marcatura x′:
x ′ = x + 𝑂𝑗 − 𝐼𝑗
EQUAZIONE DI EVOLUZIONE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x si definisce MATRICE DI INCIDENZA (C)
𝑪=𝐎−𝐈
x ′ = x + 𝐶𝑗
EQUAZIONE DI EVOLUZIONE
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
ESEMPIO
Riprendiamo l’esempio di rete di Petri introdotto in precedenza e calcoliamo la matrice di
ingresso e la matrice di uscita.
0 0
𝑰= 0 1
0 0
3
t1
p2
t2
p3
0 2
𝑶= 1 0
0 3
2
p1
OSSERVAZIONE
La matrice di ingresso e la matrice di uscita definiscono completamente la
topologia della rete di Petri.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
Calcoliamo la marcatura x, verifichiamo la condizione di abilitazione della transizione 𝑡2 …
0 1
𝑰= 0 1
0 0
3
t1
0
𝑶= 1
0
p2
t2
p3
2
p1
1
x= 1
0
1
≥ 𝐼2 = 1
0
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
2
0
3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
Calcoliamo la marcatura x, verifichiamo la condizione di abilitazione della transizione 𝑡2 …
…e calcoliamo la marcatura dopo lo scatto.
3
t1
p2
t2
2
p3
0 1
𝑰= 0 1
0 0
0
𝑶= 1
0
0
𝑪=𝑶−𝑰= 1
0
1
−1
3
p1
1
x= 1
0
1
≥ 𝐼2 = 1
0
1
1
2
→ x ′ = x + 𝐶2 = 1 + −1 = 0
0
3
3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
2
0
3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MATRICE DI INGRESSO E DI USCITA
OSSERVAZIONE
Notiamo che la matrice di incidenza non permette di ricostruire univocamente la
topologia di una rete di Petri. Vanno perdute le informazioni sugli auto-anelli.
3
t1
3
p2
t2
2
p1
0 1
𝑰= 0 1
0 0
p3
t1
p2
t2
p3
Reti di Petri distinte hanno
stessa matrice di incidenza
p1
0 2
𝑶= 1 0
0 3
0 1
𝑪 = 1 −1
0 3
0 0
𝑰= 0 1
0 0
0 1
𝑶= 1 0
0 3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
0 1
𝑪 = 1 −1
0 3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , si definisce sequenza di scatti 𝑆 una sequenza
di 𝑛 transizioni 𝑡𝑗1 𝑡𝑗2 ⋯ 𝑡𝑗𝑛 (𝑛 ∈ ℕ\ 0 , 𝑗𝑖 ∈ 1,2, … , 𝑇 ∀𝑖 ∈ 1,2, … , 𝑛 ) tali che:
x1 = x ≥ 𝐼𝑗1
x2 = x1 + 𝐶𝑗1
x2 ≥ 𝐼𝑗2
x3 = x2 + 𝐶𝑗2
x𝑛 ≥ 𝐼𝑗𝑛
x𝑛+1 = x𝑛 + 𝐶𝑗𝑛
…
…
Ovvero tali che la prima transizione è abilitata nella marcatura di partenza della rete di
Petri (x) e lo scatto di ognuna delle transizioni porta in una marcatura (x𝑖 ) in cui la
successiva transizione (𝑡𝑗𝑖 ) è abilitata.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , ipotizziamo che la condizione di abilitazione di
una transizione 𝑡𝑗 𝜖 𝑇 sia verificata:
x ≥ 𝐼𝑗
TRANSIZIONE ABILITATA
L’equazione di evoluzione porta la rete di Petri nella marcatura x′:
x ′ = x − 𝐼𝑗 + 𝑂𝑗
EQUAZIONE DI EVOLUZIONE
Notiamo che per isolare il vettore colonna j-esimo nelle matrici di ingresso e di uscita,
possiamo introdurre un vettore composto da 𝑇 elementi che tenga conto dell’occorrenza
della transizione 𝑡𝑗 𝜖 𝑇 :
𝑠= 0 ⋯ 0
1
0 ⋯ 0
𝑇
j-esima posizione
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
OSSERVAZIONE
Moltiplicando le matrici di ingresso e di uscita per il vettore 𝑠, si ottiene:
𝑰∙𝑠 =
𝑶∙𝑠 =
𝜔 𝑝1 ; 𝑡1
𝜔 𝑝2 ; 𝑡1
⋮
𝜔 𝑝 𝑃 ; 𝑡1
𝜔 𝑡1 ; 𝑝1
𝜔 𝑡1 ; 𝑝2
⋮
𝜔 𝑡1 ; 𝑝 𝑃
𝜔 𝑝1 ; 𝑡2
𝜔 𝑝2 ; 𝑡2
⋮
𝜔 𝑝 𝑃 ; 𝑡2
𝜔 𝑡2 ; 𝑝1
𝜔 𝑡2 ; 𝑝2
⋮
𝜔 𝑡2 ; 𝑝 𝑃
⋯
𝜔 𝑝1 ; 𝑡 𝑇
⋯ 𝜔 𝑝2 ; 𝑡 𝑇
⋱
⋮
⋯ 𝜔 𝑝𝑃 ;𝑡 𝑇
⋯ 𝜔 𝑡 𝑇 ; 𝑝1
⋯ 𝜔 𝑡 𝑇 ; 𝑝2
⋱
⋮
⋯ 𝜔 𝑡 𝑇 ;𝑝𝑃
0
⋮
𝜔 𝑝1 ; 𝑡𝑗
0
∙ 1 = 𝜔 𝑝2 ; 𝑡𝑗
⋮
0
𝜔 𝑝 𝑃 ; 𝑡𝑗
⋮
0
0
⋮
𝜔 𝑡𝑗 ; 𝑝1
0
∙ 1 = 𝜔 𝑡𝑗 ; 𝑝2
⋮
0
𝜔 𝑡𝑗 ; 𝑝 𝑃
⋮
0
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
= 𝐼𝑗
= 𝑂𝑗
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
La condizione di abilitazione di una transizione 𝑡𝑗 𝜖 𝑇 diventa:
x ≥ 𝑰𝑠
TRANSIZIONE ABILITATA
L’equazione di evoluzione porta la rete di Petri nella marcatura x′:
x ′ = x − 𝐼𝑗 + 𝑂𝑗 = x − 𝑰𝑠 + 𝑶𝑠 = x + 𝑶 − 𝑰 𝑠
x ′ = x + 𝑪𝑠
EQUAZIONE DI EVOLUZIONE
OSSERVAZIONE
Se a partire dalla marcatura x′ prendiamo un’altra transizione 𝑡𝑗′ 𝜖 𝑇, cui è associato un
vettore delle occorrenze 𝑠′, che è abilitata (x′ ≥ 𝑰𝑠′), l’equazione di evoluzione diviene:
x ′′ = x ′ + 𝑪𝑠 ′ = x + 𝑪𝑠 + 𝑪𝑠 ′ = x + 𝑪 𝑠 + 𝑠 ′ = x + 𝑪𝑠 ′′
𝑠 ′′ = 𝑠 + 𝑠 ′
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x e una sequenza di scatti 𝑆 si definisce vettore
delle occorrenze 𝑠 il vettore colonna di dimensione 𝑇 avente come k-esima
componente 𝑠𝑘 il numero di occorrenze della transizione 𝑡𝑘 nella sequenza di scatti 𝑆.
PROPOSIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x e una sequenza di scatti 𝑆 con vettore delle
occorrenze 𝑠, la marcatura x′ di arrivo dopo la sequenza di scatti 𝑆 è:
x ′ = x + 𝑪𝑠
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x non è detto che un qualsiasi vettore 𝑠 ∈ ℕ 𝑇
sia un vettore delle occorrenze ammissibile in quanto per essere tale si deve
conoscere la sequenza delle transizioni, non solo il loro numero. Inoltre un vettore delle
occorrenze può essere associato a più sequenze, non tutte ammissibili.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
ESEMPIO
Data una rete di Petri come in figura, si determinino le matrici di ingresso e di
uscita, nonché la marcatura.
4
t1
p1
p2
3
2
t2
SVOLGIMENTO
𝑰=
0 2
4 0
𝑶=
1 0
0 3
x=
3
1
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
Data una rete di Petri con matrici di ingresso e di uscita e marcatura iniziale:
𝑰=
0
4
2
0
𝑶=
1 0
0 3
x=
3
1
Stabilire se la sequenza di transizioni 𝑺 = 𝒕𝟐 𝒕𝟏 è una sequenza di scatti e calcolare
la marcatura finale.
SVOLGIMENTO
Per verificare che la sequenza di transizione sia una sequenza di scatti dobbiamo
verificare che le transizioni, nella corretta sequenza, siano abilitate:
2
3
≥ 𝐼2 =
0
1
−2
3
1
0
x2 = x1 + 𝐶2 =
+
=
≥ 𝐼1 =
3
1
4
4
x1 = x =
𝑪= 𝑶−𝑰=
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
1 −2
−4 3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
Per calcolare la marcatura finale x3 usiamo il vettore delle occorrenze:
𝑠=
1
1
Per cui abbiamo:
x3 = x + 𝐶𝑠 =
1
3
+
−4
1
−2
2
1
3
−1
∙
=
+
=
3
0
1
1
−1
x = x1
4
3
t2
p2
t1
p1 2
x3
Scatta 𝑡1
4
Scatta 𝑡2
t1
p1 2
x2
4
t1
3
p2
p1 2
t2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
3
t2
p2
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
VETTORE DELLE OCCORRENZE
OSSERVAZIONE
Data una rete di Petri con matrici di ingresso e di uscita e marcatura iniziale:
𝑰=
0
4
2
0
𝑶=
1 0
0 3
x=
3
1
La sequenza di transizioni 𝑺 = 𝒕𝟏 𝒕𝟐 nonostante abbia stesso vettore delle
occorrenze, NON è una sequenza di scatti!!!
Infatti la prima transizione della sequenza, 𝒕𝟏 , non è abilitata nella marcatura 𝐱 = 𝐱 𝟏 :
x1 = x =
3
0
≥ 𝐼1 =
1
4
Bisogna stare molto attenti a lavorare con i vettori delle occorrenze, in quanto questi non
tengono conto dell’ordine con cui vengono eseguite le transizioni e pertanto
perdono traccia della loro ammissibilità.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURE FONDAMENTALI DI
UNA RETE DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA IN CONFLITTO
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , due transizioni 𝑡𝑗 , 𝑡𝑘 ∈ 𝑇 danno origine ad una
struttura in conflitto se sono abilitate ma hanno in comune almeno un posto in
ingresso che contiene un numero di gettoni non sufficienti a permettere lo scatto
di entrambe le transizioni. Ovvero se:
𝑡𝑗 è abilitata…
1. 𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑗 ∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑗
2. 𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑘 ∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑘
…𝑡𝑘 è abilitata…
3. ∃ 𝑝 ∈ 𝐼 𝑡𝑗 ∩ 𝐼 𝑡𝑘 | 𝑥 𝑝 < 𝜔 𝑝, 𝑡𝑖 + 𝜔 𝑝, 𝑡𝑗 …ma non possono scattare assieme!
ESEMPIO GRAFICO
𝑡𝑗 è abilitata…
tj
p
…ma non possono
scattare assieme!
...𝑡𝑘 è abilitata…
Si sceglie con un
criterio non deterministico
chi scatta
tk
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA IN CONCORRENZA
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , due transizioni 𝑡𝑗 , 𝑡𝑘 ∈ 𝑇 danno origine ad una
struttura in concorrenza se sono abilitate, non hanno in comune alcun posto in
ingresso e sono seguite da una transizione di sincronizzazione. Ovvero se:
𝑡𝑗 è abilitata…
1. 𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑗 ∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑗
2. 𝑥 𝑝𝑖 ≥ 𝜔 𝑝𝑖 , 𝑡𝑘 ∀ 𝑝𝑖 𝜖 𝐼 𝑡𝑘 …𝑡𝑘 è abilitata…
3. 𝐼 𝑡𝑗 ∩ 𝐼 𝑡𝑘 = ∅ … non hanno posti in ingresso in comune…
4. ∃ 𝑡 ∈ 𝑇 | 𝑂 𝑡𝑗 ∪ 𝑂 𝑡𝑘 ⊆ 𝐼 𝑡 ∧ ∀𝑝𝑤 ∈ 𝑂 𝑡𝑗 → 𝜔 𝑡𝑗 , 𝑝𝑤 = 𝜔 𝑝𝑤 , 𝑡 ∧ ∀𝑝𝑧 ∈ 𝑂 𝑡𝑘 →
𝜔 𝑡𝑘 , 𝑝𝑧 = 𝜔 𝑝𝑧 , 𝑡
…e sono seguite da una transizione
di sincronizzazione 𝑡 che è abilitata
solo quando entrambe le transizioni
𝑡𝑗 e 𝑡𝑘 sono scattate.
ESEMPIO GRAFICO

px
tj
pw
t
px
tk
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
pz
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA IN CONFUSIONE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , due transizioni 𝑡𝑗 , 𝑡𝑘 ∈ 𝑇 danno origine ad una
struttura in confusione se sono in concorrenza e in conflitto con una terza
transizione 𝑡ℎ ∈ 𝑇 .
ESEMPIO GRAFICO
tj
conflitto
px
concorrenza
th
py
tk
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MACCHINA A STATI
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , essa si definisce macchina a stati se ogni
transizione ha un solo posto in ingresso e un solo posto in uscita. Ovvero se:
∀𝑡 ∈ 𝑇 𝐼 𝑡
= 𝑂 𝑡
=1
OSSERVAZIONE
Una macchina a stati non ammette transizioni di sincronizzazione.
IMPOSSIBILE !!!
px
tj
pw
t
px
tk
pz
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MACCHINA A STATI
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , essa si definisce grafo marcato se ogni posto
ha un solo arco in ingresso e un solo arco in uscita. Ovvero se:
∀𝑝 ∈ 𝑃 ∃! 𝑡𝑗 ∈ 𝑇 | 𝜔 𝑡𝑗 , 𝑝 > 0 ∧ ∃! 𝑡𝑘 ∈ 𝑇 | 𝜔 𝑝, 𝑡𝑘 > 0
OSSERVAZIONE
Un grafo marcato non ha conflitti.
tj
p
IMPOSSIBILE !!!
tk
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETE A SCELTA LIBERA
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , essa si definisce rete a scelta libera se non
ammette strutture in confusione.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
BIBLIOGRAFIA
Sezione 8.3, 8.3.1 e 8.3.2
TITOLO
Sistemi di automazione industriale
Architetture e controllo
AUTORI
Claudio Bonivento
Luca Gentili
Andrea Paoli
EDITORE
McGraw-Hill
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it