Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T20:36:03.368Z Has data issue: false hasContentIssue false
  • English
  • Français

Spatial synthesis by disjunctive constraint satisfaction

Published online by Cambridge University Press:  27 February 2009

Can A. Baykan  and
Mark S. Fox
Can A. Baykan
Affiliation:
Department of Architecture, Middle East Technical University, 06531 Ankara, Turkey
Mark S. Fox
Affiliation:
Department of Industrial Engineering, University of Toronto, 4 Taddle Creek Road, Toronto, Ontario M5S 1A4
Get access Rights & Permissions [Opens in a new window]

Abstract

The spatial synthesis problem addressed in this paper is the configuration of rectangles in 2D space, where the sides of the rectangles are parallel to an orthogonal coordinate system. Variables are the locations of the edges of the rectangles and their orientations. Algebraic constraints on these variables define a layout and constitute a constraint satisfaction problem. We give a new O(n2) algorithm for incremental path-consistency, which is applied after adding each algebraic constraint. Problem requirements are formulated as spatial relations between the rectangles, for example, adjacency, minimum distance, and nonoverlap. Spatial relations are expressed by Boolean combinations of the algebraic constraints; called disjunctive constraints. Solutions are generated by backtracking search, which selects a disjunctive constraint and instantiates its disjuncts. The selected disjuncts describe an equivalence class of configurations that is a significantly different solution. This method generates the set of significantly different solutions that satisfy all the requirements. The order of instantiating disjunctive constraints is critical for search efficiency. It is determined dynamically at each search state, using functions of heuristic measures called textures. Textures implement fail-first and prune-early strategies. Extensions to the model, that is, 3D configurations, configurations of nonrectangular shapes, constraint relaxation, optimization, and adding new rectangles during search are discussed.

Keywords

