(Get Postscript file )

A Script-Based Approach to Modifying Knowledge-Based Systems

Marcelo Tallis
Department of Computer Science and Information Sciences Institute
University of Southern California
4676 Admiralty Way, Marina del Rey, CA 90292, USA, tallis@isi.edu


Modifying knowledge-based systems (KBSs) is a complex activity. One of its difficulties is that several related portions of the KBS might have to be changed in order to maintain the coherence of the system. However, it is difficult for users to figure out what has to be changed and how. This paper presents a novel approach for building knowledge acquisition (KA) tools that overcomes some of the limitations of current approaches. In this approach, knowledge of prototypical procedures for modifying KBSs is used to guide users in changing all related portions of a KBS. These procedures, which we call knowledge acquisition scripts (or KA Scripts), capture how related portions of a KBS can be changed coordinately. By using KA scripts, a KA tool would be able to relate individual changes in different parts of a KBS, enabling the analysis of each individual change from the perspective of the overall modification. The paper also describes the implementation of ETM: a script-based tool that builds on the EXPECT framework for building KBSs ([Gil1994]), discusses how we have addressed some important issues of this approach, and describes a preliminary empirical evaluation of ETM that shows that KA Scripts allow users to perform KBSs modification tasks more efficiently.

1 Introduction

Modifying knowledge-based systems (KBSs) is a complex and recurrent activity. Events like changes in the KBSs environment, new user requirements, debugging of inadequate knowledge, and the customization of KBSs to user preferences and institutional practices are some of the causes that make KBSs modifications the rule rather than the exception. Unfortunately, modifying a KBS is a complex task. One of its difficulties is that after changing portions of the KBS, other related portions might also need to be changed to conform to the former changes. Determining what other portions have to be changed and how to change them to conform to previous changes requires a deep understanding of how the elements of the KBS interact. This requirement is especially hard to fulfill if the rationale behind the design of a KBS or the details of its implementation are unknown, which is often the case due to staff migration or third party software development.

One way of lessening the burden involved in modifying KBSs is by using knowledge acquisition (KA) tools. Most standard knowledge acquisition tools assume that the knowledge-based system follows a predefined inference structure or problem-solving method (PSM), and they only support the addition and modification of the domain-dependent knowledge required by the problem-solving method ([Marcus and McDermott1989, Puerta et al. 1992, Runkel and Birmingham1993]). For instance, SALT ([Marcus and McDermott1989]) is a KA tool tailored to the propose-and-revise problem-solving method for solving system-configuration problems. SALT only supports the acquisition of the domain-dependent knowledge used by propose-and-revise such as procedures that propose initial values to different configuration parameters. By using knowledge that is specific to the problem-solving methods, these KA tools can provide a very strong support for modifying KBSs. However, its applicability is severely limited since a) they can only be used for a particular PSM, and b) they can only support modifications to the domain-dependent knowledge specified by the corresponding PSM.

There is another class of KA tools which provide support for a wider range of KBSs and modifications (e.g., [Gil1994, Yost1993]). These tools are independent of the method and do not restrict the type of modifications that can be done. The trade-off for this gain in flexibility is that they provide a weaker support. In EXPECT ([Gil1994, Swartout and Gil1995]), the expectations for guiding KBS modification are based on the understanding of the interactions among KBS components. Based in this understanding, EXPECT is able to suggest changes to the KBS that might fix inconsistencies introduced by prior modifications. However, these suggestions are generated regardless of what have caused the inconsistencies or what other changes have been done in other parts of the KBS. Consequently, these suggestions are too general to provide a precise guidance and the resulting support is weaker.

To develop a knowledge acquisition tool that both provides strong guidance to users and allow a wide range of modifications for any type of KBS, we investigated the use of an alternative source of expectations which is also problem-solving method independent: the understanding of prototypical procedures for modifying KBSs. These procedures, which we call knowledge acquisition scripts (or KA Scripts), capture how related portions of a KBS can be changed coordinately. They provide a context for relating individual changes to different parts of a KBS and hence enable the analysis of each change from the perspective of the overall modification.

We have developed an approach for supporting modifications of KBSs that uses a library of KA Scripts to guide a user in changing all related portions of the KBS in a consistent way. This approach is being implemented in a KA tool called ETM, a KA tool for modifying KBSs that builds on the EXPECT framework. ETM has been subject to some preliminary evaluations that have shown promising results.

