Este trabalho define um modelo de execução para cláusulas Prolog, a partir do modelo abstrato de Máquinas de Cláusulas, e o Projeto de uma arquitetura paralela que suporte o modelo proposto. São também introduzidos alguns aspectos sobre as linguagens Lógicas e as máquinas Prolog visto que estes elementos estão relacionados intimamente tanto com o modelo quanto com a arquitetura propostos. Na proposta do modelo de execução são definidos uma representação para os elementos do modelo abstrato (predicados, arcos e clausulas) e um conjunto de algoritmos que permitem a operacionalização do modelo de forma a que tanto o paralelismo como a concorrência inerentes ao modelo abstrato sejam exploradas de forma integral. Na proposta da arquitetura são, primeiramente, discutidas algumas opções de arquitetura básica e, posteriormente, descrita a arquitetura escolhida tanto a nível de blocos bem como dos seus componentes principais, a saber: interface de mem6ria, processador e rede de interconexão. Para cada um destes componentes são descritas as principais instruções e são apresentados os algoritmos que as implementam. Junto com a descrição da arquitetura é definida uma estrutura de dados que permite a implementação da representação descrita no modelo de execuqao e é definido também o algoritmo de unificação que percorre a estrutura proposta. Na validação é feito o cálculo da largura de banda máxima alcançada pela arquitetura proposta, calculo este baseado no algoritmo de unificação descrito. E também feita uma avaliação do ganho de performance da arquitetura proposta em relação a um processador bem como é justificado o numero de processadores escolhidos comparando a performance alcançada na arquitetura proposta com a performance alcançada por conjuntos maiores e menores de processadores. Por fim na conclusa o são feitos comentários sobre os objetivos atingidos e sobre possíveis extensões a este trabalho. / The present work defines a execution model for Prolog clauses based on the clause machines abstract model and then proposes a parallel architecture for the execution model. Some topics about Logic languages and Prolog machines were therefore introduced because they are closely related with, both, the model and the architecture proposed. In the execution model the representation of the abstract model elements (predicates, arcs and clauses) and the set of algoritms that allow the operation of the model were defined so that the parallelism of the model can be integraly achieved. In the architecture proposal, first some options for the basic architecture were discussed and then the chosen architecture is describeb at block level as much as at its components level. The most importants components reported are the memory interface, the processor and the interconection net, for each one of them the possible instructions were describeb as well as their algoritms. Together with the especification of the architecture, the data estructure that allows the implementation of the execution model representation and the concerning unification algorit that scans the proposed representation were especified too. In the validation the thoughtput permited by the proposal architecture is calculated based on the unification algoritm earlier described. Besides that the performance gain compared with an architecture with only one processor was estimated, as much as the confrontation of the performance of lesser and greater sets of processors elements were made in order to validate the chossen number. At last, in the conclusion, some coments about the fulfilled goals and about eventual extends for the work.

No presente trabalho serão apresentadas questões usuais em jogos diferenciais, nos quais os jogadores envolvidos têm objetivos diferentes; ou seja, enquanto um dos jogadores tenta fugir, o outro tenta pegar. Além disso, será definido um modelo de especificação para o jogo diferencial lobos e cordeiro. As Redes de Petri foram escolhidas como forma de especificação para o jogo proposto. Assim, o objetivo será estabelecer estratégias eficientes para o jogo lobos e cordeiro para que se possa realizar um estudo da complexidade das questões apresentadas para este jogo, levando-se em consideração a especificação formal apresentada para tal jogo. / In this work usual questions in differential games will be presented, in which the involved players have different objectives; that is, while one of the players tries "to run away", the other tries "to catch". Moreover, a specification for the differential game "wolves and lamb" will be defined. The Petri Nets had been chosen as specification formalism for the considered game. Thus, the objective is to establish efficient strategies for the game wolves and lamb so that we can carry out a study of the complexity of the presented questions, taking into consideration the presented formal specification for the game.

