A Survey Of Computational Approaches To Space Layout Planning

Computational Approaches to Space Layout Planning

Hoda Homayouni

A Survey of Computational Approaches to Space Layout Planning (1965-2000) Hoda Homayouni Department of Architecture and Urban Planning University of Washington

1. Introduction Space layout planning is one of the most important and complex parts of any architectural design process. In order to design a building that responds to most of its related requirements, an architect (or architectural team) should spend much time and effort on studying the specific situations of the building and all the relationships that should exist within the building rooms and between the interior and exterior spaces. Beside the artistic aspect of architectural design that occurs in almost all parts of the design process, there is a substantial logical process behind the space layout planning phase. Architects cannot avoid having numbers of trial and error approach to pass that step. The combinatorial complexity of most floor plan design problems also makes it practically impossible to obtain a systematic knowledge of possible solutions using pencil and paper. Therefore, computers would seem to be a very helpful device to provide architects with a set of possible optimized solutions to the interlocking problems that exist in this part of design. Many architects and computer scientists have tried to create a program that could come up with the optimum solution for different constraints and objectives that exist in architectural design process. In 1965 Thomas Anderson, a student in civil engineering at the University of Washington, for the first time, wrote a program called SLAP1. This program locates activities in relation to one another in order to minimize the total cost of circulation between two activities. After that many other students and scientists tried to address this problem by producing different algorithm with different logics behind them. Before categorizing the different logical structures and consequently different programs that are presented and studied so far, it is worth mentioning that all of these different approaches begin by propounding numerical definitions for all the constraints existing in the design situation. There are basically two types of constraints that express the design objective requirements:

1

Computational Approaches to Space Layout Planning

Hoda Homayouni

 Dimensional constraints (geometrical constraints): constraints that are considered over one place, i.e. constraints on surface, length or width, or space orientation.  Topological constraints: constraints that are considered over a couple of spaces, i.e. adjacency between the rooms, adjacency to perimeter of the building, nonadjacencies or proximities. The numerical criteria that topologically define arrangements usually come from site analysis questions and user need questions.

1.1 Automated Space Planning Characteristics and Solution Approaches Architectural space layout problems tend to be ill-defined (Yoon, 1992) and over-constrained. Problems that are not well defined are ill-defined (Simon, 1973), in that the initial constraints on the problem are not fully formulated. Resolving ill-defined problems is a process of searching for and refining a set of design constraints. Problems that are over-constrained have no single best solution and thus have too many possible solutions (Balachandran and Gero, 1987). Automated space planning systems need a method of providing a good solution from a large set of possible solutions, and a method of allowing the designer to modify the set of design constraints to continually refine the problem definition (Arvin and House, 2000). However Tsang et al have shown that there does not appear to be a universally best algorithm and that certain algorithms may be preferred under certain circumstances (Tsang et al, 1995). Therefore, in this part a general categorization from the studied solution approaches is presented while more specification and details will be presented in section 2. 1.1.1 Categorizing the Solution Approaches As mentioned earlier, various approaches have been presented toward the computerized space layout planning objective. But for the sake of simplicity we generally categorize these different approaches to some main parts according to Galle’s divisions (Galle, 1981). Obviously each part could contain some subcategories whit different ideas and details. There are also some approaches that take benefit of the two types or more together, in a different phases of computation. 1. On-line machine control and appraisal of the designer’s layout proposals. 2. Stepwise automatic layout generation interactively guided by manual selection of desirable partial solutions. 3. Nonexhaustive automatic generation satisfying given constraints. 4. Exhaustive automatic generation satisfying given constraints. 5. Automatic generation of optimal or quasi optimal layouts under given constraints. Approach no. 1 has been advocated primarily by Maver (Maver, 1970) who argues that human creativity is superior to that of machines in solving real –world problems. This approach is prominently represented by Th’ng and Davies (Th’ng and 2

Computational Approaches to Space Layout Planning

Hoda Homayouni

Davies, 1975) whose ideas have been taken up by Gentles and Gardner (Gentles and Gardner, 1978). Although Cross (Cross, 1977) produces some counterevidence, appraisal programs enable the designer to increase the number of solutions considered. A tenfold increase has been experienced (Mayer, 1979). But the solutions are still generated intuitively and the element of randomness in traditional planning remains in the decisionmaking. Approach no.2 was suggested in graph-theoretical terms by Korf (Korf, 1977) and developed by Ruch (Ruch, 1978) for generation of planlike bubble diagrams. Such methods are likely to produce more solutions than methods of the first type but design becomes no more systematic than the designer’s behavior. Approach no.3 is represented by Weinzapfel and Handel (Weinzapfel and Handel, 1975), Pfefferkorn (Pfefferkorn, 1975), and Willey (Willey, 1978). Eastman illustrated the use of his General Space Planner (Eastman, 1971) by procedures also belonging to this class of purely heuristic methods. Approach no.4 was introduced by Grason (Grason, 1968) who generated plans as dimensionally feasible embeddings of the duals1 of graphs representing at least the required adjacencies (edges) between rooms (vertices). According to Steadman (Steadman 1976), Grason’s program fails for problems of more than five rooms. After that, Mitchell, Steadman, and Liggett (Mitchell et al, 1976) implemented an exhaustive method for solving problems stated in terms of dimensional and adjacency requirements. It includes, however, a final optimization step. To solve an n-room problem, their program searches a permanent library of topologically distinct “dissections”, i.e., tight rectangular packings of n nonoverlapping rectangles with unspecified dimensions. For each dissection matching the adjacency requirements, combinations of wall dimensions are searched so as to minimize, e.g., construction costs. Earl (Earl, 1977) has shown that the algorithm which generated the library is not exhaustive for n>=16 and the optimization method has been criticized by Gero (Gero, 1977). Later, Bloch (Bloch, 1978), Krishnamurti and Row (Krishnamurti and Row, 1978), efficiently generated all dissections with n<=10, and Stiny’s “shape grammars” (Stiny, 1976) demonstrated their usefulness for such and other generating tasks. The twostep procedure yields a valuable classification of the solutions according to their topology. However, the size of the problem independent library limited the computationally feasible values of n to at most 8.

