Representation and reasoning in Architectural space: a linear tesseral approach

Brown, A.G.P., Knight, M.W., Coenen, F.P.
and Geraghty, P.J.

School of Architecture and Building Engineering,
The University of Liverpool, U.K.
Department of Computer Science,
The University of Liverpool, U.K.

0. Introduction

The representation of space using the Cartesian system tends to lead to computationally expensive analyses when, for instance, we try to apply reasoning techniques embodied in an AI system. The approach that we describe here to tackling this problem uses the concept of tesseral addressing to describe the geometry of the space being represented. With this technique it then becomes possible to apply a spatial reasoning system based on the use of tesseral addressing. The system used here is referred to as SPARTA (SPAtial Reasoning using Tesseral Addressing) the system having been developed and refined by Coenen et.al. (1996a, 1996b).

The tesseral system currently being used in the SPARTA approach has its roots in the addressing technique referred to as Morton sequencing (Morton 1966). An early application of this system was in the investigation of atomic structures. The technique developed by Morton takes two dimensional space and divides it into cells referred to as tiles. The tiles are each assigned an address that uniquely defines its location and its spatial relationship with reference to the remaining tiles in the space. In effect the sequence defines a ribbon or string that ties the space together in a consistent repeated (tessellated) pattern (Figure 1).

Figure 1: The addressing system proposed by Morton

There are other forms of tesseral addressing that have been used. What these addressing systems have in common is the subdivision of space into isohedral (same shape) sub-spaces. These sub-spaces are most frequently found to be squares (usually called tiles) as the tessellated shape in a two dimensional representation.

One approach to subdivision (see, for example, Samet 1984) is to take the space and successively decompose it into sub-spaces until an acceptable degree of resolution is reached. This is a hierarchical approach. Alternatively the space can be divided up immediately at some chosen degree of resolution. This leads to linear tessellation as a way of defining the space.

In order to apply a reasoning approach to the analysis of the space the ribbon referred to above can effectively be unravelled and what we are left with is a one dimensional representation of the space which thus facilitates the application of reasoning which is both within the system and which is computationally effective. This compares well to other approaches where data is extracted from a GIS system and then the reasoning is applied to that data. GIS environments are data rich and Openshaw (1991) noted that new spatial analysis methods are needed to supersede the application of conventional spatial statistical methods to GIS data. The SPARTA approach provides a way of achieving the increased efficiency that Openshaw referred to.

 

256. The SPARTA Approach

The principal advantage of the SPARTA system is the definition of spatial concepts using a linear quad-tesseral representation (Diaz and Bell 1986) and the computational effectiveness that results from this representation. The representation takes the locations in an N-dimensional grid and identifies them with an address in the form of a single integer.

The reasoning technique embodied in the SPARTA system uses a depth-first constraint satisfaction technique supported by a heuristically guided constraint selection mechanism (which limits the growth of the search space). The kind of problem being addressed here, where a solution that satisfies a set of constraints is required, is usually referred to as a constraint satisfaction problem or CSP (van Hentenryck, 1989).

 

512. Advantages and refinements

The early work on the SPARTA system adopted the Morton sequence as a technique for addressing and was limited to two dimensional space. An alternative to the Morton sequence is a more direct left to right linearisation and this is the way in which the quad tesseral addressing system works in the application described here (see Figures 2 and 3)

Sign bit

Dimension 4 7 bits

Dimension 3 8 bits

Dimension 2 8 bits

Dimension 1 8 bits

Figure 2: Address bit pattern

Figure 3: Tessellated 2D space

In addition, pragmatic considerations dictate that it is most effective to increase the number of dimensions by two at a time. In the example given later the number of dimensions has been limited to four. Also, in the case that we describe, the addresses have been limited in size to 32 bit signed integers. 64 bit integers can be used but the addresses then become inappropriately long for the purposes of illustration.

Eight bits are allocated to the first three dimensions and seven for the fourth. The sign bit provides the facility for translating addresses through the space in any direction (Figure 2).

In two dimensions the tesseral unit is commonly the square (or tile); the three dimensional equivalent becomes the cube (or cell).The nature of the linearisation means that it is possible to calculate the tesseral address of a cell as follows:

address = r1 + r2(2⁸) + r3(2¹⁶) + r4(2²⁴)

in which r1 to r4 represent the discrete coordinates in the four dimensions. r1 to r3 will normally represent geographic space whilst r4 represents a fourth dimension which may well be temporal. For instance in Figure 3 the two dimensions are X and Y such that :

X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and

Y = {0, 1, 2, 3, 4}

Consequently the linearisation flows from bottom left (at 0) at the origin to the top right.

