Knowledge Analysis on Process Models

1 Introduction

Building process models is essential in many science and engineering fields. Since some of these processes are quite complex, it is useful to provide tools that enable users to specify process models. Figure 1 shows an example of a process model in Cell Biology to describe how a Lambda virus invades a cell. To be able to specify such a model, the user has to specify each of the individual steps and connect them appropriately. There are different types of connections among the steps, including decomposition links between steps and substeps, ordering constraints, disjunctive alternatives, etc. Even in process models of small size, the number of steps and connections between them is large enough that users would benefit from the assistance of intelligent acquisition tools that help them specify process models correctly. For example, the user may forget to specify the links between the steps, or may specify wrong links. We found such errors in a Biological Weapon production model built by a subject matter expert. Even though it can be considered as a relatively simple model (consisting of 54 steps) and many people had looked at it, there were at least two errors: (a) there were two steps that were both specified as the second substep of the same step; (b) there were two sequential substeps whose ordering information was missing. Although these may be simple errors, in more complex models users may generate more serious problems and have difficulty noticing and fixing them.

Graphical tools to lay out a process model and draw connections among steps abound, but the tools are limited to simple checks on the process models because there is no semantics associated to the individual steps. In contrast, we assume a knowledge-rich environment that enables users to specify what the process and its steps mean, what they should accomplish and how, and what the features of the objects involved in those steps are. In order to check a process model such as the one in the figure thoroughly, the system would have some background knowledge about what a cell is, that it can be entered because it is a physical object with a barrier, etc. It would also be helpful for the tool to know what a change of location is, and that the Enter step implies a change of location of its agent. Domain ontologies and upper or middle level ontologies are commonly used to represent this kind of background knowledge. With this context, the tool can be much more helpful in checking that the process model makes sense within the background knowledge that it has.

Past research in validation and verification of knowledge bases addresses the detection of errors in rule bases [Preece & Shinghal, 1994; O'Keefe & O'Leary, 1994] or in ontologies [McGuinness et al., 2000] and has not addressed process models specifically. Research on interactive tools to acquire planning knowledge is also related [Chien, 1998; Myers, 1996; Huffman & Laird, 1995], but their focus is on acquiring knowledge about how to generate plans instead of acquiring the specific plans themselves. Plan authoring tools are closer in spirit to the process authoring tools that we are aiming for, and as such KANAL could be used to check errors in plans produced by plan editing tools. Formal analyses of partial-order and hierarchical planning algorithms define some desirable properties of plans, such as justifiability and correctness [Kambhampati, Knoblock, & Yang, 1995; Yang, 1990; Tate, 1996]. Generative planners such as SIPE, NOAH, and NONLIN [Wilkins, 1988; Sacerdoti, 1977; Tate, 1977] use critics that detect problems in the plans that they generate while planning. Much of the work on planning does not exploit background knowledge and ontologies, which we believe is crucial technology to advance the state of the art in process modeling.

We have developed a tool that checks process models specified by a user, reports possible errors in the models, and generates specific suggestions to the user about how to fix those errors. Our system is called KANAL (Knowledge ANALysis), and it helps users build or modify process models by detecting invalid statements and pointing out what additional knowledge needs to be acquired or what existing knowledge needs to be modified. Our approach is inspired on previous work on EXPECT using Interdependency Models [Swartout & Gil, 1995; Kim & Gil, 2000]. These models of the interdependencies between different pieces of knowledge can be derived by analyzing how knowledge is used during problem solving. By analyzing these interdependencies, a knowledge acquisition tool can detect inconsistencies and missing knowledge and alert the user of potential problems in the knowledge base. Finally, based on the context provided by the Interdependency Models the tool can guide the user in fixing these problems by correcting inconsistencies and by adding further knowledge. KANAL analyzes the interdependencies among the individual steps of a process model. For example, a simulation of the execution of the steps allows KANAL to analyze interdependencies between the conditions and effects of different steps, such as that the required conditions for each step are met when the step is supposed to take place, and that the expected effects of the overall process are in fact obtained.

