Verificação formal automatizada para sistemas de raciocínio procedural (PRS) utilizando redes de petri coloridas (RPC)

Este trabalho apresenta uma técnica de verificação formal de Sistemas de Raciocínio Procedural, PRS (Procedural Reasoning System), uma linguagem de programação que utiliza a abordagem do raciocínio procedural. Esta técnica baseia-se na utilização de regras de conversão entre programas PRS e Redes de Petri Coloridas (RPC). Para isso, são apresentadas regras de conversão de um sub-conjunto bem expressivo da maioria da sintaxe utilizada na linguagem PRS para RPC. A fim de proceder fia verificação formal do programa PRS especificado, uma vez que se disponha da rede de Petri equivalente ao programa PRS, utilizamos o formalismo das RPCs (verificação das propriedades estruturais e comportamentais) para analisarmos formalmente o programa PRS equivalente. Utilizamos uma ferramenta computacional disponível para desenhar, simular e analisar as redes de Petri coloridas geradas. Uma vez que disponhamos das regras de conversão PRS-RPC, podemos ser levados a querer fazer esta conversão de maneira estritamente manual. No entanto, a probabilidade de introdução de erros na conversão é grande, fazendo com que o esforço necessário para garantirmos a corretude da conversão manual seja da mesma ordem de grandeza que a eliminação de eventuais erros diretamente no programa PRS original. Assim, a conversão automatizada é de suma importância para evitar que a conversão manual nos leve a erros indesejáveis, podendo invalidar todo o processo de conversão. A principal contribuição deste trabalho de pesquisa diz respeito ao desenvolvimento de uma técnica de verificação formal automatizada que consiste basicamente em duas etapas distintas, embora inter-relacionadas. A primeira fase diz respeito fias regras de conversão de PRS para RPC. A segunda fase é concernente ao desenvolvimento de um conversor para fazer a transformação de maneira automatizada dos programas PRS para as RPCs. A conversão automática é possível, porque todas as regras de conversão apresentadas seguem leis de formação genéricas, passíveis de serem incluídas em algoritmos

Arquitetura multiprocessada e reconfigurável para a síntese de redes de Petri em hardware

Uma arquitetura reconfigurável e multiprocessada para a implementação física de Redes de Petri foi desenvolvida em VHDL e mapeada sobre um FPGA. Convencionalmente, as Redes de Petri são transformadas em uma linguagem de descrição de hardware no nível de transferências entre registradores e um processo de síntese de alto nível é utilizado para gerar as funções booleanas e tabelas de transição de estado para que se possa, finalmente, mapeá-las num FPGA (Morris et al., 2000) (Soto and Pereira, 2001). A arquitetura proposta possui blocos lógicos reconfiguráveis desenvolvidos exclusivamente para a implementação dos lugares e das transições da rede, não sendo necessária a descrição da rede em níveis de abstração intermediários e nem a utilização de um processo de síntese para realizar o mapeamento da rede na arquitetura. A arquitetura permite o mapeamento de modelos de Redes de Petri com diferenciação entre as marcas e associação de tempo no disparo das transições, sendo composta por um arranjo de processadores reconfiguráveis, cada um dos quais representando o comportamento de uma transição da Rede de Petri a ser mapeada e por um sistema de comunicação, implementado por um conjunto de roteadores que são capazes de enviar pacotes de dados de um processador reconfigurável a outro. A arquitetura proposta foi validada num FPGA de 10.570 elementos lógicos com uma topologia que permitiu a implementação de Redes de Petri de até 9 transições e 36 lugares, atingindo uma latência de 15,4ns e uma vazão de até 17,12GB/s com uma freqüência de operação de 64,58MHz.

Ferramentas para a integração de redes de Petri e VHDL na síntese de sistemas digitais

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Comparação de técnicas de redes de Petri na descrição de um pipeline

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Desenvolvimento de uma arquitetura multiprocessada e reconfigurável para a síntese de redes de Petri em hardware

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Algoritmo para la simulación paralela de redes de petri temporizadas

[ES] Se propone un algoritmo para para paralelizar la simulación de un modelo realizado mediante una red de Petri temporizada con el objeto de disminuir su tiempo de ejecución.

Las Redes de Petri Interpretadas en el Diagnóstico de Fallos de Sistemas Híbridos. Aplicación a un Helicóptero no Tripulado