In a previous paper ([Gil and Tallis1995]) we introduced the concept of a script-based knowledge acquisition tool and demonstrated it with an initial, simplified prototype. This paper presents recent findings from our work in designing and implementing ETM, a script-based KA tool. It discusses the research issues that we face and the right and wrong design decisions that we made. Additionally, it presents the results of our preliminary evaluation of ETM. This paper adds to [Gil and Tallis1997] the discussion regarding research issues and lessons learned from our experience in building ETM. It also contains a more comprehensive description of ETM.

The remainder of this paper is organized as follows. Section 2 discusses the difficulties involved in modifying KBSs and introduces an example that will be used throughout the paper. Section 3 introduces our script-based approach for supporting KBS modifications. Section 4 discusses the lessons learned through our experience in building a script-based KA tool. Section 5 presents some background on EXPECT, a framework for developing KBSs that we used for our work. Section 6 describes ETM, our implementation of a KA Scripts based tool. Section 7 elaborates the details of the KBS modification of section 2 and uses it to illustrate an application of ETM and its advantages over EXPECT. Section 8 describes the results of a preliminary evaluation that we conducted with several users. Finally, sections 9 and 10 discuss related work and conclusions.

2 Difficulties of KBS Modifications

Consider the following example from our experience concerning a KBS for transportation planning. Suppose that this system calculates durations of trips involving only ships, and that now it has to be extended to consider aircraft too. This modification requires several individual changes. First, existing knowledge may need to be modified. The description of vehicles used for trips has to be extended to include aircraft in addition to ships. The methods (or procedures) to estimate the duration of trips need to be changed to take into account aircraft. New knowledge may also need to be added. For example, new methods to calculate the round trip time of aircraft need to be added. In all these modifications, any new knowledge needs to be integrated with existing knowledge. The distance traveled is used in the new method for the round trip time of aircraft and in the already existing calculation for the round trip time of ships, so we need to make sure that they use consistent procedures for estimating this distance.

Notice that if the user makes only some of these changes, the knowledge base system will be left in an incoherent state that will preclude its ability to calculate duration of trips. For example, suppose that the description of vehicles is extended to include aircraft, but no methods to calculate the round trip time of aircraft are added. The system will no longer be able to estimate the duration of trips because it will not be able to compute the round trip time of the aircraft. There are several reasons why it is hard for a user to complete a modification:

In sum, modifying a knowledge-based system often requires several individual changes to various components, and all those changes must be carefully coordinated. A good starting point is to build knowledge acquisition tools that find problems with the knowledge-based system and alert users about them, and in fact, this is pretty much the kind of support that a conventional compiler provides to programmers when they change their code. But helping users notice the problems only partially addresses the issue. Ideally, KA tools should also support the user in resolving these problems by making suggestions about what additional changes may be needed in the knowledge base. To do so, the tool needs to have more context and some knowledge about the task that the user is trying to accomplish.

3 Script Based Knowledge Acquisition

Our approach is to equip a knowledge acquisition tool with knowledge acquisition scripts (or KA Scripts) that represent prototypical procedures for modifying knowledge-based systems. More specifically, a KA Script describes a prototypical sequence of changes for following up the consequences of previous changes to the KBS. An example of a KA Script is:

 if a) tex2html_wrap685
    b) tex2html_wrap687

then tex2html_wrap689

This script might seem obvious. However, a KA tool lacking this knowledge could not discern whether to fix the problem described in part b) of the KA Script by generalizing a method (as the KA Script does) or by specializing the unachieved goal. The later would be incorrect because it would retract a previous change. Furthermore, this KA Script indicates which method has to be modified.

Because there is not a unique way of following up the consequences of a change, there can be several KA Scripts that apply to the same situation. For example, an alternative KA Script that applies in the previous example is to create a new method for achieving the generalized goal rather than to change an existing method. KA Scripts can also be specific to particular situations. For example, a KA Script that applies in the previous examples, but in a more particular situation isgif:

 if a) tex2html_wrap691
    b) tex2html_wrap693

    c) tex2html_wrap695

    d) tex2html_wrap697

then 1) tex2html_wrap699

     2) tex2html_wrap701

A script-based KA tool supports users in modifying a KBS by suggesting and executing KA Scripts that take care of the consequences of each individual change. To support this functionality a KA tool needs to have access to the following kinds of information: In designing a script-based knowledge acquisition tool, the following research issues were found to be important. We have learned about these issues through our experience in building a script-based KA tool. Our earlier attempts for building a script-based KA tool showed some deficiencies that were finally corrected in our current implementation. Next section summarizes some of the design decisions that led us to the construction of a successful script-based KA tool, and some that did not.

