ARP - Analisador/Simulador de Redes de Petri

Manual da versão 2.3 (dezembro de 1989)

Este software foi desenvolvido no Laboratório de Controle e Microinformática (LCMI) do Departamento de Engenharia Elétrica da Universidade Federal de Santa Catarina, entre 1985 a 1990.

índice 

Introdução

O Analisador / Simulador de Redes de Petri (ARP) é um programa para o auxílio ao projeto com redes de Petri, desenvolvido no LCMI/UFSC de 1985 a 1990, contando com várias ferramentas para redes de Petri ordinárias, com temporização e com temporização estendida.

O ARP foi construído em Pascal, de forma modular e permitindo uma inter- face com o usuário simples e de fácil aprendizado, utilizando textos e janelas. A modularidade do programa permite facilmente projetar e conectar novas ferra- mentas de análise ou tratamento de redes de Petri, razão pela qual o mesmo está em constante evolução. 

O programa roda sobre o sistema operacional DOS na versão 3.00 ou superior, em computadores compatíveis com o IBM-PC, com um mínimo de 256 Kbytes de memória disponível. E composto de dois arquivos: 

A carga do programa se faz a partir do sistema operacional, digitando-se o comando arp <enter>. A partir dai será apresentadas tela principal do analisador, com as diversas opções disponíveis, e o sistema entra na janela de edição. 

Os comandos são escolhidos pelas letras mais claras das opções do menu da janela ativa, de moldura mais clara que as demais. Para sair de uma janela, basta teclar a barra de espaço, ESC ou outra tecla não utilizada na janela. Os resultados se apresentam como textos na janela do editor, podendo ser completamente visualizados usando as teclas de setas. 

Edição de redes

A janela de edição concentra as funções encarregadas da manipulação dos arquivos que contém as redes, em disco. Um arquivo de rede é um arquivo ASCII normal, com extensão default "RDP", que contém a descrição de uma rede de Petri. Essa descrição é feita usando-se uma linguagem especifica para tal, que é detalhada adiante. Os comandos permitidos na janela de edição são os seguintes: 

Linguagem de Descrição

A linguagem de descrição de redes de Petri usada no ARP possui uma sintaxe semelhante à do Pascal, permitindo a identificação de lugares e transições por nomes quaisquer com até 20 caracteres. Os caracteres aceitos são: 

A..Z a..z 0..9 ! ? + - # @ ^ % 

A estrutura básica de um texto de descrição de rede é a seguinte:

REDE nome_da_rede; 
   declaração de constantes 
   declaração dos nodos (lugares e transições)
   declaração da estrutura (arcos)
FIM. 

Podem ser definidas constantes da seguinte forma: 

CONST
   Num_Vagas  = 7;
   Num_Envios = 10;
   Time_Out   = 45;

A declaração NODOS é dividida em duas partes: a declaração de transições e a de lugares, com um máximo de 150 nodos de cada tipo. A declaração de lugares faz-se da seguinte forma (o valor entre parênteses indica a marcação inicial dos lugares declarados, com default zero e máximo 254):

Robot_Parado, Torno_Operando  : LUGAR ; 
Robot_Ligado, Torno_em_Espera : LUGAR (1) ;
Pecas_Esperando               : LUGAR (Num_Vagas) ;

A declaração de transições é de forma similar. No caso de redes com temporização segundo o modelo de Merlin, podem ser definidos o Static Earliest Firing Time (SEFT) e o Static Latest Firing Time (SLFT), com default em [0,0]. Também pode ser definida a curva de densidade de probabilidade associada a esse intervalo, por default uniforme: 

Robot_Solta_Peca : TRANSICAO ; 
Inicia_Usinagem  : TRANSICAO [5,Time_Out] ;
Chegada_Peca     : TRANSICAO [0,5] EXPON (10) ;
Robot_Pega_Peca  : TRANSICAO [2,8] NORMAL (5); 

Nos intervalos são aceitos inteiros entre 0 e 32000, podendo ser constantes pré-definidas. As curvas de densidade de probabilidade (usadas pelo módulo de avaliação de desempenho) aceitas são: 

