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.

Os avanços tecnológicos das últimas décadas têm motivado o desenvolvimento dos edifícios inteligentes, visando à criação de ambientes mais confortáveis e seguros para os ocupantes, economicamente vantajosos para os proprietários e ambientalmente corretos. Considerando-se que nestes ambientes emergem novas formas de interação entre os usuários e os sistemas prediais, as quais não são adequadamente tratadas por técnicas convencionais de modelagem, torna-se necessário o estudo de novas soluções que abordem essas interações. Assim, este trabalho apresenta a proposta de uma abordagem sistemática para modelar e simular os sistemas de controle de edifícios inteligentes. Considera-se o sistema de controle como um sistema orientado por eventos discretos, no qual a comunicação entre os dispositivos que o constituem é realizada por meio da troca assíncrona de mensagens. Nesta abordagem, é utilizada a rede de Petri colorida para especificar as funcionalidades do edifício inteligente e a interação entre os dispositivos que constituem o seu sistema de controle. Assim, fornece-se um procedimento estruturado para desenvolver modelos que facilita a especificação do algoritmo de controle dos subsistemas do edifício inteligente. Para avaliar as principais características do procedimento proposto, foi apresentado um exemplo de aplicação que aborda a integração das funcionalidades de um sistema de telefonia distribuído e um sistema de vigilância predial. A abordagem de modelagem possibilitou a identificação das funcionalidades dos dispositivos inteligentes que integram o sistema de controle em diferentes níveis de abstração e as interações que ocorrem durante o seu funcionamento. A realização deste trabalho contribui para o aprimoramento de novas abordagens para o desenvolvimento de sistemas de controle com arquiteturas heterárquicas. Estes sistemas são constituídos por dispositivos inteligentes colaborativos, que possuem um elevado grau de autonomia. / Technological advances in recent decades have motivated the development of intelligent buildings, aimed at creating environments more productive for the occupants, economically advantageous for the owners and environmentally correct. New ways of interaction between users and the buildings systems are emerging from these kinds of systems, which are not adequately treated by conventional modeling techniques. In this sense, it is necessary the study of new approaches which address these new functionalities. Thus, this work presents a proposal for a systematic approach to model and simulate the control system of the intelligent buildings. The control system is considered to be a discrete event system, where the communication between the devices that integrate it is oriented by means of asynchronous messages exchange. This approach uses the colored Petri nets in order to specify the functionalities of the building system and their devices interactions. The approach provides a structured procedure to develop models that facilitate the algorithm specification of the control system. In order to verify the main characteristics of the proposed procedure, it is presented an example that is a control system that integrates a distributed telephony system and a surveillance building system. The approach proposed enabled the identification of the main functionalities and interactions of the intelligent devices constituting the control system. The achievement of this thesis contributes to the development of new approaches to develop heterarchical control system architectures. This kind of system architectures is constituted by collaborative intelligent devices that have a high degree of autonomy.

Controle de acesso é um tópico de pesquisa importante tanto para a academia quanto para a indústria. Controle de Acesso Baseado em Papéis (CABP) foi desenvolvido no início dos anos 1990, tornando-se um padrão generalizado para controle de acesso em vários produtos e soluções computacionais. Embora modelos CABP sejam largamente aceitos e adotados, ainda existem questões para responder. Um dos principais desafios de pesquisa em segurança baseada em papéis é determinar se uma política de controle de acesso é consistente em um ambiente altamente dinâmico. Nossa pesquisa visa preencher essa lacuna fornecendo um método para analisar políticas CABP com respeito a dois aspectos significativos: segurança e dinamismo envolvendo papéis e objetos. Para este propósito, desenvolvemos um modelo de descrição e simulação de política usando rede de Petri colorida e CPN Tools. O modelo descreve e é capaz de simular vários estados CABP em um contexto de educação a distância típico. Usando este modelo, foi possível analisar o espaço de estados produzido pela rede de Petri colorida em um cenário dinâmico envolvendo a criação de novos papéis e objetos. O resultado da análise de alcançabilidade da rede de Petri da política demonstrou que é possível verificar a consistência de políticas de controle de acesso considerando a dinamicidade de papéis e objetos, e apontou vantagens de aplicabilidade da modelagem de políticas de segurança em ambientes distribuídos utilizando rede de Petri colorida. / Access control is an important research topic both for academia and industry. Role Based Access Control (RBAC) was developed in the early 1990s, becoming a generalized standard of access control for many products and computing solutions. Although RBAC models have been widely accepted and adopted, there are issues to answer. One of the key challenges for role-based security research is to characterize whether an access control policy is consistent in a highly dynamic environment. Our research aims filling this gap providing a method to analyze RBAC policies with respect to two significant aspects: security and dynamics involving roles and objects. For this purpose, we developed a policy description and simulation model using colored Petri net and the CPN Tools. The model describes and is capable to simulate many RBAC states in a typical distance education context. Using this model it was possible to analyze the state space provided by colored Petri net that simulates a dynamic environment and the creation of new roles and objects. The result of the reachability analysis of Petri net policy showed that it is possible to check the consistency of access control policies considering dynamic of roles and objects, and point out the advantages and applicability of modeling security policies in distributed environments using colored Petri net.

