Methodology Overview

Graph transformation systems, or graph grammars, are a branch of graph theory research that rigorously defines mathematical operations such as addition and intersection in graphs. Mathematicians have developed the foundations of this research, and engineering design researchers have appropriated the concept to formalize the creation of complex engineering systems. Electric circuits, truss structures, and chemical processes are just a few of the artifacts of engineering design that are easily represented by graphs. When viewing the artifact as a graph constructed from an initial simpler graph that describes the problem, one needs to develop a set of rules to capture the valid transformations that can occur. The grammar rules, organized into rule sets are then subject to a generation process. This process has three step steps: recognize, choose, and apply as illustrated in Figure 1.

the recognize, choose, and apply process
Figure 1: For creative systems, we consider three distinct steps of 1) recognizing what rules are applicable, 2) choosing one of these rules to apply, and 3) the application of the rule which involves a graph transformation of the host to a newly synthesized state.














Representation

Rules and graphs in GraphSynth are stored in an XML format and are loaded into the program and instantiated as define graph object: nodes and arcs. Grammar rules are essentially constructed of two elements: application conditions (that, if met, are valid transitions in the state-space tree), and application instructions (how the graph is to be altered). These two elements are each represented as a graph: the conditional, recognition, or left-hand-side graph; and the application or right-hand-side graph. Figure 2 represents several rules created with GraphSynth thus far.

For more detail on recognition,
click here.

For more detail on application,
click here.




















example rule with properties window

                                                                                                                                 Figure 2: Two example rules created with
                                                                                                                                               GraphSynth: a) this first rule is from sheet metal research, where a patch of sheet metal is removed by a side notching operation. In addition to drawing the graph in GraphSynth, the designer can also change important parameters within the properties window. b) The second rule is created for the research on NSF Grant IIS-0307665 (Creating a Computational Theory for Conceptual Design) wherein function structure elements are replaced with real components.

another example rule

A rule set is essentially a set of rules that capture the space for a particular design problem. In implementing rules, the researchers have discovered that many applications require more than one rule set . Furthermore, when the number of rules becomes large it is easy to create inconsistencies amongst the rules. Therefore we allow for multiple rule-sets to capture the entire space of solutions. Figure 3 represents the graphical view of a rule set. These are described in more detail here.
 

The Big Picture

Figure 3: An example Rule-Set from the sheet-metal research. In addition, to the rules contained within a rule-set, there are additional properties such as how the rule-set terminates, and what additional rule-sets are to be invoked.
Figure 3: An example Rule-Set from the sheet-metal research. In addition, to the rules contained within a rule-set, there are additional properties such as how the rule-set terminates, and what additional rule-sets are to be invoked.

Within the source files of GraphSynth, you will find the details for classes like grammarRule.cs and ruleSet.cs are stored in the project named “Representation”. The other main projects are :  “Generation”, “GraphLayout”, “Evaluation”, “Guidance”, “Application_UI_and_Search.” This final one, is the main one, the ".exe" is found in its bin directory. The other projects compile to DLL''s. The authors of GraphSynth theorize that the division of representation, generation, evaluation, and guidance is useful in almost all computational synthesis methods. This generalization can be captured by the flowchart shown in Figure 4.

Figure 4: The generic flowchart for Computational synthesis has four basic divisions: a representation of the design space, a method for generating new solutions, a method for evaluating solutions, and a method for guiding the search process.
Figure 4: The generic flowchart for Computational synthesis has four basic divisions: a representation of the design space, a method for generating new solutions, a method for evaluating solutions, and a method for guiding the search process.  

The representation is formulated by the programmer of the computational design method to capture the forms or attributes of the design space. For example, in genetic algorithms, the representation is usually a bit-string that represents the key decision variables in the process. Using this representation, candidate solutions are generated in the generation task. In genetic algorithms, this is done by mutating and “crossing over” existing or parent candidates. Each generated candidate is evaluated in the evaluation task to determine how well it meets the objectives and constraints of the design problem. Based on the objectives calculated for the candidates a guidance strategy is implemented to inform the search process of how to find better solutions in the subsequent iterations. In genetic algorithms, this is the “survival of the fittest” tournament selection where candidates with inferior fitness values are removed from the search process.

                                                              Other than these in GraphSynth, the
                                                              project named GraphLayout contains
                                                              custom layout algorithms that the
                                                              researcher may write for their
 resulting graphs. Within the Application_UI_and_Search project, there is folder called MainFormsAndSettings which include start up routines, and the display forms. The one file searchProcess.cs not included in the directory is likely where a researcher would write their main search routine. In fact, in each project the ".cs" file not included in a subdirectory is open to modification. These are searchProcess.cs, inheritedGraphClasses.cs, graphLayout.cs,  GetToOptimum.cs, and EvaluateSwirls.cs. The latter two or for the facetious example presented in the searchProcess.cs file. These should be studied and then deleted. They merely offer an example of how the projects are intended to  interact. For a particular application, one would create their own evaluation methods, and thus there is no general methods that can be provided for this. For guidance strategies, there are currently no such methods for graph synthesis. Our current research is developing a number of these. In the meantime, GraphSynth can be use to synthesize graphs, either through user-guided or random decisions. Future updates will include guidance methods, and thus a full optimization procedure can be made to design optimal graph topologies. Earlier, a description of the basic representation classes was provided. In addition to GraphSynth also provides a clear way that graphs are created through a main generation class. The details of this are described here.

Last edited Feb 8, 2014 at 6:04 PM by mattica, version 1