3.1. Design computation process

Assume that design generation is formulated as a step by step combinatorial and constructive process of configuration of the parts of the design. At each step, for a given partial configuration, there are design decisions that are proposed. Transformation opportunities for a given design are combinatorial, that is, there is a tree of design alternatives, each of which will subsequently be the root to other trees emanating from it as a result of future design decisions. At each step of such a process a design decision may be selected and is applied, resulting in a new design. This new design is evaluated using design evaluation knowledge. Once a design alternative is evaluated some learning can be done. How this is done is explained in the next section.

At a lower level of abstraction, the design computation process may be mapped onto the traditional artificial intelligence (AI) state-operator paradigm of search (Fig. 2a), where operators match the state information to transform the existing state into a new state. In such a mapping operators map onto design decisions and states map to design contexts. The state-operator paradigm of search is used in a number of general problem solving architectures such as SOAR (Laird et al., 1987; Newell, 1990) and PRODIGY (Carbonell et al., 1991). The SOAR architecture was chosen to implement the ideas in this paper. SOAR is also an embodiment of a psychological theory of cognition (Newell, 1990), an architecture for general intelligence (Laird et al., 1987), as well a programming tool for AI. The general ideas used are best described at the knowledge level of computational designing rather than at the level of SOAR. However, two concepts, decision proposal and application, have been borrowed from SOAR.

Design experience is the historical trace of data that is generated during such a process. Because the entire computational design process is rule based, this data is an historical collection of instantiated patterns that matched and were replaced by new instantiated patterns during the process of decision proposal, application, and solution evaluation. This trace is the data that is utilized by the learning algorithm used in this paper.

3.2. Integrating learning in the design computation process

The model of learning is tightly coupled with design processes (Fig. 3). The notion of appropriateness of designs (absolute, e.g., satisfaction of constraints; relative, e.g., minimizing a global design variable) controls the design strategy and how learning is done. In this paper the focus of the demonstrative example is on the satisfaction of constraints. Such control is exercised because of the effects and side effects of a chain of events that happen as a generated design is evaluated. Evaluation of designs drives positive or negative credit assignment of design decisions. The credit assignment determines whether the consequent of a heuristic is about avoiding or preferring a design decision. Because the antecedent of the heuristic is expressed in terms of the representational space of the design context (see next section for details), the design context influences what is learned. As both of these are encapsulated in the derived heuristic, when the heuristic becomes applicable, it in turn, influences subsequent design generation and hence influences the resulting design description and its quality. The learned heuristic becomes a part of the generation control strategy, and in turn, influences future design generations in a similar situation by eliminating search effort. This is how learning incrementally changes the design process from being more search based to being more knowledge based. Every new unexplored path in the design solution space presents either an opportunity for learning or an opportunity for using what was learned.

The tight coupling between learning and designing. The arrows signify influences on the box at the head of the arrow and by the box at the tail of the arrow.

The heuristic applies for any arbitrary design context in which the extracted situation matches. If the heuristic is available at the time of proposal of the design decisions, the operator may not even be proposed if the heuristic predicts a bad solution. Therefore, these automatically derived heuristics act as strategy knowledge, just like the manually defined heuristics that are often used to prune the space of design alternatives.

3.3. Learning mechanism explained by simple example

The learning mechanism used in this paper can be better understood by initially reviewing the concept of explanation-based learning (EBL) in AI. One striking difference between EBL and other common forms of similarity-based learning is that the target concept definition already exists. The task of EBL is in reformulating it in terms of what is called operationality criteria. Operationality criteria define the space of representational terms that are allowed in the reformulated concept definition. Another difference is that learning is from a single example rather than a set of positive and negative examples. The learning mechanism used in this paper is the chunking method of SOAR, a variant of this method.

Let C1 be a training example for a target concept; here, we will use a cup. The features of C1 are the following: it is light and made of porcelain and it has a decoration, a concavity, a handle, and a flat bottom. Assume that the following five statements constitute a domain theory for the functional definition of a cup. A domain theory in EBL is a set of rules or facts that is used to determine the membership of an arbitrary instance to the target concept. In this context, let the domain theory statements be the following:

1. if an object is stable and enables drinking, it is a cup;
2. if an object has a bottom which is flat, it is stable;
3. if an object carries liquids and is liftable, it enables drinking;
4. if an object is light and has a handle, it is liftable; and
5. if an object has a concavity, it carries liquids.

