UNIVERSITA’ DEGLI STUDI DI PISA

FACOLTA’ DI INGEGNERIA ANNO ACCADEMICO 2001/2002

Petri Net Un toolbox per la progettazione, la simulazione

e l’analisi di Reti di Petri temporizzate

Pisa, 7 Marzo 2002 Gabriele Ribichini

Paolo Messina

PetriNet Capitolo 2

Pagina 2

1. Introduzione

1.1 Definizione e qualifica del progetto

PetriNet é un toolbox per Matlab 5 o superiore sviluppato nell'ambito del corso di Modellistica e Simulazione tenuto dal Prof. A. Balestrino presso la Facoltà di Ingegneria dell'Università di Pisa. Tale toolbox si compone di una serie di funzioni per la manipolazione e la simulazione di una rete di Petri e di una interfaccia grafica per l'accesso semplificato a queste funzionalità.

1.2 Situazione attuale progetti simili

Molteplici sono i progetti simili ed una lista esauriente di questi può essere consultata all’indirizzo: http://www.daimi.au.dk/PetriNets/ ma pochi simulatori gratuiti equiparano le potenzialità di PetriNet ed inoltre, nella maggioranza dei casi, il codice sorgente non è disponibile. Per dare un esempio si riporta una parte dei progetti ottenuti da una ricerca sul web di simulatori di Reti di Petri gratuiti. Progetto Reti supporate Caratteristiche Ambienti

ARP http://www.ppgia.pucpr.br/~maziero/petri/ Sorgenti: SI (in portoghese)

Reti di tappe/transizioni Reti temporizzate

Simulazione veloce Spazio di stato Tappe invarianti Transizioni invarianti Analisi strutturale Semplice analisi di prestazioni

MS DOS

CoopnTools http://lglwww.epfl.ch/Conform Sorgenti: NO

Reti di alto livello Editor Grafico Simulazione veloce Analisi strutturale

Java

CPN-AMI http://www.lip6.fr/cpn-ami Sorgenti: NO

Reti di alto livello

Editor grafico Simulazione veloce Spazio di stato Tappe invarianti Transizioni invarianti Analisi strutturale Servizi per modellazione strutturale

Sun Linux Macintosh

CPN-Tool http://www.daimi.au.dk/CPNtools/ Sorgenti: NO

Reti di alto livello Reti temporizzate

Editor grafico Animazione dei gettoni Simulazione veloce

Windows

HiQPN-Tool http://ls4-www.informatik.uni-dortmund.de/QPN/ Sorgenti: NO

Reti di alto livello Reti stocastiche

Editor grafico Animazione gettoni Spazio di stato Tappe invarianti Transizioni invarianti Analisi avanzata delle prestazioni

Sun

PetriNet Capitolo 2

Pagina 3

Progetto Reti supporate Caratteristiche Ambienti

HPSim http://home.t-online.de/home/henryk.a/petrinet/e/hpsim_e.htm Sorgenti: NO

Reti tappe/transizioni Reti stocastiche Reti temporizzate

Editor grafico Animazione gettoni Simulazione veloce Analisi semplice delle prestazioni

Windows

INA http://www.informatik.hu-berlin.de/~starke/ina.html Sorgenti: NO

Reti di alto livello Reti temporizzate

Spazio di stato Tappe invarianti Transizioni invarianti Riduzione della rete Analisi strutturale Analisi avanzata delle prestazioni

Sun Linux Windows

JARP http://jarp.sourceforge.net/ Sorgenti: SI

Reti tappe/transizioni Editor grafico Animazione gettoni Spazio di stato

Java

Maria http://www.tcs.hut.fi/Software/maria/ Sorgenti: SI

Reti di alto livello

Animazione gettoni Simulazione veloce Spazio di stato Controllo modello LTL

Sun HP Silicon Graphics Linux Windows Macintosh Ogni sistema che supporta C++

Marigold http://www.cs.york.ac.uk/~jwillans/marigold Sorgenti: ?

Reti tappe/transizioni Costruzioni diagrammi di flusso

Editor grafico Java

The Model-Checking Kit http://wwwbrauer.in.tum.de/gruppen/theorie/KIT/ Sorgenti: SI

Reti di alto livello Spazio di stato Controllo modello CTL/LTL Controllo stallo Controllo di raggiungibilità

Sun Linux

1.3 Obiettivi del progetto

Sviluppato interamente in linguaggio Matlab, PetriNet risulta essere un software multi-piattaforma e facilmente modificabile in ambito accademico dove tale linguaggio è attualmente molto diffuso. Questo progetto, infatti, non pretende di simulare le molteplici tipologie di reti ma vuole porre solide basi per futuri sviluppi fornendo al tempo stesso discrete funzionalità operative. Inoltre, la completa integrazione con Matlab fornisce un ottimo supporto per qualsiasi analisi statistica e grafica di tutti i parametri della rete, diversamente queste caratteristiche andrebbero sviluppate da zero con un impiego inutile di risorse.

1.4 Applicazioni

Con PetriNet 1.0 è possibile progettare graficamente e simulare reti a tappe e transizioni, reti temporizzate e reti stocastiche. Le sue funzionalità consentono di avere il controllo su eventuali stalli, monitorare lo stato della rete e effettuare statistiche esaustive.

PetriNet Capitolo 2

Pagina 4

1.4.1 Quali sistemi si possono modellare Le Reti di Petri si rivelano molto potenti nella modellazione di sistemi tempo discreti ma anche per formalizzare la descrizione di sistemi generici. I loro punti di forza sono dati dalle caratteristiche di astrazione e generalità che permettono la modellazione di molti problemi quali: a) Protocolli di comunicazione; b) Sistemi fault-tolerant; c) Architetture multiprocessore; d) Data flow, e) Sistemi di controllo; f) Catene di montaggio, g) Altre attività nelle industrie.

