Assembly planning is difficult and tedious, but is necessary for complex products. This thesis presents a novel approach to automating assembly planning utilizing graph grammars. Computational geometric reasoning is used to produce a label rich graph from a CAD model. This graph is then modified by graph grammar rules to produce candidate assembly sequences which are run in conjunction with a tree search algorithm. An evaluation system then evaluates partial assembly sequences, which are used by the tree- search to find near-optimal assembly sequences. / text

In this thesis, a new graph grammar representation is proposed to reason about the manufacturability of solid models. The knowledge captured in the graph grammar rules serves as a virtual machinist in its ability to recognize arbitrary geometries and match them to various machine operations. Firstly, a novel convex decomposition algorithm has been developed to decompose a given part into multiple sub-volumes, where each sub-volume is assumed to be machined in one operation or to be non-machinable. Then the decomposed part is converted into a graph so that graph grammar rules can determine the machining details. A candidate plan is a feasible sequence of all of the necessary machining operations needed to manufacture this part. If a given geometry is not machinable, the rules will fail to find a complete manufacturing plan for all of the sub-volumes. As a result of this representation, designers can quickly get insights into how a part can be made and how it can be improved based upon the feedback of the rules. A variety of tests of this algorithm on both simple and complex engineering parts show its effectiveness and efficiency. / text

With the increasing demand of fast-paced and hybrid manufacturing processes in modern industry, it is desirable to expedite the iterations between design and manufacturing through intelligent computational techniques. In this research, we propose a concurrent approach of this kind to streamline the design and manufacturing processes. With this approach, a CAD design is automatically analyzed in terms of its manufacturability in the early design stage. If the part is manufacturable, a set of process plans optimized in time, cost, fixture quality and tolerance satisfaction are reported in real time. If the part is not manufacturable, the potential design changes are provided for better manufacturing. In the approach, the geometric information of 3D models and the empirical knowledge in manufacturing processes, fixtures, and tolerances are combined and encapsulated into a graph-grammar based reasoning. The reasoning systematically extracts meaningful manufacturing details that later constitute complete process plans for any given solid model. The plans are then evaluated and optimized using a specially designed multi-objective best first search technique. The complete approach enables a concurrent and efficient manufacturability analysis tool that closely resembles real manufacturing planning practice. Numerous case studies with real engineering parts are presented to characterize the novelty and contributions of this approach. The optimality of the suggested plans is verified through computational comparisons, and the practicality of the plans is validated with hands-on implementations on the shop floor. / text

This work presents an enhancement of a search process that is suited for a problem that can be solved using a graph grammar based generative tree. Generative grammar can be used to generate a vast number of design alternatives by using a seed graph of the problem and a set of transformation rules. The problem is to find the best solution among this space by doing the least number of evaluations possible. In a previous paper, an interactive algorithm for searching in a graph grammar representation was presented. The process was demonstrated for a problem of tying a necktie and the work here builds on top of this process to be useful for solving engineering problem. To test the search process, two problems, a photovoltaic array topology optimization problem and an electromechanical product redesign problem, are chosen. It is shown this search process converges in finding the best solution within a few hundred evaluations which is a manageable number compared to the large solution space of millions of candidates. Further optimization and tweaks are done on the process to control exploration vs. exploitation and find the parameters for fastest convergence and the best solution. / text

