Redes de Petri

UNIVERSIDADE DO ESTADO DE SANTA CATARINA

DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO

TECNOLOGIA EM SISTEMAS DE INFORMAÇÃO

REDES DE PETRI

FERNANDO ALVES MICHALAK

GUSTAVO RICARDO BASTISTA

PROFESSOR ORIENTADOR
MESTRE VINICIUS DA CUNHA MARTINS BORGES

ENGENHARIA DE SOFTWARE

Joinville

2007

Sumário

Sumário................................................................................................................................... 2

Introdução............................................................................................................................... 4

História.................................................................................................................................... 5

Conceito.................................................................................................................................. 6

Definição Formal.................................................................................................................... 7

Propriedades das Redes de Petri............................................................................................ 8

Conservação.................................................................................................................... 8

Reiniciabilidade................................................................................................................ 9

Reversibilidade................................................................................................................ 9

Repetitividade................................................................................................................. 9

Consistência.................................................................................................................... 9

Vivacidade....................................................................................................................... 9

Limitação....................................................................................................................... 10

Alcançabilidade.............................................................................................................. 10

Cobertura...................................................................................................................... 10

Persistência................................................................................................................... 10

Justiça............................................................................................................................ 10

Elementos Gráficos............................................................................................................... 11

Redes de Petri e a Representação do Tempo........................................................................ 12

Rede de Petri Temporizada............................................................................................ 12

Rede de Petri Temporal.................................................................................................. 13

Rede de Petri Estocástica................................................................................................ 14

Outras extensões não baseadas em tempo............................................................................ 15

Redes de Petri Hierárquicas............................................................................................ 15

Redes de Petri com Prioridade........................................................................................ 16

Vector Addition System with States (VASS)..................................................................... 16

Rede de Petri Colorida.................................................................................................... 16

Redes de Petri Predicado-Transição................................................................................ 17

Áreas de Aplicação............................................................................................................... 18

Análise de Dados e Diagnose.......................................................................................... 18

Desenvolvimento de Software....................................................................................... 18

Método formal........................................................................................................... 18

Sistemas Distribuídos..................................................................................................... 19

Características e Vantagens das Redes de Petri................................................................... 19

Introdução

Este trabalho tem por objetivo apresentar ao leitor o conceito de Redes de Petri, a história, definição formal, propriedades, os elementos gráficos, extensões baseadas em tempo e os demais tipos de extensões e por fim as áreas de aplicação.
História

Redes de Petri (ou simplesmente RdP) foram criadas a partir tese de doutorado de Carl Adam Petri, intitulada Kommunication mit Automaten (Comunicação com Autômatos), apresentada à Universidade de Bonn em 1962. Desde o princípio, RdP objetivaram a modelagem de sistemas com componentes concorrentes.

Segundo Heuser, as primeiras aplicações de RdP aconteceram em 1968, no projeto norte-americano Information System Theory, da A.D.R. (Applied DataResearch, Inc.). Muito da teoria inicial, da notação e da representação de RdP foi desenvolvido neste projeto e foi publicado em seu relatório final. Este trabalho ressaltou como RDP poderiam ser aplicadas na análise e na modelagem de sistemas com componentes concorrentes.

A década de setenta marcou o desenvolvimento da teoria de RdP e a expansão de seu campo de aplicação. No início daquela década, o trabalho de Petri chamou a atenção de membros do Projeto MAC, do MIT (Massachusetts Institute of Technology). O Grupo de Estruturas Computacionais, deste projeto, sob a direção do Prof. Jack B. Dennis, foi a origem de consideráveis pesquisas e publicações sobre RdP, envolvendo relatórios e teses de doutorado. Duas conferências importantes foram organizadas pelo grupo, quais sejam: a “Conferência sobre Sistemas Concorrentes e Computação Paralela”, em Woods Hole (Projeto MAC, 1970) e a “Conferência sobre Redes de Petri e Métodos Relacionados”, no MIT, em 1975. A conferência realizada em 1975 no MIT foi, vale ressaltar, a primeira vez que o nome “Rede de Petri” foi oficialmente utilizado para se referir ao formalismo proposto por Carl Adam Petri treze anos antes, na Alemanha. Os resultados destes e de outros esforços no desenvolvimento da teoria de RdP estão registrados em inúmeros artigos e em três livros principais: um destes livros foi escrito pelo Prof. Wolfgang Reisig, que foi orientado do Prof. Petri, e representa a linha de pensamento mais diretamente ligada a ele; outro livro foi escrito por diversos autores franceses, liderados pelo Prof. G. W. Brams, e representa, por assim dizer, a linha de pensamento européia menos ligada ao Prof. Petri; e o terceiro livro foi escrito pelo Prof. James Lyle Peterson e representa a linha de pensamento norte-americana.