1

In mathematics, a dual graph of a given planar graph G has a vertex for each plane region of G, and an edge for each edge joining two neighboring regions. The term "dual" is used because this property is symmetric, meaning that if G is a dual of H, then H is a dual of G; in effect, these graphs come in pairs.

3

Computational Approaches to Space Layout Planning

Hoda Homayouni

Flemming (Flemming, 1978) describes another implemented two-step method which also satisfies adjacency and dimensional constraints. It combines exhaustive search for certain topologically distinct equivalence classes of solutions with a linear programming algorithm searching each class for an optimal representative. The linear constraints include derived class-specific dimensional constraints ensuring required adjacencies, and linear approximations of the user’s area constraints. Flemming presents a realistic design example with nine rooms: Eight requirements had the form “A must be adjacent to B or C”, but such alternatives cannot be managed by the program. Therefore four of the subproblems defined by the possible choices among alternative adjacencies were selected as test problems. To limit the solution set further, six “plausible” adjacency constraints were added to the first of these problems, and eight constraints were added to the other three problems. Approach no.5 is closely related to the field of operational research. For Example, Armour and Buffa (Armour and Buffa, 1963), Whitehead and Eldars (Whitehead and Eldars, 1964), Gavett and Plyter (Gavett and Plyter, 1966), Seehof et al. (Seehof et al, 1966) described various methods for generating a schematic layout minimizing internal traffic while Krejcirik (Krejcirik, 1969) also considered area minimization. Brotchie and Linzey (Brotchie and Linzey, 1971) developed a comprehensive cost-benefit model including “flows” of persons, heat, loads, etc. Some of these early techniques were later elaborated and supplemented by Cinar (Cinar, 1975), Willoughby et al. (Willoughby et al, 1970), Portlock and whitehead (Portlock and whitehead, 1971), Gawad and Whitehead (Gawad and Whitehead, 1976), Sharpe (Sharpe, 1973), and Hiller et al. (Hiller et al, 1976), among many others. Dudnik (Dudnik, 1973) and Krarup and Pruzan (Krarup and Pruzan, 1973) discuss optimal architectural space allocation and reach divergent conclusions. Unless the highly controversial notions of numerical utility of imponderables and numerical weighting of incommensurable desiderata are applied, it is impossible to express all relevant qualities of a floor plan as an objective function. The measurement technique of Kalay and Shaviv (Kalay and Shaviv, 1979) is an interesting attempt to capture the qualitative aspects of dwelling plans numerically. Radford and Gero (Radford and Gero, 1980) recommend enumeration of solutions which are Pareto-optimal with respect to several criteria. This method allows for incommensurable desiderata but like automated optimization in general, it is faced with the dilemma of architectural optimization: Either quantify what should not be quantified or ignore what should not be ignored: the intangible values of architecture.

