Esercizio: rappresentare con una rete di Petri il seguente protocollo di comunicazione: ciascun...

transcript

Esercizio: rappresentare con una rete di Petri il seguente protocollo di comunicazione: ciascun utente in modo ciclico trasferisce dati e/o passa la comunicazione all’utente successivo

Token ring

non attivo

trasferiscedati

attivo

non trasf.dati

non attivo

trasferiscedati

attivo

non trasf.dati

Token ring

utente

Non attivo

Trasferiscedati

attivo

Non trasf.dati

utente

Non attivo

Trasferiscedati

attivo

Non trasf.dati

Esercizio: rappresentare un senso unico alternato costituito da due tratte stradali senza visibilità reciproca (reciprocamente dietro un angolo); introdurre uno o più tipi di controllo con semafori ai due ingressi e rappresentarli

A libera

B libera

Fine A

controllo

A libera

B libera

Fine A

Controllo: verde per 1

Coda 1

1 nella tratta A+B

Coda 2

Interruzione coda 1

2 nella tratta A+B

1 entra: temporizz.

Controllo: verde per 2

Controllo: verde per 1 rosso per 2

Coda 1

1 nella tratta A+B

Coda 2

Interruzione coda 1

2 nella tratta A+B

1 entra: temporizz.

Controllorosso per 1 rosso per 2

Tau: percorrenza della tratta

2.5 Invarianti di posto, di transizione; grafi di sincronizzazione; controllo supervisore di una macchina:invarianti

scatto di t2 :

0 0 1 0 0 0

M2= M1+ C e2

0 1 0-1-1 1

1 0-1 1 0 0

-1-1 1 0 0 0

= M1+C e2

Sequenza di scatti s12 : t1 t2

Conteggio di scatti s12= e1 + e2

= M0 + C s12

EQUAZIONE DI TRANSIZIONE

M2= M0 + C s12

Struttura delle Reti di Petri

P-INVARIANTI

Un invariante di posto è un vettore riga definito positivo* che annulla la matrice di incidenza

* con almeno una componente positiva e le altre positive o nulle

XMi= XM0 + XC s

X 0: XC = 0XMi = XM0

-1-1 1 0 0 0 0 0

INVARIANTI DI POSTO

01110000

10100000

00000110

0 0 0 0 0-1 1 1

1 0-1 1 0 0 0 0

0 1 0-1-1 1-1 0

11210110

Insieme di posti supporto di X: Px P

Px Insieme dei posti le cui

corrispondenti componenti in X sono strettamente positive

pi Px x(i)>0

INVARIANTI DI POSTOInvariante

( [01110 0] )

I p-invarianti sono caratterizzati graficamente da una sottorete N’

- T’ transizioni collegate con posti di Px

- A’ A = (P X T) (T X P)

- A’ = (Px X T’) (T’ X Px)

Invariante( [01110 0] )

P-INVARIANTI

N’ = (Px, T’, A’)

p. att. lav.

p. in lav.

scambiop. in usc.

p.att.usc.

condizione della macchina: disp.

Interpretazione delle sottoreti “supporto”

forcellaliberada p.in usc.

pezzi fuori

P-INVARIANTI

0 1 0-1-1 1

1 0-1 1 0 0

-1-1 1 0 0 0

righe nulla

011100

101000

P-INVARIANTI

000011

*non esiste un invariante con almeno una componente più piccola

In questo grafo ogni ciclo è supporto (ovvero lo sono i suoi posti) di un p-invariante minimale*

P-INVARIANTI minimali*

In tali grafi i posti di ogni ciclo sono supporto di un p-invariante minimale

GRAFI DI SINCRONIZZAZIONE: ogni posto ha solo una transizione di ingresso e una di uscita

GRAFI DI SINCRONIZZAZIONE: ogni ciclo è supporto di un p-invariante minimale

Ogni riga (posto p*) ha un solo 1 (nella colonna t*-in) e un solo -1 (nella t*-out)

Nel ciclo, p* ha un solo predecessore, la relativa riga ha -1 nella t*-in, e un solo successore e la relativa riga ha 1 nella t*-out

Di conseguenza la somma delle righe dei posti del ciclo è nulla e quindi il ciclo è supporto di un invariante

L'invariante è minimale, infatti l’esclusione di una o più righe rende la somma non nulla

0 1 0-1

1 0-1 1

-1-1 1 0

righe nulla

-1-1 1 0 0 0 0 0

01110000

10100000

00000110

0 0 0 0 0-1 1 1

p.att. lav.

scambiop.in usc.

p.att.usc.

condizione dellamacchina

zzo in in

Interfaccia con il sistema di trasporto

pezzi fuori

forcellalibera

1 0-1 1 0 0 0 0

0 1 0-1-1 1-1 0

11210110

Senza p5 e p8 è conservativa

p. in lav.

(diventa un grafo di sincronizzazione)

Gli invarianti di due sottoreti con posti in comune (ma non transizioni) sono la traccia degli invarianti della rete globale e viceversa questi sono la composizione di quelli

-1 1 0 0 1 -1 -1 1 0 0 1 -1

1 1 -1 1 1 -1

C’X’

X” C”

P-INVARIANTI

Una rete è ricoperta da p-invarianti quando ogni posto p P appartiene ad almeno un invariante minimale

se una rete è ricoperta da p-invarianti esiste unp-invariante globale per cui Px = P