Uma vez que uma aplicação ou projeto tenha sido identificado como sujeito ao uso da simulação, decisões devem ser tomadas acerca de como conduzir os estudos. Embora não haja regras definitivas, alguns passos são geralmente recomendados, tais como: planejamento do estudo, definição do sistema, construção do modelo, execução dos experimentos, análise dos resultados e relatório final. E, a construção do modelo é uma das etapas mais demoradas e complexas. Na execução dos experimentos, e na análise dos resultados a Realidade Virtual (RV) é uma interface que pode fornecer um suporte importante para a tomada de decisões, pois a RV auxilia na criação de mundos virtuais semelhantes ao mundo real, que ajudam na compreensão do funcionamento dos sistemas. Este trabalho propõe um metamodelo para o desenvolvimento de sistemas de simulação de eventos discretos com interface de RV aplicados a ambientes ou estações de trabalho de manufatura. A proposta do metamodelo é composto por quatro módulos: i) de edição e validação de modelos, ii) de criação, edição e execução de ambientes virtuais, iii) de conexão para efetuar o elo entre os dois primeiros módulos e, iv) de controle para gerenciar a comunicação e controlar a simulação. Como resultado tem-se a simulação centralizada baseada no modelo descrito em Rede de Petris (RP) com interface de RV distribuída. O sistema computacional gerado pelo metamodelo auxiliará no aprendizado e compreensão do problema simulado, e ainda permitirá ao usuário o envolvimento através da iteração. / The VR aids in the creation of virtual worlds similar to the real world, helping in understanding how a system works. This research work is concerned with the development of a discrete-event system simulation based on Petri Nets, with Virtual Reality interface for manufacturing environment or workstations. The system is composed of four modules, the first is model editing and validation, the second module is a modeling tool for virtual objects and/or a library of virtual elements, the third module makes the link between the two previous modules, and finally, the fourth is a simulation and control module. The centralized simulation is based on models described by Petri Nets with distributed RV interface resulting in a flexible and consistent system. The system will help users in learning and understanding the simulation problem, and it will also allow the user\'s integration with the environment through the interaction, and through distributed interface.

A competição no mercado globalizado, do ponto de vista do consumidor, aumentou consideravelmente a oferta de produtos e serviços, permitindo a escolha pela qualidade, preço, prazos e/ou disponibilidade. Entretanto, do ponto de vista das empresas, o desafio de atuar em um mercado saturado, dinâmico, competitivo e com aumento da demanda de produção orientado ao consumidor altera consideravelmente toda a estrutura da empresa. Desta forma, a flexibilidade torna-se um pré-requisito fundamental para que as empresas possam atuar neste mercado. Considerando-se o contexto apresentado, o objeto de estudo do presente trabalho são os Sistemas Produtivos Flexíveis (SPFs). Os SPFs são sistemas concebidos para atender às necessidades de um mercado dinâmico e competitivo. Isto causa complexidade no comportamento global desses sistemas exigindo diferentes propostas para o projeto de Sistemas de Controle de SPFs. A complexidade advém do fato de se perder a informação quanto ao pré-determinismo da seqüência de eventos que ocorrem no sistema global, além do fato de não existir previamente a definição de todos os processos de transporte com a designação prévia de todas as ordens de transporte que os transportadores presentes na planta devem executar. Neste contexto, o objetivo deste trabalho é apresentar como resultado uma proposta de sistema de controle modular para SPFs que atenda os requisitos de fluxo de informações envolvendo hierarquia e colaboração simultânea entre os módulos, respeitando a diversidade semântica presente na arquitetura. Apresenta-se então uma sistematização de projeto dos diversos módulos de controle e uma proposta de implementação de um algoritmo de designação dos transportadores para ser utilizado em tempo real permitindo a realização eficiente das atividades de transporte. / The competition in the globalized market increased considerably the demand for products and services to the customer point of view. However, the consumer\'s driven demand change the whole structure of the company. Thus, flexibility becomes an essential pre-requisite for companies to compete in the market. Considering the context presented, the object of study of this work is the Flexible Production System (FPS). The FPS must fulfill the needs on a dynamic and competitive market. This situation causes complexity in the overall performance of these systems, requiring different proposals for the design of the control systems. The complexity arises due to the fact that loses the information about the sequence of events that occur in the global system. Besides there is no previous exist definition for all processes of transport and prior designation for it. In this context, the objective of this work is to present a proposal for modular control systems to FPS that fits the requirements of information flow involving hierarchy and simultaneous collaboration between the modules. It will be presented systematization for the modular design of control as well as an implementation of an algorithm for designation of transport in real time leading to an efficient management of these activities.

