An Investigation of Opportunistic Constraint Satisfaction in Space Planning

1. Region Line Adjacency Network

The elements used in region line adjacency network abstraction are horizontal and vertical lines and regions. Each line is unique, and extends from -infinity to +infinity. Incidence relations between a region and the lines which define it are: north-line, south-line, east-line and west-line. Their inverses define relations from lines to regions. There are also relations between two lines of the same type. Relations between vertical lines are: line-east-of and line­ west-of. Relations between horizontal lines are: line-north-of and line-south-of. These are transitive relations, in terms of relations between lines and regions and lines and lines.

{( rl

( ( h2

INSTANCE: horizontal-line

NORTH-REGIONS: r1

SOUTH-REGIONS: r2

LINE-NORTH-OF: h5

LINE-SOUTH-OF: h4} }

Figure 2: Representation of region rl and line h2

Figure 1 shows a configuration of regions and lines, and figure 2 shows how it can be represented in the region line adjacency network using the relations described above.

Networks are also used for determining the dimensions of regions and locations of lines. These values are represented as intervals with minimum and maximum allowable values. Initially an interval for the location of a line such as the x coordinate of a vertical line, extends from -infinity to +infinity, an interval for the x or y dimension of a region extends from 0 to +infinity. As design progresses minimums

INSTANCE: region

NORTH-LINE: h1

SOUTH-LINE: h2

WEST-LINE: v1

EAST-LINE: v2 } }

may only increase and maximums may only decrease, until the two are equal.

The operators for creating the topology and determining the dimensions of a network are:

• Create new region.
• Merge two lines.
• Put a line south or west of another line.
• Post minimum/maximum values for an interval.

These operators propagate new bounds· to related intervals. A new relation can be satisfied if it does not contradict existing relations and dimensions. An operation can be contradictory, redundant or constraining. When a contradiction is detected, propagation stops with failure. In case of a redundant value or relation, the operation succeeds and stops. · A constraining operator leads to further propagation of effects.

One dimensional relations between regions in the horizontal or vertical direction are defined in terms of relations between lines and regions, and lines and lines. These are similar to Allen's temporal relations (Allen 1983). Horizontal relations between regions are below, and their corresponding vertical relations are in parenthesis. The inverse of a relation is also defined if it is not symmetric, but not given below.

• region-west-of (region-south-of)
• region-west-adjacent (region-south-adjacent)
• horizontally-inside (vertically-inside)
• horizontally-overlapping (vertically-overlapping)

A horizontally-inside B is defined as west line of A being east of west line of B, and east line of A being west of east line of B. A south-adjacent B is defined as region A sharing its south line with the north line of region B.

In this representation dimensions and topology are separate yet related. Decisions can be made in any order. Every state created using the operators defined above is an approximative abstraction that defines an equivalence class of solutions in terms of the decisions made up to that point. A constraint that has been satisfied will not be violated later using these operators. All spatial relations can be explicitly represented; which makes it possible to design the layout of work centers in a kitchen at one level of detail and to design the layout of the applicances in the work center at another level. It is possible to generate packed layouts using the merge lines operation, or loosely packed layouts putting lines relative to each other.

2. Spatial Relations

Spatial relations are defined in terms of the one-dimensional relations between regions in the adjacency network. Types of relations considered are: adjacency relations, spatial-overlap relations, location relations, position relations, orientation relations and distance relations. Adjacency relations are: next­ to, completely-next-to and covers. Next-to is defined as the regions being region-west(south)-adjacent in one direction and vertically(horizontally)-overlapping in the other. Spatial­ overlap relations are inside, has-inside, overlap and non­ overlap. Location relations are north-of, south-of, east-of and west-of. Position relations are at-front, at-back, at-left and at­ right. Location relations are defined with respect to the global coordinates and position relations are defined with respect to object centered coordinates of the design units. Most design units have fronts, backs and sides which have to be treated differently in a layout. There are orientation relations: parallel-to, perpendicular-to, opposite, and distance relations.

Existing relations between design units are used in inferring new relations, and determining which new relations indicated by constraints are already satisfied and which are contradicted.

Some relations are mutually exclusive i.e.,north-of and south­ of. Given a relation between two design units, relations that ·are mutually exclusive are contradicted i.e., A north-of B contradicts A south-of B. Some relations satisfy others, such as inside satisfies overlap, and next-to satisfies non-overlap. This type of reasoning uses the definitions of the relations. Another way of reasoning uses the transitivities of the relations. Some relations are transitive, so that: if A inside B, · B inside C and C north-of D then A north-of D. Transitivity of each relation is expressed by a path grammar and used in reasoning via relations. A third way of reasoning involves making inferences. Two relations are used to infer a third: if A at-front B and orientation of A is 90 then A west-of B.

Relations level enables reasoning while more complete but combinatorially expensive reasoning at the adjacency network: level is deferred. Domain constraints expressed in object­ centered coordinates are converted to design coordinates as successive design decisions enable inferences. Some relations can be shown to be satisfied or contradicted due to interactions between relations.

D. Constraints

Constraints represent design goals and control knowledge. The categories of knowledge that need to be known in order to use constraints as a representation of knowledge and as a search technique are (Fox 1983):

