A principled approach to the construction of a
task-specific library of problem solving components
 
Enrico Motta and Zdenek Zdrahal
 Knowledge Media Institute
The Open University
Walton Hall, Milton Keynes, UK
E.Motta, Z.Zdrahal@open.ac.uk
 
Abstract. Many researchers have characterized knowledge based systems from three viewpoints: task, problem solving method and domain. In this paper we investigate the reuse of tasks and problem solving methods and we propose a model of how to organize a library of reusable components for knowledge based systems. In our approach we first describe a class of problems by means of a task ontology. Then we instantiate a search model of problem solving in terms of the concepts in the task ontology, to derive a task-specific, but method-independent, problem solving model. Individual problem solving methods can then be (re-)constructed from the generic problem solving model through a process of ontology/method specialization and method-to-task application. The resulting library of reusable components enjoys a clear theoretical basis and provides robust support for reuse. In the paper we illustrate the approach in the area of parametric design.

1. INTRODUCTION

Problem solving methods (PSMs) describe domain-independent reasoning components, which identify 'regularities' (e.g. generic tasks, inferences and knowledge roles) in the use of domain knowledge and can therefore be applied to different applications which share the same generic structure. Thus, PSMs provide an important focus for reuse in knowledge engineering: they can be used i) to structure the knowledge acquisition (KA) process (Marcus, 1988; van Heijst et al., 1992) and ii) to specify a reuse-centred model of application development, which (arguably) makes it possible to develop robust and maintainable applications (Runkel et al., 1996).

 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:

 

Figure 1. Moving from tasks to problem solving methods.

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.

2. MODELLING FRAMEWORK

Our modelling framework distinguishes between four generic types of KBS components: tasks, methods, domain and application. This organization informs both the structure of our library and that of the application models developed by reusing and configuring library components. In accordance with the discussion in the previous section our approach to developing a task-specific library of reusable problem solving components consists of the following three steps:
  1. Formalize the problem type[3] by defining the appropriate task ontology.

  2. Construct a general problem solving model associated with a problem type by instantiating a generic model of search in terms of the task ontology defined at step 1.

  3. Characterize individual PSMs (or PSM components) as specializations of the task-specific, search-based problem solving model developed at step 2.

 These steps are discussed in the next sections.

2.1 Characterizing a class of problems

Problem solving activities concentrate only on a limited number of entities in the world. The set of these objects, which can be either abstract or concrete, is called the universe of discourse.

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.

2.2 Task ontology + search = generic problem solving model for a generic task

Given an initial and a goal state, it is the specification of a suitable PSM, which describes a process for reaching a goal state from an initial one. These problem solving processes are typically described in terms of high level inference steps - e.g. design problem solving is often described as proposing, critiquing and modifying tentative solutions (Chandrasekaran, 1990). The problem with these descriptions is that they are defined in terms of conceptual operations, which differ from PSM to PSM and from task to task. Moreover, they introduce additional ontological commitments on top of those associated with a task specification - e.g. a Propose&Revise model of design problem solving assumes the existence of the relevant procedures and fixes. What we need here is a generic epistemological model which allows us to characterize any generic problem solving process applicable to a task specification. This model should generalize from any specific PSM by not introducing ontological commitments in addition to those associated with the relevant 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.

2.3 Integrating a problem solving method with domain knowledge

The modelling framework used for structuring the library construction process also supports reuse-centred application development. This consists of three major steps: i) instantiating a generic task ontology for a particular application, ii) selecting/configuring a suitable PSM and iii) integrating the chosen PSM with an application domain.

 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.

Figure 2. Overall modelling framework

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.

3. PARAMETRIC DESIGN PROBLEMS

A parametric design problem can be defined as a mapping from a six-tuple <P, Vr, C, R, Pr, cf> to a set of solution design models, {Dsol-1,......., Dsol-n}, where

 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).

4. A MODEL OF PARAMETRIC DESIGN PROBLEM SOLVING

As illustrated diagrammatically in figure 1, our modelling framework uses the selection of a generic problem solving paradigm (search) as an epistemological device to bridge the gap between the task and method dimensions. In the context of parametric design applications, our objective is to develop a search-oriented model of parametric design problem solving which can provide both a 'most generic PSM' for parametric design and an initial, highly generic, method ontology for parametric design problem solvers.

4.1 Parametric design as search

Searching in a parametric design context means to navigate a design space comprising a number of design states. These are uniquely defined by the associated design model.

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.

4.2 Design operators as primitive design steps

Each design state describes a certain model of the artefact. In the initial state, the model is very vague since only design requirements are known. In a solution state the artefact is fully specified, all requirements are satisfied and no design constraint is violated. Our task-oriented characterization of a design space describes the design space declaratively but does not provide any procedural instruments for defining transitions between states. Without means for state transitions the problem solving method would not be able to incrementally construct a solution to the task. Thus, the notion of state transition is crucial to introduce a problem solving element in the task-oriented definition of a design space given above.

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 A generic problem solving model for parametric design

In (Motta and Zdrahal, 1996) we presented a preliminary version of a generic model of parametric design problem solving, developed in accordance with the methodology discussed in section 2. In this section we re-emphasize the main points from that presentation and illustrate a more complete specification of the model.

 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.

Figure 3. Informal specification of Generic Design Control

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.

Figure 4. Subtasks of Design-from-State

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 
Table 1. Tasks in parametric design.

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 2. Problem solving knowledge for parametric design.