Orientador: Rafael Santos Mendes / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-24T01:12:10Z (GMT). No. of bitstreams: 1 Candido_RenatoMarkeleFerreira_M.pdf: 1921815 bytes, checksum: a5e82ec1bfadd836b1ba66fda5ce00ec (MD5) Previous issue date: 2013 / Resumo: A principal contribuição desta dissertação é a proposta de algoritmos de filtragem por partículas em sistemas a eventos discretos nos quais predominam os problemas de sincronização. Esta classe de sistemas pode ser descrita por meio de equações lineares em uma álgebra não convencional usualmente conhecida como álgebra Max Plus. Os Filtros de Partículas são algoritmos Bayesianos sub-ótimos que realizam uma amostragem sequencial de Monte Carlo para construir uma aproximação discreta da densidade de probabilidade dos estados baseada em um conjunto de partículas com pesos associados. É apresentada uma revisão de sistemas a eventos discretos, de filtragem não linear e de filtros de partículas de um modo geral. Após apresentar esta base teórica, são propostos dois algoritmos de filtros de partículas aplicados a sistemas Max Plus. Em seguida algumas simulações foram apresentadas e os resultados apresentados mostraram a eficiência dos filtros desenvolvidos / Abstract: This thesis proposes, as its main contribution, particle filtering algorithms for discrete event systems in which synchronization phenomena are prevalent. This class of systems can be described by linear equation systems in a nonconventional algebra commonly known as Max Plus algebra. Particles Filters are suboptimal Bayesian algorithms that perform a sequential Monte Carlo sampling to construct a discrete approximation of the probability density of states based on a set of particles with associated weights. It is presented a review of discrete event systems, nonlinear filtering and particle filters. After presenting this theoretical background, two particle filtering algorithms applied to Max Plus systems are proposed. Finally some simulation results are presented, confirming the accuracy of the designed filters / Mestrado / Automação / Mestre em Engenharia Elétrica

Les systèmes actuels deviennent chaque jour de plus en plus complexe; à la distribution s’ajoutent les contraintes temps réel. Les méthodes classiques en charge de garantir la sûreté de fonctionnement, comme le test, l’injection de fautes ou les méthodes formelles ne sont plus suffisantes à elles seules. Afin de pouvoir traiter les éventuelles erreurs lors de leur apparition dans un système distribué donné, nous désirons mettre en place un programme, surveillant ce système, capable de lancer une alerte lorsque ce dernier s’éloigne de ses spécifications ; un tel programme est appelé superviseur (ou moniteur). Le fonctionnement d’un superviseur consiste simplement à interpréter un ensemble d’informations provenant du système sous forme de message, que l’on qualifiera d’évènement, et d’en déduire un diagnostic. L’objectif de cette thèse est de mettre un place un superviseur distribué permettant de vérifier en temps réel des propriétés temporelles. En particulier nous souhaitons que notre moniteur soit capable de vérifier un maximum de propriétés avec un minimum d’information. Ainsi notre outil est spécialement conçu pour fonctionner parfaitement même si l’observation est imparfaite, c’est-à-dire, même si certains évènements arrivent en retard ou s’ils ne sont jamais reçus. Nous avons de plus cherché à atteindre cet objectif de manière distribuée pour des raisons évidentes de performance et de tolérance aux fautes. Nous avons ainsi proposé un protocole distribuable fondé sur l’exécution répartie d’un réseau de Petri temporisé. Pour vérifier la faisabilité et l’efficacité de notre approche, nous avons mis en place une implémentation appelée Minotor qui s’est révélée avoir de très bonnes performances. Enfin, pour montrer l’expressivité du formalisme utilisé pour exprimer les spécifications que l’on désire vérifier, nous avons détaillé un ensemble de propriétés sous forme de réseaux de Petri à double sémantique introduite dans cette thèse (l’ensemble des transitions étant partitionné en deux catégories de transitions, chacune de ces parties ayant sa propre sémantique). / Current systems are becoming every day more and more complex, being both distributed and real-timed. Conventional methods responsible for guaranteeing dependability, such as testing, fault injection or formal methods are no longer sufficient. In order to process any errors when they appear in a given distributed system, we want to implement a software monitoring it and capable of launching an alert when the system does not respect anymore its specification. Such a program is called monitor. A monitor interpret information received from the system as messages (these messages are called events) and propose a diagnosis. The objective of this thesis is to set in place a monitor for a distributed real-time verification of temporal properties. In particular we want our monitor to be able to check up a maximum of properties with a minimum of information. Thus, our tools are designed to work perfectly even if the observation is imperfect, that is to say, even if some events are late or never received. We have also managed to achieve this goal through a highly distributed protocol. To verify the feasibility and effectiveness of our approach, we have established an implementation called Minotor who was found to have very good performance. Finally, we detailed a set of properties, expressed in our formalism, to show it’s expressiveness.