The particular advantages of the tesseral system described are:

a) A single integer defines any cell location, unlike the Cartesian system where the number of coordinates increases linearly with the number of dimensions. As a consequence tesseral addressing produces a constant and lower computer storage requirement.

b) Translation through space can be achieved through simple integer addition and subtraction. For example in Figure 3 to move one tile North-west we (always) add 255 and to move one tile South-west we subtract 257. Again, this compares well with Cartesian translation which would require the application of either trigonometric techniques or incrementation/decrementation to perform a translation through space. Computationally, these techniques are comparatively expensive or cumbersome.

c) Groups of addresses can be compared simply since knowledge of the linearistion system means that addresses to not have to be compared individually. Thus the relationship of one group of addresses to another group is relatively easily determined.

d) It is fully compatible with established raster representations.

The potential disadvantages of the technique are that:

a) It is usually difficult to interpret addresses directly. But since it is fairly straightforward to add translators to turn SPARTA scripts into Cartesian coordinates this is not a significant drawback.

b) Linear tessellation requires the size of cells defining the problem space to be decided at the outset of the problem. It is possible that solutions could reveal differences in important values between adjacent cells which are large in critical areas. This could suggest that the grid chosen is too coarse and the problem would have to be recast.

More details on the computational advantages and the SPARTA the associated Spatial scripting language are presented elsewhere (Coenen et.al., 1997). In short the main "geographic" space is modelled first and then "objects" are added to the space. There are two significant "classes" of object in the example that we cite later; fixed objects and shapeless objects. Constraints define the relationship between spatial objects and of the relationships that are possible within the system "mappings" are the most significant.

 

768. Application to a real case

The application of the technique that we describe here is for a real problem. The case being considered is that of a Planning Public Inquiry into the effects of a proposed new access structure to be added to a major exhibition Hall in London which hosts a large number of national and international events. The proposed new access structure was aimed at relieving the problems of event management, and in particular, site organisation and congestion that result from these exhibitions and shows. There were two principal problems which could result from the acceptance of the new scheme; the loss of part of a Nature Conservation area and the generation of noise pollution as the heavy goods vehicles on the proposed structure as they passed close to existing dwellings. Our example concerns itself with the prediction of noise levels generated by traffic on the new structure.

This is not a particularly complex scenario in an architectural and environmental sense, but it serves well to illustrate how the technique described can be applied to a real world, built environment problem.

Aerial photographs show the development area as existing (Figure 4a) and, with the aid of photomontage, as proposed (Figure 4b).

Figure 4a: Aerial photograph with main site boundary marked	Figure 4b: Aerial photograph with proposed structure added in photomontage

The coarseness of the grid of cells is dictated by what we felt would be the smallest distance that we might get significant noise difference between. In this case we took 2.5m to be the appropriate size for the tesseral unit (cell).

The sound power values used for the goods vehicles in our analysis come from the evidence presented at the Planning Inquiry. There was some disagreement between the two parties in the inquiry proper about the sound generated by the noise sources. For instance the objectors said that the sound values being used were for new vehicles and that older vehicles tend to generate higher sound power values. With this in mind we took the data actually presented in the Inquiry which showed a maximum value for a new 7.5 tonne vehicle of 83dB.

Given the measured vehicle flow rates we concluded that there would only be one vehicle on the access structure at any particular time. The worst case scenario is therefore for the condition where there is one vehicle (so we represent this as a point source, rather than a line source; D.O.T. 1988) generating a sound pressure level of 83dB at 7.5m from the source. This sound pressure level converts to a sound power level at the source of 108.5dB.

Given this scenario our task was to find the worst case for noise pollution (the level and location) at the residential block near to Earls Court. This block is referred to as bb6 in our representation.

 

1024. Alternative modelling strategies and their outcome

The scenario outlined above has been modelled as a four dimensional problem; three dimensions to represent geographical space and noise represented in the fourth dimension.

The geographic space around the exhibition hall is modelled over a volume measuring 200x200x30m with a cell size of 2.5m. By exporting the data to a conventional 3D CAD package the objects in the model can be viewed (Figures 5a,b and c). We have taken the views in figure 5 from approximately the same location as the aerial photograph in figure 4 so that the objects in the representation can be more easily identified.

Figure 5 The tesseral representation of the site objects

We are concerned with the noise levels in the vicinity of block bb6 resulting from heavy goods traffic on the access structure. Since we assume that the vehicles each act as a point source then the sound pressure level at any location is given by the identity :

N= SWL - (20log₁₀R + 8)

(D.O.T. 1988)

In which SWL is the sound power level at the source, N is the sound pressure level (SPL) at a distance R from the source.