2 Annotated Bibliographies In this section brief summaries of different programs that have been presented in the field of space layout planning automation are presented.

4

Computational Approaches to Space Layout Planning

2.1 Some Computer-aided (Schnarsky, 1971)

Hoda Homayouni

Approaches

to

Housing

In this paper two different ideas and consequently two whole different computerized systems have presented. The first system begins with filling out a detailed questionnaire and ends with a robotic factory producing the unique, responsive house. The major portion of this paper deals with an explanation of possible techniques used to accomplish this system. The various techniques can be combined to form house design generating systems: TECHNIQUE 1- SYSTEMATIC COMBINATION: Using the user questionnaire information, the system will select the size and shape of each part from a predetermined array of parts. How each part relates to the next can be defined by such physical limitations as jointery, structure, life systems, and most important circulation. Working within the rules of assemblage all of the combinations can be generated. Figure 1 and Figure 2 illustrates the steps of this process as it might apply to three parts of a house.

Figure 1. Parts A, B, C are selected from an array of predetermined parts

Figure 2. Implicit in these parts are rules for assemblage

5

Computational Approaches to Space Layout Planning

Hoda Homayouni

TECHNIQUE 2- TOPOLOGICAL PLACEMENT: This technique says that different parts of the house should be placed based upon topological objectives. To solve the internal arrangement problem a technique known as hierarchical decomposition can be used. This takes the random list of elements and interactions extracted from the questionnaires and finds the optimal clusters. TECHNIQUE 3- EVALUATION OF ALTERNATIVES: As the many combinations are generated, each can be evaluated. The highest scoring solutions represent those that best meet the needs of the user. TECHNIQUE 4- WHEN YOU CANNOT MAKE A DECISION, GUESS! Random number techniques allow the computer to make irrational decisions. TECHNIQUE 5- LAY DOWN THE IMPORTANT PARTS FIRST: This technique provides a strategy which grows a plan beginning with the most critical part and adding less important ones based upon the next highest relationship to what has already been located. TECHNIQUE 6- CANNED EXPERTISE: It is possible to instruct the generating program to emulate basic planning laws that apply to any user’s requirement. This can be done by pre-solving the arrangements of all the manufactured modules at the subsystem level. TECHNIQUE 7- GENERIC SOLUTIONS: This would generate all of the possible combinations of manufactured parts once. TECHNIQUE 8- LET THE USER TRY HIS HAND: Now set the user down to an interactive graphic display tube and let him try to combine his parts. After each move by the user, the program evaluates the current arrangement and offers criticism, cost, and encouragement. After explanation about ways to get computers to design responsive houses, another concept that almost negates the need to develop the option 1 system has been presented in this paper. The idea is houses from a kit of parts. Here the user buys his house in parts and puts it together himself. As Kenneth Allinson (Allinson, 1970) has points out, a house of modules could exist that modules are added and removed as performance demands vary. One may even pay for it by credit card or return it like bottles. This option also presents the problem of conflict and infringements on the rights of others.

2.2 An Approach to Computerized Space Planning Using Graph Theory (Grason, 1971) This paper treats computerized space planning by discussing methods for the solution of a formal class of floor plan design problems. These methods have been implemented in an experimental computer program called GRAMPA (stands for GRAph

6

Computational Approaches to Space Layout Planning

Hoda Homayouni

Manipulating PAckage). The methods of solution depend on a special linear graph representation for floor plans called the dual graph representation. As shown in Figure 3 a “space” is defined to be either a room or one of the four outside spaces. A problem statement will consist of a set of adjacency and physical dimension requirements that have to be satisfied, and a problem solution is a floor plan that satisfies all of the design requirements.

Figure 3. A typical floor plan

