Embed Size (px)
Citation preview
• Publicado em 1962, por Carl Adam Petri
• Uma rede de Petri (RP) pode ser interpretada como um grafo direcionado bipartido, mais um elemento inicial, denominado marcação inicial.
• As RP são usadas para a modelagem e controle dos sistemas de produção, chamados também de SISTEMAS FLEXIVEIS DE MANUFATURA (SFM)
2
Redes de Petri
3
Redes de Petri: Aplicação em sistemas de produção
Concepção do Sistema
Modelagem do Sistema
Análise
Sistema Implementado
Supervisor
Monitoração
Fase de Concepção
Fase de Implementação
• A teoria de RP para modelagem e controle de sistemas de produção, trata de resolver o crescimento exponencial de espaço de estados de sistemas quando abordados com a teoria de autômatos finitos.
• As RPs apresentam vantagens em sistemas que apresentam: Concorrência, Sincronismo e Assincronismo, Conflito, Exclusão
Mutua, Sequenciamento de Eventos e Bloqueios.
Permitem especificar o supervisor diretamente do modelo do sistema
Permite analisar as propriedades de bloqueio e limitação do modelo do sistema
Simula os eventos discretos diretamente do modelo
Fornece as informações do estado atual do sistema permitindo a monitoração em tempo real.
4
Redes de Petri
• Os elementos de uma Rede de Petri são:
Lugares ou Posições
Transições
Arcos
5
Redes de Petri
Lugares
Lugares
Transição Arcos
• São elementos passivos, eles podem armazenar, mas não podem transformar informação
• Representam:
Condições
Recursos
Informações
Banco de Dados
6
1. Lugares
• São elementos ativos na Rede de Petri, e podem transformar informações mas nunca armazenar
• As transições representam: – Ações
– Atividades
– Transformações
– Eventos
7
2. Transições
3. Arcos
• Os nós de uma Rede de Petri são conectados por arcos rotulados com pesos (inteiros positivos). Caso não se indique o peso do arco então o valor é unitário.
• Um lugar P é entrada para uma transição t se existe um arco direcionado conectando o lugar para a transição, nesse caso o lugar é um LUGAR DE ENTRADA.
8
Definição: LUGAR DE ENTRADA
Definição: LUGAR DE SAÍDA
• Um lugar P é saída para uma transição t se existe um arco direcionado conectando a transição para o lugar, nesse caso o lugar é um LUGAR DE SAÍDA.
P t
P t
• As marcas ou fichas são atribuídas a cada lugar P um número k , inteiro positivo, de elementos denominados fichas.
• As fichas são utilizadas para marcar os lugares e determinar o ESTADO em que se encontra o sistema.
• O comportamento dinâmico do sistema modelado pela estrutura da rede de Petri pode ser caracterizado pelo movimento de fichas pelos lugares, quando a rede é executada.
9
Marcas ou Fichas
P K=3
• De modo a mover as fichas, as transições devem ser disparadas. Uma transição dever HABILITADA na marcação corrente para poder se disparar.
• Uma transição é dita HABILITADA se todos os lugares de entrada são marcados, por pelo menos, o mesmo número de fichas definido pelos pesos associados aos arcos conectando a esses lugares à transição.
10
Transições Habilitadas
Habilitado Desabilitado
P1
P2 P3
t1
Habilitado
P1
P2 P3
t1
P1
P2 P3
t1
• Observe-se, que quando a transição dispara, o número de fichas associados aos pesos dos arcos de entrada são removidos dos lugares de entrada, e depositados nos lugares de saída de acordo com os pesos associados aos arcos saindo da transição, conectando os lugares de saída,
11
Transições Habilitadas
A transição t1 dispara
P1
P2 P3
t1
2
1
1
P1
P2 P3
t1
2
1
1
• A estrutura de rede de Petri é uma 4-upla:
• Em que:
P={P1, P2,...,Pm} é um conjunto finito de lugares
T={t1, t2, ..., tn} é um conjunto finito de transições
F (PT)(TP) é um conjunto finito de arcos
W:F função de peso
P T = e P T
12
Definição: Estrutura de Rede de Petri
( , , , )N P T F W
• A marcação de uma rede de Petri é uma função:
• M(P) é a marcação do lugar P (número de marcar em P).
• A evolução da marcação simula o comportamento dinâmico de um sistema.
13
Definição: Marcação
:M P
• A rede de Petri é uma 5-upla
• Em que:
A rede de Petri é uma estrutura de rede mais uma marcação inicial
Os lugares de P são denominados de p-elementos
As transições de T são denominados de t-elementos
14
Definição: Rede de Petri
0( , )PN N M
Seja tT
t = { pP / (p,t) F } é o pre-conjunto de t (entradas de t)
t = { pP / (t,p) F } é o pós-conjunto de t (saídas de t)
Seja pP p = { tT / (t,p) F } é o pre-conjunto de p (entradas de p)
p = { tT / (p,t) F } é o pós-conjunto de p (saídas de p)
15
Definição: Rede de Petri
PN = {P, T, F, W, Mo}
P = {P1, P2, P3, P4, P5}
T = {t1, t2, t3, t4, t5}
F = {(p1,t1), (t1,p2), (t1,p3), (p2,t2), (t2,p4), (p4,t3)
(t3,p2), (p3,t4), (p4,t4), (t4,p5), (p5,t5), (t5,p1)}
W = { [(p1,t1),1], [(t1,p2),1], [(t1,p3),2], [(p2,t2),1]
[(t2,p4),1], [(p4,t3),1], [(t3,p2),1], [(p3,t4),2]
[(p4,t4),1], [(t4,p5),1], [(p5,t5),1], [(t5,p1),1]}
Mo = {(P1,1), (P2,0), (P3,0), (P4,0), (P5,0)}
A estrutura da rede de Petri é uma quadrupla N={P, T, F, W}
A rede de Petri PN é uma dupla (N, Mo), com Mo = {1, 0, 0, 0, 0}
16
Exemplo 1
17
Exemplo 1
A estrutura da rede de Petri é uma quadrupla N={P, T, F, W}, sem marcações iniciais
18
Exemplo 1
Rede de Petri PN, com marcação inicial
• Com a finalidade de simular a dinâmica de um sistema, a marcação (ou estado) de uma rede de Petri PN evolui de acordo a REGRA DE OCORRÊNCIA, cujos passos são
Pre-condição
Disparo
Pos-condição
19
Funcionamento de uma Rede de Petri
1. Pre-condição
Uma transição t esta habilitada se cada lugar de entrada p de t contém pelo menos w(p,t) fichas ou marcas, em que w(p,t) é o peso do arco de p para t
2. Disparo
Uma transição habilitada pode ou não ocorrer (disparar)
3. Pós-condição
Ao ocorrer t , então w(p,t) fichas são removidas de cada entrada p de t e w(t,p) fichas são acrescentadas a cada saída p de t , em que w(t,p) é o peso do arco de t para p .
20
Funcionamento de uma Rede de Petri
21
Exemplo 2
1
1 2
P1
P2 P3
t1
t1
1
1 2
P1
P2 P3
t1
3. Pos-condição
2. Disparo
1. Pre-condição: Transição habilitada
22
Exemplo 3
1
1
2
P3
P1 P2
t1
t1
3. Pos-condição
2. Disparo
1. Pre-condição: Transição habilitada
1
1
2
P3
P1 P2
t1
• Uma transição sem lugar de entrada é denominada transição FONTE.
• Esta transição sempre esta habilitada.
23
Definição: Transição Fonte
t1 P1
t2
P2
P3
Transição Fonte
• Uma transição sem lugar de saída é denominada transição SORVEDOURO.
• O acionamento de uma transição sorvedouro apenas consome fichas.
24
Definição: Transição Sorvedouro
P1 t1 t2 P2
Transição Sorvedouro
• AUTO-LAÇO é um par formado por um lugar p e uma transição t tal que p é ao mesmo tempo entrada e saída de t
25
Definição: Auto-laço
P1 t1 P2
(t1,P2) é um auto-laço
• É uma rede de Petri PN que não contém auto-laços.
26
Definição: Rede de Petri Pura
Definição: Rede de Petri Ordinaria
• É uma rede de Petri PN em que todos os arcos têm pesos unitários.