La seguridad y fiabilidad de los procesos industriales son la principal preocupación de los ingenieros encargados de las plantas industriales. Por lo tanto, desde un punto de vista económico, el objetivo principal es reducir el costo del mantenimiento, el tiempo de inactividad y las pérdidas causadas por los fallos. Por otra parte, la seguridad de los operadores, que afecta a los aspectos sociales y económicos, es el factor más relevante a considerar en cualquier sistema Debido a esto, el diagnóstico de fallos se ha convertido en un foco importante de interés para los investigadores de todo el mundo e ingenieros en la industria. Los principales trabajos enfocados en detección de fallos se basan en modelos de los procesos. Existen diferentes técnicas para el modelado de procesos industriales tales como máquinas de estado, árboles de decisión y Redes de Petri (RdP). Por lo tanto, esta tesis se centra en el modelado de procesos utilizando redes de petri interpretadas. Redes de Petri es una herramienta usada en el modelado gráfico y matemático con la habilidad para describir información de los sistemas de una manera concurrente, paralela, asincrona, distribuida y no determinística o estocástica. RdP son también una herramienta de comunicación visual gráfica útil como lo son las cartas de flujo o diagramas de bloques. Adicionalmente, las marcas de las RdP simulan la dinámica y concurrencia de los sistemas. Finalmente, ellas tienen la capacidad de definir ecuaciones de estado específicas, ecuaciones algebraicas y otros modelos que representan el comportamiento común de los sistemas. Entre los diferentes tipos de redes de petri (Interpretadas, Coloreadas, etc.), este trabajo de investigación trata con redes de petri interpretadas principalmente debido a características tales como sincronización, lugares temporizados, aparte de su capacidad para procesamiento de datos. Esta investigación comienza con el proceso para diseñar y construir el modelo y diagnosticador para detectar fallos definitivos, posteriormente, la dinámica temporal fue adicionada para detectar fallos intermitentes. Dos procesos industriales, concretamente un HVAC (Calefacción, Ventilación y Aire Acondicionado) y un Proceso de Envasado de Líquidos fueron usados como banco de pruebas para implementar la herramienta de diagnóstico de fallos (FD) creada. Finalmente, su capacidad de diagnóstico fue ampliada en orden a detectar fallos en sistemas híbridos. Finalmente, un pequeño helicóptero no tripulado fue elegido como ejemplo de sistema donde la seguridad es un desafío, y las técnicas de detección de fallos desarrolladas en esta tesis llevan a ser una herramienta valorada, desde que los accidentes de las aeronaves no tripuladas (UAVs) envuelven un alto costo económico y son la principal razón para introducir restricciones de volar sobre áreas pobladas. Así, este trabajo introduce un proceso sistemático para construir un Diagnosticador de Fallos del sistema mencionado basado en RdR Esta novedosa herramienta es capaz de detectar fallos definitivos e intermitentes. El trabajo realizado es discutido desde un punto de vista teórico y práctico. El procedimiento comienza con la división del sistema en subsistemas para seguido integrar en una RdP diagnosticadora global que es capaz de monitorear el sistema completo y mostrar las variables críticas al operador en orden a determinar la salud del UAV, para de esta manera prevenir accidentes. Un Sistema de Adquisición de Datos (DAQ) ha sido también diseñado para recoger datos durante los vuelos y alimentar la RdP diagnosticadora. Vuelos reales realizados bajo condiciones normales y de fallo han sido requeridos para llevar a cabo la configuración del diagnosticador y verificar su comportamiento. Vale la pena señalar que un alto riesgo fue asumido en la generación de fallos durante los vuelos, a pesar de eso esto permitió recoger datos básicos para desarrollar el diagnóstico de fallos, técnicas de aislamiento, protocolos de mantenimiento, modelos de comportamiento, etc. Finalmente, un resumen de la validación de resultados obtenidos durante las pruebas de vuelo es también incluido. Un extensivo uso de esta herramienta mejorará los protocolos de mantenimiento para UAVs (especialmente helicópteros) y permite establecer recomendaciones en regulaciones. El uso del diagnosticador usando redes de petri es considerado un novedoso enfoque. ABSTRACT Safety and reliability of industrial processes are the main concern of the engineers in charge of industrial plants. Thus, from an economic point of view, the main goal is to reduce the maintenance downtime cost and the losses caused by failures. Moreover, the safety of the operators, which affects to social and economic aspects, is the most relevant factor to consider in any system. Due to this, fault diagnosis has become a relevant focus of interest for worldwide researchers and engineers in the industry. The main works focused on failure detection are based on models of the processes. There are different techniques for modelling industrial processes such as state machines, decision trees and Petri Nets (PN). Thus, this Thesis is focused on modelling processes by using Interpreted Petri Nets. Petri Nets is a tool used in the graphic and mathematical modelling with ability to describe information of the systems in a concurrent, parallel, asynchronous, distributed and not deterministic or stochastic manner. PNs are also useful graphical visual communication tools as flow chart or block diagram. Additionally, the marks of the PN simulate the dynamics and concurrence of the systems. Finally, they are able to define specific state equations, algebraic equations and other models that represent the common behaviour of systems. Among the different types of PN (Interpreted, Coloured, etc.), this research work deals with the interpreted Petri Nets mainly due to features such as synchronization capabilities, timed places, apart from their capability for processing data. This Research begins with the process for designing and building the model and diagnoser to detect permanent faults, subsequently, the temporal dynamic was added for detecting intermittent faults. Two industrial processes, namely HVAC (Heating, Ventilation and Air Condition) and Liquids Packaging Process were used as testbed for implementing the Fault Diagnosis (FD) tool created. Finally, its diagnostic capability was enhanced in order to detect faults in hybrid systems. Finally, a small unmanned helicopter was chosen as example of system where safety is a challenge and fault detection techniques developed in this Thesis turn out to be a valuable tool since UAVs accidents involve high economic cost and are the main reason for setting restrictions to fly over populated areas. Thus, this work introduces a systematic process for building a Fault Diagnoser of the mentioned system based on Petri Nets. This novel tool is able to detect both intermittent and permanent faults. The work carried out is discussed from theoretical and practical point of view. The procedure begins with a division of the system into subsystems for further integration into a global PN diagnoser that is able to monitor the whole system and show critical variables to the operator in order to determine the UAV health, preventing accidents in this manner. A Data Acquisition System (DAQ) has been also designed for collecting data during the flights and feed PN Diagnoser. Real flights carried out under nominal and failure conditions have been required to perform the diagnoser setup and verify its performance. It is worth noting that a high risk was assumed in the generation of faults during the flights, nevertheless this allowed collecting basic data so as to develop fault diagnosis, isolations techniques, maintenance protocols, behaviour models, etc. Finally, a summary of the validation results obtained during real flight tests is also included. An extensive use of this tool will improve preventive maintenance protocols for UAVs (especially helicopters) and allow establishing recommendations in regulations. The use of the diagnoser by using Petri Nets is considered as novel approach.