In order to calculate the number of cells required in the fourth (noise) dimension we need to calculate the maximum range of SPLs possible in the geographical space. However, sound is measured in dB whereas the units of the geographic space are metres. Converting the units for the range of noise levels which can conceivably be experienced in the model, and setting a lowest threshold of 30dB, gives us a range, in terms of cells, of 50. Thus, the size of the four dimensional space (three geographic dimensions and one sound dimension) is 80x80x12x50; giving an object space of 3 840 000 cells.

A script can then be devised to represent the fixed objects (such as buildings) in the geographic space. This can then be supplemented by a further script to represent a noise object (shapeless) in excess of 30dB. A constraint is applied to fix the location of the sound source on the road.

The SPARTA analysis then produces a noise analysis for the entire geographic space. The resulting sound pressure values at the faces of the critical buildings are shown in Figure 6. Here slices are taken through the buildings at different levels and reveal a worst case of 49dB in cells representing the faces closest to the new access structure.

Figure 6: Sound pressure levels predicted at different levels in the blocks of accommodation close to the new access structure.

 

1280. From here to...?

We believe that the linearisation of space using a tesseral representation offers an efficient route to multidimensional spatial reasoning. In particular it is:

a) Computationally effective

b) Conceptually simple

c) Applicable in any number of dimensions (practically)

d) Compatible with raster representations.

The example that we have illustrated here can be interacted with in up to four dimensions and the results can be output in such a way that they can be turned into graphical representations or visualisations.

However, what is more fundamental is the ability to manipulate the contraints operating in the system so that the effect of the manipulation of objects in the model on noise levels can be investigated efficiently. The technique could be conveniently extended to encompass five dimension, allowing time to be added to the three dimensions of space and one of noise. This would allow traffic flow to be better represented in a noise pollution investigation such as the one described.

With reference again to the specific case of noise pollution we aim to enhance the model by allowing for the effects of screening (barrier attenuation) and reflection. However, even within the limited scope of the problem described we believe that the potential effectiveness of the technique described is well illustrated.

1536. References

1. Bell, S.B.M., Diaz, B.M. Holroyd, F.C. and Jackson, M.J.J. Spatially referenced methods of processing raster and vector data, Image and Vision Computing, 1 (4), pp. 211-220, 1983

2. Coenen, F.P. Beattie, B., Bench-Capon, T.J.M. Shave, M.J.R. and Diaz, B.M. An ontology for linear spatial reasoning, in Database and Expert Systems Applications, Eds. R.R. Wagner and H. Thomas, Proc. DEXA ‘96, Lecture Notes in Computer Science 1134, Springer Verlag, 718-727, 1996a.

3. Coenen, F.P. Beattie, B., Bench-Capon, T.J.M., Diaz, B.M. and Shave, M.J.R. Spatial reasoning fir Geographic information systems, Proc. 1st International Confenece on Geocomputation,, School of Geography, University of Leeds, 121-131, 1996b.

4. Coenen, F.P., Shave, M.J.R., Brown, A.G.P. and Lewis, J. Multi-dimensional tesseral spatial reasoning for noise pollution modeling, Advances in Engineering software, Butterworth Heineman, (forthcoming), 1997.

5. Department of Transport (Welsh Office), Calculation of Road Traffic noise, H.M.S.O., 1988

6. Diaz, B.M. and Bell, S.B.M. Spatial data processing using tesseral methods, publ. Natural Environment Research Council, Swindon, England, 1986

7. Grunbaum, B. and Shephard, G.C., Tilings and Patterns, Freeman, New York, 1987

8. Holdroyd, F.C., The Geometry of Tiling Hierarchies, Ars Combanitoria, Vol 16B, pp211-244, 1983

9. Morton, G.M., A computer oriented geodetic database, and a new technique on file sequencing, IBM Canada Ltd., 1996.

10. Openshaw, S., A spatial analysis research agenda, in Handling Geographical Information, Masser, I. and Blakemore, M. (Eds.), Longman, London, 1991.

11. Samet, H. The Quadtree and related data structures, ACM Comput. Survey, 16, (2), 187-260, 1984.

12. van Hentenryck, P., Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, Mass. U.S.A., 1989.

 

Addresses of Authors:

A.G.P.Brown
School of Architecture and Building Engineering,
The University of Liverpool,
Liverpool L69 3BX
U.K.
Phone: *44 151 794 2611
Fax: *44 151 794 2605
Fax: andygpb@liv.ac.uk

M. Knight
Address as above
Phone: *44 151 794 2618
Fax: *44 151 794 2605
email: mknight@liv.ac.uk