Planning meets self-organization: Integrating interactive evolutionary computation with cellular automata for urban planning

Abstract

The experiment carried by the author in 2010 is to test if self-organizing systems could be systematically regulated according to the users preference for global behavior. Self-organizing has been appreciated by architects and urban planners for its richness in the emerging global behaviors; however, design and self-organizing are contradictory in principle. It seems that it is inevitable to balance the design and self-organization if self-organization is employed in a design task. There have been approaches combining self-organizing with optimization process in a parallel manner. This experiment strives to regulate a self-organizing system according to non-defined objectives via real-time interaction between the user and the computer. Particularly, cellular automaton is employed as the self-organizing system to model a city district.

Keywords

Interactive ; Evolutionary ; Self-organization ; Cellular automata

1. Background

1.1. Self-organization

The concept of self-organization emerged from a wide range of fields such as biology, physics, chemistry, and computer science. Later it also appeared in the field of architecture and planning. We can group these fields into two categories: the natural and the artificial. The former observes certain extraordinary phenomena in natural systems and interprets them by self-organization; the latter constructs artificial systems running in a self-organizing manner for novel solutions to certain problems. Generally speaking, there are two primary problems about self-organization: how it works and how to utilize it.

It is an interesting phenomenon that the concept of self-organization always diffuses in a bundle of other concepts such as emergence, bottom-up, agent-based system, complex adaptive system and swarm intelligence. One reason for the overlapping of the concepts is that they do share some common subconcepts. Self-organization has two most basic concepts: interacting components (agents) and increase in organization. In short, local interaction leads to global behavior. Concepts like emergence, agent-based systems also cover the two concepts though the interpretations might be slightly different. Besides, a third point is often added to self-organization: there is no centralized control over the system. However, it seems that centralized control is not always excluded in self-organizing systems. The critical point is how the control associates with the global behavior. For example, the evolutionary process of bacteria in laboratories is usually considered to be self-organizing though there is a deliberate control on survival pressure. In principle, the two essential points of self-organization lead to a probabilistic model that facilitates people to study the connections between local and global, between control and adaptation.

Emergence is sometimes confused with self-organization . De Wolf and Holvoet (2005) argued that there is self-organization without emergence, as well as emergence without self-organization (Figure 1 ). For example, an iron chain under force would increase in order (self-organization) but there is no emergence before certain global patterns are observed (Figure 1 (a)); in contrast, the gas in a container has emergent features such as volume and temperature without increase in internal organization (Figure 1 (b)). Of course, self-organization and emergence can take place simultaneously in one system (Figure 1 (c)). From a different point of view, Parunak and Brueckner (2004) argued that the two concepts are orthogonal (Figure 2 ):

Figure 1. Three systems.

Figure 2. Self-organization and emergence.

we propose distinguishing between self-organization and emergence on the basis of the contrast between the horizontal concept of system boundary and the vertical concept of levels.

1.2. Integrating global objectives and self-organization

During the last decade there have been many attempts of employing self-organization in planning and architectural design. Since self-organization is a bottom-up process, regulating the self-organizing system for global objectives is a critical problem. A wide range of new techniques have been experimented to integrate specific objectives and self-organization process. On one hand, they are able to address various design criteria, on the other hand they can make novel articulations due to the self-organizing process.

One important assumption is that centralized control process can be parallel with the self-organizing process. For example, a try-and-error routine taking account of global statistics can be added to the self-organizing system: the global statistics are calculated once the states of agents are altered, then the new states are adopted if the statistics are improved (otherwise, the old states are restored). However, the centralized routine can be more advanced to the genetic algorithm. Besides the global control routine, the agents also interact with each other with local information in a self-organizing matter. Under certain conditions, the two processes can influence each other but still maintain their own behavior . For instance, in the Madestein Den Haag project Kaisersrot, 2012 hundreds of houses of several different types are self-organized in the 46,000 m⊃2; site. The plot of house is represented by a polygon and the whole site is divided into plots by Voronoi-like tessellation. Thus the shape of the plot will change as soon as its location or its neighbors' locations are changed. Similar to the Arvin and House (2002) spring system, there are forces applied to the neighbors in order to dynamically maintain their local objectives such as area, proportion and adjacency. On the global level, a genetic algorithm is applied to the system in order to improve the global criteria, e.g., the grouping of different types of houses and the efficiency of the road system. The results suggest that both novel articulation and promising statistics are possible to achieve in such a hybrid system.