Can it be shown that C1 is a cup? In this case, C1 is indeed a cup. The flat bottom of C1 makes it stable, it is light weight and has a handle that ensures liftability, its concavity allows it to carry liquids, and the liftability and ability to carry liquids enables drinking. The above explanation is an informal proof tree of why the example is a cup. Thus, the relevant features of C1 that determine “cupness” are lightness, concavity, handle, and flat bottom. The rest of the description of the cup are often stated in the context of a cup but are immaterial/irrelevant in diagnosing a cup. The output of EBL is a new rule: if an object is light, has a concavity, has a handle, and has a flat bottom, then it is a cup. Note that the explanation is a set of chains; in each chain one or more initial structural features (facts) match domain theory rules to generate new intermediate assertions that ultimately imply some functionality of the cup. All these functionalities in combination represent the cup concept. In this case, the operationality criterion was the space of structurally observable features for the cup. To derive these relevant structural features, the proof tree may be also considered to be a trace of a set of inference chains. Traversing these chains backwards (backtracing) from the functional features of the cup to their originating features until all features satisfy the operationality criteria, yields the relevant elements that in the future can diagnose a cup. This is the basic task of any explanation-based or analytical learning algorithm. In practice, this is more complicated, as the left-hand side of the derived rule would be composed of patterns rather than constants.

3.4. Mapping learning concepts to the design process

We can map the components of the EBL example to the design process. The target concept is mapped onto the concept of a good (+) or bad (−) design solution. The training example, an instance of the target concept, is mapped onto a complete or partial design solution that is generated and subsequently evaluated during the search process. The domain theory is mapped onto the design evaluation knowledge that is used to make the evaluation. Then the proof tree or justification basis for the reformulation of the concept is the part of the design experience from the time the design decision was proposed through the application of the decision to the evaluation of the design alternative. The operationality criteria are mapped onto the representation space of the design context just at the point before the design solution is about to be generated by some design decision. If the above are the mappings of EBL concepts to the parts of the design process, then analogically an EBL backtracing procedure will result in an output rule that is an association between a relevant subset of the parent design context and a preference on the design decision that constructed it.

The role of learning, again, analogically, is to change the representation of the evaluative concept of the quality of a design to “what to do, when in order to achieve a good or eliminate a bad design solution,” or in other words, “what to do when” so that the presence or absence of an instance of the feature class that defined goodness or badness could be achieved. The term “what to do” is characterized in terms of preference on a design decision. The term “when” is characterized as a situation, a potential pattern that can match a wide variety of future design contexts. When such a heuristic is available and matches the design context, the quality of the design solution that a design decision is expected to generate is now predictable directly using the features of the design context that were there before the design is even generated. This makes the result of the concept rerepresentation directly applicable to the process of designing.

3.5. A more formal description

Using the previously described mapping between the proposed design computation process to the state-operator paradigm, we can now describe the designing and the learning process more formally, combining the levels of abstraction. A design generator recursively proposes design decisions (d_k) to transform an initial partial design configuration (s₀) to generate a tree of designs (Fig. 2a).

The generation of each design is followed by the evaluation of the design, thus creating a new design context. The process as a whole is thus a transformation of design context information (s_i → s_j) (Fig. 2a), and details of a single decision application are shown in Figure 4. The additional input required for learning is the description of a design feature class (f_j) and a flag to it identifying whether the feature class is bad (−) or good (+), an evaluator to determine the quality of the design. Learning can take place only when instances of one of these evaluator feature classes is present in the newly generated design. The process of learning is essentially constructing the association between what are the conditions (c_i) under which the decision d_k should be preferred (+)/rejected (−), that is, a rule c_i → (+/−)d_k, where c_i ⊆ s_i c_i, is found by backtracing each pattern-matched variable of f_j from state s_j to its originating elements in state s_i through the trace of design experience (Fig. 4). Tracing is defined as the process of maintaining a historical chain of instantiated patterns that were matched and replaced during the process of decision proposal, application, and evaluation of design alternative. This output of trace is the design experience. Tracing is done when a design alternative is constructed using uninformed search, that is, without the aid of a heuristic preferring an operator. The process of backtracing a given instantiated pattern, f_j, is the process of traversing the historical chain of instantiated patterns from f_j in a reverse direction to its generation to find which patterns were used to generate it. In this case, it is c_i. Looking in a forward direction, c_i is one or more instantiated patterns in s_i, which were transformed by the design decision d_k to give rise to feature f_j that was subsequently evaluated in s_j to conclude about the quality of the design. The situation construction is denoted as c_i ← f_j, the reverse arrow signifying the backtracing operation. The process of learning from a single design generation and evaluation is termed in this paper as “single-step learning.”¹