Observa-se que a definição das curvas não depende de valores absolutos mas apenas da razão entre os valores máximo e mínimo. Através da declaração estrutura são descritos os arcos que ligam as transições aos lugares e vice-versa. Sua forma geral é: 

transição: (lugares de entrada) , (lugares de saída) 

Essa estrutura deve ser repetida para cada transição da rede. Os nomes dos lugares são separados por vírgulas. No caso de arco com peso não-unitário temos: 

transíção: (..., peso * Lugar, ... )

onde o peso pode ser um valor numérico ou uma constante pré-definida, entre 0 e 254. 

O exemplo a seguir ilustra a linguagem descrita. A rede modela um sistema composto de um torno e um robô que o alimenta, carregando e descarregando peças de um armazém: 

Rede Exemplo_da_Linguagem;
 
Const 
  Pecas_Entrada = 2 ; { peças na entrada da máquina }
 
Nodos 
  { armazém de pecas }
  Armazem : Lugar (Pecas_Entrada) ;
 
  { nodos do robô que alimenta o torno } 
  Robo_Livre         : Lugar (1) ;
  Robo_Carregando,
  Robo_Descarregando : Lugar; 
  Pega_Peca_Nova     : Transicao [1,10] ;
  Solta_Peca_Pronta  : Transicao [3,5] ;
  Carrega_Torno, 
  Descarrega_Torno   : Transicao [5,15] Normal (5) ;
 
  { nodos do torno }
  Usinando     : Lugar; 
  Torno_Livre  : Lugar (1) ;
 
Estrutura { controle do robô }
  Pega_Peca_Nova    : (Armazem, Robo Livre), (Robo_Carregando);
  Carrega_Torno     : (Robo_Carregando,Torno_livre), (usinando, Robo_Livre) ;
  Descarrega_Torno  : (Usinando,Robo_Livre), (Robo Descarregando, Torno_Livre) ;
  Solta_Peca_Pronta : (Robo_Descarregando) , (Armazem, Robo_Livre); 
Fim. 

Enumeração de Estados

A enumeração de estados é uma análise baseada na procura de todos os estados alcançáveis pela rede, disparando suas transições. O algoritmo usado é basicamente o de Karp-Miller, com uma pequena modificação na determinação do crescimento de fichas nos lugares, que permite uma análise mais detalhada de redes com crescimento de fichas. A capacidade do programa depende da memória disponível. 

Para redes com temporização os estados são agrupados em classes de estados com características comuns. Cada classe de estado é composta por uma marcação e um domínio de disparo (conjunto das transições sensibilizadas, cada qual com seu respectivo intervalo dinâmico de disparo). 

Ao ser ativado este módulo mostra a marcação inicial a ser usada na enumeração, que pode ser alterada usando as teclas de setas e digitando os valores desejados (entre 0 e 254). Para sair dessa janela e começar a enumeração pressiona-se ESC. O programa então faz a enumeração de estados ou classes de estados e constrói os textos com os resultados. 

O texto das propriedades observadas informa as propriedades da rede pesquisadas sobre o grafo de estados gerado: 

O texto do grafo de estados acessíveis indica a estrutura de um grafo que representa todos os disparos de transições que levam de um estado a outro. Cada linha deste texto é da seguinte forma: 

E37: (t4 [3,7]: E51) (t9 [5]: E102) 

Isto significa que, a partir do estado E37 podemos disparar a transição t4 (entre 3 e 7 unidades de tempo, no caso de rede com temporização) levando a E51, ou a transição t9 em 5 unidades de tempo, levando a E102

O texto dos estados acessíveis indica o conteúdo (disposição das fichas na rede) de cada estado e o domínio de disparo das transições sensibilizadas nesse estado, caso a rede possua temporização. Cada linha deste texto é da seguinte forma: 

E37 : {p1, p2, 3*p3,  w*p4} 
  D : {ta, tb [3], tc[4,9]}