Controle de acesso é um tópico de pesquisa importante tanto para a academia quanto para a indústria. Controle de Acesso Baseado em Papéis (CABP) foi desenvolvido no início dos anos 1990, tornando-se um padrão generalizado para controle de acesso em vários produtos e soluções computacionais. Embora modelos CABP sejam largamente aceitos e adotados, ainda existem questões para responder. Um dos principais desafios de pesquisa em segurança baseada em papéis é determinar se uma política de controle de acesso é consistente em um ambiente altamente dinâmico. Nossa pesquisa visa preencher essa lacuna fornecendo um método para analisar políticas CABP com respeito a dois aspectos significativos: segurança e dinamismo envolvendo papéis e objetos. Para este propósito, desenvolvemos um modelo de descrição e simulação de política usando rede de Petri colorida e CPN Tools. O modelo descreve e é capaz de simular vários estados CABP em um contexto de educação a distância típico. Usando este modelo, foi possível analisar o espaço de estados produzido pela rede de Petri colorida em um cenário dinâmico envolvendo a criação de novos papéis e objetos. O resultado da análise de alcançabilidade da rede de Petri da política demonstrou que é possível verificar a consistência de políticas de controle de acesso considerando a dinamicidade de papéis e objetos, e apontou vantagens de aplicabilidade da modelagem de políticas de segurança em ambientes distribuídos utilizando rede de Petri colorida. / Access control is an important research topic both for academia and industry. Role Based Access Control (RBAC) was developed in the early 1990s, becoming a generalized standard of access control for many products and computing solutions. Although RBAC models have been widely accepted and adopted, there are issues to answer. One of the key challenges for role-based security research is to characterize whether an access control policy is consistent in a highly dynamic environment. Our research aims filling this gap providing a method to analyze RBAC policies with respect to two significant aspects: security and dynamics involving roles and objects. For this purpose, we developed a policy description and simulation model using colored Petri net and the CPN Tools. The model describes and is capable to simulate many RBAC states in a typical distance education context. Using this model it was possible to analyze the state space provided by colored Petri net that simulates a dynamic environment and the creation of new roles and objects. The result of the reachability analysis of Petri net policy showed that it is possible to check the consistency of access control policies considering dynamic of roles and objects, and point out the advantages and applicability of modeling security policies in distributed environments using colored Petri net.

Os avanços tecnológicos das últimas décadas têm motivado o desenvolvimento dos edifícios inteligentes, visando à criação de ambientes mais confortáveis e seguros para os ocupantes, economicamente vantajosos para os proprietários e ambientalmente corretos. Considerando-se que nestes ambientes emergem novas formas de interação entre os usuários e os sistemas prediais, as quais não são adequadamente tratadas por técnicas convencionais de modelagem, torna-se necessário o estudo de novas soluções que abordem essas interações. Assim, este trabalho apresenta a proposta de uma abordagem sistemática para modelar e simular os sistemas de controle de edifícios inteligentes. Considera-se o sistema de controle como um sistema orientado por eventos discretos, no qual a comunicação entre os dispositivos que o constituem é realizada por meio da troca assíncrona de mensagens. Nesta abordagem, é utilizada a rede de Petri colorida para especificar as funcionalidades do edifício inteligente e a interação entre os dispositivos que constituem o seu sistema de controle. Assim, fornece-se um procedimento estruturado para desenvolver modelos que facilita a especificação do algoritmo de controle dos subsistemas do edifício inteligente. Para avaliar as principais características do procedimento proposto, foi apresentado um exemplo de aplicação que aborda a integração das funcionalidades de um sistema de telefonia distribuído e um sistema de vigilância predial. A abordagem de modelagem possibilitou a identificação das funcionalidades dos dispositivos inteligentes que integram o sistema de controle em diferentes níveis de abstração e as interações que ocorrem durante o seu funcionamento. A realização deste trabalho contribui para o aprimoramento de novas abordagens para o desenvolvimento de sistemas de controle com arquiteturas heterárquicas. Estes sistemas são constituídos por dispositivos inteligentes colaborativos, que possuem um elevado grau de autonomia. / Technological advances in recent decades have motivated the development of intelligent buildings, aimed at creating environments more productive for the occupants, economically advantageous for the owners and environmentally correct. New ways of interaction between users and the buildings systems are emerging from these kinds of systems, which are not adequately treated by conventional modeling techniques. In this sense, it is necessary the study of new approaches which address these new functionalities. Thus, this work presents a proposal for a systematic approach to model and simulate the control system of the intelligent buildings. The control system is considered to be a discrete event system, where the communication between the devices that integrate it is oriented by means of asynchronous messages exchange. This approach uses the colored Petri nets in order to specify the functionalities of the building system and their devices interactions. The approach provides a structured procedure to develop models that facilitate the algorithm specification of the control system. In order to verify the main characteristics of the proposed procedure, it is presented an example that is a control system that integrates a distributed telephony system and a surveillance building system. The approach proposed enabled the identification of the main functionalities and interactions of the intelligent devices constituting the control system. The achievement of this thesis contributes to the development of new approaches to develop heterarchical control system architectures. This kind of system architectures is constituted by collaborative intelligent devices that have a high degree of autonomy.