In this approach, in applying graph theory to floor plan layout, rooms are pictured as labeled nodes possessing certain attributes, such as intended use, area, and shape. Adjacencies between rooms are indicated by drawing lines (edges) connecting the nodes representing those rooms. These notions can be implemented by dealing with the dual graph of a floor plan which is itself treated as a linear graph. An example of such a floor plan graph is shown in Figure 4, with black nodes. In the floor plan graph, “edges” and “nodes” will be called “wall segments” and “corners” respectively. This special type of dual graph of the floor plan is the design representation to be used for the class of problems described in this paper. The general idea of its application is to first set down the four nodes and four edges of the dual graph that represent the four outside walls of a building. Then nodes and edges are added one by one to the dual graph in response to design requirements and other considerations until a completed dual graph is obtained. The incomplete dual graphs that are produced in the intermediate stages of this design process present special problems. Since edges can be colored, directed, and weighted, it is not always clear whether or not there exists at least one physically realizable floor plan satisfying the relationships expressed in the incomplete dual graph. To treat this problem, appropriate properties of the dual graph representation have been developed and are presented in this paper, but there is not sufficient space here to describe these methods.

7

Computational Approaches to Space Layout Planning

Hoda Homayouni

Figure 4. Floor plan graph with dual graph

In addition to simply storing the structural description of the dual graph, the computer data representation must be configured in such a way that it is easy to determine whether the graph is planar or not. It must also be easy to generate the various possible geometric realizations of the dual graph. A geometric realization of a planar graph is simply one of the possibly many ways in which it can be drawn in a plane. Four different realizations of a particular planar graph are shown in Figure 5.

Figure 5. Four planar realizations of a graph

8

Computational Approaches to Space Layout Planning

Hoda Homayouni

Since in a partially completed dual graph each planar realization corresponds to a topologically different set of floor plans it is important to be able to generate realizations with great facility. To deal with the problems mentioned above, a special graphical grammar called the planar graph grammar (PGG) was developed. The general intent of this grammar is to divide a graph into a set of hierarchically organized subgraphs. Each of these subgraphs can be treated as a separate entity, and if it is connected to the rest of the graph, it is by at most two nodes. These subgraphs are free to rotate about these nodes to create the various realizations of the graph. Other such “degrees of freedom” in creating realizations are also possible. The grammar allows one to deal with planarity in an inductive manner. That is, given a graph that is planar and described in terms of the planar graph grammar, if a new edge is to be added to that graph a test can be developed to tell whether the resultant graph will also be planer. This test assumes that each of the special subgraphs is already planar. It then checks to see if the proposed edge can be connected to the two endpoints without crossing an edge of one of these subgraphs. This method is extremely fast, and its computation time increases only linearly with the size of the graph considered. The computation time for other methods generally increases more than linearly with the size of the graph. At the next level, the program has two jobs to accomplish: (1) It must satisfy the physical dimension requirements. It does this by selecting nodes on the boundary of the region in question and assigning dimensions to them from the design requirement list. (2) It must “fill” the region with edges representing those adjacencies not specifically requested by the design requirements. Here the program does an exhaustive search of all possible design solutions.

2.3 Modeling Architectural Design Objectives in Physically Based Space Planning (Arvin et. al, 2000) In the physically based space planning program, the designer creates a space plan by specifying and modifying graphic design objectives rather than by directly manipulating primitive geometry. The plan adapts to the changing state of objectives by applying the physics of motion to its elements. In fact, in this approach, the architect defines programmatic objectives in the usual manner, and these objectives are then modeled as physical objects and forces used in a dynamic physical simulation. The spaces and walls are modeled as point masses, with adjacencies between spaces that are modeled as springs connecting the masses. Objectives specified in the architectural program are translated into forces applied to the masses. In the first phase the topological objectives apply forces to the center of a space. For collision detection, in this step boundary shapes are treated as circles so spaces are

9

Computational Approaches to Space Layout Planning

Hoda Homayouni

able to slide around each other. The dynamic simulation starts to run until the system is in equilibrium, which is defined as the point in time when the magnitudes of all velocities are below a small threshold. At the second phase topological objectives are turned off and geometric objectives apply forces to the polygonal edges of space boundaries. Also space boundaries are switched from a circular to a polygonal representation in this phase. Collision detection and response then act to keep spaces from overlapping, resulting in an arrangement that is very close to a recognizable building floor plan. Once a geometric simulation has reached equilibrium, the designer can begin to analyze and interact with the design by directly manipulating the graphic model rather than by respecifying design objectives in the language of the underlying system. The mass-spring representation allows the graphic model to adapt to those changes immediately. The intention here is not simulating the actual behavior of building elements, but simulating the way architects may view and interact with design elements during their conception. Sample pictures for the process are shown in Figure 6.

Figure 6. Sample results

10

Computational Approaches to Space Layout Planning