1.4.2 Esempi

0 P 1 0

Produttore Consumatore T1

T2

(Figura 1-1) Produttore – Consumatore

La tappa P contiene il numero di oggetti prodotti e non ancora prelevati. Il Consumatore prende tutti i prodotti immessi in P un po’ alla volta finchè la tappa P non viene svuotata, nel qual caso T1 abilita nuovamente il Produttore. La transizione T2 disabilita il Produttore e abilita il Consumatore dopo un periodo di produzione (in questo caso di durata aleatoria).

0 0

0 0 1

1

3 2

(Figura 1-2) Linee di produzione

Il grafo in figura modella due linee di produzione parallele, in cui le due tappe centrali rappresentano due operatori che possono lavorare su una sola linea alla volta.

PetriNet Capitolo 3

Pagina 5

2. Guida all'uso

2.1 Requisiti e Installazione

2.1.1 Requisiti software Il toolbox è stato progettato per funzionare con Matlab 5 e 6. È richiesto solamente il nucleo di Matlab senza alcun pacchetto aggiuntivo.

2.1.2 Requisiti hardware Il software risulta molto leggero sia nella fase di editing della rete che in quella di simulazione, per questo motivo i requisiti hardware sono da considerarsi equiparabili a quelli elencati nella distribuzione di Matlab di cui si è in possesso.

2.1.3 Installazione Per installare il pacchetto è sufficiente copiare la cartella PetriNet dal disco di installazione sul proprio hard-disk e aggiungere il percorso locale della cartella al path di Matlab utilizzando il "Path Browser". Non è richiesta nessuna ulteriore configurazione.

2.2 Funzioni dell'editor

Per aprire l'editor digitare il comando ped dalla console di Matlab. Verrà mostrata una finestra con una toolbar sulla sinistra da cui è possibile accedere alle funzionalità dell'editor e del simulatore. Nella parte alta della toolbar sono concentrati i pulsanti per funzioni di editazione e nella parte bassa i pulsanti per la simulazione. L'area a destra serve per editare e visualizzare la rete durante la simulazione.

(Figura 2-1) Finestra dell’editor/simulatore

PetriNet Capitolo 3

Pagina 6

2.2.1 Creazione e modifica di una rete È possibile assemblare una rete di Petri combinando tappe, transizioni e archi. Durante l'editazione si possono impostare i parametri di simulazione per ogni singolo elemento cliccando con il tasto destro del mouse sull'elemento stesso.

2.2.2 Tappe Una tappa rappresenta un punto di accumulo di gettoni. Riferirsi alla teoria sulle reti di Petri per maggiori informazioni.

Inserimento

Passare alla modalità inserimento tappe cliccando sul pulsante . Il pulsante rimane abbassato. In questa modalità è possibile inserire nello schema un tappa per ogni click effettuato sull'area bianca della finestra. Durante l'inserimento verranno utilizzati parametri di default. Per uscire dalla modalità inserimento tappe cliccare nuovamente sul pulsante, che ritorna così alla sua posizione originaria.

Modifica posizione Per spostare un tappa nell'area dell'editor è necessario uscire da qualsiasi modalità, in altre parole tutti i pulsanti della toolbar devono essere alzati. Spostare un tappa trascinandola con il tasto sinistro del mouse.

Modifica parametri di simulazione Cliccando con il tasto destro del mouse su una tappa è possibile visualizzare una piccola finestra dalla quale si visualizzano ed eventualmente si possono modificare tutti i parametri di simulazione relativi al tappa in questione.

(Figura 2-2) Finestra delle proprietà della tappa

Nel campo “Label” si può inserire un’etichetta per fornire un’indicazione intuitiva della funzionalità. Nel campo “Tokens” si può fornire il numero di gettoni al tempo zero della simulazione. Nel campo “Type” è possibile scegliere tra tre diverse modalità di risoluzione dei conflitti tra ‘random’, ‘smallerfirst’, ‘biggerfirst’. Con quest’ultimo parametro si può specificare un metodo di risoluzione dei conflitti. Se più transizioni attivabili hanno archi entranti che provengono dalla tappa in esame, allora ne verrà scelta una in base al criterio impostato:

Type Soluzione conflitto

‘random’ sceglie a caso tra le transizioni attivabili

‘smallerfirst’ soddisfa prima le richieste di gettoni più basse

‘biggerfirst’ soddisfa prima le richieste di gettoni più alte

PetriNet Capitolo 3

Pagina 7

Scegliere il pulsante “OK” per salvare i dati, “Cancel” per annullare le modifiche.

Eliminazione Entrare in modalità eliminazione cliccando sul pulsante che mostra la gomma da cancellare. Cliccare con il tasto sinistro del mouse sulla tappa per eliminarlo. Per uscire dalla modalità eliminazione cliccare nuovamente sul pulsane che mostra la gomma.

2.2.3 Transizioni Una transizione rappresenta una operazione da effettuare sui gettoni. Riferirsi alla teoria sulle reti di Petri per maggiori informazioni.

Inserimento

Passare alla modalità inserimento transizione cliccando sul pulsante . Il pulsante rimane abbassato. In questa modalità è possibile inserire nello schema una transizione per ogni click effettuato sull'area bianca della finestra. Durante l'inserimento verranno impostati parametri di default. Per uscire dalla modalità inserimento transizioni cliccare nuovamente sul pulsante, che ritorna così alla sua posizione originaria.

Modifica posizione Per spostare una transizione nell'area dell'editor è necessario uscire da qualsiasi modalità, in altre parole tutti i pulsanti della toolbar devono essere alzati. Spostare una transizione trascinandolo con il tasto sinistro del mouse.

