Redesigning a Problem-Solver's Operations to Improve Solution Quality

1 Introduction

Research on unification of problem solving and learning has led to the development of several learning methods for im­ proving problem-solving efficiency (e.g., [Mitchell et al., 1981 ]). These methods typically assume that the set of avail­ able problem-solving operators is both complete and correct. The methods instead improve the control of processing, either by compiling sequences of operators into macro-operators or by acquiring better heuristics for their selection. In this pa­ per, we are interested in the complementary learning goal of improving the quality of the solutions a problem solver gen­ erates. Modifying the control of processing is, in general, insufficient for attaining this goal because the reason why a problem solver produces poor solutions often is that its op­ erators are incorrect. The specific research issue is as fol­ lows: given a problem solver that fails to produce solutions of a desired quality, and given desired solutions for problems for which it produced poor-quality solutions, what combina­ tion of knowledge and processing enables the identification of the incorrectly specified operators and their redesign, so that problem solver can deliver solutions of the desired quality?

Ashok K. Goel

College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 goel @cc.gatech.edu

To address this problem, we have developed a learning method based on a structure-behavior-function (SBF) model of a problem-solver's processing and knowledge. This model captures (i) the functional semantics of the problem-solver's tasks, (ii) the compositional semantics of its methods which recursively synthesize the inferences drawn by its operators into the outputs of its overall task, (iii) the domain knowl­ edge available to it, and (iv) the "causal" interdependencies between its tasks, methods and domain knowledge. This model-based learning method is implemented in AUTOGNOS­ TIC, a "shell" which provides a language for representing SBF models of problem solvers, and mechanisms for monitoring the problem solving, receiving feedback on the result, and, in case of failure, assigning blame and repairing the problem solver. AUTOGNOSTic's method for assigning blame for spe­ cific kinds of failure and identifying what operators to modify is described in [Stroulia and Goel, 1996]. In this paper, we focus on its method for redesigning the incorrect operators. AUTOGNOSTIC' S integration with ROUTER, a path-planning system, is used to illustrate the method.

2 SBF Models of Problem Solving

SBF models analyze the problem-solver's task structure its domain knowledge and their interdependencies. In this framework, the problem-solver's tasks constitute the build­ ing blocks of its problem-solving mechanism. The methods that it employs decompose its complex overall tasks into sim­ ~ler subta~ks. These, in turn, get recursively decomposed mt~ even simpler sub tasks until they become elementary rea­ sonmg steps, i.e., "leaf" tasks, directly accomplished by the problem-solver's domain operators.

A task is specified as a transformation from an input to an output information state. It is characterized by the type(s) of information it consumes as input and produces as output, and the nature of the transformation it performs between the two. A task's functional semantics partially defines the task's in­ tended correct behavior, by specifying the nature of the task's information transformation; it is expressed in terms of do­ main relations among the task's inputs and outputs. 1 Notice, that functional semantics is not simply a set of pre- and post-conditions for the application of an operator; it is rather a functional concept specifying how the task's output relates to its input. For a non-leaf task, the functional semantics of the subtasks into which the task is recursively decomposed, and the ordering relations that the decomposing methods im­ pose over them, constitute a partial description of a correct reasoning strategy for this task.

1 Th~ SBF la~gua~e presently allows up to ternary relations and a smgle quahficatwn level for the representation of functional semantics.

Methods can be thought of as general plans for how the solutions of low-level subtasks get combined to deliver those of higher-level tasks. Each method captures the semantics of the composition of a set of lower-level subtasks into a higher­ level task in terms of control, and information interdependen­ cies. The tasks' control interdependencies are a set of rela­ tions partially ordering their executions; their information in­ terdependencies are a set of information producer-consumer relations among them.

Finally, the SBF model of a problem solver captures the problem-solver's domain ontology, in terms of the types of objects that the problem solver knows about, and the relations applicable to them.

The Case Study: ROUTER, [Goel et al., 1994], the case­ study problem solver which will be used in this paper to illustrate AUTOGNOSnc's model-based learning method, is a path planner. Its spatial world model is organized in a neighborhood-subneighborhood hierarchy. High-level neigh­ borhoods describe large spaces in terms of major streets and their intersections, and get refined into lower-level neigh­ borhoods which describe both major and minor streets and their intersections but over smaller spaces. In addition to its world model , ROUTER contains a memory of past path­ planning cases, also organized around the neighborhood­ subneighborhood hierarchy. Figure 1 diagrammatically de­ picts part of ROUTER's SBF model. It illustrates the SBF specification of part of its task structure and domain knowl­ edge.