4 Designing a Script-Based KA tool

To elaborate our library of KA Scripts, we first did a thorough analysis of the kinds of changes that can be done to a knowledge-based system, their possible consequences, and the successive changes that could follow up on those consequences. This analysis was done systematically by evaluating the consequences of modifying every constituent in the constructs used to represent knowledge in our framework. For example, we analyzed different types of changes to goals (e.g., modify one parameter), their possible consequences (it might not be possible to match that goal to a method), and their follow-up changes (e.g., change that same parameter in the method that achieved that goal before, and then change the body of that method accordingly). The result of this analysis was a complete set of KA scripts that followed up all possible consequences of changes. These KA Scripts cover all the situations in which a user can get when modifying a knowledge base. However, tests with our initial implementation showed that the guidance they provide to users is very general. The main problem is that they do not make good use of the context available, like particularities of the knowledge base (e.g., that the modified goal can be decomposed into two subcases) or the changes performed to other parts of the knowledge base.

To overcome this problem we tried a different approach. We analyzed several sample scenarios for modifying knowledge based systems. We looked at the changes that needed to be made, their consequences, and how subsequent changes followed those consequences. We analyzed what kinds of advice would have been useful to users at each point, and determined what information from the context was needed to generate the advice automatically. The result of this effort was a set of KA Scripts that, though incomplete, were more specific to the context and as a result provided more help to a user. We plan to continue finding more KA Scripts using this method.

Finally, KA Scripts produced by both methods were combined into a single library. Hence, there is always at least one general KA Script in the library that applies to a given situation. In situations where a more specific KA Script can also be applied, the guidance provided will be more specific to the context and more precise. The result of this effort was a library of 75 KA Scripts from which only a dozen have been implemented so far.

A KA Script library needs to have some structure to guide its development and to allow the tool to access relevant KA Scripts without examining the whole library. In our current implementation, KA Scripts are discriminated by the type of problems (or errors) that a KA Script could fix (e.g., a goal cannot be matched) and can further be discriminated by their requirements over past changes (e.g., a goal became more general) or the content of the KB (e.g., the unmatched goal can now be decomposed). Table 1 list the type of problems addressed by our KA Script library.


Table 1: Type of problems addressed by a KA Script library used to guide modifications of EXPECT knowledge bases

Our first attempt was to structure the library around type of changes to be followed up, but this produced scripts that were very cumbersome. The problem is that these changes can have very different consequences depending on the situation. Moreover, it turns out that the procedures for following up those changes are more dependent on these consequences that on the type of the change itself.

We also realized that the sequence of steps of a KA Script has to be short and simple, and not complicated with provisions for handling all possible consequences of its changes. It is better to attend these consequences in separate KA Scripts. The rationale behind this decision was also that a change can have very different consequences depending on the situation, and it is impractical to include provisions for handling all of them in every KA Script. In addition, shorter KA Scripts are easier for a user to understand and follow.

We let the execution of a KA Script to reach its end before attending the consequences of changes performed during its execution. Otherwise it would produce a high degree of nesting that would make it hard for users to follow what is happening. Another reason is that some of the problems generated in the middle of the execution of a KA Script are fixed naturally when the KA Script finishes its execution.

To avoid that the user lose the thread of what she is doing and to give her some control over the process, the user takes the initiative to start the execution of a KA Script when she considers appropriate (although the tool suggests which KA Scripts can be applied). In addition, she is free to make any change to the KBS between the execution of KA Scripts without being interrupted by the tool. To help the user follow the thread of the KA script without getting lost, the user interface shows all the steps in the current KA Script with indications of which steps have already been executed, which one is being executed now, and which are still pending.

We have built a script-based KA tool called ETM. ETM is a tool for supporting modifications of EXPECT KBSs which was also built integrated to the EXPECT system ([Swartout and Gil1995, Gil1994]).

5 EXPECT: a KBS Framework and Baseline KA tool

EXPECT is an environment for building and modifying knowledge-based systems. EXPECT provides three key capabilities: a KBS representation framework, a problem solving environment, and a KA tool. We introduce some aspects of EXPECT as we present an example knowledge base that is going to be used throughout the rest of the paper. More details about EXPECT can be found in [Gil and Melz1996, Swartout and Gil1995, Gil1994].