O crescimento da complexidade e do tamanho dos sistemas computacionais atuais suscitou um aumento na dificuldade de extração e especificação de modelos formais desses sistemas, tornando essa atividade cada vez mais dispendiosa, tanto em tempo quanto em custo. Modelos são utilizados em diversas técnicas da Engenharia de Software, com o intuito de auxiliar em processos que compreendem desde o desenvolvimento de novos softwares, até reconstrução de um sistema a partir de software legado, passando pela realização de manutenção de um software em operação. Portanto, é necessário que essas abstrações sejam confiáveis e representem fielmente o software real. Nesse sentido, a adoção de métodos formais para a construção e análise de modelos computacionais é crescente e motivada, principalmente, pela confiabilidade que os formalismos matemáticos agregam aos modelos. No entanto, a utilização de métodos formais geralmente demanda um alto investimento de recursos humanos e, consequentemente, financeiros, uma vez que a utilização de tais formalismos é condicionada ao estudo profundo de sua fundamentação matemática. Considerando-se a extensa aplicabilidade de modelos em diversas subáreas da Ciência da Computação e as vantagens advindas da utilização de métodos formais para especificar sistemas, é interessante identificar métodos e ferramentas existentes para automatizar os processos de extração e análises de modelos, em conjunto com a adoção de formalismos que possam ser utilizados por profissionais da computação que atuam na indústria de software. Dessa forma, é estimulada nesse trabalho a utilização do formalismo de Gramática de Grafos, um método formal que diferencia-se dos demais por ser intuitivo e possuir uma representação visual gráfica, o que facilita a sua compreensão e não exige um conhecimento avançado sobre o formalismo. Primeiramente, é proposta uma abordagem para a extração de modelos em Gramática de Grafos a partir de código-fonte, extraindo informações de execuções de código Java anotado. Em seguida, é apresentada uma metodologia existente para extração e análise de Gramática de Grafos a partir de Casos de Uso, juntamente com um estudo empírico realizado a fim de validar a metodologia. Por fim, são propostas possíveis verificações adicionais, a fim de extender as análises dessa metodologia. Com isso, busca-se a obtenção de modelos, descritos através do formalismo de grafos, a partir de artefatos criados nos dois pólos do processo de desenvolvimento de software, antes e depois da implementação, no sentido de viabilizar futuras comparações, no contexto de verificação de software. / The growing size and complexity of current computer systems leading to an increase in the difficulty of extraction and specification of formal models of such systems, making it increasingly expensive activity, both in time and in cost. Models are used in various techniques of software engineering in order to assist in processes that range from the development of new software, to rebuild a system from legacy software, passing for performing maintenance of software in operation. Therefore, it is necessary that these abstractions are reliable and faithfully represent the actual software. In this sense, the adoption of formal methods for the construction and analysis of models is growing and motivated mainly by the reliability that the mathematical formalism add to models. However, the use of formal methods generally demands a high investment in human resources and hence financial, since the use of such formalism is conditioned to the deep study of its mathematical foundation. Considering the extensive applicability of models in various subfields of computer science and the benefits arising from the use of formal methods for specifying systems, it is interesting to identify existing methods and tools to automate the process of extracting models, in addition to the adoption of formalism that can be used by computer professionals working in the software industry. Thus, we encourage the use of the Graph Grammar formalism, a formal method that differs from others because it is intuitive and has a graphical visual representation, making it easy to understand and does not require an advanced knowledge of the formalism. First, we propose an approach for extracting models from source code in Graph Grammar, getting information of executions of annotated Java code. Then an existing methodology for extraction and analysis of Graph Grammar from Use Cases is presented, along with an empirical study to validate the methodology. Finally, we propose possible additional checks in order to extend the analysis of this methodology. Thus, this work aims to extract models, described by the formalism of graphs, from artifacts created in the two poles of the software development process, before and after implementation, in order to allow future comparisons, in the context of software verification.