Verificación de extensiones de Redes de Petri con precios, tiempo y múltiples instancias

Las redes de Petri son un lenguaje formal muy adecuado para la modelizacíon, ańalisis y verificacíon de sistemas concurrentes con infinitos estados. En particular, son muy apropiadas para estudiar las propiedades de seguridad de dichos sistemas, dadas sus buenas propiedades de decidibilidad. Sin embargo, en muchas ocasiones las redes de Petri carecen de la expresividad necesaria para representar algunas caracteŕısticas fundamentales de los sistemas que se manejan hoy en d́ıa, como el manejo de tiempo real, costes reales, o la presencia de varios procesos con un ńumero no acotado de estados ejecut́andose en paralelo. En la literatura se han definido y estudiado algunas extensiones de las redes de Petri para la representaci ́on de las caracteŕısticas anteriores. Por ejemplo, las “Redes de Petri Temporizadas” [83, 10](TPN) incluyen el manejo de tiempo real y las ν-redes de Petri [78](ν-PN) son capaces de representar un ńumero no acotado de procesos con infinitos estados ejecut́andose concurrentemente. En esta tesis definimos varias extensiones que réunen estas dos caracteŕısticas y estudiamos sus propiedades de decidibilidad. En primer lugar definimos las “ν-Redes de Petri Temporizadas”, que réunen las caracteŕısticas expresivas de las TPN y las ν-PN. Este nuevo modelo es capaz de representar sistemas con un ńumero no acotado de procesos o instancias, donde cada proceso es representado por un nombre diferente, y tiene un ńumero no acotado de relojes reales. En este modelo un reloj de una instancia debe satisfacer ciertas condiciones (pertenecer a un intervalo dado) para formar parte en el disparo de una transicíon. Desafortunadamente, demostramos que la verificacíon de propiedades de seguridad es indecidible para este modelo...