EXPECT's knowledge bases contain factual domain knowledge and problem solving knowledge. The factual domain knowledge represents concepts, instances, relations, and the constraints among them. It is represented in Loom [MacGregor1991], a knowledge representation system from the KL-ONE family. Problem solving knowledge is represented in methods which are procedural descriptions for achieving goals. They consist of 1) a capability that represents the general goal that the method can achieve, expressed with an action name and several parameters, 2) a method body that describes the procedure for achieving the method goal in the capability, and 3) a result type that specifies the type returned after elaborating the method body. Figure 1 shows examples from a simplified transportation domain. A vehicle is defined as a kind of major equipment that has a speed and can be either a ship or an aircraft. The method M2 specifies that in order to calculate the duration of a trip by ship from a location to another location we have to find the sailing distance between the locations (a subgoal that has to be achieved by other methods) and divide it by the speed of the ship.

Figure 1: Some definitions of concepts and problem solving methods in a simplified transportation domain.

Given a generic goal (referred to as the top-level goal) such as


estimate the trip duration of a transportation movement
EXPECT's problem solver automatically generates a domain specific KBS for solving instances of this goal, such us:


estimate the trip duration of the first movement from Fort Bragg to Ryad
Problem solving proceeds as follows: the top-level goal is expanded by matching it with a method and then expanding the subgoals in the method body. This process is iterated for each of the subgoals and is recorded as a derivation tree. Throughout this process, EXPECT propagates the constraints on the goal parameters performing an elaborate form of partial evaluation which is supported by Loom's reasoning capabilities. The derivation tree is then used by the EXPECT KA tool to support knowledge acquisition. One strong capability of EXPECT is that problem-solving is performed with generic goals (such as (1)). Hence, if EXPECT is able to solve the generic problem then it would be able to solve any instance of it. In addition, EXPECT can identify what knowledge is needed for solving problem instances. This ability drives knowledge acquisition.

In our example, method M1 needs to calculate the round trip time for the lift available for a transportation movement (subgoal CALCULATE). EXPECT will look at the role HAS-AVAILABLE-LIFT in definition of TRANSPORTATION-MOVEMENT and determine that the lift of a movement includes only ships, hence this goal can be achieved using method M2. In turn, method M2 needs to find the sailing distance between two locations (subgoal FIND), which can be achieved using method M3.

Using the derivation tree, EXPECT finds the interdependencies between domain facts and problem-solving methods, which are used to guide knowledge acquisition. For example, the derivation tree will annotate that in expanding M2 the speed of a ship is used. If a new ship is entered in the knowledge base and its speed is unknown, this will be considered as an error and the knowledge acquisition tool will ask the user to specify the speed. These interdependencies also help EXPECT's KA tool to detect errors or potential problems in the KB, such as goals that cannot be matched by any method, undefined parameter types, and method result types that are incompatible with what the method expansion actually returns.

All KB errors found by EXPECT are recorded in an agenda that reminds the user of what has yet to be fixed. EXPECT supports users in resolving these agenda items by explaining these errors and suggesting fixes to them. Besides the handling of errors, the EXPECT KA tool can also display different graphical presentations as well as natural-language descriptions of the KB and provides a menu interface for executing commands that modify the KB.

6 ETM: a Script Based KA Tool for EXPECT

We have implemented a Script-based KA tool that supports modifications of EXPECT KBSs. This tool, called Expect Transaction Managergif (or ETM), was built tightly integrated to the EXPECT's architecture for two reasons: a) to make use of EXPECT built-in analytical capabilities, in particular determination of interdependencies and identification of errors, and b) to allow users to use both, EXPECT's conventional tool and the script based tool. This last feature is essential because a user may always come up with new strategies to modify the KB that are not contained in the KA Script library. To perform this integration, EXPECT required only slight extensions. Namely, EXPECT's KA tool was modified to keep record of past versions of the KB and the history of modification commands executed so far.

We built ETM to help a user to bring a KBS back to a coherent state after a user had performed some initial changes to the KBS using EXPECT conventional KA tool (the KBS is assumed to be coherent before starting its modification). ETM engages in a loop in which 1) it identifies unattended consequences of previous changes, 2) suggests KA Scripts that take care of those consequences, and 3) guides the user throughout the application of one of these KA Scripts (chosen by the user). The completion of a modification usually requires of the execution of several KA Scripts. This is because some changes can have several consequences that have to be followed up by different KA Scripts, and also because of the cascading of changes (i.e., changes that followed up consequences of previous changes have their own consequences that require being followed up).