Hoda Homayouni

2.4 Dynamic Space Ordering at a Topological Level in Space Planning (Medjdoub et. al, 2000) This approach and its implementation within ARCHiPLAN prototype is based on a constraint programming approach which importantly avoids the inherent combinatorial complexity for middle size space layout problems. In fact, this is a complementary approach to Schwarz et al (Schwarz et al. 1996) that is based on a graphtheoretical model. In this approach the topological level is a part of the computation process, but the evaluation of the solutions is done at the geometrical level. It is restricted to the small size problems (does not exceed nine rooms) and the shape contour of the building is a result of the design process. This allows architects to be the actors of the design at the topological level when choosing between feasible sketches and composing interactively an objective function for finding the best corresponding geometrical solutions. Here, two constraint groups are defined in an extensible library: (1) specification constraints; (2) research space reduction constraints. Specification constraints regroup dimensional and topological constraints. They are applied by the user and stored in a functional diagram. These constraints are introduced into ARCHiPLAN interactively by graph handling and incremental construction. Then adjacency and non-overlapping check applied between all pairs of spaces. Of course, pairs of rooms which are already constrained to be adjacent verify the non-overlapping constraint. Figure 7 shows permissible positions for e2x2 and e2 y2 (e2y2 represents the constrained variable y2 of space e2) by the non-overlapping constraint between spaces e1 and e2. This constraint is dependent on the minimal space dimension notion.

Figure 7. Permissible position for (e2.x2, e2y2) after non-overlapping constraint with e1. The partitioning of the surroundings of a space in {E,W,N,S} is given.

Research space reduction constraints allow the combinatorial reduction. They regroup the incoherent space elimination constraint, the symmetry constraint, the topological reduction constraint and the propagation orientation constraint.

11

Computational Approaches to Space Layout Planning

Hoda Homayouni

Also, a particular dynamic variable ordering (dvo) heuristic, named dso (dynamic space ordering) is developed based on the most constrained space position. Comparatively to the dvo heuristics, the dso heuristic is based on the space ordering and particularly on the space reference points. To implement this heuristic, a new attribute in space class called degree of constraint dg-cont has introduced. The more the space is constrained, the higher the dg-cont value is and the more the non-overlapping and adjacency variables corresponding to this space have a chance to be instantiated first. The initial value of dg-cont is calculated from the adjacency constraints with the building unit. If two spaces have an equal dg-cont value, the space with the highest average surface area is chosen and if it is not sufficient to distinguish this space, the first in the list is chosen. After the detection of the most constrained space with the building unit, its corresponding adjacency variables with the building unit are instantiated. After each space choice, one updates dynamically the dg-cont values of the remaining spaces. The process runs until all topological variables are instantiated but a backtracking is performed as soon as an inconsistency is detected. At this point the graphic representation of a topological solution is generated which reveals slight overlapping of rectangles in the same way as a sketch.

Figure 8. Some topological solutions of the house with two floors.

12

Computational Approaches to Space Layout Planning

Hoda Homayouni

The optimization stage consists of minimizing an objective function, called cost function. The “Branch and Bound” optimization method leads to the determination of the global optimum of a geometrical solution. This is not the case with expert systems approaches (Damski et. al., 1997) or evolutionary approaches (Jo et. al., 1998) which lead to “satisfactory solutions”. The objective functions minimize the wall length or the corridor surface area. Thus one of the major objectives that remains is to carry out multi-criteria optimization. The optimal geometrical solution of each topological solution is displayed in a collector of geometrical solutions. The most important function of this collector is to realize a classification of the topological solutions from the minimal objective function value of the geometrical solutions related to each topology. It can be noted that several geometrical solutions can correspond to the same optimum. In that case, they are all enumerated.

Figure 9. Some optimal geometrical solutions of the house with two floors.

13

Computational Approaches to Space Layout Planning

Hoda Homayouni