Isto indica que no estado E37 os lugares p1 e p2 possuem uma ficha, o lugar p3 tem 3 fichas e o lugar p4 tem infinitas fichas (detectou-se um crescimento do número de fichas nesse lugar). No domínio de disparo, ta tem disparo permitido em [0,0], tb em [3,3] e tc em [4,9] unidades de tempo. 

Análise de Invariantes

A análise de invariantes procura, através de cálculos sobre a matriz de incidência da rede, conjuntos de lugares ou transições com características especiais, como a conservação de fichas ou o funcionamento cíclico. 

Os invariantes lineares de lugar indicam as componentes conservativas da rede, ou seja, conjuntos de lugares da rede nos quais a soma ponderada do número de fichas seja constante para qualquer marcação alcançável. Todo vetor inteiro xn tal que Cmn x = 0 é um invariante linear de lugar, onde xi é a ponderação do i-ésimo lugar da rede na formação do invariante (Cmn é a matriz de incidência da rede de Petri, com m transições e n lugares).

Os invariantes lineares de transição indicam as componentes repetitivas estacionárias da rede, ou seja, conjuntos de transições que quando disparadas na ordem e freqüência adequada formam um ciclo, retomando no estado de partida. Todo vetor inteiro y, tal que ym Cmn = 0 é um invariante linear de transição, onde yi indica o numero de disparos da i-ésima transição para formar o ciclo (a ordem de disparo das transições não é diretamente calculável). Deve-se observar que os invariantes dependem somente das características estruturais da rede, e não de seu estado inicial. Portanto alguns invariantes de transição indicados podem não constar do grafo de estados acessíveis da rede, para o estado inicial definido.

O módulo implementado permite definir um conjunto de nodos obrigatórios ou proibidos, para a orientação da procura. A partir disso são fornecidos somente os invariantes que contenham os nodos obrigatórios e que não contenham os nodos proibidos indicados. Para a seleção dos nodos obrigatórios ou proibidos são usadas as teclas de setas, ENTER e ESC. 

Como resultado, o programa fornece a base linearmente independente dos invariantes encontrados e todos os invariantes positivos mínimos (que não sejam superposições de outros invariantes positivos), combinações lineares das linhas da base de invariantes. Também é efetuado um teste de cobertura sobre os invariantes encontra- dos e um teste de sub-redes, indicando quais invariantes são máquinas de estados ou grafos de eventos, conforme sua topologia:

Deve-se observar que este módulo ignora a informação temporal da rede, considerando somente sua topologia. portanto alguns invariantes de transição detectados podem não ser realizáveis, caso as restrições temporais o impeçam. 

Verificação de equivalência

A verificação por equivalência de linguagem permite observar em detalhe o comportamento de urna rede de Petri, enfocando a atenção em algumas'partes da rede e abstraindo as demais. Ela consiste em considerar um conjunto de transições da rede como sendo eventos "visíveis", sendo as demais considera- das invisíveis, e obter um autômato finito determinístico mínimo que indica o seqüenciamento entre os eventos considerados visíveis.

O usuário define quais transições da rede são visíveis (através das teclas de setas, ENTER e ESC) e o programa, a partir do grafo de estados acessíveis, fornece como resultado o autômato representando o seqüenciamento entre as transições visíveis e também os caminhos (seqüências de disparo) possíveis nesse autômato. Na descrição dos caminhos os símbolos "{" e "}" indicam repetição. Portanto um caminho descrito como "t1 {t3 t4}" significa "t1 t3 t4 t3 t4 ...". Também é permitida a entrada do autômato finito determinístico) que representa a especificação do usuário, para ser comparado com o autômato mínimo obtido da rede (a comparação entre os autômatos não está totalmente implementada). 

Simulação

O módulo de simulação permite acompanhar a evolução do funcionamento de uma rede, escolhendo as transições a disparar e observando o estado da rede e sua evolução, a qualquer instante. 

Na janela maior há um diagrama da trilha percorrida pela simulação até o momento. No lado esquerdo da trilha é indicado o nome de cada estado, se memorizado, ou sua profundidade em relação ao estado inicial. No lado direito é indicado o nome de cada transição disparada. 
Os números junto da trilha indicam o número de transições ainda não disparadas em cada estado. O estado atual é o da extremidade inferior da trilha.

