of 96 /96
Redes de Petri

5_Redes de Petri

Embed Size (px)

Citation preview

Page 1: 5_Redes de Petri

Redes de Petri

Page 2: 5_Redes de Petri

Classificação

Níveis de Abstração

Fundamental

Intermediário

Alto Nível

Modelo Representativo

Sistemas elementares

Redes condição evento

Redes Lugar/Transição

Redes Coloridas

2

Page 3: 5_Redes de Petri

Redes de Petri

Família de técnicas de descrição formal

Introduzidas por Carl A. Petri, na Universidade de Darmstadt, 1962 –Alemanha

Kommunikation mit Automaten

3

Page 4: 5_Redes de Petri

Redes de Petri

Áreas de AplicaçãoConcorrência

Arquitetura de Computadores

Protocolo de Redes

Sistemas Operacionais

Sistemas de Produção

Sistemas Digitais

Hardware/Software Co‐design

Engenharia de Software

Sistemas de Tempo Real

Modelagem e Avaliação de Desempenho

Diagnóstico de Falhas

Controle de Tráfego

Workflow

Administração

Química

etc.

4

Page 5: 5_Redes de Petri

Representação gráfica

Elementos gráficos Estrutura da Rede

5

Lugar

Transição

Arco

p1 p2t1

Page 6: 5_Redes de Petri

Representação gráfica

Múltiplos arcos Pesos indicando a multiplicidade

6

p1

t1

p3

p2 p1

t1

p3

p2

3

2

Page 7: 5_Redes de Petri

Transicão montaocorre

Transicão monta

habilitada

Exemplo I

Embalar 2 buchas e 2 parafusos em uma embalagem de plástico 

parafusos

2

2

embalagem

buchas

embaladeira livre

depósito desaída

despachaembaladeiraocupadamonta

2 embalagens;

6 parafusos;

6 buchas;

Embaladeira está livre;

Transicão despachahabilitada

Transicão despachaocorre

Nenhuma transicão pode ocorrer a partir de agora

Page 8: 5_Redes de Petri

Exemplo II

Reação química para produzir uma molécula de água 

Reaçãoquímica

O2

H2O2

H2

2

Reacão quimicahabilitada

Abstracão!!!

Page 9: 5_Redes de Petri

Rede Lugar/TransiçãoN = (P, T, F, W, M0)

P = {p0, p1, ⋅ ⋅ ⋅, pn}, conjunto finito de lugares T = {t0, t1, ⋅ ⋅ ⋅, tm}, conjunto finito de transições F: A ⊆ (P × T) ∪ (T × P), conjunto finito de arcosW: F → N, funcão peso do arco (multiplicidade)M0: P → N,  marcação inicial P ∩ T = ∅ e P ∪ T ≠ ∅

•t ={p ∈ P | (p, t) ∈ F), conjunto de lugares de entradat• ={p ∈ P | (t, p) ∈ F), conjunto de  lugares de saída•p ={t ∈ T | (t, p) ∈ F), conjunto de transições de entradap• ={t ∈ T | (p, t) ∈ F), conjunto de transições de saída

Page 10: 5_Redes de Petri

Rede Lugar/Transição

N = (P, T, F, W, M0)P = {p0, p1, ⋅⋅⋅, pn}: lugares T = {t0, t1, ⋅⋅⋅, tn}: transições F: A ⊆ (P × T) ∪ (T × P): arcos

W: F → N: funcão peso

M0: P → N: marcação inicial

10

p1 2

2

p0

p2

p3

p5t1p4t0

P = {p0, p1, p2, p3, p4, p5}T = {t0, t1}

F = {(p0, t0),(p1, t0),(p2, t0),(p3, t0),(p4, t1),(t0, p4),(t1 ,p3),(t1, p5)}

W(p0, t0) = 1 W(t0, p4 ) = 1

W(p1, t0) = 2 W(t1, p3 ) = 1

W(p2, t0) = 2 W(t1, p5 ) = 1

W(p3, t0) = 1

W(p4, t1) = 1

M0(p0 ) = 2 M0(p3 ) = 1