Vias biológicas representam interações entre entidades químicas complexas (proteínas, substratos, metabólitos etc.) que ocorrem no nível molecular das células. A representação e compreensão do comportamento destas vias é o principal alvo de estudos da Biologia Sistêmica. Esta área de estudos envolve a construção de modelos matemáticos que possam simular in silico (computacionalmente) o comportamento destes sistemas biológicos verificados in vivo (experimentalmente). Do ponto de vista computacional é evidente que tais sistemas são complexos para abordar e descrever de modo intuitivo. São necessários modelos com valor preditivo, isto é, que permitam descrever os comportamentos do sistema que são experimentalmente verificáveis. Algumas notações gráficas foram propostas para descrever vias biológicas. Entre elas, os diagramas de processos tem sido amplamente utilizados. Um diagrama de processos é essencialmente um grafo no qual vértices e arestas representam componentes biológicos, e há uma notação gráfica associada com cada elemento. Nesta dissertação propomos uma fundamentação formal para a linguagem dos diagramas de processos definindo a sintaxe usando gramática de grafos. Nós definimos primeiramente um grafo chamado BioProc, descrevendo o meta-modelo dos diagramas de processos. Instâncias do grafo BioProc são portanto diagramas de processos modelando vias biológicas. Para descrever a semântica foi proposta uma tradução algébrica dos grafos BioProc para redes de Petri estocásticas generalizadas (GSPNs) já amplamente utilizadas na modelagem de processos biológicos. O uso de gramática de grafos como formalismo intermediário na tradução habilita a verificação sintática da via com a checagem dos tipos válidos que podem ser definidos para cada reação antes da simulação na rede de Petri e usá-las posteriormente para explorar propriedades estruturais e estocásticas do modelo. Além disso serve como base para a evolução do modelo proposto. Isto é relevante já que modelos frequentemente são construídos incrementalmente para se adaptar a novos requisitos e/ou incluir novas características. / Biological pathways represent interactions between complex chemical entities (proteins, substrates, metabolites, etc.) that occur at the molecular level of cells. The representation and comprehension of biological pathways behavior is the main target of research in the field of Systems Biology. This area investigates the construction of mathematical models that can simulate in silico (computationally) the behavior of biological systems checked in vivo (experimentally). From a computational view point it is clear that such systems are too complex to analyze and describe in an intuitiveway. Models with predictive value are needed, describing the behaviors that are experimentally verifiable. There are some graphical notations to describe biological pathways. Among them, process diagrams have been widely used. A process diagram is essentially a graph in which vertices and edges represent biological components, and there is a graphical notation associated with each element. In this master thesis we give a formal foundation for biological process diagrams, by defining their (concrete and abstract) syntax and semantics using a formalism called graph grammars. We first build a graph called BioProc Graph, describing the meta-model of process diagrams. Instances of this BioProc graph are concrete process diagrams modeling biological pathways. To describe the semantics we proposed a translation of BioProc diagrams to generalized stochastic Petri networks (GSPNs) already widely used in modeling biological processes. The use of graph grammar formalism as a basis for translation enables the syntatic verification to check the valid types that can be defined for each reaction after the simulation of Petri net and before that to explore structural and stochastic properties of the model. In addition it serves as the basis for model evolution proposed. This is relevant because models are often built incrementally to adapt to new requirements and/or include new features.

O crescimento da complexidade e do tamanho dos sistemas computacionais atuais suscitou um aumento na dificuldade de extração e especificação de modelos formais desses sistemas, tornando essa atividade cada vez mais dispendiosa, tanto em tempo quanto em custo. Modelos são utilizados em diversas técnicas da Engenharia de Software, com o intuito de auxiliar em processos que compreendem desde o desenvolvimento de novos softwares, até reconstrução de um sistema a partir de software legado, passando pela realização de manutenção de um software em operação. Portanto, é necessário que essas abstrações sejam confiáveis e representem fielmente o software real. Nesse sentido, a adoção de métodos formais para a construção e análise de modelos computacionais é crescente e motivada, principalmente, pela confiabilidade que os formalismos matemáticos agregam aos modelos. No entanto, a utilização de métodos formais geralmente demanda um alto investimento de recursos humanos e, consequentemente, financeiros, uma vez que a utilização de tais formalismos é condicionada ao estudo profundo de sua fundamentação matemática. Considerando-se a extensa aplicabilidade de modelos em diversas subáreas da Ciência da Computação e as vantagens advindas da utilização de métodos formais para especificar sistemas, é interessante identificar métodos e ferramentas existentes para automatizar os processos de extração e análises de modelos, em conjunto com a adoção de formalismos que possam ser utilizados por profissionais da computação que atuam na indústria de software. Dessa forma, é estimulada nesse trabalho a utilização do formalismo de Gramática de Grafos, um método formal que diferencia-se dos demais por ser intuitivo e possuir uma representação visual gráfica, o que facilita a sua compreensão e não exige um conhecimento avançado sobre o formalismo. Primeiramente, é proposta uma abordagem para a extração de modelos em Gramática de Grafos a partir de código-fonte, extraindo informações de execuções de código Java anotado. Em seguida, é apresentada uma metodologia existente para extração e análise de Gramática de Grafos a partir de Casos de Uso, juntamente com um estudo empírico realizado a fim de validar a metodologia. Por fim, são propostas possíveis verificações adicionais, a fim de extender as análises dessa metodologia. Com isso, busca-se a obtenção de modelos, descritos através do formalismo de grafos, a partir de artefatos criados nos dois pólos do processo de desenvolvimento de software, antes e depois da implementação, no sentido de viabilizar futuras comparações, no contexto de verificação de software. / The growing size and complexity of current computer systems leading to an increase in the difficulty of extraction and specification of formal models of such systems, making it increasingly expensive activity, both in time and in cost. Models are used in various techniques of software engineering in order to assist in processes that range from the development of new software, to rebuild a system from legacy software, passing for performing maintenance of software in operation. Therefore, it is necessary that these abstractions are reliable and faithfully represent the actual software. In this sense, the adoption of formal methods for the construction and analysis of models is growing and motivated mainly by the reliability that the mathematical formalism add to models. However, the use of formal methods generally demands a high investment in human resources and hence financial, since the use of such formalism is conditioned to the deep study of its mathematical foundation. Considering the extensive applicability of models in various subfields of computer science and the benefits arising from the use of formal methods for specifying systems, it is interesting to identify existing methods and tools to automate the process of extracting models, in addition to the adoption of formalism that can be used by computer professionals working in the software industry. Thus, we encourage the use of the Graph Grammar formalism, a formal method that differs from others because it is intuitive and has a graphical visual representation, making it easy to understand and does not require an advanced knowledge of the formalism. First, we propose an approach for extracting models from source code in Graph Grammar, getting information of executions of annotated Java code. Then an existing methodology for extraction and analysis of Graph Grammar from Use Cases is presented, along with an empirical study to validate the methodology. Finally, we propose possible additional checks in order to extend the analysis of this methodology. Thus, this work aims to extract models, described by the formalism of graphs, from artifacts created in the two poles of the software development process, before and after implementation, in order to allow future comparisons, in the context of software verification.

