Kursthemen
-
Modelagem e Design de Sistemas Discretos em Redes de Petri (2016)
As redes de Petri apareceram pela primeira vez na tese de doutorado de Karl Adam Petri em 1960, para representar a comunicação entre processos. Na figura acima a rede de Petri ao lado da foto representa o processo de visita às estações de trabalho (trata-se de uma linha de montagem de impressoras) para o recolhimento de peças e partes já montadas. Estes processos tipicamente lineares compartilham recursos (AGVs por exemplo), o que pode comprometer a eficiência dos processos.
As aplicações das redes de Petri se multiplicaram e, além das aplicações na manufatura e em processos de workflow, chegaram ao gerenciamento de sistemas de telefonia e mais tarde à modelagem de processos em redes de computadores. Mais recentemente estas aplicações atingiram a Engenharia de Software, a modelagem e análise de requisitos e finalmente se incorporaram de vez ao Design de Sistemas como formalismo padrão para sistemas discretos, ou, de modo geral para qualquer sistema dinâmico modelado segundo o paradigma de estado/transição. ampliaram sistematicamente o seu escopo de aplicação. Para aproximar as aplicações dos usuários não-acadêmicos várias extensões foram propostas, sempre inserindo interpretações e features próprios do nicho de aplicação (telefonia, redes, internet, workflow, etc.). O resultado foi uma profusão de modelos e propostas, todas igualmente usando o nome de redes de Petri.
Em 2004 um grupo de especialistas do mercado e da academia apresentou um formalismo de referência que viria a se tornar uma norma (ISO/IEC 15.909), premido pela grande difusão das RdP e pela necessidade de se ter uma referência para a fabricação de dispositivos e ambientes de software para tratar a modelagem de sistemas de grande porte. Foi então definido o significado das redes chamadas Lugar/Transição (Place/Transition), das redes de Alto Nível e das redes Relacionais. Um protocolo de transferência foi definido baseado em XML, o PNML, e finalmente abriu-se a discussão sobre as extensões definidas pelos usuários, desde que não violem nenhum dos itens anteriores.Mesmo depois do lançamento da norma a discussão acadêmica (e a demanda das aplicações) continuou e as redes de Petri passaram a dar suporte ao design de sistemas de tempo real e de métodos formais de verificação, como o model-checking. Finalmente a passagem para o contínuo passou a ser um horizonte acadêmico inlcuindo aí a rede híbrida, que tem partes discretase partes contínuas.
Na primeira aula veremos uma breve introdução, ainda intuitiva, sobre as redes de Petri, e especialmente sobre os conceitos de modelagem de sistemas discretos.Também será aboradado brevemente os paradigmas de desenvolvimento e modelagem, sempre priorizando a modelagem de sistemas dinâmicos discretos seguindo a linha da modelagem estado/transição. Finalmente introduziremos os conceitos básicos de redes de Petri. -
Bem-vindos ao curso de PMR 5237. Nesta primeira aula faremos um overview sobre os objetivos do curso e uma introdução - ainda informal - sobre as Redes de Petri e sua comparação com os Autômatos Finitos na formalização e modelagem de sistemas em geral. A Teoria de Autômatos não é um dos tópicos básicos do curso mas é um requisito que se tenha um entendimento básico sobre uso de autômatos e Transition Graphs para a modelagem formal de sistemas em automação e a diferença principal destes sistemas para as redes de Petri. Assim, este tópico entrará (como sempre faremos com os tópicos secundários) como algo a ser absorvido através de uma monografia e de um estudo à parte.
Coincidentemente teremos a oportunidade de fazer isso nesta semana aproveitando o fato de que não estarei em São Paulo na semana que vem. Os que ainda estão indecisos sobre se continuarão no curso após a semana que vem podem se preferir me mandar e-mails com as dúvidas que possam ter após verificar as transparências desta primeira aula.
Monografia Para esta primeira monografia, lea com atenção o capítulo 2 do livro Introduction to the Theory of Computation, de Anil Maeshwari e MIchiel Smid (um draft de 2014, para o livro que foi editado em 2015). Ele explica de forma didática e através de exemplos o significado de um autômato determinístico e finito (DFA) e a difernça sobre os autômatos não-deterministicos.
Faça uma resumo com o que você entendeu por um DFA e a diferença entre este e um NFA. Inclua também a diferença entres estes e uma rede de Petri, baseado no material da primeira aula.
Para a próxima aula:
- Refazer o exercício do mundo de blocos usando o PIPE: Veja as indicações no forum (página da disciplina no Moodle) sobre o Petri Nets World e baixe o sistema PIPE para o seu sistema operacional. Veja as notas de aula (transparências).
- Leia o artigo colocado no link “leitura da semana”, trata-se de uma introdução informal às redes de Petri, escrito por dois dos nome mais proeminentes da área no mundo;
- Não teremos aula na semana que vem porque estarei em Recife em uma banca de concurso. Mas, temos uma monografia para cobrir a lacuna (pelo menos parcialmente), além de leitura suplementar sobre Autômatos Finitos e uma lista de exercícios. Estes assignments devem entregues na aula do dia 8 de março, cujo tópico principal será sobre modelagem em Redes de Petri.
-
Nesta semana vamos entrar mais diretamente no tema das redes de Petri, sempre preservando a estratégia de fazer isso primeiro via exemplos e de forma mais intuitiva e depois revendo o processo agora com o formalismo. Como exemplo trataremos um problema dos trens que ligam Lucerne, Engelsberg e Stans (a foto acima é da estação de Stans), que, embora seja um problema real, é pequeno o suficiente para o nosso propósito nesta parte do curso. A nossa modelarem permitiria fazer uma automação do roteamento destes trens que poderia substituir o sistema manual usado até pouco tempo.
Na aula passada vimos os princípios da modelarem de sistemas discretos e como usá-los concretamente de modo a modelar um sistema de controle como a sincronização da largada dos carros da fórmula 1, agora apoiaremos os mesmos princípios para o problema dos trens que ligam as estações de Ski da Suiça de modo a garantir a segurança do processo e a impossibilidade de acidentes graves. Usaremos para isso as redes de Petri Elementares, diretamente maleável em um controle digital on-off.
Associado à resolução deste problema temos a nossa primeira lista de exercícios.
. A lista de exercícios 1 está resumida abaixo, faça o download.
-
Nesta semana faremos uma breve revisão do que já vimos até aqui, especialmente na definição de propriedades e atributos das Redes Elementares, enfatizando o tipo de modelagem que se pode fazer com estas redes. Veremos que se trata de uma modelagem abstrata, com ações simples, e explorando muito pouco dos aspectos distribuídos dos sistemas.
Veremos em seguido os desafios para modelar sistemas produtivos, especialmente os sistemas de manufatura, e ainda de forma mais destacada os sistemas de manufatura flexível. Neste caso a concorrência entre linhas por uma mesma máquina, que por sua vez pode desempenhar várias funções, acrescenta uma considerável complexidade ao processo de modelagem. Por outro lado aparece aí a necessidade de modelar não somente o controle ou o fluxo de controle mas também o fluxo de ítens no processo, ainda na hipótese da indistinguibilidade das marcas.
Assim, introduziremos as redes lugar/transição, ou Place/Transition, como a rede mais abstrata entre as redes clássicas, de onde todas as demais podem ser derivadas impondo restrições de segurança e capacidade dos lugares. A introdução estas redes será feita por um exemplo realístico, para depois introduzir o formalismo.
Na próxima aula todos devem trazer o Milestone 1 coms os ítens descritos ao lado
Os itens para submissão do artigo final são:
Título
Abstract (em inglês)
Relação de palavras-chave
Introdução explicando e motivando o tema e
mostrando porque será resolvido com Petri Nets;
Bibliografia preliminar a ser usada. -
Nesta aula introduzimos as redes Place/Transition, mostrando que para modelar sistemas onde seja necessário ter em conta o workflow, isto é, o fluxo de itens e de controle, é necessário mais do que pode prover as redes Elementares. Estendemos portanto o conceito inicial para uma rede mais abrangente, que pode ter as redes elementares como caso especial, onde se reduz o peso dos arcos a no máximo 1, assim como a capacidade dos lugares.
Os problemas para simulação da rede foram inteiramente resolvidos com um teorema associado à construção das redes completas. Também se analisa o comportamento das redes P/T com a condição de disparo estrita e não-estrita, onde se libera a capacidade dos lugares para crescer de forma irrestrita
Finalmente se discute as possibilidades e os recursos de modelagem que temos até este momento e que serão usados na resolução dos exercícios da semana.
A leitura da semana continua sendo o artigo do Murata e aconselho a todos a avançar na leitura deste artigo. Como exercício temos duas tarefas: a primeira é um estudo dirigido e volta a tratar do problema dos jogadores de marcas, que embora seja um problema secundário é de grande importância prática. No caso avançamos na discussão de algoritmos já enunciados na lista de exercícios anteriores.
A lista de exercicios 2 também deve ser resolvida até a próxima aula. Como existia uma espécie de dúvida sobre a proposta de artigo vamos postergar a entrega desta atividade até a próxima sexta-feira à meia-noite.
-
Esta semana discutimos sobre as propriedades das redes clássicas sempre voltando a discussão para a possibilidade de obtenção de novos recursos para a modelagem e o design de sistemas automatizados discretos.
As propriedades das redes clássicas se dividem em dois blocos: as propriedades comportamentais, que dependem da marcação inicial, e as propriedades estruturais, que dependem mais da estrutura relacional da rede. Em ambos os casos, sistemas reais podem ser mapeados com respeito a propriedades dita desejáveis e que se enquadrem em um destes blocos. Assim, uma das estratégias de análise dos modelos é justamente a análise destas propriedades. Em sala recuperamos problemas da lista 1 e da lista de exercícios 2 para ilustrar estes pontos.
Certamente, um dos problemas dignos de nota é a dependência que ainda temos (até este nível da exposição sobre redes de Petri) dos métodos voltados a atingibilidade ou ao grafo de cobertura. Vamos avançar um pouco mais na discussão sobre propriedades na aula que vem e então voltaremos a este ponto no futuro, buscando novas redes e novos métodos de análise.
-0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0--0-
Mas o importante é avançar na pesquisa bibliográfica sobre o tema do artigo que será o trabalho final do curso. Assim, para a próxima aula vocês deve acrescentar ao que já têm (quem estiver atrasado deve correr para acompanhar o processo), uma nova sessão discutindo justamente porque pretendem usar redes de Petri no artigo e o que esperam como resultado.
O artigo (draft) a ser submetido no milestone 2 (próxima aula, dia 20/04) deverá ter agora: título, abstract em inglês, Introdução, uma nova sessão mostrando a proposta, isto é, como se vai usar redes de Petri na proposta apresenatda, e uma bibliografia atualizada (ela deve aumentar até atingir a fase final).
-
Nesta aula vamos introduzir a discussão sobre as redes não-clássicas, especificamente as redes de alto nível. Começaremos pela discussão do problema de simetria e do dobramento das redes, para logo depois introduzir as redes Predicado-Transição. Estas têm uma grande importância (histórica) no estudo das redes de Petri, por guardar consigo a idéia bastante atraente de utilizar os invariantes (facts) no próprio processo de modelagem ao invés de ser uma propriedade a ser analisada depois de ter um modelo pronto.
Apesar das dificuldades formais esta idéia é ainda atraente e pode ser levada adiante em outras classes de rede. Outra coisa imprtante é a própria exploração da simetria criand um novo sistema híbrido, composto por uma rede mais reduzida e um conjunto de inscrições e sorts, agora inseparáveis da rede em si.
Portanto uma questão importante pode ser levantada, qual seja: quando devemos optar pela modelagem usando redes clássicas e quando devemos optar por uma rede de alto nível. Esta questão aparece como um exercício da lista no. 3 que é disponibilizada abaixo. Os exercícios devem ser feitos até a próxima aula.
Juntamente com os exercícios, todos devem (ou pelo menos aqueles que ainda não chegarm a este ponto) produzir mais uma seção do artigo final, onde se descreve as técnicas e formalismos que serão utilizados no artigo. Algo como uma seção de "background". Este novo artigo também deve ser feito para a próxima aula.
Verifique que na aula de Redes Place/Transition, logo abaixo do link para "retorno da 2a. lista de exercícios" tem un ícon com o label PMR 5237. Este é um link para um forum de discussão que vocês podem usar para tirar dúvidas, colocar opiniões que serão compartilhadas por todos..
----------00000000-----------00000000000000-------------------00000000------------
Como combinamos o prazo para todas as listas de exercício atrasadas fica para a próxima segunda (dia 18/04) meia-noite (zero hora da terça). A proposta de artigo no que seria o segundo milestone para quarta-feira (20/04), dia de aula (notem que vamos eliminar o milestone 1 que ninguém fez mas a nota do milestone dois será contada duas vezes). Finalmente a lista de exercício 4 fica para a próxima sexta (dia 22/04) meia-noite (zero hora do sábado). Não teremos mais prorrogação nenhuma até o final do curso (mesmo por que não teríamos tempo mesmo). Por exemplo vamos acelerar os artigos e portanto teremos um milestone 3 para a aula do dia 27/04.
-
Nesta aula passaremos à discussão das redes de alto nível, incluindo agora a definição do padrão ISO/IEC 15.909-1 e o modelo semântico das redes de alto nível. Como sempre, o nosso objetivo é adquirir conhecimento e habilidade no manuseio das redes de Petri para aplicar na modelagem e design de sistemas em geral. Portanto uma questão fundamental é se o processo de projeto destes sistemas deve ser iniciado com uma rede P/T e depois gerar uma rede HLPN ou se, ao contrário existem casos onde a modelagem direto na redes HLPN é mais promissora.
No final desta aula apresentaremos um exercício simples onde esta questão pode aparecer de forma bem menos trivial do que pode parecer em princípio. Trata-se da aplicação da modelagem em redes para problemas de planejamento de atividades, no caso a montagem de blocos utilizando um robô manipulador. Para evidenciar a inversão no processo de projeto este caso deve ser tomado como um exercício (a lista 4) e deve ser resolvido como listado na última transparencia de aula, juntamente com as perguntas adicionais.
Fica também como exercício para a aula que vem o Milestone no.2 (repetimos o primeiro) onde o artigo final deve ser ampliado agora para acrescentar ao ítens já inseridos (Titulo, abstract, introdução), uma seção de background, onde se discute as teorias envolvidas no artigo (além das redes de Petri), se discute que tipo de rede será usado, e uma seção com a proposta de como as redes de Petri seriam inseridas no trabalho.
Na leitura da semana temos o artigo do Einar Smith sobre redes HLPN, um texto que pertence à Escola internacional de redes de Petri, e outro artigo que resume a última versão da orama ISO/IEC 15.909-1 antes de ser publicada em 2004.
-
Um caso especial das redes de alto nível são as redes coloridas. Estas redes surgiram nos anos 80 justamente com a proposta de estender o escopo de aplicação das redes de Petri para o design de sistemas, e portanto associar a modelagem gráfica e algébrica à linguagem de especificação funcional Standard ML (Milner). Com isso se poderia ampliar o nivel de abstração das redes, explorar simetrias - sempre uma perspectiva tentadora no design de sitemas e no design em geral.
No final dos anos 80 e inicio dos anos 90 surgiu o ambiente Design CPN proposto e mantido pelo grupo da Ahrus, Dinamarca, associado ao proponente das redes CPN, Kurt Jensen. Este ambiente evoluiu para o hoje ambiente integrado CPN Tools. (A foto acima mostra a modelagem no CPN Tools do problema de alocação de recursos em fábrica.)
Mas o importante é entender que as redes coloridas são um caso especial das redes HLPN e portanto devidamente incorporadas no novo padrão das redes. O grande desafio é abdicar do apelo bem mais intuitivo das redes clássicas e aprender a modelar sistemas diretamente nas redes CPN, o que é o foco da nossa discussão esta semana.
Como leitura da semana um artigo com uma introdução prática às redes CPN do Kurt Jensen.
====================================================================================================
Milestone 4
Devemos continuar com a preparação do artigo, agora no milestone 4, que deve conter o seguinte:
1. Título, 2. Autores, 3. Abstract (em inglês), 4. Resumo 5. Introdução, 6. Background, 7. Proposta 8. BibliografiaO artigo com este formato deve ser entregue até O MEODIA DE TERÇA-FEIRA, DIA 3 DE MAIO (antes da aula).
-
Na semana passada introduzimos o conceito de rede colorida como um caso especial das redes HLPN. A exploração direta da simetria produziu redes menores, mais compactas, mas com a mesma expressividade das redes clássicas. Ainda mais, o poder de expressão das redes de fato não se alterou, e o que conseguimos foi, explorando a simetria, combinar a representação gráfica com declarações de tipo e com uma abordagem mais abstrata, que pode ser de grande valia na modelagem e design de sistemas de grande porte.
Entretanto dois aspectos ficaram ainda por serem avaliados: a necessidade de ter que explorar a análise de propriedades - de fato os problemas de análise das redes não desapareceram - e de lidar com o problema da atingibilidade. Outro aspecto igualmente importante é a necessidade de inserir extensões, já discutido quando da apresentaçào das redes clássicas.
Duas extensões forma particularmente discutidas: a inclusão de gates (externos) e inclusão de componenetes hierárquicos. A discussão feita anteriormente foi bastante superficial, portanto, vamos agora voltar a esta discussão, primeiramente através dos conceitos, mas de forma abrangente, isto é, incluindo tanto o uso destes elementos no design com redes clássicas e/ou com redes de alto nível.
............................................................................................................................ Abaixo estão algumas transparência de aula do Van der Aalst com exercícios bem didáticos sobre como usar as redes de Petri e redes coloridas.
-
Depois de discutir os últimos avanços das redes de Petri, incluindo a nova norma que define para a indústria e para a academa o que é uma Rede de Petri, é hora de re-pensar os modelos de modelagem formal e de como estes também apresentam novos desafios para o Design em Engenharia.
O aumento da complexidade levou a dois novos paradigmas: um que se apresenta como um desafio de modelar serviços, com um dinâmica própria e um grande grau de interação e co-criação com os seus usuários, e outro se apresenta como uma forma de integrar serviços e sistemas já existentes em sistemas maiores chamados sistemas de sistemas.
Neste módulo vamos considerar como as dificuldades que já temos de modelagem e design se ampliam na perspectiva de enfrentar estes novos desafios, e como novos métodos podem surgir para enfrentar estes problemas, acabando por trazer novas perspectivas para resolver os problemas antigos. Em ambos os casos temos novos desafios para o uso das Redes de Petri.
-
Nesta aula vamos aprofundar a discussão nos métodos de modelagem e análise com redes coloridas explorando features da representação e discipina de projeto. Após uma sucessão de exemplos e exercicios onde vamos discutir especificamente o uso das redes coloridas hierárquicas e seu potencial para resolver problemas práticos. Trataremos também do enriquecimento da linugagem pelo uso de listas na formataçõa recursiva, e seguindo esta linha, a inclusão de funções na linguagem CPN-ML de modo que podemos ter um set de inscrições muito rico, com grande potencial de modelagem. Sobre este conjunto de recursos podemos rediscutir e revisitar as técnias de modelagem para abordar um problema latente desde que foram introduzidas as redes coloridas: sua diferença para as redes de alto nível que são a base da norma ISO/IEC 15.909.
Como podemos ver claramente agora, a norma propõe uma rede que é um pouco mais que uma rede fatorada tagged, com a inclsão de inscrições de forma muito mais simples - por exemplo não está muito claro na norma o uso de funções nas inscrições das redes HLPN. Por outro lado a riquea de recursos das redes coloridas levam a um ponto de inflexão: devemos apostar na riqueza e na modelagem abstrata associada às incrições ou devemos carregar mais na modelagem pela parte gráfica. O balanço adequado entre uma coisa e outra já foi objeto de discussão em aulas anteriores mas nesta aula este tópico ficará mais claro.
===============================================================================================================
O Miestone 5 é para sexta-feira e reflete o artigo que alguns vão enviar para o CBA. O prazo é 17:00h e não tem nem mesmo a tolerância de cinco minutos.
Para finalizar o curso teremos como trabalho final um outro artigo (compensado pela supressao das listas de exercicio) que deve ser entregue no dia 15 de junho até a meianoite, sem nenhum segundo extra. Como os milestones também foram absolutamente desregrados e atrasados, vamos fazer o seguinte: teremos duas notas, uma em cada paper e faremos a media onde cada artigo deve valer 35% da nota e a media de todas as listasde exercicios 30%.
-
Chegamos ao final do curso! Apesar de alguns percalços e muitos atrasos tivemos neste curso um aprendizado para todos nós inclusive pra mim. Pela primeira vez os artigos que compõem o trabalho final foram TODOS (e posso dizer todos embora nem todos tenham ido para o CBA) submetidos para publicação, com a possibildiade de termos até artigos em dois eventos (com conteúdo diferente, é claro). Algumas listas de exercicio foram sacrificadas e acho que mesmo o desenvovimento de maiores habilidades com o CPN Tools também foi meio sacrificado, mas, por outro lado os artigos usaram de fato o conhecimento de redes de Petri, ainda que tenham trazido já algum background obtido em cursos anteriores ou até com os respectivos orientadores.
Percalços à parte, vocês todos estão de parabéns, independentemente do resultado do processo de submissão. Todos os trabalhos têm propostas consistentes e um uso razoavelmente maduro das Redes de Petri como instrumento de modelageme design, que é justamente o foco da disciplina, basta ver o nome : Modelagem e Design de Sistemas Discretos em Redes de Petri. Farei novas mudanças na sequencia de tópicos baseado no resultado apresentado por vocês. E quero dizer que foi um prazer ministrar esta discipina pra vocês.
Espero que a experiência também tenha sido gratificante e proveitosa para a continuidade dos respectivos trabalhos e que vocês possam de fato inserir Redes de Petri nos respectivos trabahos de tese e dissertação.
Um grande abraço a todos,
Reinaldo
=================================================================================================
Alguns já submeteram artigos ao CBA 2016 e temos pela frente o CLCA, como foi anunciado na aula passada. O deadline, como podem ver acima é o dia 5 de junho, domingo. Portanto vocês pecisam me mandar os artigos no dia 2 até o meiodia. Vou rever e respondo direto na sexta-feira, de modo que todos poderão fazer os ajustes finais antes da submissão no dia 5 de junho. Vamos continuar com o processo e vocês devem fazer o upload da versão final (para o curso) no dia 15 de junho. Se houver tempo usaremos esta versão na submissão dos trabalhos ou podemos usar na submissão final caso sejam aceitos, ou ainda em algum outro evento. Caprichem!