Chris Webster, Fulong Wu and Sheng Zhou
Department of City and Regional Planning, Cardiff University, PoBox 906, Cardiff CF1 3YN, United Kingdom
Email: firstname.lastname@example.org; email@example.com; firstname.lastname@example.org
This paper will present a version of Wu and Websters’ urban growth simulations (Webster and Wu 1997a 1997b, Wu and Webster 1998) re-worked using object-oriented (o-o) constructs. The key feature of these simulations is that they integrate cellular automata (CA) and traditional urban economic modelling paradigms. The transition rules that govern urban evolution articulate property rights economic theory and the simulated cities are optimal in the sense of being in social and spatial equilibrium. Here we describe how a CA model may be translated into an o-o data model for implementation in C++ . The main object of the exercise is to simplify the structuring and scripting of a complex dynamic geo-computational model in order to facilitate network-based interactive visualisation in the future. CA simulations conventionally rely on an explicitly raster data model which is ill-suited to model editing or to the development of flexible and modifiable visual interfaces. Our o-o model , in contrast, hides the three dimensional arrays that model activities in space behind the class structures of a semantically rich modular programme. It also allows all the spatial analytical functions in the model to be coded as methods that are attributed to cell and super-cell class objects. The result should be a fast and flexible version of an essentially cellular urban growth model that is well adapted to modular development, customisation and implementation in a heterogeneous network environment.
Key words: dynamic modelling, urban simulation, spatial analysis, urban economics.
There has been a long tradition of urban modelling but only recently have there emerged microscopic simulation approaches to understand urban dynamics (Batty, Couclelis, and Eichen, 1997). Dating back to Hägerstrand’s (1965) simulation of diffusion phenomenon, cellular models are gaining increasing attention. Owing to their simplicity, intuitiveness, flexibility and transparency as a modelling framework, cellular automata (CA) have wide appeal. Simulations using CA have been widely applied but early attempts were typically more in the nature of metaphors of urban growth with little explicit relationship to underlying behavioural theory (Couclelis, 1985; Batty and Xie, 1994). With a better understanding of the technique, CA simulation is at the stage of exploring more complex and theoretically-based experiments. A variety of ways of calculating the potentiality of state transition and defining game rules have been reported in the literature (White and Engelen, 1993; Batty and Xie, 1994; Portugali et al, 1995; Wu and Webster, 1998). These exercises highlight the need for an integrated approach which combines CA’s relatively simple abstraction with the behaviourally richer models of urban processes found in the social sciences (Gilbert and Doran 1994). In a simulation of emergent generic urban subcentres, Wu (1998) explores hypothetical rules which explain the balance of pattern destroying and maintaining tendencies. However, with all these approaches a critical question remains regarding the way these rules should be interpreted in economic or other behavioural terms. The behavioural aspect of most CA simulations is still weak.
In terms of methodology, simulation has been conventionally carried out through procedure numerical programming. Typically at present, geographical simulations are implemented in a hybrid platform of high level script based GIS of other graphics languages and procedural code for numerical routines. Simulation is thus a procedure to manipulate the variables according to a set of rules and to observe changes in and relationship between these variables. This notion can easily be extended to an object- oriented simulation. The only difference is that the manipulation here is based on general entities or objects. The variables used in conventional simulation can be seen as the simplest objects which have only one attribute and these are embedded within an semantically rich object data model. The principle benefit for an o-o implementation we feel is the flexibility it gives to model adjustment when conducting theoretical experiments.
The stimulus for our urban simulation models comes from Wu and Websters’ (1998) work on methodological aspects of urban CA and Webster’s theoretical work on urban regulation and property rights (Webster 1998a, 1998b). The models are designed to explore the generic urban form resulting from alternative regulative regimes based on Pigovian and Coasian theories of externalities, public goods and transaction costs. They do this by simulating a mixed-market urban land economy in which developers competitively bid for sites according to the profitability of development within the constraints of various forms of government regulation and taxation controls.
The models have the following innovative feature:
The basic behavioural model underlying the simulation is that of the profit maximising developer (two types - industrial and residential) and the externality-avoiding community. Developer behaviour is represented by a falling marginal profit function. Each cell in urban space has such a function, the height of which depends on the configuration of surrounding land uses. Similarly, each cell if developed as polluting industry, will generate externalities which are consumed and valued by the surrounding residents. This is represented by a rising community externality function, the height of which depends on the number of residential cells within its sphere of influence and the distance of each. Developer profit functions are of the general form:
where the a is a function K, of the number of similar land uses in surrounding cells (reflecting agglomeration economies) and Q is the intensity of development. Community externality functions are of the general form:
where the slope q is a function of the number of residential cells in the sphere of an industrial cell’s influence.
They are related under equilibrium assumptions using the traditional Coasian analysis (Figure 1).
Figure 1. The equilibrium assumptions of marginal profit and externality of urban development
Cells are developed under a Monte Carlo simulation in which the probability of development into residential or industrial land use is a function of the relative profitability of the two land uses; stochastic influences; and the regulative or taxation regime governing the development process. The latter can be illustrated with reference to the Figure above. Under a pure market city with no government intervention, total profitability of a cell is given by the area A+B+D or:
Under a regime which regulates land use intensity to the socially optimal level Qk* but does not seek compensation, the profit from cell ij is given by the area under P(Q) to the left of Q*:
where Q* is given by the intersection of profit and externality curves. Armed with these two functions, a variety of regulative constraints can be simulated and the efficiency outcomes compared with the free-market maximum profit scenario or the socially efficient scenario at which marginal private benefit equals marginal social cost.
For a regime in which the community has full property rights over development externalities and seeks full compensation, the profit of development is reduced to the area D and profit is given by:
These regimes are, of course, caricatures. There are many theoretically interesting planning constitutions and behavioural adaptations of rights under those constitutions which could be simulated in this way. For example, if development rights rest with the community, the community may seek to maximise exaction revenue by taking an arbitrary proportion of D (betterment). If property rights effectively rest with the developer (due to toothless planning regulations for example), the community may bribe the developer to reduce output, thus increasing profit beyond D+B+A.
In Object-oriented technology an object is a direct mapping to a real world entity with states (attributes) and behaviours (methods). In the OO paradigm, data and processes on data are not separated as they are in previous programming paradigms. Object oriented methodology is an approach to program construction which takes modularity to the extreme in order to achieve certain good-programming objectives. Importantly these include robustness, extendibility, reusability and compatibility. The approach is consistent in that it integrates data with the operations on these data. New applications can be built upon the reuse of existing programming modules saving redundant programming work. The existing modules can be extended into new modules to cover new data and functionality. In many ways, the most significant advantage of OO approach is its power to decompose complexity in a problem domain because it offers a direct and more intuitive way to model the semantics and processes of the real world (Kidner and Jones, 1994). Among many features of object orientation, object identification, inheritance, encapsulation, and object persistence are widely regarded as those which have made the approach such a successful one.
There are a number of advantages which an OO approach can offer to simulation. There are obvious benefits, for example, in working with a conceptual data model which reflects the problem domain in all aspects including entities, attributes, relationships and functionality and maps this model efficiently to implementation code. The extensibility and reusability of OO systems is also invaluable for efficient model construction. The parts of common data components and functionality can be separated and reused. The model developer can concentrate on the structure and actions of the model itself rather than on those often complicated and redundant auxiliary data components and functionality. Arguably it is this flexibility of the 0-0 modular approach that makes it particularly useful for designing and coding highly complex simulations. There is inevitably a great deal of ad hocary and experimentation in a simulation algorithm. There are generally multiple ways of constructing any particular routine and it is rarely clear at the start which is the best. Simulations proceed by experimentation and learning from practice. Form this perspective the open structure of an o-o development environment is highly attractive. New adaptations can be constructed from well-tested and well understood existing modules.
The computational procedure adopted in the O-O version of our simulations is different from the one previously used (Webster and Wu, 1998 forthcoming). To implement the theoretical model as a computational model, a variety of algorithmic issues needs to be considered. This section discusses some of the more important of these issues.
Initial state. To ensure that simulation results are not biased by the initial configuration, the initial state is a random one. An approach we have used in the past is to start from a grid which consists a small number of randomly distributed residential and industrial cells. However, when the local interaction kernel is small (3x3 for example) the limited number of seeds leads to a large amount of cells remaining undifferentiated from each other in the early stages of the simulation. In other words, many cells will have similar development potential (profit). The problems of concurrency have be treated carefully in this situation and requires additional complication of the algorithm. The problem can be avoided by randomly allocating all cells into either industrial or residential uses.
Creating cities. The top level class in the simulation is the metropolis, which is subdivided into cities. Cities can adopt different development policies. A procedure is used to automatically create multiple cities through allocating initial seeds and expanding the jurisdiction areas around these seeds. After creating the initial state (Figure 2 for the random initial state, Figure 3 for the random initial cities), the simulation proceeds according to the partial equilibrium models governing the transition of cells into two kinds of land use at variable density.
Figure 2. The random initial state of land use
Figure 3. The random computer-generated cities
Land use conversion. The basic mechanism of land use conversion is that the land use raising the highest bid occupies the site. Bidding power is related to the profit gained from the site and the simulation calculates profits for each cell for industrial and residential use during each developing cycle. This created two sets of development potentialities which are then sorted into sorted vectors. In each vector the number of cells to be developed in one iteration are selected, highest valued cells first. This number is different for the two use-types with the ratio of industrial to housing given exogenously (following economic base theory). However, any single cell might be contained in both lists. The competitive bidding rule would then classify the cell to the use with the highest profitability. This disturbs the land use balance which then has to be redressed somehow. There are a number of alternative algorithms for achieving this. We have taken the approach of creating a ‘candidate pool’ of the two land uses from which cells are drawn (in profit order) to make up the required target number and ratio.
Externality field. Externalities measured through a spatial interaction function. Each cell object contains externality function or method which can be implemented to consider the impact of a polluting industrial development on the rest of the city. The function is dynamic in the sense that the marginal value of the externality (the rate at which the value of the externality rises as development intensity rises or dE/dQ) is a function of the number and spatial distribution of neighbouring residential cells. The valuation of externalities from a polluting cell is calculated as:
g is a positive constant value of distant decay;
d is the distance between the source of pollution and the affected cell;
B is an identifier, B=1 if the affected cell is in residential and also in the same jurisdiction (city) of the evaluated cell (the source of pollution), B=0, otherwise;
The final measure of the cost of a cell’s externalities is defined by dividing the measured value of I by the maximum value of I in a situation where the jurisdiction is fully developed into residential use except the cell under the evaluation. In other words, the weight is a relative measure of intensity of externality:
Wc is the relative intensity of marginal externality at site c;
Ic is the actual intensity of externality at site c.
Indicators and reporting. The simulation proceeds with iterative looping. Programmed in an OO paradigm, at any stage, the state of simulation can be preserved as an object database file. To observe the changing state, the state can also be reported as the following illustrates:
*** Metropolis summary ***
X dimension: 100 Y dimension: 100
Amount of cities: 15
Amount of site not developed: 0
Amount of Industrial Sites: 3092
Amount of Industrial Sites developed in this cycle:
Newly Developed Industrial site: 0
Converted from Residential site: 0
Redeveloped Industrial Site: 2988
Amount of Residential Site: 6908
Amount of Residential Sites developed in this cycle: 2987
Newly Developed Residential site: 0
Converted from Industrial site: 0
Redeveloped Residential Site: 2987
Current Completed Developing Cycle: 100
Industrial Production in this cycle: 57955.3 Profit: 289776
Residential Production in this cycle: 59740 Profit: 298700
Total Aggregated Industrial Production: 6.71483e+06 Profit: 3.42349e+07
Total Aggregated Residential Production: 5.95388e+06 Profit: 3.06199e+07
*** City Summary ***
Object ID: 2
City Parameter Set#1
Site Parameter Set#1
Core Site: Object ID: 4647 X: 46 Y: 30
Site amount: 716
Amount of site not developed: 0
Amount of Industrial Sites: 540
Amount of Industrial Sites developed in this cycle:
Newly Developed Industrial site: 0
Converted from Residential site: 0
Redeveloped Industrial Site: 320
Amount of Residential Site: 176
Amount of Residential Sites developed in this cycle: 173
Newly Developed Residential site: 0
Converted from Industrial site: 0
Redeveloped Residential Site: 173
Current Industrial Production: 6252.4 Profit: 31262
Current Residential Production: 3460 Profit: 17300
Total Industrial Production: 705024 Profit: 3.62481e+06
Total Residential Production: 321280 Profit: 1.66573e+06
The changes in the simulation state can also be exported into a variety of images to observe spatial distribution. For example, the land use conversion at one iteration can be shown as an image in Figure 4. To sum up, a variety of indicators can be summarised and reported. These may include: the total profits of n sectors of land uses, total externality, total quantities of production, and the measurements (such as Moran I and segregation index) of spatial patterns of all these indicators.
Figure 4. land use conversion at an iteration
The architecture and the main components of GeoLib are shown in Figure 5 and include:
Figure 5. The architecture of GeoLib
The class model of this simulation involves a three-layer urban system. At the top of is the Metropolis. At the middle is the City. At the bottom is a development Site. We believe this conceptual three-layer model should fit the general purpose of urban simulation. The model provides various macro to micro levels for simulating spatial policies. This class model is implemented with the support of GeoLib.
In terms of abstraction, the state and behaviour of classes (metropolis-city-site) are decomposed into three levels (Figure 6). At the highest level some generic features are defined. At the middle level, the spatial forms of metropolis/city/site are specified while at the lowest level, specified attributes/behaviours are defined. With resort to the top and middle levels, a simulator can be developed by writing C++ modules at the third level. At present, a grid-based structure has been implemented for this three layer hierarchy. Class Grid_Metropolis contains a GeoGrid (or an instance of its derived class) object as well as an array of all cities; Grid_City contains two arrays to record its internal and boundary sites, which implies a vector-style structure inside a grid system. Grid_Site is the basic unit in this three-layer urban system hierarchy. All components at the same level of abstraction as ‘Grid_’ are fully reusable to any domain- related grid-based applications. As simulations often need to create random data set from scratch, Grid_Metropolis has a member function which generates a set of cities within this metropolis. These cities have randomly distributed seeds and sizes. To create classes for this urban simulation model (USM), more detailed members are added to Grid-family classes, thus creating three classes: USM_Metropolis, USM_City and USM_Site.
Figure 6. The class structure of simulation
Specific model-related parameters are attached to these three classes. These parameters can be set universally in the whole metropolis or assigned individually to City and Site objects. This clearly demonstrates the flexibility of OO technology. Without the use of objects, applying a specific set of parameters to a particular site or city is extremely tedious. In terms of raster or map based procedural programming, this would require complicated referencing between layers. By creating objects, different parameters can be applied to specific spatial areas. Parameters related to three classes used in the simulation are given as follows.
For a Metropolis object, the list of parameters is:
For a City object, the list of parameters is:
For a Site object, the list of parameters is:
The discussion of detailed parameter sets is beyond the scope of this paper. Currently, we are still at the stage of fine tuning the parameters and model validation. But some experiments have been run, clearly showing that the model structure is flexible enough to meet a variety of modelling demands.
For the time being, the O-O version of the simulation has not yet been equipped with a graphic interface and display. We export the selected state to IDRISI, a raster-based GIS for display. While this saves reprogramming some spatial analysis functions available in GIS, the object identities are lost during file transferring and the advantages of the Object framework are not extended into the graphics part of the simulation.
Currently only limited experiments have been run using the object-oriented implementation and we present results here for the purpose of illustration. The simulations include a free market regime (full property rights rest with land developers) and a regulated regime (community has rights over development) in which the social cost is fully compensated.
The initial state is developed through land conversions by two simulations. After 40 and 100 iterations respectively, the land use patterns evolves to the states shown in Figures 7 and 8 (free market regime) and Figures 9 and 10 (regulated regime). While it seems that the agglomeration effect embedded in a local kernel function fails to cluster industrial uses, imposing the penalty of pollution clearly changed the ‘random’ patterns. We are currently investigating the reasons why there is a lack of clustering in the first regime and testing the sensitivity of parameters. The size of kernel and the computational procedure may be responsible. It seems that the compensation function contributes a further force in separating two types of land uses. To further illustrate the characteristics of the two regimes the distribution of profit and development intensity are shown in Figures 11-12 (for the case of free market) and 13-14 (for the case of regulated regime). To visualise the output, Figures 15-16 show the measurement of spatial autocorrelation obtained through IDRISI.
While it is obvious that two simulations contrast with each other, it must be noted that a range of tests is still needed. The most critical issue, as in all simulation, is to separate the factor under examination (here the assumption of profit with and without compensation) with other factors (the implementation procedure, distant decay parameter, kernel size, etc.). It is widely recognised that all simulation work faces the difficulty of validating the model, especially involving a complicated computational procedure and a wide range of parameters. Hill (1996) suggested a number of methods in the verification and validation of simulation models and emphasised that verification and validation should be applied not only after the implementation phase but throughout the modelling cycle. Our experiments support this viewpoint. In fact, the testing of models should be seen as a way to better understand the behaviour of the model. At the next stage we will introduce a certain disturbance to each parameter and see how the model responds and thus evaluate robustness of the model. In particular, we are interested in validating whether land uses tend to cluster to a higher extent if the compensation of externality is sought by the community.
Figure 7. The free market regime at t=40
Figure 8. The free market regime at t=100
Figure 9. The regulated regime at t=40
Figure 10. The regulated regime at t=100
Figure 11. The distribution of profit of free market regime
Figure 12. The distribution of development intensity of free market regime
Figure 13. The distribution of profit of regulated regime
Figure 14. The distribution of development intensity of regulated regime
Figure 15. The spatial autocorrelation measurement of free market regime
Figure 16. The spatial autocorrelation measurement of regulated regime.
Perhaps the most valuable aspect of object-based simulation is that it permits a high degree of flexibility to model complex behaviour. The discussion above illustrates why that flexibility is so important in the essentially creative activity of simulation model building. While many of the advantages of the object-oriented approach are still to be realised in this urban simulation model, it is clearly evident that conceptualising urban growth and land use changes as a process in which many objects - sites, cities, regions - interact with each other helps tracing its dynamics. Each object may have a distinctive set of attributes which specifies its behaviour and in consequence its action sends a signal to others. This can be conceptualised in the object-oriented process as sending a message between objects and easily translated into programming codes.
While all this is fine in theory, this does not necessarily mean the programming tasks can be easily achieved. To date, a flexible simulation environment which can allow users to define objects and specify object behaviour is still lacking. Using the C++ language to develop codes directly can be effective but imposes the heavy burden of re-programming the functionality found in GIS packages (spatial data storage, retrieval, manipulating and display). Most importantly, if the results of a simulation is to be exported to a GIS environment for the purpose of analysis and display, the advantages of the object model are lost at this stage. The objects defined in the simulation cannot be recognised, manipulated or queried in a GIS environment if the latter does not support object oriented features. In this respect our simulation experiment has exposed some limitation of current GIS techniques, especially in terms of dynamic modelling.
A number of issues are raised for future research. First, there is a need to develop a general purpose simulation tool which is ideally equipped with rich graphical interface and display functions but also supports object oriented features. There have been some attempts to develop stand alone CA modelling tools (Cecchini, 1996) and dynamic modelling languages (Wesseling et al, 1996). Future research should also be directed towards the development of simulation tool in a heterogeneous network environment. At the next stage we will use Java language to rework this simulation model and develop a Web-based simulation environment. Through resorting to rich graphic resources, the encapsulated objects can be directly displayed and manipulated. But the efficiency of Java with regard to a heavy computation task still waits to be explored.
Ammeraal L, 1997, STL for C++ Programmers. John Wiley & Sons Ltd, Chichester, England.
Batty M, Couclelis H, Eichen M, 1997, “Urban systems as cellular automata”, Environment and Planning B 24 159-164
Batty M, Xie Y, 1994a, "From cells to cities", Environment and Planning B 21 531-548
Cecchini A, 1996, “Urban modelling by means of cellular automata: generalised urban automata with the help on-line(AUGH) model” Environment and Planning B, 23 721-723.
Couclelis H, 1985, "Cellular worlds: a framework for modelling micro-macro dynamics", Environment and Planning A 17 585-596
Gilbert N, Doran J, 1994, Simulating Societies: the Computer Simulation of Social Phenomena (London: UCL press).
Hägerstrand T, 1965, “A Monte Carlo approach to diffusion”, Archive of European Sociological, VI, 43-67.
Hill D R C, 1996, Object-oriented analysis and simulation. Harlow, UK: Addison- Wesley.
Kinder D B, Jones C J, 1994, A deductive object-oriented GIS for handling multiple representations, in T.C. Waugh and R.G. Healey(eds.), Advances in GIS Research, Taylor & Francis, London, ii.882-900
Portugali J, Benenson I, 1995, "Artificial planning experience by means of a heuristic cell-space model: simulating international migration in the urban process" Environment and Planning A 27 1647-1665
Stroustrup B, 1997, The C++ Programming Language, 3rd. ed., AT& T: New York.
Webster CJ, 1998a, Public Choice, Pigovian and Coasian Planning Theory, Urban Studies 35(1), pp 53-75.
Webster CJ, 1998b, Analytical public choice planning theory. Accepted by Town Planning Review 69(2), pp191-209.
Webster CJ, Wu F, 1997a, Simulating Urban Growth Under Alternative Systems of Property Rights, in Sikdar PK, (Ed) Proceedings of the 6th International Conference on Computers in Urban Planning and Urban Management, held in Bombay 16-19 December 1997, Bombay: Indian Institute of Technology, pp734-745.
Webster CJ, Wu F, 1997b, Simulations of urban growth with models of pollution property rights and subcentre formation, in Mumford A (ed.), Graphics, Visualisation and the Social Sciences, Report from Workshop held May 8-9 at Loughborough University, Joint Information Systems Committee (JISC) Advisory Group on Computer Graphics (AGOCG) Technical Report Series No. 33, pp115-122, ISSN 1356-9066.
Webster CJ, Wu F, 1998 - forthcoming, Urban growth, pollution property rights and land use zoning, Accepted by Environment and Planning A.
Wesseling C, Karssenberg, D, Burrough P A, Deursen W, 1996, “Integrating dynamic environmental models in GIS: the development of a dynamic modelling language”, Transactions in GIS, 1, 40-48.
White R, Engelen G, 1993, "Cellular automata and fractal urban form: a cellular modelling approach to the evolution of urban land-use patterns" Environment and Planning A 25 1175-1189
Wu F, Webster CJ, 1998, “Simulation of land development through the integration of cellular automata and multi-criteria evaluation”, Environment and Planning B 25, pp103-126.
Wu F, 1998, forthcoming, “An experiment on generic polycentricity of urban growth in a cellular automatic city” Environment and Planning B.
Zhou S, 1998 (under preparation), Object-oriented Geographical Information Handling: with Planning Applications. PhD thesis, Cardiff University.