Automated design using Genetic Algorithm
This paper is an exploration into the potential of Genetic Algorithms(GA) for automated design of stiff rods and air-muscles based kinetic geometries. It starts with a brief background, which includes the genesis of the research, history and relevant applications of GA.
The hardware components of Magnakit are discussed, along with the simulator’s developed in parallel to the hardware, followed by details of a manual design interface which enables quick and fast digital design of geometries.The development and results of an objective GA are illustrated and discussed, which is a completely automated method of evolving designs based on a logic understood by the computer, i.e. displacement in +x direction after a certain time interval. And finally, the development and results of an interactive GA, which evolves design based on ratings provided by the user through an easy to use interface is described. After gathering results from the three different methods of design, they are compared and each method’s strengths and weaknesses, and their suitable applications are projected. It ends with a discussion about secondary learnings which have come out of this thesis and are worth exploring in the future.
Background and Objectives
My teammates and I were working on building a toolkit which allows makers to build human-scale air actuated geometries quickly and easily. During tests, we realized that most of our designs were either simple geometries or inspired from interesting existing folding geometries, like the Hoberman sphere. We were struggling with visualizing and designing innovative and interesting dynamic geometries because there was no digital tool which could aid us for this specific purpose.
Having experience in working with genetic algorithms (GA), I realized that this is a perfect scenario to use them for automated design of these dynamic geometries. Since we were using a limited kit of parts, the designs were limited by simple rules and constraints. Modern computer’s immense computational power combined with GA has the potential to come up with structurally sound designs we’ll struggle to visualize otherwise.
As discussed by De Jong et al. (1997), the first use of the evolutionary process to solve computational problems can be traced back to the late 1950s by Friedberg (1958). Genetic algorithms (GAs), were first introduced by Holland in the early 1960s and was inspired from simple biological evolutionary systems driven by notions like ”survival of the fittest” and ”continuous production of new offspring”. However, since these systems are driven by coded logic, they could not deal with subjective criteria. For example, Does it look good? Does it taste good? Is it moving elegantly?
The notion of interactive selection in the design of digital graphical lifeforms was first introduced by Dawkins (1986). The basic premise is to let a computer generate a bunch of viable design options and let user/s pick the good ones. The computer then uses this data to generate more relevant options, and repeat the process over and over until a satisfactory design has been achieved. As discussed by Bentley & Corne (2002), it was envisioned as an aid to designers who have to solve complex problems involving a large number of parameters, constraints and conflicting objectives. This enabled designers, artists, architects, and other professionals to integrate GA in their process. Professionals which operate on fuzzy logic and goals which keep changing over time.
Frazer (1995) and his students were one of the pioneers of evolutionary architecture systems in the late 1990s. They tried a variety of techniques like cellular automate to develop structures which involved using repetitive modular components. Gero (1996) and his colleagues investigated the viability of evolution to generate new architectural forms, floor plans, and style-based buildings. Soddu (2002) designed a software which created paintings, architecture, products and so much more with an evolutionary approach. Buelow (2002) developed the Intelligent Genetic Design Tool (IGDT), to evolve design from user interactions. Recently, architectural firms are adopting GAs and other evolutionary techniques in commercial project in different aspects of design.
A similar approach is being tested by companies like Autodesk for commercial applications like the design of lighter and more efficient jetliners, McKnight (2017). The solution is also being rolled out in mainstream CAD software like Fusion360, which can be used by designers directly in their workflow (Figure 1.1). It is apparent that the role of designers and computers is in a flux.
While a lot of work has been done to test the applicability of interactive evolution to drive the design of optimized and aesthetically pleasing architectural structures, it is still vague. Potential approaches have been proposed by Fasoulaki (2008), Buelow (2002) and others. But there is still a lot to be explored.
Is genetic evolution a practical method to develop feasible designs of stiff rods and air- muscles based kinetic geometries?
In this thesis, I am trying to test this hypothesis by building a simulation system for air-actuated geometries (MagnaKit). The whole process can be broadly split into the following steps-
- Build a simulation software which closely reflects the physics and dynamics of the MagnaKit.
- Build an interface which gives full control to the designers, and lets them design manually in a traditional CAD
- Build a GA system for the evolution of geometries based on any objective
- Build an interface over GA which lets a human user guide the evolution using interactive selection.
- Compare the experience and applicability of the above three approaches to designing geometries.
I am also collaborating with the team behind the hardware design of MagnaKit (Figure 1.3), so as to constantly test and get results.
The Simulation Engine
MagnaKit is a kit of parts which enables makers to design and build human-scale kinetic structures quickly and easily. The ’kit’ consists of aluminum rods, 3D printed joints (see Figure 2.1), and air muscles (see Figure 2.2(a)). The hardware development of the joints was going alongside this research, which is why there are some discrepancies in the two aspects of this project. They will be discussed further in this chapter.
Air muscles (also called McKibben PAM or pneumatic artificial muscles) are used as the actuators. They consist of a stretched balloon surrounded by a braided fiber mesh connected by a tube on one side. When air is pumped into the balloon, it inflates and compresses. However, the mesh restricts the expansion of the balloon leaving the muscle to compress in a single axis only. They have been widely used in mobile robots, artificial fine-motion limbs, bio-mimetic robotics, and heavy industries.
They are manufactured by companies like Festo (see Figure 2.2(b)) for industrial purposes, but they are very expensive. We constructed our own without any special tools for a nominal cost.
For digital simulation of air muscles, Kelasidi et al. (2011)’s and Ranjan et al. (2012)’s models were investigated. Eventually, Ranjan et al. (2012)’s model was adopted because it was developed after extensive testing illustrated in his research.
The equation was applied as is in the simulation and no further tests were done to test or improve it, as achieving precision was not the priority. The simulation’s purpose is to capture the essence of the design and aid designer.
The first task was to build a simulation engine which can capture the essence of rods and air muscle based geometries. Processing IDE (https://processing.org/) was chosen as the coding platform because it is supported by open source physics libraries like Toxiclibs (http://toxiclibs.org/), and allows for high customisability. Figures 2.3 and 2.4 attempt to capture the first steps towards the development of the engine showing the transition from 2d to 3d.
In order to test the viability of the physics system, a folding bridge was constructed both physically using MagnaKit and digitally using the simulator (Figure 2.5). Following observations were made-
- The library chosen for simulating physics could only work with universal joints, which was fine when the decision was made. However, Magnakit team developed custom joints (see Figure 2.1), but it was too late to implement them in the simulator. This limitation was overcome by adding diagonal rod elements to the faces to imitate hinge joints.
- We were not using industrially manufactured muscles so each one behaved slightly differ- Also, their behavior changed over time leading to leaks in the balloons after 3-4 hours of heavy usage. Thus, The behavior of muscles in simulator didn’t exactly follow the physical air muscles. But they were acceptable for the time being.
- The process of building the geometry in the simulator involved feeding in the coordinates of nodes and defining the connections directly within the code. This took a lot of time and was difficult to work.
Manual Interface Design
With the simulator up and running, the next step was to design a simple interface which would allow the hardware designers of MagnaKit to play with and test the simulator.
The first version of interface worked in the following way (Figure 3.1)-
- Interface starts with an origin node. Clicking over it activates it and allows the user to decide position of the next
- We decided to go with a square-grid, which meant the user had to choose between one of the two specific lengths (edge or diagonal) for each connection.
- It is possible to connect two existing nodes by activating one and clicking the
- It is also possible to lock some nodes so as to root the geometry to the ground. In reality, the same can be achieved by adding extra weight onto the bottom
- The user has the option to build a rod or a muscle as a connection by pressing a key to toggle.
The first version was tested by 4 users and found unintuitive and difficult to use. Deciding the position of new nodes was a cumbersome part. With the suggestions and comments brought together, a new interface was designed (Figure 3.2)-
- Interface starts with an origin node. Clicking over it activates it and projects all the possible next
- Clicking on one of the projections would make a node at that location and draw a rod/muscle between the
- This allowed users to rapidly build and visualize
One of the users commented that it’s almost like doodling in 3D. The comments were positive, and a few nice designs (Figures 3.3 and 3.4) came out of it.
Additional utility classes were built which allowed users to save the geometry’s information in external files to instantly rebuild it later.
The manual interface worked well if the user already had a good idea about what they want to build. So the next step was to use GA and harness the computer’s immense computational power to automate the designs.
A lot of substantial work has been done in the domain of evolutionary robotics, which gave a footing and inspired the practical work done in this section. Sims (1994) Komosinski & Ula- towski (n.d.) used GA to evolve digital creatures which showed surprisingly life-like behaviour. Komosinski & Ulatowski (n.d.) pushed it further by and built an interface which allowed users to build their own creatures and evolve them. Lipson & Pollack (2000) took this to another level by automating the process of fabrication from the digital, so as to bridge the reality gap, something which has been a huge issue when it comes to robots driven by simulations.
The two most fundamental aspects of any GA is the genotype and the phenotype. Simply put, a genotype is the “code” or the genetic data of an individual. A phenotype is the actual physical reincarnation of the individual.
Clearly, the first step is to generate random geometries. Figures 4.2, 4.3 and 4.4 illustrate how the software to generate random geometries progressed initially.
The random phenotypes coming out of the software were interesting, but impractical when it came to physically building them.
Just like in the last chapter, length of the connections was restricted to two possible lengths based on the rule length2 = sqrt(2)*length1, effectively making length2 a diagonal of a square of edge length1.
It was observed that the designs naturally followed a strict 3D grid because of the restriction on rod lengths. Embracing the ’grid’ made things a lot easier, both in terms of generating phenotypes and storing genotypes in a compressed format and it eventually became the default starting point of the simulation software.
Something which was observed in the evolved creatures of Lipson & Pollack (2000) and consciously implemented in Cheney (2014) was the principle of anti-phase synchronization. This feature was added as well by using two sets of muscles inflating in opposite phases triggered by a clock and was integrated into all future simulations.
The updated software generated random geometries in this order-
- Creates a 3d grid of points in the space. Size of the grid is decided by the user
- Calculates the central point in the grid and makes a node
- Makes a list of 18 immediate neighbors and makes a link to a random one from the
- Picks a random existing node and repeats step 3 for ’n’ number of ’n’ is a parameter pre-decided by the user
- Every new connection can be either a rod or a muscle. The proportions are pre-decided by the user.
Each point in the grid has a unique id based on its position relative to other points in the grid.
uniqueID = positionX + positionY * 100 + positionZ * 10000
The equation above is based on the assumption that there will never be more than 99 points in any axis of the grid.
The genotype is stored in form of a linear array. Each connection is essentially a set of 3 pieces of information. Initially, they were – id of the source node, direction of the connection and type of the link. Eventually, it was changed to – id of the source node, id of the target node and the connection type as it worked better for random generation and cross-breeding (see Table 4.1).
Table 4.1: First version of genotype
Figures 4.6 and 4.7 illustrate two phenotypes born out of different parameters, which give im- pression of a ”life-like” behaviour. Note that these are just random geometries. No evolution has been applied to them yet.
However, when crossover was applied to two different genotypes, many issues started coming up-
- Multiple rods or muscles would appear on the same location after crossover.
- A function was made to avoid the duplicity, but it led to a slow and gradual reduction of the number of connections in the off-springs.
- As more functions were stacked on top of this, the process got computationally heavy for the computer, and eventually, it ran out of resources.
Following this, the genotype was redesigned. The new version was a simple string of numbers which went through each possible link in linear succession and only defined the type of joint present there, including null. So the new genotype looked something like this-
This automatically aligned genotypes of the same size and allowed for clean and simple execution of functions like crossover and mutation.
The program was run with a simple fitness criterion, the distance traveled by geometries towards right direction (+x axis). Additionally, multiple phenotypes were generated at the same time to speed up the process of evolution.
Figure 4.8 and 4.9 illustrates one of the runs. In this specific case, the simulation ran for 50 generations at a mutation rate of 0.05. Each generation had 600 individuals, 60 tested at once in the simulation. The simulation was allowed to run for 10 seconds to let the individuals perform. It then measured their displacement from their starting position. However, it can be seen in Figure 4.9(a) that the seemingly best solution has already been found at around 20th generation. Figure 4.9(b) keeps improving because the evolution is still diverging towards the best solution so far. Figures 4.10 and 4.11 are data from the evolution of slightly more complex geometries highlighting different results.
With the GA working well for an objective criterion, it was time to step further. In its basic form, the system had no way to drive the evolution towards subjective criteria like aesthetics.
As discussed by Bentley & Corne (2002), a lot of work has been done to build GAs which can generate solutions based on fuzzy criteria. One of the most popular ways to do that is by the method of Interactive Selection, a GA guided by a human user.
After Dawkins (1986) introduced interactive selection to drive the evolution of biologically inspired systems, it was used by many scientists, artists, designers to evolve designs on vague and subjective criterion. One of the most successful and popular implementations was by Sims (1993) in his exhibition Genetic Images. He used genetic algorithms to drive the evolution of computer images using visitor’s interest levels as a fitness function. The experiment since has been replicated in lots of different shapes and forms.
Another simple example to illustrate this technique was used by Shiffman (2012) which is illustrated in Figure 4.1. Even though it has been discussed before in the thesis before and with great clarity by the above authors, it is worth revisiting the concept of genotype and phenotype. In words of (Sims 1994, p. 15), “A genotype is a coded representation of a possible individual or problem solution” which are “read to produce phenotypes which are then evaluated according to some fitness criteria and selectively reproduced.”
As discussed by Bentley & Corne (p. 45, 2002), adding human guidance into the evolutionary process can have its pros and cons. They discuss as follows.
- Good searching ability – if evolution seems to get stuck (converge) on a certain type of solution, the user can alter their guidance and force evolution to try
- A wide range of different solutions – the longer user plays with such systems, the more solutions they will
- The ability to evolve solutions for which there is no clear fitness function – if one is unable to figure out a logic behind a criterion, like aesthetics, the software cannot differentiate between good and bad solutions. However, a human being can easily make that assessment.”
- Speed – humans can only judge solutions at a very slow rate, so evolution may take rather long.
- Consistency – humans often change their minds, get distracted or bored, or become influenced by other solutions, so they will not judge solutions
- Coverage – in order to provide effective guidance, users need to judge most (ideally all) solutions in an evolving But as problems get complex, a large population size might be needed, which will lead humans struggling trying to cope with the thousands or millions of evaluations.”
Also discussed by Bentley & Corne (2002) is the potential GA carries in helping the user diverge and explore many different possible solutions before converging into a specific one. ‘Exploitative’ search nature comes naturally to GA and gives it an edge over other machine learning algorithms when it comes to design guided by humans.
A design methodology similar to this holds great potential in our current context. It was observed that the users struggled to visualize the designs of dynamic geometries which can be built using MagnaKit. Most designs which came out of the kit were based on primitive geometries or inspired from existing interesting folding geometries. And while the manual interface discussed in Chapter 3 helped, it still took a lot of time to learn to exploit the potential of air muscles in design.
Using this algorithm, an interface was developed (see Figure 5.3). Instead of placing them on the ground, the geometries were hung on to the ceiling like a chandelier, i.e. all the nodes on the topmost layer were locked. Also, instead of completely random geometries, a pattern was introduced. The pattern was simply a set of random connections which repeats itself. These two changes made the interaction more interesting for the users :
- The user is shown 4 hanging geometries at once.
- Coloured spheres floating under each phenotype represents its ratings.
- All of the spheres are marked neutral(blue) as default.
- As the user uses the mouse to hover over a geometry, the sphere gets bigger so as to highlight itself.
- At this point, the user can mark it good with the left mouse button (or up arrow on the keyboard) or bad using the right mouse button (or down arrow on the keyboard).
- The user can move on and to rate more phenotypes by pressing ’Enter’ key on the keyboard.
- This process keeps repeating until the user is satisfied, at which point he can pause the simulation by pressing ’p’ on the keyboard and have a better look at the final design.
A few important observations came out of the interface after it was tested for a few hours-
- The interface gets boring very quickly if the forms generated in the first generation are not interesting. It helps to start with patterns instead of completely random
- The evolution starts with a very diverse population and lets the user discover and explore a variety of forms (see Figure 4(a)).
- Eventually, the evolution starts converging into similar looking forms based on the user’s likes and dislikes (see Figure 4(b).
- Even if a satisfactory design is not found, the interface is inspiring for the user because it goes through a lot of unique and interesting forms which one might not have imagined or designed
In the above chapters, we went through three different ways to design stiff rods and air muscles based kinetic geometries-
- Manually designing them on a simulator with a point-and-click
- GA based on an objective
- GA driven by a user’s
All three methods of design were tested via prototypes, and observations were discussed in the individual chapters.
Now to answer the research question – Is genetic evolution a practical method to develop feasible designs of stiff rods and air-muscles based kinetic geometries? The short answer is yes. It is indeed, a feasible method of designing dynamic air actuated. But is it the best method? It depends. The three design strategies have their strengths and weaknesses which make them more suitable for specific scenarios and applications which are discussed in Table 6.1.
6.3 Further Discussions
While the GA is working well for simple geometries, it fails at slightly bigger or complex geometries. Beyond simple functions like crossover and mutation, more advanced forms of GAs have been developed. Cheney (2014) used (Compositional Pattern Producing Networks) CPPN, a more sophisticated genetic algorithm to evolve air actuated digital creatures which exhibited “natural looking morphology and behaviour”. He also pushed the boundaries of complexity, an issue regarding genetic evolution that has been felt and discussed extensively in work of Lipson & Pollack (2000). There is a lot of room for improving the GA developed in this thesis. However, unlike Lipson & Pollack (2000), Cheney (2014) made no attempts to create physical counterparts of the generated digital robots, which is crucial to us.
It was observed that some individuals which showed high potential during the evolution did not survive the crossover cause they could not compete in the initial runs. Some of the strategies mentioned be (Bentley & Corne 2002, p. 15) might work really well to improve solve this, i.e. “Distributed GAs” where “multiple populations are separately evolved with few interactions between them”, or “GAs with niching and speciation” where “the population within the GA is segregated into separate species”, or “Injection Island GAs” where “separate populations” are evolved and occasionally “good solutions are injected from one” population “into another”.
It is easy to get lost in the digital world and come up with interesting and complex forms which might be impossible to produce in reality. The reality gap is a very real issue, and strategies have been developed to encounter it, like in the work of Jakobi et al. (1995). Lipson & Pollack (2000) and Bongard et al. (2006) developed very innovative and effective strategies to counter the reality gap.
Besides the fact that it’s limited to only universal joints (as opposed to a hinge joint included in MagnaKit), the muscles in the simulator also do not truly reflect the air muscles in the physical toolkit. It is important to note that the MagnaKit in its current state does not include industrially manufactured air muscles and joints. Therefore it’s not worth trying to get perfect realism in the simulator. For the sake of this thesis, the simulator is there to capture the essence of air actuated geometries which can be built using the kit.
Unlike natural evolution, the system of artificial evolution can only work within the parameters first set up by the user. In fact, it relies on well-defined parameters to produce favorable results. But while the software can sometimes generate solutions which are original, surprising, innovative and efficient solutions, it will always be restricted by its initial parameters. Bentley & Corne (2002) proposes removing all (or most) of the initial constraints to allow the computer to be truly original and innovative. However, in reality, a constraint-less GA in our context will lead to a search space so large that it might never diverge into something coherent. While constraining the evolution not negate the use of GA in any creative process, in my opinion, this is the biggest difference between a human and a code being ‘creative’.
Since the only input expected from the user is judging the displayed phenotypes, more and more people with no prerequisite skills or qualifications can be involved in the design. Potentially, this can also allow people from different disciplines take part in the design process and reach a well-balanced solution which satisfies all. This has been explored before in the design of aerodynamic structures and by Buelow (2002) for the evolution of architectural structures with Intelligent Genetic Design Tool (IGDT).
After looking at how the three different design strategies have different strengths and weaknesses, one cannot help but wonder if its possible to have a design tool which combines these three strategies into one. A user could start sketching manually driven by a personal inspiration and then enable interactive GA to help him get through to the end. Another user could combine interactive and objective GA to produce an efficient and aesthetically pleasing design. Another user could guide the interactive GA to design something which is almost perfect but finishes it off manually. A design tool like this holds great potential for many applications. McKnight (2017) has already dived into something like this with Fusion360.
Aaronson, L. (2016), ‘Check out the original patent for the hoberman sphere.’.
URL: https://lsc.org/news-and-social/news/check-out-the-original-patent-for-the- hoberman-sphere
Aschenbeck, K. S., Kern, N. I., Bachmann, R. J. & Quinn, R. D. (2006), Design of a quadruped robot driven by air muscles, in ‘The First IEEE/RAS-EMBS International Conference on Biomedical Robotics and Biomechatronics, 2006. BioRob 2006.’, pp. 875–880.
Bentley, P. J. & Corne, D. W. (2002), – an introduction to creative evolutionary systems, in P. J. Bentley & D. W. Corne, eds, ‘Creative Evolutionary Systems’, The Morgan Kaufmann Series in Artificial Intelligence, Morgan Kaufmann, San Francisco, pp. 1 – 75. URL: http://www.sciencedirect.com/science/article/pii/B9781558606739500355
Bongard, J., Zykov, V. & Lipson, H. (2006), ‘Resilient machines through continuous self- modeling’, Science 314(5802), 1118–1121. URL: http://science.sciencemag.org/content/314/5802/1118
Buelow, P. V. (2002), Chapter 12 – using evolutionary algorithms to aid designer of architectural structures, in P. J. Bentley & D. W. Corne, eds, ‘Creative Evolutionary Systems’, The Morgan Kaufmann Series in Artificial Intelligence, Morgan Kaufmann, San Francisco, pp. 315 – 336. URL: http://www.sciencedirect.com/science/article/pii/B9781558606739500501
Cheney, N. (2014), ‘Unshackling evolution: evolving soft robots with multiple materials and a powerful generative encoding.’, ACM SIGEVOlution. 7(1), pp. 11–23.
Dawkins, R. (1986), The Blind Watchmaker, London: Penguin.
De Jong, K., Fogel, D. & Schwefel, H.-P. (1997), ‘A history of evolutionary computation’, pp. A2.3:1–12.
Fasoulaki, E. (2008), Genetic algorithms in architecture : a necessity or a trend ? Frazer, J. (1995), ‘An evolutionary architecture’.
Friedberg, R. M. (1958), ‘A learning machine: Part i’, IBM J. Res. Dev. 2(1), 2–13. URL: http://dx.doi.org/10.1147/rd.21.0002
Gero, J. (1996), ‘Design tools that learn: A possible cad future’. Honus (n.d.), ‘How to make air muscles!’. URL: https://www.instructables.com/id/How-to-make-air-muscles!/
Jakobi, N., Husbands, P. & Harvey, I. (1995), ‘Noise and the reality gap: The use of simulation in evolutionary robotics.’, Morn F., Moreno A., Merelo J.J., Chacn P. (eds) Advances in Artificial Life. ECAL 1995. Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence) 929.
Kelasidi, E., Andrikopoulos, G., Nikolakopoulos, G. & Manesis, S. (2011), ‘A survey on pneu- matic muscle actuators modeling’, 6.
Knuth, D. (n.d.), ‘More on punctuated equilibrium’. URL: https://evolution.berkeley.edu/evolibrary/article/side00/punctuated01
Komosinski, M. & Ulatowski, S. (n.d.), ‘Framsticks’. URL: http://www.framsticks.com/
Lipson, H. & Pollack, J. (2000), ‘Automatic design and manufacture of robotic lifeforms.’, Nature 406(6799), pp. 974–8.
McKnight, M. (2017), ‘Generative Design: What it is? How is it Being Used? Why its a Game Changer!’, The International Conference on Design and Technology. pp. 176–181.
Ranjan, R., Upadhyay, D. P. K., Kumar, D. A. & Dhyani, D. P. (2012), Theoretical and experi- mental modeling of air muscle.
Rapid-Kinetic (n.d.), ‘Rapid-kinetic’. URL: https://rapid-kinetic.com
Shiffman, D. (2012), ‘Nature Of Code’, https://natureofcode.com/book/ chapter-9-the-evolution-of-code/. Accessed: 2018-07-06.
Sims, K. (1993), ‘Genetic Images’, http://www.karlsims.com/genetic-images. html. Accessed: 2018-07-06.
Sims, K. (1994), ‘Evolving Virtual Creatures’, Proceedings of the 21st annual conference on computer graphics and interactive techniques. pp. 15–22.
Soddu, C. (2002), Creative evolutionary systems, Morgan Kaufmann Publishers Inc., San Fran- cisco, CA, USA, chapter Recognizability of the Idea: The Evolutionary Process of Argen`Ia, pp. 109–127. URL: http://dl.acm.org/citation.cfm?id=510349.510353