O presente trabalho trata da verificação e design de sistemas complexos, especificamente da verificação de sistemas de tempo real concorrentes e distribuídos. Propõe-se uma técnica enumerativa para a verificação formal de modelos que permite determinar a validade de propriedades quantitativas, além das qualitativas. A técnica proposta separa a construção do espaço de estados dos algoritmos de rotulação das fórmulas temporais, o que possibilita a diminuição da complexidade do processo de verificação, tornando-o viável para aplicações práticas. A técnica proposta foi inicialmente aplicada sobre modelos de redes de Petri temporizadas e depois em uma rede unificada chamada GHENeSys para aproveitar as características de abstração, hierarquia e de elementos de interação chamados pseudo-boxes. A definição da rede GHENeSys foi modificada para permitir a modelagem de sistemas onde os requisitos temporais devem ser expressos através de atrasos e prazos como e o caso dos sistemas de tempo real. A rede suporta ainda mecanismos de refinamento tanto para os elementos ativos quanto os passivos. A demonstração da manutenção de propriedades como invariantes, vivacidade, limitação assim como da validade de fórmulas lógicas no processo de refinamento constitui um aspecto fundamental no projeto de sistemas complexos, e foi portanto revista em detalhes para a rede GHENeSys. Alguns exemplos práticos são apresentados para avaliar o desempenho dos algoritmos e um estudo de caso finaliza a apresentação, onde se pode contrastar os algoritmos propostos com os implementados na ferramenta UPPAAL. / This work deals with the process of design and verification of complex systems, mainly real time, concurrent and distributed systems. An enumerative technique is proposed for model-checking which is capable of determining both quantitative and qualitative properties. The proposed technique detach the algorithm for labeling the formula being checked from the state space construction, allowing a better result in the verification process. This model-checking approach shows itself valuable in practical applications. This approach was first applied to systems modeled by Time Petri Nets and further extended to a unified net called GHENeSys, which includes abstraction and hierarchy concepts as well as elements for data and control interchange, called pseudo-boxes. The GHENeSys definition was modified in order to deal with systems in which temporal requirements can be expressed through delays and deadlines as in the real-time systems. The GHENeSys environment supports a refinement technique applied to both passive and active elements. Net properties like invariants, liveness, boundedness and also the validity of temporal formulas was proved to be maintained through the refinement process if some conditions are satisfied. Such characteristics are useful to deal with complex systems design. Some experiments based on well known academic articles were used to avaliate the performance of the algorithms and a case study is presented in order to compare obtained results with those obtained using the UPPAAL tool.

O sistema de elevadores como equipamento para o transporte vertical de pessoas e bens é um componente fundamental no projeto de edifícios e, neste âmbito, a disponibilidade e eficiência do seu serviço deve ser objeto de cuidadosa análise em função de sua influência no desempenho e produtividade das atividades dos usuários do prédio. Neste contexto e considerando especificamente os edifícios inteligentes cuja finalidade é a otimização a nível estrutural e funcional do edifício como um todo, e onde a integração entre seus sistemas cumpre um papel fundamental para atingir estes objetivos, o presente trabalho propõe uma metodologia para a modelagem de sistemas de elevadores nestes prédios, que considera a sua integração com outros sistemas prediais. A abordagem empregada no desenvolvimento deste trabalho baseia-se na caracterização dos sistemas de elevadores como sistemas a eventos discretos (SED), pois sua dinâmica é definida através da ocorrência de eventos e a manutenção de estados discretos. Assim, na metodologia utiliza-se técnicas derivadas das redes de Petri (redes de Petri interpretadas), de comprovada eficiência para a modelagem, análise e controle de SEDs. Estas ferramentas são usadas através de uma abordagem estrutural, onde o sistema é modelado em diferentes níveis de abstração: um modelo conceitual obtido pelo uso da técnica PFS (Production Flow Schema) em um primeiro nível, e o refinamento deste para modelos funcionais através do uso do MFG (Mark Flow Graph) e suas extensões, onde são preservadas as estruturas das atividades do nível superior e são descritos os detalhes em um nível funcional. A metodologia proposta confirmou ser útil e eficiente para a modelagem do sistema de elevadores em edifícios inteligentes, ao permitir a especificação do modelo funcional de todo o sistema (objeto de controle e sistema de controle) e das estratégias que facilitam a sua integração com outros sistemas prediais / The elevator system as mean for the vertical transport of people and goods is a fundamental component in the design of buildings. The availability and efficiency of this service must be object of careful analysis due to its influence on the performance and productivity of the building users' activities. In intelligent buildings, the purpose is the optimization of its structural and functional levels and where also the integration between all building systems accomplishes a fundamental role to reach these objectives. In this context, this work proposes a methodology for the modeling of elevator systems in these buildings, which consider your integration with others buildings systems. The approach developed in this work is based on the characterization of elevator systems as Discrete Event Systems (DES), since the dynamic behavior is defined through the discrete events and discrete states. The proposed methodology uses techniques, that are derived of interpreted Petri nets, which has been proven as an efficient tool for modeling, analysis and control of DES. In this context, systems are modeled in different levels of abstraction: a conceptual model which is obtained by using the PFS (Production Flow Schema) technique level, and a functional model by using MFG (Mark Flow Graph) and its extensions. The MFG abstraction level describes details in a functional form, where are preserved the description activities of previous levels. The methodology proposal confirmed to be useful and efficient to elevator systems modeling, when allowing the functional specification of the whole system (object of control and control system), and strategies that facilitate its integration with others building systems.

