Prof. Kristen Nygaard, Università di Oslo

(1)

i Alla mia famiglia ed

ai miei amici

"Programmare è capire"

Prof. Kristen Nygaard, Università di Oslo

Padre di Simula e della programmazione ad oggetti

(2)

(3)

iii

Indice

INTRODUZIONE...V

CAPITOLO I-MODELLISTICA E SIMULAZIONE DELLE RETI DI PETRI...- 10 -

1.1 INTRODUZIONE... -10-

1.2 DEFINIZIONE BASE DI RETE DI PETRI... -12-

1.2.1

Marcatura e sistema rete...- 17 -

1.2.2 Abilitazione e scatto di una transizione ...- 20 -

1.2.3 Proprietà dinamiche elementari ed equazione di stato...- 26 -

1.3 TIPOLOGIE DI RETI DI PETRI... -29-

1.3.1 Estensioni delle reti P/T...- 29 -

1.3.2 Classi di reti di Petri posto/transizione...- 29 -

1.3.3 Classi di reti temporizzate...- 37 -

1.4 UTILIZZO DELLE RETI DI PETRI... -50-

1.5 AMBIENTI DI SIMULAZIONE ATTUALI... -55-

CAPITOLO II- PROPRIETÀ ANALITICHE DELLE RETI DI PETRI ...- 59 -

2.2 RAGGIUNGIBILITÀ... -60-

2.3 PROPRIETÀ COMPORTAMENTALI... -64-

2.4 VETTORI INVARIANTI ED ANALISI STRUTTURALE... -70-

2.5 PROPRIETÀ STRUTTURALI... -73-

CAPITOLO III- PETRI NET TOOLBOX : UN SIMULATORE A BLOCCHI ...- 77 -

3.2 POTENZIALITÀ DI MODELLAZIONE... -78-

3.3 MODALITÀ DI SVILUPPO... -80-

3.4 INSTALLAZIONE DEL SOFTWARE E FINESTRA PRINCIPALE... -81-

3.5 CREAZIONE E MODIFICA DI UNA RETE... -84-

3.5.1 Tappe...- 84 -

3.5.2 Transizioni...- 86 -

3.5.3 Archi...- 89 -

3.6 MEMORIZZAZIONE DELLA RETE SU DISCO... -91-

3.7 FUNZIONI DEL SIMULATORE... -94-

3.7.2 Step(pulsante 7) ...- 95 -

3.7.3 Pause(pulsante 9)...- 95 -

3.7.4 Stop(pulsante 10) ...- 95 -

3.7.5 Opzioni del simulatore...- 96 -

3.7.6 Messaggi stallo ...- 97 -

3.8FUNZIONI PER L'ANALISI... -98-

3.8.1 Tipo di dati raccolti ...- 98 -

3.8.2 Selezione target analisi ...- 98 -

3.8.3 Visualizzazione dati ...- 98 -

3.8.4 Rimando alle funzioni Matlab per la statistica...- 100 -

3.9 FUNZIONAMENTO DELLA SIMULAZIONE... -100-

3.9.1 Fase I...- 100 -

3.9.2 Fase II...- 104 -

3.10 ANALISI COMPORTAMENTALE E STRUTTURALE... -104-

3.11 CONTROLLO TRAMITE GMEC E ALBERO DI RAGGIUNGIBILITÀ\COPRIBILITÀ... -108-

3.12 MATRICE DI INCIDENZA... -112-

3.13 CONCLUSIONI... -113-

(4)

CAPITOLO IV- CONTROLLO SUPERVISORE DI RETI DI PETRI ...- 114 -

4.2 GMEC E LORO POTERE DESCRITTIVO... -116-

4.3 POSTI MONITOR E SISTEMA A CICLO CHIUSO... -122-

4.4 SPECIFICHE NON RAPPRESENTABILI CON GMEC ... -125-

4.4 TRANSIZIONI NON CONTROLLABILI E NON OSSERVABILI... -128-

4.5 RISOLUZIONI DI SPECIFICHE NON CONVESSE CON ARCHI INIBITORI... -132-

4.6 DEFINIZIONE DELLE STRUTTURE DI BASE DI UNA RETE... -137-

V CONCLUSIONI E PROSPETTIVE DI SVILUPPO...- 145 -

BIBLIOGRAFIA ...- 147 -

APPENDICE A: INDICE DELLE FUNZIONI ...- 148 -

APPENDICE B :ALGORITMI NOTEVOLI ...- 157 -

(5)

v

Introduzione

Le reti di Petri sono uno strumento grafico e matematico per la rappresentazione e la modellizzazione di interazioni logiche complesse tra componenti fisici o attività in un sistema.

Come strumento grafico, le reti di Petri possono essere usate come aiuto di comunicazione visuale simile ai grafi di flusso, diagrammi a blocchi e reti. Infatti tale formalismo grafico è composto solo da semplici posti e transizioni collegate da archi che permettono ai

“ gettoni ” di fluire tra posti e transizioni.

Come strumento matematico, è poi possibile definire equazioni di stato, equazioni algebriche e altri modelli matematici che governano il comportamento di sistemi.

Quindi le reti di Petri possono essere usate indifferentemente da teorici e pratici, fornendo un potente mezzo di comunicazione tra le due categorie: i pratici possono imparare dai teorici come rendere più metodici i loro modelli, e i teorici possono imparare dai tecnici come rendere i propri modelli più realistici.

Storicamente parlando, il concetto delle reti di Petri hanno origine dal

saggio di Carl Adam Petri, inviato nel 1962 alla facoltà di Matematica e

Fisica al Technical University di Darmstadt, Germania dell’ovest. Il