Modifica parametri di simulazione Cliccando con il tasto destro del mouse su una transizione è possibile visualizzare una piccola finestra dalla quale si visualizzano ed eventualmente si possono modificare tutti i parametri di simulazione relativi alla transizione in questione.

(Figura 2-3) Finestra delle proprietà della transizione

Nel campo “Label” si può inserire un’etichetta per fornire un’indicazione intuitiva della funzionalità. Nel campo “Type” è possibile scegliere tra tre diverse modalità di attivazione tra ‘const’, ‘uniform’, ‘gaussian’. Nel campo “Params” vanno impostati i parametri per le diverse modalità di attivazione. Il significato di questo campo dipende dal valore di “Type”:

PetriNet Capitolo 3

Pagina 8

Type Params Tempo di attivazione

‘const’ [t] costante, pari a t passi

‘uniform’ [] (non usato) distribuito uniformemente nell’intervallo specificato da Bounds, estremi inclusi

‘gaussian’ [mu, sigma] distribuzione gaussiana con media mu e deviazione standard sigma

Il campo “Bounds” specifica il limite inferiore e superiore al tempo di attivazione, utili nel caso di distribuzioni di probabilità con supporto illimitato. Scegliere il pulsante “OK” per salvare i dati, “Cancel” per annullare le modifiche.

Eliminazione Entrare in modalità eliminazione cliccando sul pulsante che mostra la gomma da cancellare. Cliccare con il tasto sinistro del mouse sulla transizione per eliminarla. Per uscire dalla modalità eliminazione cliccare nuovamente sul pulsane che mostra la gomma.

2.2.4 Archi Un arco collega un tappa con una transizione e viceversa. Riferirsi alla teoria sulle reti di Petri per maggiori informazioni.

Inserimento

Passare alla modalità inserimento archi cliccando sul pulsante . Il pulsante rimane abbassato. Cliccare con il tasto sinistro del mouse su una tappa e successivamente su una transizione per aggiungere un arco che parte dalla tappa e termina sulla transizione, cliccare sulla transizione e successivamente sulla tappa per aggiungere un arco un senso inverso. Il peso di default di un arco è posto pari a 1 durante l’inserimento. Per uscire dalla modalità inserimento archi cliccare nuovamente sul pulsante, che ritorna così alla sua posizione originaria.

Modifica posizione Gli archi vengono disegnati dalla tappa alla transizione o viceversa in modo automatico. Non è possibile cambiarne né la forma né la posizione.

Modifica parametri di simulazione Cliccando con il tasto destro del mouse su una transizione è possibile visualizzare una piccola finestra dalla quale si visualizza ed eventualmente si può modificare il peso dell’arco.

(Figura 2-4) Finestra delle proprietà dell’arco

Inserire un peso negativo per trasformare l’arco in un arco negato, un arco negato è facilmente individuabile nella rete per un piccolo cerchio alla sua base. Scegliere il pulsante “OK” per salvare i dati, “Cancel” per annullare le modifiche.

PetriNet Capitolo 3

Pagina 9

Eliminazione Entrare in modalità eliminazione cliccando sul pulsante che mostra la gomma da cancellare. Cliccare con il tasto sinistro del mouse sull’arco per eliminarlo. Per uscire dalla modalità eliminazione cliccare nuovamente sul pulsane che mostra la gomma.

2.2.5 Memorizzazione della rete su disco La rete può essere memorizzata su disco in formato Matlab, con estensione “pet”.

(Figura 2-5) Menù file

Salvataggio Dopo aver disegnato una rete selezionare “Save as…” dal menù “File”, fornire un nome per il file che conterrà la rete tramite il dialogo standard di salvataggio file.

Apertura Selezionare “Open…” dal menù “File”, poi scegliere il file da cui leggere la rete tramite il dialogo standard di apertura file. L’area di lavoro, preventivamente svuotata, mostrerà la rete caricata.

Importazione Selezionare “Import…” dal menù “File”, scegliere il file dal disco e premere il pulsante OK. L’importazione inserisce una rete nell’area di lavoro attualmente in uso, senza eliminare la rete eventualmente già presente. Con questa funzione è possibile organizzare delle librerie di sottoreti.

2.3 Funzioni del simulatore

Nella parte inferiore della toolbar è possibile accedere a tutti i comandi del simulatore. Le opzioni sono invece disponibili tramite menù.

2.3.1 Play

Con il pulsante Play è possibile dare inizio alla simulazione. La simulazione continuerà finché non verrà fermata o verrà determinata una condizione di stallo. Se la simulazione era ferma (dopo uno Stop) viene memorizzato lo stato come stato iniziale della simulazione per essere ripristinato alla successiva pressione del pulsante Stop.

PetriNet Capitolo 3

Pagina 10

2.3.2 Step

Premere il pulsante Step per effettuare un solo passo di simulazione. Se la simulazione era ferma (dopo uno Stop) viene memorizzato lo stato come stato iniziale della simulazione per essere ripristinato alla successiva pressione del pulsante Stop.

2.3.3 Pause

Premendo il pulsante Pause durante la simulazione è possibile sospenderla temporaneamente. La simulazione verrà fermata e sarà possibile osservare lo stato attuale della rete. Se lo stato viene modificato durante la pausa, continuando la simulazione l’evoluzione seguirà dalle nuove impostazioni, ma premendo il tasto Stop verrà ripristinato lo stato iniziale, quello precedente all’inizio della simulazione.

2.3.4 Stop

Con il pulsante Stop si ferma completamente la simulazione. Lo stato della rete viene ripristinato con i dati iniziali, quindi la rete sarà pronta per una nuova simulazione.

2.3.5 Opzioni simulatore Per modificare le opzioni del simulatore scegliere “Simulation” dal menu “Options”. Verrà mostrata una finestra con tutti i parametri utilizzati dal simulatore.

