Programação

  • Introdução (Aula 1)

    Contrair tudo Expandir tudo

    fábrica da Rima ImpressorasRdP da circulação de AGVs na fábrica da RIMA

    A figura mostra a antiga fábrica de impressoras RIMA cujo fluxo de material transportado por AGVs foi projetado e analisado pela Escola Politécnica em 1990. 


    Desde a sua criação em 1962 as redes de Petri só fizeram ampliar o seu escopo de aplicação. Parelelamente, o formalismo também foi ampliado e aperfeiçoado, e várias extensões surgiram para atender a domínios de aplicação localizados (embora muito importantes). Assim, a chegada do século XXI marca um período de grande profusão e até alguma confusão, sobre o formalismo base das redes de Petri, o que é também um requisito para a difusão das Redes de Petri, especialmente no meio industrial, que precisa de uma certa unidade para investir em produtos (CLPs, SDCDs, por exemplo) que possam fazer uso deste formalismo.
    Um comitê de pesquisadores passou a discutir a padronização formalismo base, culminando com a proposição de uma norma, premido pela grande difusão das RdP inclusive para a área de software, análise de requisitos, planejamento automático, verificação formal, model checking, etc., além do seu uso normal como esquema para a modelagem de sistemas discretos e simulação destes sistemas.

    Nesta primeira aula veremos uma breve introdução, ainda intuitiva, sobre as redes de Petri, e especialmente sobre os conceitos da modelagem de sistemas discretos.Também serão abordados brevemente os paradigmas de modelagem e análise, sempre priorizando os sistemas dinâmicos discretos segundo o paradigma de modelagem estado/transição.

  • Modelando processos simples

    Nesta semana tratamos de forma mais concreta do processo de modelagem de sistemas discretos, primeiro de uma forma mais intuitiva. Para isso tomaremos o problema dos trens que ligam Lucerne, Engelsbert e Stans (a foto acima é da estação de Stans), que, embora seja de fato um problema real, é pequeno o suficiente para o nosso propósito nesta parte do curso.

    Vimos portanto os princípios de modelagem e como usá-los concretamente de modo a modelar um sistema de controle 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, como o choque das composições no trecho unificado.

    Associado à resolução deste problema temos a nossa primeira lista de exercícios.

  • Modelando sistemas produtivos

    Nesta semana faremos uma breve revisão do que já vimos até aqui, especialmente a definição de propriedades e atributos das Redes de Petri clássicas, enfatizando o tipo de modelagem que se pode fazer com estas redes. Veremos que se trata de uma modelagem abstrata, com ações simples, explorando os aspectos distribuídos dos sistemas. Portanto é preciso dar uma certa atenção à modelagem formal baseada em propriedades e na análise da equação de estados. Com este desafio pela frente, voltaremos a discutir os aspectos formais e conceituais das redes de Petri, incluindo a definição dos sistemas completos e a eliminação dos problemas de contato da rede.

    Finalmente, vamos introduzir os desafios para modelar sistemas produtivos, especialmente os sistemas flexíveis de manufatura. Neste caso temos as opções em uma mesma linha de produção, o uso de uma mesma linha para fabricar produtos diferentes e a concorrência entre linhas por uma mesma máquina (ou outro recurso). Geralmente trata-se de máquinas de comando numérico que podem desempenhar várias funções,  e isso acrescenta 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. Isso nos leva a introduzir as Redes Place/Transition com a hipótese de ter múltiplas marcas nos lugares com a hipótese da indistinguibilidade das marcas.

    Encerraremos com a definição formal das redes Place/Transition (P/T), 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 destas redes será feita por um exemplo realístico, justamente ligado à manufatura flexível.


     

    Para a próxima aula se recomenda colocar a modelagem     

    do processo de fabricação no PIPE2 e formalizar a

    proposta do artigo (1o. milestone) 0cujos ítens estão ao lado.  

    O milestone deve ser submetido em .pdf neste site. Um coletor      

    será colocado abaixo.   
    Os itens para submissão do 1o. milestone do artigo final são:

    Título
    Abstract (em inglês)
    Relação de palavras-chave

    Introdução explicando e motivando o tema
    Bibliografia preliminar

  • Redes Place/Transition

    Nesta aula vamos abordar de forma mais direta 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. Este é o entendimento da norma de redes de Petri ISO/IEC 15.909.

    Os problemas para simulação da rede foram inteiramente resolvidos com um teorema associado à construção das redes completas que discutimos na aula passada. A justificativa formal para relaxar a condição de disparo estrita e ter um jogador de marcas baseado na equação de estado, ficou também estabelecido. Também se analisa o comportamento das redes P/T com a condição de disparo estrita e não-estrita com a capacidade dos lugares liberada para crescer de forma irrestrita. Isso nos habilita a detectar o crescimento monotonico da marcação e portanto alguma falha no controle/automação do sistema sendo analisado, embora não nos seja realmente possivel modelar um sistema com marcação infinita (mesmo que cresça de forma discreta).

    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 lista 2.

  • 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 aparecerá como um exercício da lista no. 3 distribuida na semana que vem.  

    Procurem atualizar até esta próxima sexta-feira a lista de exercícios 2 e o milestone do artigo. Depois disso o link será fechado pontualmente à meianoite da sext-feira 13. Portanto dá azar não entregar os exercícios e o milestone!

  • 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.

    Como leitura da semana um artigo com uma introdução prática às redes CPN do Kurt Jensen.


    Vamos voltar ao artigo, já que estamos praticamente na metade da disciplina e o tempo está ficando muito escasso. Assim, faremos nesta aula um estudo dirigido sobre as redes de alto nível seguindo os slides em anexo e, para a próxima aula (a lista fica para esta sexta-feira) teremos como meta entregar um primeiro draft do artigo contendo título (é importante discutir com os respectivos orientadores sobre isso, abstract em inglês, introdução (colocação do tema do artigo, motivação, referência a outros trabalhos e descrição geral do que se pode esperar dos resultados) e a seção que descreve o background, isto é, quais as técnicas e métodos seriam usadas no artigo. Certamente poderemos modificar isso, mas cabe definir o que vamos usar das redes de Petri no artigo e mais que outras técnicas, métodos e teorias deverão figurar ao lado das redes de Petri. A entrega será no dia da aula, até a meianoite.


  • Redes HLPN

    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 nota de aula, juntamente com as perguntas adicionais.

    Devemos continuar a elaboração dos respectivos artigos e o procedimento agora é o seguinte: vocês terão feedback sobre os artigo e devem reagir a estes comentários modificando ou adequando os artigos. A entega será marcada para a sexta-feira 1 de novembro à meia-noite. 

    A leitura da semana é o capítulo 3 do livro texto, para revisar os conceitos e ver as definições (mostradas em sala) formais no capítulo 4.


  • Propriedades das Redes Clássicas e de Alto Nível

    Esta semana discutimos sobre as propriedades das redes clássicas e de alto nível sempre voltado 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. As redes de alto nível possuem propriedades semelhantes, mas a forma de calcular estas propriedades é distinta e em alguns casos mais interativa.

    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. A rede de alto nível introduz algo semelhante, conhecido como O-Graph. Vamos avançar um pouco mais na discussão sobre propriedades na aula que vem, depois de tentar aplicar estes métodos a um problema de modelagem e design mais realístico.   Para a aula que vem portanto teremos que avançar significativamente nesta modelagem e no artigo final.

  • Modelagem Análise e verificação com Redes de Petri




    Nesta aula vamos entrar no detalhe sobre os processos de modelagem e análise (e verificação) de sistemas discretos usando Redes de Petri, tanto para as redes clássicas P/T quanto as redes de alto nível (ou coloridas) analisando prós e contras, inclusive de começar a modelagem com cada uma delas. Veremos a diferença nestas duas opções de rede, dado que nem todas as propriedades têm equivalente nas duas redes - pelo menos não com a mesma interpretação ou o mesmo método. Além disso, a existência de algoritmos para o cálculo automatizado das propriedades também não é garantido para redes de de alto nível (coloridas). Portanto a possibilidade de verificação formal não é equivalente nos dois casos embora seja possível. Existem por exemplo vários trabalhos recentes propondo novas abordagens para a análise de propriedades em redes de alto nível (coloridas).

    Outra possibilidade muito interessantes é o uso das redes de Petri no processo de design, especificamente na análise de requisitos - que vem a ser um dos campos que mais cresce na comunidade acadêmica da área. Especialmente para o caso de sistemas dinâmicos - que é o caso de sistemas automatizados - é importante antecipar a formalização, e especificamente durante a fase de requisitos. Faremos uma discussão sobre este tópico, que de fato é assunto de pesquisa e um problema ainda em aberto, passando pela transformação de abordagens diagramaticas clássicas de representação (semi-formal) de requisitos como a UML para redes de Petri. Novas abordagens, orientadas a objetivo também passam pelo mesmo processo. Veremos alguns trabalhos da literatura tratando deste problema. 

  • Análise de invariantes e método de modelagem e design



    Na aula passada vimos as propriedades principais envolvidas em um processo de modelagem e design de sistemas (discretos) automatizados: limitação (boundedness), vivacidade (liveness), reversibility (reversibilidade) e exclusão mútua (mutex). Introduzimos também o conceito de equanimidade (fairness), e sua importância no processo de análise. Agora vamos introduzir o conceito de invariantes - sempre pensando em favorecer o processo de modelagem e design - e mostrar como o cálculo de invariantes (inicialmente sobre as redes clássicas, isto é, lidando com invariantes algébricos) pode ser importante, tanto como uma propriedade de análise importante no processo de modelagem e design, quanto como método de prático de análise, na medida em que pode servir de base, de maneira formal, para a avaliação das demais propriedades. Existe na literatura vários métodos de cálculo de invariantes baseados em algoritmos especiais, usando programação matemática (SIMPLEX), ou em métodos canônicos, como Gaus-Jordan. Estes algoritmos estão já fora do escopo da disciplina, mas abordaremos a forma de como inserir o cálculo de invariantes no processo de modelagem e design.

    Na próxima aula (depois da apresentação dos respectivos artigos) veremos como tratar os invariantes nas redes coloridas e de alto nível.

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


    A submissão inicial do artigo, marcada para a aula de hoje (12/11) fica agora para 16/11, 00:00h (madrugada de 15 para 16 de novembro). Um feedback será dado no sábado para que todos possam usá-lo na preparação das apresentações para o dia 19/11.

  • Modelagem em Redes Coloridas

     

    Na aula anterior à apresentação dos trabalhos discutimos a modelagem e análise de sistemas usando redes de Petri clássicas P/T e suas propriedades. Avançamos a discussão das propriedades básicas - limitação, vivacidade, reversibilidade e exclusão mútua - depois estendida para incluir equanimidade (fairness), também para as redes coloridas. A atingibilidade (modelagem do espaço de estados), base da simulação fico como pano de fundo, e, no caso das redes coloridas incluir a síntese do O-graph, como mostrado na figura acima. Discutimos na aula anterior a esta os invariantes e os algoritmos de cálculo baseados em programação linear (Simplex) ou no método de Gaus-Jordan. Ficou faltando completar esta discussão para incluir a análise de invariantes sobre as redes coloridas.

    Como vamos ver não temos um algoritmo consolidado de cálculo de invariantes sobre redes coloridas, dada a dificuldade de ter uma "matriz de transformação" sobre qual basear este cálculo (como tínhamos nas redes P/T). Entretanto uma análise de invariantes ainda pode ser feita e esta deve ser enquadrada nos processos de modelagem e análise com redes CPN. No caso dos "invariantes de design" (veja definição nos slides da aula) podemos encaixar esta análise durante a modelagem dos requisitos do sistema ou durante a fase de design (neste caso para garantir que o processo modelagem satisfaz os requisitos). Porém, no caso dos invariantes operacionais, que surgem da dinâmica do processo modelado, isto não é possível. Devemos então usar a possibilidade de fazer o "unfolding" da rede e retornar a uma rede P/T para aplicar os algoritmos disponíveis. Na aula que vem definiremos as redes de alto nível (High Level Petri Nets, HLPN) e em seguida os processos de folding e unfolding serão objeto de um teorema que garante a reversibilidade destes processos em uma rede HLPN.

    A leitura da semana trata das definições de invariante de lugar e transição em redes coloridas usando um exemplo, antes de introduzir o formalismo. 

  • Redes Estendidas e Orientadas a Objetos

    Destaque

    Completando o nosso estudo sobre a modelagem e design de sistemas em redes de Petri, introduziremos as redes HLPN formalmente (discutimos este tópico sob a égide das redes CPN e nos referimos a aspectos práticos e conceitos durante o curso, mas sem apresentar uma definição formal). Estas redes foram apresentadas no escopo da elaboração da norma ISO/IEC 15.909 com o objetivo de completar o ciclo de abstração que começa com a rede clássica P/T.  Portanto este processo culmina com a proposição de que qualquer que seja a rede P/T, esta admite uma rede quociente e a partir desta podemos sintetizar uma rede HLPN, e vice versa, é possível, á partir de uma rede HLPN fazer o unfolding para obter uma rede quociente associada a uma rede P/T.  Portanto o processo de folding e unfolding pode ser formalizado e portanto traduzido para um algoritmo, que por sua vez pode integrar um ambiente de execução (como o CPN Tools) para, forma automática ou semi-automática, apoiar o processo de modelagem e design. Também é possível associar este algoritmo ao processo de modelagem e design de sistemas à partir dos requisitos, como mostraremos na aula de hoje.  

    A partir daí vamos tratar brevemente do aspecto mais abstrato da extensões da redes de Petri que são as redes Orientadas a Objetos. Até aqui o elenco das extensões foi composto pela abstração, com uma breve menção aos gates, como elementos capazes de propagar informação mas não fluxo concreto de marcas e a hierarquia de redes, tratadas junto com as redes P/T mas extensíveis às redes coloridas. As redes por objetos e um dos casos especiais, as redes aninhadas, são objeto de estudo e discussão pela comunidade de pesquisa em redes de Petri e já podem ser encontradas em ambientes de apoio como o Renew. Não teremos mais tempo para aprofundar esta discussão, infelizmente, mas pelo menos teremos uma idéia mais clara dos principais tópicos de discussão sobre redes de Petri, além daqueles pertinentes a novas aplicações. Também trataremos "en passant" das redes híbridas.