Vias biológicas representam interações entre entidades químicas complexas (proteínas, substratos, metabólitos etc.) que ocorrem no nível molecular das células. A representação e compreensão do comportamento destas vias é o principal alvo de estudos da Biologia Sistêmica. Esta área de estudos envolve a construção de modelos matemáticos que possam simular in silico (computacionalmente) o comportamento destes sistemas biológicos verificados in vivo (experimentalmente). Do ponto de vista computacional é evidente que tais sistemas são complexos para abordar e descrever de modo intuitivo. São necessários modelos com valor preditivo, isto é, que permitam descrever os comportamentos do sistema que são experimentalmente verificáveis. Algumas notações gráficas foram propostas para descrever vias biológicas. Entre elas, os diagramas de processos tem sido amplamente utilizados. Um diagrama de processos é essencialmente um grafo no qual vértices e arestas representam componentes biológicos, e há uma notação gráfica associada com cada elemento. Nesta dissertação propomos uma fundamentação formal para a linguagem dos diagramas de processos definindo a sintaxe usando gramática de grafos. Nós definimos primeiramente um grafo chamado BioProc, descrevendo o meta-modelo dos diagramas de processos. Instâncias do grafo BioProc são portanto diagramas de processos modelando vias biológicas. Para descrever a semântica foi proposta uma tradução algébrica dos grafos BioProc para redes de Petri estocásticas generalizadas (GSPNs) já amplamente utilizadas na modelagem de processos biológicos. O uso de gramática de grafos como formalismo intermediário na tradução habilita a verificação sintática da via com a checagem dos tipos válidos que podem ser definidos para cada reação antes da simulação na rede de Petri e usá-las posteriormente para explorar propriedades estruturais e estocásticas do modelo. Além disso serve como base para a evolução do modelo proposto. Isto é relevante já que modelos frequentemente são construídos incrementalmente para se adaptar a novos requisitos e/ou incluir novas características. / Biological pathways represent interactions between complex chemical entities (proteins, substrates, metabolites, etc.) that occur at the molecular level of cells. The representation and comprehension of biological pathways behavior is the main target of research in the field of Systems Biology. This area investigates the construction of mathematical models that can simulate in silico (computationally) the behavior of biological systems checked in vivo (experimentally). From a computational view point it is clear that such systems are too complex to analyze and describe in an intuitiveway. Models with predictive value are needed, describing the behaviors that are experimentally verifiable. There are some graphical notations to describe biological pathways. Among them, process diagrams have been widely used. A process diagram is essentially a graph in which vertices and edges represent biological components, and there is a graphical notation associated with each element. In this master thesis we give a formal foundation for biological process diagrams, by defining their (concrete and abstract) syntax and semantics using a formalism called graph grammars. We first build a graph called BioProc Graph, describing the meta-model of process diagrams. Instances of this BioProc graph are concrete process diagrams modeling biological pathways. To describe the semantics we proposed a translation of BioProc diagrams to generalized stochastic Petri networks (GSPNs) already widely used in modeling biological processes. The use of graph grammar formalism as a basis for translation enables the syntatic verification to check the valid types that can be defined for each reaction after the simulation of Petri net and before that to explore structural and stochastic properties of the model. In addition it serves as the basis for model evolution proposed. This is relevant because models are often built incrementally to adapt to new requirements and/or include new features.

