Rede de Petri

Uma rede de Petri ou rede de transição é uma das várias representações matemáticas para sistemas distribuídos discretos. Como uma linguagem de modelagem, ela define graficamente a estrutura de um sistema distribuído como um grafo direcionado com comentários. Possui nós de posição, nós de transição, e arcos direcionados conectando posições com transições. Redes de Petri foram inventadas em agosto de 1939 por Carl Adam Petri quando ele tinha 13 anos. Vinte e três (23) anos depois, ele documentou o trabalho como parte de sua tese de doutorado.

A qualquer momento durante a execução de uma rede de Petri, cada posição pode armazenar um ou mais tokens. Diferente de sistemas mais tradicionais de processamento de dados, que podem processar somente um único fluxo de tokens entrantes, as transições de redes de Petri podem consumir e mostrar tokens de múltiplos lugares. Uma transição só pode agir nos tokens se o número requisitado de tokens aparecer em cada posição de entrada.

Transições agem em tokens de entrada por um processo denominado disparo. Quando uma transição é disparada, ela consome os tokens de suas posições de entrada, realiza alguma tarefa de processamento, e realoca um número específico de tokens nas suas posições de saída. Isso é feito atomicamente. Como disparos são não determinísticos, redes de Petri são muito utilizadas para modelar comportamento concorrente em sistemas distribuídos.

Definição formal

Rede de Petri de exemplo

Uma rede de Petri $(S,T,F,M_{0},W,K)$ é dada por:

• $S$, um conjunto de posições.
• $T$, um conjunto de transições.
• $F$, um conjunto de arcos também chamados de relações de fluxo. Ele é sujeito à restrição de que nenhum arco conecta duas posições ou transições, ou mais formalmente: $F\subseteq (S\times T)\cup (T\times S)$.
• $M_{0}:S\to \mathbb {N}$ conhecido como marco inicial, no qual para cada posição $s\in S$, existem $n\in \mathbb {N}$ tokens.
• $W:F\to \mathbb {N^{+}}$ conhecido como um conjunto de pesos de arco, relaciona para cada arco $f\in F$ um $n\in \mathbb {N^{+}}$ denotando quantos tokens são consumidos de uma posição por uma transição, ou alternativamente, quantos tokens são produzidos por uma transição e colocados em cada posição.
• $K:S\to \mathbb {N^{+}}$ conhecido como restrições de capacidade, relaciona para cada posição $s\in S$ um número positivo $n\in \mathbb {N^{+}}$ denotando o número máximo de tokens que podem ocupar aquela posição.

Uma variedade de outras definições formais existem. Essa definição é para uma rede posição-transição. Muitas das outras definições não incluem os pesos de arco e as restrições de capacidade.

Atualmente as Redes de Petri são ferramentas importantes para controle de sistemas e eventos discretos que possuem infinitas variáveis de nivel lógico limitado. São importantes ferramentas para a Automação Industrial.

Básico de redes de Petri

Uma rede de Petri consiste em posições, transições e arcos direcionados. Arcos interligam posições e transições, não podendo conectar posições e posições ou transições e transições. As posições de entrada de uma transição são aquelas as quais um arco se destina. As posições de saída são aquelas das quais um arco se origina.

Posições podem conter qualquer número de tokens. Transições podem ser disparadas, isto é, executadas: quando uma transição é disparada, ela consome um token de cada uma das suas posições de entrada, e produz um token em cada uma das suas posições de saída. Uma transição é habilitada quando ela pode ser disparada, isto é, quando existem tokens em cada posição de entrada.

A execução de uma rede de Petri é não-determinística. Isso significa que múltiplas transições podem ser habilitadas ao mesmo tempo (cada uma pode ser disparada) e que nenhuma transição deve ser obrigatoriamente executada em determinado momento.

Básico de propriedades matemáticas

O estado de uma rede de Petri é representado por um vetor M, no qual o primeiro valor do vetor é a quantidade de tokens na primeira posição da rede, o segundo é a quantidade de tokens na segunda posição, e assim por diante. Tal representação descreve completamente o estado de uma rede de Petri.

