Adapting principles of developmental biology and agent-based modelling for automated urban residential layout design

Abstract

The objective is to automate the design of residential layouts as an aid for planners dealing with complex situations. The algorithm COmputational Urban Layout Design, applied to sites with various shapes, is guided by the goal of many mutually accessible residences and can be set to generate orthogonal or irregular road layouts. Using biological principles of genomic equivalence, conditional differentiation and induction, it grows from an embryonic ‘adaptive cell’ into a plan. Cells are ‘genetically identical’ with full development potential and can simultaneously lay roads and residential lots, using the gene set to change cell expression and adapt to local contexts. Cells can be seen as self-propagating agents that sort out their dependencies through local interactions.

When COmputational Urban Layout Design is set to grow a non-orthogonal layout, the plan has winding roads and irregular residential lots. Such a plan achieves the objective of relatively high residential density and accessibility, leading to walkable and coherent communities.

Keywords

Agent-based modelling automated subdivision bio-inspired algorithm generative design urban residential layout design

Introduction

Current residential layout design is based on ideas and manual processes that are already well supported by computer applications. This study seeks to establish that automated planning can go further, not only by satisfying quantified objectives but also by exploring multiple goals, constraints and site configurations. It should be able to cope with specifications extending beyond the residential lots and roads, considered in this study, to associated infrastructure.

The purpose is to develop a flexible algorithm for planning a residential layout to fill a regular or irregular suburban space. Within the spatial constraints, implementation is guided by the goals of increasing the number of residential blocks and improving accessibility between residences. However these goals are often in conflict, so that a single compromise objective function is needed (Section ‘An objective function to reflect community needs’).

The aim in developing an autonomous method of urban design has not been to replace existing methods but to generate novel plans that meet density and accessibility requirements. An automated system capable of innovating can help planners and designers deal with complex interplays between numerous elements and explore options to overcome ‘potential limitations of “conventional wisdom” and “design ﬁxation”’ (Bentley, 1999: 42).

Network modelling

Models to analyse the growth and use of networks were reviewed by Xie and Levinson (2009) who noted the development of simulations to study the historical evolution of various complex networks. Koenig and Bauriedel (2009) paid particular attention to the control parameters in simulating with cellular automata but saw their paper as a contribution ‘to the search for a general generative explanation of the evolution of certain regional and urban settlement structures’. They noted the introduction of randomness in such simulations but were wary of it, mentioning Batty’s (2005) view of random variables as equivalent to suddenly appearing innovations.

Strano et al. (2012) took the search for generative explanation further with their precise mathematical representation of processes governing the evolution of a road network. In modelling Milan for 200 years they showed the significance of (i) increasing road density around existing centres and (ii) roads triggering the expansion of the urbanisation front. They characterised the features observed in Milan as ‘morphogenetic behaviour that they appear to share with many living organisms and other natural systems’.

Subsequently Marshall and Sutton (2014) took the important step of applying simulation to create new network layouts. In particular, they used random selection of the next location to generate each additional road. Under varying street layout rules, their procedure results in a novel mixture of regular and irregular (but orthogonal) grids to fill a specified space.

Zhao et al. (2016) focus on population’s role in stimulating the growth of the road system. A new network is generated by solving a series of location problems. The authors show the importance of measures of betweenness centrality, circuitness and treeness.

Biological analogy and creativity

This paper employs biological analogy in modelling but not in the sense of Tero et al. (2010) who use a growing slime mould to simulate part of the Tokyo transport network. The analogies here are primarily at the cellular level, without drawing on the behaviour of any living organism.

Evolutionary algorithms, especially genetic algorithms, have had great success in mimicking nature’s ability to adapt (e.g. Cao et al., 2011; Fogel, 1998; Porta et al., 2013; Tuhus-Dubrow and Krarti, 2010; Yang, 2014). The irony is that optimising algorithms are designed to converge to the fittest solutions while natural processes not only produce better solutions but also diversity and novelty. One purpose of this study is to show that an automated land use design system can be ‘creative’ by imitating and exploiting nature’s ability to generate divergent outcomes.

An indication that an algorithm is ‘creative’, with novel design solutions, is whether it changes the configuration of the search space – the number of variables and their relationships (Bentley and Corne, 2002; Gero, 1995). Modifying the search space opens possibilities that have not been specified, leading to novel results that go beyond the recombination of parameters. The algorithm is able to produce original solutions that have not been predetermined. Otherwise the space traversed by the search algorithm may be prescribed and defined, with a constant number of variables and relationships between them. This limits the candidate solutions that can be reached. Variables and relationships may be switched on and off but the search is still in a predefined space, with the structures of the solutions limited by human prescription.

Features of our proposed model

The specific goal of our research is to develop a vector-based (as opposed to raster-based) application COULD (COmputational Urban Layout Design) which can automatically create original road and land-use plans for residential sites within geometrical and topological constraints. It decides how a site is divided into residential lots and roads to achieve good spatial structure. Although it can improve existing designs, COULD is mainly intended to be a system that can generate ‘entirely new designs starting from little or nothing …, and be guided purely by functional performance criteria’ (Bentley, 1999: 39). Hard coding of human knowledge has been avoided as much as possible and the focus has been on identifying a short list or set of inputs that can generate original designs. The end product is flexible enough to deal with most problems, rather than needing a specific solution for each situation. It can design for a regular or irregular site, with or without existing obstacles such as lakes or nature reserves.

Some preliminary results were presented in Sun et al. (2014) which also discussed the formulation of the objective function. This paper deals with model design, challenges in layout planning and essential technicalities. At every step, COULD has a spatial planning representation. Key aspects are:

Whereas many models lay down residential lots before roads or roads before residential lots, COULD deals with them at the same time (Section ‘Resolution of the land-first or road-first problem’).

COULD is a stochastic searching algorithm inspired by how organisms (especially plants) develop. Rather than generating complete plans from the start, as many algorithms do, we begin with the simplest feasible solution – the ‘seed’, which is an adaptive cell comprising a road segment and potential dwellings (Section ‘Formulation of the adaptive cell and its biological inspiration’). Changes to the seed cell are made in stepwise fashion, which means that the search for a layout with many accessible dwellings is kept close to the last layout at each step. Complexity and structure emerge from the process of seeking ‘the arrival of the fittest’ (a term borrowed from Wagner, 2014) where ‘fitness’ here means achieving the objective (Section ‘An objective function to reflect community needs’, equation (1)). Section ‘Formulation of the adaptive cell and its biological inspiration’ discusses the core technical component of COULD – the adaptive cell (or universal module), with brief introductions of the biological processes that inspired its composition and mechanisms.

The macroscopic structure of the design emerging from bottom-up through local interactions among agents – the adaptive cells – makes COULD creative. Many comparable applications use procedure-based top-down approaches (Section ‘Comparison with top-down planning’). Generative methods are commonly used, e.g. rewriting systems such as L-systems and shape grammars (Mitchell, 1990; Prusinkiewicz et al., 1990).

COULD is a generalised model focusing on the algorithmic aspect of automated design. It does not take account of many planning and engineering regulations, standards and procedures which would require added goals, constraints and operators.

Subsequent sections deal with: An objective function to reflect community needs, Resolution of the land-first or road-first problem (Footprint formation, plot subdivision, route propagation and the branching tree, challenges with two step processes and the resolution), Formulation of the adaptive cell and its biological inspiration, The structure of the adaptive cell, Cell propagation during development, Genotype to phenotype mapping, Genomic equivalence and conditional differentiation, Induction (Lateral inhibition, environmental inhibition, remote induction), Application of the algorithm, Results and discussion of the bottom-up method, the amenity of plans generated, comparison with top-down planning and potential extensions.

Generation of an urban layout

An objective function to reflect community needs

The first goal is to maximise land lots to meet population needs and generate revenue. Roads laid out in a tree structure provide the best topology to minimise road costs and maximise the usable land area. Not all tree layouts are efficient but the design with the maximum number of lots will inevitably have a tree topology, often containing cul-de-sacs which require less roads (Southworth and Ben-Joseph, 2003). These may be liked by some residents (Koohsari et al., 2015) but fewer roads make land parcels less accessible and cul-de-sacs are often criticised for increasing travel distances (Frank et al., 2006; Randall and Baetz, 2001). Thus maximising dwelling lots is not the only goal.

The second goal is to maximise accessibility, measured as straightness centrality (Crucitti et al., 2006). Streets shaped by traffic engineers generally favour automobiles over other users, so that accessibility of pedestrians and cyclists has been sacrificed (Southworth and Ben-Joseph, 2003); this is reflected in urban forms. In many cases, the lack of integration between transport and land use has created ‘the vicious cycle of [urban] sprawl and car dependence feeding one another’ (Cervero and Sullivan, 2011: 210). The objective function is formulated so that COULD automatically generates spatial structure that promotes active transport, such as walking and cycling, to reduce car dependency. It does so by reducing distances between points of the network since pedestrians and cyclists are sensitive to distance (Atash, 1994; Aultman-Hall et al., 1997; Hottenstein et al., 1997; Randall and Baetz, 2001).

The balance between number of residential blocks and accessibility between residences is achieved in the objective function (equation (1)) that guides the stochastic search in COULD. It is used directly to calculate fitness scores without further transformation.

ξ (N) = C_{avg} (N) * H = \frac{\sum_{i < j \in N} \frac{d_{ij}^{Eucl}}{d_{ij}}}{N \frac{(N - 1)}{2}} * H

(1)

where,

The number of houses in the solution;

C_avg

The average straightness centrality of the solution (Vragović et al., 2005). For each pair of residential lots, the straightness centrality is the ratio of $d_{ij}^{Eucl}$ to $d_{ij}$ ;

d_{ij}^{Eucl}

Euclidean (straight line) distance between land lots i and j;

d_{ij}

The shortest network distance between land lots i and j (Figure 7);

The number of countable lots. N and H do not cancel each other because N excludes pairs of lots from the same cul-de-sac. Such pairs would score close to 1 in centrality; their exclusion imposes a downward bias on the centrality value C_avg, but limits the growth of cul-de-sacs.

In equation (1), high average straightness centrality of the lots indicates good connectivity, which has been shown to promote walking within the neighbourhood (Hajrasouliha and Yin, 2015; Hooper et al., 2015). However, higher centrality requires more roads which decrease the space available for lots.

Layout design optimizing problems are generally NP-Hard, which means they do not have known efficient solutions (Drira et al., 2007). The topological complexity of the road network and dependency between its elements and residential lots pose modelling difficulties. Changes can have ripple effects on other parts of the network; for example, deletion of a road section might leave roads or lots disconnected. The interplay between residential lots and roads raises the question of which should be treated first.

Resolution of the land-first or road-first problem

Marshall (2009) discusses three possible paradigms for generating urban layout patterns, footprint formation, plot subdivision, route propagation. In footprint formation, buildings are placed in succession and the area left between forms streets and open space. Plot subdivision is the repetitive partitioning of plots into smaller land parcels: roads could follow some of the subdivision boundaries. In route propagation, roads propagate into space and define the spatial structure.

Footprint formation