The paper begins by describing the representation of process models assumed in KANAL. Then we describe how Interdependency Models can be applied to check various features of process models. Next, we present the current implementation of KANAL and the algorithms that it uses to detect different kinds of errors. Finally, we present the results from a preliminary evaluation that show that KANAL can detect most of the errors that were randomly introduced in originally error-free process models, suggesting useful fixes that often point directly to the source of the errors.

2 Representing Process Models

This section describes briefly our representation of process models, which is consistent with current efforts on standard languages and process ontologies, such as PDDL [Ghallab et al., 1998] and NIST's PSL [Tissot & Gruninger, 1999].

A process model is composed of a number of (sub)steps. Each individual step has preconditions and effects, where the preconditions specify the conditions needed to be satisfied to activate the step and the effects describe changes that result from the execution of the step. For example, an "Enter" step has a precondition that the objects to enter should be near the entrance of a container object. Its effect can include a location change from outside of a space to inside of the space and also a status change to being contained within the container. These can be represented as a precondition list and add/delete lists (as in STRIPS operators).

The steps within a process model are connected to other steps through different kinds of links including:

• AF decomposition links: Users can specify superstep/substep relations. For example, an Invade step can have Arrive, Enter and Take Control as its substeps, and each of these substeps can have their own substeps.
• AF temporal links: Users can specify ordering constraints among the steps. For example, in modeling virus invasion, the Take Control step should follow the Enter step.
• AF disjunctive links: There might be more than one way of performing a given task, and the alternatives can be represented by disjunctive links. For example, the DNA of a Lambda virus can either start its replication right after entering a cell or be integrated with the host chromosome before the replication.
• AF causal links: If the editor allows users to specify enablement/disablement between steps, since KANAL can compute the actual causal relationships among the steps from the simulation results (by examining the outcome of the steps and the preconditions checked by other steps), the user-specified causal links can be used for validating the model.

Each step can have several roles. For example, in an Enter step an object can play the role of an agent and another object can play the role of the container being entered. A general description of an Enter step can be instantiated for the Virus invasion process by assigning the concept virus to the agent role of Enter and the concept cell to the container role. These role assignments cause further interdependencies in the knowledge base, since the objects assigned to the roles have their own constraints and definitions that must be consistent with those of the process models and their steps.

3 Acquiring Process Models: The End-to-End System

Currently, KANAL is being developed as a module within an ambitious end-to-end system that will support subject matter experts entering domain knowledge as part of the DARPA Rapid Knowledge Formation (RKF) program. In this project, users will build process models is by using "concept composition" [Clark & Porter, 1997]. Users can build process models by retrieving components (actions and objects) and then connecting them using various kinds of links. The user interface and the component library have not been fully implemented and integrated with KANAL, although a preliminary version of the three was done to illustrate the approach with a small scale scenario of a process model for virus invasion.

Figure 2 is an interface that we built to show how the component approach can be used to build process models by linking various objects in the knowledge base. The user has selected the Invade component to start building the Virus Invasion model. The "agent" role can be assigned to the Virus concept, the Enter component can be linked as a subevent, and so on.

Although KANAL is built to check process models constructed by concept composition, it can also be used for checking process models in other environments. For example, providing procedural knowledge required by intelligent tutoring systems has been an ongoing challenge, and they sometimes use simulators to build and refine their models [Scholer et al., 2000]. We are also investigating the use of KANAL to help teachers formalize process models that will be used as lessons by a tutoring system.

4 Using Interdependency Models

In past work, InterdependencyModels have been successfully used in building and checking problem-solving knowledge in EXPECT [Kim & Gil, 1999; Kim & Gil, 2000]. They have been used in analyzing how individual components of a knowledge base are related and interact when they are used during problem solving. An example of interdependency between two pieces of procedural knowledge is that one may be used by the other to achieve a subgoal. Other kinds of Interdependency Models include interdependencies between factual knowledge and procedural knowledge. Interdependency Models can point out missing pieces in solving a problem and be used to predict what pieces are related and how. In this paper, we show a novel use of InterdependencyModels to check process models.

To guide users in developing process models, KANAL builds interdependencies among objects in the knowledge base, and uses them to perform two kinds of checks: static checks and dynamic checks. Static checks are performed by posing questions about various features of the process model, and dynamic checks are performed by simulating the execution of the process model. Our initial work to date has focused on dynamic checks.

