Sites Inria

Version française

Applied Mathematics, Computation and Simulation

7/05/2007

A(rt)lgorithm, design informed by mathematics

The Centre Pompidou in Paris is currently offering specialists as well as the general public a new exhibition of its permanent collection of contemporary and modern art. This artistic voyage includes an introduction to the new wave of international architects and designers, including EZCT Architecture & Design Research and their chair prototypes, created with evolutionary algorithms developed by Inria researchers

Two worlds come together

This unprecedented convergence between art and mathematics was initiated by EZCT architects and their exploration of the relationship between computing and architecture. Through their research, EZCT architects are part of the current interweaving of science and technology, collaborating with theorists and academics from a broad range of disciplines. This innovative approach appealed to Marc Schoenauer, an Inria computer scientist and head of Tao project-team. The resulting collaboration is based on the novel idea of approaching architectural problems with evolutionary algorithms, using the representative case of chair design. Marc Schoenauer and Hatem Hamda, one of his former doctoral students, focused on the "evolution" of chairs: how to minimise their weight while maintaining their ability to withstand one or several loads (such as a seated person). Their investigations were based on evolutionary algorithms.

(R)evolutionary algorithms

According to Charles Darwin (1809–1882), the evolution of natural species is governed by the conjunction of two key mechanisms: the so-called blind variations which occur in genetic material as it is passed from parents to offspring, and natural selection, which tends to favour individuals who are best adapted to their environment as a result of random variations. This very simplified mechanism can be transferred to computers using evolutionary algorithms; the most well-known amongst them are genetic algorithms.
To resolve a given problem, researchers make a population of individuals artificially evolve by randomly modifying their characteristics from one generation to the next, and by selecting those that best answer the question posed. To design the chair's shape (so it doesn't collapse when we sit on it), researchers create a population of chairs with computers, which they then "cross", allowing random mutations to occur. They select for the most resistant chairs for a given manner of sitting.
The two key questions are thus:

  • How should a chair's quality be judged , or to put it more simply, how should two structures designed as chairs be compared to determine which is more likely to produce offspring that will actually function as chairs.
  • How can structures be represented using computers , so that 1) the representation makes it possible to model real chairs, and 2) the random manipulation of these representations through crossing and mutation enables researchers to explore, with maximal efficiency, a set of structures as broad as possible, in order to discover the most interesting specimens from an architectural point of view.

Chair selection criteria

The researchers have obtained an answer to the first question: the chair must be as light as possible while still being able to withstand the load of a seated person. The necessary resistance is computed using the finite element method, widely applied in industry (aeronautics, automotive, etc.). The designer imagines situations with someone seated on the chair, applying different forces to various areas of the structure; the maximal authorised deformations are also considered. The level of structural adaptation is thus given by the weight of the chair, to which penalties are added for exceeding the authorised deformation limits.
It should be noted that for the experiments presented here, all loads are static. In other words, the possibility of someone sitting on the chair with excessive force is not considered, only the situation where he or she is actually seated. Dynamic calculation is required for more realistic results. While this presents no conceptual difficulties, it does considerably increase computation time.

How should the (future) chairs be represented?

This involves finding a computerised representation that is as general as possible, with a view to the structures' "genetic" evolution. For simplicity, they are represented as consisting of a single material. We will also assume that these structures remain confined to a predefined domain. Rather than trying to represent each small spatial element that will be used to calculate the level of adaptation of these structure-chairs, it is more efficient to use a higher-level representation, which in this case is based on Voronoi diagrams.
Imagine a group of rubber balloons with fixed centres. They are inflated until they meet other balloons or the boundaries of the authorised domain, partitioning this domain into convex polygons (see figure 1, left). If certain balloons are filled with matter, and the others remain empty, all the matter together constitutes a structure within the authorised domain – in other words, a possible chair.
In more mathematical terms, a Voronoi diagram is a set of points within the domain of definition; these points are called Voronoi sites. Each site is associated with a Voronoi cell, including all the points in the domain that are closer to this site than to any other. Together these cells partition the domain into convex polygons. As for the computing aspect, the genome of each individual-chair simply consists of the set of Voronoi sites and the status of each site's cell as empty or full. This makes it easy to imagine the operators of Darwinian variation for these individuals:

  • Two parent structures recombine, thereby exchanging sites (see figures). Once the domain of definition is separated into two parts, the sites on one side are exchanged between the two structures, and each structure is then reconstituted from the new set of sites. The underlying idea is to recombine the best parts of each structure, for example the back of one individual, selected because this element gave it an advantage over its peers, together with the equally advantageous seat of another individual. The basic idea was to have a non-zero probability of obtaining a chair-offspring that performs better than both of its chair-parents.

  •  There is also a small probability that each structure will undergo mutations, which consist either in changes in the positions of the existing Voronoi sites (see Figure 3), or in the random addition of new sites, or the elimination of existing sites. These mutations are usually very slight, but on occasion they may significantly modify the structure (the distance sites are moved follows a Gaussian law, for example).

But where do architects come in?

The method proposed is not (yet?) intended as an alternative to the complete design chain, but rather an exploratory tool allowing designers to develop new design ideas which would be difficult to imagine directly, and to meet initial specifications. Furthermore, the random nature of algorithms makes it possible to find a number of different solutions to the same problem, accentuating the creative aspect of the process.
But ultimately, the result depends exclusively on the expertise of the computer engineer and the architect (who are ideally the same person) and on their choices in designing the algorithm, from the representation and variation operators, to the definition of what constitutes a well-adapted structure and the accompanying simulations (choice of domain, fixed components to which force is applied, the forces themselves). The results generated with these algorithms may serve as an excellent source of inspiration for designers, offering new possibilities for continued research.

Keywords: Saclay - Île-de-France Marc Schoenauer Algorithm Design

Top