Dentre as várias abordagens consagradas para análise de desempenho de algoritmos em termos de tempo de execução, destacam-se, por exemplo, a análise assintótica, as técnicas de recorrências e a análise probabilística. Entretanto, há algoritmos que apresentam certas peculiaridades que tornam o uso dessas técnicas puramente matemáticas de avaliação de desempenho inadequadas ou excessivamente árduas. É o caso, por exemplo, de algoritmos cujo tempo de execução pode variar significativamente para um mesmo dado de entrada em função da dinâmica de execução. O mesmo acontece no caso de algoritmos distribuídos em que, dependendo da complexidade da política de distribuição utilizada, a avaliação por meio de métodos analíticos do efeito de um gradual incremento de processadores no seu tempo de execução pode tornar-se impraticável. Em situações como essas, a fim de evitar a alta complexidade matemática envolvida na análise de desempenho desses algoritmos, algumas alternativas baseadas em métodos empíricos ou em modelagem visual vêm sendo adotada pelos pesquisadores. Contudo, ambas alternativas apresentam inconvenientes: no caso dos métodos empíricos, eles requerem a implementação dos algoritmos analisados, o que tem um efeito perverso particularmente no caso dos algoritmos distribuídos, uma vez que eles demandam a aquisição prévia de recursos de hardware dispendiosos de multi-processamento antes mesmo de saber se a proposta de distribuição investigada, de fato, vale a pena. Já as abordagens baseadas em modelos visuais atualmente utilizadas (baseadas em grafos, autômatos e Unified Modeling Language - UML) não contam com os recursos dinâmicos necessários para lidar com a avaliação do tempo de execução dos algoritmos. Neste cenário, o presente trabalho propõe uma abordagem visual formal para avaliar o tempo de execução de algoritmos baseada em simulações automáticas de modelos de Redes de Petri Coloridas Hierárquicas (RdPCH) no ambiente gráfico CPN Tools. A abordagem proposta é validada por meio de cálculo dos seguintes parâmetros associados aos algoritmos usados como estudo de caso: a função de complexidade, o tempo de execução real e, no caso dos algoritmos distribuídos, o speedup e a eficiência. Foram usados como estudos de caso os seguintes três relevantes algoritmos de busca usados nos agentes da Inteligência Artificial com a finalidade de definir as ações mais apropriadas que tais agentes devem executar de modo a cumprir seu objetivo, com êxito, em um ambiente em que um oponente tenta minimizar suas chances de sucesso: os algoritmos seriais Minimax e Alpha-Beta; e o algoritmo distribuído PVS. Os resultados obtidos confirmam a correção da abordagem proposta. / Among the various approaches established for analyzing the performance of algorithms in terms of runtime, one can highlight as examples, the asymptotic analysis, recurrence techniques, and probabilistic analysis. However, there are algorithms that present certain peculiarities, which make the use of these purely mathematical performance evaluation techniques inadequate or excessively difficult. This is the case of algorithms for which the runtime varies significantly for the same input data, due to its execution dynamics. The same happens in the case of distributed algorithms, where depending on the complexity of the distribution policy being used, the evaluation by means of analytical methods concerning the effect of a gradual increase in processors on runtime can become impractical. In situations such as these, in order to avoid the high mathematical complexity involved in the performance analysis, researchers have adopted alternatives based on empirical methods or visual modeling. However, both alternatives have drawbacks: in the case of empirical methods, they require the implementation of analyzed algorithms, which has a perverse effect especially in the case of distributed algorithms. This occurs, as they demand the acquisition beforehand of expensive multiprocessing hardware resources before knowing if the distribution proposal under investigation is in fact viable. On the other hand, those approaches based on visual models currently under use (based on graphs, automata and Unified Modeling Language) one notes that does not contain the necessary dynamic resources for dealing with the runtime evaluation of algorithms. In this scenario, the present study proposes a formal visual approach, in order to evaluate the algorithm runtime based on automatic simulations of Hierarchical Colored Petri Net models in the CPN Tools graphic environment. The proposed approach is validated through the calculation of the following parameters associated with the algorithms being used as a case study: the complexity function, real runtime, and in the case of distributed algorithms, speedup and efficiency. The cases studies were based on three relevant search algorithms used in the agents of the Artificial Intelligence, with the aim of defining the most appropriate actions that these agents need to execute in order to fulfil their objective, in an environment where the opponent tries to minimize their chances of success. The algorithms under consideration were the serial algorithms Minimax and Alpha-Beta; and the PVS distributed algorithm. The obtained results confirm the correction of the proposed approach. / Tese (Doutorado)