ROUTER's task, path-planning, is to find a path from anini­ tial to a goal location. To that end, ROUTER first identifies the neighborhoods in which these locations belong (elabo­ ration subtask). Then, it searches in its path memory, for a path that is close to the current problem (retrieval). If the two given locations belong in the same neighborhood, ROUTER may use the intrazonal-search method to search for a path be­ tween them. This method is essentially a breadth-first search within the common neighborhood of the two locations. Ini­ tially, ROUTER sets up as its current location the initial loca­ tion, and initializes its tmp-path to contain only this location. Then, by repeating the path-increase subtask, it incrementally expands the tmp-path. If, at some point, the tmp-path reaches the goal location, RouTER assigns its value to the path and returns it as the solution. If the given locations do not be­ long in a common neighborhood, ROUTER can either per­ form a hierarchical search in its neighborhood organization (interzonal-search method) or it can use the path it retrieved from its memory, as the basis for solving the current problem (case-based method).

3 Redesigning Incorrect Operators

The inability of a problem solver to produce solutions of the desired quality is revealed when, for some particular problem, it receives as feedback a desired solution different from the one it actually produced. The first subtask of our model-based learning method is to assign blame for the failure to a specific operator so that it can then proceed to redesign it.

3.1 Assigning Blame

Blame assignment is performed through a successively fo­ cused examination of the tasks and methods involved in the production of the solution. Beginning with the problem­ solver's overall task, the blame-assignment method evaluates whether the feedback and the task's actual input validate the task's functional semantics. If this is the case, it infers that the task in question should have produced the feedback, and the reason why it did not must lie within the subtasks in which it was decomposed. Based on the problem-solving trace, the last such subtask is identified and the blame assignment fo­ cuses on it. If the functional semantics of a particular task are violated by the feedback and its actual input, the blame­ assignment method attempts to infer alternative inputs which would make the feedback value valid with respect to the task's semantics. If such alternative inputs can be found, the actual inputs are considered undesirable, and the blame-assignment focuses on the earlier subtask responsible for their produc­ tion.

Identifying Over-Constrained Operators: If the blame as­ signment reaches a leaf task whose semantics is violated by the feedback solution and its actual input, and no alternative input can be found to make the feedback valid, then it pos­ tulates as one potential cause for the problem-solver's fail­ ure the over-constrained semantics of the task. The feedback solution exemplifies. a set of quality requirements which, al­ though in accordance with the overall behavior expected by the problem solver, conflict with the specification of the be­ havior delivered by a low-level operator. Thus, the feedback reveals an error in the information transformation that this particular operator was designed to accomplish in the con­ text of the overall task, since it prevents the production of an acceptable and desired solution.

Identifying Under-Specified Operators: Alternatively, the blame-assignment may reach a leaf task whose semantics is validated by the output desired of it as well as its actual output. This situation implies that the problem-solver's task structure is not sufficiently specified to produce the right qual­ ity of solutions. Thus, the blame assignment postulates that the cause of the failure might be the under-specified semantics of the task, which allows both the actual and the desired val­ ues to be produced, when only the latter conforms with the requirements on the quality of the problem-solver's solutions, as exemplified by the feedback.

3.2 Redesigning an Incorrect Operator

To address the learning tasks that arise from identifying an operator, under-specified or over-constrained with respect to the overall problem-solving task in service of which it is em­ ployed, a learning method must be able to formulate new functional semantics for this operator. That is, the learning method must be able to discover new functional concepts to characterize the relation of the operator's output to its input. In the former case, the new semantics will refine(specialize) the functionality of the faulty operator, in the latter one, it will extend(generalize) it. To that end, the model-based learning method we present in this paper relies first, on the examples of the behavior desired of the operator in the context of the overall task as exemplified by the feedback, and second, on its comprehension of the domain knowledge generally avail­ able to the problem solver.

Let us now see how the examples of the operator's desired behavior are generated. As it successively refines the focus of the investigation from the overall task to its increasingly specific subtasks, the blame assignment also "translates" the behavior desired of this overall task into behaviors desired of its subtasks. This translation occurs in two steps. In the first, when the investigation is focused from one task to the last subtask set up by the method used to accomplish it, the feed­ back becomes the output desired of the more specific subtask. In the second, when the investigation moves from a subtask to an earlier one, the feedback enables the inference of al­ ternative inputs for the current task which, then, become the outputs desired of the earlier one. Thus, by the time the blame assignment reaches an incorrect (i.e., under-specified or over­ constrained) operator, it has also produced an example of the behavior desired of this operator in the actual problem­ solving session, namely an input-output tuple, which, if pro­ duced by the operator, could lead to the production of the feedback desired of the overall task. In the case of an underspecified operator, the actual-input desired-output tuple con­ stitutes an example of the behavior desired of it, where the actual-inputactual-outputtuple constitutes an example of un­ desired behavior. In the case of an over-constrained opera­ tor, both the actual-input desired-output and the actual-input actual-output tuples constitute examples of desired behavior. Having such a set of positive and negative examples of the information transformation that the operator should perform, the next goal of the learning method becomes to discover a se­ mantics specification to characterize them in an abstract way.