(Figura 2-6) Finestra delle proprietà del simulatore

Step time In questo campo può essere impostata la durata in millisecondi della metà di un passo di simulazione. La simulazione può essere in questo modo velocizzata o rallentata per mettere in evidenza i risultati finali o l’evoluzione.

Exhaustive search Se attivata fa in modo che il simulatore risolva in un solo passo tutti i possibili conflitti di attivazione, che altrimenti richiederebbero più passi.

Short circuit Se attivata esegue la simulazione più velocemente, ma forzando l’attivazione anche in condizioni di ambiguità può dar luogo ad attivazioni spurie o non desiderate.

[Per maggiori dettagli “3.3 Funzionamento simulazione”]

PetriNet Capitolo 3

Pagina 11

2.3.6 Messaggi stallo Se durante la simulazione nessuna transizione può essere attivata l’utente viene avvertito con un messaggio nella console Matlab e la simulazione viene fermata:

• 'Stall detected: no more transitions can be activated' Mostrato quando tutte le condizioni per l’attivazione delle transizioni non possono essere soddisfatte, la simulazione deve terminare.

• 'Stall detected: all transitions conflict each others (may retry)'

Mostrato quando le condizioni per l’attivazione di qualche transizione possono essere soddisfatte ma essendo in conflitto tra loro non permettono l’attivazione della transizione. Se il metodo di risoluzione dei conflitti, impostato nelle opzioni delle tappe, è di tipo random allora continuando la simulazione il conflitto potrebbe essere risolto.

2.4 Funzioni per l'analisi

2.4.1 Tipo di dati raccolti I dati raccolti vengono memorizzati nella struttura Log accessibile dalla console di Matlab per consentire una veloce analisi statistica. Per le tappe viene memorizzato il numero di gettoni e per le transizioni lo stato di attività, ad ogni passo della simulazione.

[Per le specifiche dettagliate “3.1.3 Struttura Log”]

2.4.2 Selezione target analisi

Premere il pulsante Select per entrare nella modalità di analisi. I target selezionati mostreranno un contorno tratteggiato. Effettuare un click con il tasto sinistro del mouse per selezionare o deselezionare le tappe e le transizioni di cui si vuole effettuare l’analisi statistica. Per limitare l’impiego di risorse, i dati per le analisi statistiche vengono raccolti solo se espressamente richiesto. Si consiglia inoltre di modificare la selezione dei target solo a simulazione conclusa, pena la possibile incongruenza temporale dei dati raccolti. Per uscire dalla modalità statistica cliccare nuovamente sul pulsante, che ritorna così alla sua posizione originaria.

2.4.3 Visualizzazione dati

Premere il pulsante Select per entrare nella modalità di analisi. I target che dispongono di informazioni statistiche mostrano un contorno tratteggiato. Effettuare un click con il tasto destro del mouse su tali target per visualizzare i grafici. E’ possibile visualizzare informazioni statistiche solo per i target preventivamente selezionati e dopo aver eseguito una simulazione. Per uscire dalla modalità statistica cliccare nuovamente sul pulsante, che ritorna così alla sua posizione originaria.

PetriNet Capitolo 3

Pagina 12

PetriNet 1.0 dispone di un semplice sistema di visualizzazione dei dati statistici raccolti durante la simulazione.

(Figura 2-7) Finestra Statistiche delle Tappe

(Figura 2-8) Finestra Statistiche delle Transizioni

Nella Finestra Statistiche delle Tappe è mostrato l’andamento nel tempo della quantità di gettoni presenti nella tappa analizzata, mentre nella Finestra Statistiche delle Transizioni si può osservare l’andamento del tempo di attivazione ad ogni passo. I grafici riportati in figura riportano l’analisi di una tappa che fornisce gettoni a una transizione con attivazione uniforme nell’intervallo [1, 3]. Nella Finestra Statistiche delle Tappe è riportata la media matematica, con una linea blu, della quantità di gettoni presenti durante tutto l’intervallo di simulazione analizzato, mentre nella Finestra Statistiche delle Transizioni è riportata la media dei tempi di attivazione, calcolata sui passi in cui comincia l’attivazione, con una linea blu e la media dei tempi di attività, calcolata su tutti i passi, con una linea rossa. In basso, un piccolo grafico a barre riporta il valore 1 se in quell’istante ha avuto inizio un’attivazione, -1 se l’attivazione era già avvenuta ma non è ancora terminata, 0 se la transizione non è attiva.

2.4.4 Rimando alle funzioni Matlab per la statistica Matlab è uno strumento matematico molto potente che supporta l’analisi statistica sia grazie a funzioni native che allo “Statistic Toolbox” presente nelle varie distribuzioni. Sarebbe inutile pretendere di presentare al lettore in modo esauriente le numerose funzioni disponibili, per questo motivo si rimanda alla documentazione fornita con Matlab stesso.

PetriNet Capitolo 3

Pagina 13

3. Specifiche tecniche

3.1 Rappresentazione di una rete di Petri

La rappresentazione di una rete di Petri si può logicamente suddividere in due sottoinsiemi: i parametri statici della rete, che sono tutti quei parametri che non variano durante l'evoluzione della rete, e i parametri dinamici, che viceversa possono variare durante l'evoluzione e sono necessari a completare la descrizione della rete in un dato istante. Il ruolo delle strutture dati Net e State é appunto quello di memorizzare, in una forma facilmente manipolabile, rispettivamente i parametri statici e dinamici della rete. Inoltre é presente una struttura dati aggiuntiva che tiene traccia di informazioni dedotte dalla storia dei parametri dinamici della rete, utili ad esempio a caratterizzare statisticamente l'evoluzione della rete durante la simulazione.