The overall control loop for the execution of KA Scripts is shown in Figure 2. The loop begins after the user has executed some changes to the KBS and requested the help of ETM to follow up the consequences of those changes. For each problem in the KBS caused by previous changes, ETM proposes KA Scripts that apply to that situation. If the user agrees with one of them then ETM, with the help of the user, executes it. If not, the user fixes the problem using EXPECT's basic KA tool.

Figure 2: ETM's Control Loop

Our goal is to automate as much as possible the application of KA Scripts. Although full automation is not possible, the tool can take care of significant parts of the process, leaving important high-level decisions to the user. Detecting which KA Scripts are applicable (including often several instantiations of a same KA Script) is a task that can be done by the tool. At any given time, there can be many problems in the knowledge base and several KA Scripts may apply for each problem. ETM guides the user by suggesting KA Scripts that will resolve problems that occur earlier during problem solving because after fixing these problems, the problem-solving process could continue in a different way. When several KA Scripts are applicable for the same problem, we leave the choice up to the user, since the appropriateness of a choice may depend on information that is not readily available to the tool (e.g., user's preferred strategy to modify knowledge bases). Finally, the execution of a KA Script is shared between the KA tool and the user.

Figure 3 shows in detail one of the KA Scripts in our librarygif. The representation of KA Scripts includes the following kinds of information:

Figure 3: KA Script example

7 An Example Scenario for KA Scripts

Suppose that the KBS of Figure 1 has to be modified because the available lift for transportation movements can now include aircraft besides ships. This modification requires five changes as depicted by Figure 4. First, in the definition of TRANSPORTATION-MOVEMENT, the range of the role HAS-AVAILABLE-LIFT has to be generalized to VEHICLE, which already includes both SHIP and AIRCRAFT. This is achieved with Action 1 (see Figure 4). The fillers of this role are one of the arguments of the goal CALCULATE in method M1, hence this argument changes automatically from SHIP to VEHICLE too. After this change, the goal CALCULATE in M1 cannot be matched any more with M2 (M2 applies only to ships). However, the new goal can be decomposed into two disjunctive subgoals, one for ships and the other for aircraft. In order to achieve the ship subgoal, the method that achieved it originally (M2) can still be used. This same method can also serve as a basis for constructing a new method for the aircraft subgoal. With Actions 2 and 3 the user creates this new method (M2-PRIME) by duplicating M2 and then modifying its copy (substituting SAILING-DISTANCE by FLYING-DISTANCE and adding the computation of the time that the aircraft spend in in-route stops). The new method contains two goals that cannot be achieved with the current knowledge: a modification of the goal FIND, whose argument SAILING-DISTANCE was changed to FLYING-DISTANCE, and the new goal COMPUTE. The user, with Action 4, creates a method (M3-PRIME) for achieving the modified FIND based on the method that achieved the original FIND (M3), and with Action 5 a new method (M4) for achieving COMPUTE.

Figure 4: KBS modification scenario

In sum, five changes in different parts of the KB were needed to modify the KBS. If some of these changes were omitted, the KBS would have been left incoherent. It is important to realize that these changes are difficult for a user to determine. For example, to determine that after generalizing the range of the role HAS-AVAILABLE-LIFT (Action 1), a method for calculating the round trip time for an aircraft has to be created (Action 2), the user needs to determine the following facts: 1) The fillers of the role HAS-AVAILABLE-LIFT are used in one parameter of the goal CALCULATE of method M1, 2) CALCULATE was achieved by M2, 3) M2 cannot achieve the variation of CALCULATE, and 4) CALCULATE can be decomposed into a subgoal for ships and another for aircraft. Many of these facts are supported by logic inferences like goal subsumption (e.g., whether goal CALCULATE can be decomposed into disjunctive subcases or not) what makes it even harder for users to figure it out.

The KA Script of Figure 3 could be applied to fix the problem caused by the first change of this scenario, ``Goal CALCULATE (of M1) cannot be matched'', and would suggest to the user Actions 2 and 3 of that scenario. It is applicable because: Action 1 caused that argument SHIP of CALCULATE changed to VEHICLE (condition (a)), this goal was achieved by M2 before (condition (b)), and now it can be decomposed into two subgoals, one for SHIP and another for AIRCRAFT (conditions (c) and (d)). Figure 5 shows ETM's user interface during the application of this KA Script.

