Enumeration of Floor Plans Based on a Zero-Suppressed Binary Decision Diagram

Abstract

This paper presents novel algorithms for enumerating architectural floor plans. The enumeration approach attempts to generate all feasible solutions that satisfy given constraints. Therefore, such a method might usefully reveal the potential diversity of Open Building floor plans. However, combinatorial enumeration solutions easily explode even for small problem sizes. We represent a space by a set of cells and organize some cells into polyomino-like configurations. We then enumerate all cell combinations that can be tiled in the given space using an efficient search algorithm for combinatorial problems. We also propose queries for extracting specific floor plans that satisfy additional constraints from all enumerated floor plans without re-enumeration. Our approach solves a 56-cell configuration space within a realistic timeframe.

Get full access to this article

View all access options for this article.

References

Gero

J. S.

ed., Design Optimization (Notes and Reports in Mathematics in Science and Engineering), Academic Press, New York, 1985.

Mitchell

W. J.

Steadman

J. P.

, and Liggett

R. S.

, Synthesis and optimization of small rectangular floor plans, Environment and Planning B, 1976, 3(1), 37–70.

March

, and Earl

C. F.

, On counting architectural plans, Environment and Planning B, 1977, 4(1), 57–80.

Gero

J. S.

, Note on “Synthesis and optimization of small rectangular floor plans” of Mitchell, Steadman, and Liggett, Environment and Planning B, 1977, 4(1), 81–88.

Earl

C. F.

, A note on the generation of rectangular dissections, Environment and Planning B, 1977, 4(2), 241–246.

Krishnamurti

, and Roe

P. H. O.

, Algorithmic aspects of plan generation and enumeration, Environment and Planning B, 1978, 5(2), 157–177.

Flemming

, Wall representations of rectangular dissections and their use in automated space allocation, Environment and Planning B, 1978, 5(2), 215–232.

Flemming

, Wall representations of rectangular dissections: Additional results, Environment and Planning B, 1980, 7(3), 247–251.

Baybars

, and Eastman

C. M.

, Enumerating architectural arrangements by generating their underlying graphs, Environment and Planning B, 1980, 7(3), 289–310.

10.

Earl

C. F.

, Rectangular shapes, Environment and Planning B, 1980, 7(3), 311–342.

11.

Habraken

N. J.

, Supports: An Alternative to Mass Housing, Praeger, New York, 1972.

12.

Doi

Takada

Yasueda

and Kamo

, The Role of Fixed Infill When Installing and Changing Variable Infill – Through the experiments in “Infill Laboratory Glass Cube” located in NEXT21-, Jo urnal of Architecture and Planning, 2013, 683(78), 11–18.

13.

Saitoh

Kawahara

Yoshinaka

Suzuki

and Minato

, Path Enumeration Algorithms Using ZDD and Their Performance Evaluations, IPSJ SIG Notes, 2011, 2011-AL-134(17), 1–6.

14.

Minato

, Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems: Proceedings of the 30th International Design Automation Conference, Dallas, 1993, 272–277.

15.

Avis

and Fukuda

, Reverse Search for Enumeration, Discrete Applied Math, 1996, 6, 21–46.

16.

Golomb

S. W.

, Polyominoes: Puzzles, Patterns, Problems, and Packings, Revised and Expanded Second edition, Princeton University Press, 1996

17.

Nakano

, Enumerating Floorplans with n Rooms, IEICE transactions on fundamentals of electronics, communications and computer sciences, 2002, E85- A(7), 1746–1750.

18.

Bryant

R. E.

, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, 1986, C-35(8), 677–691.

19.

Inoue

Iwashita

Kawahara

, and Minato

, Graphillion: Software library for very large sets of labeled graphs, International Journal on Software Tools for Technology Transfer, 2014, 1–10.

20.

Heitor

T. V.

Duarte

J. P.

Pinto

R. M.

, Combing Grammars and Space Syntax: Formulating, Generating and Evaluating Designs, International Journal of Architectural Computing, 2004, 2(4), 492–515.

21.

Takizawa

Takechi

Ohta

Katoh

Inoue

Horiyama

Kawahara

, and Minato

, Enumeration of Region Partitioning for Evacuation Planning Based on ZDD, ISO RA, 2013, 64–71.