Footprint formation is naturally implemented in raster based applications. Hillier and Hanson (1984) use an abstract footprint formation model to simulate the organic growth of urban space. It is essentially built on grid cells but achieving realistic shapes for both land and roads is challenging for raster based applications (Wickramasuriya et al., 2011), partly because grouping cells into reasonably shaped land lots and interconnected roads is complex. In contrast, shape control is easier and probably more computationally efficient in vector-based applications because of their parametric nature.

Plot subdivision

The slicing structure (Tam, 1992; Wu and Appleton, 2002), which prescribes how to partition a space, is a classic example of plot subdivision. Most existing vector based land subdivision programs belong in this group (e.g. Dahal and Chow, 2014; Vanegas et al., 2009; Wickramasuriya et al., 2011) although they do not use the term slicing structure. Compared to the grid cell approach, it is easier to control shapes with a slicing structure. When applied to an urban layout the cuts could be turned into a road network (Vanegas et al., 2009). However Dahal and Chow (2014) had difficulty in getting a slicing structure to produce sinuous roads and multiple cul-de-sacs.

Route propagation and the branching tree

Examples of route propagation are L-systems which can evolve an acyclic street layout through rewriting grammars (Hemberg et al., 2008; Prusinkiewicz et al., 1990). Parish and Müller (2001) developed modifications so that they could use L-systems to model loops in the street network. A branching tree method (essentially a form of route propagation) was initially developed for this study but was not adopted for the reasons stated in the next section.

Challenges with two step processes and the resolution

Marshall’s paradigms indicate an important design decision, whether streets or land should be treated first. Footprint formation and plot subdivision consider land use before the street network, while route propagation does the reverse. Adopting any of these paradigms means land use and road network design are done in two separate steps, but the interdependencies between them pose challenges. In land-first approaches, if parts of the subdivision boundaries are expanded into roads in the second stage then the blocks alongside will have significant easement and possibly become unusable. One solution is to merge unusable lots with neighbouring lots (Dahal and Chow, 2014) but it means the second stage will change the results of the first stage. The road-first approach creates difficulties in dividing the areas between streets into usable blocks in the second stage. COULD circumvents the land-first or road-first dilemma by laying down road sections and land parcels simultaneously within its self-contained building blocks – the adaptive cells. For these reasons, we did not use branching for route propagation.

Formulation of the adaptive cell and its biological inspiration

The adaptive cells of our software enable layout generation in one step. They comprise geometric components, roads and centroids that may generate lots or roads (Section ‘The structure of the adaptive cell’), and the genotype consisting of a set of rules determining how cells interact (Section ‘Genotype to phenotype mapping’). The one type of adaptive cell adapts to any situation in the urban structure, like stem cells with a fixed genome differentiating to fit their surroundings (Slack, 2013). Adaptive cells can self-reproduce so that the structure grows like a plant (Section ‘Cell propagation during development’), although roads and dwellings that do not improve accessibility can be pruned. The genotype comprises rules (Section ‘Induction’) realised and maintained by genes (or operators, Section ‘Application of the developmental algorithm, COULD’) that determine how cells interact. The following sections indicate how developmental biology inspired mechanisms of the model.

COULD was developed using the Aimsun software package (www.aimsun.com) designed for traffic simulation but used here to construct road networks and calculate shortest paths. Our code was written in C++ through Aimsun’s software development kit (SDK).

The structure of the adaptive cell

The adaptive cell carries the potential to grow new roads and residential lots that are implemented as and when needed, giving the whole structure flexibility to fit the topography and any reservations or obstructions. It parallels the adaptability of cells in developing organisms which has been explored by a number of writers, including Carroll (2011), Desvoyes et al. (2014), Fehér (2015) and Karr et al. (2012). All cells have the same development potential but the spatial expression is determined by local context (neighbouring cells, natural obstacles and site boundaries) and will continue to change as the structure develops.

Figure 1 shows the structure of the adaptive cell, comprising a pair of road sections serving opposite directions, and 10 buds connected to them. Each bud has three potential states: land lot, road section or void. In Figure 1(a), they are all expressed as residential lots, each represented by a centroid that can send and receive traffic. Centroids are joined to the road by connectors shown as thin lines. Because the adaptive cell contains both the land and road components, the requirements of both can be accommodated together. All the land lots are attached to the road in the one cell and new roads have to grow out of the existing buds to ensure connectedness. The configuration of the adaptive cell imposes some constraints. The buds are set to grow at angles with 45° increments, i.e. 0°, 45°, 90°, 135°, 180°, 225°, 270°, 315°. Smaller or even non-fixed angles could be used.

Figure 1.

(a) A cell with all buds being land lots. (b) Road extension.

Figure 1(a) is an isolated cell so all buds are expressed as residential lots. However, in order to connect to other cells, at least one bud needs to become a road section and some other buds may have to be sacrificed to clear the space, as shown in Figure 1(b).

The feasibility of model growth is guaranteed by the geometry. For residential lots, dimensions are more important than shapes. A lot is usable as long as there is minimum separation from neighbouring elements. Lot boundaries are inserted after determining the locations of roads and land lots. Figure 2 shows one way of doing it, which produces a basic Voronoi Diagram (Okabe et al., 2009). Figure 2(a) shows the separation distance between two centroids as the virtual line AB between them. Then the orthogonal boundary line CD is drawn from its midpoint. One boundary line ends when it crosses another, as in Figure 2(b). There are also alternative rules such as connecting the midpoint between centroids or drawing block boundaries perpendicular to the adjoining road. They generate different block shapes but are often equally applicable. Multiple ways of interpreting the same centroid layout give human designers the flexibility to express their preferences.

Figure 2.

Insertion of block boundaries as a basic Voronoi diagram.