Em relação às aplicações, RdP atingiu áreas como a modelagem de componentes de hardware, controle de processos, linguagens de programação, sistemas distribuídos e protocolos de comunicação.

Ainda na década de setenta, surgiram três tipos de RdP capazes de modelar características temporais determinísticas, quais sejam, as RdP temporizadas de Ramchandani, de Merlin e de Sifakis.

As aplicações de RdP aumentaram consideravelmente na década de oitenta, com o surgimento das chamadas redes de Petri de alto nível, como por exemplo, as numéricas, as predicado/transição e as coloridas. Em meados da década de oitenta surgiram também extensões de RdP estocásticas. Tais inovações acrescentaram uma grande força descritiva ao processo de modelagem, pelo uso de marcas com identidade e, conseqüentemente, do uso de conjuntos de marcas na representação da dinâmica dos sistemas modelados, bem como pela possibilidade de se associar taxas de ocorrência não determinísticas aos eventos dos sistemas modelados. Desta forma, as RdP atingiram outras áreas, como automação de escritórios, bancos de dados, inteligência artificial e sistemas de informação de maneira geral. No final da década de oitenta era publicado um artigo seminal sobre RdP, pelo Prof. Tadao Murata. Embora este artigo trate primordialmente das redes de baixo nível, ele é um dos artigos mais referenciados sobre o assunto ainda nos dias de hoje.

Na década de noventa as RdP tiveram como seu principal representante a segunda versão das RdP Coloridas, desenvolvidas pelo Prof. Kurt Helmer

Jensen, da Universidade de Aarhus, na Dinamarca. Além de trabalharem com marcas diferenciáveis, tais redes apresentam tratamento de aspectos temporais e permite a representação de tipos de dados abstratos, um diferencial que as outras extensões existentes no final da década de oitenta e início da de noventa não apresentavam. Foi nesta década também que surgiram alguns livros sobre RdP, em português.

Outra preocupação era com a diversidade de extensões de RdP que estavam sendo propostas. A exemplo do que ocorreu com as linguagens de programação nas décadas de sessenta e setenta, cada grupo que sentia necessidade de determinada característica estava propondo sua extensão de RdP, mas por conveniências locais de implementação, estas extensões não se conversavam e estavam formando uma verdadeira Torre de Babel. Esta situação motivou, em meados da década de noventa, o início de um esforço para a padronização das redes de alto nível, bem como de uma sintaxe de transferência que pudesse ser comum a todas as RdP. Esta proposta foi encabeçada pelo Prof. Jonathan Billington e levada à ISO, International Standards Organization, em 1995 que a acolheu e atribuiu-lhe a designação de padrão ISO/IEC-15909, tendo sido dividido em três partes, quais sejam: a parte 1, designada por High-level Petri Nets – Concepts, Definitions and Graphical Notation; a parte 2, designada por High-level Petri Nets – Transfer Format; e a parte 3, designada por High-level Petri Nets – Extensions. Estas três partes iniciaram sua tramitação pelo longo processo de aprovação de padrões ISO em momentos diferentes e, conseqüentemente, estão em fases diferentes de padronização. A ISO/IEC- 15909-1 foi ratificada como padrão em julho de 2003, tendo seu texto recebido a última atualização em maio de 2002. A ISO/IEC-15909-2 e a ISO/IEC-15909-3 iniciaram suas tramitações, respectivamente, em junho de 2003 e janeiro de 2004. Atualmente estão tramitando no Comitê Técnico em estágios diferentes, quando ainda podem receber alterações mais importantes aos seus textos.

Espera-se que em janeiro de 2006 a tramitação destas duas partes seja sincronizada, produzindo um padrão internacional completo até o final de 2006.