Learning from an instance of design generation and evaluation, the knowledge “If pattern ci matches some context sm then prefer(+)/avoid(−) dk.”

Once c_i is obtained, the task is to turn it into a variable c_i (also called variablizing) so that it can pattern match future design contexts. The process of variabilization is a direct consequence of using the chunking algorithm of SOAR (Laird et al., 1986) and its implicit generalization strategy. This corresponds to the same variable identifier replaced by the same variable and different identifiers by different variables.

3.6. Connection with SOAR

The main reason for using SOAR framework is that it allows a uniform representation space to be used for both learning and problem solving. With other systems there may be the issue of mapping the representation space of learned knowledge to that of a representation space for problem solving to use what has been learned.

SOAR uses a variant of EBL called chunking. Chunking results in rules known as chunks. The learning method described in the previous subsection is based on SOAR's chunking algorithm that has been specialized, reinterpreted, and applied in the context of computational design. Learned heuristics map onto SOAR chunks. The principle of chunking in SOAR is: whenever there is problem solving done within a subgoal, it can be bypassed the next time because of a chunk (rule) that captures an association between the results of the subgoal and the features of the supergoal that led to the result in the subgoal. But chunking is an abstract domain independent learning mechanism, applying it in the context of generic design tasks requires commitment on several aspects that chunking does not commit to, for example, the nature of subgoal generation, and nature of problem solving in design subgoals. This is equivalent to the addition of one knowledge level that captures the generic tasks involved in computational design and maps them to the domain general knowledge level of SOAR. Nath (2000) describes these in more detail and proposes extensions and variations to this method. The successful integration of learning and problem solving is also a direct consequence of using the SOAR architecture, as SOAR treats the learned chunks in the same way as human encoded rules.

4.1. Shape representation

A shape (instance) is represented using an anticlockwise ordered sequence of directed unit edges called facelets from a base point.²

Figure 7b is the pictorial representation of an abstract shape class {base point, any − 5 × anticlockwise − 3 × opposite − 4 × clockwise − 2 × straight − 1 × clockwise}. Its base point is circled and labeled A and the facelet that has its tail at A is the starting facelet. The directional move sequence in this representation is a shape generation plan, where each move (viz., anticlockwise, opposite, clockwise, straight) is relative to the starting cardinal direction, “any,” to which the initial facelet can be instantiated. Numerals in this representation represent the number of consecutive times of application of the same relative move. Thus, the cardinal directions of nonstarting facelets can be instantiated to four possible directions depending on the instantiation of “any” to north, south, east, or west. This abstract representation with a given base point, suffices to encode four possible instantiations of the shape for a given starting base point. If the base point representation is also parametric, the set of possible shapes, which belong to this class, are multiplied by the number of possible base points. Figure 7a shows one instantiation of the shape class shown in Figure 7b with a given base point and the starting facelet pointing to west. Design evaluation knowledge and reasoning are on shape classes rather than their instantiations, so that the knowledge that it produces as a result of learning is more general.

The elements of representation of (a) a shape and (b) a shape class.

Adjacency between an already placed room A and B (being currently configured), is achieved by instantiating a given shape class such that B's starting facelet is equal in position (same end points as the joining facelet of A1) but opposite in the direction to any facelet of A. This is shown in Figure 8, and is the task of the design decisions. The combinatorics of the design alternatives (and design decisions) for a given room are defined by the choices of different allowable shape classes, the different facelets of room A that can be used as the instantiation seed for the initial facelet of room B, and the different shape generation plans.

The adjacency of design parts: representation.

4.2. Design evaluation criteria

One evaluation criterion that often governs good layout designs is “efficient usage of space.” To demonstrate the effectiveness of the ideas, let us assume that the concept of efficient usage of space is defined as the absence of three feature classes: narrow deep (con)cavities (I-shaped and L-shaped) between two or more rooms, unit holes between two or more rooms, and too much edge overlap between two given rooms. Positive and negative examples of what is implied by the first two criteria and are shown in Figure 9. Two of the rules that identify typical unit holes and deep concavities are shown in Figure 10. The last criterion is formulated as follows: for two given rooms, the number of overlapping facelets of each of these rooms should be ≤2. The Hall being the one room with limited perimeter, which is adjacent to most rooms, cannot afford to have its perimeter edges consumed by a single room to satisfy adjacency criteria, because when the last few rooms are being configured with respect to the hall, there may not be enough perimeter length of the Hall left to satisfy the adjacency requirement of these later rooms. In that case, the program goes into costly backtracking operations.