Because COULD works on spacing rather than lot shapes, it tends to produce irregular land lots (Section ‘Results and discussion’). It can be forced to produce more regular shapes by making buds 2, 4, 7, 9 void so that growth will be orthogonal (Figure 3).

Figure 3.

Cell propagation starting from a seed (orthogonal growth with buds 2, 4, 7, 9 disabled).

Cell propagation during development

COULD deals with challenges in stepwise fashion akin to natural development. The genotype does not need to be a rigid blueprint prescribing every component, which is difficult for systems with many variables. Just as nature does not start with complete solutions but grows them from embryos, COULD starts from one or more seed cells that gradually grow into a mature solution (Figure 3). Dependencies between elements are sorted out progressively during development.

Genotype to phenotype mapping

The distinction between phenotype and genotype and the generative nature of the genotype is an important feature of the adaptive cell. Phenotype is the physical solution and genotype is its coded counterpart, or the genetic package in biological terms (Bentley, 1999; Cooper and Hausman, 2013). In biology, genotype interacts with the environment to produce a phenotype to suit the context (Klug et al., 2013). Some computer algorithms do not separate the two and those that do often use one-to-one mapping (Bentley, 1999), meaning that a genotype acts like a blueprint describing every variable and dependency in the phenotype. This makes sizes of genotype and phenotype correlated, in terms of number of variables.

One-to-one mapping does not exist in natural organisms (Bentley and Kumar, 1999) and the mechanisms behind complex life are much simpler than might be expected (Carroll, 2011). The fact that the human genome does not contain many more genes than that of a simple plant (Arabidopsis) and only about double that of the roundworm (Centre for Genetics Education, 2013) suggests that natural genotypes are scale-free, which enables a small number of common elements to create immense diversity through ‘the power of combinatorial logic in biology’ (Carroll, 2011: 120). Following the same path, COULD decouples the sizes of the genotype and phenotype in order to create much from little. Instead of a step-by-step manual as in the slicing structure (Section ‘Plot subdivision’), the genotype contains rules for local interaction (Section ‘Induction’) through which the outcome is produced.

The procedure of growing the layout is path dependent and guided by a single genotype. At every step the plan is modified on the basis of the new possibilities revealed and within the limitations resulting from the preceding operations. The changes are dynamic along the way, especially when stochasticity is involved.

In the language of the relatively new science of evolutionary developmental (evo-devo) biology (Carroll, 2011), the unchanging genotype of COULD and its changing phenotype make it purely developmental (devo).

Genomic equivalence and conditional differentiation

Genomic equivalence and conditional differentiation in COULD, with all adaptive cells carrying the same genetic package and full developmental potential, enable flexible development. Conditional differentiation complements genomic equivalence by determining which subset of genes to express and how and where to express them to produce a form that suits the situation. The full developmental potential remains so that a cell always has more possibilities than its current state and it is ready to change its physical form whenever the neighbouring cells change.

Differentiated cells need to be organised spatially to form a functional structure. Figure 4 contains four examples of differentiated cells that fit together to form a structure. Figure 4(a) is a cul-de-sac, (b) differentiates into a section of road with no land parcels attached, (c) represents four land parcels along the side of a road section and (d) is a similar configuration except that land parcels have different orientation.

Figure 4.

A structure with differentiated cells: (a) cul-de-sac, (b) connecting road section, (c) road section with land parcels and (d) land parcels at an angle.

The fate of living embryonic cells (their eventual form) is determined progressively during development (Hodge, 2010; Slack, 2013); their potentials are broad at the start and become narrower as development proceeds. Similarly, the adaptive cells change form during development and the potential for subsequent change tends to be reduced due to the constraints imposed by what is already in place. It is difficult to predetermine which part of the genotype will need to be expressed at what time so that the combination of genomic equivalence and conditional differentiation gives the robustness and flexibility that underpin the ability to adapt. The induction mechanisms discussed in the next section ensure that differentiation is context sensitive.

Induction

Induction is a term applied in various fields to particular types of inference or influence. In this study, partly following the usage in biology, induction is the determination of a cell’s form by other elements such as its fellow cells or the environment; and it determines how cells interact with each other and the environment. COULD uses three forms of induction, lateral inhibition, environmental induction and remote inhibition, all being contained in the genotype. The first two are implemented in verification genes responsible for feasibility checks (Section ‘Application of the developmental algorithm, COULD’), while the last one is used in the objective function to determine whether to accept or reject a change (Section 'Remote induction').

Lateral inhibition

Lateral inhibition is a competitive process important to pattern formation in nature and to this method of residential layout design. Cells differentiating early will inhibit differentiation in adjacent cells to ensure regular spacing. Similar things can be found during the growth of bird’s feather or tree leaves (Wolpert et al., 2007).

Lateral inhibition in COULD maintains cellular spacing; the road and land components of an existing cell can inhibit the growth of a new cell (entirely or partially) within its effective range. In Figure 5, a new cell on the left sprouts from the structure on the right. The residential lots on the right hand side (circled) of the new cell are suppressed by the existing land parcels.

Figure 5.

Lateral inhibition during differentiation and development.

Environmental inhibition

Environmental elements such as site boundaries and natural obstacles can also inhibit the growth of new structures. For example, in Figure 6(a), growth stops at the site boundary. Figure 6(b) shows growth stopping at the edge of a lake.

Figure 6.

Inhibition by boundaries and natural obstacles ((a) is an orthogonal design).

Remote induction

Remote induction in this model refers to layout changes being assessed by their impacts on the fitness of the whole. That is an induction process in which the existing cells determine the outcome of new changes. This form of remote induction is inspired by morphogenesis in biology (Hodge, 2010; Lawrence and Levine, 2006) which is simplified to distance decay, the strength of interaction declining with increased distance.