2. Experimental

2.1. Cellular automata

The experiment carried by the author in 2010 was to investigate how a self-organizing system could be systematically regulated by user preference (for global behavior). As mentioned above, self-organization could be compatible with the optimization process for global statistics. However, design objectives are not limited to well-defined ones. For example, user preference on forms is difficult to be formulated explicitly. To approach this problem, the experiment tries to regulate the self-organizing process via real-time interaction between the user and the computer by which un-formulated goals can be achieved. Particularly, cellular automaton is employed as a self-organizing system to model a city district.

The concept of cellular automata (CA) was raised by the research of Ulam (on crystal growth) and Neumann (on self-replicating system). However, it did not become a widely recognized model until Gardner (1970) introduced Conveys Game of Life. The dynamical system is based on a 2-dimensional lattice. Each cell has two states: “on” and “off”. There is a set of local rules for updating the state of each cell. Obviously, it is a self-organizing system. The simple machine amazed a lot of people by its complex products, e.g., still structure, oscillators and “spaceships” (periodic movement). Some scientists employed CA as a universal tool to model complex behavior. For example, Wolfram (1984) stated that:

Natural systems from snowflakes to mollusc shells show a great diversity of complex patterns. The origins of such complexity can be investigated through mathematical models termed “cellular automata”.

Nevertheless, two points should be clarified before introducing the details of the experiment: First, CA is only one model among many others for modeling complex structures. Second, the complex patterns created by CA depend on the observer. Therefore, they are relative rather than absolute in quality. For example, the “oscillator” or “spaceships” are only certain explanations of the observer, for the system itself is totally mindless. However, this experiment is to evolve the rules of CA according to the observers preference for global patterns. Some researchers (Coates et al ., 1996  ;  Herr, 2007 ) have tried to employ CA in architecture design, while it seems that the methods to integrate local behavior and global patterns are not well developed.

2.2. Method

A CA with eight neighbors is employed, and the state of a cell in the next iteration is determined by the current states of the 3×3 grid around it. Thus, the updating rules are a function that has nine boolean inputs and one boolean output. The task is to derive a specific function which leads to a preferred global behavior. The user interface is shown in Figure 3 , Figure 4  ;  Figure 5 . The variations of CA are shown on the top. Notice that the system is a dynamical system, and the image for each CA is the resulting state after running the CA for dozens of iterations. Based on the interface, the user can select one particular CA to see an animation of the evolving process. By these images or animations, users can input preferences (give high scores to several favorite ones). Then the computer will create a new generation of CAs by reproducing, mutating and crossing the preferred ones (Figure 4  ;  Figure 5 ). The procedure is very similar to a genetic algorithm, in which the new generation always has new variations and probabilistically move toward certain direction imposed by the selection.

Figure 3. User interface for selecting and evolving CAs. Step 1: the initializations of the CAs. The red bars below the icons result from user selection.

Figure 4. Step 2: a new generation of CAs are produced by crossing over or mutating the selected CAs in step 1. The red bars below the icons result from user selection in the second round.

Figure 5. Step 3: a new generation of CAs are produced and the users can select and evolve the CAs further until satisfying ones are discovered.

2.3. Results

The results indicate that it is feasible to evolve CAs according to the user preference. On one hand, both the self-organization within each CA and the multiple variations of CAs provide novel candidates; on the other hand, users are able to guide the generations of CAs toward their own “flavor” gradually. However, the main drawbacks are that the users exploration is time consuming (dozens of generations can easily make users impatient) and good results are not always assured. The main challenge is that the artificial evolution in this program is not always continuous. In other words, the preferred CAs do not always produce desirable offspring in the succeeding generations. However, non-continuity is an essential aspect of evolution since it brings novel offsprings. As a result, there is a trade-off between novelty and continuity.

At the final stage, the selected CA is used to simulate the development of a city district (Figure 6 ). There are two aspects which are valuable for architects or planners. One is about the form which might contain interesting shapes or special topological structures; the other is about the stability of the dynamical system: Some CAs will converge to a certain pattern (toward equilibrium) even with different initial states; by contrast, some others will have very different results even with similar initial states. Thus, this approach is useful for studying the dynamics of the city if we postulate that there is a high correlation between CA and the urban mechanism.

