Programação

  • Introdução (Aula 1)

    Contrair tudo Expandir tudo

    Modelagem e Design de Sistemas Discretos em Redes de Petri (2017)











    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.

    Nesta primeira aula veremos uma breve introdução, ainda intuitiva, sobre as redes de Petri, e especialmente sobre os conceitos de modelagem de sistemas discretos. Veremos brevemente a herança teórica das Redes de Petri (Teoria dod Grafos, Autômatos Finitos, Transition Systems) e sua importância para automação. Abordaremos 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.

    O curso foi substancialmente modificado este ano para atualizar a bibliografia e ampliar o escopo, de modo que começaremos já na próxima aula com um conteúdo direto sobre Redes Place/Transition, tendo as redes elementares como caso especial. Usaremos como livro texto o livro Petri Nets for Systems Engineering: A guide to modeling, verification and applications, de Claude Girault e Rudger Valk (Springer), edição de 2003. Portanto não usaremos mais os cursos clássicos de 1998, ministrados em Berlim. Outras referências serão indicadas para reforçar alguns tópicos, bem como artigos seminais e de grande impacto, como o célebre artido do Tadao Murata. 

    Um artigo longo foi escrito recentemnete por Manuel Silva, em 2013, que na verdade celebrava o aniversário de 50 anos das redes de Petri em 2012. Este artigo é indicado em anexo para download e servirá ao longo do curso inteiro como uma base histórica e um relato da evolução dos trabalhos em redes de Petri e o seu uso tanto na academia quanto na prática. 

  • Modelando processos simples

    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.

                                                                                                                    .

    Para a próxima aula cada um deve submeter ao sistema o Milestone 1 que consiste na primeira submissão do que resultará em um artigo que para nós consiste na avaliação principal do curso. Como podem ver nas transparências da aula passada a avaliação depende da submissão das listas de exercicio (é importante fazer as listas mesmo que não acertem todos os exercicios, o objetivo é saber se estão aprendendo) e depende também da submissão dos milestones. Portanto neste curso controlamos o processo e não o "produto" final. Assim, submetam até a próxima aula o título e abstract de um artigo (em PDF) que será o seu trabalho final. Claro, espero que todos consultem os respectivos orientadores de modo a propor um artigo que seja de alguma utilidade nas respectivas dissertações ou teses.

  • Modelando sistemas produtivos

    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.

  • Redes Place/Transition

    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.  Vocês deve aproveitar o tempo para avançar no desenvolvimento do artigo, que será cobrado no próximo milestone. Portanto o tempo previsto para isso não começa na próxima aula e sim agora.

    A lista de exercicios 2 também deve ser resolvida até domingo zero hora.  Não esqueçam de consultar os respectivos orientadores sobre o artigo final.

    Finalmente, lembro a todos que apesar de não estarmos seguindo (ainda) a mesma sequencia do livro texto, estamos no capítulo 3 e, após a introdução da rede colorida e de alto nível vamos entrar em fase com este livro. Vale a pena adiantar e já ler estes capítulos. A esta altura vai funcionar como uma revisão suave do conteúdo que vimos até aqui.

  • Redes de Alto Nível

    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.

    ===========================================================================================

    Embora o contato com as redes de Alto Nível seja ainda inicial, a idéia é que esta seja também uma alternativa, no desenvolvimento do artigo final. Portanto como o compromisso de cada um com o uso das redes de Petri no artigo, vocês podem agora optar por usar as redes de ato nível, incluindo-se aí as Redes Coloridas. Isso deve ser sincronizado com a próxima etapa dos milestones onde cada um deve inserir, a primeira sessão do artigo contendo a proposta de problema para o qual será apliada a rede de Petri, clássica ou de alto nível. 

  • Redes Coloridas

    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.

    Disponibilizamos abaixo textos do comitê que elaborou a norma ISO/IEC 15.909. Para redes coloridas usem o livro texto.

    ===============================================================================================

    Listas de exercício

    A Lista 3 ficou para o dia 12/04 que seria um dia de aula mas está na semana santa

    A Lista 4 fica então para o próximo dia de aula, que será 19/04

           ====================================================================================================

    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 (seção onde se descreve a motivação do artigo e o porque do uso das redes de Petri), 7. Proposta (definição de qual será a contribuição do artigo, ou seja, onde se aplicará as redes de Petri e qual o resultado esperado) 8. Bibliografia

    O artigo com este formato deve ser entregue até A MEIANOITE DO DIA 19 DE ABRIL (próxima aula depois da semana santa). 




  • Redes Coloridas


       Petri Nets, classic or coloured? 

         That's the question. 

    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 ficou implícito no processo que para sintetizar uma rede colorida ou de alto nível seria preciso ter, antes, uma rede Place/Transition, onde seriam identificadas as simetrias que dariam suporte aos dobramentos. Não é muito intuitivo para nenhum de vocês a síntese de uma rede colorida à partir do problema, como se a modelagem só fosse possível em "small steps".  Nesta aula vamos em primeiro lugar ver as duas redes definidas na norma ISO/IEC 15.909-1, as redes P/T e de alto nível, como representações formais de igual expressividade e começar a combater este feeling de que "seria natural" desenvolver primeiro uma rede clássica. Na verdade trata-se de uma opção, e temos que explorar o que se perde e o que se ganha com cada uma delas. Como exercício vamos experimentar sintetizar uma rede colorida diretamente do problema do mundo de blocos, operado por um robô. 



    		           


  • Modelagem e Análise com Redes Coloridas

    tradeoff

    Nesta aula vamos aprofundar a discussão sobre a perspectiva de usar redes P/T (place/transition) ou redes coloridas e de alto nível nos projetos e nas aplicações mecatrônicas. Vamos enriquecer esta discussão tratando a abordagem de alto nível como o que realmente é, isto é, a possibilidade de aumentar o nível de abstração do processo de design, que pode ter como efeito colateral a redução da parte de rede. Nesse caso, sintetizar direto uma rede colorida (de alto nível) se justifica por explorar as simetrias desde o processo de requisitos. Por outro lado, no que se refere à análise de propriedades temos a análise das propriedades estruturais - que não dependem da marcação inicial poderemos ter maiores dificuldades para analizar, por exemplo invariantes. Nesse caso é sempre possível retornar a uma rede Place/Transition, onde os algoritmos de análise de invariantes estão bem definidos.

    A conclusão é que tanto uma forma como outra P/T e coloridas (de alto nível) formam duas faces da mesma moeda e podem ser usadas em conjunto. Fica então à critério da conveniência e do problema que se quer analizar. Lembrando que na aula anterior discutimos um teorema onde, dada uma rede P/T é possível fatorá-la e depois obter uma representação de alto nível. Similarmente também é possível fazer o "unfolding" (discutido na aula passada), para, a partir de uma rede colorida, obter a sua correspondente rede P/T.

    Usaremos também esta aula para nos familiarizar com o uso da rede colorida seguindo as regras derivadas dos fundamentos teóricos desta rede. Temos que aumentar a nossa habilidade de usar a ferramenta CPN Tools, dado que a partir da aula que vem entramos no terceiro módulo da disciplina, que consiste no uso das redes de Petri definidas pelo padrão ISP/IEC 15.909 para modelagem e design de sistemas automatizados. 

    ===============================================================================================================

    O Milestone 5 deve ser entregue na próxima quarta-feira, dia 3 de maio. Neste milestone todas as dúvidas surgidas com respeito ao artigo devem estar resolvidas e a proposta (que remonta ao milestone 3 no que se refere a tamanho) deve conter: título, autores, abstract (inglês), resumo (português), e uma introdução que traz a motivação para o trabalho e os resultados esperados. 

     


  • Voltando aos métodos de design

     ss

    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. 

    Neste módulo vamos considerar como as dificuldades que já temos de modelagem e design se ampliam quando enfrentamos desafios de projeto, e como novos métodos podem surgir para enfrentar estespara  problemas ou trazer novas perspectivas para resolver os problemas antigos. Em ambos os casos temos novos desafios para o uso das Redes de Petri.

    Vamos considerar igualmente, como faz o livro texto as redes coloridas e clássicas e tentar vencer a barreira que nos impede de lidar diretamente com a abstração das redes coloridas ou HLPN e voltar à discussão dos métodos de análise e da análse de propriedades dos sistemas em redes de Petri. Vamos também começar a dar uma abordagem voltada a sistemas.

  • Modelagem e Design de Sistemas com Redes de Petri



    Esta semana vamos colocar um fim na discussão dos aspectos básicos das redes de Petri, pertinentes ao formalismo em si, e vamos agora discutir métodos, tips, conceitos e boas práticas para modelar sistemas, desde os requisitos até a síntese de soluções e sua comparação para a escolha da solução definitiva. Portanto vamos re-editar a discussão da primeira aula, mas, evidentemente, em um nível bem mais alto. Alguns vícios de atitude precisam ser trabalhados, como por exemplo a tentativa de sintetizar uma rede de Petri onde os nós tentamos representar o modelo físico como lugares e transições da rede, em detrimento do que realmente precisa ser capturado: a dinâmica do sistema e suas propriedades mais relevantes.   Tendo isso em mente vamos pensar em um processo mais flexível, onde podemos sintetizar, modelar e analisar os sistemas ao mesmo tempo, seja em redes clássicas ou em redes de alto nível (usando extensões mais simples, como gates, hierarquia, etc.).



    Para a próxima aula vocês precisam atualizar a leitura do livro texto (capítulos 5 e 6), onde o 6 é somente um resumo da parte básica de conceitos sobre Redes de Petri. O capítulo 7 é curto e tem somente uma introdução à parte de modelagem. Estamos discutindo de fato o capítulo 8 e seria bom lê-lo antes da próxima aula. Vocês têm até amanhã, dia 11/05 ao meio-dia para postar o milestone 5. Receberão também uma lista de exercício para o dia para o dia 19/05. E devem preparar uma versão completa do artigo para o dia 25/05. Depois disso terão mais duas semanas para entregar a versão final.       

  • Modelando com Redes de Petri


    Chegamos a um ponto em que os conceitos sobre o formalismo das redes de Petri estão consolidados e os exercícios parecem exequíveis mas irreais, isto é, não se assemelham a um projeto real. O capítulo 8 do livro texto é rico em exemplos de problemas realísticos que são apresentados em forma textual, como normalmente aparecem na prática. Começa então a surgir a dúvida de como tratar estes casos e de como começar a modelagem. Na verdade temos que inserir o uso das redes de Petri no escopo dos projetos reais, começando por diferenciar a identificação do problema e o "project statement" das demais fases de especificação e análise de requisitos (portanto referentes ao problema), das fases de proposição de uma arquitetura (pressupondo que temos em mente um sistema distribuído) relacional dos componentes e sub-sistemas e da solução proposta sobre esta arquitetura.

    Devemos portanto enfrentar nossos vícios imediatistas, e a disposição para achar uma solução "única" antes mesmo de entender o problema. Portanto nesta aula de hoje vamos discutir esta inserção do formalismo de redes de Petri no processo de projeto, notadamente na análise de requisitos e como linguagem de especificação e como formalismo para expressar a solução do problema, capaz de dar suporte para o processo de validação e verificação formal. Devemos levar também esta discussão para o processo de elaboração dos artigos.

  • Systems Design with Petri Nets

    Destaque


    Nesta aula fizemos um checkpoint final sobre o processo de modelagem em geral e sobre o ciclo de vida de processo usando Redes de Petri, tratando no mesmo bloco as redes clássicas e de alto nível. Os problemas de modelagem não dizem respeito ao tipo de rede, mas é bom poder escolher de forma adequada por qual rede queremos começar o processo, dependendo do sistema a ser modelado. Outro ponto de grande importância é a relação entre os modelos e cada parte do ciclo de vida de projeto de sistemas, eliminando praticamente o dilema enre o "ovo e a galinha" que tínhamos colocado há duas aulas atrás. 

    As redes de Petri são agora apresentadas como uma linguagem que além de poder representar e modelar requisitos pode servir como linguagem de especificação e finalmente servir no processo de design das soluções, mostrando assim o seu poder descritivo, analítico e de verificação formal que foi preconizado durante todo o curso.

    Chegamos ao final do curso com um fechamento que agora reune a teoria e aplicação das redes de Petri e o Design de Sistemas, que é o que tinhamos planejado desde o inicio. Espero que tenham ficado satisfeitos com este fechamento e que isso tenha aberto uma nova perspectiva de como usar as redes de Petri em projetos e no trabalho acadêmico. Temos agora que fechar a nossa agenda de exercícios e especialmente o trabalho final. Nesse caso temos as seguintes datas:

    29/05 submissão do artigo completo  (Milestone 6)

    03/06 feedback da submissão 

    14/06 submissão do artigo final

    21/06 divulgação das notas finais.

    Espero que o curso tenha servido para abrir novas perspectivas e possibilidades no trabalho de vocês. Acho que cumprimos um bom roteiro de curso.

    Sucesso nos trabalhos! 

    Reinaldo



    Resultado Final do Curso


    Nome
    Media Listas
    Media
    Milestones
    Artigo Final
    Media Final
    Conceito
    Alexandre do Nascimento 6,3 7,8 7 7,12 B
    Jeferson Dias 6 7,5 7 6,85 B-
    Jose R. Sicchar 6,16 8,5 8 7,59 B
    Miguel Orellana 6 7,3 7 7,39 B
    Nilberto Machado 0 0 6 - -