Here, let us discuss how the comprehension of the do­ main knowledge is used in the redesign of faulty operators. The SBF specification of the problem-solver's tasks' seman­ tics is based on the domain relations known to the prob­ lem solver. In a sense, these domain relations provide the "terms" in which the information-transformation functions of the problem-solver tasks are expressed. By specifying the do­ main relations available to the problem solver, independently of whether or not they are used by its current task structure, the SBF model specifies the range of inferences that are possi­ ble in the problem-solver's domain. This specification of po­ tential inferences enables our model-based learning method to recognize new uses for the problem-solver's knowledge in characterizing the alternative information-transformation functions desired of its currently incorrectly specified oper­ ators.

Figure 2 depicts the algorithm for discovering a new se­ mantics with which to characterize a set of positive and neg­ ative examples of an operator's desired behavior. The learn­ ing method consists of two basic steps. First, it establishes a hypothesis space in which to search for possible alternative semantics for the incorrectly specified operator, and second, it successively evaluates the hypotheses in this space and col­ lects these semantics that correctly characterize the behavior desired of the operator.

Establishing a Hypothesis Space: Given the representation of the functional semantics of a task in the SBF language, the formulation of the semantics hypothesis space requires first, the identification of the possible domain relations on which this semantics may be based, and second, the identification of the information types which, in addition to the operator's output, may be mentioned in the semantics.

To address the first requirement, the method uses the SBF specification of the operator's output information, to infer in which type of object it belongs. Next, based on the SBF spec­ ification of this object type, it identifies the set of domain re­ lations relating this object type with other object types whose instances can be found among the set of available information types (line 1 of the algorithm shown in Figure 2). To address the second requirement, the method identifies the set of infor­ mation types, available to the problem solver when the incor­ rect operator is applied. To that end, it identifies the most spe­ cific method which invokes the incorrect operator, and then these subtasks of the method which should have already been accomplished before the operator is invoked. Then, the types of information that can be used in the description of the new functional semantics are the types of information consumed and produced by these subtasks (line 2). The final step in­ volves the formulation of hypotheses for the new semantics, using the set of available information types and the set of do­ main relations that may apply to them. For each domain rela­ tion, a semantics is formulated using as arguments the oper­ ator's output information and every other available informa­ tion whose type conforms with the type of the relation's other argument (line 3).

Evaluating the Semantics Hypotheses: Having formulated a set of potential semantics for the incorrect operator, the learning method proceeds to evaluate which of them actu­ ally characterize the operator's desired behavior, by evaluat­ ing which ones are validated by the positive examples of the operator's desired behavior and fail for the negative examples (line 4). Any of the semantics relations that fulfill these requirements can be used to respecify the incorrect operator. If no such semantics relation is found, the learning method uses the SBF specification of the object type of the operator's out­ put to infer its attributes and their corresponding values for the output actually produced and the output desired of it, and proceeds to repeat the above step sequence, in order to iden­ tify semantics in terms of the output-information's attributes (line 5). If again no semantics is found, the learning method extends the set of available information types by collecting the information types available in the context of a more gen­ eral method subsuming the incorrect operator (line 6).

4 An Example in RouTER

Let us now illustrate the above method with an example from ROUTER. RouTER is given the problem of going from (lOth center) to (walnut dalney). It produces the path (center lOth) (lOth atlantic) (atlantic walnut) (walnut dalney), and is given the shorter path (center lOth) (center mapple) (mapple dalney) (dalney walnut) as feedback.

Assigning Blame: AUTOGNOSTIC first evaluates whether or not the feedback path is valid with respect to the functional semantics of ROUTER's overall path-planning task (as shown in Figure I). The desired path begins at the initial intersection and ends at the final one, therefore, AUTOGNOSTIC infers that the desired value is within the class of solutions that ROUTER was intended to produce in this particular problem. Thus, it successively refines the focus of its investigation to increas­ ingly specific subtasks of the path-planning task which pro­ duce the path, that is, search and subsequently path-increase.