Figure 6. Simulation of the urban development by the selected CA.

3. Further discussion

3.1. From function to performance

There have been many debates on the relationships between function and form of the architecture during the 20th century. In the domain of design computing, the relationship between the two has been seen more clearly. In a problem solving approach, all the possibilities are fixed in the beginning as a search space. The best one in the space is to be attained by a search process, which means the form (as a point in a fixed state space) follows the function (as explicitly formulated objectives). However, the new approaches based on probabilistic models (e.g., self-organization) do not follow the paradigm any more. The state space is usually not defined explicitly. Moreover, the overall performance rather than the function is essential. Performance including the structure, the form and their function (implicit and explicit) can be considered the behavior of the architecture as a whole, which is a new key to the function–form problem.

3.2. Integration of urban rules

An interesting issue is integrating specific rules of urban development so that the system can be more helpful in urban design. There are two distinct ways to take account of the specific mechanisms of urban development. First, since certain mechanisms can be encoded as rules of CA, we can impose these rules on all CAs in the evolution. As a result, the process only explores only a sub-space of the original search space. Second, if rich information of an urban environment is available, the evolvement of CAs can use this information as a 2-dimensional map. For instance, a new CA rule about how to interact with the map can be added to the standard CA rule set.

3.3. From control to regulation

In contrast to the traditional methodology of problem-solving in the filing of CAAD, the experiment with the cellular automat plus an evolutionary strategy is not to control but to regulate the form-finding process. Problem-solving usually prefers deterministic models, since high fitness of the solution rather than interesting behavior of the solution is expected during the process. Although this methodology might be plausible for building engineering, it does not help a lot in architectural design. Architecture differs from many artifacts (especially machines) by the great importance of the implicit meanings of the overall structure and form. From the perspective of the users, the function and the user interface of the machine are more essential than its internal structure and its mechanism. Therefore, the machine can be designed part by part given a framework. By contrast, the functions of architecture are difficult to be described in a formal language, while the structure and the form have the most profound impacts on the inhabitants. For architects the logic of generating the design as a whole is most essential. As a result, the goal of architectural design is difficult to be divided into sub-goals and subsequently the conventional problem-solving method (in which the sub-scores are usually summed to a single score) is untenable. To be more general, rigid control does not make much sense in design and planning. Thus we argue that regulation as “soft” control which allows complex behavior to emerge is more productive in architectural design or urban planning.

References

1. Arvin and House, 2002 Arvin, S.A.,House, D.H., 2002, Modeling architectural design objectives in physically based space planning. in: Automation in Construction, vol. 11, pp 213–225
2. Coates et al., 1996 Coates, P., Healy, N., Lamb, C.,Voon W.L., 1996. The use of cellular automata to explore bottom-up architectonic rules. Paper presented at Euro graphics UK Chapter 14th Annual Conference Imperial College, London.
3. De Wolf and Holvoet, 2005 T. De Wolf, T. Holvoet; Emergence versus self-organisation: different concepts but promising when combines; A. Sven, Serugendo Di Marzo, Hales Giovanni, David (Eds.), Engineering Self-organising Systems (Eds.), Springer, Brueckner (2005)
4. Gardner, 1970 Gardner, M., 1970, Mathematical Games—The fantastic combinations of John Conways new solitaire game “life”. Scientific American, 223 October 1970, 120–123 .
5. Herr, 2007 Herr, C.M., 2007. Adapting cellular automata to support the architectural design process. In: Automation in Construction 16 (2007) pp. 61–69 .
6. Kaisersrot, 2012 Kaisersrot, 〈http://www.kaisersrot.ch/kaisersrot-02/2003_Madestein,_Den_Haag_%28NL%29.html〉 2012 (accessed 15.03.12).
7. Parunak and Brueckner, 2004 H.D. Parunak, S.A. Brueckner; Engineering swarming systems; F. Bergenti, M.P. Gleizes, F. Zambonelli (Eds.), Methodologies and Software Engineering for Agent Systems, Kluwer (2004)
8. Wolfram, 1984 S. Wolfram; Cellular automata as models of complexity; Nature, 311 (1984), pp. 419–424