Browsing by Subject "Graph grammar"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
Item Assembly sequencing through graph reasoning : graph grammar rules for assembly planning(2013-12) Manion, Charles Austin; Campbell, Matthew I.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.Item A concurrent approach to automated manufacturing process planning(2014-05) Fu, Wentao; Campbell, Matthew I.; Crawford, Richard H.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.Item A graph grammar based approach to automated manufacturing planning(2012-05) Fu, Wentao; Campbell, Matthew I.; Eftekharian, Ata A.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.Item A graph grammar scheme for representing and evaluating planar mechanisms(2010-05) Radhakrishnan, Pradeep, 1984-; Campbell, Matthew I.; SV, SreenivasanThere are different phases in any design activity, one of them being concept generation. Research in automating the conceptual design process in planar mechanisms is always challenging due to the existence of many different elements and their endless combinations. There may be instances where designers arrive at a concept without considering all the alternatives. Computational synthesis aims to arrive at a design by considering the entire space of valid designs. Different researchers have adopted various methods to automate the design process that includes existence of similar graph grammar approaches. But few methods replicate the way humans’ design. An attempt is being made in the thesis in this direction and as a first step, we focus on representing and evaluating planar mechanisms designed using graph grammars. Graph grammars have been used to represent planar mechanisms but there are disadvantages in the methods currently available. This is due to the lack of information in understanding the details of a mechanism represented by the graph since the graphs do not include information about the type of joints and components such as revolute links, prismatic blocks, gears and cams. In order to overcome drawbacks in the existing methods, a novel representation scheme has been developed. In this method, labels and x, y position information in the nodes are used to represent the different mechanism types. A set of sixteen grammar rules that construct different mechanisms from the basic seed is developed, which implicitly represents a tree of candidate solutions. The scheme is tested to determine its capability in capturing the entire set of feasible planar mechanisms of one degree of freedom including Stephenson and double butterfly linkages. In addition to the representation, another important consideration is the need for an accurate and generalized evaluator for kinematic analysis of mechanisms which, given the lack of information, may not be possible with current design automation schemes. The approach employed for analysis is purely kinematic and hence the instantaneous center of rotation method is employed in this research. The velocities of pivots and links are obtained using the instant center method. Once velocities are determined, the vector polygon approach is used to obtain accelerations and geometrical intersection to determine positions of pivots. The graph grammar based analysis module is implemented in an existing object-oriented grammar framework and the results have found this to be superior to or equivalent to existing commercial packages such as Working Model and SAM for topologies consisting of four-bar loop chain with single degree of freedom.Item Rule based stochastic tree search(2011-12) Kumar, Mukund; Campbell, Matthew I.; Crawford, RichardThis 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.