O sistema de elevadores como equipamento para o transporte vertical de pessoas e bens é um componente fundamental no projeto de edifícios e, neste âmbito, a disponibilidade e eficiência do seu serviço deve ser objeto de cuidadosa análise em função de sua influência no desempenho e produtividade das atividades dos usuários do prédio. Neste contexto e considerando especificamente os edifícios inteligentes cuja finalidade é a otimização a nível estrutural e funcional do edifício como um todo, e onde a integração entre seus sistemas cumpre um papel fundamental para atingir estes objetivos, o presente trabalho propõe uma metodologia para a modelagem de sistemas de elevadores nestes prédios, que considera a sua integração com outros sistemas prediais. A abordagem empregada no desenvolvimento deste trabalho baseia-se na caracterização dos sistemas de elevadores como sistemas a eventos discretos (SED), pois sua dinâmica é definida através da ocorrência de eventos e a manutenção de estados discretos. Assim, na metodologia utiliza-se técnicas derivadas das redes de Petri (redes de Petri interpretadas), de comprovada eficiência para a modelagem, análise e controle de SEDs. Estas ferramentas são usadas através de uma abordagem estrutural, onde o sistema é modelado em diferentes níveis de abstração: um modelo conceitual obtido pelo uso da técnica PFS (Production Flow Schema) em um primeiro nível, e o refinamento deste para modelos funcionais através do uso do MFG (Mark Flow Graph) e suas extensões, onde são preservadas as estruturas das atividades do nível superior e são descritos os detalhes em um nível funcional. A metodologia proposta confirmou ser útil e eficiente para a modelagem do sistema de elevadores em edifícios inteligentes, ao permitir a especificação do modelo funcional de todo o sistema (objeto de controle e sistema de controle) e das estratégias que facilitam a sua integração com outros sistemas prediais / The elevator system as mean for the vertical transport of people and goods is a fundamental component in the design of buildings. The availability and efficiency of this service must be object of careful analysis due to its influence on the performance and productivity of the building users' activities. In intelligent buildings, the purpose is the optimization of its structural and functional levels and where also the integration between all building systems accomplishes a fundamental role to reach these objectives. In this context, this work proposes a methodology for the modeling of elevator systems in these buildings, which consider your integration with others buildings systems. The approach developed in this work is based on the characterization of elevator systems as Discrete Event Systems (DES), since the dynamic behavior is defined through the discrete events and discrete states. The proposed methodology uses techniques, that are derived of interpreted Petri nets, which has been proven as an efficient tool for modeling, analysis and control of DES. In this context, systems are modeled in different levels of abstraction: a conceptual model which is obtained by using the PFS (Production Flow Schema) technique level, and a functional model by using MFG (Mark Flow Graph) and its extensions. The MFG abstraction level describes details in a functional form, where are preserved the description activities of previous levels. The methodology proposal confirmed to be useful and efficient to elevator systems modeling, when allowing the functional specification of the whole system (object of control and control system), and strategies that facilitate its integration with others building systems.