5. ORGANIZING A LIBRARY OF PROBLEM SOLVING METHODS

The model of parametric design problem solving presented in the previous section is defined in terms of a number of generic tasks which provide useful building blocks for re-engineering existing problem solving methods for parametric design and for constructing new ones. In this section we will use these building blocks to model a number of parametric design methods. In particular we will show that this uniform view of problem solving methods provides a number of advantages, including: (i) a common framework suitable for comparing and contrasting different methods, (ii) an organizational schema providing the overall structure of a library of reusable problem solving components and (iii) a search-centred interpretation model which can be used to understand the problem solving role played by the mechanisms and knowledge structures employed by problem solving methods - e.g. the fix mechanism in Propose&Revise.

5.1 Structuring problem solving methods

In what follows we will characterize the methods in the library in terms of a generic method description template which considers a method's knowledge requirements, its approach to state selection and processing, and its global properties, such as completeness and optimality. We use this particular template for the simple reason that it provides all the information we need to understand what a PSM can provide (global properties), what knowledge it requires (knowledge requirements) and how it behaves (state selection and processing). Of course, it is important to keep in mind that the library does not comprise monolithic PSMs, but rather method components (e.g. generic tasks) and ontological definitions which can be easily combined to produce hundreds of alternative PSMs. Therefore, when talking about a "PSM in the library" we are really only indicating a particular configuration of method components which is interesting from some viewpoint.

 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 

Table 3. Synoptic description of Generic-Parametric-Design.

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 

Table 4. Propose&Backtrack

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 

Table 5. Propose&Revise

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 

Table 6. CMR-A*

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 

Table 7. Propose&Improve

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).

5.2 Summing up

Earlier we said that the approach we have taken to constructing and organizing a library of reusable components for parametric design provides the following benefits: i) a common framework suitable for comparing and contrasting different methods, ii) an organizational schema providing the overall structure of a library of reusable problem solving components and iii) an interpretation model which can be used to understand the problem solving role played by the mechanisms and knowledge structures employed by different problem solving methods.

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.

 

Figure 5. Taxonomy of problem solving methods for parametric design.

6. APPLICATIONS

Our application domains include the Sisyphus-I (Linster, 1994) and KMI (Motta, 1998a) office allocation problems, the VT elevator design problem (Yost & Rothenfluh, 1996), sliding bearing design, problems of simple mechanics (Hatala, 1997), initial vehicle (truck) design, design and selection of casting technology and sheet metal forming technology for manufacturing mechanical parts (Valasek & Zdrahal, 1997).

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).

7. RELATED WORK

The work discussed here is relevant to several areas of research, including knowledge modelling, knowledge acquisition and design problem solving. Here we will only compare our work to other approaches to the organization of PSM libraries. A comparison between this and related work on design can be found in (Motta and Zdrahal, 1996; Motta, 1998a). A more comprehensive review of other approaches to knowledge modelling can be found in (Motta, 1998a).

7.1 Comparison with Common KADS library

The most comprehensive generic library of model components is the one produced as a result of the Common KADS project (Breuker and Van de Velde, 1994). It consists of three main classes of library components: modelling components, modelling operators, and generic models. Generic models are "complete expertise models" (Valente et al., 1994); modelling components are elements of expertise models; and modelling operators are relations between generic models. These specify a possible transformation of a generic model. Modelling operators are included in the library to ensure that not only the results, but also the model building steps involved in a model construction exercise are captured by the library.

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.

7.2 Comparison with libraries based on task-method structures

A number of researchers have developed libraries of PSMs structured as task decomposition hierarchies (Steels, 1990; Chandrasekaran et al., 1992; Puerta et al., 1992; Van Heijst et al., 1992; Benjamins, 1993). While the details of the various approaches differ in various respects, the basic idea is essentially shared by all these approaches. Constructing a problem solving method for a specific application consists of recursively navigating a task-method decomposition tree, and at each stage selecting one of a number of possible methods applicable to a task. This selection can be done at run-time or during the design phase.

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.

7.3 Comparison with DIDS library

The DIDS system (Balkany et al., 1994; Runkel et al., 1996) provides domain-independent support for building design applications. The system is based on a generic model of configuration design problem solving, which defines the generic data structures and tasks, called mechanisms in the DIDS terminology, required for building design applications. The work presented here has a number of similarities with the DIDS approach. Both frameworks are based on a view of design as search through a design space and we share with the DIDS researchers the goal of generating a set of reusable components for design applications.

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.

8. CONCLUSIONS AND FUTURE WORK

In this paper we have discussed a framework for application development and for organizing a library of reusable components. This framework draws from various KBS technologies/approaches, including ontologies, problem solving methods, search, KA as modelling and KBS reuse. In particular our approach identifies the different types of knowledge which comprise an application model, provides a clear theoretical basis to the development of a library of reusable components, and imposes a uniform model of problem solving which makes it easier to understand, compare, contrast and 'plug & play' problem solving components.

 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.

ACKNOWLEDGEMENTS

This paper has benefited from in-depth criticisms/suggestions by Dieter Fensel, Bob Wielinga, Nigel Shadbolt, Tamara Sumner and several anonymous reviewers for KAW and IJHCS.

REFERENCES

Balkany A., Birmingham W.P. and Tommelein I.D (1993). An Analysis of Several Configuration Design Systems. AI in Engineering, Design, and Manufacturing, 7, pp. 1-17.

 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.

FOOTNOTES

 [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!