Programação

  • Introdução (Aula 1)

    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, quando foram propostas pela primeira vez por Carl Adam Petri, as redes de Petri vêm ampliando 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 específicos. 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 foi também um requisito para sua difusão, especialmente no meio industrial. Entretanto, aplicações industriais demandam uma certa uniformidade para dar suporte a produtos (CLPs, SDCDs, por exemplo). Por isso, um comitê de pesquisadores passou a discutir a padronização das Redes de Petri, culminando com a proposição de uma norma, que por um lado atendesse à grande difusão das RdP inclusive para a área de software, análise de requisitos, planejamento automático, verificação formal, model checking, etc., e por outro atendesse à demanda do meio industrial. 

    O nosso curso será norteado pela norma ISO/IEC 15.909-1 que define os modelos clássicos de Redes de Petri (sem adjetivos adicionais, mas seria o modelo mais amplo das redes Place/Transition), e das redes de Alto Nível 
    ISO/IEC 15.909-2 (que tem como modelo mais difundido as redes coloridas). Trataremos brevemente do modelo de transferência - que permite que modelos possam migrar entre plataformas e software de apoio) em XML, que é o PNML (Petri Nets Markup Language), e incluiremos algumas extensões - ISO/IEC 15.909-3 - como os gates inibidores, os lugares de conexão, e o modelo hierárquico. 

    Nesta primeira aula veremos uma breve introdução, ainda intuitiva, sobre redes de Petri, especialmente sobre sobre sua aplicação na modelagem de sistemas discretos.Também serão abordados brevemente os paradigmas de modelagem e análise, sempre priorizando os sistemas dinâmicos discretos e 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 á análise baseada na equação de estados. Com este desafio, 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 a modelar de sistemas produtivos, especialmente voltada para os sistemas flexíveis de manufatura. Neste caso, temos vários produtos em uma mesma linha de produção. O uso de uma mesma linha para fabricar produtos diferentes gera a concorrência de vários processos para usar 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 mais 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 possibilidade de ter múltiplas marcas nos lugares mantendo a hipótese da indistinguibilidade entre estas 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 redes clássicas podem ser derivadas, impondo restrições de segurança e capacidade dos lugares. A introdução destas redes será feita com um exemplo realístico, ligado à manufatura flexível.


     

    Para a próxima aula:

    Definição do artigo final 

      Cada um deve definir um tema para o artigo final e depositar um documento (pdf) com título e abstract (em inglês). 
  • Redes Place/Transition

    Nesta aula vamos abordar de forma mais direta as redes Place/Transition, especialmente na modelagem de sistemas onde é necessário ter em conta o workflow, isto é, o fluxo de itens e de controle. Nesse caso é necessário mais do que pode prover as redes Elementares. Estenderemos portanto o conceito de Redes de Petri para uma formulação mais abrangente, que pode ter as redes elementares (e condição/evento) como caso especial. Esta formulação é a base da norma ISO/IEC 15.909, que unifica entre academia e aplicações, o uso das redes de Petri.

    Os problemas referência para observadores distintos podem ser resolvidos com um teorema das redes completas (S-complete) já mencionada na aula passada. Veremos também como relaxar a condição de disparo estrita e ter mais flexibilidade para explorar a  atingibilidade e o jogo de marcas. Introduziremos também a análise de propriedades da rede incluindo os invariantes de lugar e transição. Finalmente, discutiremos 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 estar intimamente ligadas ao processo de modelagem de sistemas em geral nas ciências exatas e naturais. Mais tarde poderemos associar este conceito aos invariantes.

    A exploração da simetria cria um formalismo híbrido, usando propriedades mais abstratas, e resulta em uma rede reduzida no que se refere à representação gráfica, mas com o acréscimo de um conjunto de inscrições, agora inseparáveis da rede em si. Portanto trata-se de uma outra forma de representar formalmente os sistemas dinâmicos discretos, com o mesmo poder de expressão. Fica a pergunta: quando devemos optar pela modelagem usando redes clássicas e quando devemos optar por uma rede de alto nível ou rede colorida?. Voltaremos a esse tem na aula seguinte e  exercício da lista no. 3, que será distribuída também na próxima aula.  

  • 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, com a introdução de formalismo mais abstrato no design de sistemas, associando a modelagem gráfica e algébrica à linguagem de especificação funcional Standard ML. Desse modo, é possível ampliar o nível de abstração das redes e explorar simetrias - uma perspectiva muito forte no design de sistemas e no design em geral.

    No final dos anos 80 e inicio dos anos 90 surgiram as redes coloridas e o ambiente Design CPN ,proposto e mantido pelo grupo da Aarhus, Dinamarca, associado ao criador das redes CPN, Kurt Jensen. Este ambiente evoluiu para o ambiente integrado CPN Tools, que usaremos nesta disciplina. (A foto acima mostra a modelagem no CPN Tools do problema de alocação de recursos em fábrica.)

    As redes coloridas são um caso especial das redes HLPN (High-Level Petri Nets) e estão devidamente integradas ao padrão ISO/IEC 15.909 que vimos na aula passada. O grande desafio é abdicar do apelo intuitivo das redes clássicas e aprender a modelar sistemas diretamente nas redes CPN, o que é o foco da nossa discussão esta semana.

    Discutiremos um caso prático, a modelagem da automação de um posto de gasolina, e tentaremos sintetizar a dinâmica desse sistema diretamente em redes coloridas, sem uma modelagem prévia em Redes P/T. 



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

    Esta semana vamos tratar das propriedades das redes clássicas e de alto nível (coloridas) sempre em busca de novos recursos para a modelagem e o design de sistemas discretos automatizados.

    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 da estrutura relacional da rede. Em ambos os casos, sistemas reais podem ser mapeados com  propriedades ditas desejáveis (reversibilidade, vivacidade, limitação, ...), e outras que devem ser evitadas (deadlock, gargalos, ...). Uma das estratégias de análise de sistemas se baseia na análise destas propriedades - associadas à representação formal - e de outras, associadas ao processo de modelagem (equanimidade, invariantes,...). Tanto as redes clássicas como as de alto nível (coloridas) possuem propriedades semelhantes, mas a forma de calcular (e usar) estas propriedades é distinta.

    Certamente, um dos problemas dignos de nota é a dependência - pelo menos nos métodos usados na prática -  dos métodos voltados a atingibilidade. A rede de alto nível (colorida) introduz o O-Graph, como o equivalente do grafo de cobertura para as redes clássicas. Na aula de hoje vamos nos concentrar nas propriedades básicas para as redes clássicas e coloridas. Na próxima aula ampliaremos esse escopo, agora associado aos métodos de modelagem e design.   


  • Análise de invariantes



    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). Existem também outros conceito como equanimidade (fairness), que trataremos nas aulas seguintes. Nesta aula 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) pode ser importante no processo de modelagem e design de sistemas, e também como método de prático de análise, servindo de base formal para a avaliação de outras propriedades. Existe na literatura vários métodos de cálculo de invariantes baseados em algoritmos especiais, usando programação matemática (SIMPLEX), pela análise de semiflows, ou baseados em métodos canônicos, como Gauss-Jordan. Estes algoritmos estão já fora do escopo da disciplina, mas abordaremos a inserção do cálculo de invariantes no processo de modelagem e design, confiando na capacidade dos ambientes de apoio para fazer o cálculo.

    Na próxima aula veremos com mais detalhes como tratar os invariantes nas redes coloridas e de alto nível.

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


    Temos um fórum aberto para tratar da elaboração do artigo final.

  • Técnicas de modelagem de sistemas com RdP


    Ilustramos essa aula com uma imagem alusiva ao OPC UA (Open Platform Communication - Unified Architecture) um standard para a comunicação industrial segura, um suporte essencial para a Indústria 4.0. Aproveitamos para enfatizar que estes sistemas são mais do que um novo arranjo tecnológico avançado mas um novo modelo produtivo, necessário automatizado e sustentável. E a flexibilidade envolvida requer com mais força recursos de modelagem de processos, e de sistemas formais, como as redes de Petri.

    Trataremos nessa aula justamente das técnicas de modelagem, que podem ser aplicadas, tanto usando as redes clássicas P/T como as redes de Alto Nível ou coloridas. Como afirmamos antes, prosseguiremos nestas parte do curso com técnicas e depois métodos de modelagem de sistemas, suas respectivas demandas, usando seja um ou outro tipo de rede e comparando prós e contras resultantes da opção escolhida. Sempre lembrando que podemos fazer a qualquer momento a conversão de um tipo a outro, por "folding" (das redes P/T para as redes coloridas) ou "unfolding" (das redes coloridas para as redes P/T), e a discussão é sobre qual técnica é melhor aplicada nesta ou naquela rede. 

    Iniciaremos ampliando as propriedades básicas para incluir o "fairness" (mencionaremos brevemente a distância síncrona) e seguiremos adiante com a análise de invariantes nas redes coloridas e a introdução das técnicas de análise.

  • Modelagem formal de sistemas baseada no espaço de estados



    Chegamos ao foco da discussão sobre modelagem de sistemas com Redes de Petri, e agora, usaremos todos os princípios, métodos, teoremas (mesmo os que não foram demonstrados), propriedades, e as técnicas discutidas na aula passada, para compor métodos de modelagem e design de sistemas com redes de Petri. Estes métodos podem ser baseados no uso tanto das redes clássicas P/T como das redes coloridas (aqui representando a classe das redes de Alto Nível). 

    Temos basicamente dois métodos para a modelagem e análise das redes: o método orientado à análise do espaço de estados e os métodos orientados a eventos. O primeiro é mais usado na modelagem de sistemas em diversas áreas e se enquadra melhor com os métodos de design formal, uma vez que é direcionado à resolução de problemas. Entretanto, está no limite (e além) do escopo desta disciplina, como veremos na aula de hoje. O segundo (que veremos na aula que vem) é mais familiar, e direcionado a workflow e modelagem de transações. Na prática ambos são usados, e em trabalhos recentes, combinados em abordagens híbridas, especialmente para sistemas (automatizados) de maior complexidade. 

  • Modelagem de Sistemas Orientada a Eventos


     

    The information system supporting research

    Completaremos a discussão sobre modelagem de sistemas introduzindo o método orientado a eventos, mais intuitivo, e mais voltado para a interpretação do "sistema físico" (ou arquétipo). Destacaremos o aspecto metodológico preservando a abordagem top down, típica para sistemas, como visto nas aulas anteriores. É possível nesse método combinar a divisão do sistema em partes - de forma estruturada - que seriam desenvolvidas separadamente, com a reutilização de componentes, especialmente se estes forem encarados como sub-sistemas. Assim, esta abordagem se mostra aderente ao processo de modelagem de sistemas distribuídos ou System of Systems (SoS). 

    Ficamos portanto com o problema (que aliás motivou a proposição das redes de Petri) de propor um protocolo de comunicação entre sub-sistemas. Este protocolo pode também ser modelado com Álgebra de Processos, mas este tópico está fora do escopo desta disciplina. Portanto discutiremos a modelagem usando somente Redes de Petri, sejam as redes clássicas P/T ou coloridas. Finalizaremos com a discussão sobre o papel da validação ou verificação nesta abordagem orientada a eventos. Antecipando a discussão da nossa aula final, terminaremos a aula com uma consideração sobre novos domínios de aplicação da modelagem de sistemas com redes de Petri.


  • Tópicos de pesquisa em Redes de Petri

    Destaque

    Chegamos ao final do nosso curso, e, sendo matéria de pós-graduação terá o seu final dedicado à discussão sobre tópicos de interesse para pesquisa e desenvolvimento em Redes de Petri, e seu respectivo impacto em outras áreas e campos de estudo. Já discutimos alguns destes tópicos, como o uso das Redes de Petri como linguagem de especificação de requisitos e de soluções, gerando o problema da verificação formal entre requisitos e design. Terminamos na aula passada introduzindo os conceitos de bissimilarity e bissimulation que estão já fora do escopo do programa desta disciplina. 

    Seguiremos este mesmo curso de discussão para falar sobre um campo bastante promissor e que reune esforço de pesquisa da Engenharia e Ciência da Computação: as redes por objeto. Embora esteja também fora do escopo da disciplina este tópico é muito importante na pesquisa atual e está também ligado aos modelos de verificação formal. Além de permitir uma visão abstrata do espaço de estados, esta abordagem facilita a reutilização e agentes e modelos, além do uso de herança e polimorfismo. Trataremos desses tópicos com o foco em aplicações, mais do que na base formal. Reduções do modelo global também ser!ao abordadas como as "tagged nets" e as redes aninhadas.

     

  • Quadro de Notas

    O quadro de notas segue o critério descrito nas primeiras aula: a média das listas de exercício e milestones vale 40% e o artigo final 60%. O equilíbrio é dado pelo fato do resultado final (artigo) ser derivado dos milestones (embora seja possível fazer diretamente o artigo). A idéia é beneficiar quem acompanhou o curso, ainda que tenha errado nas listas ou na elaboração do artigo.


    Boas férias a todos!