The factored state representation and concurrency semantics of Petri nets are closely related to those of classical planning models, yet automated planning and Petri net analysis have developed independently, with minimal and mainly unconvincing attempts at crossfertilisation. This thesis exploits the relationship between the formal reachability problem, and the automated planning problem, via Petri net unfolding, which is an attractive reachability analysis method for highly concurrent systems as it facilitates reasoning about independent sub-problems. The first contribution of this thesis is the theory of directed unfolding: controlling the unfolding process with informative strategies, for the purpose of optimality and increased efficiency. The second contribution is the application of directed unfolding to automated planning. Inspired by well-known planning heuristics, this thesis shows how problem specific information can be employed to guide unfolding, in response to the formal problem of developing efficient, directed reachability analysis methods for concurrent systems. Complimenting this theoretical work, this thesis presents a new forward search method for partial order planning which can be exponentially more efficient than state space search. Our suite of planners based on directed unfolding can perform optimal and suboptimal classical planning subject to arbitrary action costs, optimal temporal planning with respect to arbitrary action durations, and address probabilistic planning via replanning for the most likely path. Empirical results reveal directed unfolding is competitive with current state of the art automated planning systems, and can solve Petri net reachability problems beyond the reach of the original “blind” unfolding technique. / Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2008

Made available in DSpace on 2016-12-12T17:38:33Z (GMT). No. of bitstreams: 1 Daniel Gumiero Noronha Maas.pdf: 6258702 bytes, checksum: 06207c47266ccded357fbb819c6ae9bf (MD5) Previous issue date: 2014-09-09 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a multilayer architecture for fault diagnosis in embedded systems that allows a better discrimination of the type and source of the failure, providing an accurate and assertive diagnosis. This architecture contemplates the necessary interfaces to allow integration of this diagnostic framework in the embedded system and also considers the treatment of diagnostic information for recovery system actions purposes, or simply allows the externalization of such information. This work considers the diagnosers designed according to the methodology of fault diagnosis in DES modeled by automata. Once designed the diagnosers are implemented in ANSI C language through an automated software generation tool, and finally incorporated into the main product software where it intends to perform the diagnosis. This architecture diagnosis was then applied in a case study for Frost Free refrigerator, for which the diagnosers were designed then were implemented in software and subsequently validated in order to confirm the effectiveness of the diagnosers, of the proposed architecture beyond the C language conversion process. / Este trabalho apresenta uma arquitetura de diagnóstico multicamadas para detecção de falhas em sistemas embarcados, que permite uma melhor discriminação do tipo e origem da falha, possibilitando um diagnóstico mais preciso e assertivo. Esta arquitetura contempla as interfaces necessárias para permitir a integração no sistema embarcado e também considera o tratamento das informações de diagnóstico para fins de ações de recuperação do sistema, ou simplesmente a externalização destas informações. Neste trabalho, consideram-se os diagnosticadores projetados conforme a metodologia de diagnóstico de falhas em SEDs modelados por autômatos. Uma vez concebidos, os diagnosticadores são implementados em linguagem ANSI C, através de uma ferramenta de geração automática de software, e finalmente incorporados ao software principal do equipamento onde se pretende realizar o diagnóstico. Esta arquitetura de diagnóstico foi então aplicada em um estudo de caso para um refrigerador Frost Free, para o qual foram projetados os diagnosticadores, em seguida os mesmos foram implementados em software e posteriormente validados a fim de comprovar a eficácia não somente dos diagnosticadores mas também da arquitetura proposta, além do processo de conversão dos mesmos em linguagem de software.

