Connection Grammar

This package provides tools to generate interconnected objects whose connection points are defined by a context-free grammar. If you want to start using this or hacking on it, check out the getting started guide.

Overview

The field of computational design synthesis involves using computer algorithms to create designs to meet a set of engineering requirements. There are many tools and algorithms available to aid in computational design synthesis[5]. Generative grammars are one broad class of solutions to this problem.

This work uses context-free grammars to represent valid connections between objects. This is somewhat similar in concept to previous grammar systems for generating trees or algae[10]. The generated a language issues commands to a 3D object printer. It moves and rotates an imaginary print head and issues requests to place objects. This is similar to the "turtle interpretation" for L-systems [15] described in [3]:

The concept is based on the idea of an imaginary turtle that walks, turns and draws according to instructions given. At any time the turtle has a current position in 3-space and a heading vector (the forward direction of movement). Individual letters in a string are treated as commands. Different letters change position or heading, record vertices in a polygon, apply pre-defined surfaces to the current position and orientation, change colour, etc.

A picture is worth a thousand words, so here is a graphical explanation from [7]:

As in other procedural modeling grammar applications [11], non-terminal symbols generically represent opportunities for our grammar to grow new structures.

While context-free grammars are suitable for modeling possible connections, they do not have a concept of global state and cannot "see" the rest of the generated objects. A second layer fitness function, modeling a user-defined global rule set, is required to generate object graphs that adhere to specific global parameters. This is similar to the methods used in other work [1][2]. In the case of simple interconnected shapes, a 3D collision space may be a suitable fitness function to ensure a physically valid shape. Additional rules can be added to ensure that a generated shape is suitable in other ways. For example, rules could be added for thermal dissipation to model behavior of various shapes for use as a heat sink.

Grammar production rules may also be assigned a probability to model possible interconnections as a probabilistic context-free grammar (PCFG). This allows each created model to be unique, and provides a product designer with more tools to enhance their creative work[9].

Complexity

The underlying complexity of this process creates the need for a few optimizations.

Exponential Brute-force Solution

At the highest level, this algorithm is searching all utterances of a grammar and attempting to find the best fit against a fitness function. Because most CFGs can produce countably infinite valid utterances, we at minimum need some sort of bound on language length.

There are many ways to accomplish this, but there are also some other practical considerations for this problem. Namely, the number of strings generated by a grammar increases exponentially with the allowed string length. Because we have to evaluate each produced string, our total complexity is O(cⁿ).

Exponential complexity is generally intractable, and our case is no exception. Any practical application necessitates a large n and a relatively complex fitness function, so in order for this algorithm to run in reasonable time, we need to make some significant compromises.

Linear Time Simplification

The simplification that I have chosen to implement for this project is to optimize for local maxima instead of global maxima. This means that we are likely going to miss the best global solution, but we can find a solution in linear time instead of exponential time.

Specifically, we will simply apply the production rule to the left-most non-terminal that produces the best fitness without considering any other possible non-terminals. This would be akin to solving the Traveling Salesman Problem by simply visiting the next closest point on each iteration. This is clearly sub-optimal, but for many applications we can design and organize our grammar rules in a clever way to produce reasonable results.

In particular, grammar rules that are most likely to produce the best global results should be tested first. This both ensures that they win ties, and ensures that they are immediately used in the case that multiple rules return optimal fitness.

The final algorithm for fitting a model to the fitness function is as follows:

1. Initialize a list of symbols containing only the start symbol.
2. Find the left-most non-terminal symbol.
3. Generate a new text by applying a production rule that we have not tried yet.
4. Check the generated text against our fitness function and store the result.
5. Repeat back to (3) for each production rule.
6. Apply the production rule that returned the highest fitness (first rule wins in case of a tie).
7. Repeat back to (2) until the string contains only terminals.

One practical benefit of this algorithm is that it may allow certain types of fitness functions to cache and build on previous results increasing real-world performance. This technique is used in some of the following examples to produce structures with n>3000 in under 15 seconds on modest hardware using a fairly slow interpreted language. This could likely be done in real-time if properly optimized.

Examples

This package and basic algorithm could be used to model many kinds of interconnected structures. For demonstration purposes, I will explore interconnected stud-and-tube-based building blocks such as [4]:

This sort of system is familiar to most people. Using this for demonstration eliminates the need to describe external domain knowledge as part of an explaining this methodology. It also has the convenient side-effect of being a cheap physical object that can be quickly assembled for debugging and problem solving.