3.1.1 Struttura Net Questa struttura contiene tutti i parametri statici della rete, che ne determinano l'evoluzione nel tempo, e alcuni parametri grafici, utilizzati dall'Editor e dal Simulatore per la rappresentazione visuale della rete. La struttura Net é così composta:

Net

NumPlaces Place Trans Options

Label Label StepTime

NumTrans Rect Rect Exhaustive

Type Type ShortCircuit

InputArcs (Conflict) Bounds

Param

OutputArcs

NumPlaces, NumTrans Numeri interi, memorizzano rispettivamente il numero di tappe e di transizioni della rete.

Place Vettore di strutture, il cui i-esimo elemento contiene i parametri relativi alla i-esima tappa della rete: la posizione nel piano (Rect), l'eventuale etichetta associata (Label) e il tipo di risoluzione dei conflitti (Type), quando due o più archi uscenti dalla tappa incidono su transizioni attivabili.

Trans Vettore di strutture, il cui i-esimo elemento contiene i parametri relativi alla i-esima transizione della rete: quali la posizione nel piano (Rect), l'eventuale etichetta associata (Label), il tipo di attivazione (Type), che può specificare un tempo di attivazione costante o aleatorio.

PetriNet Capitolo 3

Pagina 14

InputArcs Matrice degli archi di ingresso nelle transizioni (NumTrans × NumPlaces). Contiene i pesi su ciascun arco che parte da una tappa e termina su una transizione. Un peso positivo indica una richiesta di gettoni per l'attivazione, cioè la tappa di partenza deve avere un numero di gettoni maggiore o uguale del peso dell'arco affinché la transizione possa attivarsi. Un peso negativo modella invece gli archi inibitori e ne estende le funzionalità, cioè la tappa di partenza deve avere un numero di gettoni inferiore al peso dell'arco cambiato di segno per poter attivare la transizione. Ad esempio, un peso –1 attiva la transizione solo se la tappa è vuota. Un peso nullo rappresenta una connessione inesistente.

OutputArcs Matrice degli archi di uscita dalle transizioni (NumTrans × NumPlaces). Contiene i pesi su ciascun arco che parte da una transizione e termina su una tappa. Il peso dell'arco rappresenta il numero di gettoni depositati nella tappa quando l'attività della transizione viene completata. Un peso nullo rappresenta una connessione inesistente.

Options Struttura che contiene le opzioni di simulazione della rete: la durata di un passo di simulazione (StepTime), la ricerca esaustiva di possibili attivazioni (Exhaustive) e il corto-circuito durante la valutazione dell'attivabilità di una transizione (ShortCircuit).

3.1.2 Struttura State Questa struttura contiene tutti i parametri dinamici della rete, che ne descrivono l'evoluzione nel tempo. La struttura State é così composta:

State

Tokens

Activity

Tokens Vettore riga, contiene il numero di gettoni che si trovano in ciascuna tappa.

Activity Vettore riga, contiene il numero di passi di simulazione che mancano a completare l'attività di ciascuna transizione. Zero se la transizione non é attiva.

3.1.3 Struttura Log Questa struttura contiene i dati raccolti durante la simulazione della rete, che possono essere visualizzati graficamente con l’Editor o analizzati facilmente con Matlab. La struttura Log é così composta:

Log

Place Trans

Selected Selected

Evolution Evolution

PetriNet Capitolo 3

Pagina 15

Place Vettore di strutture, il cui i-esimo elemento contiene: il numero di gettoni nella tappa i-esima ad ogni passo della simulazione (Evolution), se questa è stata selezionata (Selected) per la raccolta dati.

Trans Vettore di strutture, il cui i-esimo elemento contiene: lo stato della transizione i-esima ad ogni passo della simulazione (Evolution), se questa è stata selezionata (Selected) per la raccolta dati.

3.2 Operazioni su una rete

3.2.1 Creazione Le strutture dati che rappresentano una rete di Petri vengono inizializzate con le seguenti chiamate a funzione:

net = createnet; state = createstate(net);

Con la funzione CreateNet si costruisce una rete vuota, mentre con la funzione CreateState si costruisce uno stato di default per la rete passata come parametro. Lo stato di default della rete consiste in nessun gettone in ciascuna tappa e tempi di attività nulli per ciascuna transizione ed equivale ad uno stato di riposo.

3.2.2 Aggiunta Per aggiungere alla rete delle nuove tappe o transizioni si possono utilizzare le seguenti chiamate a funzione:

[net, state, idx] = addplace(net, state); [net, state, idx] = addtransition(net, state);

Entrambe le funzioni restituiscono una nuova rete e un nuovo stato in cui sono state apportate le modifiche richieste e l’indice della tappa o transizione appena aggiunta. Lo stato e i parametri del nuovo componente sono quelli di default.

3.2.3 Cancellazione Per rimuovere dalla rete delle tappe o transizioni si possono utilizzare le seguenti chiamate a funzione:

[net, state] = delplace(net, state, idx); [net, state] = deltransition(net, state, idx);

Entrambe le funzioni richiedono l’indice della tappa o transizione da rimuovere e restituiscono una nuova rete e un nuovo stato in cui sono state apportate le modifiche richieste.

3.2.4 Validazione Per verificare la validità delle strutture dati che rappresentano una rete di Petri si possono utilizzare le seguenti chiamate a funzione:

[nplaces, ntrans] = validate(net); [nplaces, ntrans] = validatestate(net, state);

PetriNet Capitolo 3

Pagina 16

Entrambe le funzioni restituiscono le dimensioni della rete e verificano la consistenza delle strutture dati passate come parametri. In caso di dati non validi l’esecuzione si blocca e viene visualizzato un messaggio con la causa dell’errore.

3.2.5 Unione Si possono unire due reti di Petri chiamando la seguente funzione:

[net, state] = joinnets(net, state, addnet, addstate);

La funzione prende in ingresso due reti e i relativi stati e ne restituisce l’unione.

3.2.6 Modifica Si possono richiamare le seguenti funzioni di modifica globale della rete:

net = setdefaults(net); net = setoptions(net, optionname, optionvalue, ...);

La prima reimposta i parametri statici della rete ai valori di default. La seconda imposta i parametri di simulazione.

3.2.7 Simulazione La simulazione di una rete di Petri si ottiene richiamando ciclicamente le seguenti funzioni:

[midstate, stall] = beginstep(net, state); state = endstep(net, midstate);

La funzione BeginStep calcola lo stato intermedio di attivazione della rete e lo restituisce insieme alla condizione di stallo. Se nessuna transizione può essere attivata la condizione di stallo risulta vera e viene visualizzato un messaggio di avviso, nel qual caso lo stato intermedio è identico a quello passato alla funzione. La funzione EndStep calcola lo stato finale dovuto all’attivazione delle transizioni e conclude un passo della simulazione.

[Per ulteriori dettagli “3.3 Funzionamento simulazione”]

3.2.8 Analisi L’analisi del comportamento della rete si basa sulla raccolta di alcuni dati significativi durante la simulazione. Le funzioni preposte allo scopo sono le seguenti:

log = createlog(net); log = updatelog(net, state, midstate, log);

La funzione CreateLog crea la struttura che conterrà i dati raccolti per l’analisi. Questa operazione si rende necessaria ogni volta che la rete viene modificata e comunque prima di ogni simulazione. La funzione UpdateLog va inserita in mezzo alle due funzioni di simulazione e utilizza lo stato intermedio della rete per scoprire le attivazioni che ci sono state ad ogni passo, anche quelle di durata unitaria che con la sola conoscenza dello stato alla fine di ogni passo non potrebbero essere individuate. Infatti il tempo di attività di una transizione che duri un solo passo, quando questa viene attivata, sale ad 1 per ritornare subito a 0 alla fine del passo.

[Per ulteriori dettagli “3.1.3 Struttura Log”]

PetriNet Capitolo 3

Pagina 17

3.2.9 Funzioni di appoggio Restano poi alcune funzioni ausiliarie:

[nplaces, ntrans] = getsize(net);

Ritorna le dimensioni della rete, senza controlli sulla validità della struttura.

ped; fig = editnet(net, state, log); net = getnet(figure); log = getlog(figure);

Funzioni relative all’utilizzo dell’interfaccia grafica. [Per ulteriori dettagli “5 Riferimento alle funzioni del toolbox”]

3.3 Funzionamento simulazione

Il tipo di rete di Petri preso in considerazione non è facilmente trattabile da punto di vista teorico matematico e quindi l’algoritmo per la simulazione è stato derivato unicamente dalla definizione. Il mattone fondamentale per la realizzazione della simulazione è l’esecuzione di un singolo passo, che può essere logicamente e funzionalmente suddivisa in due fasi distinte.

3.3.1 Fase I La prima fase consiste nella attivazione delle transizioni e nel conseguente prelievo di gettoni dalle tappe di ingresso. Vengono prima ricercate tutte le transizioni attivabili, cioè quelle in cui le condizioni espresse dagli archi di ingresso sono soddisfatte, poi vengono risolti gli eventuali conflitti e determinate le transizioni effettivamente attivate. Due o più transizioni sono in conflitto quando hanno archi di ingresso che provengono dalla medesima tappa e la cui richiesta di gettoni non può essere contemporaneamente soddisfatta, cioè il numero di gettoni presenti nella tappa è minore della somma di tutte le richieste fatte da transizioni attivabili. Per la risoluzione dei conflitti vengono adottate due strategie diverse, la cui scelta dipende dall’opzione Shortcircuit della rete. In entrambi i casi la funzione che risolve i conflitti è la stessa e come risultato fornisce l’insieme delle transizioni che hanno vinto la competizione e l’insieme di quelle che hanno perso. Nel caso di corto-circuito l’algoritmo prende in esame le transizioni attivabili una ad una e per ciascuna di esse risolve gli eventuali conflitti sulle sue tappe di ingresso. Se dal conflitto esce sconfitta una qualunque transizione questa viene esclusa da qualunque altra competizione e marcata come non attivabile. Questo comportamento si basa sulla considerazione che una transizione che non riceva gettoni da una sua tappa di ingresso non soddisfa più le condizioni di attivabilità ed è quindi inutile farla competere in altre tappe. In questo modo si aumenta la probabilità che altre transizioni si possano attivare e si possono sbloccare situazioni di stallo dovute a conflitti incrociati, cioè quando tutte le transizioni attivabili perdono la competizione in almeno una tappa. Se non viene specificato il corto-circuito l’algoritmo prende in cosiderazione tutte le tappe di ingresso di tutte le transizioni attivabili e per ciascuna di esse risolve gli eventuali conflitti. Le transizioni che perdono la competizione non vengono eliminate subito, come nel caso precedente,

PetriNet Capitolo 3

Pagina 18

ma solamente alla fine. E’ quindi possibile che alcuni dei conflitti potessero essere evitati e che venga penalizzata qualche transizione che poteva invece essere attivata. Entrambe le procedure si concludono con l’attivazione delle transizioni vincitrici, ma può accadere che al termine dell’attivazione ci siano ancora delle transizioni attivabili. Questo dipende dall’implementazione della routine di risoluzione dei conflitti che, data la sua semplicità, non considera tutte le possibili combinazioni. Con l’opzione Exhaustive si specifica se iterare il procedimento finchè non ci siano più transizioni attivabili. Senza questa opzione si renderebbero necessari passi di simulazione aggiuntivi, durante la cui esecuzione però lo stato della rete cambia. Pro e contro delle varie opzioni di simulazione: Opzione Pro Contro