O presente trabalho trata da verificação e design de sistemas complexos, especificamente da verificação de sistemas de tempo real concorrentes e distribuídos. Propõe-se uma técnica enumerativa para a verificação formal de modelos que permite determinar a validade de propriedades quantitativas, além das qualitativas. A técnica proposta separa a construção do espaço de estados dos algoritmos de rotulação das fórmulas temporais, o que possibilita a diminuição da complexidade do processo de verificação, tornando-o viável para aplicações práticas. A técnica proposta foi inicialmente aplicada sobre modelos de redes de Petri temporizadas e depois em uma rede unificada chamada GHENeSys para aproveitar as características de abstração, hierarquia e de elementos de interação chamados pseudo-boxes. A definição da rede GHENeSys foi modificada para permitir a modelagem de sistemas onde os requisitos temporais devem ser expressos através de atrasos e prazos como e o caso dos sistemas de tempo real. A rede suporta ainda mecanismos de refinamento tanto para os elementos ativos quanto os passivos. A demonstração da manutenção de propriedades como invariantes, vivacidade, limitação assim como da validade de fórmulas lógicas no processo de refinamento constitui um aspecto fundamental no projeto de sistemas complexos, e foi portanto revista em detalhes para a rede GHENeSys. Alguns exemplos práticos são apresentados para avaliar o desempenho dos algoritmos e um estudo de caso finaliza a apresentação, onde se pode contrastar os algoritmos propostos com os implementados na ferramenta UPPAAL. / This work deals with the process of design and verification of complex systems, mainly real time, concurrent and distributed systems. An enumerative technique is proposed for model-checking which is capable of determining both quantitative and qualitative properties. The proposed technique detach the algorithm for labeling the formula being checked from the state space construction, allowing a better result in the verification process. This model-checking approach shows itself valuable in practical applications. This approach was first applied to systems modeled by Time Petri Nets and further extended to a unified net called GHENeSys, which includes abstraction and hierarchy concepts as well as elements for data and control interchange, called pseudo-boxes. The GHENeSys definition was modified in order to deal with systems in which temporal requirements can be expressed through delays and deadlines as in the real-time systems. The GHENeSys environment supports a refinement technique applied to both passive and active elements. Net properties like invariants, liveness, boundedness and also the validity of temporal formulas was proved to be maintained through the refinement process if some conditions are satisfied. Such characteristics are useful to deal with complex systems design. Some experiments based on well known academic articles were used to avaliate the performance of the algorithms and a case study is presented in order to compare obtained results with those obtained using the UPPAAL tool.