Despite its simple appearance, blocks of this nature to provide enough interesting behavior to demonstrate the complexity that can be generated using context-free grammars. For example, blocks may only be stacked, so in order to move laterally multiple blocks must be stacked in an interconnected pattern.

Stack of Bricks

Trivially, this system can be used to generate a stack of bricks linearly upwards in a single dimension. This simplistic example provides a good starting point for demonstration purposes.

Program Generation

The following is a simple grammar that could be used to generate instructions for a basic brick tower:

Stud -> 'Move(0,-1,0)' 'Place("Brick1x1")' Stud
Stud -> ɛ

Adding a simple fitness function to return perfect fitness unless we have more than 3 bricks in the model will allow us to generate a placement program. Here are the steps for the generation process:

1. Stud (Start symbol in our grammar)
   • 0 Elements
   • Fitness: 1.0
2. Move(0,-1,0) Place("Brick1x1") Stud
   • 1 Element
   • Fitness: 1.0
3. Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Stud
   • 2 Elements
   • Fitness: 1.0
4. Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Stud
   • 3 Elements
   • Fitness: 1.0
5. Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Stud
   • 4 Elements
   • Fitness: 0.0
   • Our element list now contains more than three elements, so it fails our simple fitness test.
   • Therefore, we don't apply this production rule and instead try the next one.
6. Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1") Move(0,-1,0) Place("Brick1x1")
   • 3 Elements
   • Fitness: 1.0
   • We now have only terminals, so we have generated a complete, valid program.

Program Execution

Now that we have the program generated, let's step through the program execution. The only state we need to consider is the current position and the list of placed elements:

1. Program initialization

   • position = (0,0,0)
   • elements = []

2. Execute Move(0,-1,0)

   • position = (0,-1,0)
   • elements = []

3. Execute Place("Brick1x1")

   • position = (0,-1,0)
   • elements = [("Brick1x1",0,-1,0)]
   • Rendered output:

4. Execute Move(0,-2,0)

   • position = (0,-2,0)
   • elements = [("Brick1x1",0,-1,0)]

5. Execute Place("Brick1x1")

   • position = (0,-2,0)
   • elements = [("Brick1x1",0,-1,0), ("Brick1x1",0,-2,0)]
   • Rendered output:

6. Execute Move(0,-1,0)

   • position = (0,-3,0)
   • elements = [("Brick1x1",0,-1,0), ("Brick1x1",0,-2,0)]

7. Execute Place("Brick1x1")

   • position = (0,-3,0)
   • elements = [("Brick1x1",0,-1,0), ("Brick1x1",0,-2,0), ("Brick1x1",0,-3,0)]
   • Final rendered output:

Stacked Bricks with Rotation and Translation

The stacking example represents some of the basic concepts, but it is a simplification of the complete system. In addition to the above instructions, this system also implements Rotate to adjust the direction of the head. Move instructions adjust position relative to head direction, and Place instructions use head direction to determine the orientation of placed objects. Positions are also stored on a stack and can be pushed and popped in order to simplify grammar and program design.

The state of a running program consists of:

1. A stack of head positions. This is initialized with one position at the origin. A position is represented as a 4-tuple (x, y, z, rotation_matrix). The rotation matrix is a standard 3x3 3D transformation matrix.
2. A list of elements. Elements are represented as a 3-tuple of (position, color, name).

Rotation and translation are important, as connections between these building blocks and many other physical objects depend on connections being made at specific locations and orientations. This applies in many contexts including screws lining up with associated holes in a connected part and surface-mount PCB connectors properly aligning with their mate. Including rotation and translation in our system allows us to model complex connection types in 3D space.

Program Generation

Consider the following grammar that includes translation in the xz plane as well as head rotation:

Stud -> 'Move(-2,0,0)' 'Rotate(90)' 'Move(-3,-3,-1)' 'Place(3001)' 'Move(-3,0,-1)' Stud
Stud -> ɛ

Using the same simple fitness function as before to limit us to three elements, this grammar will generate the following placement program:

Move(-2,0,0)
Rotate(90)
Move(-3,-3,-1)
Place(3001)
Move(-3,0,-1)
Move(-2,0,0)
Rotate(90)
Move(-3,-3,-1)
Place(3001)
Move(-3,0,-1)
Move(-2,0,0)
Rotate(90)
Move(-3,-3,-1)
Place(3001)
Move(-3,0,-1)

Stepping through the program will generate the following:

1. Execute Move(-2,0,0) Rotate(90) Move(-3,-3,-1) Place("Brick2x4") Move(-3,0,-1)

![](ex