In order to perform static checks, we plan to maintain a list of sample query templates, such as retrieving the values of different links, types of roles assigned to steps, etc. A list of instantiated queries can be generated for a particular model using these templates. Users could select key queries from this list and also specify the answers expected from the queries. A trace of the answer to a query can be considered as a model of the interdependencies in that it reflects how different pieces of knowledge are put together to generate the answer.

Dynamic checks can be done on the simulated execution of the process model. The simulation results show how different steps are related to each other, including temporal ordering and causal relationships. The results also show how certain effects are produced by a set of sequences of steps. The resulting Interdependency Model enables checking if all the steps are properly linked, all the preconditions of each step are satisfied during the simulation, all the expected effects can be achieved, there are no unexpected effects, there are no impossible paths, etc. Also the interdependencies can point to potential ways of solving errors and gaps in the model, such as changing ordering constraints to reinstate disabled effects, finding steps that can generate unachieved effects, adding missing links, etc.

Our current work focuses on dynamic checks, using the simulation as a tool to generate InterdependencyModels. The next section describes how we check the process models using simulation results.

5 Checking Process Models with KANAL

Our current implementation is built using the KM knowledge representation and reasoning system [Clark & Porter, 2000], and invokes its simulator to generate alternative simulations of a process model. KM's simulation of process models can be seen as a symbolic execution of a linearization of the process model using Skolem instances. KM provides a function that can execute a step in a given situation and create a new situation based on the add/delete lists of the step. KANAL uses this function to execute the steps in the given model and check various kinds of problems. Whenever a precondition test fails or any of the events are undoable (a step is undoable when not all of its previous steps were executed), KANAL interrupts the simulation and reports the unreached steps (a step is unreached when the simulation stops before the step is simulated). It also reports other problems found until it finishes the simulation. From the simulation results, including the problems detected during the simulation, KANAL can compute potential fixes based on Interdependency Models.

The subsections below describe each type of check that KANAL performs in detail.

5.1 Checking Unachieved Preconditions

A precondition is not achieved either because there is no previous step that produces the needed effect or because some previous steps undo the precondition. For example, an Integrate step of a virus DNA into a host chromosome may undo a precondition (that the viral DNA is exposed) of a step to Synthesize protein from DNA. To be able to synthesize the viral protein needed for the replication, an additional Dis-Integrate step that can reinstate the exposure is required.

The general algorithm to check preconditions is as follows:

1. Detect problem
2. (a) Run simulation with Skolem instances
3. (b) Collect failed step(s)
4. (c) Collect unachieved preconditions of failed step
5. (d) Show them to user
6. Help user fix problem
7. (a) Suggest that there are missing steps:
8. Find components in the knowledge base that have the effects needed as preconditions by the failed step and suggest inserting one of these components somewhere within the current process model before the failed step
9. (b) Suggest that there are missing ordering constraints:
10. Find steps that were executed before the failed step that may have effects that undid the unachieved preconditions
11. Find steps that follow the failed step and have effects that assert the unachieved precondition and suggest inserting an ordering constraint between those steps and the failed step
12. (c) Suggest modifying the step whose preconditions were not achieved

For the above type of failure, KANAL suggests (a) adding a Dis-Integrate step, (b) changing or adding ordering constraints for the Integrate step, and (c) deleting or modifying the Synthesize step. Suggestion (a) would be the one that user is looking for in order to fix the problem in this example.

5.2 Checking Expected Effects

KANAL informs the user of the effects of each step during simulation. This allows users to check that the process occurs as they anticipated. In addition, users can specify to KANAL what they expect to be the case after the overall process happens. These expected effects are what the user indicates should result from the simulation and/or the postconditions of the composed process model. For example, the user may expect that after a virus invasion of a cell, the viral nucleic acid should be located inside the cell. These expected effects can be checked by looking at the results from the simulation. The simulation results are represented as an accumulation of added and deleted facts. Since there may be multiple disjunctive branches in the model, the results from different paths are accumulated separately. KANAL checks the results from each path to see if all of them satisfy the expectation. If there are unachieved effects, KANAL can propose either to add new steps that would achieve them or to modify existing steps.

Currently KANAL checks for expected effects, but does not check explicitly for unexpected effects. We are planning to highlight any unexpected effects to let the users examine whether they should in fact occur.

