PSMs can be specified either in a task-specific (Chandrasekaran, 1990; Benjamins, 1993) or task-independent style (Beys et al., 1996; Fensel et al., 1997). Task-specific PSMs are reasoning components which subscribe to a task-specific vocabulary and can therefore be applied to applications which share the same generic task structure (e.g. a diagnostic PSM can be applied to all diagnostic applications). Task-independent PSMs do not subscribe to a task-specific vocabulary but specify reasoning steps either in terms of a generic problem solving paradigm, such as search (Newell and Simon, 1976), or in terms of the epistemological properties of the domain knowledge base (Beys et al., 1996).
Both approaches, as pursued in recent years, suffer from problems. Task-independent PSMs do not provide enough leverage for knowledge acquisition and are more difficult to reuse than task-specific ones (Klinker et al., 1991). On the other hand a task-specific terminology limits the possibility of reusing PSMs across classes of tasks and can impede our understanding of what a PSM really does (Motta and Zdrahal, 1996). Moreover, as shown by the task-independent reformulation of a Propose&Revise problem solver presented by Fensel et al. (1997), the use of a strong, task-specific terminology doesn't automatically imply strong problem solving commitments: in some cases a task-specific terminology is nothing more than a terminology.
Thus, we believe there is a need for an approach to PSM specification and library organization which can reconcile the advantages in terms of KA and reuse afforded by task-specific formulations with the clear theoretical foundations and problem generality provided by task-independent problem solving paradigms, such as search. In particular our approach relies on the following three key ideas:
In this paper we illustrate these ideas in the context of a library of reusable components for parametric design problems (Wielinga et al., 1995; Motta and Zdrahal, 1996). The paper is organized as follows. In the next section we provide an outline of the generic modelling framework adopted to structure both the application development process and the organization of the library. In section 3 we will briefly introduce the class of parametric design problems. In section 4 we will illustrate a generic model of parametric design problem solving, obtained by instantiating the search paradigm in terms of the parametric design task ontology. Then, in section 5, we will illustrate a library of PSMs for parametric design defined as specializations of the generic model presented in section 4. Section 6 briefly discusses some application models developed using our library of reusable components. Finally, in sections 7 and 8 we compare our work with alternative approaches to developing and organizing PSM libraries and we highlight some issues for future research.
These steps are discussed in the next sections.
In the universe of discourse the problem is characterized by at least two distinguishable states: the initial state and the final (goal) state. For example, the initial state of a medical diagnostic problem specifies all observable symptoms, a class of diseases and the patient's symptoms. The final state is characterized by an association of the symptoms with a particular disease. Similarly, the initial state of a design problem describes design requirements, available components and possible component configurations and the final state specifies a blueprint for constructing the artefact. The key to defining generic and reusable problem specifications is that similar problems can be characterized in terms of a common, abstract universe of discourse, associated with a problem type.
A reusable conceptualization of a universe of discourse is called an ontology (Gruber, 1993). Here we use ontologies to conceptualize the abstract universe of discourse associated with a problem type. This is called a task ontology.
The answer to this problem is given by the notion of problem solving as search (Newell and Simon, 1976), which characterizes problem solving as the process of navigating a state space. The search model perfectly satisfies our requirements. On the one hand, given a task specification, unless we assume additional knowledge related to the state space, the only course of action left to a problem solver is to search - this property has been called the existential predicament of intelligent systems (Newell, 1990). On the other hand, as already pointed out, all PSMs can be modelled as search processes. Specialized PSMs essentially increase the efficiency of the search process by making use of additional problem solving knowledge.
Thus, by applying search as a general problem solving paradigm to the state space generated by a task ontology we can produce a task-specific, method-independent generic problem solving model and a highly generic method ontology. The former fulfils two roles: i) it defines a framework which can be used to compare the competence and performance of alternative methods and ii) it makes it possible to characterize method development as a model specialization process. The latter specifies the minimal ontological commitments which need to be fulfilled by a problem solving method associated with the given problem type. These commitments - discussed in more detail in section 4 - essentially formalize the notions of state and state transitions, which are associated with a problem solver performing search.
The method ontology obtained by instantiating the search paradigm in terms of a task ontology can be regarded as the most generic ontology associated with a problem solver which subscribes to the state space view. Of course, because of the generic nature of the search paradigm, any specific PSM for the given class of tasks can be defined as a specialization of the generic method ontology. In other words we assume that the proposed, task-oriented instantiation of the search metaphor is adequate to describe the behaviour of large classes of knowledge-based systems. Individual problem solving methods will differ in terms of the knowledge used for navigating the search space. This problem solving knowledge will determine the competence and efficiency of a method. For example, if the goal state of the task requires consistency and the problem solver possesses knowledge which makes it possible to remove inconsistencies, then the path through the state space may include inconsistent states. In contrast with this behaviour, a problem solver which is not able to remove inconsistencies need to construct a solution path through the state space which only includes consistent states.
Domain knowledge itself can be specified in a task- or PSM-independent fashion. These reusable knowledge bases are usually called multi-functional (Murray and Porter, 1988). Two problems typically arise when applying a PSM to a multi-functional knowledge base:
A representation mismatch can be addressed by adding appropriate mapping mechanisms (Gennari et al., 1994). For instance the method-specific concept of parameter can be mapped to the domain-specific concept of employee when applying a parametric design problem solver to an office allocation problem (Motta, 1998a).
The second bullet point concerns knowledge missing in the domain model. For example, in an office allocation problem the knowledge about office preferences and allocation requirements is important. This knowledge is application-specific and therefore cannot be part of a multi-functional domain knowledge base. Therefore, it needs to be acquired on an application-specific basis.
In order to account for these two modelling situations, i.e. formulating the relevant mapping mechanisms and acquiring application-specific knowledge, our framework includes a fourth type of component, application configuration knowledge. In contrast with the other three components (task, problem solving method and domain model) this knowledge tends to be application specific and therefore not reusable. The overall modelling framework is shown in figure 2.
In the rest of the paper we will show how the framework introduced in this section can be used for building a library of reusable components for parametric design and for developing parametric design applications by reuse. We will begin by briefly characterizing the class of parametric design problems.
P is a set of parameters, {p1, ... , pn};
Vr is a set of value ranges, {V1, ... Vn}, where Vi = {vi1, ... , vil}
C is a set of constraints, {c1, ... , cm};
R is a set of requirements, {r1, ... , rk};
Pr is a set of preferences, {pr1, ... , prj};
cf is a cost function;
Dk is a design model, {<pi, vij>}.
Because of space limitations we will not enter into the details of parametric design applications - the interested reader is referred to (Motta and Zdrahal, 1996; Motta, 1998a). However, we should emphasize that our discussion here is only concerned with the formal parametric design problem - how to construct a solution design from a formal task specification. Naturally, there is more to design than deriving design models from input specifications. In particular acquiring a task specification is itself a complex, collaborative process during which various stakeholders negotiate a common view of a design problem (Ehn, 1989; Greenbaum and Kyung, 1991). Moreover, this negotiation process, often called problem framing (Schoen, 1983) is typically an iterative process, which is intertwined with both problem solving and design evaluation (Bonnardel and Sumner, 1996). Hence, the fact that the work presented here is concerned exclusively with the formal design problem should not be taken as implying that the other aspects of the design process are less important or that the design life-cycle can be characterized by means of a waterfall model where design formulation and problem solving are carried out sequentially.
In accordance with the approach proposed in this paper we have formalized parametric design problems by means of a task ontology, which comprises about forty definitions. This ontology is described in detail in (Motta, 1998a).
In order to formulate a design space we need only a task specification, given that this provides all the necessary information for generating all possible design models associated with a task. No additional assumptions are introduced here, either about the structure of the design space or the availability of search-control knowledge. Thus, the notion of design space makes it possible to move from a task-oriented perspective to a problem solving-oriented one. Let us consider a design space about which we only know the generic structure of a node. It follows that, in the absence of additional knowledge, the only approach which a problem solving agent can take to solve the task is to search. Thus, by introducing the notion of design space, we introduce a problem solving framework which is completely method-independent and presupposes only the existence of a task specification. By instantiating this framework in terms of the concepts defined in the parametric design task ontology, we can then formulate a generic model of parametric design problem solving.
Transitions between design states are achieved in our model by applying design operators. A design operator is a generic concept which represents an elementary design step. Specific design methods may specialize design operators by including additional problem solving knowledge. For instance, a Propose&Revise problem solver refines the concept of design operator by differentiating between those design operators used during the Propose task and those used during the Revise task.
4.3.1. Basic goals and assumptions. The main objectives of the model presented here are: i) to identify the main tasks which characterize parametric design problem solving, and ii) to provide the `root node' of a library of methods for parametric design.
The first objective is based on the assumption that there exists a set of generic subtasks which is common to different methods for parametric design. This assumption is justified both by theoretical and empirical evidence. From a theoretical point of view the adoption of a search-centred framework constrains the number and the type of feasible problem solving activities. Empirical evidence is provided by existing surveys of design problem solvers (Balkany et al., 1993), which have uncovered generic problem solving activities which are common to different approaches.
The second objective has to do with developing a problem solving method for parametric design which subscribes to the given task and method ontologies, exhibits enough complexity to uncover the space of parametric design subtasks but at the same time avoids unnecessary control and ontological commitments. This method, named Generic-Parametric-Design, provides a kind of `method template', from which more specialized problem solving methods can be generated. Accordingly, in section 5 we will illustrate a number of methods which were constructed by refining and augmenting the generic problem solving model and which subscribe to the same generic control structure.
4.3.2. Method-generic control regime. Given the adopted search-based approach we can define a simple, but generically applicable control regime, which provides the main control structure of our problem solving model. This control regime - informally specified in figure 3[4] - initializes the design space and then iteratively performs a cycle in which a design state is selected according to some criterion and then subtask Design-from-State is invoked. This cycle is exited either when the design has been completed or when state selection fails.
The important feature of the control regime shown in figure 3 is that it is completely method-generic, i.e. all methods included in our library subscribe to it. Thus, it is possible to differentiate between alternative methods only on the basis of specific solutions to design subtasks, rather than in terms of the overall control regime. The advantage of this approach is that it is much easier to reason about functionally characterized behaviours than about different control regimes. Moreover, this approach also facilitates the process of mixing and matching problem solving components.
4.3.3. State evaluation. There are four main types of knowledge associated with a design state which might be needed by a problem solver: consistency (whether the model violates some constraints), cost, completeness (whether any parameter is unbound in the model), and feasibility (whether the state can lead to a solution). This breakdown is meant to provide maximal coverage - i.e. in our experience these four classes provide all the knowledge required to make decisions about the current design state. However not all problem solvers would require all four classes of knowledge. For example, some problem solvers are not concerned with cost issues.
4.3.4. State selection. At any stage of the design process, a problem solver (be it human or artificial) knows about a number of design states which are relevant to the problem in hand. Typically, these are the states which have been explored during the current design process, i.e. the states included in the portion of the design space searched so far. However, human designers are also capable of reusing past designs and the same applies to problem solvers which make use of case-based reasoning techniques when solving design applications (Zdrahal & Motta, 1996). Therefore, from a general point of view we assume that the input to task Select-Design-State refers generically to all the design states available to the problem solver, either because they have been explored during the current design process, or because the problem solver has access to other relevant design knowledge.
Assuming that a rational problem solver would not normally select a design state known to be unfeasible (a dead end), it follows that state selection is carried out in terms of the other three main criteria discussed in the previous section: completeness, consistency, and cost. In section 5 we will show that different state selection criteria account for the different behaviours of alternative PSMs - see also (Motta and Zdrahal, 1996).
4.3.5. State-centred design. By selecting a design state the problem solver decides which design model becomes the focus of the design process. Having focused on a model, a problem solver has to decide how to modify it, which requires a decision on which operator to apply to the current model. In general, there are various levels of decision-making required in order to reach a decision on the selection of a design operator. At the highest level of abstraction operator selection is driven by the current design context. This can be seen as a high-level abstraction which is useful to denote typical design scenarios. For instance a Propose&Revise problem solver distinguishes between two kinds of operators: procedures and fixes. If the selected design model is inconsistent, then the problem solver may choose one of the relevant fixes, otherwise it will choose one of the applicable procedures. To account for this behaviour we say that operator selection in a Propose&Revise problem solver is carried out in two different contexts: one in which design extensions are carried out, and one in which inconsistent models are revised.
Having selected the current design context, a problem solver then decides on which element of the current design model to focus the design process. We call this the design focus. For example, in the context of the revision phase a Propose&Revise problem solver focuses on the particular constraint violation which it is trying to resolve. If the context is one of model extension, then the design focus would be given by the parameter which is going to be assigned a value.
The notions of design context and design focus allow us to introduce two intermediate levels of decision making which are carried out after state selection and before the selection of a design operator. Thus, we can decompose task Design-from-State as shown in figure 4[5].
Space limitations do not allow us to discuss these subtasks in detail, therefore we only indicate the main decision-making aspects associated with them. Full details can be found in (Motta, 1998a). The control method associated with task Design-from-State provides the main differentiation in terms of control between different PSMs. Methods such as Propose&Backtrack (Runkel et al., 1996) exhibit a simple control structure which repeatedly selects and extends the selected state. Instantiations of the Propose&Revise class of PSMs carry out different actions, depending on whether the current context is 'propose' or 'revise' and whether they intermingle the two phases or carry out revisions only after model completion (Zdrahal and Motta, 1995).
Tasks Design-from-Context and Design-from-Focus provide generic control regimes at different stages of the design process. The former selects a design focus and invokes task Design-from-Focus; the latter selects and applies a design operator and evaluates the resulting state.
A listing of the main tasks included in the generic model of parametric design problem solving is given in table 1. The tasks are divided in four classes. Goal specification tasks are tasks which do not define a task body - i.e. they provide only a goal specification. Problem types are a subclass of goal specification tasks. Composite tasks introduce a task-subtask decomposition; primitive tasks solve a goal directly.
| Tasks | Type |
| Parametric Design | Problem Type |
| Generic Design Control | Composite Task |
| Design from State | Goal Specification Task |
| Reflect Design State | Goal Specification Task |
| Initialize Design Space | Composite Task |
| Select Design State | Goal Specification Task |
| Evaluate Design State | Composite Task |
| Evaluate feasibility | Primitive Task |
| Evaluate cost | Primitive Task |
| Evaluate consistency | Primitive Task |
| Evaluate completeness | Primitive Task |
| Extend design | Composite Task |
| Collect design foci | Goal Specification Task |
| Design from context | Composite Task |
| Select design focus | Goal Specification Task |
| Design from focus | Composite Task |
| Collect focus operators | Goal Specification Task |
| Order focus operators | Primitive Task |
| Select design operator | Goal Specification Task |
| Try design operator | Goal Specification Task |
| Apply design operator | Primitive Task |
The tasks shown in the table provide a set of high-level building blocks for constructing parametric design problem solvers. In our experience this set is quite complete. In particular we found that the only situation in which a new task needed to be added was when introducing new contexts. For instance, in order to model Propose&Revise we needed to add a task Revise-Context, associated with a revise context.
Table 2 shows a synoptic description of the main knowledge roles included in the generic method ontology associated with Generic-Parametric-Design. The classes shown in bold indicate the main domain roles associated with the framework. These roles can be filled by means of the appropriate application-specific knowledge, much as in the approach based on role-limiting methods (Marcus, 1988). Other types of domain knowledge, which are shown in bold-italics, denote optional roles, which are useful to improve the efficiency of the problem solving process, but are not essential to develop an application. Finally, the roles shown in plain text indicate intermediate knowledge structures generated during a problem solving process.
| Knowledge Classes | Description |
| Design Operator | Knowledge for modifying design models |
| Design Space | The space of all design models considered by a problem solver |
| Design State | An element of the design space |
| Design Context | Abstract label associated with a design state which can be used to decide the next problem solving step. |
| Design Focus | Abstract notion which denotes the main design element driving the selection of a design operator. |
| Focus Selection Knowledge | Knowledge used to select a design focus |
| Operator Selection Knowledge | Knowledge used to select a design operator |
| Available Parameter Values | Knowledge which supports the generation of the values available for an unbound design parameter. |
Table 3 applies our method description template to an instantiation of the Generic-Parametric-Design PSM described in the previous section. This PSM makes use of a depth-first search strategy as well as focus selection and operator selection knowledge. The former is used to minimize backtracking and the latter to perform local optimizations. It only considers one design context, extend, and its state selection policy always select the maximal, consistent and feasible design model.
| State selection & processing | ||
| State Selection Policy | 1) Violated constraints: No
2) Design model: Max |
|
| Contexts | Extend (Extend incomplete state) | |
| Focus Types | Parameter | |
| Knowledge requirements | ||
| Design Operator Types | Design extension operator | |
| Problem Solving Knowledge | Focus Selection Knowledge
Operator Selection Knowledge Available Parameter Values (Cost Function not needed) |
|
| Global properties | ||
| Reachable Design Space | All feasible states generated by the depth-first search. | |
| Completeness, Optimality | Complete, optimizes design operator selection | |
It is interesting to note that because of the state-based control regime used, this method does not require a global cost function. At each cycle of the design process, the state selection mechanism will always return either zero or one states which are consistent and maximal and therefore any further cost-based discrimination would be unnecessary.
5.1.1. Propose&Backtrack. Propose&Backtrack is the method used by (Runkel et al. 1996), to solve the VT problem without resorting to the use of fixes. This method implements a simple depth-first control regime in which, at each step of the design process, unassigned parts are selected and assigned. The assignment is carried out by selecting a value from the value range of the selected parameter (part). If the assignment results in an inconsistency, a different value is tried. If there are no values left, chronological backtracking is used to go back to a consistent state. When deciding which value to assign to a part, Propose&Backtrack assumes the existence of local preference knowledge, which can be used to rank available parameter values. In the case of the VT application, this knowledge is based on the cost assigned to the relevant procedures and fixes.
As shown by the template in table 4, Propose&Backtrack is essentially the same PSM as Generic-Parametric-Design. Like the latter, Propose&Backtrack makes use of local preference knowledge to make 'good' design extensions, and on chronological backtracking to go back and explore alternatives paths to a solution, when an inconsistency or a dead end is encountered. Therefore, its performance relies on two crucial aspects of the problem: that the available local preference knowledge is effective in guiding the search process, and that the problem exhibits only a weakly connected constraint network. These are pretty strong assumptions, which are rarely jointly satisfied except in relatively simple parametric design problems. For instance, chronological backtracking is too weak a control regime to tackle VT efficiently (Runkel et al., 1996), while we also found the available local preference knowledge in the KMI office allocation problem[6] (Motta, 1998a) was inadequate to achieve a good solution by means of Propose&Backtrack. However, in those cases where the constraint network is only weakly connected (Sadeh and Fox, 1996), as it is the case with the Sisyphus-I office allocation problem (Linster, 1994), then Propose&Backtrack can be used to generate solutions to the problem quite efficiently[7], even if these are not necessarily optimal.
| State selection & processing | |
| State Selection Policy | 1) Violated constraints: No
2) Design model: Max |
| Contexts | Extend |
| Focus Types | Parameter (Part) |
| Knowledge requirements | |
| Design Operator Types | Design extension operator |
| Problem Solving Knowledge | Preference knowledge for value ranges
Available Parameter Values |
| Global properties | |
| Reachable Design Space | All feasible states generated by the depth-first search. |
| Completeness, Optimality | Complete, optimizes design operator selection |
5.1.2. Propose&Revise. A problem with the two methods described so far is that they both rely on a uniform problem solving approach. As Stefik (1995) points out, "Seldom does a single search method provide an adequate problem-solving framework for a complex task." In particular a uniform problem solving approach inevitably restricts the types of problem solving knowledge which can be applied to the problem. For this reason researchers have developed problem solving methods which distinguish between multiple phases and introduce a richer variety of knowledge structures. A famous example of such an approach is Propose&Revise (Marcus and McDermott, 1989), which differentiates between design extension and revision and introduces the appropriate knowledge roles for both phases.
Given that all design methods contain a model extension phase, the main contribution of the Propose&Revise class of methods is in the introduction of the revise task, which modifies pre-existing assignments by means of special-purpose design modification operators called fixes.
Applying fixes can be understood as performing knowledge-based backtracking (Marcus et al., 1988). Another way to look at fix application is by adopting a state-centred viewpoint. If we take this view then the main novelty of a Propose&Revise approach is that it does away with the assumption that only consistent states can be found on a solution path (i.e. a path from an initial to a goal state). This principle of constraint violation tolerance opens up a number of possible strategies for design problem solving. For instance this principle can be instantiated in case-based design by relaxing the constraint that only consistent design models need to be stored in a library of cases. In such a scenario, a case-based design problem solver could select the design model in the library which most closely match the current specification (Zdrahal and Motta, 1996), regardless of consistency issues, and then repair eventual inconsistencies by means of repair methods (Minton et al., 1992).
As discussed in detail in (Zdrahal and Motta, 1995), several approaches to design revision are possible within the basic Propose&Revise approach. However, we can abstract from specific architectures and characterize the class of Propose&Revise in generic terms. Such characterization is shown in table 5.
| State selection & processing | |
| State Selection Policy | 1) Design model: Max
2) Violated constraints: Min 3) Cost: Min |
| Contexts | Extend, Revise |
| Focus Types | Parameter (Extend), Constraint (Revise) |
| Knowledge requirements | |
| Design Operator Types | Design extension operator, Fix (Revise) |
| Problem Solving Knowledge | Fixes, operator cost, available parameter values |
| Global properties | |
| Reachable Design Space | All feasible states (Propose), Revision space (Revise) |
| Completeness, Optimality | Method-dependent |
As shown in the table Propose&Revise refines our generic model by differentiating between extend and revise contexts and between design extension and design revision operators. This differentiation of course introduces flexibility in the problem solving process and allows for specialized problem solving knowledge. However, the most important aspect which emerges from the table concerns the state selection policy used by Propose&Revise problem solvers, which gives priority to the size of design models over cost and consistency. Intuitively, the idea of a Propose&Revise approach is that backtracking needs to be avoided: the currently most complete model should be operated on, even if it is inconsistent. Thus, we can say that Propose&Revise introduces a paradigm shift from a consistency-oriented to a completeness-oriented approach to design problem solving.
Issues of completeness and optimality cannot be discussed for Propose&Revise as a class but are associated with specific instantiations. For instance, the Propose&Revise method originally developed by Marcus and McDermott (1989) checks for inconsistencies after each model extension step and revises the design model as soon as an inconsistency is found. We call this control regime Extend-Model-then-Revise (EMR) (Zdrahal and Motta, 1995). As discussed in (Motta and Zdrahal, 1996) EMR prunes heavily the search space while not providing a sound converging criterion and is therefore an incomplete method. Motta (1998a) describes an alternative to EMR, which gently degrades to depth-first search if a fix application fails (and is therefore complete).
Only local optimality is typically provided by Propose&Revise methods, such as EMR. However, it is possible to define an instantiation of the Propose&Revise approach which makes use of a global optimality criterion when searching the revision space. The resulting PSM, CMR-A*, is described in the next section.
5.1.3. CMR-A*. An alternative to EMR is the Complete-Model-then-Revise (CMR) approach (Zdrahal and Motta, 1995), in which revision only takes place once the design model has been completed. An advantage of CMR is that because all constraint violations are tackled together, after the completion of the design extension process, it is therefore possible to reason about the relations between constraints, parameters and fixes, and about the fix application process itself. For instance it is possible in a CMR approach to make use of techniques such as the min-conflict heuristic, which improve the efficiency of the constraint satisfaction process in the average case (Minton et al., 1992).
The CMR-A* method uses an A*-style search during the revision phase (Zdrahal and Motta, 1995). The important aspect of this method is that its state selection policy adopts a cost-centred strategy. Thus, the method sacrifices quick convergence criteria (choosing the maximal design state) for cost minimization. This method is characterized in table 6.
| State selection & processing | |
| State Selection Policy | 1) Design model: Max
2) Cost: Min |
| Contexts | Extend, Revise (Heuristic cost control) |
| Focus Types | Parameter (Extend), Constraint (Revise) |
| Knowledge requirements | |
| Design Operator Types | Design extension operator, fixes |
| Problem Solving Knowledge | Heuristic cost function, heuristic search control, fixes, operator cost, available parameter values |
| Global properties | |
| Reachable Design Space | All feasible states generated so far |
| Completeness, Optimality | Complete, global optimization over the revise space |
5.1.4. Propose&Improve. Another way of introducing differentiation in the problem solving process, without sacrificing a consistency-oriented approach is by means of the Propose&Improve class of methods (Motta, 1998a) - see table 7.
| State selection & processing | |
| State Selection Policy | 1) Violated constraints: No
2) Design model: Max 3) Cost: Min |
| Contexts | Extend, Improve |
| Focus Types | Parameter - Unassigned (Extend), Most expensive (Improve) |
| Knowledge requirements | |
| Design Operator Types | Design extension operator, design modification operator |
| Problem Solving Knowledge | Focus selection, operator selection, available parameter values, detailed cost function |
| Global properties | |
| Reachable Design Space | All feasible states generated so far (Propose), Currently best state (Improve) |
| Completeness, Optimality | Complete, globally optimal with respect to 'improve' phase |
The basic idea underlying Propose&Improve is that optimality can be achieved or approximated by dividing the problem solving process into two phases: a 'propose' phase, which is concerned with finding a solution, and an 'improve' one which attempts to improve it. This problem solving method is an example of using a 'pick and mix' approach The propose phase is carried out as in a Propose&Backtrack method, i.e. as a search process driven by local preference knowledge, with backtracking when inconsistent model is encountered. The 'improve' phase consists of a global hill-climbing process which identifies the solution components which are currently most expensive, and then uses specific improvement operators to modify them. As in the case of Propose&Revise, a Propose&Improve method can be defined as a specialization of Generic-Parametric-Design, simply by introducing the relevant contexts and operator types.
Propose&Improve is particularly suitable for parametric design problems in which optimality is an important solution criterion and which are characterized by a dynamic cost function - i.e. a cost function in which the cost of an assignment can only be fully evaluated once a number of other assignments have been completed. This situation often arises in resource assignment problems, such as timetabling and office allocation (Motta, 1998a).
In the previous sections we have shown how different methods can be characterized as specializations of our framework and compared in terms of their knowledge requirements, global and state-related properties. These descriptions can be used to understand and differentiate the behaviours of alternative methods. For example, as discussed in detail in (Motta and Zdrahal, 1996) it is easy to see that the better competence exhibited by CMR-A* over EMR and CMR in the VT application was due to the incomplete nature of the search policies used by EMR and CMR - in particular the non converging criterion used for state selection.
The uniform description of PSMs afforded by our framework also makes it possible to understand better the nature of the problem solving knowledge used by different PSMs. For instance, our framework characterizes fixes as specialized operators for a revision context and isolates this notion from specific approaches to searching the revision space. In particular, when we configured our generic model of Propose&Revise problem solving to develop a rational reconstruction of the EMR method used by Marcus et al. (1988) we found that the there was no need to introduce the distinctions between incremental and non-incremental fixes and between fixes and fix combinations discussed in (Yost and Rothenfluh, 1996). These distinctions do not denote types of problem solving knowledge which are relevant to a knowledge-level analysis of Propose&Revise; instead they specify a particular search strategy, which consists of navigating a revision space in a cost-conscious way (Motta, 1998a).
We have also shown that our framework provides engineering leverage supporting a specialization-oriented process of PSM specification. In particular, the notions of design operator, design focus and design context provide very powerful abstraction mechanisms for defining new PSMs. For instance, less than 10 definitions were needed to define an EMR-style PSM as a refinement of Generic-Parametric-Design. These definitions were introduced to define i) the class of fixes as a refinement of class design-modification-operator; ii) a method associated with task Design-from-State specifying the EMR control regime; and iii) the relevant methods required to specify focus and operator selection and collection in a revise context.
Figure 5 shows the space of the main classes of PSMs which we have modelled in our library. The taxonomy is based on two criteria: whether or not a method's state selection policy only considers consistent states (CVi is always empty), and whether a method pursues local or global optimization policies. Of course, the figure only reflects some interesting points in the space of the PSMs and is not meant to circumscribe the coverage of the library. Endless possibilities for PSM configuration are available, by 'mixing and matching' different method components (e.g. we have defined a Propose-Revise-Improve method). Moreover, the figure does not include a number of case-based PSMs which we have also developed (Zdrahal and Motta, 1996). To date we have built and made use of eighteen different PSMs out of library components.
Sisyphus-I is quite a simple problem which we used as a test case for trying out several PSMs. In particular, we found that a simple dynamic search rearrangement heuristic (Dechter and Meiri, 1989) was able to account for all but one of the problem solving steps of the virtual domain expert (Siggi). Moreover, by applying the A*-propose PSM to the problem, we found that the solution reached by Siggi was not optimal.
The reuse of various versions of Propose&Revise developed for the VT problem to the sliding bearing design and simple mechanics problems was straightforward and required only simple domain mappings.
Tackling the KMI office allocation was more complex, given that the relevant optimality criterion (minimizing the distance between each KMI member and his collaborators across a number of 'affinity groups') was non-monotonic. In particular, we found that approaches based on local optimization did not produce very good solutions to the problem and that A*-type search was too expensive. As a result, we devised the Propose&Improve PSM, which performed much better than other alternatives.
Initial vehicle design, design and selection of casting technology and sheet metal forming technology for manufacturing mechanical parts are large applications being developed in cooperation with industrial partners. In all these cases application development includes selecting and adapting method components from the library to make use of application-specific problem solving knowledge as well as to integrate additional tools (databases, simulation packages etc.). The preliminary results indicate that this technology leads to significant improvement in the efficiency of the design process (worst improvement by a factor 10).
The generality of the approach taken in the Common KADS library essentially defines both the strengths and weaknesses of the Common KADS approach. It makes it possible to account for different approaches to modelling and to library organization but necessarily it only provides fairly weak principles for structuring a library. In contrast with the CommonKADS approach, our library has a clear, task-independent theoretical basis, which combines ontological engineering with a search model of problem solving.
The basic principle of task-method structures is that given a task it is possible to find a number of methods which can be used to solve it. However, these approaches do not provide a model by which alternative methods can be compared and contrasted. As a result it is quite difficult to get the task-method structure right (Orsvärn, 1996). In contrast with these approaches our library is based on a 'most generic PSM' of which all other methods are specializations. This method-generic, but task-specific model is in turn based on a model of problem solving as search. As a result the whole library has a strong structure. Any new method added to the library has to be formulated in terms of the overall model of parametric design problem solving. This approach is consistent with the principle of method generality suggested by Orsvärn: method adaptation is difficult and therefore should be avoided. Hence, PSMs should be as generic as possible. This principle, in its informal connotation, applies to the library of method components presented in this paper.
An important difference between the DIDS approach and ours is that we seem to subscribe to alternative views of what constitutes reuse. For the DIDS researchers reuse consists of providing a very general problem solving method. However, the price for such generality is inefficiency - see solution #1 to VT problem (Runkel et al., 1996). In contrast with the DIDS approach, we believe that supporting reuse consists of providing a rich set of reusable mechanisms, which can be used in different problem solving scenarios to develop efficient problem solvers. This set is not meant to be minimal. On the contrary it is meant to be maximal and provide adequate leverage for developing efficient reasoners. For this reason our framework comprises a much more fine-grained breakdown of parametric design tasks than afforded by the DIDS tools and our library includes a variety of problem solving approaches, rather than just a constraint satisfaction engine.
A second difference between the DIDS approach and ours is that while our approach is based on a generic model of problem solving as search, the library of mechanisms in DIDS has been empirically constructed from an analysis of several configuration design systems (Balkany et al., 1993). However, as pointed out in (Motta and Zdrahal, 1996), the granularity of the mechanisms uncovered by this analysis varies significantly. The problem with such a bottom-up approach is that each system uses a different terminology, solves a different class of tasks - for instance arrangement vs. parametric design - and employs control mechanisms at different levels of abstraction. Therefore it is difficult to compare them. The approach we have taken here is different. We have specified exactly the class of tasks we are dealing with - parametric design - and then we have formulated the generic structure of the problem solving model appropriate for this class of tasks. This means that specific parametric design problem solvers can then be described by analysing how they carry out the generic tasks introduced by our framework.
In the future we plan to extend this approach by tackling other problem types, such as diagnosis. As discussed in this paper, the search model of problem solving is completely generic and therefore we do not envisage any problem in applying this approach to other areas. Of course, in order to model diagnostic problem solving we expect that we will need to introduce a higher degree of differentiation in the state space (i.e. multiple types of contexts and operators) than it was needed for tackling parametric design.
Recent work by Fensel and Motta (1998) builds on the approach described here by characterizing method specification as a process of navigating a three-dimensional space consisting of problem-solving paradigms, e.g. search; problem spaces, i.e. task ontologies; and domain assumptions, i.e. method ontologies. This navigation process can be carried out by formulating the relevant adapters (Fensel, 1997), which formalize individual PSM-building steps. This work aims to provide a comprehensive theory of problem solving methods, subsuming both task-independent and task-specific approaches, and integrating knowledge-based development with `conventional' software engineering approaches.
Finally, the library presented here provides the baseline resource for a large, collaborative research project, IBROW3 (Benjamins et al., 1998), which aims to develop web-based tools supporting KBS construction by reuse.
Balkany , A., Birmingham W.P. and Runkel, J.T. (1994). Solving Sisyphus by Design. International Journal of Human-Computer Studies 40, pp. 221-241
Benjamins, R. (1993). Problem Solving Methods for Diagnosis. PhD Thesis, Department of Social Science Informatics, University of Amsterdam.
Benjamins, R., Plaza, E., Motta, E., Fensel, D., Studer, R., Wielinga, B.. Schreiber, G., Zdrahal, Z. (1998): An Intelligent Brokering Service for Knowledge-Component Reuse on the World-Wide-Web. In Proceedings of the 11th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW'98), Banff, Canada.
Beys, P., Benjamins, R., and Van Heijst, G. (1996). Remedying the Reusability-Usability Tradeoff for Problem-Solving Methods. In Proceedings of the 10th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW'96), Banff, Canada, 9-14 November, 1996.
Bonnardel, N. and Sumner, T. (1996). Supporting Evaluation in Design. Acta Psychologica, 91, pp. 221-244.
Breuker, J. A. and Van De Velde, W. (1994). CommonKADS Library for Expertise Modelling. IOS Press, Amsterdam, The Netherlands.
Chandrasekaran, B. (1990). Design Problem Solving: A Task Analysis. AI Magazine 11(4), pp. 59-71.
Chandrasekaran, B., Johnson, T.R. and Smith, J.W. (1992). Task-Structure Analysis for Knowledge Modelling. Communications of the ACM, 35(9), pp 124-137.
Dechter, R., and Meiri, I. (1989). Experimental evaluation of preprocessing techniques in constraint satisfaction problems. Proceedings of the 11th International Joint Conference on Artificial Intelligence - IJCAI `89, pp. 271-277. San Mateo, CA, Morgan-Kaufmann.
Ehn, P. (1989). Work-Oriented Design of Computer Artefacts. Arbetslivscentrum, Stockholm.
Fensel, D. (1997). The Tower-of-Adapter Method for Developing and Reusing Problem-Solving Methods. In R. Benjamins and E. Plaza (Editors). Knowledge Acquisition, Modeling, and Management. Proceedings of the 10th European Workshop, EKAW `97. Lecture Notes in Artificial Intelligence 1319, Springer-Verlag.
Fensel, D. and Motta, E. (1998). Structured Development of Problem Solving Methods. In Proceedings of the 11th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW'98), Banff, Canada.
Fensel, D., Motta, E., Decker, S., and Zdrahal, Z. The use of Ontologies for Specifying Tasks and Problem Solving Methods: A Case Study. In Benjamins, R. and Plaza, E. (editors). EKAW `97, 10th European Workshop on Knowledge Acquisition, Modeling, and Management. Lecture Notes in Artificial Intelligence, Springer-Verlag, 1997.
Gennari, J. H., Tu, S. W., Rothenfluh, T. E., Musen, M. A. (1994). Mapping Domains to Methods in Support of Reuse. Proceedings of the 8th Banff Knowledge Acquisition Workshop, Banff, Canada, 1994.
Greenbaum, J. and Kyung, M. (1991). Design at Work: Cooperative Design of Computer Systems. Lawrence Erlbaum Associates, Hillsdale, NJ.
Gruber, T. R. (1993). A Translation Approach to Portable Ontology Specifications. Knowledge Acquisition, 5(2).
Hatala M. (1997). The OCML terminal. Technical report. Knowledge Media Institute, The Open University.
Klinker, G., Bhola, C., Dallemagne, G., Marques, D., and McDermott, J. (1991). Usable and Reusable Programming Constructs. Knowledge Acquisition 3, pp. 117-136.
Laird, J., Newell, A., and Rosenbloom, P. (1987). Soar: An Architecture for General Intelligence. Artificial Intelligence 33, pp. 1-64.
Linster M (1994). Problem statement for Sisyphus: models of problem solving. International Journal of Human-Computer Studies (1994) 40. pp. 187-192
Marcus S. (editor) (1988). Automatic Knowledge Acquisition for Expert Systems. Kluwer Academic.
Marcus, S. and McDermott, J. (1989). SALT: A Knowledge Acquisition Language for Propose and Revise Systems. Journal of Artificial Intelligence, 39(1), pp. 1-37.
Marcus, S., Stout, J., and Mc Dermott, J. (1988). VT: An Expert Elevator Designer that uses Knowledge-Based Backtracking. AI Magazine 9(1), Spring Issue, pp. 95-112..
Minton S., Johnson M.D., Philips A.B. and Laird P. (1992). Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58. (1992). pp. 161-205.
Motta E. (1998a) Reusable Components for Knowledge Models. PhD Thesis. Knowledge Media Institute. The Open University. UK. Available from URL http://kmi.open.ac.uk/~enrico/thesis/thesis.html
Motta, E. (1998b). An Overview of the OCML Modelling Language. Paper presented at the 8th Workshop on Knowledge Engineering Methods and Languages (KEML '98). Available from URL http://kmi.open.ac.uk/~enrico/papers/keml98.ps
Motta E. and Zdrahal Z. (1996). Parametric design problem solving. In Proceedings of the 10th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW'96), Banff, Canada, 9-14 November, 1996.
Murray, K. and Porter, B. (1988). Developing a Tool for Knowledge Integration: Initial Results. Proceedings of the 3rd Banff Knowledge Acquisition Workshop, Banff, Canada.
Newell A. (1990). Unified Theories of Cognition. Harvard University Press.
Newell, A. and Simon, H. A. (1976). Computer Science as Empirical Enquiry: Symbols and Search. Communications of the ACM, 19(3), pp. 113-126, March 1976.
Orsvärn, K. (1996). Principles for Libraries of Task Decomposition Methods - Conclusions from a Case-study. In Proceedings of the European Knowledge Acquisition Workshop, EKAW'96. Lecture Notes in Artificial Intelligence, 1076. Springer-Verlag, pp. 48-65.
Puerta, A. R., Egar, J. W., Tu, S. W., and Musen, M. A. (1992). A multiple-method knowledge-acquisition shell for the automatic generation of knowledge-acquisition tools. Knowledge Acquisition 4(2), 1992, 171-196.
Runkel, J. T., Birmingham, W. B. and Balkany, A. (1996). Solving VT by Reuse. International Journal of Human-Computer Studies 44 (3/4), pp. 403-433.
Sadeh, N. and Fox, M. S. (1996). Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 86(1), pp. 1-41, September 1996.
Schoen, D. A. (1983). The Reflective Practitioner: How Professionals Think in Action. New York, Basic Books.
Steels, L. (1990). Components of Expertise. AI Magazine, 11(2), pp 29-49.
Stefik, M. (1995). Introduction to Knowledge Systems. Morgan Kaufmann. 1995.
Valasek M. and Zdrahal Z. (1997) Experiments with Applying Knowledge Based Techniques to Parametric Design. ICED 97. Tampere. Finland.
Valente, A., Breuker, J. A. and Van De Velde, W. (1994). The CommonKADS Expertise Modelling Library. In Breuker, J. A. and Van de Velde, W., The CommonKADS Library for Expertise Modelling. IOS Press, Amsterdam, The Netherlands.
Van Heijst G., Terpstra P., Wielinga B. and Shadbolt N. (1992). Using Generalized Directive Models in Knowledge Acquisition. In Th. Wetter, K.-D. Althoff, J. Boose, B.R. Gaines, M. Linster and F. Schmalhofer (eds.) Current Developments in Knowledge Acquisition - EKAW '92 (Springer-Verlag) pp.112-32
Wielinga B.J., Akkermans J.M. and Schreiber A.TH. (1995). A Formal Analysis of Parametric Design Problem Solving. In Proceedings of the 9th Banff Knowledge Acquisition for Knowledge-Based Systems Workshop (B.R.Gaines and M.Musen eds.). pp. 37-1 - 37- 15.
Yost G.R. and Rothenfluh T.R. (1996). Configuring elevator systems. International Journal of Human-Computer Studies (1996) 44. pp. 521-568.
Zdrahal Z. and Motta E. (1995). An In-Depth Analysis of Propose & Revise Problem Solving Methods. In Proceedings of the 9th Banff Knowledge Acquisition for Knowledge-Based Systems Workshop (B.R.Gaines and M.Musen eds.). pp. 38-1 - 38- 20.
Zdrahal Z. and Motta E. (1996). Improving Competence by Integrating Case-Based Reasoning and Heuristic Search. In Proceedings of the 10th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW'96), Banff, Canada, 9-14 November, 1996.
[1] Here we use the term 'problem solving model', rather than 'problem solving method', to emphasize that, like generic algorithmic schemas in conventional software, this model may not be fully specified - e.g. it may abstract from specific control regimes.
[2] This statement does not imply that a problem solver effectively has to search (i.e. that it has to examine possible alternative paths to a solution). It only emphasizes that all problem solving behaviour can be modelled as a search through a state space. Hence, in contrast with approaches such as Soar (Laird et al., 1987), we do not use search as the basis for a computational problem solving architecture, but simply as a 'methodological device', which allows us to move from a problem specification to a generic problem solving model, without introducing additional problem solving commitments - see also discussion in section 2.2.
[3] A problem type is a high-level generic task describing a class of applications (Breuker and van de Velde, 1994). Examples of problem types include parametric design, fault diagnosis and resource assignment.
[4] We are giving an informal specification of this control task only for the sake of convenience. The components in the library are specified in OCML (Motta, 1998b), which is an operational modelling language.
[5] The figure only shows a subset of the tree of subtasks of Design-from-State - see (Motta, 1998a) for the complete task structure.
[6] This is a real-world office allocation problem which our institute faced when moving to a new building.
[7] Assuming that the appropriate focus selection knowledge or heuristics are used!