• How to generate states satisfying a constraint.
• How to test if a constraint is satisfied.
• Possible relaxations of a constraint.
• Relative importance of a constraint.
• Uncertainty of a constraint.

Constraints encoding knowledge of the design domain are posted to prototype design units. Design unit instances inherit constraints from their prototypes and the prototypes above it in the hierarchy. The constraint values inherited from different prototypes for a constraint type can be added on, i.e. sink1 may inherit constraint values from solid, architectural­ du, and sink for the same variable and constraint type, or a value placed at sink may replace those specified above it.

Domain constraints which specify a relation between two prototypes such as: sink should be next to wall, is inherited at sink1 and refined into: sink1 should be next-to wall1 or wal12. How the instances walll and wall2 should be combined is specified at each constraint or inherited from the type of constraint, for example non-overlap constraints are combined with and. Similar relations are posted between constraints to indicate that the actual instances selected should be the same, i.e., if sink is placed next-to walll, it should also be parallel-to wall1, and not to another wall instance.

Constraints at the network level express an instantiated constraint in terms of one-dimensional relations between regions. For example, sink1 inside sink-center1 is refined into: sink1 is horizontally inside sink-center1 and sink1 is vertically inside sink-centerl. The goal tree is an and/or tree of constraints starting with domain constraints between prototype design units and ending with one dimensional relations between instances.

E. Problem Solver

A space which serves as the envelope and its adjacent spaces are the minimum givens that make up the initial state. Any features that should be fixed in the design and some information about the design context such as house area, household population, and building type should also be given. First stage of problem solving is pre-search analysis.

Based on givens, additional constraints are posted by rules of the form: If kitchen area is greater than or equal to 15% of the house area, then the kitchen should be an eat-in kitchen with a table and adequate seating. Design unit types are selected: there should be a sink, a refrigerator, a cooker etc. The goal tree is set up using the instances selected to be in the design and those present in the initial state. The interactions between constraints that can be determined are found. A geometric modeling program finds the existing relations between design units, and creates a region line adjacency network representation of the initial state.

The second stage in problem solving is opportunistic search. Search control operates by selecting a state and a constraint to generate new states. Each search step consists of the following operations:

• ~ .-;elect a state
• select a constraint
• generate new states
• update constraints
• update states

Constraints are selected based on their uncertainties. Identifying interactions between constraints is useful to identify opportunistic decisions. Constraints are said to be independent if achieving one goal has no effect on the second, cooperating if achieving one goal makes it easier to achieve the second, competing if one goal can only be achieved at the expense of the other, and conflicting if achieving one goal must take the second into account due to an interaction (Mostow 1985).

Other information for determining the uncertainties of constraints are: importance of a constraint, severity of a constraint the type and state of the variable(s) constrained, the size of design unit(s) affected by the constraint. Uncertainty is used as a measure for rating the opportunism of constraints, and determining where to focus attention during search.

Opportunism is focusing the attention of the problem solver on the most constrained operation that can be performed at each step instead of taking a pre-determined strategy for control such as top down, goal driven, or data driven (Stefik 1980). A top down approach locates work centers first and uses this to guide the location of applicances. In an opportunistic approach, if the location of an applicance is more constrained than the location of a work center, then the applicance is placed first and this guides decisions at higher levels regarding the location of work centers. Islands of certainty through which the solutions must pass can be identified by understanding the approximate topology of the search space [4] Search proceeds by using the islands as starting points and expands them.

Since design involves relaxing and adding constraints as well as searching for a solution defmed by a set of constraints, we find a representative sampling of significantly different solutions. Significance of differences are based on which constraints are satisfied and the values used to satisfy them.

III TEST RESULTS

Version 0 of WRIGHT uses reasoning at the spatial relations and user interface abstractions, but not at the adjacency network level. Selection of levels is fixed. A variable is selected based on the uncertainties of its constraints. Then all the constraints of that variable are applied in order of certainty to generate all valid ranges of values for that variable. Each constraint is applied first at the relational level. If there is no conflict then the constraint is used to generate a range of values. After all the constraints of the variable are applied, then a discrete set of values are selected from the range of the best state to continue the search with other variables.

Version 1 of WRIGHT about to be completed uses reasoning at all the levels described. Levels are searched opportunistically and all constraints of a variable do not have to be considered together.

WRIGHT has been tried on different test cases. This approach works better when the solutions are tightly constrained. Research on the types of knowledge that enable us to identify opportunistic decisions is continuing.

IV CONCLUSIONS

WRIGHT version 0 results indicate that starting search with more strongly constrained design units efficiently eliminates many dead ends and leads search towards the better solutions. The ability to defer uncertain aspects of a decision while being able to reason at a higher abstraction level is needed to use islands of certainty as guidance for search. WRIGHT version 1 is formulated to achieve this capability.

One of the limitations of wRIGHT is the types of constraints that can be considered. The goal tree should start with general performance issues such as daylighting, spatial order and energy efficiency and derive specific constraints from these. This level of the goal tree is omitted in this research, to concentrate on using space planning constraints opportunistically. We attempt to generate a sampling of good solutions so that the designer can compare in the light of other constraints.