The algorithm is as follows:

1. Ask user to specify expected effects
2. Detect problem
3. (a) Run simulation with Skolem instances
4. (b) Collect unachieved effects from each path and record the steps in the failed paths
5. (c) Show them to user
6. Help user fix problem
7. (a) Suggest that there are missing steps:
8. Find components in the knowledge base that have the effects needed and suggest inserting one of these components somewhere within the current process model
9. (b) Suggest modifying steps:
10. Find steps that may have effects that can potentially change the role values of the unachieved effects and suggest modifying those steps to achieve the effects needed
11. (c) Suggest that there are missing ordering constraints: - Find steps that may have effects that undid the expected effects and find actions that assert the expected effects and suggest inserting an ordering constraint in order to maintain the expected effect where needed

Following the example above, suppose that the user specifies that after the invasion occurs the viral nucleic acid should be located inside the cell. Suppose also that the user forgot to add the Enter step in the model of virus invasion. KANAL suggests (a) adding new steps, such as Move or Enter, that would change the location of the virus, (b) modifying Arrive since it is an existing step that causes the virus to change location, or (c) changing/adding ordering constraints among these steps. The user would choose option (a) to add an Enter step, and the problem would be fixed.

5.3 Checking Unordered Steps

Sometimes the user may either forget to specify links between the steps, or may specify wrong links as in the Biological Weapon production example mentioned in the introduction. These problems may be detected by mapping the steps to the components in the knowledge base that have certain ordering constraints already specified for their substeps, or by running simulation and doing the checks as describe above for unachieved preconditions and effects. During the simulation, KANAL walks through the steps and substeps using the user specified decomposition links and ordering constraints. The simulation is interrupted if some steps cannot be reached because of lack of ordering constraints or the steps are undoable. KANAL highlights these problems and proposes changing or adding ordering constraints among the steps. (We do not show the detailed algorithm here because of lack of space.)

5.4 Checking Inappropriate Execution of Steps

KANAL can also find modeling errors by watching the execution of steps. For example, if some of the assertions to be deleted by a step are not true in the situation where the step is executed, these assertions are reported. Also, if a step produces no effect, i.e., it does not delete or add any assertions, then KANAL reports such problem as well. This type of problem can occur when the step's roles or attributes are assigned to the wrong objects during the composition. Also, if its previous steps have incorrect assignments already and produced unexpected effects, then the following steps cannot be executed appropriately.

KANAL proposes modifying the steps by changing their role assignments or modifying previous steps.

5.5 Checking Invalid Expressions

During the simulation, KANAL checks the truth/falsity of many assertions, especially for the precondition tests and the expected effect tests. Whenever there are objects tested but undefined, KANAL reports the problem of accessing undefined objects (or invalid expressions).

5.6 Checking Loops

Loops are not necessarily a problem in process models. For example, the replication of DNA can be repeated multiple times. However, they can be unintended repetitions especially when the user defines many ordering constraints across steps. KANAL provides a warning for such cases to let the user check if the loops are in fact intended.

5.7 Checking Disjunctive Branches

When there are disjunctive branches in a model, the user may not notice that some of the combinations of alternatives should in fact not be possible. KANAL exposes different branches in the models by showing different alternative combinations of substeps. As in the case of loops, disjunctive branches are not necessarily a problem and KANAL simply informs the user about them.

5.8 Checking Causal Links

After the simulation, KANAL computes the interdependencies between the steps based on how some steps generated effects that satisfied the preconditions of some other steps. For example, synthesizing viral protein needed for replication enables the replication step. These causal links may not have been explicitly indicated by the user. KANAL informs users when it notices causal links in order to help them validate the model. It also informs users when they specified a temporal constraint and there does not seem to be a causal link between the steps to justify the ordering.

6 Interaction among problems and fixes

This section shows some examples of the kinds of errors detected and the fixes proposed by KANAL from a simplified Lambda virus invasion model shown in Figure 3. (In the model, first a lambda virus moves next to a cell (Arrive), and then it enters into the cell (Enter). The lambda DNA forms a circle (Circularize), and then either becomes integrated with the host chromosome (Integrate) or starts synthesizing viral protein needed for the formation of new viruses (Synthesize). When it gets integrated, it lies dormant in the chromosome during cell divisions (Divide). An environmental change can induce the genome to leave the host chromosome (DisIntegrate) and to start synthesizing viral protein and subsequent DNA replication (Replicate) [Alberts et al., 1998].)

