the most complicated part of the elevator design problem, whose solution requires either (i) more sophisticated search strategies, which can be expensive, or (ii) the use of an alternative problem solving paradigm.
Our solution to this problem combines both of the above mentioned approaches and is based on the integration of case-based reasoning and heuristic search techniques. In particular we used a bestfirst search algorithm to solve the ?difficult cases?, which were then stored in a case library, and we replaced the original Propose & Revise problem solver with a case-based one.
In the paper we describe four alternative algorithms for performing case-based design and we show how we were able to integrate the pre-existing search control knowledge, originally acquired in the context of a Propose & Revise approach, with a case-based approach to design. These algorithms exploit both general properties of parametric design as well as domain specific aspects of the VT problem. In particular we used our knowledge of the relative complexity of the various subsystems of the VT domain and we designed the case-based algorithms so that the case retrieval component prefers cases whose difficult subsystems do not need any modifications. The rationale for this approach is that subsystems which are difficult to design are also difficult to adapt.
The heuristic knowledge used for adaptation, originally acquired in the context of the Propose & Revise problem solver, makes it possible to estimate the minimum and the maximum cost of adaptation. Since design is an optimisation task, the upper and lower bounds of the adaptation cost can be used for filtering out cases which cannot minimise the cost criterion. Here, adaptation is broken down to elementary corrective steps. Each step represents a modification of the case which increases the cost of the solution. The control of the adaptation algorithm applies an A* like strategy which makes use of the results and costs of the elementary corrections.
These observations, which hold in many design domains, provide the ?design philosophy? of the algorithms described in this paper.
2 PARAMETRIC DESIGN
The elevator design application is an example of a parametric design problem. Parametric design problems are a class of design problems where the solution can be described in terms an assignment of values to a set of parameters. This assignment typically has to satisfy a number of design constraints and requirements, and should achieve (or at least approximate) some quality criterion. A (possibly incomplete) set of parameter assignments is called a design model. The set of all design models is called a design space.
A constraint specifies a condition which must not be violated by a consistent design. For instance, the VT elevator design application includes constraints such as ?The cab height must be between 84 and 240 inches, inclusive?. Requirements are also constraints and, as discussed in (Wielinga et al., 1995), the difference between requirements and constraints is conceptual rather than formal. Requirements describe the desired properties of a solution, while constraints limit the space of valid designs. Moreover, constraints normally specify case-independent restrictions, while requirements are typically case-specific. For instance, a requirement in the VT application specifies the desired capacity of the target elevator, which is of course case-specific.
In accordance with their role in the design process we can distinguish between restrictive and constructive constraints. Restrictive constraints eliminate certain combinations of parameter values. Constructive constraints define legal combinations of parameter values. They can be expressed in a functional notation which indicates the expected way of using the constraint in a design process.
The distinction between constructive and restrictive constraints allows us to define a class of parameters which are calculated by constructive constraints. The parameters which cannot be calculated by constructive constraints are called key design parameters. Key design parameters and their possible values define the degrees of freedom in the design process and, consequently, the size of the design space. In other words, the essential task during the design process is to decide upon the values to be assigned to key parameters; the values of the other parameters can then be determined by propagating the relevant functional (constructive) constraints.