Figure 5:  Snapshot of ETM's User Interface. The EXPECT's KA tool window is in the background overlapped by three other windows displayed by ETM during the execution of the KA Script of Figure 3. The back-most window shows the changes sequence of the KA Script. This snapshot was taken during the execution of change 2 (create a method analogous to the basis). On top of this window there is a window that guides the user step by step through the execution of this change. Finally, the front-most window is an ETM's suggestion for the first step (specify global substitutions for capability). Namely, substitute SHIP by AIRCRAFT and ?S by ?A.

EXPECT's original support for accomplishing this modification is limited. EXPECT reports the errors that are present in the KB and suggests solutions to them. However, these suggestions are too general. EXPECT generates suggestions from a model that relates errors with possible fixes. However, error information alone is not enough to provide precise suggestions. An understanding of how this error was originated as well as of how its fix will contribute to the overall modification is also required. For example, after the first change of this scenario, EXPECT will report that the goal CALCULATE in M1 cannot be achieved and will suggest three possibilities: 1) modifying M1, 2) modifying some other method's capability, and 3) creating a new method. It cannot specify that it is method M2 the one that has to be modified in suggestion (2) because it does not know which method used to achieve goal CALCULATE before this change. It also cannot suggest the creation of a method for AIRCRAFT based on the method for SHIP because it is a fix that only applies to goals being made more general, and EXPECT does not know that that was the cause of the error.

8 Preliminary Results

We conducted some preliminary evaluations of our work by comparing the performance of four subjects using EXPECT and ETM with two different scenarios that required modifying a knowledge base. Both scenarios used the same knowledge base (from a simplified transportation domain). One of the scenarios (PAEgif) was slightly more complex than the other one (RTTgif). Each subject had to solve both scenarios, one of them using EXPECT and the other using ETM. The scenarios and tools were used by the subjects in different order so that the results were not influenced by tiredness or increased familiarity with the domain. For these preliminary evaluations, all of our subjects were familiar with EXPECT (but not with ETM), and had some previous exposure to the transportation domain. The subjects were first given some introductory material about the tools, the domain, and were given a chance to practice using both tools. For each scenario, they were given instructions for the modification and a sample test problem with the expected solution after the modification. The experiment took several hours for each of the subjects, and we took detailed transcripts of what they were doing during that time. We also instrumented the tools to record the user's interactions, the errors in the knowledge base, and the time between each modification. The table below shows some results of these evaluations.


The total time includes the time to understand the instructions for modification and the time to complete the modification (i.e., to leave the knowledge base in a coherent state and successfully computing a given set of sample problems). According to our expectations, subjects using ETM took consistently less time and the contrast was greater in the more complex scenario (PAE). Notice that the subjects were familiar with EXPECT but not with ETM. We expect the difference to be much larger in our future tests with users who are not familiar with EXPECT. The table also shows the number of changes done semi-automatically by the KA Scripts, which may be one of the reasons why the subjects took less time with ETM.

It is interesting to note that in the longer scenario (PAE) both subjects using EXPECT had forgotten to perform part of the modification specified in the instructions. To realize which was the problem that was causing the wrong results that they got during the execution of the sample problems, and to revert that situation (which sometimes required to redo part of the modification in a different way) took them considerable time. One possible explanation of why subjects using ETM did not have that problem is that KA Scripts represent ``checklists'' of changes that the user should consider making.

In contrast with our experience with previous versions, users were able to understand what the KA Scripts suggested and to follow the guidance that they provided in completing modifications. Although ETM allows users to abandon the KA Scripts and use EXPECT, none of our subjects decided to pursue this option.

9 Related Work