-1 1 0 0 1 -1 -1 1 0 0 1 -1

N.B.: un solo invariante, minimale e globale, due cicli (non è un grafo di sincronizzazione)

Gli invarianti minimali formano una base per tutti gli invarianti

Un grafo di sincronizzazione marcato è vivo se ogni ciclo contiene almeno una marca

Proprietà dei Grafi di sincronizzazione

P-invarianti e limitatezzaP-invarianti e limitatezza

Se la rete è ricoperta di p-invarianti (minimali)è limitata

P-invarianti e conservativitàP-invarianti e conservatività

Se esiste un invariante globale° la rete è conservativa per ogni marcatura iniziale con lo stesso peso * w (e viceversa?)

°con x>0: xMi = xM0 + xCs = xM0

per ogni possibile M0 e s*in questo caso la rete si dice strutturalmente conservativa

W=2 W=2

Una rete è ricoperta da p-invarianti quando ogni posto p P appartiene ad almeno un invariante minimale

1 -1 0 0-1 1 0 0 0 1 -1 0 0 0 -1 1 0 0 1 -1

Non è ricoperta

E’ un grafo di sincronizzazione: i cicli sonosupporto di invarianti

Algoritmo di Alaiwan-ToudicAlgoritmo di Alaiwan-Toudic

Serve a determinare gliinvarianti minimali

Con trasformazioni matriciali si riducono progressivamente le dimensioni fino a

trovare le soluzioni intere positive minime di XC=0

Controllo con invariantiControllo con invarianti

Costruendo un invariante con un

posto del controllo si può

imporre il valore della somma

delle marche in assegnati posti

del processo controllatoCiò può corrispondere a specifiche

significative per il processo

Cp : matr. inc. del processo Mp0 : stato iniziale del processoCc : matr. inc. del controllo Mc0 : stato iniziale del controlloLc : matrice delle specifiche B : limiti specificati

SPECIFICHE PER IL PROCESSO: LcMp B

con Lc e B assegnati

Cc := - Lc Cp => le righe di [ Lc Ic ] annullano la matrice di incidenza a ciclo chiuso Cp

sono cioè degli invarianti del sistema processo-controllo, ovvero:

LcMp0 + Mc0 = LcMp + Mc

Quindi se Mc0 := B - LcMp0

LcMp = B - Mc B

B = LcMp + Mc

GATTO TOPO

St.2 St.2St.3

St.5St.4St.4

GATTO TOPO

St.2 St.2St.3

St.5St.4St.4

-1 1 0 0 1 -1 -1 1 0 0 1 -1

T-INVARIANTIT-INVARIANTI

Y 0: C Y = 0

Se unasequenza s riinizializza, il suo conteggio di scatti s è un t-invariante:

Mi=Mi+ C s= Mi

-1 1 0 0 1 -1 -1 1 0 0 1 -1

T-INVARIANTI

dato un t-invariante di 0 e 1, il suo supporto dà una sequenza che,se è ammissibile, riinizializza

0 1 0-1

1 0-1 1

-1-1 1 0

colonne nulla

Invariante: 111

T-INVARIANTI

Magazzino componenti

Magazzino utensili

SUDscheda

testa nord

testa sud

braccio

MACCHINE SMTArchetti, Sciomachen: RAPPRESENTAZIONE ED ANALISI, CON RETI DI PETRI, DI SISTEMI DI LAVORAZIONE - 1989 Consorzio Autofaber, Milano

- modulo B (“tool change & pick”): in cui una testa cambia attrezzo e preleva, mentre l’altra resta ferma

- modulo C (“pick & place”): in cui le operazioni di fissaggio e di prelievo di un componente sono svolte concorrentemente dalle due teste

- modulo D (“pick”): in cui viene affettuato un prelievo di un componente da una delle due teste, mentre l’altra è ferma

- modulo E (“place”): in cui viene affettuato solamente un fissaggio di un componente da una delle due teste, mentre l’altra è ferma

pick nord place sud

NFM NHM

scheda

testa nord

testa sud

braccio

pick nord place (sud)

scheda

testa nord

testa sud

braccioPKN

13 11 9

NFM NHM

BM: movimenti della scheda

AMN: movimenti del braccio da sud a nord

NFM: movimenti del magazzino nord

NHM: movimenti di allineamento della testa nord per prelievo

AMS: movimenti del braccio da nord a sud

SFM: movimenti del magazzino sud

SHM: movimenti di allineamento della testa sud per prelievo

NFM NHM AMN

13 11 9

15357 B

4 623 25

P&Pnord

NHT: attività di preparazione della testa nord per fissaggio

SHT: attività di preparazione della testa sud per fissaggio

SHMSFM AMS NHT

NHMNFM AMN SHT

8 6 4 161

7 5 3 15

1991113

P&Pnord

P&Psud

Un invariante di posto

Tutta la rete P&P è il supporto di un invariante di transizione minimale:

YT = 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Infatti la transizione BM deve scattare due volte e le altre 18 una sola per tornare alla condizione iniziale

NFM NHM AMN

13 11 9

P&Pnord

PLNPKN

CSS AS S AS

S AS S AS

d c ea b

N AS N AS

d c ea b

AR BR BS

PLNPKN

Esercizio: rappresentare con una rete di Petri il seguente protocollo di comunicazione: ciascun...

Documents