Spatial synthesis by disjunctive constraint satisfaction

Download

index.pdf

Date

1997-09-01

Author

Baykan, CA
Fox, MS

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

151
views

0
downloads

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(n(2)) 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.

Subject Keywords

Industrial and Manufacturing Engineering, Artificial Intelligence

URI

https://hdl.handle.net/11511/66175

Journal

AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING

DOI

https://doi.org/10.1017/s0890060400003206

Collections

Department of Architecture, Article

Suggestions

OpenMETU
Core

LinGraph: a graph-based automated planner for concurrent task planning based on linear logic Kortik, Sitar; Saranlı, Uluç (Springer Science and Business Media LLC, 2017-10-01) In this paper, we introduce an automated planner for deterministic, concurrent domains, formulated as a graph-based theorem prover for a propositional fragment of intuitionistic linear logic, relying on the previously established connection between intuitionistic linear logic and planning problems. The new graph-based theorem prover we introduce improves planning performance by reducing proof permutations that are irrelevant to planning problems particularly in the presence of large numbers of objects and a...
Relative consistency of projective reconstructions obtained from the same image pair Otlu, Burcak; Atalay, Mustafa Ümit; Hassanpour, Reza (World Scientific Pub Co Pte Lt, 2006-08-01) This study obtains projective reconstructions of an object or a scene from its image pair and measures relative consistency of these projective reconstructions. 3D points are estimated from an image pair using projective and epipolar geometry. Two measures are presented for verification of projective reconstructions with each other. These measures are based on the equality of ratios between the x-, y- and z-coordinates of 3D reconstructed points which are obtained from the same corresponding points. This in...
An approach to two-dimensional cutting stock problems Dağlı, Cihan H.; Tatoğlu, Yalçın (Informa UK Limited, 1987-2) One of the resource utilization problems is the location of two-dimensional patterns onto stock sheets with finite dimensions. Stock sheets, in this respect, are depletable resources to be used and the remaining material which is known as the scrap (or trim loss) cannot usually be used later for allocating patterns. Thus, a decrease in the amount of scrap yields a decrease in the raw material cost. In the solution of the problem, usually templates of the patterns to be cut are placed on a stock sheet and th...
Linear and nonlinear intersubband optical absorptions in an asymmetric rectangular quantum well Karabulut, I.; Atav, U.; Safak, H.; Tomak, Mehmet (2007-02-01) The linear and nonlinear intersubband optical absorptions in AlxlGa1-xlAs/GaAs/AlxrGa1-xrAs asymmetric rectangular quantum well are studied within the framework of the density matrix formalism. We have calculated the electron energy levels and the envelope wave functions using the effective mass approach. In addition, we have obtained an expression for saturation intensity. It is shown that the parameters such as asymmetry and width of potential well not only shift the peak positions in absorption spectrum ...
Goal–oriented a posteriori error estimation for Dirichlet boundary control problems Yücel, Hamdullah (Elsevier BV, 2021-1) We study goal-oriented a posteriori error estimates for the numerical approximation ofDirichlet boundary control problem governed by a convection diffusion equation withpointwise control constraints on a two dimensional convex polygonal domain. The localdiscontinuous Galerkin method is used as a discretization technique since the controlvariable is involved in a variational form in a natural sense. We derive primal–dualweightederrorestimatesfortheobjectivefunctionalwithanerrortermrepresentingthemismatch in ...

Citation Formats

C. Baykan and M. Fox, “Spatial synthesis by disjunctive constraint satisfaction,” AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING, pp. 245–262, 1997, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66175.