3 Conclusion Several results could be inferred from reviewing computational approaches to space layout planning at the first glance: 1. There is a demand for more comprehensive software to simplify the design process. 2. Different techniques and methods are presented in this field where each has focused on different areas of space layout planning and optimization. 3. Most of these approaches have stopped in the research stage and are not evolved into the marketing stage. To get to the point, one of the reasons that these programs are not applicable in the marketing stage is their excessive runtime. On one hand, the runtime of these programs increases exponentially by increasing the objectives so that the program can not handle calculating complexities. On the other hand, the best application of such programs could be the complex projects. In fact, architects usually have enough experience and knowledge to solve the design objectives in small projects that they do not need to use additional helping software. Furthermore, architects are capable to consider aesthetic aspects of design while this job is not easy for programmers. Future work would involve finding the best program among the presented methods which its runtime could become close to a linear function of the number of objectives. Also, according to the limitations that exist in using different forms for different spaces, the chosen program should be able to present solutions at the end of topological stage. This will let the architect to use his tact and aesthetic aspects in the design. In fact, an imaginable near future for these approaches, is the situation that the software could help the architect in the design process especially in analyzing and optimizing tasks. It is important to highlight that the software should be an assistant to the architect and not the opposite.

4 References Allinson,A.D. Credit Card Dwellings. November 1970, Daeha pub., London. Armour, G. C., and Buffa, E. S. A heuristic algorithm and simulation approach to relative location of facilities. Management Sci. 9, 2 (Jan. 1963), 294-309. Arvin, S. A., and House, D. H. (2000). Modeling Architectural Design Objectives in Physically Based Space Planning.

14

Computational Approaches to Space Layout Planning

Hoda Homayouni

Balachandran, M. and Gero, J. S. (1987). Dimensioning of architectural floor plans under conflicting objectives. Environment and Planning B (14), 29-37. Bloch, C. J., and Krishnamurti, R. The counting of rectangular dissections. Environment and Planning B 5, 2 (Dec. 1978), 207-214. Brotchie, J. E., and Linzey, M. P. T. A model for integrated building design. Building Sci. 6, 3 (Sept. 1971), 89-96. Cinar, U. Facilities planning: A systems analysis and space allocation approach. In Spatial Synthesis in Computer-Aided Building Design. C. M. Eastman, (Ed.) Applied Science Publishers Ltd. London (1975), 19-40. Cross, N. The Automated Architect. Pion Ltd. London (1977), 85-101. Damski JC, Gero JS. An evolutionary approach to generating constraint-based space layout topologies. In: Junge R, editor. CAAD future, Dordrecht: Kluwer (1997), p. 855-74. Dudnik, E. E. An evaluation of space planning methodologies. In Environmental Design Research. Vol. 1, Selected Papers, 4th Int. EDRA Conf., W. F. E. Preiser, (Ed.), Dowden, Hutchinson & Ross, Inc., Stroudsburgh (1973), 414--427. Earl, C. F. A note on the generation of rectangular dissections. Environment and Planning B 4, 2 (Dec. 1977), 241-246. Eastman, C. M. Heuristic algorithms for automated space planning. 2nd Int. Joint Conf. on Artificial Intelligence. British Computer Society (1971), 27-39. Flemming, U. Wall representations of rectangular dissections and their use in automated space allocation. Environment and Planning B 5, 2 (Dec. 1978), 215-232. Galle, p. An algorithm for exhaustive generation of building floor plans. Nordisk Kollegium, Denmark. (Dec. 1981) Gavett, J. W., and Plyter, N. V. The optimal assignment of facilities to locations by branch and bound. Operations Res. 14, 2 (Mar.-Apr. 1966), 210-232. Gawad, M. T., and Whitehead, B. Addition of communication paths to diagrammatic layouts. Building and Environment 11, 4 (Dec. 1976), 249-258. Grason, J. An Approach to Computerized Space Planning Using Graph Theory, (1971), Carnegie-Mellon University. Jo JH, Gero JS. Space layout planning using an evolutionary approach. Artif Intell Engng (1998), 12:149-62.

15

Computational Approaches to Space Layout Planning

Hoda Homayouni

