Stigmergic planning Tim Ireland Bartlett School of Graduate Studies, University College London, UK. t.ireland@ucl.ac.uk Published in Proceedings of 2010 Association for Computer Aided Design in Architecture (ACADIA) conference To cite this article: Ireland, T. (2010). “Stigmergic Planning”, in LIFE in:formation: On Responsive Information and Variations in Architecture. Aaron Sprecher, Shai Yeshayahu and Pablo Lorenzo-Eiroa (eds.). Proceedings of the 30th Annual Conference of the Association for Computer Aided Design in Architecture (ACADIA 2010), New York, USA. Pp 183-189. Abstract This paper presents an application of swarm intelligence towards the problem of spatial configuration. The methodology classifies activities as discrete entities, which selforganise topologically through associational parameters: an investigation of emergent route formation and spatial connectivity based on simple agent and pheromone interaction, coupled with the problem of ‘loose’ rectangular geometric assembly. A concept model sniffingSpace (Ireland 2009) developed in Netlogo (Willensky 1999), which established the self-organising topological capacity of the system, is extended in Processing (Fry and Rea 2009) to incorporate rectangular geometry towards the problem of planning architectural space. 1 Introduction The model presented takes precedence from Kurt Lewin’s theory of Hodological space (1959), which defines the variable conditions a person faces moving between two points. Lewin’s notion was a concept of psychological space; an analytical concept in which a subject’s behaviour is perceived a result of a dynamic subject-environment relation. This behavioural notion of space is extended computationally in a generative process, in light of work in ecological psychology (Barker 1968), cybernetics (Pask 1969) and Uexküll’s theory of Umwelt (2001), to a pragmatic notion of the practical configuration of space: coined here as concrete space, in reference to O.F. Bollnow’s spatial theory (Shuttleworth & Kohlmaier forthcoming). Architectural space is the manifestation of the built form, and as such, concrete space is a particular aspect of architectural space--being the space of activity created in dialogue between the subject and its environment. The work looks to swarm intelligence (SI) and established computational methods based on the behaviour of social insects and animals, to approach the configuration of Stigmergic planning 1 architectural space from a position of distributed representation. The intent is to broach spatial thinking and the imitation of standard spatial templates in the process of configuring architectural space. Thus spatial configuration is perceived in terms of the functional space of an organism (Uexküll 2001; Sharov 2001); the perspective of the independent organism-environment relation is translated computationally, not only as an approach to problem solving but in a manner in which the model is the theory. The paper will first elucidate the author’s spatial thinking and approach to spatial configuration to position the application of SI: a position stemming from work at CECA (Miranda and Coates 2000; Coates 2004). The model sniffingSpace (Ireland 2009) will then be outlined to explain the method. The model presented extends sniffingSpace to incorporate rectangular geometry towards generating architectural diagrams of spatial configuration. The model draws on the problem of architectural space planning, in terms of purpose, and as such alludes to the field of automatic plan generation. The model sits within such a body of work in terms of an alternative method and approach but is not a tool for spatial planning per se. It is a conceptual approach to sketching spatial configuration--a playful tool to amplify the creative intuition of the designer. In these terms, optimisation, an issue briefly addressed in reflection with comparative models and performance oriented design, is a significant issue. 2 Questioning: Space in architecture Proposing a user oriented ecological approach in architectural design, in which a building’s ‘umwelt’ is conceived, Lawson (2001) commented that architects’ “tend to consider space as an abstract concept and not a behavioural phenomenon, and yet paradoxically assume that behaviour will follow their predictions.” Such an observation critiques a deterministic attitude and objectified approach to design, as opposed to a cybernetic, systems approach in which dynamical relations between the space and occupant are allowed to unfold patterns. This is a notion of architecture as the manifestation of a ‘complex of places’: the organisation of a framework for activities and the interrelation of settings for performing activities (Norberg-Schultz 1971). This is a complex problem perceived here as the defining or manipulating of relations between parts, and parts of parts in servitude to combinatorial, topological, associative, and communicative properties. The work is concentrated at the diagrammatic-cogitatingunravelling stage in the design process, namely the point at which an architect deliberates a brief’s spatial parameters and determines the organisation of the building--tying architectural space to the user, relative to behaviour, function and context. Le Corbusier’s (1929) well known adage, “Man walks in a straight line because he knows where he is going,” explicates the determined nature of a methodology forming the modern man-made environment: an optimisation perceiving the path of a person’s movement as a mathematical rule that the shortest distance is the straight line. This is not a representation of a subject within an environment. The approach here is prompted by systems occurring in nature, a ‘dirty sketch’ view perceived as good enough: See 4.1. Stigmergic planning 2 Opposed to the geometrical line which connects two points as an abstract representation of a person’s journey, the German social psychologist Kurt Lewin studied the problem of movement and how in reality paths do not follow the mathematical rule, that the shortest distance is the straight line: as demonstrated by the Peploid model (Helbing 2001). 3 Spatial thinking. The author’s focus is of a subject embedded in its environment going about its business, and this activity perceived as spatial patterning: a dynamic unfolding process, which is self-organising, defined through performance. This notion, stemming from the thinking of Simmel (1997), Lefebvre (1992), Hillier (1998), Perec (1999), and de Certeau (1988), considers every-day, social activity as spatial patterning, a dynamic relationship between people and the environment: a concept of concrete space as social geometry. 3.1 Spatial configuration as a complex adaptive system Hillier’s elucidation of the relationship between user and context (1998), Lefebvre’s critique (1992), and the concept of a building as a spatial system (Hillier and Hanson 1984) signify the problem of spatial configuration as complex. A distinctive property of concrete space is low-dimensionality. Spatial relations constrain one another and consequentially spatial organisation exhibits patterning: making space productive. Reaction-diffusion, self-organisation, swarming and flocking, stigmergy, habits, etc., are all enabled by spatiality (Bullock 2009). AL and AI research has successfully transposed the above into mathematical models and the computer’s capacity to emulate such dynamic systems provides the potential to generate and unfold architectural patterns of spatial configuration (Coates 2010). 4 Applying swarm intelligence to the problem of spatial configuration Research into the behavioural and cognitive mechanisms underlying numerous collective phenomena observed in animal groups and societies offer interesting principles and methods which may be applied architecturally (Theraulaz 2009). “Swarm intelligence offers an alternative way of designing ‘intelligent’ systems, in which autonomy, emergence, and distributed functioning replace control, pre-programming, and centralisation” (Bonabeau et al. 1999). The emphasis is on these principles being applied architecturally from a perspective of the user rather than towards the manifestation of form and not used on the premise of simulating human behaviour. It has been demonstrated that spatial organisation is an important aspect in the life of social insect colonies. Their stigmergic nature defines an intimate relation between insect, colony, and the environment: for example building of the nest, brood-sorting, corpse-aggregation and food foraging (Theraulaz et al. 2003). Lefebvre (1995) noted that space affects people and people affect space. Similarly, Hillier (1998) proposed that space affects behaviour and behaviour affects space. These are basically notions of a feedback relationship between space (the environment) and people, a relationship which is stigmergic, providing an alternative process of spatial configuration. Stigmergic planning 3 4.1 In search of the ‘good enough’: a dirty sketch. Models of social insect behaviour have been well documented and been applied to the design and modelling of complex systems (Bonabeau et al. 1999). These are generally towards optimisation problems, such as routing in communication networks and tend to rely on or have some form of a-priori knowledge planned into the behaviour of the system to promote optimisation: i.e., a global governing routine ‘helps’ guide an agent on its return journey, and control the evaporation and depositing of pheromones in the well known ACO heuristic (Dorigo and Stutzle 2004). In Reznick's (1994) ‘Ant’ model the nest emits an alternative pheromone defining a ‘compass’ by which to guide the agents back to the nest. Such methodologies provide a generally predictable outcome and thereby serve to illustrate what may be achieved manually; deemed tautological within the terms of this work (Ireland 2008a). See figure 1. Image1. Top: nests emitting pheromone direct agents back home: defining an orthogonal representation of connectivity. Above: Two trail method; the later sequence illustrates the connectivity between colonies changing through different connotations of full connectivity. Optimisation is not the purpose of the model presented here, indeed the behaviour of the emergent trail system impedes the formation of a unified solution. The system displays a state of self-organised criticality (Jensen 1998) whereby formed trails endure a lifespan: the formation of trails is constantly refreshed, thereby forcing agents to reinstate new Stigmergic planning 4 routes. This behaviour is due to a threshold of the reinforcement of trails through the behaviour of agents and their interaction with the environment. This results in a break in reinforcement, coupled with agent behaviour, the diffusion and evaporation of pheromone prevents trails forming and converging to an optimised route between destination points; instead, trails emerge, converge, fluctuate, and expire. (See figure 2.) Thus, if optimisation is defined as the search for the best element from some set of available alternatives or as performance improvement, then this model does not facilitate optimisation. Secondly the method is based on Lewin’s notion of Hodological space, defining a locus of action whose scope is defined by the field of force generated as the subject reacts with its environment--a variable state conditioned by the affect of a dynamic environment. The author is not adverse to optimisation; it is a necessary ‘engineering’. The point being made is the distinction between comparative models and the epistemological approach. Image 2. Series showing the formation and cessation of trails, between fixed nests. 4.2 The ant foraging analogy A second clarification concerns the application of SI and relation to precedent models. The method employs ant colonies in terms of an abstract representation of food foraging behaviour and should not be confused with Dorigo’s ACO algorithm, which is focused primarily on the search for an optimal path. The method is based on the work of Panait Stigmergic planning 5 and Luke (2004); a response to the complicated nest discovery devices employed by algorithms such as ACO. The method relies on two pheromones: one applied when searching, the other when returning to the nest. The principle being a simple mechanism with no hard-coding, used as a method of distributed representation. 5 Using artificial ant colonies to generate diagrams of architectural space. In essence, the model is very simple, taking Mitchel Resnick’s model ‘Ant’ (1994) and revising the return-to-nest mechanism of the ant following the trail emitted by the nest to a second trail laid by the ants: See 4.2 above. The nest-ant-food relationship is revised here to nest/food-ant. One colony’s nest is another colony’s food, and vice versa; therefore, the eventual pheromone trail which emerges amongst the colonies becomes a communication network through which the antagents traverse between associated colonies. A colony’s nest represents an activity, thereby a specific space or area requirement in terms of an architectural brief. This method is the basic mechanism of the model, described briefly below in 5.1. The nests are represented geometrically as a rectangle. The rectangular form was employed due to the flexibility of packing that rectangular geometry allows: See Steadman (2006) for a thorough explanation. 5.1 Interpreting the spatial template The notion of concrete space as outlined effects the reconsideration of standard spatial templates typically assumed in architectural practice, on the premise that users are generally obligated to conform to an imposed spatial pattern or to remodel accordingly. Here activities are defined according to associational parameters: these may be defined relative to a specific behavioural pattern in order to investigate the emergent spatial configurations and explore the resulting unconstrained spatial patterning. To date the model has not been tested to this degree; it is presented here in terms of the system, its reasoning, mechanics and behaviour. Deconstructing typical spatial templates identifies an array of activities, which will inherently own some measure of association with each other, may be asymmetric, have associations to activities typically located in other areas or have varied and ambiguous associations, relative to the particular behaviour pattern explored. The premise is that the dynamic association of these associational parameters may develop spatial topographies previously obstructed by the traditional hierarchical definition of rooms in typical plan arrangement: a spatial template. Spatial configuration is not an exacting or finite production. As such, the task here is to determine the loose arrangement of spaces, bringing them together in an agglomerated whole. The approach takes precedent from the LOOS program (Flemming 1986) which focused on ‘loosely packed’ arrangements, in which rectangles describing crucial spatial relations between the primary elements were allocated, and remaining gaps or holes used Stigmergic planning 6 to allocate auxiliary spaces or added to previously allocated spaces once the shape of the circulation area was determined. 5.2 Sniffing Space The model presented is a development of a model coined sniffingSpace, described in detail elsewhere (Ireland 2008b, 2009). In short the model consists of an array of ant colonies. A colony is composed of two types of agents: an ant-agent and a nest-agent. An ant-agent forms an army; a single ant-agent is termed a soldier. Soldiers leave the nest in search of associated nest sites (food) and return home upon discovering an associate, eliminating the find from their associate list. This process is repeated until a soldier has discovered all its associates; then it dies. Trails emerge between associated nest sites generating a communication network between colonies. Diffusion and evaporation affect the trails. The nest represents an activity--a space. Nests check visiting soldiers to determine their association. If associated, the nest will follow a returning soldier; the nest’s movement is gradual, ensuring that its advance is not affected by a single soldier. The network therefore generates a gravitational force between associated colonies. The nests representing different activities therefore use these trails as a routing, along which they traverse to come together with their associates. (See figure 3.) Nests reproduce soldiers until they are in the company of all their associates. Image 3: sequence illustrating nests traversing trails towards agglomeration. 5.3 The G&T algorithm1 The nests rectangular geometry is created with a random x and y dimension, satisfying their specific area condition. As nests are drawn together, their boundary conditions conflict. A nest therefore has three behavioural traits to accommodate geometrical assembly relative to its relation with its neighbours: adapt boundary conditions, move away or overlap. 1) Adapt boundary conditions: A nests x and y dimensions are variable, so it will alter its configuration in order to nestle. 1 A playful term by the author to distinguish the rules extending the sniffingSpace model, to incorporate rectangular geometry. Stigmergic planning 7 2) Move away: Various activities have common or specific adversaries’: i.e., social/private or noisy/quiet activities. A nest whose boundary is overlapping with an adversary will move away. Note, it can settle next to, but not overlie. 3) Overlap: associated nests must overlie to settle. Nests with no association are not restricted from coinciding. Image 4: Nest relations between 5 colonies. Blue line signifies connection between associates, red line between adversaries. Two versions of the model were produced taking into consideration the soldier-nest encounter condition: a nucleus version, where a soldier must locate the central area of the nest and a boundary version where the soldier must just cross the boundary before detecting a find and returning home. These were tested with five colonies, with varied associations. (See figure 4). The behaviour of the two systems differs. The nucleus version has a tendency to result in an agglomerated whole. In operation, it generally takes longer to form conspicuous paths and for the system to ‘get going’. Once a connectivity network has formed and the nests start to gravitate, they appear to move around more, changing position a number of times in the process rather than getting straight into position. The nests appear to fight and tussle jostling for position and every so often one appears to give up, trying an alternative course. Stigmergic planning 8 Image 5: Results of nucleus version. The results of the boundary version appear less resolute; one time forming separate groups of associated activities, another time a single cluster. The agglomerations are generally more simplistic, rather than a lot of multi-overlaps as in the nucleus version, the nests tends to get into position much quicker, their course changing less in the process. Image 5: Results of boundary version. 6 Conclusions The model incorporates two systems of agents working in parallel. These agents form a colony of which there is an array. A colony has associational parameters reflecting the spatial parameters contained in an architectural brief. Information is transmitted throughout the system via a communication network which emerges as a result of local interaction between soldiers and pheromone and the associational parameters between colonies. A gravitational pull between associated colonies causes the nest sites to selfassemble their spatial configuration. The use of agents in a process of distributed representation generates a diagram in which the geometry of the system is an emergent property of the model, resulting in a spatial structure that emerges as a consequence of the behaviour of the system. The approach to the formation of concrete space outlined is the design or description of Stigmergic planning 9 relations: between parts, and parts of parts in servitude to combinatorial, topological, associative, and communicative properties, congruent to utilitarian practices, their spatial parameters (association, adjacency, permeability, integration, and categories), environment and context. To date, the model does not incorporate all of these aspects. The model presented is a reflection of an ontological theory of space: an interpretation of a particular aspect of space based upon an interdisciplinary review of spatial thinking. Interaction with the model resonates the process of sketching spatial diagrams. Manually, this is a process in which many options will be outlined in a process of roughly working through varied arrangements of spatial configuration. A process that evolves relative to the designer’s intuition, developing a solution, worked up in a process of trial and error. The model outlined does not suffice as an alternative, but it does offer an approach which potentially could result in diagrams that suggest alternative options to the typical spatial template. In deconstructing the spatial template, focusing on what people actually do, and drawing on a designer’s intuition, creativity may be amplified: in that, with further development, the affordances between the resulting configurations may be scrutinized. Acknowledgements This research is carried out under the supervision and guidance of Professor Philip Steadman at the Bartlett School of Graduate Studies, University College London and Paul Coates head of the Centre for Evolutionary Computation in Architecture (CECA) at University of East London. Thanks also to Mr Emmanouil Zaroukas for his stimulating dialogue and feedback and to Dr. Seth Bullock, Head of Group in Science and Engineering of Natural Systems Group at the University of Southampton for his comments on another paper which have been incorporated here. This research is funded by the Engineering and Physical Sciences Research Council (EPSRC), UK. References Barker, R. G. (1968). Ecological Psychology: Concepts and methods for studying the environment of behaviour. Stanford, California: Stanford University Press. Bonabeau, E., M. Dorigo, and G. Theraulaz. (1999). Swarm Intelligence. From natural to artificial systems. New York: Oxford University Press. Bollnow, O. F. (1963). Mensch und Raum (Man and space). In Human space. Trans. C. Shuttleworth. ed. J. Kohlmaier. London: Hyphen Press. Forthcoming. Bullock, S., and C. Buckley. (2009). Embracing the tyranny of distance: Space as an enabling constraint. In Technoetic Arts, 7 (2). pp. 141-152. Coates, P. (2004). Review paper: some experiments using agent modelling at CECA. In Proceedings of the 7th Generative art conference. Milan: GA2004. Stigmergic planning 10 Coates, P. (2010). Programming.Architecture. Routledge. De Certeau, M. (1988). The practice of everyday life. Trans S. Rendall. University of California Press. Dorigo, M., and T. Stutzle. (2004). Ant colony optimization. A Bradford book, The MIT Press. Flemming, U. (1986). On the representation and generation of loosely packed arrangements of rectangles. In Environment and Planning B: Planning and design. Volume 13, Pages 189-205. Fry, B., and R. Casey. (2009). Processing: v1.04, http://processing.org/. Cambridge, MA: MIT Media Lab. Helbing D., P. Molnar, I. J. Farkas, and K. Bolay. (2001). Self-organising pedestrian movement. In Environment and Planning B: Planning and design, Vol 28, pages 361 – 383. Hillier, B., and J. Hanson. (1984). The social logic of space. Cambridge: Cambridge University Press. Hillier, B. (1998). Space is the machine. Cambridge: Cambridge University Press. Jensen H. J. (1998). Self-Organized Criticality: Emergent Complex Behaviour. In Physical and Biological Systems. Cambridge: Cambridge University Press. Ireland, T. (2008a). Space Diagrams: The problem of spatial arrangement and the automatic generation of architectural plans. In Proceedings of the 26th eCAADe Conference on Education and Research in Computer Aiderd Architecturel Design in Europe. September 17-19, 2008. Antwerpen, Belgium. Ireland, T. (2008b). Sniffing Space. In Proceedings of the 11th Generative art conference. Milan: GA2008. Ireland, T. (2009). Emergent space diagrams. In Proceedings of the 13th International CAAD Futures Conference. Montréal: 2009. Lawson, B. (2001). The language of space. Oxford: Architectural Press. Le Corbusier. (1929). The city of tomorrow. London: The architectural press. Lefebvre, H. (1995). The production of space. Trans. D. Nicholson-Smith. Oxford: Blackwell Publishers Ltd. Lewin, K. (1959). Field theory in social science. London: Tavistock Publications Ltd. Miranda, P., and P. Coates. (2000). Swarm modelling: The use of swarm intelligence to generate architectural form. In Proceedings of the 3rd Generative art conference, Milan: GA2000. Norberg-Schulz, C. (1971). Existence, space and architecture. London: Studio Vista. Stigmergic planning 11 Panait, L., and S. Luke. (2004). Ant foraging revisted. In Proceedings of the Ninth International Conference on the simulation and synthesis of living systems. (ALIFE9). Pp569. Pask, G. (1969). The architectural relevance of cybernetics. In Architectural Design. September. Pages 494 to 496. Perec, G. (1999). Species of spaces in Species of spaces and other pieces. Ed. J. Sturrock. London: Penguin books,. Resnick, M. (1994). Turtles, Termites and Traffic Jams: Explorations in Massively Parallel Microworlds. Cambridge, MA: MIT Press. Sharov, A. (2001). Umwelt-theory and pragmatism. In Semiotica. Issue 134, July. Pages 211-228. Simmel, G. (1997). The sociology of space. In Simmel on culture, eds. D. Frisby, and M. Featherstone. London: Sage Publications Ltd. Steadman, P. (2006). Why are most buildings rectangular? In Arq magazine, Volume 10, No.2. Pages 119 to 130. Theraulaz, G., J. Gautrais, S. Camazine, and J. Deneubourg. (2003). The formation of spatial patterns in social insects: from simple behaviours to complex structures. Phil. Trans. R. Soc. Lond. A 15 June 2003 vol. 361 no. 1807 1263-1282 Theraulaz, G., R. Solé, and P. Kuntz. (2009). From insect nest to human architecture: Workshop on engineering principles of innovation in swarm-made architectures. September 23rd-25th. Venice, Italy. von Uexküll, J. (2001). The new concept of Umwelt: a link between science and the humanities. In Semiotica. Issue 134, July. Pages 111-123. Willensky, U. (1999). Netlogo, http://ccl.northwestern.edu/netlogo. Evanston, IL: Center for Connected Learning and Computer-Based Modeling, Northwestern University. Stigmergic planning 12