Sistemas Reativos caracterizam-se por reagir continuamente a estímulos externos e internos e controlar atividades humanas. A ocorrência de falhas nesses sistemas pode resultar em grandes prejuízos. Dessa forma, o uso de métodos e técnicas rigorosas para a especificação do comportamento desse tipo de sistema é essencial, buscando-se evitar inconsistências e ambigüidades no modelo. Redes de Petri é uma das técnicas que têm sido usadas para a especificação de sistemas reativos. Teste e validação são atividades essenciais na produção dessa classe de sistemas. Por isso, o critério Análise de Mutantes, um critério de teste baseado em erros normalmente aplicado ao teste de programas, tem sido explorado no contexto de teste de especificações de sistemas reativos. É necessário o desenvolvimento de ferramentas que apóiem sua utilização, visto que a aplicação manual do critério é impraticável. O objetivo deste trabalho é a implementação da ferramenta Proteum-RS/PN, que apóia a aplicação do critério Análise de Mutantes para validar especificações baseadas em Redes de Petri. / Reactive Systems are characterized by continuously reacting to external as well as internal stimuli and controlling human activities. In these systems, faults can result in large losses. The use of rigorous methods and techniques for the specification of their behavior is essential to avoid inconsistencies and ambiguities. Petri Nets have been used for reactive-system specification. The test and validation of the underlying model are essential activities for the production of such systems. Thus, the Mutant Analysis -- a fault-based criterion usually used for program testing -- has been explored in the context of specification testing. The development of tools to support its application is necessary, since its manual application is unrealistic. The objective of this work is the implementation of Proteum-RS/PN, a testing tool which supports the application of Mutant Analysis criterion to validate Petri-Nets based specifications.

Coloured Petri nets (CPN) are an extension of a standard place-transition Petri nets (P/T PN). Every token and place have its type (and eventually a value) and various inscriptions can be inserted into the net. CPN excel with great readibility and expresivity. At the same time, they carry a well-defined formal basis, which eases its computer simulation and allows limited verification of certain attributes to be performed. Motivation for doing this project is the simple fact that currently only one public software tool is available for CPN creation and simulation - CPNTools developed on the Aarhus university. The program, however, is quite complicated and hard to handle for an unexperienced user. The goal is to research capabilities and properties of both CPNs and CPNTools and on this basis design and implement a didactic application with swift and intuitive interface that helps users without deeper theoretical insight to get a grasp of the problematics.