• AF inappropriate execution of a step

When the agent (virus) of the Arrive step is not specified, KANAL detects inappropriate execution of the step since its delete-list contains assertions that are invalid (the location of a Thing instead of the location of the virus). In such cases, KANAL proposes to either to modify the assignments of the Arrive step or to add some steps before Arrive so that they can assert the location of the Thing. The first fix directly points to the deleted link, and we call it a direct fix. The latter one will eventually lead the user to the problem because it mentions the location but does not point to it directly. We call it an indirect fix.

• AF unachieved preconditions

In the above case (missing agent of the Arrive step), the precondition of the Enter step that follows (location of the virus should be near the cell) may also fail because of the failure of the Arrive step. KANAL detects this unachieved precondition and proposes multiple ways of fixing the problem: (1) modify the Arrive step so that it can change the location of the virus, (2) add a newMove or Arrive step to achieve the precondition, or (3) modify the Enter step to have different preconditions. Note that in this case, the same fix (i.e., modifying the Arrive step) is suggested for solving two different errors (inappropriate execution of Arrive and unachieved precondition of Enter).

Also, the same set of fixes may resolve two different errors. For example, if the assignment of the patient (virus) of Enter is missing, its precondition (the patient should be near the destination) fails. KANAL produces an error message and proposes similar fixes as in the above case.

• AF failed expected effects

One of the expected effects was that the the virus should be inside the cell after an execution of the scenario. When the assignment of destination (the cell) of the Enter step is missing, the effect (the virus enters into the cell) cannot be achieved.

• AF missing ordering constraints

When ordering between steps are missing (e.g., the link between the Arrive step and the Enter step is not specified), KANAL interrupts the simulation and reports an error. It proposes to add or modify temporal links between the steps so that the simulator can execute the unreached steps. When there is any ambiguity in the ordering, it generates a warning, asking for explicit ordering constraints among the steps.

In addition to the above, KANAL reports other results from the simulation:

• AF causal links

There were three causal links reported from the scenario: (1) Arrive enabled Enter by achieving the location the virus being near the cell, (2) Integrate enabled Disintegrate by achieving the DNA being integrated with the chromosome, and (3) Synthesize enabled Replicate by providing the viral protein needed for the replication.

• AF disjunctive links

The disjunctive branches stemming from Circularize were shown to the user as two alternative paths.

• AF simulated paths

There were two simulated paths because of the disjunctive branches: (Arrive AX Enter AX Circularize AX Integrate AX Divide AX DisIntegrate AX Synthesize AX Replicate) and (Arrive AX Enter AX Circularize AX Synthesize AX Replicate).

Notice that KANAL can detect the same error in multiple ways since one abnormality can lead to another. For example, missing an ordering constraint can make some steps unreached during the simulation, which can also lead to failed expected effects because of the unexecuted (unreached) steps. Since whenever there are unreached steps there tends to be failed expected effects, users may want to focus on fixing problems about the unreached steps first. The same case holds for failed preconditions and unreached steps because failed preconditions interrupt simulation, leading to unreached steps. To help avoid confusion, KANAL can selectively present fixes so that the user can concentrate on the actual source of the problem. For the case of failed preconditions and unreached steps, KANAL presents the fixes for the failed preconditions first, but lets users check other fixes if they want.

7 Preliminary Evaluation

KANAL is being integrated with concept composition, explanation tools and their interfaces in the end-to-end system mentioned above, and we are planning to perform an extensive user evaluation of this integrated system. The preliminary evaluation presented here focuses on how useful KANAL is in itself as a module to detect and fix errors.

To evaluate KANAL's help in detecting and fixing errors, we used three process models: a virus invasion process, a Lambda virus invasion, and a Check-CondensateDrain-Motor procedure from a High Pressure Air Compressor (HPAC) domain which has been also used for acquiring process models (lessons) for intelligent tutoring systems [Scholer et al., 2000]. The first and last ones were written by other researchers.