There is a vast number of techniques for assisting the development of knowledge-based systems that, like ETM, follow the paradigm of detecting problems in a KBS and suggesting repairs. These techniques have been used in knowledge base refinement (e.g., TEIRESIAS [Davis1979], theory revision (e.g., EITHER [Ourston and Mooney1994], FOCL [Pazzani and Brunk1991]), apprenticeship systems (e.g., ODYSSEUS [Wilkins1990] and NeoDISCIPLE [Tecuci1992]), and Validation & Verification (e.g., [O'Keefe and O'Leary1993]). However, none of them uses a concept similar to our scripts or even considers the context in which errors were produced. This is because the purpose of those techniques is different than ours. The above mentioned approaches attempt to correct the errors in a KBS when it is being developed. In contrast, the purpose of ETM is to guide a user in modifying a KBS that is initially correct. In the case of ETM, the errors to be corrected were introduced during the modification process. Hence, ETM can rely on knowledge about this process in correcting these errors.

Some knowledge-based software engineering (KBSE) tools have incorporated a concept similar to our KA Scripts. KBEmacs ([Waters1985]) is a knowledge-based program editor that permits the construction of a program by combining algorithmic fragments (called cliches) from a library. KBEmacs cliches are equivalent to ETM KA Scripts except that cliches are algorithmic fragments and that are used to generate programs while KA Scripts are procedures and they are used to modify KBSs. Another difference is that KBEmacs does not support the selection and application of cliches while ETM automatically detects opportunities for using KA Scripts, suggests what KA Scripts can be applied, and guides users in applying a KA Script. An interesting point worth noticing is that both KBEmacs and ETM allow a user to perform modifications not supported by their procedure libraries by letting her to resort to a more general purpose tool (Emacs and EXPECT respectively) .

Another example of a script-based KBSE tool is the Knowledge-based Software Assistant (KBSA) and its successor ARIES ([Johnson and Feather1991, Johnson et al. 1992]). The purpose of these tools is to provide integrated support for requirements analysis and specifications development. They provide a library of evolution transformations (or ET) that a user can apply to make consistency-preserving modifications to the description of a software system. These ETs are similar in spirit to ETM's KA Scripts. Their main distinction lies in that ETs are used to manipulate a semi-formal description of a system, while ETM modifies the actual implementation of a system. This demanded of ETM the use of special techniques for understanding the consequences of changes, like the determination of interdependencies among KBS elements or the analysis of the past states of a KBS to determine how KBS elements used to fit together. Ours ultimate goal is to enable end users to modify a KBS themselves. For this reason we put special emphasis in supporting end users and have incorporated some special techniques that KBSA and Aries do not have because they support programmers instead. First, we keep a history of previous changes to the system in order to interpret the user intentions and to avoid giving advice that may contradict them. Second, we included into the library KA Scripts that are specific to particular situations. Although these KA Scripts lack generality, they provide a more precise and hence more helpful guidance.

10 Conclusions

Our goal is to develop an approach for building knowledge-acquisition tools that provide strong support for a wide range of modifications and knowledge-based system types. To achieve this goal, we equipped a knowledge-acquisition tool with a library of knowledge-acquisition scripts (or KA Scripts) which represent prototypical procedures for modifying knowledge-based systems. A knowledge-acquisition tool uses these KA Scripts to guide users in following up the consequences of changes performed to a KBS. The advantage of KA Scripts is that they provide a context for relating individual changes to different parts of the knowledge-based system enabling the tool to analyze each change from the perspective of the overall modification. This kind of analysis complements previous approaches for interpreting changes to a KBS and enables a knowledge-acquisition tool to provide a more precise guidance. Because KA Scripts are problem-solving method independent, they can be used to support modifications of any kind of knowledge-based system. Furthermore, because KA Scripts represent varied procedures for modifying different aspects of a KBS, they can support a wide range modifications.

We have implemented a script-based knowledge-acquisition tool called ETM that supports modification to knowledge-based systems developed within the EXPECT framework. In implementing ETM we addressed several research issues that concerned the development of a KA Script library, the coordination of KA Scripts, and the model of interaction with the user.

To evaluate ETM, we carried out an experiment that compared the performance in modifying KBSs for subjects using ETM vs. subjects using EXPECT. The experiment showed that subjects using ETM outperformed the ones using EXPECT, especially in the more complex modification tasks. In this first experiment we chose subjects that were already familiar with EXPECT but not with ETM. We expect that the difference in performance will be more significant in our future experiments involving subjects not familiar with EXPECT.

One important extension to our approach consists of advising users how to start a modification, not just how to complete it. In fact, three of our four subjects made the comment that they would like help in figuring out where to start the modification. One way to achieve this goal is by integrating KA Scripts of different level of abstraction. The more abstract KA Scripts would plan the overall modification while the more specific ones would take care of the details.


I would like to thank Yolanda Gil, Ion Muslea, and Andre Valente for their valuable comments on this paper. Our special thanks to the past and present members of the EXPECT research group that patiently participated in our experiments, making possible the evaluation of ETM reported here. We gratefully acknowledge the support of DARPA with the contract DABT63-95-C-0059 as part of the DARPA/Rome Laboratory Planning Initiative.


 Randall Davis. Interactive transfer of expertise: Acquisition of new inference rules. Artificial Intelligence, 12(2):121-157, 1979.
Gil and Melz1996
 Yolanda Gil and Eric Melz. Explicit representations of problem-solving strategies to support knowledge acquisition. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, August 1996.
Gil and Tallis1995
 Yolanda Gil and Marcelo Tallis. Transaction-Based Knowledge Acquisition: Complex Modifications Made Easier. In Proceedings of the Ninth Knowledge-Acquisition for Knowledge-Based Systems Workshop, Banff, Alberta, Canada, 1995.
Gil and Tallis1997
 Yolanda Gil and Marcelo Tallis. A script-based approach to modifying knowledge-based systems. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, Providence, RI, July 1997.
 Yolanda Gil. Knowledge refinement in a reflective architecture. In Proceedings of the Twelfth National Conference on Artificial Intelligence, Seattle, WA, 1994.
Johnson and Feather1991
 W. Lewis Johnson and Martin S. Feather. Using evolution transformations to construct specifications. In Automating Software Design, pages 65-92. AAAI Press, 1991.
Johnson et al. 1992
 W. Lewis Johnson, Martin S. Father, and David R. Harris. Representation and presentation of requirements knowledge. IEEE Transactions on Software Engineering, 18(10):853-869, October 1992.
 R. MacGregor. The evolving technology of classification-based knowledge representation systems. In J. Sowa, editor, Principles of Semantic Networks: Explorations in the Representation of Knowledge. Morgan Kaufmann, San Mateo, CA, 1991.
Marcus and McDermott1989
 S. Marcus and J. McDermott. SALT: A knowledge acquisition language for propose-and-revise systems. Artificial Intelligence, 39(1):1-37, May 1989.
O'Keefe and O'Leary1993
 Robert M. O'Keefe and Daniel E. O'Leary. Expert System Verification and Validation: A Survey and Tutorial. Artificial Intelligence Review, 7:3-42, 1993.
Ourston and Mooney1994
 Dirk Ourston and Raymond J. Mooney. Theory refinement combining analytical and empirical methods. Artificial Intelligence, 66:311-344, 1994.
Pazzani and Brunk1991
 Michael J. Pazzani and Clifford A. Brunk. Detecting and correcting errors in rule-based expert systems: an integration of empirical and explanation-based learning. Knowledge acquisition, 3(2):157-173, June 1991.
Puerta et al. 1992
 A. R. Puerta, J. W. Egar, S. W. Tu, and M. A Musen. A multiple-method knowledge-acquisition shell for the automatic generation of knowledge-acquisition tools. Knowledge Acquisition, 4(2):171-196, 1992.
Runkel and Birmingham1993
 J. T. Runkel and W. P. Birmingham. Knowledge acquisition in the small: Building knowledge-acquisition tools from pieces. Knowledge acquisition, 5(2):221-243, 1993.
Swartout and Gil1995
 Bill Swartout and Yolanda Gil. EXPECT: Explicit Representations for Flexible Acquisition. In Proceedings of the Ninth Knowledge-Acquisition for Knowledge-Based Systems Workshop, Banff, Alberta, Canada, 1995.
 G. D. Tecuci. Automating knowledge acquisition as extending, updating, and improving a knowledge base. IEEE transactions on Systems, Man, and Cybernetics, 22(6):1444-1460, 1992.
 R. Waters. The programmer`s apprentice: A session with kbemacs. IEEE Transactions on Software Engineering, 11(11):1296-1320, November 1985.
 David C. Wilkins. Knowledge base refinement as improving an incorrect and incomplete domain theory. In Machine Learning: An Artificial Intelligence Approach, volume 3, pages 493-513. Morgan Kaufmann, San Mateo, CA, 1990.
 Gregg R. Yost. Acquiring knowledge in soar. IEEE Expert, 8(3):26-34, June 1993.
A more detailed description of this KA Script is presented in Section 6 and shown in Figure 3.
 Using an analogy with databases, we can view the process of modifying the knowledge base as a sequence of transactions., where KA Scripts support users by enforcing that transactions are completed so that the knowledge base is not left incoherent
Note that KA Scripts are implemented in Lisp. Figure 3 is a natural-language description of a KA Script procedure.
PAE stands for Personnel Aspect Evaluation. This scenario consisted in refine a rough estimation of the personnel needed for a trip, by discriminating personnel requirements depending on the type of seaports.
RTT stands for Round Trip Time. This scenario consisted in adding aircraft to the definition of the vehicles available for a transportation (which originally consisted only in ships).