COULD uses the shortest road distance between two points for remote induction (Figure 7). Shortest network distance $d_{ij}$ is incorporated into the objective function (equation (1)), being compared with direct Euclidian distance $d_{ij}^{Eucl}$ to determine centrality. It is calculated between each pair of residential lots except those in the same cul-de-sac. The average ratio for all lots is used as one of the two components in the objective function (Section ‘An objective function to reflect community needs’).

Figure 7.

The shortest path between two residential lots.

Application of the developmental algorithm, COULD

Figure 8 shows the computing routine for experiments that start from scratch. It repeatedly applies the genotype (made of a set sequence of genes) with the goal of maximising the objective function. The model can also start from an existing design, in which case the first step will be changed to ‘open an existing file’. Everything else remains the same. The stepwise procedure is somewhat similar to that used by Greene (1989) to model plant growth.

Figure 8.

The computing routine for starting from scratch.

The operators ‘add’, ‘link’, ‘cut’ and ‘verify’ are differentiated for dwellings, roads and whole adaptive cells. Each operator (gene) is a collection of programming codes for implementing the processes described in Section ‘Formulation of the adaptive cell and its biological inspiration’. The add operator grows the structure (Section ‘Cell propagation during development’) by adding a road segment or dwelling or whole cell. The link operator forms cyclic paths by joining adjacent cells. The cut operator can remove previous growth to make way for new. Verification operators check structural integrity and violations of constraints.

The program starts by placing the seed cell(s) (Figure 8) after which each operator gene is fired a set number of times before the program moves to the next operator. Different sequences and firing frequencies of operators have been tried with various levels of success. In one of the more successful cases, a computing cycle attempted, subject to the acceptance tests, to add whole cells 100 times, to add dwellings 300 times, to link dwellings or roads 40 times and make cuts 20 times. The location of a gene’s execution is randomly selected from the eligible locations. For example, bud-a-cell (which grows a new cell from an existing land lot) will be fired by a randomly chosen lot of a randomly chosen cell. Cells without a lot (Figure 4b) are not eligible for such an operation.

All genes are context sensitive, following the mechanisms described in Section ‘Formulation of the adaptive cell and its biological inspiration’. The result is immediately checked by verification operators. If it is at least partially valid, the impact on fitness will be calculated and used in the acceptance test to determine whether to keep the operation. In deterministic decision making, new operations meeting the set criteria are accepted unconditionally and ones that do not are always rejected. With stochastic decision making, better results have more chance of acceptance but it is not guaranteed. Invalid operations that bring no meaningful changes and those that do not pass the probabilistic acceptance test are reversed. The algorithm terminates when the set criteria are met, normally the total number of iterations or time since last progress.

Results and discussion

Figure 9 illustrates the type of layout achieved when 45° road bends or intersections are allowed. In this case, decisions on acceptance of each valid computation step were stochastic. The block boundary lines have been inserted as indicated in Section ‘The structure of the adaptive cell’. This is a second round operation, using AutoCAD, after model development is complete.

Figure 9.

Computed street and subdivision plan for a 25 hectare site (dwelling centroids not shown).

A square site with one entry was chosen for simplicity. Multiple entries can be handled by putting a seed cell at each one but a prior link between them is required because the algorithm will remove disconnected elements. The link could be hypothetical, to be discarded when the plan is completed. COULD can also cope with variable site shapes and topography, including natural obstacles as illustrated in Figure 6(b).

Figure 10 shows how fitness improves during a typical development process. There is rapid improvement during the first stage (the first 70 or so computation steps to the left of the vertical dashed line) and then only fine adjustment to the almost completed layout. In this stage of the search there may be little or no increase in fitness.

Figure 10.

Fitness curve during a typical development search process.

A bottom-up method of generating residential plans

The capacity to generate much from little exhibited by COULD’s bottom-up method could be seen as a type of emergence – when elements in a system interact to produce new properties that are qualitatively different to their simple sum (Holland, 1998; Taylor, 1992). The separation between genotype and phenotype enables large complex phenotypes to emerge from a relatively small set of rules in the genotype.

