micahveilleux.com

  

Lego Bridge Builder

Micah Veilleux, Phil Carter, and Walter Pierce

The java applet on this page attempts to use a simulated annealing algorithm to optimize a bridge made out of legos. Initially, a rectangular array of lego bricks is placed so as to span the gap between two "ground bricks." Then a simulated annealing algorithm makes random mutations to the layout of the bricks, favoring changes that are determined to improve bridge stability. Once a stable bridge design has been produced, the algorithm continues to mutate the design (preserving the bridge's stability), but now favors changes that reduce the weight of the bridge. This applet was written as a project for a modeling and simulation class at Christopher Newport University in the fall of 2008, under professor David Heddle. The inspiration for this work and a more comprehensive project on "Computer Evolution of Buildable Objects" can be found here.

Broken!

Lego bridge optimizer

Color Meaning
  Ground brick
  Brick/joint with unknown stress
  Supported brick / joint with no stress
  Joint with some stress
  Unsupported brick / joint at maximum stress
  Overstressed joint

Determining bridge stability

Bridge stability was determined by a network flow algorithm, which is applied individually to each brick in the bridge design. The weight of each brick (see table below) must be distributed to one or both of the ground bricks. Starting with a "selected brick," a path is found connecting it to a ground brick, and the torques on joints along that path are adjusted (if possible, see table below) to account for some or all of the selected brick's weight. As many paths as possible are examined until the selected brick's weight can be absorbed. If it is not possible to absorb the selected brick's weight, one of the joints will be overtorqued in the hope that later on it will be torqued back in the opposite direction. This process is repeated for every brick in the current design. Bricks and paths are selected randomly.

Brick size Brick weight (grams)
2 0.75
4 1.5
6 2.25
8 3.0
10 3.75
12 4.5
Joint overlap Maximum torque (μN⋅m)
2 37.37
4 163.08
6 339.75
8 374.91
10 386.97
12 392.97

Note that this method will sometimes falsely identify a bridge as unstable, though it will never declare an unstable bridge stable. To be perfect, it would have to simultaneously distribute the weight of all bricks — a much more difficult problem.

The initial bridge design is likely to be unstable, and must be modified until it becomes stable. To determine whether modifications make the design more or less stable, it is necessary to measure how unstable a bridge is. This applet measures stability by summing up the absolute value of the torques on each overtorqued joint. This is an imperfect measure of stability, as the torques are assigned by an imperfect algorithm. As the algorithm assigns torques by choosing bricks and paths in a random order, repeated stability measurements of the same bridge design may not be equal. Even so, this measure of stability serves its purpose.

There is one more stability requirement; if a modification causes the bridge to break in half (so there is no path from one ground brick to the other), the bridge is declared unstable.

Optimizing the bridge

In the first stage of bridge optimization the goal is a stable bridge. Optimization is achieved with a simulated annealing algorithm. Bridge stability is measured, then a small modification (or mutation) is made to the bridge design, and stability is remeasured. If the modified design is more stable than the original design, the new design is kept. If it is less stable, it may still be kept. A new mutation is then considered, and the process repeats until a stable bridge is found or 1000 mutations occur without success. For each step, one of the following mutations is selected:

Undesirable mutations (which result in a less stable bridge design) are permitted to prevent the algorithm from getting stuck in local minima, as the goal is to find the absolute minimum (a stable bridge). An undesirable mutation will be kept if e-E⁄T is greater than a random number between 0 and 1. The energy (E) is set to the difference between the stability as measured before and after the mutation. The temperature is T=imax-i⁄0.8i, where i is the current iteration and imax is the total number of iterations. The energy serves to rank undesirable mutations on a scale that goes from bad to worse, so the worse ones can be discouraged. Temperature serves to discourage undesirable mutations as the algorithm proceeds to iterate (hopefully), towards a stable bridge design.

In the second stage of bridge optimization the goal is to minimize bridge weight. There are only a few differences in the algorithm used in this case. The energy is the bridge weight before and after a mutation, and the temperature is now set to 1000e-10i. The bridge mutates as before, except that mutations which break the stability of the bridge are forbidden. If all goes well, the result is an optimized lego bridge!