O objeto de estudo deste trabalho é a construção de modelos que permitam a estruturação do projeto do controle de sistemas flexíveis de manufatura que considerem não somente estados de operação normal, mas também estados anormais, isto é, em situações de falhas. Entende-se como falha o desvio de pelo menos uma propriedade do sistema que leva o mesmo a um estado de defeito, que por sua vez se define como um comportamento incomum, não projetado, do sistema sob estudo, que finalmente é manifestado como um defeito. Sistemas flexíveis de manufatura são sistemas que executam múltiplos processos visando à produção de diversos bens. O processo é um conjunto de ações de transformação que por sua parte requerem um conjunto de recursos que são compartilhados por outros processos simultaneamente. Sistemas flexíveis de manufatura envolvem um número relativamente grande de componentes, máquinas, equipamentos e operadores humanos, que interagem de maneira diversificada manipulando um grande conjunto de informação e diferentes materiais em ambientes que podem até ser agressivos. Independentemente de qualquer programa de manutenção, falhas são eventos que são possíveis de acontecer em qualquer sistema de tal natureza. Num ambiente ideal, o funcionamento de todos os componentes poderia ser monitorado com o objetivo de detectar as falhas prematuras, mas devido ao custo envolvido, isso se torna inviável. Neste sentido surge o desafio de detectar as falhas a partir da observação do contexto do funcionamento do processo, mediante a monitoração de alguns parâmetros, em geral de fácil acesso, e tomando em consideração manifestações (sintomas) das falhas de um ponto de vista qualitativo. O presente trabalho propõe a utilização de redes Bayesianas para o diagnóstico de falhas em sistemas flexíveis de manufatura. As redes Bayesianas constituem uma ferramenta útil para a representação das relações que existem entre as causas (componentes em estado de falha) e os sintomas (observações anormais do processo). A partir deste modelo, inferências podem ser feitas para o diagnóstico do sistema.Por outro lado, nos últimos anos a rede de Petri tem sido utilizada exitosamente na representação dos aspectos de controle de sistemas produtivos e particularmente de sistemas de manufatura e, desta forma, considera-se aqui tal ferramenta para a modelagem do sistema não só em condições normais de funcionamento como também para a representação do tratamento de falhas, no contexto de um sistema tolerante a anomalias do processo. Especial ênfase é dada à estruturação de uma metodologia que permita a concepção de um procedimento eficaz para a construção de modelos de controle. / The objective of the present work is the construction of models proper for the easy implementation of flexible manufacturing control systems able to handle not only with normal behavioral conditions, but with abnormal (or faulty) behavior as well. A fault is defined as a deviation of at least one system property that drives the system into an error state. An error is defined as an uncommon behavior, not expected from the system functionalities. Flexible manufacturing systems are systems that execute multiple processes for the production of several items in several ways. A process is a sequence of certain transformation tasks that require a set of resources shared simultaneously by multiple processes. In this sense, flexible manufacturing systems are constituted of a relatively great number of devices, machines, equipments and human operators that work together manipulating great quantities of information and materials. This work is usually performed in aggressive environments. So, independent of any maintenance program, faults are events that cannot be totally avoided. In an ideal environment, the monitoring of all components is the way to avoid faults. Nevertheless, due to the cost involved, this is an impossible task. In this context, there is a challenge to properly detect faults from the observation of the systems context, through the monitoring and observation of some parameters in general easy to access, including also qualitative information from operators. In the present work, it is proposed the use of Bayesian networks for the fault diagnosis in flexible manufacturing systems. Bayesian networks constitute a useful tool for the modeling of the causal relation between the causes (faulty components) and the symptoms (manifestations). Based on this model, inference can be done for the system diagnosis task. Additionally, in the last years Petri net has been successfully used for the modeling of control systems of productive systems and particularly, manufacturing control systems. In this work, beyond the use of Petri net for the modeling of normal situations of the system, Petri net is used for the modeling of the fault treatment techniques. This drives the system tolerance to faults. Especial emphasis is laid into methodological issues that allows for the structuration of a systematic procedure proper for the modeling and construction of control systems.

nÃo hà / Esse trabalho propÃe um novo mÃtodo para sÃntese de supervisores em sistemas a eventos discretos, utilizando redes de Petri coloridas, baseado no contexto da teoria de controle supervisÃrio. Como aspecto principal, tem-se a formalizaÃÃo teÃrica e a prova matemÃtica do mÃtodo para sÃntese desses supervisores, denominado RestriÃÃes de Controle sobre Cores Decompostas (RCCD). AlÃmdisso, como consequÃncia, à apresentado ummÃtodo para reduÃÃo do nÃmero de lugares de controle denominado FusÃo de Controladores (FC). Os mÃtodos RCCD e FC sÃo uma extensÃo do trabalho de Moody e Antsaklis, que propÃem, originalmente, um Teorema comprovando a sÃntese de supervisores usando redes de Petri ordinÃrias e, dessa forma, sÃo propostas aqui as extensÃes desse Teorema, para o contexto das redes de Petri coloridas. Nesse caso, explora-se a decomposiÃÃo da matriz de incidÃncia de uma rede de Petri colorida para de…nir lugares de controle que nÃo sÃo con‡itantes em suas aÃÃes, usando o soft CPNTools como ferramenta. A seguir, à realizada a fusÃo desses lugares de controle, obtidos com o RCCD, com a aplicaÃÃo do mÃtodo FC, em que o lugar de controle encontrado, denominado supervisor resultante da fusÃo, atende as mesmas restriÃÃes e contribui com a mesma performance de controle do sistema. / This work proposes a newmethod for synthesis of supervisors in discrete event systems using coloured Petri nets, based in the theory of supervisory control. As a main aspect, there is the theoretical and formal mathematical proof of the method for synthesis of supervisors, called Control Constraints on Decomposed Colors (CCDC). In addition, as a consequence, it is presented a method for reducing the number of control places called Fusion of Controllers (FC). The CCDC and FC methods are an extension of the work of Moody and Antsaklis, they propose, originally a theorem proving the synthesis of supervisors using Petri nets thus are proposed here extensions of this theorem to the context of coloured Petri nets. In this case, it is explored the decomposition of the incidence matrix of a coloured Petri net to de…ne control places that are not con‡icting in their actions, using the soft CPNTools. The following is realized the fusion of these control places obtained with CCDC, with the aplication of the FC method. The obtained place is called the resulting fusion supervisor, where it is found the same constraints and contributes with the same control system performance.