Extração de casos de teste utilizando Redes de Petri hierárquicas e validação de resultados utilizando OWL.

Este trabalho propõe dois métodos para teste de sistemas de software: o primeiro extrai ideias de teste de um modelo desenvolvido em rede de Petri hierárquica e o segundo valida os resultados após a realização dos testes utilizando um modelo em OWL-S. Estes processos aumentam a qualidade do sistema desenvolvido ao reduzir o risco de uma cobertura insuficiente ou teste incompleto de uma funcionalidade. A primeira técnica apresentada consiste de cinco etapas: i) avaliação do sistema e identificação dos módulos e entidades separáveis, ii) levantamento dos estados e transições, iii) modelagem do sistema (bottom-up), iv) validação do modelo criado avaliando o fluxo de cada funcionalidade e v) extração dos casos de teste usando uma das três coberturas de teste apresentada. O segundo método deve ser aplicado após a realização dos testes e possui cinco passos: i) primeiro constrói-se um modelo em OWL (Web Ontology Language) do sistema contendo todas as informações significativas sobre as regras de negócio da aplicação, identificando as classes, propriedades e axiomas que o regem; ii) em seguida o status inicial antes da execução é representado no modelo através da inserção das instâncias (indivíduos) presentes; iii) após a execução dos casos de testes, a situação do modelo deve ser atualizada inserindo (sem apagar as instâncias já existentes) as instâncias que representam a nova situação da aplicação; iv) próximo passo consiste em utilizar um reasoner para fazer as inferências do modelo OWL verificando se o modelo mantém a consistência, ou seja, se não existem erros na aplicação; v) finalmente, as instâncias do status inicial são comparadas com as instâncias do status final, verificando se os elementos foram alterados, criados ou apagados corretamente. O processo proposto é indicado principalmente para testes funcionais de caixa-preta, mas pode ser facilmente adaptado para testes em caixa branca. Obtiveram-se casos de testes semelhantes aos que seriam obtidos em uma análise manual mantendo a mesma cobertura do sistema. A validação provou-se condizente com os resultados esperados, bem como o modelo ontológico mostrouse bem fácil e intuitivo para aplicar manutenções.

WI-BIO: redes de monitoramento de pacientes em ambientes de automação hospitalar utilizando o padrão IEEE 802.11

The monitoring of patients performed in hospitals is usually done either in a manual or semiautomated way, where the members of the healthcare team must constantly visit the patients to ascertain the health condition in which they are. The adoption of this procedure, however, compromises the quality of the monitoring conducted since the shortage of physical and human resources in hospitals tends to overwhelm members of the healthcare team, preventing them from moving to patients with adequate frequency. Given this, many existing works in the literature specify alternatives aimed at improving this monitoring through the use of wireless networks. In these works, the network is only intended for data traffic generated by medical sensors and there is no possibility of it being allocated for the transmission of data from applications present in existing user stations in the hospital. However, in the case of hospital automation environments, this aspect is a negative point, considering that the data generated in such applications can be directly related to the patient monitoring conducted. Thus, this thesis defines Wi-Bio as a communication protocol aimed at the establishment of IEEE 802.11 networks for patient monitoring, capable of enabling the harmonious coexistence among the traffic generated by medical sensors and user stations. The formal specification and verification of Wi-Bio were made through the design and analysis of Petri net models. Its validation was performed through simulations with the Network Simulator 2 (NS2) tool. The simulations of NS2 were designed to portray a real patient monitoring environment corresponding to a floor of the nursing wards sector of the University Hospital Onofre Lopes (HUOL), located at Natal, Rio Grande do Norte. Moreover, in order to verify the feasibility of Wi-Bio in terms of wireless networks standards prevailing in the market, the testing scenario was also simulated under a perspective in which the network elements used the HCCA access mechanism described in the IEEE 802.11e amendment. The results confirmed the validity of the designed Petri nets and showed that Wi-Bio, in addition to presenting a superior performance compared to HCCA on most items analyzed, was also able to promote efficient integration between the data generated by medical sensors and user applications on the same wireless network

