Spring-mass systems in Artificial Life

Accurate soft body simulation in silico is routinely achieved by physicists and engineers through Finite Element Modelling (FEM). This modelling method works by dividing solids in a mesh, and solving the equations at the mesh's points. Although it can produce very realistic simulations, this method is computationally very expensive.

In contrast, soft bodies can also be simulated by using spring-mass systems: meshes of points connected by springs. This method is far simpler than FEM, although it lacks of several features:

  • it is usually very hard to figure out the parameters of the points and springs to accurately simulate a given material.
  • numerical stability strongly depends on the quadrature method and its step size.
  • Simulation results strongly depend on the mesh's geometry and discretization.
  • Shape stability is harder to achieve with spring-mass systems.

Even taking into account these inconvenients, spring-mass systems make a good compromise to simulate soft bodies, since they are easier to code and computationally less expensive than FEM, and can provide a reasonably good simulation unless ultimate realistic simulations are required.

Therefore, spring-mass systems have been fairly popular in a wide array of applications related to Artificial Life, whenever soft body simulation is needed. Simulations of organisms can be roughly classified in two lvels: those at a coarse grain level, using points as cells and springs as intercellular forces, and those at a more detailed level, using a mesh to model each cell.

 Let's review spring-mass systems in the context of AL.

 

Computer Graphics

While it can be argued that realistic Computer Graphics are at the very fringe of serious Artificial Life research, this discipline has undoubtedly pioneered techniques that were later applied to more serious research, like the use of spring-mass systems. In 1988 , Miller used a spring-mass model to mimic the movement of snails and snakes, in order to render realistic Computer Graphics. Following this work, Tu's thesis (1994) developed spring-mass models to realisticly simulate fish's movements and behaviours. Tu's work (and his colleage's, 1995, 1996) was a cornerstone for Computer Graphics based on spring-mass models. After their work, tens to hundreds of researchers have used spring-mass models for Computer Graphics. Tu and his colleagues ’s work is the most cited in this area.

 

Virtual Environments

 A number of master thesis have been devoted to create virtual environments to simulate Artificial Life. These works are usually as concerned with achieving graphical appeal as well as with defining a rich physical environment to model complex creatures, so they sit at the borderline bewteen Computer Graphics and Artificial Life proper. While there are quite a number of environments for rigid body creatures (following the graphical appeal of Sims' creatures), environments for soft-body ones are somewhat scarcer. Two examples are Urban's (2001) and Noser's (2003)

 

Artificial organisms for image segmentation

 The work by Harmaneth and McIntosh is, a priori, a somewhat unexpected research line, marrying two seemingly unrelated fields: Artificial Life and Image Processing. They have found a innovative way to include physical constraints in the segmentation process to get more accurate segmentations. To this end, they use virtual objects called artificial organisms: spring-mass meshes  with a layered control system, each layer including segmentation knowlodge at a levels ranging from color intensity to morphological cues. These organisms are placed over medical images (as X-ray images), and then move through the image, using the color levels and the organism's shape as an input to the control layers. In turn, the control layers make the organism to to move and warp. These techniques have been applied to 2D images (2005) as well as 3D images (2006a , 2006b).


Artificial embryogeny

 Artificial embryogeny is a slowly emerging field; it arrived in the 1990s as Artificial Life gained momentum. Several research lines coexist, the most obvious being the modelling of embryogeny processes to understand their dynamics. However, the use of soft-body simulations is not widespread, given the high computational costs. Artificial embryogeny is frequently used to model real life processes; in this respect, researchers have long studied plant structures' embryogeny, and some have used spring-mass systems: Rudge (2005a , 2005b) uses springs to model cells'  walls, while Mjolsness (2006) models at a more coarse grain level, using points as cells and springs as intercellular forces.In this respect, it is worth to note that spring-mass systems have been used together with L-systems to create stunningly realistic models of plants (1990).

A closely related line is implicit encoding: in evolutionary computation, the map from genotype to phenotype is usually straightforward, which usually leads to performance issues when problems are either scaled up or rendered more complex. To improve scalability in evolutionary algorithms, implicit encoding techniques are used: the genotype does not specifies the phenotype, but controls a developmental process that builds the phenotype. By using implicit encoding, the genotype can be far less shorter for larger or more complex problems. Again, spring-mass systems are harder to find in this context than simpler counterparts, but examples do exist. Eggenberger's work on embryogeny and shape encoding (2003) uses genetic networks to warp spring meshes into embryo-like movements.


Soft-body artificial organisms

Several models of artificial organisms based on spring-mass systems also make use of artificial embryogeny; it is the case of Thomas' tehcnical report (1999) describing swimming creatures very akin to Ventrella's SwimBots, and Devert's trusses (2008), which are evolved to maximize strength while minimizing used material. The trusses' shape and distribution of material are defined by a developmental program using spring-mass systems that are warped by a genetic control system (although for fitness evaluation they are simulated as finite element bodies).

Other works involving artificial organisms based on spring-mass models do not use physic-based embryogenies, as  Luca's (2002) and Komatsu's (2008), both working on implicit encoding techniques for evolving graphs. Interestingly, Komatsu's testbed is SodaRace, a platform based on SodaPlay. Sodaplay is a platform for designing and simulating spring-mass artificial organisms, while SodaRace is a framework to let these organisms to compete in races, a well established way to enable open-ended evolution. Some people have tried to extend SodaRace to enable other ways of competition, like Lam's SodaSumo (2008), a sort of wrestling game for SodaPlay creatures

Other works, while still using organisms based on spring-mass systems, do not use any embryogeny at all, as Jones' work (2008 ) on control of bilateralian movements.


Cell simulation 

A few thesis are focused on simulating real cells as soft bodies made of spring-mass systems; in this concern, it is worth to mention Nilsson's thesis (2008), that models embryonic cells in the C. elegans embryogeny. Cell membranes are spring meshes, while cell volume and turgence is recreated by simulating the cell's internal pressure. Another relevant work is Muddana's thesis (2006), that interestingly uses uses spring-mass systems to model the cell's cytoskeleton as a tensegrity structure. Both works are 3D.

More abstract is Astrom's paper (2006 ),  that uses 2D models of cell membranes as sprin-mass systems with internal pressure (much like Nilsson's work) to research the physics of densely packed cell aggregates.