M0(p1 ) = 2 M0(p4 ) = 0

M0(p2 ) = 3 M0(p5 ) = 0

ou simplesmente M0 (P) = [2, 2, 3, 1, 0, 0]

Page 11: 5_Redes de Petri

Redes Lugar/Transição

N = (P, T, I, O, M0)P = {p0, ⋅⋅⋅, pn}, conjunto finito e não vazio de lugares T = {t0, ⋅⋅⋅, tm}, conjunto finito e não vazio transições I: T→ P ∞, conjunto de entrada 

O: T→ P∞, conjunto de saída

M0: P→ N, marcação inicial 

P∩ T = ∅ e P∪T ≠ ∅

11

Page 12: 5_Redes de Petri

P = {p0, p1, p2, p3, p4, p5, p6}

T = {t0, t1, t2, t3, t4, t5}

M0 = [1, 0, 0, 1, 0, 0, 1]

Matrizes I e 0

12

0  0  1  0  0  01  0  0  0  0  00  1  1  0  0  0

O =  0  0  0  0  0  10  0  0  1  0  00  0  0  0  1  00  1  0  0  0  1

t0 t3

t2

t1 t4

t41  0  0  0  0  00  1  0  0  0  00  0  1  0  0  0

I =  0  0  0  1  0  00  0  0  0  1  00  0  0  0  0  11  0  0  1  0  0

p0

p1

p2

p3

p4

p5

p6

Page 13: 5_Redes de Petri

Regra de disparo (ocorrência)

13

t0 t3

t2

t1 t4

t4

p0

p1

p2

p3

p4

p5

p6

(M(p0) = 1) ≥ (w(p0,t0) = 1)

M’(p1) = M(p1) + w(t0,p1) ‐ w(p1,t0)1     =      0     +        1       ‐ 0

M’(p0) = M(p0) ‐ w(p0,t0) + w(t0,p0)0     =      1     ‐ 1       +       0

1. A transição tj está habilitada sse∀ pi ∈ P, M(pi) ≥ w(pi, tj)

2. Uma transição habilitada pode ou não ocorrer

3. Se a transição tj ocorrer, então:∀ pi ∈ I(tj) ∧ ∀ ps ∈ 0(tj)• M’(pi) = M(pi) ‐ w(pi,tj) + w(tj,pi)

• M’(ps) = M(ps) + w(tj,ps) ‐ w(ps,tj)

Page 14: 5_Redes de Petri

Redes de Petri

Transição sorvedouro Transição fonte

14

t0

p0 t0

p0t0

p0 t0

p0

Antes daocorrência

Depois daocorrência

Antes daocorrência

Depois daocorrência

Page 15: 5_Redes de Petri

Rede de Petri pura

Uma Rede de Petri R=(P,T,I,O,) é pura se e somente se:I(pj,ti) × O(pj,ti) = ∅,

∀ ti∈T, ∀pj∈P

Não há auto‐laços

15

Caso haja: adiciona‐se um par (transição e lugar) sem função (dummy) para elimina‐lo

p1

p0

t0

p2

P2’

t1

par semfunção

p1

p0

t0 p2

Auto‐laço

Page 16: 5_Redes de Petri

Modelos básicos

16

Seqüenciamento

Distribuição

Junção

Escolha

Page 17: 5_Redes de Petri

Conflito estrutural

N = (P,T,I,O), t1, t2 ∈ T estão em conflito estrutural sse ∃ p ∈ P tal que I(p,t1) × I(p,t2) ≠ 0

17

t1 t2

p

Page 18: 5_Redes de Petri