Quando há bloqueio a trilha termina em uma barra horizontal. Quando o estado gerado por um disparo for duplicata de algum estado já percorrido, este é indicado por uma linha tracejada, e o simulador permanece no estado onde ocorreu o disparo.

O comandos disponíveis no simulador são: 

Avaliação de Desempenho

Este módulo trabalha com redes de Petri com temporização estendidas, que possuem uma função de densidade de probabilidade associada ao intervalo de disparo de cada transição. Para a avaliação de desempenho são possíveis duas abordagens: a orientada a estados e a orientada a eventos.

No modo orientação a estados é definido um estado (marcação) inicial e até 10 estados destino, sendo então realizados ciclos de simulação. Cada ciclo de simulação consiste no disparo das transições sensibilizadas em instantes aleatórios (sorteados de acordo com o intervalo de disparo e a curva de densidade de probabilidade de cada transição) até alcançar um destino, um bloqueio ou superar o número máximo de disparos fixado pelo usuário. Ao fim de cada ciclo são atualizados os contadores estatísticos e restaurada a marcação inicial. Os ciclos são repetidos até ser alcançada a precisão desejada ou ocorrer uma interrupção pelo usuário, pressionando uma tecla qualquer. 

No modo orientação a eventos são definidos um evento (transição) inicial e até 10 eventos destino. As transições são disparadas como na orientação a estados, sendo as medidas estatísticas efetuadas entre o disparo do evento inicial e o disparo de algum evento destino. Com isso pode-se medir o tempo médio entre eventos e a probabilidade de ocorrência de eventos. 

Durante a avaliação é mantida uma tela com alguns resultados obtidos até o momento, para dar ao usuário uma idéia dos valores finais e de sua convergência. 

O usuário tem como opções de entrada permitidas: 

Resulta da avaliação um texto contendo as seguintes medidas estatísticas efetuadas sobre a rede: 

Impressão de Resultados

O módulo de impressão de resultados permite transformar os dados em memória em uma listagem na impressora. A saída pode ser redirecionada pelo usuário para um arquivo em disco, onde serão concatenadas todas as saídas que lhe forem enviadas. O arquivo com listagens de saída leva a extensão default "LST". A seleção de resultados a imprimir é bastante simples, bastando pressionar as teclas correspondentes ao que se deseja imprimir. 

Roteiro Exemplo de Utilização

Abaixo estão indicados os procedimentos necessários para a utilização de cada um dos módulos do ARP, com uma rede dada como exemplo. Mesmo sendo simples o uso do programa, este roteiro pode ser necessário para um primeiro contato com o mesmo. A rede usada neste roteiro exemplo é a mesma usada para exemplificar a linguagem de descrição de redes neste manual. O primeiro passo do roteiro objetiva carregar o programa ARP no computador, tornando-o pronto para a utilização do usuário. 

Carregar o programa

  1. Inserir o disquete no driver desejado.
  2. Digitar "ARP" e após a tecla ENTER (RETURN). 

Ao ser carregado, o programa entra na janela de edição. No segundo passo é feita a leitura e compilação da rede "EXEMPLO.RDP". 

Carregar a rede

  1. Teclar "L" (leitura de rede).
  2. Digitar "EXEMPLO.RDP" e teclar ENTER.
  3. Teclar "C" e aguardar o fim da compilação. - Teclar duas vezes a barra de espaço.

Agora o programa está no menu principal, com uma rede já carregada. A partir daqui o usuário pode escolher que tipo de análise executar. Abaixo são definidos os passos necessários para cada análise, a partir do menu principal. 