O crescimento da complexidade e do tamanho dos sistemas computacionais atuais suscitou um aumento na dificuldade de extração e especificação de modelos formais desses sistemas, tornando essa atividade cada vez mais dispendiosa, tanto em tempo quanto em custo. Modelos são utilizados em diversas técnicas da Engenharia de Software, com o intuito de auxiliar em processos que compreendem desde o desenvolvimento de novos softwares, até reconstrução de um sistema a partir de software legado, passando pela realização de manutenção de um software em operação. Portanto, é necessário que essas abstrações sejam confiáveis e representem fielmente o software real. Nesse sentido, a adoção de métodos formais para a construção e análise de modelos computacionais é crescente e motivada, principalmente, pela confiabilidade que os formalismos matemáticos agregam aos modelos. No entanto, a utilização de métodos formais geralmente demanda um alto investimento de recursos humanos e, consequentemente, financeiros, uma vez que a utilização de tais formalismos é condicionada ao estudo profundo de sua fundamentação matemática. Considerando-se a extensa aplicabilidade de modelos em diversas subáreas da Ciência da Computação e as vantagens advindas da utilização de métodos formais para especificar sistemas, é interessante identificar métodos e ferramentas existentes para automatizar os processos de extração e análises de modelos, em conjunto com a adoção de formalismos que possam ser utilizados por profissionais da computação que atuam na indústria de software. Dessa forma, é estimulada nesse trabalho a utilização do formalismo de Gramática de Grafos, um método formal que diferencia-se dos demais por ser intuitivo e possuir uma representação visual gráfica, o que facilita a sua compreensão e não exige um conhecimento avançado sobre o formalismo. Primeiramente, é proposta uma abordagem para a extração de modelos em Gramática de Grafos a partir de código-fonte, extraindo informações de execuções de código Java anotado. Em seguida, é apresentada uma metodologia existente para extração e análise de Gramática de Grafos a partir de Casos de Uso, juntamente com um estudo empírico realizado a fim de validar a metodologia. Por fim, são propostas possíveis verificações adicionais, a fim de extender as análises dessa metodologia. Com isso, busca-se a obtenção de modelos, descritos através do formalismo de grafos, a partir de artefatos criados nos dois pólos do processo de desenvolvimento de software, antes e depois da implementação, no sentido de viabilizar futuras comparações, no contexto de verificação de software. / The growing size and complexity of current computer systems leading to an increase in the difficulty of extraction and specification of formal models of such systems, making it increasingly expensive activity, both in time and in cost. Models are used in various techniques of software engineering in order to assist in processes that range from the development of new software, to rebuild a system from legacy software, passing for performing maintenance of software in operation. Therefore, it is necessary that these abstractions are reliable and faithfully represent the actual software. In this sense, the adoption of formal methods for the construction and analysis of models is growing and motivated mainly by the reliability that the mathematical formalism add to models. However, the use of formal methods generally demands a high investment in human resources and hence financial, since the use of such formalism is conditioned to the deep study of its mathematical foundation. Considering the extensive applicability of models in various subfields of computer science and the benefits arising from the use of formal methods for specifying systems, it is interesting to identify existing methods and tools to automate the process of extracting models, in addition to the adoption of formalism that can be used by computer professionals working in the software industry. Thus, we encourage the use of the Graph Grammar formalism, a formal method that differs from others because it is intuitive and has a graphical visual representation, making it easy to understand and does not require an advanced knowledge of the formalism. First, we propose an approach for extracting models from source code in Graph Grammar, getting information of executions of annotated Java code. Then an existing methodology for extraction and analysis of Graph Grammar from Use Cases is presented, along with an empirical study to validate the methodology. Finally, we propose possible additional checks in order to extend the analysis of this methodology. Thus, this work aims to extract models, described by the formalism of graphs, from artifacts created in the two poles of the software development process, before and after implementation, in order to allow future comparisons, in the context of software verification.