saggio fu stilato mentre Adam Petri lavorava come scienziato

all’università di Bonn. L’opera di Petri fu notata da A.W. Holt, che più

(6)

tardi fu alla guida della Information System Theory Project of Applied Data Research Inc. , negli Stati Uniti.

Dal 1970 al 1975, il Communication Structures Group del MIT è stato il più attivo nel condurre ricerche relative alle reti di Petri. Nel luglio del 1975 ci fu una conferenza sulle reti di Petri al MIT, ma niente venne pubblicato.

Nel tardo 1970, furono molto attivi nell’organizzare convegni e pubblicare relazioni delle conferenze sulle reti di Petri. Nell’ottobre 1979, circa 135 ricercatori per la maggior parte da paesi europei si riunirono ad Amburgo, Germania dell’ovest, per un corso avanzato di due settimane sulla teoria generale delle reti di processi e sistemi. Le diciassette lezioni date in questo corso furono pubblicate nei suoi referti, in stampa al momento.

Il secondo corso fu tenuto a Bad Hoffen, Germania dell’ovest, nel settembre 1986. I referti di questo corso contengono 34 articoli, inclusi due recenti articoli di C.A. Petri; uno riguardo ai suoi assiomi della teoria della concorrenza e l’altro con i suoi suggerimenti per future ricerche.

Il primo convegno europeo sulle applicazioni e sulla teoria delle reti di Petri fu tenuto nel 1980 a Strasburgo, in Francia.

Da allora, questa serie di convegni è stata tenuta ogni anno in differenti locazioni in Europa: 1981, Bad Honnef, Germania dell’ovest;

1982, Varenna, Italia; 1983; Tolosa, Francia; 1984, Aarhus, Danimarca; 1985, Espoo, Finlandia; 1986, Oxford, Gran Bretagna;

1987, Saragozza, Spagna; 1988, Venezia, Italia; e 1989, Bad Honnef,

Germania dell’ovest. La distribuzione delle relazioni di queste

(7)

vii conferenze è limitata ai partecipanti. Comunque, articoli selezionati da questi studi e altri articoli sono stati pubblicati da Springer-Velag come Advances in Petri Nets .

Il volume del 1987 contiene la bibliografia più comprensiva delle reti di Petri annoverando 2074 elementi pubblicati dal 1962 al 1987.

La sezione “pubblicazioni recenti” della newsletter delle reti di Petri raccoglie brevi estratti delle pubblicazioni recenti tre volte all’anno, ed è una buona fonte di informazioni sulla recente letteratura delle reti di Petri. Nel luglio 1985 venne iniziata un’altra serie di convegni internazionali. Questa serie pone enfasi sulle reti temporizzate e stocastiche e le loro applicazioni per realizzare stime. Il primo convegno internazionale sulle reti temporizzate si tenne a Torino, in Italia, nel luglio 1985; il secondo si tenne a Madison, Wisconsin, nell’agosto 1987; il terzo a Kyoto, Giappone, nel dicembre 1989 e il terzo in Australia nel 1991. Le relazioni dei primi due convegni sono disponibili presso la IEEE Computer Society Press.

Se da una parte la semplicità di comprensione e di uso delle reti di Petri ha determinato negli anni un interesse sempre maggiore verso le stesse, dall’altra la difficoltà e la complessità nell’assemblare il modello di un processo reale di dimensioni significative, quali ad esempio una catena di montaggio con relativi robot che assemblano parti prelevate da un 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

(8)

composto da qualche decina tra posti e transizioni con una conseguente perdita di leggibilità e distinzione funzionale all’interno dello schema di assemblaggio globale.

Si pone dunque l’esigenza di semplificare l’assemblaggio pre- simulazione della rete, ricorrendo a rappresentazioni di tipo

“macroposto”, “macrotransizione” o combinazione dei due per semplificare e rendere i sottomoduli più simili a sistemi con ingressi ed uscite .

Infatti, definendo degli ingressi e delle uscite, o quantomeno dei posti e delle transizioni di interfaccia , si riesce a definire meglio delle connessioni intermodulari, lasciando sotto forma di “ black-box ” la struttura interna.

Scopo della presente tesi infatti è quello di sviluppare un simulatore in grado di trattare reti di Petri temporizzate e allo stesso tempo definire degli ingressi e delle uscite con significato analogo a quello della Teoria dei Sistemi classica.

Non a caso l’ambiente di sviluppo da cui è stata presa l’ispirazione è il ben noto Simulink

^®

sotto Matlab

^{® 1}

, sotto il quale è possibile definire sottosistemi e collegarli tra loro come in un gioco di scatole cinesi.

Il simulatore sviluppato include inoltre metodi di controllo standard come le GMEC, Generalized Mutual Exclusion Costraints e viene dimostrato come anche in questo caso il controllo sia divisibile a livello di sottorete.

1 The MathWorks, Inc. Software License Agreement

(9)

ix Laddove le GMEC falliscano, si ricorre a metodi di controllo misti che includono l’uso degli archi inibitori.

Il risultato è stato, come è lecito aspettarsi, una notevole semplificazione in fase di progetto, di simulazione e di controllo, oltre ad un alleggerimento del carico computazionale che rappresenta un altro problema delle reti di Petri, specialmente nell’analisi delle proprietà comportamentali, strutturali e di raggiungibilità della rete.

Dunque dopo una introduzione sulle reti di Petri e parte delle loro numerose proprietà, si illustrerà le differenze del simulatore proposto con quanto di già esistente per poi passare in rassegna esempi di simulazione e controllo in cui verranno studiate sia alcune proprietà statistiche che alcune importanti proprietà intrinseche quali la vivezza , la raggiungibilità etc.