As it evaluates the semantics of path-increase, AUTOGNOS­ TIC notices that the feedback path does not have as its sub­ path the task's input tmp-path. The tmp-path selected in the last repetition of the loop was (center lOth) (lOth atlantic) (at­ lantic walnut), and it is not a prefix of the desired path. At this point, AUTOGNOSTIC infers that the desired path could not possibly have been produced by the path-increase task given the information it received as input. To infer alternative val­ ues for the input tmp-path which could enable the task at hand to produce the desired path, AUTOGNOSTIC uses the predicate for the inverse prefix-path relation, and infers that (center lOth) (center mapple) (mapple dalney) is one prefix of the desired path, which, if given as tmp-path to the path-increase subtask, could result in the feedback's production. Thus, the cause of the failure must lie within the subtask that produced the "wrong" tmp-path, i.e., the task tmp-path selection.

AUTOGNOSTIC focuses its investigation towards identifying why this earlier subtask did not produce the desired tmp-path. It evaluates its functional semantics for the tmp-path desired of it, and notices that it is satisfied. Indeed, the desired tmp-path belongs in the set of possible-paths, and therefore, it could have been produced by tmp-path selection. Since this is a leaf task, accomplished by an operator, AUTOGNOSTIC infers that the specification of the tmp-path selection operator is too general with respect to the quality of solutions desired of the overall path-planning task.

Redefining the tmp-path selection Operator: Indeed, if "short length" is a quality desired of the paths that RouTER produces, then its intrazonal-search method, which is essen­ tially a breadth-first search within a neighborhood, is inappro­ priate. Instead, a depth-first search method should be used to actively prefer short paths, and in order for that to happen, the tmp-path selection should be redesigned to prefer the short paths in the possible-paths list. Let us now see how AUTOG­ NOSTIC reaches this conclusion.

The blame-assignment step has localized the under­ specified tmp-path selection operator. It actually produced the Imp-path (center lOth) (lOth atlantic) (atlantic walnut), when it should have produced (center lOth) (center mapple) (mapple dal­ ney) in order for the overall path-planning to produce the feed­ back.

The next step of the learning method is to collect the types of information available to ROUTER when the tmp-path selec­ tion is accomplished. This set includes the inputs and out­ puts of the search-initialization subtask, the only subtask of the intrazonal-search method (i.e., the method invoking the incor­ rect operator) which precedes the operator. Thus, the set con­ sists of initial-zone, initial-int, possible-paths. These are the in­ formation types that can be used as terms in the new seman­ tics of the tmp-path selection operator, and they are a neigh­ borhood, an intersection, and a path respectively. Next, Au­ TOGNOSTIC collects the domain relations relating the above types of objects with paths, and formulates a set of poten­ tial semantics relations with these domain relations relating the initial-zone, or initial-int or possible-paths with tmp-path. Fi­ nally, it proceeds to evaluate whether any of these semantics characterizes the behavior desired of tmp-path selection. None of them does, so AUTOGNOSTIC proceeds to search for se­ mantics based on the attributes of the available information types. In this effort, it identifies a single candidate for the role of tmp-path selection semantics, namely the relation forall p in possible-paths, length(tmp-path)::; length(p ). AUTOGNOSTIC pro­ ceeds to redefine the tmp-path selection operator to perform the function suggested by its new semantics, i.e., to select from the set of possible-paths the shortest one to expand 2 . Then, after presenting ROUTER with the same problem for a second time and producing the desired path as output, AuTOGNOSTIC verifies the appropriateness of the new semantics.

5 Experimentation and Evaluation

Two important issues for unified problem-solvers and learn­ ers, such as AUTOGNOSTIC, are how well do their learn­ ing methods accomplish their learning tasks in individual problem-solving episodes, and whether the learning con­ verges to a stable design for the problem-solver. To test the efficacy of AUTOGNOSTIC's learning method in individ­ ual episodes, we gave AUTOGNOSTIC-on-ROUTER three (3) sequences of forty (40) randomly-generated path-planning problems. For each problem, we also gave as feedback the shortest path, where path length was measured by the num­ ber of discrete path segments in a path plan. We found that for all failed problem-solving episodes, in which ROUTER generated a path longer than the desired one, AUTOGNOS­ TIC succeeded in assigning blame and appropriately repair­ ing ROUTER. However, since AUTOGNOSTICis an incre­ mental learner, it suffers from the familiar problem of over­ generalization (and over-specialization) of the functional se­ mantics on the basis of a single example.

2 The "reprogramming" of the operator is done manually.