Shortcircuit SI Maggiore velocità di simulazione Sblocco di stalli dovuti a conflitti

L’attivazione dipende dall’ordinamento di tappe e transizioni Si sbloccano anche situazioni di effettiva indecidibilità

Shortcircuit NO L’attivazione non dipende dall’ordinamento di tappe e transizioni

Aumenta il residuo di transizioni attivabili ma non attivate

Exhaustive SI Attivazione di tutte le transizioni possibili in un solo passo

Minore velocità di simulazione

Exhaustive NO Maggiore velocità di simulazione La rete potrebbe comportarsi in modo diverso dalle aspettative

In conclusione si può affermare che senza corto-circuito si ottiene una specie di attivazione parallela, in cui ciascun conflitto viene risolto indipendentemente dagli altri. Questo può portare a situazioni di stallo anche quando ci sono transizioni che soddisfano tutte le condizioni per l’attivazione e una tale situazione può evidenziare dei problemi nella struttura della rete: per esempio, due transizioni in conflitto su due tappe diverse potrebbero risultare vincitrici in una e perdenti nell’altra. In assenza di informazioni su quale delle due ha la precedenza, entrambe non vengono attivate. Il corto-circuito, in analogia con la valutazione delle espressioni logiche del C/C++, risolve il problema tramite l’ordinamento: i conflitti sono valutati in sequenza e appena ci sono sufficienti informazioni per stabilire che una transizione non può essere attivata, viene esclusa dalle altre competizioni. Può darsi che una tale soluzione non sia desiderabile e quindi la scelta di usare o meno questa opzione viene demandata all’utente. La ricerca esaustiva, viceversa, sarebbe sempre utile, ma può portare a notevoli rallentamenti nel caso di reti molto grandi, per cui anche la scelta di attivare o meno questa opzione è affidata all’utente. Si fa notare che con una più accurata procedura per la risoluzione dei conflitti la ricerca esaustiva potrebbe rendersi non più necessaria.

3.3.2 Fase II La seconda fase consiste nel completamento dell’attività delle transizioni e nel conseguente trasferimento di gettoni nelle tappe di uscita. Il tempo di attività delle transizioni attive viene decrementato e quando raggiunge lo zero si provvede ad aggiungere alle tappe in uscita il numero di gettoni specificato dagli archi di collegamento. Questa suddivisione di un passo di simulazione si è resa necessaria sia per consentire la visualizzazione grafica dell’attivazione, sia per la raccolta dei dati da analizzare. Infatti transizioni la cui attività dura un solo passo non potrebbero altrimenti essere osservate.

PetriNet Capitolo 3

Pagina 19

Nel complesso la seconda fase non presenta particolari problemi, poiché non è possibile alcun conflitto in uscita dalle transizioni, avendo supposto che le tappe non hanno una capacità massima. La procedura è risultata quindi di semplice realizzazione.

PetriNet Capitolo 4

Pagina 20

4. Conclusioni

PetriNet 1.0 è stato progettato in ambito universitario. I sorgenti, in codice Matlab, ampiamente curati e commentati, sono disponibili sotto le limitazioni della licenza GNU. Nota l’importanza delle Reti di Petri per la modellazione e la simulazione, si intende fornire una buona base di pubblico dominio per futuri sviluppi, completamente integrata in Matlab che garantisca una buona compatibilità tra le piattaforme e un ottimo metodo di analisi matematica e statistica.

4.1 Limitazioni

Dall’invenzione delle Reti di Petri ad oggi, sono state standardizzate molte tipologie diverse di reti, ognuna riconducibile alle reti originarie ma con metodi di descrizione e di simulazione molto diversi tra loro. E’ per questo motivo che risulta alquanto complicato generalizzare le reti di Petri e cercare di racchiuderle tutte in un unico modello. Con PetriNet 1.0 è possibile trattare solo le reti a tappe e transizioni, le reti temporizzate e le reti stocastiche.

4.2 Sviluppi futuri

Il punto di forza di questo progetto è sicuramente la modularità e la disponibilità dei sorgenti in linguaggio Matlab. In quest’ottica le limitazioni riportate al paragrafo precedente sembrano svanire. Chiunque potrà aggiungere nuove funzionalità e, grazie alla licenza GNU, saranno pubblicamente disponibili per nuove idee.

4.2.1 Sviluppi di media durata Trasformazione della rete in una rete colorata. Esecuzione di una procedura Matlab, in modo asincrono, durante l’attivazione delle transizioni.

4.2.2 Sviluppi di lunga durata Dipendenza del peso degli archi in funzione dei gettoni presenti nelle tappe. Implementazione di librerie con parti di reti. Implementazione dei sottosistemi analoghi a quelli di Simulink.

PetriNet Capitolo 5

Pagina 21

5. Riferimento alle funzioni del toolbox

PetriNet - Editing and Simulation Toolbox. Version 1.0 - Licensed under GNU Public License Copyright (C) P. Messina - G. Ribichini, 08-mar-2002 Function index: Ped - Launch PetriNet Editor. EditNet - Opens the specified net and initial state in the Editor. GetNet - Retrieve Net and State structures from an Editor window. GetLog - Get the Log structure from an Editor window. CreateNet - Builds an empty Petri net. CreateState - Builds a default state for an existing Petri net. CreateLog - Builds an empty log for an existing Petri net. AddPlace - Add a new place to a Petri net. AddTransition - Add a new transition to a Petri net. DelPlace - Deletes a place from a Petri net. DelTransition - Deletes a transition from a Petri net. GetSize - Retrieve the size of a PetriNet. JoinNets - Join two PetriNet structures. SetDefaults - Set structures to default values. SetOptions - Set simulation options of a Petri net. BeginStep - Compute the first phase of a simulation step. EndStep - Compute the second phase of a simulation step. PED Launch PetriNet Editor. Ped opens a new editor window. EDITNET Opens the specified net and initial state in the Editor. fig = EditNet(Net, State, Log) returns the figure used to show the net. Net - structure representing a Petri net State - initial state for places and transitions Log - history of activations and place contents All arguments are optional and they are replaced with default values if missing. GETNET To retrieve Net and State structures from an Editor window. [Net, State] = GetNet(figure) returns Net and State structure of the figure. GETLOG Get the Log structure from an Editor window. Log = GetLog(figure) returns the Log structure of simulation in the figure.