Proposta para minimizar penalidade do tráfego de melhor esforço (BE) em redes óticas passivas ethernet (EPON): análise através de modelo híbrido analítico/simulado

Neste trabalho, propõe-se uma melhoria na estratégia de escalonamento baseada em pesos das classes de tráfego em redes óticas passivas Ethernet – EPON, de modo a não penalizar demasiadamente a classe tipo melhor esforço (BE). Como suporte, desenvolveu-se um modelo híbrido analítico/simulado para análise de desempenho do fluxo de subida, baseado no atraso total de quadros. A modelagem foi feita utilizando Redes de Petri Coloridas Estocásticas (Stochastic Colored Petri Nets - SCPN) da qual se obtém, por simulação, o tamanho médio da fila que posteriormente é usado para, analiticamente, obter-se o atraso total. Não obstante ao crescimento de aplicações multimídia em tempo real, no ano de 2010, o tráfego tradicional na Internet (navegação web, email, mensagens instantâneas) classificado como melhor esforço ainda foi responsável, sozinho (excluindo transferência de arquivos P2P), por valores em torno de 18% do tráfego na Internet. Somando-se a este percentual as aplicações P2P, que também não são essencialmente sensíveis ao atraso, têm-se uma participação de 58% (o tráfego P2P foi no ano de 2010 responsável por aproximadamente 40% do volume total de informações trafegadas na Internet). Mesmo em previsões feitas para o ano de 2014 o tráfego BE ainda representará aproximadamente 40% do volume total de dados a serem trafegados nas redes IPs mundiais. Estes números demonstram que a preocupação com este tipo de tráfego não pode ser relegada a uma importância secundária em detrimento às aplicações que exigem maior qualidade de serviço. Tomando como base o escalonamento IPACT (Interleaved Polling with Adapting Cycle Time) esta dissertação demonstra que é possível, através da melhoria proposta, obter atrasos menores no tráfego de melhor esforço, sem que as classes de tráfego prioritárias ultrapassem as especificações de atraso recomendadas para cada uma destas.

Optimizing urban traffic flow using genetic algorithm with petri net analysis as fitness function

This paper describes a new methodology adopted for urban traffic stream optimization. By using Petri net analysis as fitness function of a Genetic Algorithm, an entire urban road network is controlled in real time. With the advent of new technologies that have been published, particularly focusing on communications among vehicles and roads infrastructures, we consider that vehicles can provide their positions and their destinations to a central server so that it is able to calculate the best route for one of them. Our tests concentrate on comparisons between the proposed approach and other algorithms that are currently used for the same purpose, being possible to conclude that our algorithm optimizes traffic in a relevant manner.

Modelagem e análise das cadeias de suprimentos globais e resilientes baseadas em rede de Petri.

Em um cenário de aumento de competitividade, crescente expectativa por inovações do produto e necessidade de atender diferentes perfis de consumidores, o conceito de gerenciamento de cadeias de suprimentos globais (GSCM) surge como uma estratégia para coordenar mais eficazmente as atividades dispersas geograficamente dos sistemas produtivos. Na adoção do GSCM, as organizações devem lidar com rupturas que impactam no gerenciamento das suas atividades, tais como a interrupção de vias de transporte, pane no fornecimento de energia, desastres naturais e até ataques terroristas. Nesse contexto, o trabalho introduz um procedimento sistematizado para modelagem das cadeias de suprimentos visto como um sistema a eventos discretos e sua análise por simulação das atividades do GSCM baseada em técnicas formais como a rede de Petri (PN) e o Production Flow Schema (PFS). Um exemplo é também apresentado para ilustrar e comprovar as vantagens do método proposto na análise do GSCM.

Modelado de sistemas concurrentes con OMNeT++

El objetivo del siguiente proyecto es proporcionar una herramienta para estudiar el rendimiento de sistemas multiprocesador. Para ello estos sistemas serán previamente modelados como redes de Petri y simulados mediante el entorno de simulación de sistemas de eventos discretos OMNeT++.

Grafos internos e multirrelações como "spans" : propriedades e composicionalidade

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.