To test the long-term effectiveness of the learning process, after each of the above training sets, we gave AUTOGNOSTIC­ on-ROUTER a sequence of one hundred and fifty (150) ran­ domly generated path-planning problems. For each training set, and for each problem in the test set, we compared the quality of the solutions produced by the original and the mod­ ified ROUTER. The table below summarizes the results:

In these experiments, AUTOGNOSTIC modified ROUTER's tmp-path selection operator, as we described above, and two ad­ ditional operators invoked by the case-based and the interzonal­ search methods. This enabled ROUTER to perform a greedy search for short paths, which, for an almost canonical street network, returns the shortest path in most cases. In addition, AUTOGNOSTIC extended the size of ROUTER's neighborhoods to enable it to search through larger spaces in order to find shorter paths. That AUTOGNOSTIC modified the same three operators for all the different problems in the three experi­ ments suggests that AUTOGNOSTICis able to determine that only some operators are "faulty" in ROUTER's design. It also indicates that AUTOGNOSTIC does not keep on modifying the problem solver indefinitely, but stops when, after some explo­ ration and redesign, a good enough design is found.

6 Related Research

Although much of past research on unification of prob­ lem solving and learning has focused learning methods for improving problem-solving efficiency, recent work in the Prodigy [Carbonell et al., 1989] framework has also ex­ plored learning of problem-solving operators. Perez [1994] describes a learning method for improving the quality of a problem-solver's solutions. This method uses both a trace of the problem solving that led to the solution of less than the desired quality and a trace of hypothetical problem solving that would lead to a solution of the desired quality. It as­ sumes that the problem-solver's operators are correct and the cause of its failure to produce good solutions lies in its in­ correct operator-selection heuristics. Gil [ 1994] describes a method for identifying missing pre- or post-conditions in a problem-solver's operator specification. This is similar to the learning task of AUTOGNOSTIC, but different, since it does not modify the information transformation the incorrect operators perform. Wang [ 1995] describes a method for acquiring oper­ ators from problem-solving traces, where the GPS-like oper­ ators again are specified in terms of pre- and post-conditions, without any functional specification of the input-output rela­ tions.

While the learning methods in the Prodigy framework are trace-based, the learning methods in our theory are model­ based. In particular, AUTOGNOSTic' s learning methods use SBF models of problem solvers. We initially developed SBF models to capture the functional, compositional and causal semantics of physical devices [Goel 1991]. In AUTOGNOS­ ncwe have used the SBF modeling methodology to explic­ itly specify the tasks, methods, control of processing, and domain knowledge of problems solvers in a manner consis­ tent with Chandrasekaran' s framework of Generic Tasks and Task Structures [Chandrasekaran 1989]. CommonKADS [Wielinga et al. 1992] is another task-oriented framework for analyzing and describing problem solving. A major ad­ vantage of analyzing problem-solvers in terms of tasks and methods is that enable specification of the organization of problem solving, which in turns localizes the learning. Al­ ternative model-based methods, such as that of Castle [Freed et al., 1992], can only describe problem solvers performing a linear sequence of tasks, and, in addition, are limited in the learning tasks they address.

7 Conclusions

We have described a learning method based on SBF mod­ els of problem solvers which is able to identify incorrectly specified problem-solving operators, and to appropriately re­ design them. This method relies on the specification of the functional semantics of the problem-solver's tasks, the com­ positional semantics of the methods that combine the infer­ ences of its low-level operators into the outputs of its high­ level tasks, and its domain knowledge.

The learning method uses the specification of the func­ tional semantics of the problem-solver's tasks to establish the range of behaviors that the problem-solver's design is in­ tended to deliver. Also, by evaluating the functional seman­ tics of the problem-solver's subtasks relative to the solution desired of the problem solver, the learning method identifies which of the operators are incorrect with respect to the de­ sired solution. This also enables the learning method to infer the behaviors desired of these subtasks in specific problems, which are then· used as the positive examples in formulating their new functional semantics. Finally, the representation scheme for functional semantics in the SBF language enables the learning method to define the dimensions of the space of the new functions.

The SBF specification of the compositional semantics of the problem-solver's methods enables the learning method to limit the number of information interdependencies it exam­ ines, specifically by investigating only the tasks involved in the production of the undesired output. In addition, it en­ ables the incremental specification of the information types in terms of which the new functional semantics of the incor­ rect operator can be specified. Finally, the specification of the problem-solver's domain ontology enables the learning method to establish the set of information relations that can be used in the specification of these new functions.

Acknowledgments

This paper has benefited from numerous discussions with members of the Intelligence and Design research group at Georgia Tech. This work has been supported in part by re­ search grants from NSF (IRI-92-10925 and DMI-94-20405) and ONR (research contract N00014-92-J-1234) . ·