Features that make layouts undesirable: deep (con)cavities and holes between rooms.

Typical rules that define one case of deep (con)cavities and unit holes.

These design evaluator features (labeled as bad) are described by reasoning about the facelets between rooms (Fig. 10). In this example, the task of learning is to rerepresent the concept of unit holes, deep concavities, and excess edge overlap in terms of a subset of patterns in the previous design context from which these features were generated, so that for the future those patterns could be used as a predictor of these types of bad features and thus be used to avoid decisions that will produce such features.

8.1. Strengths of the method

There are many advantages in using this method. First, learning is dynamically driven by the requirements of the designing process to produce better solutions rather being than a passive process of classification of designs. This is the basis for a highly coupled interaction between learning and designing processes that results in a self-improving design search procedure. Second, the uniform representation space for learning and designing borrowed from the SOAR framework allows seamless transfer in both directions. Third, the learning method and the knowledge learned aid the design computation process in reasoning about regions of the search space rather than specific points. This is possible because the situations embedded as antecedents of learned heuristics encode in their patterns complex conditions that correspond to regions of the solution space. In addition, the knowledge engineer can control the level of generality desired in these learned heuristics. The more abstract, the evaluation reasoning, and the representation of the problem, the more general and applicable the learned knowledge will be. Fourth, sets of inappropriate solutions can be eliminated using a single learning session thus enabling rapid exploration of the solution space. This, of course, has a bearing on the level of abstraction employed in representation and reasoning of the domain. Fifth, costly processes are involved in domain-oriented knowledge engineering like elicitation of tacit knowledge and subsequent encoding of heuristics are eliminated. Only those heuristics are constructed by the program that are relevant to goal of satisfying the design requirements under consideration.

The experimentation strategy and the results showed that the heuristics did not fail, the situations embedded in the heuristics did not estimate a bad design solution as good, nor did it classify a good design solution as bad. The process uses an approach similar to EBL and performs a deductive compilation of the domain theory (design evaluation rules) based on operational criteria. This implies that the learned heuristics could only fail if the knowledge engineer incorrectly encodes the domain theories employed in evaluative reasoning. It is therefore important that the user of this method has precise definitions of what exactly constitutes a bad design and what is a good design. Because of this advantage, the embedded situations in the heuristics do not need any statistical evaluation to determine their success or failure. At the knowledge level, a correctly encoded evaluative domain theory will result in a correct concept rerepresentation, that is, correct heuristics.

Finally, the unlike many other works on learning, the learned knowledge can be inspected to have an understanding of the kind of learned knowledge generated and thus have greater control over it. The need for such inspection could be not only for the human designer or the researcher to experiment with their representations to best utilize a tool such as this to suit their goals, but also to understand the nature of tacit hard to explain knowledge that is captured as a result of learning. The tacit nature of this learned knowledge was explored in another work (Nath, 2003).

It is these advantages that should encourage computer-aided design system developers or researchers to incorporate such an approach in the design of their tools for designing. Practicing designers, who would be users of such a tool, would also gain these advantages.

8.2. Distinction from past work

The work that is presented here is distinct from learning from designs, on which there is a plethora of research. This work demonstrates learning and designing co-occurring in a coupled design process. Manfaat et al. (1996) have reported generalizations from a set of spatial layout designs. The form of learning reported here can also be viewed as one form of knowledge compilation (Mostow, 1990). Knowledge compilation has been applied by Brown and colleagues (Sloan & Brown, 1988; Brown & Spillane, 1991; Liu & Brown, 1991; Chabot & Brown, 1994; Brown, 1996) to learn design process knowledge, but these works were not in the spirit of the tight coupling between a learning and a designing process. Braudaway and Tong (1989) introduced a knowledge compilation-based system called RICK, which describes how an inefficient generate and test problem solver for a parametric building layout design problem, can adapt itself to the problem specific constraints. No heuristics are learned here; instead, a more efficient LISP program (constrained generators) for solving the particular problem is synthesized. Voigt and Tong (1989) describe an extension of RICK called MENDER, which reformulates the global design constraints as an evaluation function and derives “hill-climbing patchers” through knowledge compilation.