Informações atualizadas sobre estes e outros assuntos relativos a redes de Petri podem ser obtidas em vários sítios na internet, sendo o principal deles o hospedado pela Universidade de Aarhus ( http://www.daimi.au.dk/PetriNets ).

Conceito

Redes de Petri constitui um formalismo matemático capaz de representar sistemas digitais em um nível de abstração bastante alto. Seu aspecto estrutural equivale a um grafo direcionado e bipartido composto por três elementos básicos, quais sejam, estados, ações e arcos. Os estados e as ações correspondem aos vértices do grafo, e os arcos às suas arestas. Os subconjuntos de estados e de ações são disjuntos, motivo pelo qual se diz que o grafo subjacente é bipartido. Cada um dos elementos do subconjunto de arcos, por sua vez, tem por origem um elemento do subconjunto de estados e por destino um elemento do subconjunto de ações, ou vice-versa. Por esta razão, o grafo é dito direcionado. Os estados de uma RdP representam a parte estática do sistema modelado, isto é, cada um dos possíveis estados elementares pelos quais o sistema pode passar em alguma fase de seu funcionamento. As ações de uma RdP representam a parte dinâmica do sistema modelado, ou seja, cada uma das operações que o sistema pode executar no decorrer de sua existência. Os arcos de uma RdP representam a relação de fluxo entre estados e ações.

Cada estado da RdP que serve de condição prévia para a ocorrência de determinada ação deve estar ligada a ela por um arco dirigido do estado para a ação. Cada estado da RdP resultante da ocorrência de uma ação é, por sua vez, uma condição decorrente da operação (ou conjunto de operações) associada à ação e a ela deve estar ligado por um arco dirigido com origem na ação e destino no estado. Fora esta visão estrutural, o comportamento de uma RdP pode ser analisado, para que se possa entender o funcionamento do sistema que se estiver modelando. Para se identificar quais as condições da RdP estão satisfeitas em cada instante do seu funcionamento, utilizam-se marcas nos estados correspondentes. A distribuição das marcas pelos estados da RdP em cada instante é dita marcação da rede.

Graficamente, representam-se os estados por elipses, as ações por retângulos, os arcos por setas e as marcas por pontos. As elipses, freqüentemente degeneram para círculos e os retângulos para quadrados ou para simples traços. Via de regra estas mudanças não influi no comportamento da rede ou no significado do objeto gráfico. Contudo, em alguns poucos casos a representação de ações por retângulos ou por traços podem significar comportamentos diferentes, em particular, em algumas extensões estocásticas. Os arcos, nestes casos, também podem ter suas terminações alteradas e, em vez de terminarem em setas, como é usual, podem terminar em pequenos círculos, representando uma mudança no seu significado. As ações de uma RdP são potencialmente paralelas e assíncronas, isto é, uma vez satisfeitas as condições para a sua ocorrência, elas podem acontecer em qualquer instante independentemente umas das outras. Para que uma ação ocorra, todas as suas pré-condições devem estar satisfeitas e todas as suas pós-condições devem comportar o resultado de sua execução. A conseqüência da ocorrência de uma ação é a eliminação de um subconjunto de marcas existentes nos seus estados de entrada e a criação de outro subconjunto de marcas nos seus estados de saída. Note-se que há mais de uma classe de RdP e muitas extensões em cada uma delas. Para cada extensão de RdP a regra geral de ocorrência de uma ação, enunciada no parágrafo anterior, pode sofrer algumas adaptações, restringindo-a ou relaxando-a.

Definição Formal

Formalmente, a rede de Petri é dada por uma quíntupla, RP = (P, T, F, W, M0), em que (Murata, 1989):

• P = {p1, p2, …, pm} conjunto finito de lugares;

• T = {t1, t2, …, tm} conjunto finito de transições;

• F Í (P x T) È (T x P) conjunto de arcos;

• W : F {1, 2, 3, …} função de pesos;

• Mo : P ® {0,1, 2, 3, …} marcação inicial;

• P Ç T = Æ e P È T ¹ Æ.

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.

Propriedades das Redes de Petri

As propriedades das RdP podem ser divididas em dois grandes grupos, quais sejam: as propriedades estáticas (ou estruturais) e as propriedades dinâmicas (ou comportamentais).

As propriedades estáticas das RdP são aquelas que têm a ver com a estrutura da rede e que não se modificam no transcurso de seu funcionamento. Elas não dependem do estágio de execução em que a rede se encontra, sendo, portanto, independentes da marcação da rede.

As propriedades dinâmicas das RdP são aquelas que têm a ver com o seu comportamento e que se modificam durante o funcionamento. Elas são essencialmente dependentes do estágio de execução em que a rede se encontra e são, por conseguinte, dependentes da marcação da rede.

Conservação

A propriedade de conservação corresponde ao caso no qual o número total de marcas na rede não se modifica. Uma ação é dita conservativa se a soma dos arcos que a liga `as suas pré-condições for igual `a soma dos arcos que a liga `as suas pós-condições. Desta forma, quando a ação for executada, nenhum recurso ligado a ela será criado ou eliminado. Se todas as ações de uma RdP forem conservativas, diz-se que a rede é estritamente conservativa.

A propriedade de conservação estrita é bastante restritiva, contudo, há casos nos quais é possível se associar a cada arco da rede um peso (um fator multiplicador) de modo que para esta nova combinação o conjunto de marcas removido das pré-condições de cada ação passa a ser igual ao conjunto de marcas gerado após a execução da ação correspondente.

O que se passa a considerar agora é o somatório ponderado dos pesos dos arcos da rede. Se este somatório for constante, pode-se dizer que a RdP é conservativa em relação a esta distribuição de pesos. Note-se que cada um destes pesos deve ser um valor inteiro e positivo. Há ainda o caso em que não é possível encontrar um vetor de pesos tal que torne toda a RdP conservativa. Entretanto, pode-se encontrar um vetor de pesos que torne parte da rede conservativa. Esta situação pode ser encontrada tornando todos os elementos do vetor de pesos nulos, exceto aqueles correspondentes aos estados que se deseja considerar. Neste caso, diz-se que a rede é parcialmente conservativa, em relação ao vetor de pesos P.

Reiniciabilidade

Uma RdP é dita reiniciável se, para qualquer marcação alcançável, for possível voltar à marcação inicial.

Reversibilidade

Marcação de base (Home-marking; Marquage d’accueil) é uma marcação Mh, alcançável a partir da marcação inicial M0, tal que para toda a marcação Mi, também alcançável a partir de M0, haja uma seqüência de disparos que leve de Mi a Mh. Uma RdP é dita reversível se, existir uma marcação base, acessível de qualquer outra marcação do conjunto de alcançabilidade da rede.

Repetitividade

Uma RdP é repetitiva se existir uma seqüencia de disparos, associada a uma dada marcação, na qual todas as ações são executadas um número de vezes infinito. Se a seqüência existir, mas apenas algumas ações forem disparadas ilimitadamente, a rede é dita parcialmente repetitiva.

Consistência

Uma RdP é consistente se ao disparar uma seqüência de ações a partir de uma marcação inicial, for possível retornar a esta marcação executando, pelo menos uma vez, cada uma das ações da rede. é possível mostrar que uma rede é consistente se, e somente se, existir um vetor d, não nulo, tal que sua multiplicação pela matriz de incidência da RdP seja igual a zero, isto é, D • _ = 0.

Vivacidade

Uma RdP é dita viva se for possível executar todas as suas ações a partir de qualquer uma das marcações alcançáveis da rede. Esta propriedade é muito importante na análise de sistemas digitais, uma vez que, quando verificada, indica a inexistência de bloqueios no sistema modelado. Porém, a verificação da vivacidade irrestrita de uma RdP é, freqüentemente, muito cara. Por esta razão é possível relaxar esta propriedade, adotando se níveis de vivacidade.

Podemos então definir cinco níveis de vivacidade, como segue:

• Ação viva no nível 4 (N4) ou, simplesmente, viva: é aquela que pode ser executada pelo menos uma vez, em pelo menos uma seqüência de disparos, a partir de cada marcação pertencente ao conjunto de alcançabilidade A(R, M0).

• Ação viva no nível 3 (N3): é aquela que pode ser executada um número infinito de vezes em alguma seqüência de disparos possível a partir da marcação inicial S(R, M0).

• Ação viva no nível 2 (N2): é aquela que pode ser executada pelo menos k vezes em alguma seqüência de disparos S(R, M0), para um dado inteiro k > 1.

• Ação viva no nível 1 (N1): é aquela que pode ser executada pelo menos uma vez em alguma seqüência de disparos S(R, M0).

• Ação viva no nível 0 (N0), ou rede morta: é aquela que nunca puder ser executada em qualquer seqüência de disparos S(R, M0); isto é, se não existir marcação em A(R, M0) que habilite a ação em questão.

Uma RdP é dita viva no nível Ni se todas as suas ações forem vivas em um nível j3i.

Vivacidade no nível 4 é a mais abrangente e corresponde à vivacidade plena mencionada no início desta seção. Pode-se dizer que a vivacidade em um determinado nível implica a vivacidade nos níveis menos restritos, sendo o nível 4 o mais restrito e o nível 1 o menos restrito. Com certeza, esta propriedade não se aplica ao nível zero, pois, se a rede é viva em algum nível diferente de zero ela não é morta e vice-versa. Pode-se definir vivacidade estrita no nível i se determinada ação for viva neste nível, mas não em nível superior.

Limitação

Uma RdP é limitada se em cada lugar da rede, o número total de marcas nunca exceder a um inteiro k. Neste caso a rede é dita k-limitada. Se a rede for limitada ao inteiro 1, diz-se que a rede é segura. Uma RdP é estruturalmente limitada se for limitada para qualquer marcação inicial. Isto significa que deve existir um vetor de inteiros positivos com dimensão igual à cardinalidade do conjunto de estados da rede de tal sorte que o produto deste vetor de pesos (P) pela matriz de incidência (D) da rede seja menor ou igual a zero, isto é, P • D _ 0.

Alcançabilidade

Uma marcação é dita alcançável em uma RdP se existir uma seqüência finita de disparos que conduza a ela a partir da marcação inicial. Se todas as marcações alcançáveis forem decorrentes da inicial, a rede é dita alcançável.

Cobertura

Uma RdP é dita coberta se, para toda a marcação M’, alcançável a partir de Mo, existir outra marcação M”, maior ou igual a M’ e alcançável a partir de M’. M” é considerada maior ou igual a M’, se o número de marcas em cada lugar de M” for maior ou igual ao número de marcas do lugar correspondente em M’, para todos os lugares da rede (M00 _ M0 ! M00(li) _ M0(li), 8li 2 L).

Persistência

Uma RdP é dita persistente se havendo mais de uma ações habilitadas, em qualquer das marcações da rede, a ocorrência de uma delas não desabilita a ocorrência das demais.

Justiça

Uma RdP é dita justa se, para quaisquer duas ações, o número de vezes que uma é executada enquanto a outra não é executada é finito. Esta propriedade também é conhecida como justiça limitada. Se, por outro lado, uma dada seqüência de disparos s for finita ou se cada ação da rede aparecer nesta seqüência um número infinito de vezes, s é dita incondicionalmente justa. Uma RdP é dita incondicionalmente justa se todas as seqüências de disparo originárias em alguma marcação de A(R, M0) forem incondicionalmente justas.

Elementos Gráficos

Existe uma notação gráfica adequada para a representação dos elementos das redes de Petri. Esta notação determina que:

- os estados são representados por elipses;

- as ações são representadas por retângulos; e

- os elementos da relação de fluxo por setas.

Vale notar que tradicionalmente, em alguns modelos, estas figuras geométricas são degeneradas, sendo os estados representados por círculos e as ações por barras ou quadrados. No caso das redes lugar/transição, por exemplo, utilizam-se círculos e barras. Em outros casos, como algumas redes estocásticas, as ações podem ser representadas tanto por barras quanto por retângulos, para diferenciar ações com disparo imediato de ações com disparo temporizado.

Então, uma rede cuja representação algébrica é dada por:

R = (E, A, F)

E = {e1, e2, e3, e4, e5}

A = {a1, a2, a3, a4}

F = {(e1,a2), (e2,a2), (e3,a1), (e5,a4), (e4,a3), (a2,e3), (a3,e1), (a1,e2), (a4,e4), (a1,e5)}

é representada graficamente como mostra a figura abaixo.

Redes de Petri e a Representação do Tempo

As Redes de Petri permitem descrever a ordem em que determinados eventos acontecerão, dando plena visibilidade de qual evento precederá outro no tempo, o que faz com que o tempo seja utilizado de modo quantitativo. Com o objetivo de utilizar o tempo explicitamente nas Redes de Petri, vários trabalhos foram confeccionados, fazendo com que o tempo fosse associado diretamente à Rede de Petri, passando a fazer parte do controle ao invés de ser um dado. Trabalhos fundamentados nestes modelos são utilizados para avaliar o desempenho de sistemas representados por Redes de Petri. Existem duas grandes classes de modelo: Rede de Petri Temporal e Rede de Petri Temporizada, as quais serão vistas a seguir.

Rede de Petri Temporizada

A Rede de Petri Temporizada foi introduzida por Ramchandani, e consiste em associar o tempo aos lugares ou às transições, fazendo com que as marcas fiquem indisponíveis durante essa duração. Se um lugar representa uma atividade qualquer X, a associação de tempo a este lugar apenas trata de designar ? como tempo de duração dessa atividade.

Dessa forma, quando uma ficha chegar a este local, ela somente poderá sair deste ? instantes após a sua chegada. Este local, o qual chamaremos de p, pode se desdobrar em uma seqüência lugar-transição-lugar, como poderemos verificar na figura abaixo.

Esse desdobramento gera os seguintes componentes:

• p1 - lugar que corresponde à atividade sendo executada;

• t’ - transição que corresponde ao tempo transcorrido;

• p2 - lugar encarregado de realizar a sincronização com as demais atividades, se existirem, após o final da atividade X.

Dessa forma, quando a atividade X é disparada por t1, a ficha fica indisponível em p1 até que a atividade seja finalizada, não podendo sensibilizar t’. Quando a atividade acaba, t’ é sensibilizada e a ficha se torna disponível a t2 que pode ser sensibilizada e realizar outras eventuais atividades. A associação de tempo à transição é obtida associando-se a cada transição da rede ordinária uma duração de tiro, fazendo com que a ficha não fique disponível durante este tempo. Esta associação só possui sentido se a transição é interpretada como uma atividade e não como evento instantâneo. Com o intuito de verificarmos o funcionamento interno desta associação, podemos substituir uma transição por uma seqüência transição-lugar-transição, como podemos observar na figura abaixo.

Esse desdobramento nos gera os seguintes itens:

• t’ - transição que atua como evento instantâneo marcando o início da atividade;

• p’ - lugar que atua na memorização da atividade que estão em execução (duração);

• t - evento instantâneo que marca o fim da atividade.

Neste caso, quando a transição é disparada as fichas correspondentes ao peso do arcos são retiradas, fazendo com que estas fiquem não visíveis durante a execução da atividade. Quando a atividade for finalizada, as fichas são colocadas no lugar de saída (p2).

Rede de Petri Temporal

Foi introduzida por Merlin em seu trabalho de doutoramento e é obtida através da associação de um intervalo de duração de sensibilização a cada transição. A cada transição é associado um intervalo no formato (?mim, ?max) que determina o intervalo de sensibilização. Este deve ser maior que ?mim e menor que ?max. Diferentemente das Redes de Petri Temporizadas, durante a sensibilização de uma transição as fichas continuam visíveis às outras transições. Existem alguns casos em que as fichas devem ficar visíveis somente para certas transições em um dado momento. Um caso típico é o watchdog

No problema watchdog o lugar espera permite que o sistema esteja receptivo a chegada de uma ficha (evento) no lugar condição, o que causaria o disparo da transição fim1. Mas se este lugar não estiver marcado ao fim do tempo ?, um alarme é acionado pelo disparo da transição fim2. As duas formas de associar tempo na Rede de Petri Temporizada não permitem a correta representação deste problema, pois se associássemos um tempo de atividade ao lugar espera atrasaríamos o disparo de fim1 mesmo se lugar condição recebesse a ficha mais cedo, e se atribuíssemos um tempo à transição fim2 faríamos com que a ficha contida em espera fosse imediatamente reservada para esta transição, e após o tempo ?, o alarme seria disparado, mesmo que uma ficha houvesse chegado em condição. No entanto podemos dizer que o modelo de Rede de Petri Temporal é mais geral que o da Rede de Petri Temporizada, jáque permite descrever o problema do watchdog. Isso se faz possível porque durante todo o intervalo de tempo as fichas permanecem disponíveis a qualquer transição t, e, desta forma, podem ser utilizadas por transições em conflito como no problema do watchdog.

Rede de Petri Estocástica

As Redes de Petri Estocásticas são as redes em que as durações de sensibilização associadas às transições são definidas por distribuições geométricas e exponenciais, a fim de

poder construir um processo markoviano equivalente e assim analisar o comportamento da rede.

A partir de uma Rede de Petri Estocástica podemos construir uma cadeia de Markov. O fato de podermos construir uma cadeia de Markov a partir de uma Rede de Petri Estocástica permite realizarmos a análise da rede.

Outras extensões não baseadas em tempo

Quando utilizamos Redes de Petri Ordinárias para a representação de problemas complexos temos que optar por ou modelar o comportamento geral do sistema sem precisar a identidade de cada processo, mas somente seu número, ou modelar, individualmente, cada um dos processos que constituem o sistema e modelar a interação existente entre eles. Se optarmos pela primeira alternativa obterá uma descrição compacta que não os oferece todas as informações suficientes. Se optarmos pela segunda, o modelo pode se tornar pouco prático de se utilizar ou pelo seu grande tamanho ou pelo grande número de interações que apresenta. Logo, para representarmos problemas complexos em Redes de Petri necessitamos um modelo que nos permita dobrar a rede, isto é, agrupar mesmas estruturas em um único componente, mantendo o mesmo sistema através de uma forma mais compacta, e ainda necessitamos a possibilidade de diferenciarmos as fichas, fazendo com que estas possam transmitir uma informação.

Redes de Petri Hierárquicas

Outra extensão popular para as RdP é a Hierárquica. A hierarquia na forma de diferentes visões que suportam níveis de refinamento e abstração diferentes foi estudada por Fehling. Outra forma de hierarquia é encontrada na tão citada Rede de Petri a Objetos ou sistemas de objetos onde a rede pode conter Redes de Petri como marcações, induzindo a uma hierarquia aninhada que se comunica por sincronização de transições em diferentes níveis.

Redes de Petri com Prioridade

Redes de Petri com Prioridade adicionam prioridades às transições, onde uma transição não pode ser disparada, se existe outra transição com maior prioridade (está sensibilizada).

Portanto, transições são colocadas nos grupos de prioridades. Por exemplo, o grupo de prioridade 3 pode ser disparado se, e somente se, todas as transições estão desabilitadas nos grupos de prioridade 1 e 2. é importante lembrar que dentro de um mesmo grupo a escolha da transição que será disparada continua sendo não determinística.

Vector Addition System with States (VASS)

Um Vector Addition System with States (VASS) pode ser visto como uma generalização de uma RdP. Considere um autômato de estados finitos (AFD) onde cada transição é rotulada por uma transição de uma RdP. A RdP é então sincronizada com o AFD, por exemplo: a transição no autômato é dada ao mesmo tempo em que a transição correspondente na RdP. é possível apenas tomar uma transição no autômato se a transição correspondente na RdP está sensibilizada, e só é possível disparar uma transição na RdP se existe uma transição no AFD com o mesmo rótulo.

Rede de Petri Colorida

Neste tipo de rede, são atribuídas cores as fichas a fim de diferenciá-las. Por conseqüência, a cada lugar se associa o conjunto de cores das fichas que podem pertencer a este lugar.

A cada transição se associa o conjunto de cores que corresponde às diferentes maneiras de disparar uma transição. Nos casos mais simples, quando todos os processos possuem rigorosamente a mesma estrutura e são independentes uns dos outros, as cores são diretamente associadas aos processos, e o conjunto de cores dos lugares e das transições é idêntico. O conjunto de cores de uma transição indica as diferentes maneiras de como ela pode disparar. Cada cor de transição corresponde a uma das transições da rede ordinária equivalente. Em outras palavras, cada transição da rede ordinária que é dobrada numa transição da rede colorida, vai corresponder a uma cor do conjunto de cores desta última.

As etiquetas dos arcos em redes de Petri Coloridas não são mais números inteiros como nas redes ordinárias, mas funções que representam matrizes de inteiros. Para cada cor de uma transição é necessário descrever quais cores quais cores de fichas serão retiradas dos lugares de entrada e quais cores de fichas serão colocadas nos lugares de saída. A representação de uma rede colorida se dá principalmente por meio de notação matricial, o que a torna compacta. Embora isso gere melhora no campo visual, continua-se a tratar com a mesma complexidade do sistema original da rede de Petri ordinária.

Redes de Petri Predicado-Transição

Nas Redes de Petri Coloridas o poder de descrição é aumentado perante uma rede de Petri ordinária. No caso das redes predicado-transição, as transições de uma Rede de Petri Ordinárias são consideradas como regras num sistema de lógica proposicional, e o poder de descrição são aumentados substituindo por regras da lógica de primeira ordem. Assim, não somente a representação é mais concisa, mas o modelo permite estudar melhor as propriedades estruturais e comportamentos do sistema. Dessa forma, uma regra (transição) descreve uma família de eventos e não mais um evento. A família é definida pelo conjunto de substituições possíveis de variáveis por valores, como as do tipo:

se uma peça <x> e uma máquina <y>, fazer uma usinagem <u>

para o caso de um sistema de manufatura. As variáveis que se encontram entre os símbolos de < e > assumirão, respectivamente, valores no conjunto de constantes descrevendo as peças em espera, o conjunto de máquinas livres e o conjunto de operações que podem ser realizadas. Essas constantes possuem papel análogo ao das cores na Rede de Petri Colorida. Neste modelo, a transição dobrada é vista como um esquema que possui como instâncias todas as transições de uma rede ordinária que representam o mesmo evento. Neste modelo, ainda, os lugares da rede representam as relações dinâmicas do sistema, indicadas por predicados, motivo pelo qual o modelo é chamado predicado transição. As funções e relações da parte estática, ou mais precisamente, seus nomes, vão aparecer nas anotações. As anotações das condições e ações são expressões que resumem as sentenças afirmativas da linguagem natural. Os operadores (símbolos da função) e predicados (símbolos da relação) formam o vocabulário da linguagem.

Áreas de Aplicação

Análise de Dados e Diagnose

Um fato importante que se pode observar nos Sistemas de Manufatura Automatizados é que o comportamento das atividades possui uma natureza predominantemente discreta, como será visto posteriormente, onde os estados do sistema evoluem conforme a ocorrência de um ou mais eventos que podem ou não estarem mutuamente relacionados (Miyagi 1989). Estas características fazem com que os sistemas complexos sejam praticamente impossíveis de serem projetados, previamente analisados e implementados através de técnicas tradicionais de controle. As principais dificuldades estão relacionadas com a inadequação dos modelos para tratar sistemas concorrentes e assíncronos com alto grau de complexidade. Desta forma, necessita-se uma técnica de modelagem que possa ser útil para a representação das características de um Sistema Flexível de Manufatura capaz de contribuir para o planejamento e realização das atividades como: supervisão do sistema, diagnose e reparo de falhas no sistema, carga e descarga de pallets, monitoramento do sistema, preparação das máquinas e ferramentas, etc. Neste sentido as Redes de Petri são uma ferramenta de modelagem de eventos discretos capazes de representar com muita simplicidade atividades paralelas e/ou concorrentes assim como assíncronas, sendo essa a razão da sua importância na automação industrial.

Desenvolvimento de Software

Há uma década, vem se tentando encontrar um processo ou metodologia previsível e repetível que melhore a produtividade e qualidade. Alguns tentaram sintetizar e formalizar a tarefa aparentemente incontrolável de escrever um software. Outros aplicaram técnicas de gerenciamento de projeto na escrita de software. Sem o gerenciamento de projeto, projetos de software podem facilmente sofrer atraso ou estourar o orçamento. Como um grande número de projetos de software não atendem suas expectativas em termos de funcionalidades, custo, ou cronograma de entrega, o efetivo gerenciamento de projeto esta provando ser muito difícil.

Método formal

Os Métodos Formais são abordagens matemáticas para resolver problemas de software e hardware ao nível de requerimento, especificação e projetos. Exemplos de métodos formais incluem Método-B, Redes Petri, RAISE e VDM. Várias notações de especificação formal estão disponíveis, tais como a notação-Z. De forma mais genérica, a teoria do autômato pode ser usada para construir e validar o comportamento da aplicação para o projeto de um sistema de maquina de estado finito.

Maquinas de estado finito baseadas nestas metodologias permitiram especificar software executáveis e contornar a codificação convencional.

Sistemas Distribuídos

Um sistema distribuído é uma "coleção de computadores independentes que se apresenta ao usuário como um sistema único e consistente.

Assim, a computação distribuída consiste em adicionar o poder computacional de diversos computadores interligados por uma rede de computadores ou mais de um processador trabalhando em conjunto no mesmo computador, para processar colaborativamente determinada tarefa de forma coerente e transparente, ou seja, como se apenas um único e centralizado computador estivesse executando a tarefa. A união desses diversos computadores com o objetivo de compartilhar a execução de tarefas é conhecida como sistema distribuído.

Características e Vantagens das Redes de Petri

Destacam-se as seguintes características e vantagens desta técnica:

· Representar à dinâmica e a estrutura do sistema segundo o nível de detalhamento desejado.

· Identifica estados e ações de modo claro e explicito, facilitando com isto a monitoração do sistema em tempo real.

· Tem a capacidade para representar de forma natural as características dos SED (sincronização, assincronismo, concorrência, causalidade, conflito, compartilhamento de recursos, etc ).

· Associa elementos de diferentes significados numa mesma representação, ou segundo o propósito do modelo (avaliação de desempenho, implementação do controle, etc).

· Oferece um formalismo gráfico que permite a documentação e monitoração do sistema, facilitando assim o dialogo entre o projetista e as pessoas que participam no processo de projeto ou de analise do comportamento do sistema (projetista, operador, gerente, etc).

· Constitui-se como uma teoria muito bem fundamentada para a verificação de propriedades qualitativas.

· Possui uma semântica forma e precisa que permite que o mesmo modelo possa ser utilizado tanto para a analise de propriedades comportamentais (analise quantitativa e/ou qualitativa) e avaliação do desempenho, assim como para a construção de simuladores a eventos discretos e controladores (para implementar ou gerar códigos para controle de sistemas). Além de servir para verificar comportamentos indesejáveis como bloqueio limitação, etc.

· Incorpora conceitos de modelagem do tipo refinamento (“top down”) e do tipo composição modular (“bottom up”) através de técnicas como: modularização, reutilização, refinamento, etc.

Conclusão
Este trabalho nos apresentou de forma resumida os aspectos que constituem as Redes de Petri, o qual se apresentou como técnica eficaz para a documentação e controle de diversos problemas que necessitem de alto nível de modularidade.