Le " serious gaming " est une approche récente pour mener des activités " sérieuses " telles que communiquer, sensibiliser ou apprendre, en utilisant les techniques mises en œuvre dans les jeux vidéo. Les jeux sérieux sont devenus aujourd'hui un élément incontournable de la formation en ligne. C'est dans ce cadre du serious gaming pour la formation que se situe ce sujet de thèse. En effet, quelle que soit l'acception privilégiée, de nombreuses questions de recherche se posent. En particulier, comment peut-on évaluer les connaissances acquises par le joueur/apprenant à travers le jeu ? Nous sommes concentrés sur les jeux de type étude de cas utilisés notamment en gestion ou en médecine et proposons une méthode basée sur l'Evidence Centered Design pour concevoir le suivi de l'apprenant à des fins de diagnostic à destination de l'enseignant et de l'apprenant. Les actions liées aux études de cas sont très proches des actions métiers et recourent à des règles bien précises. Nous avons fait le choix de les représenter à l'aide de réseaux de Petri. Pour apporter de la sémantique à l'analyse par réseau de Petri, nous l'avons adossé à une ontologie du domaine et des actions de jeu. L'ontologie apporte une complémentarité non négligeable au réseau de Petri qui a une dimension purement procédurale. Nous combinons des réseaux de Petri et les ontologies afin de produire des indicateurs de performance pour cette catégorie particulière de jeux sérieux. L'étude des erreurs nous a conduits à proposer une taxinomie particulière pour les jeux sérieux en nous inspirant notamment des travaux réalisés dans le domaine de la sécurité. / "Serious gaming" is a recent approach, using the techniques implemented in video games, to conduct "serious" activities such as communication, awareness and learning. Serious games have now become an essential element of online training. This thesis takes place in the context of serious games for training. Indeed, whatever the preferred meaning, many research questions arise. In particular, how can we assess the knowledge acquired by the player / learner through the game? We have focused on case study type games used especially in management or medicine. We propose a method based on Evidence Centered Design to plan the monitoring of the learner for diagnostic purposes to the teacher and the learner. Actions in case studies are very close to business actions and resort to specific rules. We have chosen to represent them using Petri nets. To bring semantics to the Petri net analysis, we have added a domain and game action ontology. The ontology provides a significant complementarity to Petri net that has a purely procedural dimension. We have combined Petri nets and ontologies to produce performance indicators for this particular category of serious games. The study of errors led us to propose a particular taxonomy for serious games based on the work done in the field of security.

Cette thèse contribue à l’identification de modèles compacts et expressifs de Systèmes à Evénements Discrets (SED) réactifs, à des fins de rétro-conception ou de certification. L’identification est passive, et boîte-noire, la connaissance se limitant aux signaux d’entrées/sorties du système. Les Réseaux de Petri Interprétés (RdPI) permettent de modéliser à la fois le comportement observable (causalités entrées/sorties observées directement), et le comportement non observable du système (évolutions de variables internes). Cette thèse vise à identifier des modèles RdPI à partir d’une séquence observée de vecteurs entrées/sorties. Notamment, l’enjeu étant de traiter des systèmes concurrents de taille réaliste, l’approche développée permet le passage à l’échelle de résultats précédents.La construction de la partie observable est d’abord améliorée par l’ajout d’un filtre. Celui-ci détecte et supprime les synchronisations parasites causées par le contrôleur en présence de systèmes concurrents. Une nouvelle approche est ensuite proposée pour découvrir la partie non observable, basée sur l’utilisation de projections, et garantissant la reproductibilité du comportement observé malgré la concurrence. Une heuristique permet de construire un modèle satisfaisant pour la rétro-ingénierie, à coût de calcul limité. Enfin, une approche distribuée est proposée pour réduire davantage le coût de calcul, en partitionnant automatiquement le système en sous-systèmes. L’effet cumulatif de ces contributions est illustré par l’identification de RdPI sur un système de taille raisonnable, validant leur efficacité. / This thesis proposes a method to identify compact and expressive models of closed-loop reactive Discrete Event Systems (DES), for reverse-engineering or certification. The identification is passive, and blackbox, accessible knowledge being limited to input/output signals. Interpreted Petri Nets (IPN) represent both the observable behaviour (direct input/output causalities) and the unobservable behaviour (internal state evolutions) of the system. This thesis aims at identifying IPN models from an observed sequence of I/O vectors. The proposed contributions extend previous results towards scalability, to deal with realistic systems who exhibit concurrency.Firstly, the construction of the observable part of the IPN is improved by the addition of a filter limiting the effect of concurrency. It detects and removes spurious synchronizations caused by the controller. Then, a new approach is proposed to improve the discovery of the unobservable part. It is based on the use of projections and guarantees the reproduction of the observed behaviour, despite concurrency. An efficient heuristic is proposed to compute a model adapted to reverse-engineering, limiting the computational cost. Finally, a distributed approach is proposed to further reduce the computational cost, by automatically partitioning the system into subsystems. The efficiency of the cumulative effect of these contributions is validated on a system of realistic size.