Generating floor plan layouts with K-D tree algorithms and evolutionary strategies
Inhaltsverzeichnis
Reference
Katja Knecht; Reinhard König: Generating floor plan layouts with K-D tree algorithms and evolutionary strategies. In: Generative Art 2010.
DOI
Abstract
K-dimensional trees, abbreviated as k-d trees in the following, are binary search and partitioning trees which represent a set of n points in a multi-dimensional space [1]. K-d tree data structures have primarily been used for nearest neighbor queries and several other query types for example in database applications. [1]
In the context of a research project at the Bauhaus-University Weimar concerned with the development of a creative evolutionary design method for layout problems in architecture and urban design, spatial partitioning with k-d trees has been applied as a partial solution to generate floor plan layouts. Unlike, for example, packing algorithms in [2] and slicing tree structures in [3] the employment of k-d tree algorithms in combination with evolutionary algorithms to generate floor plan layouts has not previously been examined in the scope presented here.
In the application developed in this project the k-d tree algorithm is initially used to subdivide a given rectangular area. The dividing lines thereby correspond to eventual spatial boundaries. By combining the k-d tree algorithm with genetic algorithms and evolutionary strategies, layouts can – in the current version - be optimized in three criteria dimensions (size, ratio and topology). Through user interaction the layouts can be dynamically adjusted and altered in real time. The result is a generative mechanism that provides an interesting and promising alternative to existing well-established algorithms for the creative and evolutionary solution of layout problems in architecture and urban design.
Extended Abstract
Bibtex
Used References
1. Frazer, J., Reptiles. Architectural Design, 1974(April): p. 231-239.
2. Elezkurtaj, T. and G. Franck, Algorithmic Support of Creative Architectural Design. Umbau, 2002. 19: p. 129-37.
3. Bentley, J.L., Multidimensional Binary Search Trees Used for Associative Searching, in Communications of the ACM. 1975, ACM: New York, NY, USA. p. 509 - 517.
4. Bentley, J.L., K-d Trees for Semidynamic Point Sets, in Sixth Annual Symposium on Computational Geometry. 1990, ACM: Berkley, California, United States. p. 187 - 197.
5. Goodrich, M.T. and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples. 2002, New York, United States: John Wiley & Sons
6. Moore, A.W. (1991) An introductory tutorial on kd-trees. Extract from Andrew Moore's PhD Thesis: Efficient Memory-based Learning for Robot Control Technical Report No. 209.
7. Carela-Español, V., et al., K-Dimensional Trees for Continuous Traffic Classification, in Traffic Monitoring and Analysis, F. Ricciato, M. Mellia, and E. Biersack, Editors. 2010, Springer Berlin / Heidelberg. p. 141-154.
8. Deng, K. and A.W. Moore, Multiresolution Instance-Based Learning, in Proceedings of the 14th International Joint Conference on Artificial Intelligence. 1995, Morgan Kaufmann Publishers Inc.: Montreal, Quebec, Canada. p. 1233 - 1239.
9. Moore, A.W., Very Fast EM-based Mixture Model Clustering using Multiresolution kd-trees, in Advances in Neural Information Processing Systems 11, M.S. Kearns, S.A. Solla, and D.A. Cohn, Editors. 1999, MIT Press: Cambridge. p. 543 - 549.
10. Buchanan, A. and A. Fitzgibbon, Interactive Feature Tracking using K-D Trees and Dynamic Programming, in 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2006, IEEE Computer Society. p. 626 - 633.
11. Fussell, D.S. and K.R. Subramanian, Fast Ray Tracing Using K-d Trees, in Technical Report: CS-TR-88-07 1988: Austin, TX, USA.
12. Wald, I. and V. Havran, On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N), in Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. 2006: Salt Lake City, UT, United States. p. 61 - 69.
13. Bentley, J.L. and J.H. Friedman, Data Structures for Range Searching, in ACM Computing Surveys (CSUR). 1979, ACM: New York, NY, USA. p. 397 - 409.
14. Maneewongvatana, S. and D.M. Mount, It's okay to be skinny if your friends are fat, in Center for Geometric Computing 4th Annual Workshop on Computational Geometry. 1999: John Hopkins University
15. Friedman, J.H., J.L. Bentley, and R.A. Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, in ACM Transactions on Mathematical Software (TOMS). 1977, ACM. p. 209 - 226.
16. De Berg, M., et al., Computational Geometry: Algorithms and Applications. 1997, Berlin; Heidelberg; New York; London; Barcelona; Budapest; Hong Kong; Milan; Paris; Santa Clara; Singapore; Tokyo: Springer.
17. Koenig, R. and C. Bauriedel, Computer-generated City Structures, in Generative Art Conference. 2004: Milan.
18. Coates, P., et al., The use of Cellular Automata to explore bottom up architectonic rules, in Eurographics UK Chapter 14th Annual Conference. 1996, Eurographics Association UK: London.
19. Coates, P., T. Broughton, and H. Jackson, Exploring three-dimensional design worlds using Lindenmeyer systems and Genetic Programming, in Evolutionary Design Using Computers, P. Bentley, Editor. 1999, Morgan Kaufmann Publishers Inc.: San Francisco, California. p. 323 - 341.
20. Li, S.-P., J.H. Frazer, and M.-X. Tang. A Constraint-Based Generative System for Floor Layouts. in Fifth Conference on Computer Aided Architectural Design Research in Asia (CAADRIA). 2000. Singapore
21. Arvin, S.A. and D.H. House, Modeling architectural design objectives in physically based space planning. Automation in Construction, 2002. 11: p. 213–225.
22. Duarte, J.P., Customizing mass housing: a discursive grammar for Siza's Malagueira houses, in Faculty of Architecture. 2000, Massachusetts Institute of Technology.
23. Coates, P., et al., Generating architectural spatial configurations. Two approaches using Voronoi tessellations and particle systems, in Proceedings of the VIII Generative Art International Conference (GA2005). 2005: Milan, Italy.
24. Koltsova, A., et al., A Case Study of Script-Based Techniques in Urban Planning, in Design Computing and Cognition DCC’10, J.S. Gero, Editor. 2010, Springer: Stuttgart. p. 671 - 690.
25. Harding, J. and C. Derix, Associative Spatial Networks in Architectural Design: Artificial Cognition of Space using Neural Networks with Spectral Graph Theory, in Design Computing and Cognition DCC’10, J.S. Gero, Editor. 2010, Springer: Stuttgart. p. 305 - 323.
26. Kado, K., An Investigation of Genetic Algorithms for Facility Layout Problems. 1995, University of Edinburgh: Edinburgh.
27. Frazer, J., An Evolutionary Architecture. 1995, London: Architectural Association Publications.
28. Coates, P. and L. Hazarika. The use of genetic programming for applications in the field of spatial composition. in Proceedings of the 2nd Generative Art Conference (GA1999). 1999. Milan: Generative Design Lab Milan Polytechnic University, Italy.
29. Jo, J.H. and J.S. Gero, Space layout planning using an evolutionary approach. Artificial Intelligence in Engineering, 1998. 12: p. 149-162.
30. Schneider, S., J.-R. Fischer, and R. König, Rethinking Automated Layout Design: Developing a Creative Evolutionary Design Method for Layout Problems in Architecture and Urban Design, in Design Computing and Cognition DCC’10, J.S. Gero, Editor. 2010, Springer Verlag: Stuttgart, Germany. p. 367 - 386.
31. Elezkurtaj, T., Evolutionäre Algorithmen zur Unterstützung des kreativen architektonischen Entwerfens, in Institut für Architekturwissenschaften. 2004, Technische Universität Wien: Vienna, Austria.
32. Von Buelow, P., Using Evolutionary Algorithms to Aid Designers of Architectural Structures, in Creative Evolutionary Systems, P.J. Bentley and D.W. Corne, Editors. 2001, Morgan Kaufmann Publishers: San Francisco, CA, USA. p. 315 - 336.
Links
Full Text
http://www.generativeart.com/on/cic/GA2010/2010_18.pdf