Spatial LayoutGeometric ReasoningDisjunctive Constraint Satisfaction
Type
Articles
Information
AI EDAM , Volume 11 , Issue 4 , September 1997 , pp. 245 - 262
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Akin, O., Dave, B., & Pithavadian, S. (1992). Heuristic generation of layouts (HeGeL): Based on a paradigm for problem structuring. Environ. Plann. B 19, 33–59.CrossRefGoogle Scholar
Aggoun, A., & Beldiceanu, N. (1993). Extending Chip in order to solve complex scheduling and placement problems. Math. Computational Modelling 17(7), 57–73.CrossRefGoogle Scholar
Allen, J.F. (1983). Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843.CrossRefGoogle Scholar
Author. (1984). Domestic kitchen design: Conventional planning. Architects J., October, 71–78.Google Scholar
Baybars, I., & Eastman, C.M. (1980). Enumerating architectural arrangements by generating their underlying graphs. Environ. Plann. B 7, 289–310.CrossRefGoogle Scholar
Baykan, C.A. (1991). Formulating spatial layout as a disjunctive constraint satisfaction problem. PhD Thesis. Carnegie Mellon University, Pittsburgh, PA.Google Scholar
Baykan, C.A., & Fox, M.S. (1992). Wright: A constraint based spatial layout system. In Artificial Intelligence in Engineering Design, Volume I (Tong, C. and Sriram, D., Eds.), pp. 395–432. Academic Press, Inc., Boston.Google Scholar
Davis, E. (1987). Constraint propagation with interval labels. AI 32(3), 281–331.Google Scholar
Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. AI 49, 61–95.Google Scholar
Dhar, V., & Ranganathan, N. (1990). Integer programming vs. expert systems: An experimental comparison. Commun. ACM 33(3), 323–336.CrossRefGoogle Scholar
Drake, F., & Pheasant, S. (1984). Domestic kitchen design: The ergonomists view. Architects J., October, 79–80.Google Scholar
Eastman, C.M. (1973). Automated space planning. AI 4, 41–64.Google Scholar
Flemming, U. (1978). Wall representations of rectangular dissections and their use in automated space allocation. Environ. Plann. B 5, 215–232.CrossRefGoogle Scholar
Flemming, U. (1986). On the representation and generation of loosely packed arrangements of rectangles. Environ. Plann. B 13, 189–205.CrossRefGoogle Scholar
Flemming, U., Baykan, C.A., Coyne, R.F., & Fox, M.S. (1992). Hierarchical generate-and-test vs. constraint-directed search: A comparison in the context of layout synthesis. In Artificial Intelligence in Design '92 (Gero, J.S., Ed.), pp. 817–838. Kluwer Academic Publishers, Dordrecht, The Netherlands.Google Scholar
Forbus, K. (1984). Qualitative process theory. AI 24, 85–168.Google Scholar
Fox, M.S. (1987). Constraint-Directed Search: A Case Study of Job-Shop Scheduling. Morgan Kaufmann, Los Angeles.Google Scholar
Fox, M.S., Sadeh, N., & Baykan, C.A. (1989). Constrained heuristic search. Proceedings IJCAI–11, 309–315.Google Scholar
Gulliver, W. (1984). Domestic kitchen design: Specifying built-in furniture. Architects J., October, 91–93.Google Scholar
Haralick, R.M., & Elliott, G.L. (1980). Increasing tree search efficiency for constraint satisfaction problems. AI 14, 263–313.Google Scholar
Jones, R.J., & Kapple, W.H. (1984). Kitchen planning principles—equipment—appliances. Small Homes Council—Building research Council. University of Illinois, Urbana-Champaign.Google Scholar
Liggett, R.S. (1980). The quadratic assignment problem: An analysis of applications and solution strategies. Environ. Plann. B 7, 141–162.CrossRefGoogle Scholar
Mackworth, A.K. (1977). Consistency in networks of relations. AI 8, 99–118.Google Scholar
Mackworth, A.K., & Freuder, E.C. (1985). The complexity of some polynomial network consistent algorithms for constraint satisfaction problems. AI 25, 65–74.Google Scholar
Malik, J., & Binford, T.O. (1983). Reasoning in time and space. Proc. Eighth Int. Conf. Artif. Intell., 343–345.Google Scholar
Miell, C. (1984). Domestic kitchen design: the building regulations. Architects J., October, 95–97.Google Scholar
Mitchell, W.J., Steadman, J.P., & Liggett, R.S. (1976). Synthesis and optimization of small rectangular floor plans. Environ. Plann. B 3, 37–70.CrossRefGoogle Scholar
Mittal, S., & Falkenhainer, B. (1990). Dynamic constraint satisfaction problems. Proc. Eighth Nat. Conf. Artif. Intell., 25–32.Google Scholar
Pfefferkorn, C. (1971). Computer design of equipment layouts using the design problem solver. PhD Thesis. Carnegie Mellon University, Pittsburgh, PA.Google Scholar
Prizeman, J. (1984). Domestic kitchen design: Services. Architects J., October, 99–103.Google Scholar
Purdom, P.W. (1983). Search rearrangement backtracking and polynomial average time. AI 21, 117–133.Google Scholar
Small Homes Council. (1950). Handbook of kitchen design. University of Illinois, Urbana-Champaign. Circular C5.32R.Google Scholar
Smith, B.M., Brailsford, S.C., Hubbard, P.M., & Williams, H.P. (1996). The progressive party problem: Integer linear programming and constraint programming compared. Constraints 1(1), 119–138.CrossRefGoogle Scholar
Stallman, M.R., & Sussman, G.J. (1977). Forward reasoning and dependency directed backtracking in a system for computer-aided circuit analysis. AI 9(2), 135–196.Google Scholar
Waltz, D. (1975). Understanding line drawings of scenes with shadows. In Psychology of Computer Vision (Winston, P.H., Ed.), pp. 19–91. McGraw Hill, New York.Google Scholar