Enumeração de Estados

  1. Teclar "N" (análise) e "E" (enumeração de estados).
  2. Alterar a marcação inicial, se desejar. As teclas de setas movem o cursor. As teclas numéricas e o backspace permitem a edição dos valores. Para terminar a edição pressionar ESC. Para este exemplo não altere nenhum valor.
  3. Aguardar o fim do processo de enumeração de estados.
  4. Ao final são mostradas as propriedades observadas. O texto pode ser movido usando-se as teclas de setas.
  5. Teclar ESC, ENTER ou ESPAÇO para retornar ao menu da enumeração, onde pode se escolher o que visualizar.
  6. Visualizar os resultados desejados.
  7. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal. 

Cálculo de Invariantes

  1. Teclar "N" (análise) e "L" (invariantes de lugar) ou "T" (invariantes de transição).
  2. Teclar "I" (iniciar calculo).
  3. Aguardar o fim do cálculo dos invariantes.
  4. Ao final são mostrados os resultados obtidos. O texto pode ser movido usando-se as teclas de setas.
  5. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal. 

Verificação

  1. Teclar "V" (verificação).
  2. Teclar "V" (eventos visíveis), e escolher, usando as teclas de setas e ENTER, as transições "Carrega Torno" e "Descarrega Torno". Ao final teclar ESC.
  3. Teclar "M" (marcação inicial) e, usando as teclas de setas e as numéricas, colocar 2 fichas no lugar "Robô Livre", simbolizando a existência de 2 robôs no sistema (manter a marcação dos demais lugares). Ao final teclar ESC.
  4. Teclar "i" para iniciar o processo de verificação. - Aguardar o final do processo de verificação.
  5. Ao final são mostrados os resultados obtidos. O texto pode ser movido usando-se as teclas de setas.
  6. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal. 

Avaliação de Desempenho 

  1. Teclar "D" (avaliação de desempenho). - Teclar "E" (orientação a estados).
  2. Teclar "D" (marcações destino) e entrar marcação destino 1, com 1 ficha em "Robô Carregando" e 1 ficha em "Usinando" (nenhuma ficha nos demais lugares). No final teclar ESC.
  3. Teclar "D" (marcações destino) e entrar marcação destino 2, com 1 ficha em "Armazém", 1 ficha em "Robô Descarregando" e 1 ficha em 'Torno-Livre" (nenhuma ficha nos demais lugares). Ao final teclar ESC.
  4. Teclar "i" para iniciar o processo de avaliação.
  5. Aguardar o andamento da avaliação. Desejando interrompê-la pressionar uma tecla qualquer. Caso contrário a avaliação termina ao alcançar a precisão desejada.
  6. Ao final são mostrados os resultados obtidos. O texto pode ser movido usando-se as teclas de setas.
  7. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal. 

Simulação

  1. Teclar "S" (simulação). 
  2. Teclar "G" e "E" para habilitar o armazenamento do registro de evolução da simulação. 
  3. Teclar "D" e disparar a transição "Pega Peça Nova", pressionando ENTER.
  4. Informar o instante de disparo da transição. 
  5. Disparar a transição "Carrega Torno", pressionando ENTER.
  6. Informar o instante de disparada transição. 
  7. Teclar ESC para sair do disparo de transições. 
  8. Teclar "M" e "M" para memorizar o estado atual. Digitar um nome qualquer e teclar ENTER.
  9. Teclar "V" e ENTER para visualizar o estado atual. Após visualizar teclar ESC, ENTER ou ESPAÇO para retornar ao menu de simulação.
  10. Teclar "F" para terminar a simulação.
  11. Ao final é mostrado o texto com a evolução da simulação, efetuada. O texto pode ser movido usando-se as teclas de setas.
  12. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal. 

Impressão de Resultados

  1. Teclar "i" (impressão).
  2. Se não houver impressora conectada ao micro, teclar "Q" e digitar o nome do arquivo onde serão gravados os resultados. O programa insiste na leitura do nome até o usuário digitar um nome válido.
  3. Pressionar as teclas correspondentes aos resultados que se deseja gravar ou imprimir. Para sair de uma janela teclar ESC, ENTER ou ESPAÇO.
  4. Teclar ESC, ENTER ou ESPAÇO até voltar ao menu principal.

Este documento foi digitalizado e formatado a partir de um antigo manual impresso.