Conflito efetivoN=(P,T,I,O,M0), se t1, t2 ∈ T estão em conflito efetivo para M se estão em conflito estrutual e M[t1>, M[t2> e M(p) < I(p,t1) + I(p,t2)

18

t1 t2

p

Page 19: 5_Redes de Petri

Confusão

Simétrica Assimétrica

19

t0 t2t1

p0 p1

t0

t2

t1

p0 p1

p2

t0 e t2 são concorrentes e estão em conflito com t1.  A ocorrência de t1 impossibilita o ocorrência de t0 e t2

t0 e t2 são concorrentes, mas se t2 ocorre primeiro, t0 e t1 estarão em conflito efetivo

Page 20: 5_Redes de Petri

Controle de fluxo

Computação simples

20

Seqüenciamento

Page 21: 5_Redes de Petri

função

Chamada de função

21

Page 22: 5_Redes de Petri

Processos paralelos

22

M0

M2 M3

M5

M1

M4

M0

M5

M1

M4

s0={t0}

s1={t1,t2}

s2={t3}

Grafo de alcançabilidade Grafo de passos

p0

p1

p3

p5

p4

p2

t0

t1

t3

t2

t0

t2

t2

t1

t1

t3

Page 23: 5_Redes de Petri

Exclusão mútua

23

t0 t3

t2

t1 t4

t5

p0

p1

p2

p3

p4

p5

p6

Page 24: 5_Redes de Petri

Computação por fluxo de dados

24

a t0

b

a

a t3 a=0

t2 a≠0

t4 (a‐b)/a t5 2(a‐b)/a

t1a‐b

Page 25: 5_Redes de Petri

Comunicação

Síncrona Assíncrona

25

t0

p0

p2

p1

t0

p0

P`1

p4

t2

p2

p3

Page 26: 5_Redes de Petri

Comunicação síncrona com reconhecimento

26

t0

p0

p1

p6

t2

p3

p4

t1

p2

t3

p5

p7

Page 27: 5_Redes de Petri

buffer

ConsumidorProdutor

Produtor/Consumidor (buffer ilimitado)

27

t0

p0

p1 p4

t2

p2

p3

t1 t3

produziuum item

pronto paraconsumir

pronto paraproduzir

consumiuum item

Page 28: 5_Redes de Petri

contador(c=3)

buffer

ConsumidorProdutor

Produtor/Consumidor (buffer limitado)

28

t0

p0

p1

p4

t2

p2

p3

t1 t3

produziuum item

pronto paraconsumir

pronto paraproduzir

consumiuum item

p5

desabilitada(não produz)

Page 29: 5_Redes de Petri

Jantar dos filósofos

garfo 1garfo 2

comendo

Decartes

pensando

garfo 3

comendo

pensando

Aristótelescomendo

pensando

Demócrito

Page 30: 5_Redes de Petri

Abordagem de modelagem

Top‐downRefinamento

Botton‐upComposição

HíbridaRefinamento e Composição

30

Page 31: 5_Redes de Petri

Refinamento

31

p0

p1

p2 p6

p3

p5

p4

p423

p421

p424

p422

t424

t422 t423

t421

t2

t3 p42

p41

t41

t42

t5

t4

t1

t0

Page 32: 5_Redes de Petri

Composição

32

p0

p1

p6

p3

p5

t3

t5

t4

t1

t0

p0

p2

p5

p4

t2

t3

t0

Fusão

Sincronização

p2

Page 33: 5_Redes de Petri

Propriedades

Análise: baseada em algorítmos que não objetivam a verificação de uma determinada propriedade. Ao contrário, são algorítmos mais genéricos que fornecem informações sobre diversas propriedades e seus resultados podem ser utlizados como base para algorítmos de verificação. 

Mesmo que a resposta seja sim ou não, não há prioridade de um sim sobre o nãoTambém são usadas para responder questões do tipo: Quais são os conjuntos de lugares cujo somatório de marcas permanece constante?

33

Page 34: 5_Redes de Petri

Propriedades

Comportamentais

Estruturais

34

Page 35: 5_Redes de Petri

Propriedades comportamentais

Alcançabilidade (Reachability)Indica a possibilidade de se atingir uma determinada marcação pelo ocorrência de um número finito de transições, a partir de uma marcação inicial

Marcação alcançávelSeja Mi[tj>Mk e Mk[th>Ml então Mi[tj th>Ml. Por recorrência designamos a ocorrência de uma seqüência σ ∈ T* por M[σ>M’. Dizemos que M’ é alcançável a partir de M. O conjunto de todas as possíveis marcações alcançáveis de  a partir de M0 na Rede (N, M0) é denotado por 

R(N,M0)={M’ ∈ℵm| M0[σ >M’}, m = #P

35

Page 36: 5_Redes de Petri

Alcançabilidade

36

p0

t4

t3t1

t0

p1

p2

t2 p3

M’=[0,0,0,1] é acessível a partir de M0?

M0=[1,0,0,0]

M1=[0,1,0,0]

M2=[0,0,1,0]

M3=[0,0,0,1]Sim, pela ocorrência de δ’= t0t1t3

t3

t1

t0

Page 37: 5_Redes de Petri

Alcançabilidade

37

p0

t4

t3t1

t0

p1

p2

t2 p3

M’=[0,0,0,1] é acessível a partir de M0?

M0=[1,0,0,0]

M2=[0,0,1,0]

M3=[0,0,0,1]

Sim, pela ocorrência de δ’= t0t1t3 ou de δ’’= t2t3

t3

t2

Page 38: 5_Redes de Petri

ImpasseDefine a impossibilidade da ocorrência de qualquer transição da rede

38

p0

p1

p2

p3

p4

p5

p6

Impasse

t3

t1

t0

t4

t5t2p7

Page 39: 5_Redes de Petri

Grafo de alcançabilidade

Seja uma Rede  de Petri marcada (N,M0)

R(N,M0)=(V,A) define o grafo de alcançabilidade (Reachability Graph)

V é o conjunto de vértices definido pelo conjunto de marcações alcançáveis

A ⊆ V×T×V é uma relação definindo associações entre marcações alcaçáveis

39

Page 40: 5_Redes de Petri

Grafo de alcançabilidade

40

t0 t3

t2

t1 t4

t5

p0

p1

p2

p3

p4

p5

p6

M0

M5M1

M6

M4

M2

M3 M7

t2

t4M0 = [1001001]M1 = [0101000]M2 = [0011001]M3 = [0010100]M4 = [0010011]M5 = [1000100]M6 = [1000011]M7 = [0100010]

t0 t3

t1 t4

t5

t0t5

t1 t2t5

t2

t3

R(N,M0) = {M0, M1, M2, M3,M4, M5, M6, M7}

Page 41: 5_Redes de Petri

Vivacidade

Transição potencialmente disparávelUma transição tj é potencialmente disparável em uma dada marcação M0 se:

∃M’ ∈ R(N,M0) | M’[tj>

Rede vivaUma Rede (N,M0) é dita viva se:∃ σ ∈ T* | ti ∈ σ, M’[σ >, ∀M’ ∈ R(M0), ∀ti ∈ T

41

Page 42: 5_Redes de Petri

Vivacidade

Vivacidade é mais forte do que ausência de impasses

42

p0M0

M1

M2

M3

p1 p2

p3 p4

t0

t1

t2 t4

t3

t0

t1 t4

t3

Sem impassesNão viva

Page 43: 5_Redes de Petri

Vivacidade

Vivacidade é muito restritiva e computacionalmente cara para provarUma transição t pode ser classificada em níveis de vivacidade

N0‐viva (morta): se  σ ∈ L(R,M0) | t ∈ σ, ou seja,  M ∈ R(M0) | M[t>N1‐viva (potencialmente disparável): se t pode ocorrer pelo menos uma vez em alguma seqüência de disparo σ ∈ L(R,M0)N2‐viva: se dado qualquer inteiro positivo k, t pode ocorrer pelo menos k vezes em alguma seqüência σ ∈ L(R,M0)N3‐viva: se t aparece um número infinito de vezes em alguma seqüência σ ∈ L(R,M0)N4‐viva ou simplesmente viva: se t é N1‐viva ∀M ∈ R(N,M0)

43

Page 44: 5_Redes de Petri

Cobertura

Cobertura de uma marcação: seja a marcação M’ em uma Rede (N,M0). M’ é dita coberta se:

∃M’’∈ R(N,M0) | M’’(pi)≥M’(pi) ∀pi ∈ P

44

Page 45: 5_Redes de Petri

Recorrência e reversibilidade

Reversibilidade: inicialmente uma Rede é dita reversível se para cada marcação Mi no conjunto das marcações acessíveis a marcação inicial pode ser novamente alcançada

Estado recorrente: seja uma marcação Mk ∈R(N,M0). Mk é denominado um estado recorrente se Mi [>Mk, ∀Mi ∈ R(N,M0)Reversibilidade: uma Rede (N,M0) é reversível se ∃Mk , tal que Mi  [> Mk, ∀Mi ∈ R(N,M0)

45

Page 46: 5_Redes de Petri

Reversibilidade

46

t0

t1

t2

t3

p0

p1

p2

p3

Reversível

Page 47: 5_Redes de Petri

Reversibilidade

47

t0

t1t2

t3

p0

p1

p2 p3

Reversível

t4

Page 48: 5_Redes de Petri

Reversibilidade

48

Irreversível

t0 p4

t1

t2

p0

p1

p2

p3

t3

Page 49: 5_Redes de Petri

Persistência

Uma Rede é dita persistente se para qualquer par de transições t1 e t2 a ocorrência de uma não desabilita a outra

Seja uma Rede (N,M0). N é dita persistente se para todo par (t1,t2) ∈ T2 | ∃Mk [t1> e Mk [t2> ⇒Mk [ti>M’,  M’[t2> e vice‐versa. Onde  Mk, M’∈ R(N,M0)

49

Page 50: 5_Redes de Petri

PersistênciaTodo grafo‐marcado é persistente. Nem toda Rede persistente é uma grafo‐marcado

50

Persistentes

Grafo marcado Não é grafo marcado

t0

p0

p1

t1

p3

p2

p4

t2

t3

t0

p0

p1

t1

p3

p2

p4

t2

t3

Page 51: 5_Redes de Petri

Conservação

Está relacionada ao somatório de marcas a medida que as transições ocorrem

Rede Conservativa: seja uma Rede (N,M0) tal que M∈ R(N,M0) é uma marcação alcançável e W=(w1,...,wn), onde n=#P. N é dita conservativa se:

∑pi ∈ P Wi ×M(pi) = ∑pi ∈ P Wi ×M0(pi), ∀M∈ R(N,M0)

51

Page 52: 5_Redes de Petri

Conservação

52

t1 t3

t2 t4

p0

p2

p4

p1

p3

3

3

2

22

2

W1 = [3,0,1,0,0]W2 = [0,2,0,1,0]W3 = [0,0,4,3,6]W4 = [3,2,5,4,6]

∑pi∈P W4×m(pi) = 17, ∀pi ∈ P

(3 × 1) + (2 × 1) + (5 × 0) + (4 × 0) + (6 × 2) = 17(3 × 0) + (2 × 1) + (5 × 3) + (4 × 0) + (6 × 0) = 17(3 × 1) + (2 × 0) + (5 × 0) + (4 × 2) + (6 × 1) = 17

Page 53: 5_Redes de Petri

Propriedades estruturais

São propriedades inerentes a estrutura da Rede

Não dependem da marcação do modelo

Limitação Estrutural

Conservação Estrutural

Repetitividade

Consistência

53

Page 54: 5_Redes de Petri

Limitação estrutural

Seja uma Rede R = (P, T, I, O) e M0 uma marcação inicial. R é definida como estruturalmente limitada se R é limitada  para qualquer M0

TeoremaUma Rede R = (P, T, I, O) é estruturalmente limitada sse ∃W tal que W.C ≤ 0, onde |W| = #P e ωi > 0

54

Page 55: 5_Redes de Petri

Limitação estrutural

Seja uma Rede R = (P, T, I, O) e M0 uma marcação inicial. R é definida como estruturalmente limitada se R é limitada  para qualquer M0

55

2

Page 56: 5_Redes de Petri

Conservação estrutural

Seja uma Rede R = (P, T, I, O). R é definida como estruturalmente conservativa se R é conservativa  para qualquer M0

TeoremaUma Rede R = (P, T, I, O) é estruturalmente conservativa sse ∃W tal que W.C = 0, onde |W| = P e ωi > 0

56

Page 57: 5_Redes de Petri

Conservação estrutural

57

SP1 = {p0, p1}  SP2 = {p3, p4}

p0

p2

p4p1

p3

t0 t1 t2 t3

Rede não é estruturalmenteconservativa

Page 58: 5_Redes de Petri

Conservação estrutural parcial

Seja uma Rede R=(P,T,I,O) e M0 uma marcação inicial. R é definida como estruturalmente parcialmente conservativa se R tem algum componente conservativo  para qualquer M0

TeoremaUma Rede R = (P, T, I, O) é estruturalmente parcialmente conservativa sse ∃W≠0 tal que W.C = 0, onde |W| = P e ωi ≥ 0.

58

Page 59: 5_Redes de Petri

Conservação estrutural parcial

59

SP1 = {p0, p1}  SP2 = {p3, p4}

p0

p2

p4p1

p3

t0 t1 t2 t3

Rede é parcialmenteestruturalmente conservativa

Page 60: 5_Redes de Petri

Repetitividade

Seja uma Rede R = (P, T, I, O). R é definida como repetitiva se ∃M0 tal que M0[s>M’, onde M’≥M0e S>0, com si > 0

TeoremaUma Rede R = (P, T, I, O) é repetitiva sse ∃ S tal que C.S ≥ 0, onde |S| = T e si>0

60

Page 61: 5_Redes de Petri

Repetitividade

61

p0

t0

p1 p2

t1 t2

p3

t3

p4

t4

p0

t0

p1 p2

t2

p3

t1

t3

repetitiva

não repetitiva

Page 62: 5_Redes de Petri

Repetitividade parcial

Seja uma Rede R = (P,T,I,O). R é definida como parcialmente repetitiva se ∃M0 tal que M0 [s>M’, em que M’ ≥M0 e S ≠ 0, com si ≥ 0Teorema

Uma Rede R = (P,T,I,O) é repetitiva sse ∃ S≠0 tal que C.S ≥ 0, onde |S| = T e si ≥ 0

62

Page 63: 5_Redes de Petri

Repetitividade parcial

63

p0

t0

p1 p2

t2

p3

t1

t3

parcialmente repetitiva

Page 64: 5_Redes de Petri

Consistência

Seja uma Rede R = (P,T,I,O). R é definida como consistente se ∃M0 tal que M0 [s>M’, onde M’=M0 e S > 0, com si > 0 

TeoremaUma Rede R = (P,T,I,O) é consistente sse ∃ S tal que C.S = 0, onde |S| = T e si > 0

64

Page 65: 5_Redes de Petri

Consistência

65

p0

t0

p1 p2

t2

t3t1

consistente

Page 66: 5_Redes de Petri

Consistência parcial

Seja uma Rede R = (P,T,I,O). R é definida como parcialmente consistente se ∃M0 tal que M0[s>M’, onde M’= M0 e S ≠ 0, onde si ≥ 0Teorema

Uma Rede R = (P,T,I,O) é parcialmente consistente sse ∃ S ≠ 0 tal que C.S = 0, onde |S| = T e si ≥ 0

66

Page 67: 5_Redes de Petri

Consistência parcial

67

p0

t0

p1 p2

t2

p3

t1

t3

parcialmente consistente

Page 68: 5_Redes de Petri

Reduções

Análise por transformações

Análise de Redes grandes dimensões não é um problema trivial

Reduções são utilizadas para análise

68

Page 69: 5_Redes de Petri

Fusão de lugares em série

Seja N = (P,T,I,O,M0) é uma Rede e ti ∈T uma transição, O(pj) = I(pk)=[ti].  N pode ser transformada em N’=(P’,T’,I’,O’,M0’) pela fusão dos lugares pj e pk e eliminação de ti. O lugar pj/k∈ P’ representa os lugares fundidos, onde I(pj/k)= I(pj) e O(pj/k)=O(pk)

69

pj

ti

pk

pj

Page 70: 5_Redes de Petri

Fusão de transições em série

Seja N = (P,T,I,O,M0) é uma Rede e pi∈P uma transição, O(tj)=I(tk)=[pi].  N pode ser transformada em N’=(P’,T’,I’,O’,M0’) pela fusão das transições tj e tk e eliminação de pi. A transição tj/k ∈T’ representa as transições fundidas, onde I(tj/k)= I(tj) e O(tj/k)=O(tk)

70

tj

pi

tk

tj/k

Page 71: 5_Redes de Petri

Fusão de lugares em paralelo

Seja N=(P,T,I,O,M0) é uma Rede e pi,ph∈P lugares, I(pi)=I(ph)=[tj] e O(pi)=O(ph)=[tk]. N pode ser transformada em N’=(P’,T’,I’,O’,M0’) pela fusão dos lugares pi e ph. O lugar pi/h∈P’ representa os lugares fundidos, onde I(pi/h)= I(pi)= I(ph)= e O(pi)=O(ph)

71

tj

pi

tk

ph

tj

pj/h

tk

Page 72: 5_Redes de Petri

Fusão de transições em paralelo

Seja N=(P,T,I,O,M0) é uma Rede e ti,th∈T  transições, I(ti)= I(th)=[pj] e O(ti)= O(th)=[pk]. N pode ser transformada em N’=(P’,T’,I’,O’,M’0) pela fusão das transições ti e th. A transição ti/h∈T’ representa as transições fundidas, onde I(ti/h)=I(ti)=I(th) e O(ti/h)=O(ti)=O(th)

72

pj

tj/k

pk

pj

ti

pk

th

Page 73: 5_Redes de Petri

Eliminação de auto‐laços

Seja N=(P,T,I,O,M0) uma Rede e ei ∈ P∪T  um elemento. Se ei ∈ P, M(ei)≥#O(ei). Se I(ei)=O(ei) então N pode ser transformada em N’=(P’,T’,I’,O’,M’0) pela eliminação de ei

73

ti pj pj

tjtjpi

Page 74: 5_Redes de Petri

Extensões às redes de Petri

Extensões para considerar tempo

Extensões para aumentar o poder de modelagem

Outras

74

Page 75: 5_Redes de Petri

Redes temporizadas

75

Extensõestemporizadas

Token‐timed Transition‐timed Place‐timed

Stochastic PN Time PN Timed PN

Page 76: 5_Redes de Petri

Redes de alto nível

As redes Predicado/Transição foram as primeiras redes de alto nível (Pr/T‐nets)

As PrT‐nets foram desenvolvidas por HartmannGenrich e Kurt Lautenbach, 1979

76

Page 77: 5_Redes de Petri

Redes Lugar/Transição

77

Prod

Envia

Enviaprodutor

ProdEnvia

Enviaprodutor

Rec

RecCons

Rec

Rec

Cons

consumidor

consumidor

Page 78: 5_Redes de Petri

Estrutura da rede repetida

78

Prod

Envia

Enviaprodutor

ProdEnvia

Enviaprodutor

Rec

RecCons

Rec

Rec

Cons

consumidor

consumidor

Page 79: 5_Redes de Petri

Redes Predicado/Transição

79

produtor consumidor

Prod Envia Rec Cons

p p

pp

c c

cc

(p,c) (p,c)

D={azul,laranja,verde,vermelho}var c,p: D

Cada ficha carrega um valor de dadosÉ colorida!!!

Possíveis corres para as fichasD, D×D, D×D×D, etc.

Page 80: 5_Redes de Petri

Redes de Petri de alto nível

A definição das redes Pr/T foi o primeiro passo em direção às redes de alto‐nível como são conhecidas hoje

Fichas podem ser distinguidas umas das outras e portanto são ditas coloridas

Transições podem ocorrer de diversas maneiras dependendo da cor das fichas de entrada disponíveis

Expressões de arcos e guardas podem ser utilizadas para especificar  condições para habilitação e os efeitos das ocorrências

80

Page 81: 5_Redes de Petri

Redes de Petri Coloridas (CPN)

81

produtor consumidor

Prod Envia Rec Cons

p p

pp

c c

cc

(p,c) (p,c)

colset Prod = {vermelho, azul}colset Cons = {verde, rosa}colset pacotes = product Prod * Cons

Prod

Prod Cons

Cons

Pacote

Especificação mais precisa das cores das fichas

var p : Prodvar c : Cons

Page 82: 5_Redes de Petri

Conjuntos de Cores (Tipos)

Tipos de dados (colour sets) são utilizados para especificar diferentes tipos de fichas que podem estar nos diferentes lugaresTipos podem ser arbitrariamente complexos:

Atômicos (inteiros, cadeias de caracteres, binários e enumerações)Estruturados (produtos, registros, uniões, listas, e subconjuntos)

O uso de tipos permite construir descrições mais legíveis utilizados mnemônicos para nomes de tipos, como:

PROD, CONS, pacotesPodemos também obter descrições mais “corretas”

Verificação automática de tipos para expressões de arcos

82

Page 83: 5_Redes de Petri

Descrições Hierárquicas (módulos)

83

produtor consumidor

Prod Envia Rec Cons

p p

pp

c c

cc

(p,c) (p,c)Prod

Prod Cons

Cons

Pacote

Page 84: 5_Redes de Petri

HSconsumidor

Visão abstrata

84

HS produtor Buffer

pacotes

Transição deSubstituição

Refere‐se à sub‐rede(módulo)

Interface(socket place)

Usado paratrocar fichas entre

as sub‐redes

Page 85: 5_Redes de Petri

Módulo produtor

85

produtor

BufferProd Envia

p p

pp

(p,c)Prod

Prod

Pacote

Out

InterfacePorta de saída

Usado paraexportar fichaspara o restoda rede

Page 86: 5_Redes de Petri

Módulo consumidor

86

consumidor

Buffer

Pacote

In

InterfacePorta de entrada

Usado paraimportar fichas

do restoda rede

Rec Cons

c c

cc

(p,c)

Cons

Cons

Page 87: 5_Redes de Petri

Descrições hierárquicas

Módulos são utilizados para estruturas descrições grandes e complexas

Módulos permitem esconder detalhes que não devem ser considerados em um determinado nível de abstração

Módulos possuem interfaces bem definidas, que consiste de lugares socket e port, através dos quais módulos trocam fichas com o ambiente

Módulos podem ser reusados

87

Page 88: 5_Redes de Petri

Célula de manufatura

88

Rota iRota j

Pi

Pj

máquina 1

máquina 2

máquina 3

robô 1

robô 2robô 3

Depósito deentrada da

célula

Depósito desaída dacélula

Depósito deentrada da

máquina

Depósito desaída damáquina

Recurso deprodução da

máquina

Page 89: 5_Redes de Petri

Abordagem estruturada

89

Page 90: 5_Redes de Petri

Transporte entre células

90

Page 91: 5_Redes de Petri

Transporte dentro das células

91

Page 92: 5_Redes de Petri

Recursos das máquinas

92

Page 93: 5_Redes de Petri

Quatro células

93

Transporte entre células

Transporte dentro das células

Recursos de produção

Fazendo a fusãode lugares etransições

Nem todos osarcos estãoRepresentados!

E no caso deexistirem maiscélulas?

Page 94: 5_Redes de Petri

“Modelo” CPN

94

Page 95: 5_Redes de Petri

Mais informações sobre CP‐nets

http://www.daimi.au.dk/CPnets/

Introdução às CP‐nets, incluindo exemplos detalhados

Manuais dos conjuntos de ferramentas Design/CPN e CPN Tools

Um lista com mais de 50 aplicações industriais

Detalhes sobre os três livros sobre CPN

95

Page 96: 5_Redes de Petri

O que mais?

Outras extensões:Redes de Petri nebulosas

Redes de Petri orientadas a objetos

Redes de Petri algébricas

http://www.daimi.au.dk/PetriNets/

Análise algébrica e estruturalInvariantes

Equação de estados

96