Kalay, Y. and Shaviv, E. A method for evaluating activities layout in dwelling units. Building and Environment 14, 4 (Dec. 1979), 227-234. Hiller, M., Kolbe, O., Bayer, W., and Ruhrman, I. Heuristic solution of general allocation problems in administration and regional planning. Bulletin of Computer Aided Architectural Design 20 (May 1976), 30-36. Korf, R. E. A shape independent theory of space allocation. Environment and Planning B 4, 1 (Jun. 1977), 37-50. Krarup, J. and Pruzan, P. M. Computer-aided layout design. Mathematical Programming Study 9 (Jul. 1978), 75-94. Krejcirik, M. Computer-aided plant layout. Computer Aided Design 2, 1 (Autumn 1969), 7-19. Krishnamurti, R. and Roe, P. H. O'N. Algorithmic aspects of plan generation and enumeration. Environment and Planning B 5, 2 (Dec. 1978), 157-177. Gentles, J., and Gardner, W. BILD--building integrated layout design. A BA C US Occasional Paper No. 64. University of Strathclyde, Glasgow, Scotland (1978), 12 p. Gero, J. S. Note on "Synthesis and optimization of small rectangular floor plans" of Mitchell, Steadman, and Liggett. Environment and Planning B 4, 1 (Jun. 1977), 81-88. Grason, J. A dual linear graph representation for space-filling location problems of the floor plan type. In Emerging Methods in Environmental Design and Planning. G. T. Moore, (Ed.) Proc. of The Design Methods Group, 1st Int. Conf., Cambridge, MA. (1968), 170- 178. Maver, T. W. A theory of architectural design in which the role of the computer is identified. Building Science 4, 4 (Mar. 1970), 199- 207. Mayer, T. W. Models and techniques in design. Design Methods and Theories 13, 3/4 (Jul. /Dec. 1979), 173-177. Medjdoub, B, Yannou, B. Dynamic Space Ordering at a Topological Level in Space Planning, (2000), University of Cambridge. Mitchell, W. J., Steadman, J. P., and Liggett, R. S. Synthesis and optimization of small rectangular floor plans. Environment and Planning B 3, 1 (Jun. 1976), 37-70. Nigel Cross, The Automated Architect, Viking Penguin (1977). Charles E. Pfefferkorn, A heuristic problem solving design system for equipment or furniture layouts, Communications of the ACM, v.18 n.5, p.286-297 (May 1975).

16

Computational Approaches to Space Layout Planning

Hoda Homayouni

Portlock, P. C. and Whitehead, B. Provision for daylight in layout planning. Building Science 8, 3 (Sept. 1973), 243-249. Radford, A. D. and Gero, J. S. On optimization in computer aided architectural design. Building and Environment 15, 2 (Jun. 1980), 73-80. Julia Ruch, Interactive space layout: A graph theoretical approach, Proceedings of the no 15 design automation conference on Design automation, p.152-157 (June 19-21, 1978), Las Vegas, Nevada, United States Jerrold M. Seehof , Wayne O. Evans , James W. Friederichs , James J. Quigley, Automated facilities Layout Programs, Proceedings of the 1966 21st national conference, p.191-199 (January 1966). Schnarsky, A. Some Computer-aided Approaches to Housing (1971), University of Wisconsin- Milwaukee. Sharpe, R. Optimum space allocation within buildings. Building Science 8, 3 (Sept. 1973), 201-205. Simon, H.A. (1973), The structure of ill-structured problems. Artificial Intelligence (4), 215-229. Steadman, P. Graph-theoretic representation of architectural arrangement. In The Architecture of Form. L. March, (Ed.) Cambridge Univ. Press. London, New York, Melbourne (1976), 94- 115. Stiny, G. Two exercises in formal composition. Environment and Planning B 3, 2 (Dec. 1976), 187-210 Th'ng, R. and Davies, M. SPACES: an integrated suite of computer programs for accommodation scheduling, layout generation and appraisal of schools. Computer Aided Design 7, 2 (Apr. 1975), 112-118. Tsang EPK, Borrett JE, Kwan ACM. An attempt to map the performance of a range of algorithm and heuristic combinations. Hybrid problems, hybrid solutions. In Proceedings of AISB. IOS Press (1995). p. 203-16 Weinzapfel, G. and Handel, S. IMAGE: computer assistant for architectural design. In Spatial Synthesis in Computer-Aided Building Design. C. M. Eastman, (Ed.) Applied Science Publishers Ltd. London (1975), 61-97. Whitehead, B., and Eldars, M. Z. An approach to the optimum layout of singlestorey buildings. The Architects" Journal (17 June), 1964, 1373-1380. Willey, D. S. Structure for automated architectural sketch design. Computer Aided Design 10, 5 (Sept. 1978), 307-312.

17

Computational Approaches to Space Layout Planning

Hoda Homayouni

Willoughby, T., Paterson, W., and Drummond, G. Computer aided architectural planning. Operational Research Quarterly 21, 1 (1970), 91-98. Yoon, K.B. (1992). A Constraint Model of Space Planning. Southampton, UK: Computational Mechanics Publications.

18