Many (e.g. Bentley and Kumar, 1999; Dawkins, 1988; Hornby, 2003; Janssen, 2006; McCormack, 1993; Ulieru and Doursat, 2011) have used generative processes to overcome the limitations and rigidity of top-down paradigms. COULD is different in encapsulating the generative rules within the adaptive cells. This is similar to agent-based modelling (ABM), another bottom-up approach that may show emergent behaviour (O'Sullivan and Haklay, 2000). The adaptive cells can be viewed as agents carrying the decision rules contained in the genotype. They make their own decisions to self-propagate, adapting to others and the environment in order to survive. Dependencies between agents are negotiated so that their homogeneous rule set can produce heterogeneous physical forms. Although they are not mobile, the definition of ‘a self-contained problem-solving system capable of autonomous, reactive, proactive, social behaviour’ is applicable (Wooldridge and Jennings, 1999).

COULD was originally inspired by developmental biology so the biological analogy and its theoretical framework were pursued. With hindsight, the model is seen to have characteristics of a rewriting system such as L-systems or shape grammar. Most of COULD’s operators could be expressed as rewriting rules. If COULD were to be formulated as a rewriting system more rules might be required to replace the single mechanism of conditional differentiation in order to specify what happens in each set of circumstances.

Connectivity and the amenity of plans generated

High straightness centrality is one of the two components of the fitness of residential plans achieved by COULD under the guidance of the objective function (equation (1)); it is a measure of connectivity. There are polarised views on connectivity held by new urbanists and their critics among defensible space and CPTED (crime prevention through environmental design) advocates. The latter dislike high connectivity because it might make neighbourhoods vulnerable to burglary (Beavon et al., 1994; Davies and Johnson, 2015; Taylor and Gottfredson, 1986; White, 1990). Layouts produced by COULD are somewhat organic, achieve connectivity almost as high as a grid network (Sun et al., 2014) and could promote walkable and coherent communities. The winding roads, ringness and (mostly short) cul-de-sacs make the layout somewhat unpredictable, which should not be a problem for residents familiar with their surroundings. On the contrary, the authors argue that this type of layout is more interesting than regular patterns such as grids. The irregularity makes it harder for outsiders to navigate, a possible inconvenience for visitors and delivery personnel but a deterrent to possible intruders (Brantingham and Brantingham, 1991) and likely to reduce through traffic. Compared to lollypop patterns, it has more route choices, which should result in more evenly distributed internal traffic.

Comparison with top-down planning

Top-down methods of automated land subdivision include those presented by Dahal and Chow (2014), Vanegas et al. (2009), Vanegas et al. (2012) and Wickramasuriya et al. (2011). These applications generally imitate how human designers tackle the task, partitioning land parcels with prescriptive procedures such as recursive bisection or arithmetic approximation, all being specified by humans. Most of them are not treated as optimizing problems and are not guided by an objective function, but the purpose is usually to produce as many regularly shaped lots as possible, subject to geometrical constraints such as lot width or block size. Demetriou et al. (2013) apply a genetic algorithm for land partitioning but have not included roads.

In COULD’s bottom-up approach,there is no prescriptive subdivision. Although the adaptive cells are predefined, the planned layout emerges purely as the result of the interaction between cells. Whereas the prescriptive systems achieve regularity in lot shapes but often struggle to achieve variety (Dahal and Chow, 2014; Wickramasuriya et al., 2011), COULD generates varied road configurations and lot shapes but its designs are irregular even if the site is regular. To achieve regular blocks, orthogonality could be specified but then road bends and intersections would all be right angled due to the way the adaptive cells are constructed (Figures 3 and 6a). In contrast, top-down methods generate regular designs for both irregular and regular sites, relying on human domain knowledge to specify ad hoc procedures for different sites.

If regularity is important then prescriptive procedures may be preferred. However our intention is to get computers to generate novel designs – with features that are not foreseeable and are not implicitly coded by the designers. On the other hand, procedures that generate novel plans may be unpredictable (Knight, 2003). Results cannot be foreseen from inputs and a small change can cause a large shift in outcome.

Potential extensions

More operators can be developed and others improved. Lateral inhibition could be enhanced to deal with different land use types such as open space or public facilities that require larger clearance (Figure 11). An existing centroid could be chosen to mutate into a larger block by increasing its inhibition range. The location of the mutation could be random or based on some criterion such as high betweenness centrality.

Figure 11.

Lateral inhibition for a particular land use requiring large clearance.

Lateral inhibition could also be applied to intersections in order to make them comply with the separation requirements of traffic engineering standards (Figure 12).

Figure 12.

Intersection inhibition.

Conclusion

To generate residential plans by bottom-up incremental generation instead of top-down subdivision, a method of autonomous ‘creative design’ has been developed. Each plan results from repeated application of operators at random locations, subject to rules and constraints. The goal of the computer search is to achieve many mutually accessible residences in any specified site; this goal could be modified or expanded and more constraints added.

The key element is the adaptive cell which simultaneously lays roads and residential blocks, using a gene set to change cell expression during development. The form of each added cell is determined by the emerging environment, including other cells. Conditional differentiation determines which genes to express and how and where to express them. Cells change their configurations according to local environments so that topological and geometrical needs are satisfied at the same time, avoiding the complexities of a two-tiered approach.

In nature, complex phenotypes do not just appear; they evolve from simple forms. This principle is embodied in the adaptive cells developed for residential layout design by analogy with biological cells but these cells can also be viewed as self-propagating agents that resolve their dependencies through local interactions. The biological analogy underlies the fixed set of decision rules in the genotype that can lead to many planning outcomes under varying circumstances. Rather than having to specify every variable and relationship as in one-to-one mapping, this generative genotype defines the development process.

Development is crucial to the diversity found in nature and in this planning model. This paper shows that complex residential layout designs can be artificially generated by just a small set of rules. The development process is not a simple genotype–phenotype mapping but a dynamic transformation in which structure emerges.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The research was funded by Planning and Transport Research Centre (PATREC) and Australian Research Council Linkage project LP0562422.

Yuchao Sun has worked in both industry and academia, in which he participated in a range of research and consulting activities including some large scale infrastructure and mining projects. His main research interests include emergence, bio-inspired algorithms, the impact of future transport technologies especially Connected and Autonomous Vehicles, transport modelling, data analytics, optimisation, and discrete event simulation for supply chain management.

John Taplin became Director of the Bureau of Transport Economics following his PhD at Cornell University and later Deputy Secretary of the Australian Department of Transport with responsibility for rail, road, sea, air and international transport policy. Later he became Director General of Transport in Western Australia. As Winthrop Professor of Transport and Logistics at the University of WA, interests have included genetic algorithm and artificial intelligence applied to transport and the theoretical relationship between choice and demand. He was made a Member of the Order of Australia (AM) in 1993.

References

Atash

(1994) Redesigning suburbia for walking and transit: Emerging concepts. Journal of Urban Planning and Development 120: 48–57.

Aultman-Hall

Roorda

Baetz

(1997) Using GIS for evaluation of neighborhood pedestrian accessibility. Journal of Urban Planning and Development 123: 10–17.

Batty

(2005) Cities and Complexity: Understanding Cities with Cellular Automata, Agent-Based Models, and Fractals, London, UK: MIT Press.

Beavon

Brantingham

(1994) The influence of street networks on the patterning of property offenses. In: Clarke

(ed.) Crime Prevention Studies, Vol. 2, Monsey, NY: Criminal Justice Press, pp. 115–148.

Bentley

(1999) An introduction to evolutionary design by computers. In: Bentley

(ed.) Evolutionary Design by Computers, San Francisco, CA: Morgan Kaufmann, pp. 1–74.

Bentley

Corne

(2002) An introduction to creative evolutionary systems. In: Corne

Bentley

(eds) Creative Evolutionary Systems, San Francisco, CA: Morgan Kaufmann, pp. 15–74.

Bentley P and Kumar S (1999) Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In: Proceedings of the genetic and evolutionary computation conference (GECCO-1999). Orlando, FL: Kaufmann, pp.35–43.

Brantingham

(1991) Notes on the geometry of crime. In: Brantingham

Brantingham

(eds) Environ Criminology, Prospect Heights, IL: Waveland Press, pp. 26–54.

Cao

Batty

Huang

et al. (2011) Spatial multi-objective land use optimization: Extensions to the non-dominated sorting genetic algorithm-II. International Journal of Geographical Information Science 25(12): 1949–1969.

10.

Carroll

(2011) Endless Forms Most Beautiful: The New Science of Evo Devo and the Making of the Animal Kingdom, London, UK: Quercus Publishing.

11.

Centre for Genetics Education. (2013) The Human Genetic Code – The Human Genome Project and Beyond: Fact Sheet 24. St Leonards, NSW, Australia.

12.

Cervero

Sullivan

(2011) Green TODs: Marrying transit-oriented development and green urbanism. International Journal of Sustainable Development & World Ecology 18: 210–218.

13.

Cooper

Hausman

(2013) The Cell: A Molecular Approach, Sunderland, MA: Sinauer Associates.

14.

Crucitti

Latora

Porta

(2006) Centrality measures in spatial networks of urban streets. Physical Review E 73: 036125. 1–5.

15.

Dahal

Chow

(2014) A GIS toolset for automated partitioning of urban lands. Environmental Modelling & Software 55: 222–234.

16.

Davies

Johnson

(2015) Examining the relationship between road structure and burglary risk via quantitative network analysis. Journal of Quantitative Criminology 31: 481–507.

17.

Dawkins

(1988) The evolution of evolvability. In: Langton

(ed.) Artificial Life, SFI Studies in the Sciences of Complexity, Reading, MA: Addison-Wesley, pp. 201–220.

18.

Demetriou

See

Stillwell

(2013) A spatial genetic algorithm for automating land partitioning. International Journal of Geographical Information Science 27(12): 2391–2409.

19.

Desvoyes

Fernández-Marcos

Sequeira-Mendes

et al. (2014) Looking at plant cell cycle from the chromatin window. Frontiers in Plant Science 5: 369.

20.

Drira

Pierreval

Hajri-Gabouj

(2007) Facility layout problems: A survey. Annual Reviews in Control 31: 255–267.

21.

Fehér

(2015) Somatic embryogenesis — Stress-induced remodeling of plant cell fate. Biochimica et Biophysica Acta (BBA) – Gene Regulatory Mechanisms 1849(4): 385–402.

22.

Fogel

(1998) Evolutionary Computation: The Fossil Record, Piscataway, NJ: IEEE Press.

23.

Frank

Sallis

Conway

et al. (2006) Many pathways from land use to health. Journal of the American Planning Association 72: 75–87.

24.

Gero

(1995) Computers and creative design. In: Tan

Teh

(eds) CAAD Futures, Singapore: Centre for Advanced Studies in Architecture, National University of Singapore, pp. 11–19.

25.

Greene

(1989) Voxel space automata: Modeling with stochastic growth processes in voxel space. Computer Graphics 23(3): 175–184.

26.

Hajrasouliha

Yin

(2015) The impact of street network connectivity on pedestrian volume. Urban Studies 52(13): 2483–2497.

27.

Hemberg

O'Reilly

U-M

Menges

et al. (2008) Genr8: Architects’ experience with an emergent design tool. In: Romero

Machado

(eds) The Art of Artificial Evolution, Berlin, Germany: Springer, pp. 167–188.

28.

Hillier

Hanson

(1984) The Social Logic of Space, Cambridge, UK: Cambridge University Press.

29.

Hodge

(2010) Developmental Biology: From a Cell to an Organism, New York, NY: Facts On File, Inc.

30.

Holland

(1998) Emergence: From Chaos to Order, Cambridge, MA: Perseus Books.

31.

Hooper

Knuiman

Foster

et al. (2015) The building blocks of a ‘Liveable Neighbourhood’: Identifying the key performance indicators for walking of an operational planning policy in Perth, Western Australia. Health & Place 36: 173–183.

32.

Hornby GS (2003) Generative representations for evolutionary design automation. PhD Thesis, Department of Computer Science, Brandeis University.

33.

Hottenstein

Turner

Shunk

(1997) Bicycle and Pedestrian Travel Demand Forecasting: Summary of Data Collection Activities, Austin: Texas Transportation Institute.

34.

Janssen

(2006) A generative evolutionary design method. Digital Creativity 17: 49–63.

35.

Karr

Sanghvi

MacKlin

et al. (2012) A whole-cell computational model predicts phenotype from genotype. Cell 150: 389–401.

36.

Klug

Cummings

Spencer

et al. (2013) Concepts of Genetics: Pearson New International Edition, San Francisco, CA: Pearson Education, Limited.

37.

Knight

(2003) Computing with emergence. Environment and Planning B: Planning and Design 30: 125–155.

38.

Koenig

Bauriedel

(2009) Generating settlement structures: A method for urban planning and analysis supported by cellular automata. Environment and Planning B: Planning and Design 36: 602–624.

39.

Koohsari

Badland

Sugiyama

et al. (2015) Mismatch between perceived and objectively measured land use mix and street connectivity: Associations with neighborhood walking. Journal of Urban Health 92: 242–252.

40.

Lawrence

Levine

(2006) Mosaic and regulative development: Two faces of one coin. Current Biology 16: R236–R239.

41.

McCormack

(1993) Interactive evolution of L-system grammars for computer graphics modelling. In: Green

Bossomaier

(eds) Complex Systems: From Biology to Computation, Amsterdam, Netherlands: IOS Press, pp. 118–130.

42.

Marshall

(2009) Cities Design and Evolution, New York, NY: Routledge.

43.

Marshall

Sutton

(2014) Explorations in generative street layouts. In: Carmona

(ed.) Explorations in Urban Design: An Urban Design Research Primer, Surrey, UK: Ashgate, pp. 181–192.

44.

Mitchell

(1990) The Logic of Architecture: Design, Computation, and Cognition, Cambridge, MA: MIT Press.

45.

Okabe

Boots

Sugihara

(2009) Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Hoboken, USA: Wiley.

46.

O'Sullivan

Haklay

(2000) Agent-based models and individualism: Is the world agent-based? Environment and Planning A 32: 1409–1425.

47.

Parish YIH and Müller P (2001) Procedural modeling of cities. In: Fiume E (ed.) Proceedings of the 28th annual conference on computer graphics and interactive techniques. Los Angeles, CA: ACM, pp.301–308.

48.

Porta

Parapar

Doallo

et al. (2013) High performance genetic algorithm for land use planning. Computers, Environment and Urban Systems 37: 45–58.

49.

Prusinkiewicz

Lindenmayer

Hanan

et al. (1990) The Algorithmic Beauty of Plants, New York, NY: Springer-Verlag.

50.

Randall

Baetz

(2001) Evaluating pedestrian connectivity for suburban sustainability. Journal of Urban Planning and Development 127: 1–15.

51.

Slack

JMW

(2013) Essential Developmental Biology, Hoboken, NJ: John Wiley & Sons.

52.

Southworth

Ben-Joseph

(2003) Streets and the Shaping of Towns and Cities, Washington, DC: Island Press.

53.

Strano

Nicosia

Latora

et al. (2012) Elementary processes governing the evolution of road networks. Scientific Reports 2: 296.

54.

Sun

Qiu

Taplin

(2014) Achieving residential connectivity and density goals with computer-generated plans in a greenfield area. Environment and Planning B: Planning and Design 41: 430–449.

55.

Tam

(1992) A simulated annealing algorithm for allocating space to manufacturing cells. International Journal of Production Research 30: 63–87.

56.

Taylor

(1992) “Fleshing out” Artificial Life II. In: Langton

Taylor

Farmer

et al. (eds) Artificial Life II, Redwood City, CA: Addison-Wesley, pp. 25–38.

57.

Taylor

Gottfredson

(1986) Environmental design, crime, and prevention: An examination of community dynamics. In: Reiss

Tonry

(eds) Communities and Crime, Chicago, IL: The University of Chicago Press, pp. 387–416.

58.

Tero

Takagi

Saigusa

et al. (2010) Rules for biologically inspired adaptive network design. Science 327: 439–442.

59.

Tuhus-Dubrow

Krarti

(2010) Genetic-algorithm based approach to optimize building envelope design for residential buildings. Building and Environment 45(7): 1574–1581.

60.

Ulieru

Doursat

(2011) Emergent engineering: A radical paradigm shift. International Journal of Autonomous and Adaptive Communications Systems 4: 39–60.

61.

Vanegas

Aliaga

Benes

et al. (2009) Visualization of simulated urban spaces: Inferring parameterized generation of streets, parcels, and aerial imagery. IEEE Transactions on Visualization and Computer Graphics 15(3): 424–435.

62.

Vanegas

Kelly

Weber

et al. (2012) Procedural generation of parcels in urban modeling. Computer Graphics Forum 31(2): 681–690.

63.

Vragović

Louis

Díaz-Guilera

(2005) Efficiency of informational transfer in regular and complex networks. Physical Review E 71: 1–9.

64.

Wagner

(2014) Arrival of the Fittest: Solving Evolution's Greatest Puzzle, London, UK: Oneworld Publications.

65.

White

(1990) Neighborhood permeability and burglary rates. Justice Quarterly 7: 57–67.

66.

Wickramasuriya

Chisholm

Puotinen

et al. (2011) An automated land subdivision tool for urban and regional planning: Concepts, implementation and testing. Environmental Modelling & Software 26(12): 1675–1684.

67.

Wolpert

Tickle

Lawrence

et al. (2007) Principles of Development, Oxford, UK: Oxford University Press.

68.

Wooldridge

Jennings

(1999) Software engineering with agents: Pitfalls and pratfalls. Internet Computing, IEEE 3: 20–27.

69.

Appleton

(2002) The optimisation of block layout and aisle structure by a genetic algorithm. Computers & Industrial Engineering 41: 371–387.

70.

Xie

Levinson

(2009) Modeling the growth of transportation networks: A comprehensive review. Networks and Spatial Economics 9(3): 291–307.

71.

Yang

X-S

(2014) Nature-Inspired Optimization Algorithms, New York, NY: Elsevier Science.

72.

Zhao

Sun

et al. (2016) Population-driven urban road evolution dynamic model. Networks and Spatial Economics 16(4): 997–1018.