Cette thèse porte sur le diagnostic des défauts dans des Systèmes à Evènements Discrets (SED) pour lesquels l’occurrence des événements est soumise à des contraintes temporelles. Les domaines d’application potentiels sont nombreux et variés allant de la production manufacturière aux systèmes de transport en passant par les réseaux de communication et les systèmes d’information. La complexité croissante de ces systèmes nécessite l’élaboration de méthodes de surveillance de plus en plus efficaces et performantes pour garantir leur sécurité, leur disponibilité ainsi que le maintien de leurs propriétés dans le temps. Les réseaux de Petri Stochastiques Temporisés Partiellement Observés (RdPSTPO) sont utilisés pour modéliser le système ainsi que les défauts qui peuvent l’affecter. L’étude concerne particulièrement les défauts qui se traduisent par la violation des contraintes temporelles. Une exploitation pertinente des informations temporelles, en vue du diagnostic, constitue la contribution majeure de la thèse. En effet, une meilleure utilisation de ces informations permet de discerner avec précision les différents comportements qui expliquent les mesures. De plus, la probabilité d’occurrence des défauts est calculée en fonction des dates des mesures collectées. Deux approches sont développées : la première est dédiée aux défauts ponctuels et la seconde aux dérives lentes dans les systèmes cycliques. / This PhD thesis deals with the fault diagnosis of Discrete Event Systems (DES) for which the occurrence of events is constrained by temporal specifications. The domain of application is large and varied ranging from manufacturing systems to transportation systems, communication networks and information systems. The increasing complexity of these systems requires the development of effective and efficient monitoring methods to ensure their security, availability and the maintenance of their properties over the time. For that purpose, Partially Observed Stochastic Timed Petri Nets (POSTPN) are used to model the system and the different faults that may affect it. The study is particularly concerned with faults that result after the violation of temporal constraints. Our main contribution in this thesis is the relevant exploitation of the timed information for the fault diagnosis. In fact, a better use of these temporal informations allow to discern with precision the different behaviors that are consistent with the measurements. In addition, the probability of faults occurrence is evaluated according to the dates of collected measurements. Two approaches are developed : the first one is used for single faults and the second one for slow drifts in cyclical systems.

<p>Sampled-data supervisory control deals with timed discrete event systems (TDES) where the supervisors are to be implemented as sampled-data controllers. A sampled-data controller views the system as a series of inputs and outputs and is controlled by a periodic clock. It samples its inputs, changes state, and updates its outputs on each clock edge (the tick event). The sampled-data supervisory control framework provides a set of conditions that the TDES system must satisfy to ensure its correct behaviour in order to be implemented as sampled data controllers. A serious limitation for automatic verification of systems is the size of the system's synchronous product. To overcome this limitation, we propose the use of a compositional approach to the verification of sampled-data supervisory control. In this approach, first we recast the required conditions for sampled-data supervisory control in terms of other properties such as language inclusion, nonblocking or controllability, which already have existing compositional methods and algorithms. This makes the sampled-data properties suitable for compositional verification, considerably increasing the size of systems that can be handled using sampled-data supervisory control. We also develop and implement a set of algorithms for the compositional verification of these sampled-data properties. We provide an example of the SD Controlled Flexible Manufacturing System to test our algorithms.</p> / Master of Science (MSc)