If one views this work as adaptive search, that is, tailoring a generic generative mechanism to produce desirable designs, there is research by Cagan and colleagues (Cagan & Mitchell, 1993; Reddy & Cagan, 1995; Shea & Cagan, 1997; Schmidt & Cagan, 1998), who apply simulated annealing to optimize grammatical design generation. In a similar stochastic spirit, there has been some recent applications by Vale and Shea (2003a, 2003b), which attempt to distinguish good sequences of design generation operators from the bad using search experience. The intention is to use scores on these sequences as strategies that allow good sequences to be preferred over the bad in design generation. Machine learning here is of the incremental parameter tuning variety (Samuel, 1959), where the parameter is a score that is calculated on the basis of changes in objective function over grammar rule sequences weighted by the probabilities assigned to sequences based on past experience and future utility. However, the relation between the problem conditions and when a sequence could be useful is not explicitly modeled, and it is not clear whether the probabilistic weights capture such a relationship implicitly.

Approaches to learning heuristics in design using the chunking method of SOAR has been reported by Modi et al. (1995a, 1995b) while using SOAR as a design problem solver in the design of chemical engineering distillation sequences. However, the focus of that work was not on learning heuristics for preferring good solutions to inferior ones, but on heuristics for choosing evaluation functions from a predefined set. The research presented in the current paper treats learning design process knowledge more generally.

8.3. Weaknesses of the method

The first weakness of the method is the inability to handle negated reasoning in its evaluative domain theory. This is more a consequence of the use of chunking algorithm of SOAR than the approach itself. The primary difference between chunking and EBL is that the backtracing of the concept in EBL takes place using the symbolic structure of the rules, rather than the instantiated rules. When instantiated patterns are used as the source for backtracing, the design experience as a result of tracing can account for the presence of instantiated patterns but cannot account for the absence of instantiated patterns. Hence, the resulting heuristics are likely to be overgeneral. It is in such situations that the heuristics may fail, despite a correct domain theory. But this problem can be overcome by using another analytical learning algorithm like the traditional EBL, which uses backtracing through uninstantiated patterns.

As the evaluative reasoning tends to get more complex with many cases of applicability and increasing number of reasoning chains, it can often seem like new strategy knowledge is generated. However, at the theoretical level, there no new knowledge (outside the bounds of what was given) is generated as a result of learning. All heuristic knowledge is within the deductive closure of the knowledge that was encoded a priori, although to the human it may seem like new knowledge.

8.4. Scalability issues

Analytical learning from experience is often designed to incrementally increase the performance of a search mechanism. So the learning mechanism in itself is a step toward future scalability in terms of efficiency of exploration of a space. The time taken to learn is not really the issue for scalability, whereas the ability to match learned knowledge to a future design context to apply it to some future design context is. In other words, scalability is more of an issue at the applicability time of the learned knowledge rather than at learning time.

At the knowledge level, the scalability of a heuristic at application time, in isolation, is related to the complexity of the situation that is embedded in the heuristic. The complexity of the situation depends on the number of unit representational entities (object–attribute–value triplets) and shared constraining interrelationships that have to be matched to a given design context. Sometimes such a heuristic with a large set of conditionals and many shared relationships could be very expensive to match (Tambe & Newell, 1988) with a large data set encapsulated in a design context, and as a consequence, that the system suffers a slowdown (Minton, 1988) after learning, contributing to what is called the utility problem. In general, the utility problem occurs for all systems that learn rules from experience. The main reason for such a slowdown, especially when production systems like SOAR are used, can be understood at the internal algorithmic level rather than at the design knowledge level. For SOAR, the greatest amount of computational resources are used in matching rules and the knowledge search (Tambe, 1991) for which rules apply to the given context. This is significant even though SOAR uses an efficient production match algorithm like RETE (Forgy, 1982) and rule firing is simulated to be in parallel. SOAR's chunking algorithm is well known to reduce the number of steps to solve a subproblem the next time, but when the utility problem occurs, the cost of matching the learned chunks becomes expensive as a result of the production match algorithm that offsets the benefit gained from the reduction in the number of problem solving steps. Ideally, the cost of using the learned rules should always be bounded by the cost of the problem-solving episode from which they are learned (Kim & Rosenbloom, 1996). The current solution is to design representations for data and reasoning in such a way that a larger number of cheaper chunks with smaller patterns is generated. A way in which the above could be possible is to trade off expressivity of representation for speed (Tambe & Rosenbloom, 1989). A related but different reason that could also contribute to the utility problem is what is known as the average growth effect (Doorenbos et al., 1992) of the knowledge base because of heuristics being learned continuously. Interaction across heuristics slows down the system even though the heuristics are not themselves expensive. Solutions to the average growth effect have already been proposed (Doorenbos et al., 1992; Doorenbos, 1993).