We evaluated how KANAL could help users with one important kind of error: if they forget to specify one, two, or three links or role assignments. For example, to specify the Virus Invasion model the user would need to make a total of 19 links and assignments if no errors are made. The test cases were generated by taking the original correct process models and randomly deleting a subset of the links or assignments that users would need to make.

Table 1 shows the results from our preliminary evaluation. The first rows in each table show the number of cases tested and the second rows show the total number of errors in the test cases. The third row shows how many of those errors were detected by KANAL. KANAL was able to detect most of the errors when there is only one error (55 of 56). KANAL misses one case in the Lambda virus invasion model because its Invade component has Container as its patient which should in fact be a Cell (a more special concept than Container), but there was no explicit violation in any of the checks KANAL performs. To be able to detect such problems we may need to examine slots tested in the model and check if they in fact belong to the concept. For example, Cells contain cytoplasm but not any Containers do in general.

KANAL missed some errors when more than one link were deleted (42 among 60 without 2 links, and 47 among 90 without 3 links). This is to be expected, since some errors interrupt the simulation, and other errors cannot be detected unless further steps are simulated, as described in the previous section.

The number of errors which had direct fixes are shown in the fourth rows in the tables. There were a few cases where KANAL detected errors but was not able to provide direct fixes. For example a step's role can refer to a deleted slot of another step, such as when the agent of the Enter step refers to the agent of the Invade step. If the Enter step failed because of the missing agent of the Invade step, then the failed step is different from the step with missing links, making it harder to find the sources of the problems. We are planning to examine how we can follow such links among the steps to trace back to the original sources. Some other cases of lack of direct fixes happened when there are multiple errors at the same time because some errors are hidden as described above. KANAL's selective presentation of fixes helps, and we expect that fixing one problem at a time may be easier for end users.

The numbers of fixes shown in the fifth rows of the tables are based on the selected fixes described above. Direct fixes should be more useful than indirect fixes in general. The number of direct fixes are shown in the sixth rows in the tables. For most of the errors detected, KANAL was able to provide at least one direct fix.

In summary, our preliminary evaluations show:

• AF KANAL virtually always (115 of 116 test cases) detected an error and made suggestions to the user. The one case that KANAL missed was a process model that was perfectly consistent although it was overgeneral, which is a problem that could only be noticed by a user.
• AF Detecting an error impaired detecting others since posterior steps will not be executed in the simulation. Although KANAL detected 98%, 70%, and 52% of the errors in the case where one, two, and three links and assignments were missing, it always detected at least one error in each of the process models that had more than one error. Once an error was fixed, the next error was always found by KANAL (direct fixes).
• AF For 91.6% of the errors detected, KANAL's fixes pointed directly to the source of the errors.

8 Conclusions

As we mentioned, we are planning to perform an extended evaluation with end users (biologists) when KANAL is integrated with the end-to-end system described earlier. In doing so, we will also be able to test the usefulness of KANAL with different types of errors than the ones we show here, including selecting wrong components in the knowledge base.

There have been a lot of verification and validation techniques developed in software engineering [Wallace et al., 1996; Basili, 1987]. Although many of them are not directly applicable, there are many common issues in building process information, including efficiency, maintenance, cost, reuse, etc. We are planning to examine useful techniques developed for such issues.

KANAL is built for concept composition where components in the knowledge base are assumed not to have any errors. However, in other environments, such as in acquiring procedural knowledge for intelligent tutoring systems, we cannot expect that the models of actions will always be correct. Often, incomplete operators are used to model procedures and they are refined based on instructor input or through autonomous learning by experimentation. We believe that KANAL will be also useful in such environments.

Acknowledgments

We would like to thank Bruce Porter and Peter Clark for their help in integrating KANAL with the KM simulator and for providing the virus invasion scenario, and Andrew Scholer for his help with the HPAC process model and with the simulator of the tutoring system mentioned. We would also like to thank Vinay Chaudhri, Mabry Tyson, and Jerome Thomere for their comments and feedback on this work. Kevin Knight provided very helpful comments on earlier drafts. This research was funded by the DARPA Rapid Knowledge Formation (RKF) program with subcontract number 34-000-145 to SRI International under contract number N66001-00-C-8018.