PetriNet Capitolo 5

Pagina 22

CREATENET Builds an empty Petri net. Net = CreateNet returns a new Petri net structure. ------------------------------------------------------------- Net (struct): description of a Petri net, with evolution parameters .NumPlaces - number of places in the net .NumTrans - number of transitions in the net .Place (array of struct): .Label - string specifying a label for the place .Rect - array with the rectangular region where the place lies .Type - string specifying the type of conflict resolution .Conflict - (reserved - used internally for conflict resolution) Type = 'random' choose randomly among demanding transitions Type = 'smallerfirst' smaller requests of tokens are satisfied first Type = 'biggerfirst' bigger requests of tokens are satisfied first .Trans (array of struct): .Label - string specifying a label for the transition .Rect - array with the rectangular region where the transition lies on the plane .Type - string specifying the type of activation .Params - array of parameters for the various types of activation .Bounds - two element array with lower and upper bounds to activation time [lb, ub] Type = 'const' constant time => Params = [time] Type = 'uniform' uniformally distributed in the [lb, ub] interval (inclusive) => Params = [] (unused) Type = 'gaussian' gaussian distrib. with mean mu, std.deviation sigma => Params = [mu, sigma] .InputArcs - input arcs matrix: rows are transitions, columns are places 0 => no arc w>0 => arc with weight (place tokens must be >= w to activate transition) w<0 => inhibition (place tokens must be < -w to activate transition) .OutputArcs - output arcs matrix: rows are transitions, cols are places 0 => no arc w>0 => arc with weight (completed transitions put w tokens in relative place) .Options (struct): .Exhaustive - boolean, search for possible activations until there aren't anymore .Shortcircuit - boolean, if a transition lose activation for one place, don't count it for the others .StepTime - duration of a simulation step, in milliseconds

PetriNet Capitolo 5

Pagina 23

CREATESTATE Builds a default state for an existing Petri net. State = CreateState(Net) returns a zero state for specified Petri net. ------------------------------------------------------------- State (struct): actual state of a Petri net .Tokens - row vector containing the tokens present in each place .Activity - row vector containing activity time for each transition (in steps) 0 => inactive, t>0 => still t steps to complete the transition createlog Builds an empty log for an existing Petri net. Log = CreateLog(Net) returns a new log for the specified Petri net. ------------------------------------------------------------- Log (struct): activity log of a Petri net .Place (array of struct) .Selected .Evolution - row vector containing the tokens at each simulation step .Trans .Selected .Evolution - row vector containing transition activity at each simulation step 0 => idle, 1 => activated, -1 => busy (already active) ADDPLACE Add a new place to a Petri net. [Net, State, i] = AddPlace(Net, State) returns the modified net structure and state, along with the index of the new place. NOTE: You should re-create the log using CreateLog, after the structure of the net has changed. ADDTRANSITION Add a new transition to a Petri net. [Net, State, i] = AddTransition(Net, State) returns the modified net structure and state, along with the index of the new transition. NOTE: You should re-create the log using CreateLog, after the structure of the net has changed. DELPLACE Deletes a place from a Petri net. [Net, State] = DelPlace(Net, State, i) returns the modified net structure and state, wants the index of the place to delete. NOTE: You should re-create the log using CreateLog, after the structure of the net has changed.

PetriNet Capitolo 5

Pagina 24

DELTRANSITION Deletes a transition from a Petri net. [Net, State] = DelTransition(Net, State, i) returns the modified net structure and state, wants the index of the transition to delete. NOTE: You should re-create the log using CreateLog, after the structure of the net has changed. GETSIZE To retrieve size of a PetriNet. [nPlaces, nTrans] = GetSize(Net) returns nPlaces and nTrans of Net. JOINNETS To join two PetriNet structures. [Net, State] = JoinNets(Net, State, AddNet, AddState) returns the modified net structure and state. NOTE: You should re-create the log using CreateLog, after the structure of the net has changed. SETDEFAULTS set structures to default values. Net = SetDefaults(Net) returns the modified net structure SETOPTIONS Set simulation options of a Petri net. Net = SetOptions(Net, OptionName, OptionValue, ...) returns the modified net structure, with options set as specified. OptionName OptionValue Meaning ------------------------------------------- 'exhaustive' [0|1] enables exhaustive search 'shortcircuit' [0|1] enables shortcircuit 'steptime' millisec sets simulation step delay BEGINSTEP Computes the first phase of a simulation step. [NewState, Stall] = BeginStep(Net, State) returns the intermediate state of the net and the stall condition. The first phase finds all the possible activations and returns an intermediate state for the simulation where the proper transitions have been fired up. This is needed to see activations in the simulator. If no activation can take place, the stall condition is detected and displayed. The returned Stall variable is a logical variable, thus it's true (1) or false (0), whether or not a stall is detected. ENDSTEP Compute the second phase of a simulation step NewState = EndStep(Net, State) returns the final state of the net after one step of execution. The second phase decreases the activity time of active transitions and sends the specified amount of tokens in the output places of completed transitions.