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.
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.
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:
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.
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.
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.
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).
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:
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:
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.
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.
Ao
ser carregado, o programa entra na janela de edição. No segundo passo é feita a
leitura e compilação da rede "EXEMPLO.RDP".
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.
Este documento foi digitalizado e formatado a partir de um antigo manual
impresso.