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

token

non attivo

trasferiscedati

attivo

non trasf.dati

token

non attivo

trasferiscedati

attivo

non trasf.dati

Token ring

token

utente

Non attivo

Trasferiscedati

attivo

Non trasf.dati

token

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

In A

In B

controllo

A libera

B libera

Fine A

In A

In B

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

Tau +

>>Tau

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

p1 p2

p3

p4

p6

t1

t2

t3

p5

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

0 1 0

= M1+C e2

Sequenza di scatti s12 : t1 t2

Conteggio di scatti s12= e1 + e2

= M0 + C s12

M2 =

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

p7

p5

p4

p3

p2

p1

p6

p8

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] )

p1 p2

p3

p4

p6

t1

t2

t3

p5

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] )

p1 p2

p3

p4

p6

t1

t2

t3

p5

P-INVARIANTI

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

p. att. lav.

p. in lav.

op.

scambiop. in usc.

p.att.usc.

condizione della macchina: disp.

pezzo

in

ing

r.

Interpretazione delle sottoreti “supporto”

forcellaliberada p.in usc.

pezzi fuori

P-INVARIANTI

p1 p2

p3

p4

p6

t1

t2

t3

p5

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

t4

lav

t1

t2

t3

t5

t6

t8

t7

*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

t4

lav

t1

t2

t3

t5

t6

t8

t7

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

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

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

p1 p2

p3

p4

t1

t2

t3

0 1 0-1

1 0-1 1

-1-1 1 0

righe nulla

0111

1010

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

p6

p4

-1-1 1 0 0 0 0 0

01110000

10100000

00000110

0 0 0 0 0-1 1 1

p.att. lav.

op.

scambiop.in usc.

p.att.usc.

condizione dellamacchina

pe

zzo in in

gr .

Interfaccia con il sistema di trasporto

pezzi fuori

forcellalibera

p7

p5p3

p2

p1

p8

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)

1

2

3

4

12 3

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 1 1 -1

1 1 -1 1 1 -1

CX

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

2

3

4

12 3

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

1 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

t4

lav

t1

t2

t3

t5

t6

t8

t7

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

t4

lav

t1

t2

t3

t5

t6

t8

t7

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

1

2 3

4

5

1 2

34

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

Controllo con invariantiControllo con invarianti

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

Cc

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

Controllo con invariantiControllo con invarianti

GATTO TOPO

St.2 St.2St.3

St.1

St.5

St.3

St.1

St.5St.4St.4

Controllo con invariantiControllo con invarianti

GATTO TOPO

St.2 St.2St.3

St.1

St.5

St.3

St.1

St.5St.4St.4

1

2

3

4

12 3

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

T-INVARIANTIT-INVARIANTI

1100

0011

1111

Y 0: C Y = 0

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

Mi=Mi+ C s= Mi

1

2

3

4

12 3

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

T-INVARIANTI

1100

0011

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

p1p2

p3

p4

t1

t2

t3

0 1 0-1

1 0-1 1

-1-1 1 0

colonne nulla

Invariante: 111

T-INVARIANTI

Magazzino componenti

Magazzino utensili

NORD

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

357

NFM NHM

BM

scheda

AMN

testa nord

testa sud

braccio

1

pick nord place (sud)

scheda

testa nord

testa sud

braccioPKN

17

13 11 9

357 2

NFM NHM

BM

AMN 1

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

PKN

17

13 11 9

PLN

21

SHT

15357 B

M

1

2

19

4 623 25

46

P&Pnord

NHT: attività di preparazione della testa nord per fissaggio

SHT: attività di preparazione della testa sud per fissaggio

PKS

SHMSFM AMS NHT

PLS

BM2

2014

PKN

NHMNFM AMN SHT

PLN

2624

18 22

10

8 6 4 161

7 5 3 15

23 25

17 21

1991113

P&Pnord

P&Psud

SMT

12

23

AMN

PKN

PKS

AMS

17

9

10

4

18

3 24

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

PKN

17

13 11 9

PLN

21

SHT

153

57 BM

1

2

19

23 25

46

P&Pnord

SHT

PLNPKN

CSS AS S AS

d

ca

bAMAS

S AS

BR BM

BS

CR

NFM

NTC

AR

N

TN

e

S AS S AS

d c ea b

S AS

STC

N AS N AS

d c ea b

BM

AM

AS

S

AR BR BS

CS

CR

N

CS

TS

TN

CR

PLS

SFM

NHT

SHT

PLNPKN

NFM

NTC

PKS