Vias biológicas representam interações entre entidades químicas complexas (proteínas, substratos, metabólitos etc.) que ocorrem no nível molecular das células. A representação e compreensão do comportamento destas vias é o principal alvo de estudos da Biologia Sistêmica. Esta área de estudos envolve a construção de modelos matemáticos que possam simular in silico (computacionalmente) o comportamento destes sistemas biológicos verificados in vivo (experimentalmente). Do ponto de vista computacional é evidente que tais sistemas são complexos para abordar e descrever de modo intuitivo. São necessários modelos com valor preditivo, isto é, que permitam descrever os comportamentos do sistema que são experimentalmente verificáveis. Algumas notações gráficas foram propostas para descrever vias biológicas. Entre elas, os diagramas de processos tem sido amplamente utilizados. Um diagrama de processos é essencialmente um grafo no qual vértices e arestas representam componentes biológicos, e há uma notação gráfica associada com cada elemento. Nesta dissertação propomos uma fundamentação formal para a linguagem dos diagramas de processos definindo a sintaxe usando gramática de grafos. Nós definimos primeiramente um grafo chamado BioProc, descrevendo o meta-modelo dos diagramas de processos. Instâncias do grafo BioProc são portanto diagramas de processos modelando vias biológicas. Para descrever a semântica foi proposta uma tradução algébrica dos grafos BioProc para redes de Petri estocásticas generalizadas (GSPNs) já amplamente utilizadas na modelagem de processos biológicos. O uso de gramática de grafos como formalismo intermediário na tradução habilita a verificação sintática da via com a checagem dos tipos válidos que podem ser definidos para cada reação antes da simulação na rede de Petri e usá-las posteriormente para explorar propriedades estruturais e estocásticas do modelo. Além disso serve como base para a evolução do modelo proposto. Isto é relevante já que modelos frequentemente são construídos incrementalmente para se adaptar a novos requisitos e/ou incluir novas características. / Biological pathways represent interactions between complex chemical entities (proteins, substrates, metabolites, etc.) that occur at the molecular level of cells. The representation and comprehension of biological pathways behavior is the main target of research in the field of Systems Biology. This area investigates the construction of mathematical models that can simulate in silico (computationally) the behavior of biological systems checked in vivo (experimentally). From a computational view point it is clear that such systems are too complex to analyze and describe in an intuitiveway. Models with predictive value are needed, describing the behaviors that are experimentally verifiable. There are some graphical notations to describe biological pathways. Among them, process diagrams have been widely used. A process diagram is essentially a graph in which vertices and edges represent biological components, and there is a graphical notation associated with each element. In this master thesis we give a formal foundation for biological process diagrams, by defining their (concrete and abstract) syntax and semantics using a formalism called graph grammars. We first build a graph called BioProc Graph, describing the meta-model of process diagrams. Instances of this BioProc graph are concrete process diagrams modeling biological pathways. To describe the semantics we proposed a translation of BioProc diagrams to generalized stochastic Petri networks (GSPNs) already widely used in modeling biological processes. The use of graph grammar formalism as a basis for translation enables the syntatic verification to check the valid types that can be defined for each reaction after the simulation of Petri net and before that to explore structural and stochastic properties of the model. In addition it serves as the basis for model evolution proposed. This is relevant because models are often built incrementally to adapt to new requirements and/or include new features.