351 |
Supervisor Synthesis for Automated Manufacturing Systems Based on Structure Theory of Petri Nets. / Synthèse de contrôleurs de Systèmes de production automatisés basés sur la théorie structurelle des réseaux de Petri.Liu, Gaiyun 27 December 2014 (has links)
Le contrôle de systèmes industriels à cause de l’automatisation et la réduction de nombre des opérateurs devient un enjeu crucial. Les systèmes de production automatisés (AMS) sont d’autant plus touchés car une défaillance du programme de contrôle peut réduire considérablement la productivité voire entraîner l’arrêt du système de production. Pour certains de ces systèmes où le partage des ressources est pondérant, la notion de blocage partiel ou global est fréquente et la validation avant implantation est préférable pour réduire les risques.En raison de la capacité des réseaux de Petri à décrire aisément l’exécution concurrente des processus et le partage des ressources, de nombreuses méthodes de vérification d’absence de blocage et de synthèse de contrôleurs basées sur la théorie structurelle ou le graphe d’accessibilité des réseaux de Petri ont été proposées au cours des deux dernières décennies.Traditionnellement, une méthode de prévention de blocage est évaluée selon trois critères de performance: la complexité structurelle, la permissivité comportementale, et la complexité de calcul. Les méthodes fondées sur l’espace d’état aboutissent généralement à un contrôle maximal permissif mais souffrent de l'explosion combinatoire de l'espace d'états. En revanche, les méthodes de synthèse de contrôleurs fondées sur l’analyse structurelle évitent le problème de l’explosion de l’espace d’état mais aboutissent à des superviseurs pouvant restreindre considérablement les comportements admissibles du système. De plus si la théorie structurelle de contrôle de siphons pour la synthèse des superviseurs est mature dans le cas des réseaux de Petri ordinaires, elle est en développement pour les réseaux de Petri généralises. Par ailleurs, la plupart des travaux existants partent du principe que les ressources sont constamment disponibles. Or l’indisponibilité de ressources est en réalité un phénomène ordinaire. Il serait donc judicieux de développer une politique de vérification de blocage qui soit efficace tout en considérant des ressources non fiables.Cette thèse vise principalement à faire face aux limitations mentionnées ci-dessus. Nos principales contributions à la fois théoriques et algorithmiques sont les suivantes.Premièrement, après avoir revisité les conditions de contrôlabilité des siphons (cs–propriété) et précisé les limitations de la max cs- propriété et max’ cs- propriété, nous définissons la max’’ cs-propriété et nous démontrons que cette nouvelle propriété est une condition non seulement suffisante mais aussi nécessaire pour la vivacité de la classe des GS3PR (Generalized Systems of SimpleSequential Processes with Resources).Par la suite nous montrons comment le problème de la vérification de cette propriété et donc la vivacité des GS3PR peut se ramener à la résolution d’un programme linéaire en nombre entiers.Dans une seconde partie, nous proposons une classe de réseaux de Petri appelée M-Nets dotée d’une forte capacité de modélisation des systèmes de production automatisés. En combinant la théorie du contrôle siphon avec la théorie des régions, nous développons une méthode de prévention de blocage ayant un bon compromis entre l'optimalité du comportement et la complexité de calcul. De plus, nous proposons une méthode de synthèse d'un contrôleur maximal permissif pour une sous-classe de réseaux notée b-nets.Enfin, nous proposons dans cette thèse une méthode de conception d’un superviseur de systèmes de production automatisés où les ressources ne sont pas toutes fiables et particulièrement efficace pour la classe des S3PR (Systems of Simple Sequential Processes with Resources). / Because of automation and reduction of the number of operators, the control of industrial systems is becoming a critical issue. For automated manufacturing systems (AMS) where resource sharing is preponderant, the notion of partial or total blocking is frequent and validation before implementation is preferable to reduce the risks.Due to the easy and concise description of the concurrent execution of processes and the resource sharing by Petri nets, many methods to verify deadlock-freeness and to synthesize controllers using structural theory or reachability graph have been proposed over the past two decades.Traditionally, a deadlock control policy can be evaluated by three performance criteria : structural complexity, behavioral permissiveness, and computational complexity. Generally, deadlock control policies based on the state space analysis can approach the maximal permissive behavior, but suffer from the state explosionproblem. On the contrary deadlock control policies based on the structural analysis of Petri nets avoid in general the state explosion problem successfully, but cannot lead to the maximally or near maximally permissive controller. Morover, the current Deadlock control theory based on siphons is fairly mature for ordinary Petri nets,while for generalized Petri nets, it is presently at an early stage.On the other hand, most deadlock control policies based on Petri nets for AMS proceed on the premise that the resources in a system under consideration are reliable. Actually, resource failures are inevitable and common in most AMS, which may also cause processes to halt. Therefore, it is judicious to develop an effective and robust deadlock control policy considering unreliable resources.This thesis aims to cope with the limitations mentioned above. Our main theoretical and algorithmic contributions are the following. Firstly, after revisiting the controllability conditions of siphons and limitations of max and max' controlled-siphon properties, we define the max'' cs property and we prove that this new cs-property is not only sufficient but also a necessary liveness condition forgeneralized systems of simple sequential processes with resources (GS3PR). Moreover, we show how the checking of this property and hence liveness of GS3PR nets can be translaled into resolution of an integer programming (IP) model.Secondly, we propose a class of manufacturing-oriented Petri nets, M-nets for short, with strong modeling capability. Combining siphon control and the theory of regions, we develop a deadlock prevention method that makes a good trade-off between behavioral optimality and computational tractability Moreover, this thesis proposes a maximally permissive control policy for a subclass of Petri nets (calledBéta-nets) based on the token distribution pattern of unmarked siphons.Finally, we propose a designs method for robust liveness-enforcingsupervisors for AMS with unreliable resources appropriate in particular for systems of simple sequential processes with resources(S3PR)
|
352 |
A Class of Stochastic Petri Nets with Step Semantics and Related Equivalence NotionsBuchholz, Peter, Tarasyuk, Igor V. 15 January 2013 (has links) (PDF)
This paper presents a class of Stochastic Petri Nets with concurrent transition firings. It is assumed that transitions occur in steps and that for every step each enabled transition decides probabilistically whether it wants to participate in the step or not. Among the transitions which what to participate in a step, a maximal number is chosen to perform the firing step. The observable behavior is defined and equivalence relations are introduced. The equivalence relations extend the well-known trace and bisimulation equivalences for systems with step semantics to Stochastik Petri Nets with concurrent transition firing. It is shown that the equivalence notions form a lattice of interrelations.
|
353 |
Modelagem temporal de sistemas : uma abordagem fundamentada em redes de petri / Temporal modeling of information systems: a Petri net based approachAntunes, Dante Carlos January 1997 (has links)
Neste trabalho e proposta a abordagem TempER-Tr, uma técnica de modelagem conceitual, fundamentada em rede de Petri, que integra a especificação das propriedades dinâmicas de um sistema a um modelo de dados temporal do tipo entidade relacionamento. Um modelo ou esquema conceitual descreve as propriedades identificadas de um sistema a ser desenvolvido. Estas propriedades podem ser classificadas em propriedades estáticas e propriedades dinâmicas As propriedades estáticas descrevem os estados que o sistema pode alcançar, enquanto que as propriedades dinâmicas descrevem as transições entre estes estados. A modelagem conceitual das propriedades estáticas é normalmente conhecida como modelagem de dados. A modelagem das propriedades dinâmicas é denominada de modelagem funcional ou comportamental. Mais especificamente, o modelo TempER-Tr é uma extensão de um trabalho anterior, conhecido como ER-Tr. No modelo ER-Tr, para descrever as propriedades estáticas de um sistema utiliza-se o modelo entidade-relacionamento convencional. No modelo TempER-Tr passa-se a adotar um modelo entidade-relacionamento temporal. Aliado a isto, uma nova linguagem de anotação, baseada em SQL, com mais poder de expressão é proposta. O modelo entidade-relacionamento convencional não possui dispositivos de modelagem capazes de especificar restrições que envolvam a associação dos objetos com o tempo, exigindo que isto se faca ao nível da modelagem das propriedades dinâmicas. Em um modelo entidade-relacionamento convencional, os conjuntos de entidades e relacionamentos apresentam apenas duas dimensões: a primeira refere-se as instâncias (linhas) e a segunda aos atributos (colunas). Em uma abordagem entidade relacionamento temporal, uma nova dimensão e acrescentada: o eixo temporal, possibilitando que as restrições temporais decorrentes da associação entre os objetos possam ser especificadas ao nível do modelo estático. Um requisito importante a ser preenchido por um modelo de dados temporal é permitir que em um mesmo diagrama seja possível associar objetos (entidades, relacionamentos ou atributos) temporalizados com objetos não temporalizados. lsto porque em sistemas de informação alguns dados precisam ser explicitamente referenciados ao tempo e outros não, ou porque não mudam com o tempo, ou porque é irrelevante ao usuário saber quando os fatos ocorreram. O modelo de dados temporal proposto neste trabalho, denominado TempER, pressupõe que todas as entidades, sejam elas temporalizadas ou não temporalizadas, apresentam uma "existência", ou seja, uma validade temporal. No caso das entidades temporalizadas esta existência é um subconjunto de pontos do eixo temporal. Em virtude disto são chamadas de entidades transitórias. Em relação as entidades não temporalizadas, e assumido que "existem sempre", ou seja, a sua validade temporal é constante, implícita e igual a todo o eixo temporal. Por isto são denominadas entidades perenes. Tanto as entidades transitórias quanto as entidades perenes, são focalizadas pelo modelo TempER através de duas perspectivas: uma intemporal e outra temporal. Através da perspectiva intemporal as entidades apresentam duas dimensões, semelhança do que ocorre em um modelo entidade-relacionamento convencional. Através da perspectiva temporal as entidades apresentam três dimensões, as duas convencionais e mais o tempo. Enquanto que o modelo de dados temporal descreve as propriedades estáticas de um sistema, o modelo comportamental, a outra face da abordagem TempER-Tr, focaliza as transações executadas no interior do sistema, em resposta a eventos que ocorrem no ambiente externo. Estas transações, quando efetivadas, provocam mudanças de estados no sistema. Entretanto, para estarem habilitadas a ocorrer, é necessário que um determinado conjunto de restrições dinâmicas sejam atendidas, o que se configura em um comportamento análogo ao de uma rede de Petri. O modelo TempER-Tr é completamente mapeável, inclusive o modelo de dados temporal, para a rede CEM, um tipo de rede de Petri de alto nível. Isto permite que a sua semântica seja formalmente especificada e possibilita o aproveitamento das características das redes de Petri. / This dissertation presents TempER-Tr approach. TempER-Tr is a conceptual modeling technique based on Petri nets that integrates the specification of the dynamic properties of system to a temporal entity-relationship data model. A model or conceptual schema describes the identified properties of a system. These properties can be classified into static and dynamic properties. The static properties describe the states that the system can reach, while the dynamic properties describe the transitions between the states. The conceptual modeling of the static properties is usually known as data modeling, while behavioral or functional modeling deals with dynamic properties. The TempER-Tr model is an extension of a model known as ER-Tr. In the ER-Tr model, the conventional entity-relationship model is used to describe the static properties of a system. In the TempER-Tr model, it is adopted a kind of temporal entityrelationship model. In addition, a new notation language is proposed, based on SQL, with more expression power. The conventional entity-relationship model doesn't provide tools to specify constraints that involve the association of objects with the time dimension, requiring that this have to be done at the dynamic properties modeling level. At the conventional entityrelationship model the entities and relationships sets present just two dimensions: the first one is related to the instance (lines) and the second to the attributes (columns). At a temporal entity-relationship approach, a new dimension is added: the time line. This way, the temporal constraints can be specified at the level of the static diagrams. An important requirement to be supplied by any temporal data model is the possibility to relate, into the same diagram, time-varying objects with time-invarying objects. This is due to the fact that in information systems some data need to be explicitly related to time and others don't, either because they don't change with time, or because users don't need to know when the facts occurred. • The temporal data model proposed in this work, nominated TempER, presupposes that all entities, being them time-varying or time-invarying, have an "existence", or a temporal validity. At the time-varying entities, named transitory entities, this existence is a subset of points from the time line. In time-invarying entities, named perennial entities, it is assumed that they "always exist", i.e., their temporal validity is constant, implicit, and equal to all points of the time line. Transitory entities, as much as perennial entities, are focused by the TempER model through two perspectives: a temporal perspective and a non-temporal perspective. Through the non-temporal perspective the entities present two dimensions - lines and columns - similar to a conventional entity-relationship model. Through the temporal perspective the entities present three dimensions: the two conventional dimensions and, in addition, the time dimension. While the temporal data model describes the static properties of a system, the behavioral model in the TempER-Tr approach focus the transactions that are executed by the system, in response to the events that occur at the external environment. A certain set of dynamic constraints must be attended so that transactions are enable to occur. This configures a behavior similar to a Petri net. The TempER-Tr model is completely mappeable, inclusive the temporal data model, to the CEM net, a kind of high level Petri net. This way, the semantic of TempER-Tr model is formally specified. In addition, the utilization of the characteristics of Petri nets is possible.
|
354 |
Modelagem temporal de sistemas : uma abordagem fundamentada em redes de petri / Temporal modeling of information systems: a Petri net based approachAntunes, Dante Carlos January 1997 (has links)
Neste trabalho e proposta a abordagem TempER-Tr, uma técnica de modelagem conceitual, fundamentada em rede de Petri, que integra a especificação das propriedades dinâmicas de um sistema a um modelo de dados temporal do tipo entidade relacionamento. Um modelo ou esquema conceitual descreve as propriedades identificadas de um sistema a ser desenvolvido. Estas propriedades podem ser classificadas em propriedades estáticas e propriedades dinâmicas As propriedades estáticas descrevem os estados que o sistema pode alcançar, enquanto que as propriedades dinâmicas descrevem as transições entre estes estados. A modelagem conceitual das propriedades estáticas é normalmente conhecida como modelagem de dados. A modelagem das propriedades dinâmicas é denominada de modelagem funcional ou comportamental. Mais especificamente, o modelo TempER-Tr é uma extensão de um trabalho anterior, conhecido como ER-Tr. No modelo ER-Tr, para descrever as propriedades estáticas de um sistema utiliza-se o modelo entidade-relacionamento convencional. No modelo TempER-Tr passa-se a adotar um modelo entidade-relacionamento temporal. Aliado a isto, uma nova linguagem de anotação, baseada em SQL, com mais poder de expressão é proposta. O modelo entidade-relacionamento convencional não possui dispositivos de modelagem capazes de especificar restrições que envolvam a associação dos objetos com o tempo, exigindo que isto se faca ao nível da modelagem das propriedades dinâmicas. Em um modelo entidade-relacionamento convencional, os conjuntos de entidades e relacionamentos apresentam apenas duas dimensões: a primeira refere-se as instâncias (linhas) e a segunda aos atributos (colunas). Em uma abordagem entidade relacionamento temporal, uma nova dimensão e acrescentada: o eixo temporal, possibilitando que as restrições temporais decorrentes da associação entre os objetos possam ser especificadas ao nível do modelo estático. Um requisito importante a ser preenchido por um modelo de dados temporal é permitir que em um mesmo diagrama seja possível associar objetos (entidades, relacionamentos ou atributos) temporalizados com objetos não temporalizados. lsto porque em sistemas de informação alguns dados precisam ser explicitamente referenciados ao tempo e outros não, ou porque não mudam com o tempo, ou porque é irrelevante ao usuário saber quando os fatos ocorreram. O modelo de dados temporal proposto neste trabalho, denominado TempER, pressupõe que todas as entidades, sejam elas temporalizadas ou não temporalizadas, apresentam uma "existência", ou seja, uma validade temporal. No caso das entidades temporalizadas esta existência é um subconjunto de pontos do eixo temporal. Em virtude disto são chamadas de entidades transitórias. Em relação as entidades não temporalizadas, e assumido que "existem sempre", ou seja, a sua validade temporal é constante, implícita e igual a todo o eixo temporal. Por isto são denominadas entidades perenes. Tanto as entidades transitórias quanto as entidades perenes, são focalizadas pelo modelo TempER através de duas perspectivas: uma intemporal e outra temporal. Através da perspectiva intemporal as entidades apresentam duas dimensões, semelhança do que ocorre em um modelo entidade-relacionamento convencional. Através da perspectiva temporal as entidades apresentam três dimensões, as duas convencionais e mais o tempo. Enquanto que o modelo de dados temporal descreve as propriedades estáticas de um sistema, o modelo comportamental, a outra face da abordagem TempER-Tr, focaliza as transações executadas no interior do sistema, em resposta a eventos que ocorrem no ambiente externo. Estas transações, quando efetivadas, provocam mudanças de estados no sistema. Entretanto, para estarem habilitadas a ocorrer, é necessário que um determinado conjunto de restrições dinâmicas sejam atendidas, o que se configura em um comportamento análogo ao de uma rede de Petri. O modelo TempER-Tr é completamente mapeável, inclusive o modelo de dados temporal, para a rede CEM, um tipo de rede de Petri de alto nível. Isto permite que a sua semântica seja formalmente especificada e possibilita o aproveitamento das características das redes de Petri. / This dissertation presents TempER-Tr approach. TempER-Tr is a conceptual modeling technique based on Petri nets that integrates the specification of the dynamic properties of system to a temporal entity-relationship data model. A model or conceptual schema describes the identified properties of a system. These properties can be classified into static and dynamic properties. The static properties describe the states that the system can reach, while the dynamic properties describe the transitions between the states. The conceptual modeling of the static properties is usually known as data modeling, while behavioral or functional modeling deals with dynamic properties. The TempER-Tr model is an extension of a model known as ER-Tr. In the ER-Tr model, the conventional entity-relationship model is used to describe the static properties of a system. In the TempER-Tr model, it is adopted a kind of temporal entityrelationship model. In addition, a new notation language is proposed, based on SQL, with more expression power. The conventional entity-relationship model doesn't provide tools to specify constraints that involve the association of objects with the time dimension, requiring that this have to be done at the dynamic properties modeling level. At the conventional entityrelationship model the entities and relationships sets present just two dimensions: the first one is related to the instance (lines) and the second to the attributes (columns). At a temporal entity-relationship approach, a new dimension is added: the time line. This way, the temporal constraints can be specified at the level of the static diagrams. An important requirement to be supplied by any temporal data model is the possibility to relate, into the same diagram, time-varying objects with time-invarying objects. This is due to the fact that in information systems some data need to be explicitly related to time and others don't, either because they don't change with time, or because users don't need to know when the facts occurred. • The temporal data model proposed in this work, nominated TempER, presupposes that all entities, being them time-varying or time-invarying, have an "existence", or a temporal validity. At the time-varying entities, named transitory entities, this existence is a subset of points from the time line. In time-invarying entities, named perennial entities, it is assumed that they "always exist", i.e., their temporal validity is constant, implicit, and equal to all points of the time line. Transitory entities, as much as perennial entities, are focused by the TempER model through two perspectives: a temporal perspective and a non-temporal perspective. Through the non-temporal perspective the entities present two dimensions - lines and columns - similar to a conventional entity-relationship model. Through the temporal perspective the entities present three dimensions: the two conventional dimensions and, in addition, the time dimension. While the temporal data model describes the static properties of a system, the behavioral model in the TempER-Tr approach focus the transactions that are executed by the system, in response to the events that occur at the external environment. A certain set of dynamic constraints must be attended so that transactions are enable to occur. This configures a behavior similar to a Petri net. The TempER-Tr model is completely mappeable, inclusive the temporal data model, to the CEM net, a kind of high level Petri net. This way, the semantic of TempER-Tr model is formally specified. In addition, the utilization of the characteristics of Petri nets is possible.
|
355 |
Estudo e experimentação de uma linguagem de modelagem de sistemas baseada em redes de petri e orientação a objetos. / Study and experimentation of a system modeling language based on petri nets and object orientation.CANEDO, Edna Dias. 18 September 2018 (has links)
Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-09-18T16:35:32Z
No. of bitstreams: 1
EDNA DIAS CANEDO - DISSERATAÇÃO PPGCC 2002..pdf: 967964 bytes, checksum: aee05fbebc2049f4cd9fb4dea8a9aa1d (MD5) / Made available in DSpace on 2018-09-18T16:35:32Z (GMT). No. of bitstreams: 1
EDNA DIAS CANEDO - DISSERATAÇÃO PPGCC 2002..pdf: 967964 bytes, checksum: aee05fbebc2049f4cd9fb4dea8a9aa1d (MD5)
Previous issue date: 2002-08-29 / A integração da teoria de redes de Petri com os conceitos da Orientação Objetos surgiu
como uma solução para a decomposição e estruturação de modelos em Redes de Petri. Neste trabalho é apresentado um estudo e experimentação de uma linguagem de modelagem baseada em redes de Petri e Orientação a Objetos (RPOO). RPOO foi definida integrando esses dois formalismos em uma perspectiva ortogonal, permitindo que o sistema modelado tenha duas visões: uma visão do ponto de vista de redes de Petri e uma visão do ponto de vista da Orientação a Objetos. O estudo e experimentação da notação RPOO é efetuado através da sua aplicação na modelagem de sistemas de software real. Para tanto, foram desenvolvidos alguns experimentos de modelagem. Assim, os experimentos desenvolvidos serão utilizados na validação da linguagem RPOO como alternativa para a estruturação e decomposição de modelos em redes de Petri, quando da modelagem de sistemas de software distribuídos e concorrentes. / The integration of Petri nets theory and object oriented-object concepts has emerged
as a solution to decompose and structure Petri net models. In this work it is presented a
study and experimentation of a modeling language based on Petri nets and oriented-object
concepts(RPOO). RPOO was defined by integrating these two formalisms on an orthogonal perspective, allowing that the modeled system has two visions: one Petri net visionand one OO vision. The study and experimentation of RPOO notation is accomplished through its application on the modeling of real software systems. Some experiments of modeling had been developed. These experiments will be used to validate RPOO as an alternative for the structure and decomposition of Petri nets models, when modeling distributed and concurrent software systems.
|
356 |
Automatic Code Generation from a Colored Petri Net Specification for Game Development with Unity3DCarlsson, Martin January 2018 (has links)
This thesis proposes an approach for automatic code generation from a Colored Petri net specification. Two tools were developed for the aforementioned purpose, a Colored Petri net editor to create and modify Colored Petri nets, and an automatic code generator to generate code from a Colored Petri net specification. Through the use of the editor four models were created, these models were used as input to the automatic code generator. The automatic code generator successfully generated code from the Colored Petri net specification, code in the form of component scripts for the Unity3D game engine. However, the approach used by the code generator had flaws such as introducing overhead in the generated code, failing to deal with concurrency, and restricting the types of Colored Petri nets which could be used as input. The aforementioned tools could be used in the future to research the benefits and disadvantages of modeling game systems with Colored Petri nets, and automatically generating code from Colored Petri nets.
|
357 |
Vers des outils efficaces pour la vérification de systèmes concurrents / Towards efficient tools for the verification of concurrent systemsGeffroy, Thomas 12 December 2017 (has links)
Cette thèse cherche à résoudre en pratique le problème de couverture dans les réseaux de Petri et les systèmes de canaux à pertes (LCS). Ces systèmes sont intéressants à étudier car ils permettent de modéliser facilement les systèmes concurrents et les systèmes distribués. Le problème de couverture dans un système de transitions consiste à savoir si on peut, à partir d’un état initial arriver à un état plus grand qu’un état cible. La résolution de ce problème dans les systèmes de transitions bien structurés (WSTS) sera le sujet d’études de la première partie. Les réseaux de Petri et les LCS sont des WSTS. On donnera dans la première partie une méthode générale pour le résoudre rapidement en pratique. Cette méthode utilise des invariants de couverture, qui sont des sur-approximations de l’ensemble des états couvrables. La seconde partie sera consacrée aux réseaux de Petri. Elle présentera diverses comparaisons théoriques et pratiques de différents invariants de couverture. Nous nous intéresserons notamment à la combinaison de l’invariant classique de l’inéquation d’état avec une analyse de signe simple. Les LCS seront le sujet d’études de la troisième partie. On présentera une variante de l’inéquation d’état adaptée aux LCS ainsi que deux invariants qui retiennent des propriétés sur l’ordre dans lequel les messages sont envoyés. La thèse a mené à la création de deux outils, ICover et BML, pour résoudre le problème de couverture respectivement dans les réseaux de Petri et dans les LCS. / The goal of this thesis is to solve in practice the coverability problem in Petri nets and lossy channel systems (LCS). These systems are interesting to study because they can be used to model concurrent and distributed systems. The coverability problem in a transition system is to decide whether it is possible, from an initial state, to reach a greater state than a target state. In the first part, we discuss how to solve this problem for well-structured transition systems (WSTS). Petri nets and LCS are WSTS. In the first part, we present a general method to solve this problem quickly in practice. This method uses coverability invariants, which are over-approximations of the set of coverable states. The second part studies Petri nets.We present comparisons of coverability invariants, both in theory and in practice. A particular attention will be paid on the combination of the classical state inequation and a simple sign analysis. LCS are the focus of the third part. We present a variant of the state inequation for LCS and two invariants that compute properties for the order in which messages are sent. Two tools, ICover and BML, were developed to solve the coverability problem in Petri nets and LCS respectively.
|
358 |
Modelagem e análise de performance de sistemas flexíveis de manufatura baseado em redes de Petri temporizadas: estudo de caso na indústria automobilística. / Modeling and performance analysis of flexible manufacturing systems using timed Petri nets: case study in automobilistic industry.Rossini Sálvio Bomfim dos Santos 20 June 2008 (has links)
A necessidade de aumento de produção, da redução de custos e do aumento da qualidade de bens de consumo, tem motivado a constante evolução dos sistemas de produção, migrando os tradicionais sistemas de produção para os modernos e complexos sistemas de manufatura, onde a performance depende da eficiência dos equipamentos e do controle do processo. Por outro lado, a eficiência dos equipamentos depende de sua confiabilidade e manutenabilidade. Neste trabalho a análise de performance é avaliada com o uso de Rede de Petri p-t-Temporizada e através de simulações, incluindo a avaliação da confiabilidade do processo pela análise da otimização da saída do sistema, isto é, quantidade de itens produzidos. Nesta abordagem, uma lógica linear foi desenvolvida e validada utilizando-se uma comparação de resultados das classes de estados do algoritmo proposto com a ferramenta de simulação Tina para um modelo de um esquema produtor consumidor. Apresenta-se um estudo de caso na indústria automotiva, consistindo na análise dos problemas reais enfrentados em uma fábrica de carrocerias, com o uso da Rede de Petri p-t-Temporizada. / The necessity of growing in production, with reduction of costs and improvement in the quality of consumption good, has motivated the constant evolution of production systems, transforming traditional production systems into the modern and complex manufacturing systems, where the performance depends on the efficiency of the equipment and process control. On the other hand, the equipment efficiency depends of their reliability and maintainability. In this work it is proposed a performance evaluation and analysis with the use of p-t- Timed Petri Nets using simulations, including process reliability analysis of the system through the throughput optimization, i.e., produced amount of goods. In this approach, a linear logic statement was developed and validated using a comparison of results of classes of states between the Tina simulation environment and the algorithm considered for a model of a producing consuming system. A case study in the automotive industry is presented, consisting of the analysis of the real problems found in a body shop plant, with the use of Timed Petri Net.
|
359 |
Verificação formal de sistemas discretos distribuídos. / Formal verification of distribuited discrete systems.Pedro Manuel González Del Foyo 07 December 2009 (has links)
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.
|
360 |
Modelagem e análise de conhecimento para planejamento automático: uma abordagem baseada em GORE e redes de Petri. / Modeling and analysis of knowledge in automated planning: an approach based on GORE and Petri Nets.Javier Martinez Silva 19 December 2016 (has links)
Trabalhos recentes na área de Planejamento e Escalonamento têm gerado uma grande expectativa em relação à aplicação dos resultados em sistemas reais. Neste cenário, métodos, ferramentas e conceitos provenientes das Engenharia do Conhecimento e da Engenharia de Requisitos se tornam fundamentais para caracterizar melhor, entender e especificar os domínios de planejamento. Nesse caso uma especial importância deve ser dada às etapas iniciais do processo, onde o conhecimento sobre o domínio é incompleto e onde existem poucas ferramentas, seja para o suporte ou automação parcial do processo, e as ferramentas já existentes carecem de métodos formais para a modelagem e análise dos requisitos. Neste trabalho propõe-se o ReKPlan (Ambiente para a Engenharia de Requisitos usando KAOS em problemas de planejamento), que usa KAOS, um método orientado a objetivos, para a modelagem de requisitos. Entretanto, o uso do KAOS (ou de qualquer outro método goaloriented) não atende à necessidade de verificar formalmente o comportamento dinâmico quando o alvo são sistemas de planejamento. A proposta deste trabalho é combinar o uso do método orientado a objetivos com o formalismo das Redes de Petri (Rdp) -especificamente a abordagem seguida pelo GHENeSys- para representar e analisar requisitos no projeto de sistemas de planejamento. Finalmente é proposto um método sobre o processo de projeto que, guiado por modelos, gera instruções PDDL servindo de entrada para os planejadores. A método foi aplicado a vários estudos de caso que o avaliam como um mecanismo promissor e eficiente na Engenharia de Requisitos resultando em uma melhor definição dos requisitos em problemas de planejamento. / Recent works in Planning and Scheduling, lead to a great expectations about how to apply achieved results in real systems. In this scenario, methods, tools and concepts from Knowledge and Requirements Engineering seem to be a key issue for characterizing, understanding and specifying the domain of planning problems. In this case a special attention should be given to the initial stages of the process, where knowledge about the domain is incomplete and there are a few tools to support or partially automate the process, and there is a lack of formal methods for modeling and analysis of requirements in the existing tools. This work proposes the ReKPlan (Requirement Engineering Using KAOS for Planning Problems) which uses KAOS, a goal-oriented method, for modeling requirements. However, the use of KAOS (or another goal-oriented method) don\'t seem the most appropriate for formal verification of the dynamic behavior of planning systems. The purpose of this work is to combine the use of KAOS with Petri Nets formalism (Rdp) - GHENeSys approach specifically - for modeling and analyzing requirements in the design of planning system. Finally is proposed a model driven engineering mechanism over a design for guiding, until the generation of PDDL instructions as input for planners to solve problems.
|
Page generated in 0.0411 seconds