Uma lista de transição de estados, ${\vec {\sigma }}=\langle M_{i_{0}}t_{i_{1}}M_{i_{1}}\ldots t_{i_{n}}M_{i_{n}}\rangle$, que pode ser simplificada em ${\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle$ é chamada uma sequência de disparo se cada transição satisfaz o critério de disparo, isto é, existem tokens suficientes na entrada de cada transição. Nesse caso, a lista de transição de estados de $\langle M_{i_{0}}M_{i_{1}}\ldots M_{i_{n}}\rangle$ é chamada a trajetória, e $M_{i_{n}}$ é chamado alcançável a partir de $M_{i_{0}}$ através da sequência de disparos de ${\vec {\sigma }}$. Matematicamente: $M_{i_{0}}[{\vec {\sigma }}>M_{i_{n}}$. Todas as sequências de disparo que pode ser atingidas em uma rede $N$ com estado inicial $M_{0}$ são denotadas como $L(N,M_{0})$.

A matriz de transição de estados $W^{-}$ é grande $|T|$ por $|S|$, e representa a quantidade de tokens passados por cada transição de cada posição. Similarmente, $W^{+}$ representa a quantidade de tokens dados por cada transição para cada posição. A soma dos dois, $W=W^{-}+W^{-}$, pode ser utilizada para calcular a equação mencinada acima de $M_{i_{0}}[{\vec {\sigma }}>M_{i_{n}}$. Ela agora pode ser escrita simplesmente como $M_{0}-M_{n}=W^{T}\cdot \sigma$, no qual $\sigma$ é um vetor de quantas vezes cada transição foi disparada na sequência. Note que somente porque a equação pode ser satisfeita não significa que ela pode utilizada; para isso deve haver tokens suficientes para cada transição ser disparada, isto é, somente com a equação não é suficiente dizer que o estado $M_{n}$ pode ser atingido a partir do estado $M_{0}$.

Todos os estados que podem ser atingidos em uma rede $N$ com estado inicial $M_{0}$ são denotados como $R(N,M_{0})$. Surge o problema de alcaçabilidade: é verdadeiro que $M_{w}\in R(N,M_{0})$? No qual $M_{w}$ é, por exemplo, um estado inválido tal qual um elevador se movendo enquanto a porta está aberta.

A alcançabilidade dos estados pode ser representada pelo grafo de alcançabilidade no qual os destinos de um grafo direcionado representam estados (por exemplo M), e transições de arcos entre dois dos tais estados. O grafo é construído como a seguir: o estado inicial $M_{0}$ é definido, e todos as possibilidades de transição são exploradas a partir desse estado, depois a partir os estados resultantes da primeira iteração, e assim por diante.

Enquanto a alcançabilidade parece ser uma boa ferramenta para encontrar estados errôneos, o grafo construído possui estados demais para problemas práticos. Por essas razões, a lógica linear temporal com o método de tableau é geralmente utilizado para provar que tais estados não podem ser alcançados. Essa lógica usa a técnica de semi-decisão para encontrar se realmente um estado pode ser alcançado, ao procurar um conjunto de condições necessárias para o estado ser alcançado e provando que tais condições não podem ser satisfeitas.

Atividade

Uma transição t de uma rede de Petri ($N,M_{0}$) está

• $L_{0}$ viva, ou morta, Sse ela não pode ser disparada, isto é, não está em nenhum ${\vec {\sigma }}\in L(N,M_{0})$
• $L_{1}$ viva Sse ela pode ser possivelmente disparada, isto é, está em uma sequência de disparo ${\vec {\sigma }}$ na qual ${\vec {\sigma }}\in L(N,M_{0})$
• $L_{2}$ viva Sse para qualquer número k inteiro positivo, t pode ser disparado pelo menos k vezes em uma sequência de disparo ${\vec {\sigma }}$ na qual ${\vec {\sigma }}\in L(N,M_{0})$
• $L_{3}$ viva Sse existe uma sequência de disparo ${\vec {\sigma }}\in L(N,M_{0})$ na qual t é disparada infinitamente.
• $L_{4}$ viva, ou viva, Sse em qualquer estado possível m ($\forall M\in R(N,M_{0})$) t é $L_{1}$ viva.

Note que se uma transição é $L_{3}$ viva, ela é automaticamente $L_{0}$,$L_{1}$ e $L_{2}$ da mesma maneira.

Uma rede de Petri é $L_{k}$ viva Sse toda transição pertencente é $L_{k}$ viva.

Limitações

Existem redes de Petri nas quais as posições são limitadas em um número máximo de tokens. Nesse caso, a limitação é uma propriedade inerente. Apesar disso, redes de Petri podem ser definidas sem limitações como uma propriedade estrutural. Uma rede de Petri limitada não estruturada é k-limitada se não existe estado possível no qual alguma posição contém mais que k tokens. Uma rede de Petri é segura se ela é 1-limitada.

Limitações de certas posições em uma rede inerentemente limitada podem ser feitas em uma rede inerentemente não-limitada ao utilizar uma transformada de posição, no qual uma nova posição (chamada contra-posição) é criada, e todas as transições que levam x tokens na posição original levam x tokens para a contra-posição. O número de tokens em $M_{0}$ agora deve satisfazer a equação $place+counter-place=boundedness$. Assim, aplicar uma transformada de posição para todas as posições em uma rede limitada, e restringindo o estado inicial $M_{0}$ para satisfazer a equação acima, uma rede limitada pode facilmente ser transformada em uma rede não-limitada. Desta maneira qualquer análise usada em uma rede não-limitada pode ser utilizada em redes limitadas. A recíproca não é verdadeira.

Extensões

Existem várias extensões para redes de Petri. Algumas delas são completamente compatíveis com o modelo tradicional (por exemplo redes de Petri coloridas), algumas adicionam propriedades que não podem ser definidas no modelo tradicional (por exemplo redes de Petri temporizadas). Se elas podem ser definidas no modelo tradicional, não são realmente extensões, e sim maneiras mais convenientes de demonstrar a mesma coisa, de forma que podem ser transformadas com fórmulas matemáticas para o modelo tradicional, sem perda de informação. Extensões que não podem ser transformadas para o modelo tradicional são muitas vezes poderosas, mas geralmente não possuem ferramentas matemáticas suficientes para análise como no modelo tradicional de redes de Petri.

O termo redes de Petri de alto-nível é utilizado por vários formalismos de redes de Petri que estendem o formalismo posição/transição. Isso inclui redes de Petri coloridas, redes de Petri hierárquicas, e outras extensões como segue:

• Em uma rede de Petri tradicional, tokens são indistinguíveis. Em uma rede de Petri colorida, cada token possui um valor. Em várias ferramentas para redes de Petri coloridas, os valores dos tokens são tipados, e podem ser testados e manipulados usando uma linguagem de programação funcional. Uma derivação de redes de Petri coloridas são as redes de Petri bem formadas, nas quais os arcos e expressões de guarda são restritas para tornar a rede mais fácil de ser analisada.

• Outra extensão popular para redes de Petri é a hierarquia: hierarquia na forma de diferentes visões suportando níveis de refinamento e abstração, assim como estudado por Fehling. Outra forma de hirarquia é encontrada nas chamadas redes de Petri Objeto ou Sistemas Objeto, no qual uma rede de Petri pode conter outra rede de Petri como token, introduzindo o conceito de redes de Petri aninhadas que se comunicam ao sincronizar transições entre diferentes níveis.

• Um Sistema de Adição de Vetor com Estados (Vector Addition System with States - VASS) pode ser visto como uma generalização de uma rede de Petri. Considerado um autômato finito no qual cada transição é denominada por uma transição da rede. A rede de Petri é então sincronizada com o autômato finito, isto é, uma transição no autômato é feita no mesmo momento que a mesma transição na rede de Petri. É somente possível utilizar uma transição no autômato se a transição correspondente na rede de Petri está habilitada, e é somente possível disparar uma transição na rede de Petri se existe uma transição no mesmo estado no autômato.

• Redes de Petri Prioritizadas adicionam prioridades para as transições, de forma que uma transição não pode ser disparada se uma transição de prioridade maior está habilitada. Desta forma, transições estão em grupos de prioridade, e, por exemplo, um grupo de prioridade 3 só pode disparar se todas as transições estão desabilitadas nos grupos 1 e 2. Mesmo em um grupo de prioridade, disparos ainda assim são não-determinísticos.

• A propriedade não determinística é bem útil, pois permite ao usuário abstrair um grande número de propriedades (dependendo da finalidade da rede). Em certos casos, entretanto, existe também a necessidade de modelar também temporizações. Para esses casos são utilizadas redes de Petri temporizadas, no qual existem transições que são temporizadas, e possivelmente transições não temporizadas (nesse caso, transições não temporizadas são prioritárias em relação as temporizadas). Desta forma, a propriedade de tempo também pode ser modelada, não somente a estrutura. Uma derivação de redes de Petri temporizadas são as redes de Petri estocásticas, que adicionam tempos não-determinísticos através de aleatoriedade ajustável nas transições. A distribuição exponencial é utilizada para cronometrar essas redes. Nesse caso, o grafo de alcançabilidade dessas redes pode ser usado como uma Cadeia de Markov.

Existem várias outras extensões para redes de Petri, entretanto, é importante saber que ao adicionar complexidade nas redes ao adicionar propriedades, se torna mais difícil utilizar ferramentas tradicionais para calcular certas propriedades da rede. Por essa razão, é uma boa idéia utilizar a rede mais simples possível para uma tarefa dada.

Teoria de rede de Petri (Universidade Federal de Alagoas - 2014)

As propriedades teóricas de redes de Petri vêm sendo muito estudadas.

Uma situação em uma rede de Petri é alcançável se, iniciando de uma situação inicial, uma sequência de transições disparadas podem atingir tal situação. Uma rede de Petri é limitada se existe um limite ao número de tokens nas suas situações alcançáveis.

Principais tipos de redes de Petri

Existem seis tipos principais de redes de Petri:

• Máquina de estado - cada transição possui um arco de entrada, e um arco de saída. Isso significa que não pode existir concorrência, mas pode haver conflito (por exemplo, para onde o token deve ir a partir de uma posição? Para uma das transições ou outra?). Matematicamente: $\forall t\in T:|t\bullet |=|\bullet t|=1$.

• Grafo marcado - cada posição possui um arco de entrada e um arco de saída. Isso significa que não pode existir conflito, mas pode haver concorrência. Matematicamente: $\forall p\in P:|p\bullet |=|\bullet p|=1$

• Livre escolha - um arco ou é o único arco de saída da posição, ou é o único arco de entrada numa transição. Isso significa que pode haver ou concorrência ou conflito. Matematicamente: $\forall p\in P:(|p\bullet |\leq 1)\vee (\bullet (p\bullet )=\{p\})$

• Livre escolha estendida - uma rede de Petri que pode ser transformada em uma Livre escolha.

• Escolha assimétrica - concorrência e conflito (em outros termos, confusão). Matematicamente: $\forall p_{1},p_{2}\in P:(p_{1}\bullet \cap p_{2}\bullet \neq 0)\to [(p_{1}\bullet \subseteq p_{2}\bullet )\vee (p_{2}\subseteq p_{1}\bullet )]$

• Rede de Petri - confusão é permitida.

Áreas de aplicação

• Desenvolvimento de software
• Análise de dados
• Programação concorrente
• Diagnose
• Sistema flexível de manufatura

Ver também

• Máquina de estados finita não determinística
• Teoria dos Grafos

Ligações externas

• Petri Nets World (em inglês)
• Petri Net Markup Language (em inglês)
• exchangeable Routing Language (em inglês)
• Citations from CiteSeer (em inglês)