Este trabalho foi motivado pela necessidade de considerar comportamento estocástico durante o planejamento da produção de sistemas de manufatura, ou seja, o que produzir e em que ordem. Estes sistemas possuem um comportamento estocástico geralmente não considerado no planejamento da produção. O principal objetivo deste trabalho foi obter um método que modelasse sistemas de manufatura e representasse seu comportamento estocástico durante o planejamento de produção destes sistemas. Como os métodos que eram ideais para planejamento não forneciam a modelagem adequada dos sistemas, e os com modelagem adequada não forneciam a capacidade de planejamento necessária, decidiu-se combinar dois métodos para atingir o objetivo desejado. Decidiu-se modelar os sistemas em rede de Petri e convertê-los em processos de decisão markovianos, e então realizar o planejamento com o ultimo. Para que fosse possível modelar as probabilidades envolvidas nos processos, foi proposto um tipo especial de rede de Petri, nomeada rede de Petri fatorada. Utilizando este tipo de rede de Petri, foi desenvolvido o método de conversão em processos de decisão markovianos. A conversão ocorreu com sucesso, conforme testes que mostraram que planos podem ser produzidos utilizando-se algoritmos de ponta para processos de decisão markovianos. / The present work was motivated by the need to consider stochastic behavior when planning the production mix in a manufacturing system. These systems are exposed to stochastic behavior that is usually not considered during production planning. The main goal of this work was to obtain a method to model manufacturing systems and to represent their stochastic behavior when planning the production for these systems. Because the methods that were suitable for planning were not adequate for modeling the systems and vice-versa, two methods were combined to achieve the main goal. It was decided to model the systems in Petri nets and to convert them into Markov decision processes, to do the planning with the latter. In order to represent probabilities in the process, a special type of Petri nets, named Factored Petri nets, were proposed. Using this kind of Petri nets, a conversion method into Markov decision processes was developed. The conversion is successful as tests showed that plans can be produced within seconds using state-of-art algorithms for Markov decision processes.

Este trabalho foi motivado pela necessidade de considerar comportamento estocástico durante o planejamento da produção de sistemas de manufatura, ou seja, o que produzir e em que ordem. Estes sistemas possuem um comportamento estocástico geralmente não considerado no planejamento da produção. O principal objetivo deste trabalho foi obter um método que modelasse sistemas de manufatura e representasse seu comportamento estocástico durante o planejamento de produção destes sistemas. Como os métodos que eram ideais para planejamento não forneciam a modelagem adequada dos sistemas, e os com modelagem adequada não forneciam a capacidade de planejamento necessária, decidiu-se combinar dois métodos para atingir o objetivo desejado. Decidiu-se modelar os sistemas em rede de Petri e convertê-los em processos de decisão markovianos, e então realizar o planejamento com o ultimo. Para que fosse possível modelar as probabilidades envolvidas nos processos, foi proposto um tipo especial de rede de Petri, nomeada rede de Petri fatorada. Utilizando este tipo de rede de Petri, foi desenvolvido o método de conversão em processos de decisão markovianos. A conversão ocorreu com sucesso, conforme testes que mostraram que planos podem ser produzidos utilizando-se algoritmos de ponta para processos de decisão markovianos. / The present work was motivated by the need to consider stochastic behavior when planning the production mix in a manufacturing system. These systems are exposed to stochastic behavior that is usually not considered during production planning. The main goal of this work was to obtain a method to model manufacturing systems and to represent their stochastic behavior when planning the production for these systems. Because the methods that were suitable for planning were not adequate for modeling the systems and vice-versa, two methods were combined to achieve the main goal. It was decided to model the systems in Petri nets and to convert them into Markov decision processes, to do the planning with the latter. In order to represent probabilities in the process, a special type of Petri nets, named Factored Petri nets, were proposed. Using this kind of Petri nets, a conversion method into Markov decision processes was developed. The conversion is successful as tests showed that plans can be produced within seconds using state-of-art algorithms for Markov decision processes.