Authoring tool for bayesian network troubleshooters Number:7,385,716 from the United States Patent and Trademark Office (PTO) owispatent

Title: Authoring tool for bayesian network troubleshooters

Abstract: An authoring tool assists an author in building an automated troubleshooter for a product. The authoring tool includes a cause editor interface, an action editor interface and a question editor interface. The cause editor interface allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product. The action editor interface allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product. The question editor interface allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product.

Patent Number: 7,385,716 Issued on 06/10/2008 to Skaanning

---

Inventors:	Skaanning; Claus (Dronninglund, DK)
Assignee:	Hewlett-Packard Development Company, L.P. (Houston, TX)
Appl. No.:	09/388,891
Filed:	September 2, 1999

---

Current U.S. Class:	358/1.14 ; 714/4
Field of Search:	358/1.1,1.14,1.13,1.15 706/46,47,50,55,59,61,20,21,45,52 714/4,26

---

References Cited [Referenced By]

---

U.S. Patent Documents

4891766	January 1990	Derr et al.
4965742	October 1990	Skeirik
5596712	January 1997	Tsuyama et al.
5835683	November 1998	Corella et al.
5978784	November 1999	Fagg, III et al.

Foreign Patent Documents

	0 332 322		Feb., 1989		EP
	2 271 005		Sep., 1993		GB
	WO 85/05711		Jun., 1985		WO

Other References

de Kleer, J. and Williams, B., "Diagnosing multiple faults" in Artificial Intelligence, 32:97-130 (1987). cited by other . Heckerman, D., Breese, J., and Rommelse, K., "Decision-theoretic Troubleshooting," in Communications of the ACM, 38:49-57 (1995). cited by other . Lauritzen, S.L., and Spiegelhalter, D.J., "Local Computations with Probabilities on Graphical Structures and their Applications to Expert Systems," in Journal of the Royal Statistical Society, Series B, 50(2): 157-224 (1988). cited by other . Jensen, F.V., Lauritzen, S. L., and Olesen, K.G., "Bayesian Updating in Causal Probabilistic Networks by Local Computations," in Computational Statistics Quarterly, 4:269-282, (1990). cited by other . Breese, J.S. and Heckerman, D. "Decision-theoretic Troubleshooting: A Framework for Repair and Experiment", Technical Report MSR-TR-96-06, Microsoft Research, Advanced Technology Division, Microsoft Corporation, Redmond, USA (1996). cited by other . Henrion, M., Pradhan, M., del Favero, B., Huang, K., Provan, G., and O'Rorke, P., "Why is Diagnosis using Belief Networks Insensitive to Imprecision in Probabilities?", Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, (1996). cited by other.

Primary Examiner: Garcia; Gabriel

---

Claims

---

I claim:

1. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a cause editor interface that allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product; an action editor interface that allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product; and a question editor interface that allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product; wherein information within the cause data structure, the action data structure and the question data structure are all used by the automated troubleshooter to provide troubleshooting steps to a user of the automated troubleshooter, the troubleshooting steps being steps the user can use to troubleshoot the product.

2. An authoring tool as in claim 1 wherein the authoring tool additionally comprises a library of modules, at least one of the modules containing troubleshooting information about a component of the product.

3. An authoring tool as in claim 2 wherein the author can save the library of modules to a disk storage device, load the library of modules from the disk storage device and create a new library of modules.

4. An authoring tool as in claim 2 wherein the author can select modules from the library of modules when building the automated troubleshooter for the product.

5. An authoring tool as in claim 4 wherein the author can create new modules and delete modules.

6. An authoring tool as in claim 5 wherein the author can rename modules and import modules from other libraries of modules.

7. An authoring tool as in claim 1 wherein information pertaining to a cause relates to the following categories: name of the cause; parent of the cause; explanation of the cause; and, probability of the cause being source of malfunction.

8. An authoring tool as in claim 7 wherein the information pertaining to the cause additionally relates to the following categories: category of the cause; dependency on environment; and, indication that a customer is not to access information pertaining to the cause.

9. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a cause editor interface that allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product; an action editor interface that allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product; and a question editor interface that allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product; wherein information pertaining to an action relates to the following categories: name of the action; explanation of the action; causes solved by the action; probabilities that the action solves specified causes an indication whether the action is for information-gathering or is a potential solution; costs of taking the action; and, trustworthiness of an answer to the action.

10. An authoring tool as in claim 9 wherein the information pertaining to the action additionally relates to the following categories: an indication as to whether the action should be taken before other actions; an indication as to whether the action is a workaround; additional actions included with the action; whether the action can only be performed after a specified question has been answered; and, whether the action cannot be performed after a specified question has been answered.

11. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a cause editor interface that allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product; an action editor interface that allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product; and a question editor interface that allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product; wherein information pertaining to a question relates to the following categories: name of the question; explanation of the question; number of answers; names of answers; costs of finding an answer to the question; and, trustworthiness of the answer to the question.

12. An authoring tool as in claim 11 wherein the information pertaining to the question additionally relates to the following categories: whether the question can only be performed after a specified question has been answered; whether the question cannot be performed after a specified question has been answered; an indication as to whether the question should be asked before other questions; and, whether the question is a symptom question or a general question.

13. An authoring tool as in claim 11 wherein information pertaining to the question particularly pertains to a symptom question and additionally relates to the following categories: causes of a symptom; probability of answers to the question conditional on causes that can cause the symptom; and, probability of answers to the question conditional on no causes that can cause the symptom.

14. An authoring tool as in claim 11 wherein information pertaining to the question particularly pertains to a general question and additionally relates to the following categories: prior probabilities of answers to the question; causes that are affected by answers to the question; and, probability of the affected causes conditional on each answer to the question.

15. An authoring tool as in claim 1 wherein: the cause editor interface additionally allows an author to create new cause entries; the action editor interface additionally allows an author to create new action entries; and the question editor interface additionally allows an author to create new question entries.

16. An authoring tool as in claim 1 wherein: the cause editor interface additionally allows an author to edit existing cause entries; the action editor interface additionally allows an author to edit existing action entries; and the question editor interface additionally allows an author to edit existing question entries.

17. An authoring tool as in claim 1 wherein: the cause editor interface additionally allows an author to delete existing cause entries; the action editor interface additionally allows an author to delete existing action entries; and the question editor interface additionally allows an author to delete existing question entries.

18. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a cause editor interface that allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product, wherein for a cause the information relates to the following categories: name of the cause, parent of the cause, explanation of the cause, probability of the cause being source of malfunction, and dependency on environment in which the product is located; wherein the information within the cause data structure is used by the automated troubleshooter to provide troubleshooting steps to a user of the automated troubleshooter, the troubleshooting steps being steps the user can use to troubleshoot the product.

19. An authoring tool as in claim 18 wherein the information pertaining to the cause additionally relates to the following categories: cause category, and indication that a customer is not to access the information pertaining to the cause.

20. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: an action editor interface that allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product, wherein for an action the information relates to the following categories: name of the action, explanation of the action, causes solved by the action, probabilities that the action solves specified causes, an indication whether the action is for information-gathering or is a potential solution, costs of taking the action, and trustworthiness of an answer to the action.

21. An authoring tool as in claim 20 wherein the information pertaining to the action additionally relates to the following categories: an indication as to whether the action should be taken before other actions, an indication as to whether the action is a workaround; additional actions included with the action, whether the action can only be performed after a specified question has been answered, and whether the action cannot be performed after a specified question has been answered.

22. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a question editor interface that allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product, wherein for a question the information relates to the following categories: name of the question, explanation of the question, number of answers, names of answers, costs of finding an answer to the question, and trustworthiness of an answer to the question.

23. An authoring tool as in claim 22 wherein the information pertaining to the question additionally relates to the following categories: whether the question can only be performed after a specified question has been answered; whether the question cannot be performed after a specified question has been answered; an indication as to whether the question should be taken before other questions; and, whether the question is a symptom question or a general question.

24. An authoring tool as in claim 22 wherein information pertaining to the question particularly pertains to a symptom question and additionally relates to the following categories: causes of a symptom; probability of answers to the question conditional on causes that can cause the symptom; and, probability of answers to the question conditional on no causes that can cause the symptom.

25. An authoring tool as in claim 22 wherein information pertaining to the question particularly pertains to a general question and additionally relates to the following categories: prior probabilities of answers to a question; causes that are affected by answers to the question; and, probability of the affected causes conditional on each answer to the question.

26. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a troubleshooter model editor interface that allows the author to place in a troubleshooter model structure, information pertaining to malfunction of the product; and, a library module editor interface that allows the author to place in a library data structure information pertaining to modules corresponding with components of the product; wherein the information within the troubleshooter model structure is used by the automated troubleshooter to provide troubleshooting steps to a user of the automated troubleshooter, the troubleshooting steps being steps the user can use to troubleshoot the product.

27. An authoring tool as in claim 26 wherein the information pertaining to modules corresponding with components of the product comprises: name of a component of a module; causes of the component malfunctioning; actions that can resolve malfunctioning of the component; and, questions that can provide information about the causes of the component malfunctioning.

28. An authoring tool as in claim 26 wherein the information pertaining to malfunction of the product comprises: name of a problem; causes of the problem; actions that can help resolve the problem; questions that can provide information about the problem; and, an amount of time required to observe whether the problem is present.

29. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a troubleshooter model editor interface that allows the author to place in a troubleshooter model structure, information pertaining to malfunction of the product; and, a library module editor interface that allows the author to place in a library data structure information pertaining to modules corresponding with components of the product; wherein the author can create a new troubleshooter model, load troubleshooter models from disk storage, save the troubleshooter models to the disk storage such that the troubleshooter models can be run by external troubleshooter software, save the troubleshooter models in text format, and print a troubleshooter model in text format.

30. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a troubleshooter model editor interface that allows the author to place in a troubleshooter model structure, information pertaining to malfunction of the product; and, a library module editor interface that allows the author to place in a library data structure information pertaining to modules corresponding with components of the product; wherein the author can export causes, actions and questions from a current troubleshooter model to a current library module, and export causes, actions and quests form the current library module to the current troubleshooter model.

31. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a troubleshooter model editor interface that allows the author to place in a troubleshooter model structure, information pertaining to malfunction of the product; and, a library module editor interface that allows the author to place in a library data structure information pertaining to modules corresponding with components of the product; wherein the author can get an overview of all causes in the library data structure for quick lookup and insertion, get an overview of all actions in the library data structure for quick lookup and insertion, and get an overview of all questions in the library data structure for quick lookup and insertion.

32. An authoring tool as in claim 31 wherein the author can add new categories of causes to the modules, and look up causes that fall into specific categories.

33. An authoring tool that assists an author in building an automated troubleshooter for a product, the authoring tool comprising: a troubleshooter model editor interface that allows the author to place in a troubleshooter model structure, information pertaining to malfunction of the product; and, a library module editor interface that allows the author to place in a library data structure information pertaining to modules corresponding with components of the product; wherein the author can view causes in a tree structure, specify sets of probabilities for each level of causes in the tree structure, and normalize the probabilities on each level of causes in the tree structure.

---

Description

---

RELATED APPLICATIONS

The subject matter of the present patent application is related to the subject matter set out by Claus Skaanning, Uffe Kjoerulff and Finn V. Jensen in a co-pending patent application Ser. No. 09/261,769, filed on Mar. 3, 1999 for A METHOD FOR KNOWLEDGE ACQUISITION FOR DIAGNOSTIC BAYESIAN NETWORKS, and to by Claus Skaanning, Finn V. Jensen, Uffe Kjoerulff, Paul A. Pelletier, Lasse Rostrup Jensen, Marilyn A. Parker and Janice L. Bogorad in co-pending patent application Serial Number 09/353,727, filed on Jul. 14, 1999 for AUTOMATED DIAGNOSIS OF PRINTER SYSTEMS USING BAYESIAN NETWORKS.

BACKGROUND

The present invention pertains to support of products and pertains particularly to an authoring tool for Bayesian network troubleshooters.

Currently, it is highly expensive for printer manufacturers to diagnose the systems of their customers. Typically, a customer calls a printer call agent at the manufacturer. This call agent guides the customer through a troubleshooting sequence that leads to resolution of the problem or identification of the cause. This method requires the intervention of a call agent which results in a high cost.

When using call agents the printer manufacturer hires many call-agents which the customer in turn can call when he experiences problems with his printer system. The call-agent attempts to gather as much information as possible by interviewing the customer over the phone. When he reaches the conclusion, he will either have solved the problem, identified the cause, or had to dispatch a field agent that will attempt to resolve the problem at the customer site.

One drawback of using call-agents is the expense. In addition, there can be problems with consistency in the order and types of troubleshooting steps used by different call agents. It is a problem if customers are not given approximately the same troubleshooting steps in the same order with similar problems, as they may then feel confused. Also, the call agent solution allows only limited logging of information, has only limited integration of programmatic data-collectors, and very limited integration of multi-media presentations. Use of call-agents however, does provide the benefit of human-to-human communication between the call agent and the customer as the call agent will obviously be able to detect soft information that a computer-based system cannot easily detect, such as, e.g., whether the customer is irritated with some line of questioning, the level of experience of the customer, and so on.

Decision trees can be used to provide automated diagnosis of printer systems. The decision-tree approach specifies the possible troubleshooting sequences as a so-called decision tree. At each branching of the tree, one of the branches will be chosen based on the information provided by the customer at the last step. However, decision-trees are static in the sense that for practical reasons it only allows a limited number of possible sequences of the troubleshooting steps. With decision-trees all sequences that should be available to the customer have to be encoded and as the size of the decision tree is exponential in the number of these, it is only possible to encode a limited number of them. This on the average will cause the decision tree to provide longer troubleshooting sequences with lower probability of actually diagnosing the problem, as it is not possible to take all possible scenarios into account.

Case-based reasoning can also be used to provide automated diagnosis of printer systems. The case-based approach gathers a high amount of descriptive cases from troubleshooting scenarios where various problems are seen. Based on information about the current situation, the case-based reasoning engine can then select the cases that are most similar. The most similar cases are then investigated to find the best next action or question that has the highest likelihood to rule out as many cases as possible. This continues until the single case that matches most the current situation is determined.

Case-based systems gather cases that are descriptive of the troubleshooting domain and use these cases to suggest actions and questions that as quickly as possible narrows the scope down to a single case. The quality of a case-based system hinges on its case database which has to be very large to adequately describe a printer system domain. The possible configurations/cases in a printer system are 2.sup.N for N variables (10.sup.24 for 80 variables), if all the variables are binary. A subset of cases out of these would have to be extremely large to be sufficiently descriptive to be useful to a case-based system. Thus, it is doubtful that case-based systems will be successful in representing the printing system with its many variables to an optimal level of accuracy.

Rule-based systems can also be used to provide automated diagnosis of printer systems. Rule-based systems can be perceived as a subset of Bayesian networks, as they can be represented with Bayesian networks. They have a subset of the modeling capabilities of Bayesian networks, and the belief updating methods are not guaranteed correct as they are with Bayesian networks.

Rule-based systems, however, have updating methods that are not optimal when there are loops in the model. Loops are very common in models of real-world systems (e.g., common causes, troubleshooting steps that fixes several causes, etc.).

One troubleshooter based on Bayesian networks is described by Heckerman, D., Breese, J., and Rommelse, K. (1995), Decision-theoretic Troubleshooting, Communications of the ACM, 38:49-57 (herein "Heckerman et al. 1995").

A Bayesian network is a directed acyclic graph representing the causal relationships between variables, that associates conditional probability distributions to variables given their parents. Efficient methods for exact updating of probabilities in Bayesian networks have been developed. See for example, Lauritzen, S. L., and Spiegelhalter, D. J. Local Computations with Probabilities on Graphical Structures and their Applications to Expert Systems. Journal of the Royal Statistical Society, Series B, 50(2):157-224 (1988), and Jensen, F. V., Lauritzen, S. L., and Olesen, K. G., Bayesian Updating in Causal Probabilistic Networks by Local Computations, Computational Statistics Quarterly, 4:269-282 (1990). Efficient methods for exact updating of probabilities in Bayesian networks have been implemented in the HUGIN expert system. See Andersen, S. K., Olesen, K. G., Jensen, F. V. and Jensen, F., HUGIN--a Shell for Building Bayesian Belief Universes for Expert Systems, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. (1989).

Bayesian networks provide a way to model problem areas using probability theory. The Bayesian network representation of a problem can be used to provide information on a subset of variables given information on others. A Bayesian network consists of a set of variables (nodes) and a set of directed edges (connections between variables). Each variable has a set of mutually exclusive states. The variables together with the directed edges form a directed acyclic graph (DAG). For each variable v with parents w1, . . . , w.sub.n, there is defined a conditional probability table P(v|w.sub.1, . . . , w.sub.n. Obviously, if v has no parents, this table reduces to the marginal probability P(v).

Bayesian networks have been used in many application domains with uncertainty, such as medical diagnosis, pedigree analysis, planning, debt detection, bottleneck detection, etc. However, one of the major application areas has been diagnosis. Diagnosis (i.e., underlying factors that cause diseases/malfunctions that again cause symptoms) lends itself nicely to the modeling techniques of Bayesian networks.

The currently most efficient method for exact belief updating of Bayesian networks is the junction-tree method that transforms the network into a so-called junction tree, described in Jensen, F. V., Lauritzen, S. L., and Olesen, K. G., Bayesian Updating in Causal Probabilistic Networks by Local Computations, Computational Statistics Quarterly, 4:269-282 (1990). The junction tree basically clusters the variables such that a tree is obtained (i.e., all loops are removed) and the clusters are as small as possible. In this tree, a message passing scheme can then update the beliefs of all unobserved variables given the observed variables. Exact updating of Bayesian networks is NP-hard (Cooper, G. F., The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks, Artificial Intelligence, 42:393-405, (1990)), however, it is still very efficient for some classes of Bayesian networks. The network for the printing system contains several thousand variables and many loops, but can still be transformed to a junction tree with reasonably efficient belief updating.

Heckerman et al. 1995 presents a method for performing sequential troubleshooting based on Bayesian networks.

For a device to troubleshoot that has n components represented by the variables c.sub.1, . . . . c.sub.n, Heckerman et al. 1995 follow the single-fault assumption that requires that exactly one component is malfunctioning and that this component is the cause of the problem. If p.sub.i denotes the probability that component c.sub.i is abnormal given the current state of information, then

.times..times..times. ##EQU00001## under the single-fault assumption. Each component c.sub.i has a cost of observation, denoted C.sub.i.sup.o (measured in time and/or money), and a cost of repair C.sub.i.sup.r.

Under some additional mild assumptions not reproduced here (see Heckerman et al. 1995 for more information), it can then be shown that with failure probabilities p.sub.i updated with current information, it is always optimal to observe the component that has the highest ratio p.sub.i/C.sub.i.sup.o. This is intuitive, as the ratio balances probability of failure with cost of observation and indicates the component with the highest probability of failure and the lowest cost of observation. Under the single-fault assumption, an optimal observation-repair sequence is thus given by the plan set out in Table 1 below:

TABLE-US-00001 TABLE 1 Step 1: Compute the probabilities of component faults p.sub.i given that the device is not functioning. Step 2: Observe the component with the highest ratio p.sub.i/C.sub.i.sup.o. Step 3: If the component is faulty, then repair it. Step 4: If a component was repaired, then terminate. Otherwise, go to step 1.

In the plan described in Table 1 above, if a component is repaired in step 3, it is known from the single-fault assumption that the device must be repaired, and the troubleshooting process can be stopped. The algorithm works reasonably well if the single-fault assumption is lifted, in which case step 1 will take into account new information gained in steps 2 and 3, and step 4 will be replaced as in Table 2 below:

TABLE-US-00002 TABLE 2 Step 1: Compute the probabilities of component faults p.sub.i given that the device is not functioning. Step 2: Observe the component with the highest ratio p.sub.i/C.sub.i.sup.o. Step 3: If the component is faulty, then repair it. Step 4: If the device is still malfunctioning, go to step 1.

Heckerman et al. 1995 introduces a theory for handling a service call that is used when the expected cost of the most optimal troubleshooting sequence is higher than the cost of a service call (e.g., calling the manufacturer for assistance). The theory changes to the above plan that enables it to approximately handle systems with multiple faults and non-base observations. Non-base observations are observations on something that is not a component but potentially provides useful information for the troubleshooting process. In a companion paper (Breese, J. S. and Heckerman, D., Decision-theoretic Troubleshooting: A Framework for Repair and Experiment, Technical Report MSR-TR-96-06, (1996) Microsoft Research, Advanced Technology Division, Microsoft Corporation, Redmond, USA), the method is further advanced to also enable configuration changes in the system to provide further useful information that can potentially lower the cost of the optimal troubleshooting sequence.

However, the Bayesian-network based troubleshooters described by Heckerman et al. 1995 have a one-to-one correspondence between causes and actions which does not hold in reality, have myopic (one-step lookahead) selection of questions, and have too slow selection of questions when there are many of them. Furthermore, Heckerman et al. 1995 presents no method of knowledge acquisition for their troubleshooters.

SUMMARY OF THE INVENTION

In accordance with a preferred embodiment of the present invention, an authoring tool assists an author in building an automated troubleshooter for a product. The authoring tool includes a cause editor interface, an action editor interface and a question editor interface. The cause editor interface allows an author to place, in a cause data structure, information pertaining to causes of malfunction of the product. The action editor interface allows an author to place, in an action data structure, information pertaining to actions that can be taken to correct malfunction of the product. The question editor interface allows an author to place, in a question data structure, information pertaining to questions that can be asked a user of the product to help identify causes of malfunction of the product.

In the preferred embodiment, the authoring tool additionally comprises a library of modules, at least one of the modules containing troubleshooting information about a component of the product. The author can select modules from the library of modules when building the automated troubleshooter for the product.

For example, the information pertaining to causes relates to the following categories: name of the cause, parent of the cause, explanation of the cause, and probability of the cause being the source of malfunction. The information pertaining to the cause may additionally relate, for example, to the following categories: cause category, dependency on environment, and indication that a customer is not to access this cause information.

The information pertaining to an action relates, for example, to the following categories: name of the action, explanation of the action, causes solved by the action, probabilities that the action solves specified causes, and an indication whether the action is for information-gathering or is a potential solution. The information pertaining to the action also may relate, for example, to the following categories: an indication as to whether the action should be taken before other actions, an indication as to whether the action is a workaround, costs of taking the action, trustworthiness of the answer to the action, additional actions included with the action, whether the action can only be performed after a specified question has been answered, and whether the action cannot be performed after a specified question has been answered.

The information pertaining to a question, for example, relates to the following categories: name of the question, explanation of the question, number of answers, names of answers, and costs of answers. The information pertaining to the question also may additionally relate, for example, to the following categories: whether the question can only be performed after a is specified question has been answered, whether the question cannot be performed after a specified question has been answered, an indication as to whether the question should be asked before other questions, and whether the question is a symptom question or a general question. When information pertaining to the question particularly pertains to a symptom question, the information may additionally relate, for example, to the following categories: causes of the symptom, probability of answers to the question conditional on causes of the symptom, and probability of answers to the question conditional on none of the causes that can cause the symptom. When information pertaining to the question particularly pertains to a general question, the information may additionally relate, for example, to the following categories: prior probabilities of answers to the question, causes that are affected by answers to the question, and probability of the affected causes conditional on each answer to the question.

In the preferred embodiment, the cause editor interface allows an author to create new cause entries and delete and edit existing cause entries. The action editor interface allows an author to create new action entries, and delete and edit existing action entries. The question editor interface allows an author to create new question entries, and to delete and edit existing question entries.

An authoring tool in accordance with the preferred embodiment of the present invention greatly decreases the time requirements of knowledge acquisition. The authoring tool is structured such that the author is guided through a series of questions that allows him to specify only the absolute minimum amount of information. The authoring tool is structured such that information of the domain is specified in ways that are proven to be natural and intuitive to the domain experts. The authoring tool is structured such that knowledge of Bayesian networks is not required, thus, a Bayesian network expert is no longer required to be present during the knowledge acquisition (KA) process. Also, initial construction of troubleshooting models for error conditions in the domain in question will be relatively slow, however, through the reuse of modules the authoring speed will increase as more and more modules in the domain will be built.

The authoring tool allows swift maintenance of prior constructed troubleshooters. Prior to the existence of the authoring tool, direct manipulation of the underlying Bayesian network was required to modify the behavior of a troubleshooter. However, with the authoring tool, the required changes can be performed on a representation much more suited to the purpose. Further, due to reuse of modules, a change in a module can be propagated to all the places where this module is used. Thus, time requirements for maintenance of troubleshooter models are decreased greatly.

The authoring tool allows swift migration from one product to the next. As troubleshooting information is arranged in a modular manner, it is a quick and easy process to migrate a troubleshooter for one product to the next by simply considering only the modules that have changed. With many product series, there are only few changes between different versions, different revisions and or different models. The required changes usually reside in clearly defined modules. Further, when creating initial troubleshooting models for a product, information that is likely to change with the next model can be flagged. Thus when migrating these models, the authoring tool can display the flagged information for consideration by the domain expert. In this way time requirements for migration can be decreased by the arrangement of information in modules and flagging of information likely to change between models.

The preferred embodiments of the invention allow the knowledge acquisition to be performed by the people with the knowledge of the domain, that is, the domain experts. No expertise with Bayesian networks, troubleshooting algorithms, etc., is necessary. Thus, the authoring tool described herein allows the minimal labor possible to generate troubleshooters.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an overview of a troubleshooting environment in accordance with a preferred embodiment of the present invention.

FIG. 2 is a simplified block diagram of a web server in accordance with a preferred embodiment of the present invention.

FIG. 3 is a simplified block diagram of components within a customer personal computer used in the troubleshooting process in accordance with a preferred embodiment of the present invention.

FIG. 4, is an overview of steps to perform knowledge acquisition in accordance with a preferred embodiment of the present invention.

FIG. 5 shows a main interface for an authoring tool in accordance with a preferred embodiment of the present invention.

FIG. 6 shows an interface for a cause editor in accordance with a preferred embodiment of the present invention.

FIG. 7 shows an interface for a cause probability editor in accordance with a preferred embodiment of the present invention.

FIG. 8 shows an interface for a cause category editor in accordance with a preferred embodiment of the present invention.

FIG. 9 shows an interface for an action editor in accordance with a preferred embodiment of the present invention.

FIG. 10 shows an interface for an action probability editor in accordance with a preferred embodiment of the present invention.

FIG. 11 shows an interface for a general question editor in accordance with a preferred embodiment of the present invention.

FIG. 12 shows an interface for a probability change editor in accordance with a preferred embodiment of the present invention.

FIG. 13 shows an interface for a symptom question editor in accordance with a preferred embodiment of the present invention.

FIG. 14 shows an interface for an explanation editor in accordance with a preferred embodiment of the present invention.

FIG. 15 shows an interface for a cost editor in accordance with a preferred embodiment of the present invention.

FIG. 16 shows an interface for an extra information editor in accordance with a preferred embodiment of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 1 is an overview of a troubleshooting environment in accordance with a preferred embodiment of the present invention.

FIG. 1 shows a web-server 200, a customer personal computer (PC) 205, a printer server 209 and a printer 210. A printer system troubleshooter 201 runs on a web-server 200. A user on customer PC 205 can access troubleshooter 201 over Internet 202. A web-browser 206 within customer PC 205 is used to access web-server 200. In response to the customer's interaction with troubleshooter 201, troubleshooter 201 responds with suggestions 203 for troubleshooting steps that the customer can perform. Troubleshooter 201 essentially functions as an expert system that utilizes artificial intelligence. The customer provides information 204 back to troubleshooter 201 which informs troubleshooter 201 on the outcome from acting on suggestions 203. Information 204 may include information 207 the customer obtains from printer server 209 and/or information 208 the customer obtains from printer 210.

FIG. 2 is a simplified block diagram of web-server 200. Troubleshooter 201 executes in a memory 301 of web-server 200. Troubleshooter 201 utilizes secondary storage devices 303 for storage of troubleshooting models. A video display 304 can be used by a technician to monitor the troubleshooting process and to maintain the troubleshooting models. Web server 200 also includes an input device 305, such as a keyboard, a CPU 306 and a network card 307 for communication with web-browser 206 in customer PC 205.

FIG. 3 is an overview of the components of the troubleshooting process. Web-server 200 is shown. The customer communicates with troubleshooter 201 (shown in FIG. 1) within web-server 200 through web-browser 206 running on customer PC 401. The customer receives suggestions 203 from troubleshooter 201 and in return provides answers 204. The customer uses troubleshooter 201 when experiencing a malfunction in the printer system which consists of printer server 209 and printer 210. In general, when a customer attempts to print from an application 406, the print job first goes to a printer driver 407, then through a local spooler 408, if utilized, and then to an operating system (O/S) redirect 409. O/S redirect 409 is the part of the operating system that determines which way the print job goes, i.e., to a network connection 413 via a network driver 410 and a network card 411, or to a local port 412 in the case of a local parallel connected printer. If the print job goes to a local parallel connected printer, the print job goes through a parallel cable 415 before reaching printer 210. If the print job goes to a network printer, it either goes through network connection 413 to printer server 209, or through a direct network connection 414 to printer 210. Direct network connection 414 may be utilized for certain printers, e.g., the HP LaserJet 5Si available from Hewlett-Packard Company, having a business Address of 3000 Hanover Street, Palo Alto, Calif. 94304. When printer 210 is controlled by printer server 209, the print job goes through a printer queue 420 in printer server 209, and then the print job is sent across either a network connection 417 to printer 210, or a parallel cable 418, depending upon how printer 210 is connected to printer server 209.

Application 406, printer driver 407, spooler 408 and O/S redirect 409 all execute in operating system 405 on customer PC 205. When printing a print job from application 406, the print job follows one of the above-described paths on its way to printer 210, depending on the system setup. If anything goes wrong along the way, this can result in no output or unexpected output. Troubleshooter 201 will, through tests on components in the system, attempt to determine which component(s) caused the problem.

FIG. 4, is an overview of steps to perform knowledge acquisition in order to implement troubleshooter 201. The knowledge acquisition process is the process of constructing the troubleshooting models by gathering sufficient information about the domain from so-called domain experts. The domain experts are familiar with the domain that is being modeled, in this case printer systems. These domain experts have intimate knowledge of the domain under consideration, having assisted in the construction phase, troubleshooting or support phase of the product. The knowledge acquisition process has to be guided by someone familiar with the rules and requirements of the process. Participating in or guiding the knowledge acquisition process requires no expertise in the area of Bayesian networks. To aid in illustration, the problem of "light print" is used as an example throughout discussion of the steps disclosed in FIG. 4. "Light print" is the problem of the user receiving an output from the printer that is lighter than expected.

In a step 900, the issues to troubleshoot are identified. The problem that is being modeled is identified, defined precisely and separated from other problems. Initially, it is very important to precisely define the problem under consideration and the audience of the troubleshooting tool, as this will have a large impact on the following knowledge acquisition steps. The skill level of the audience is important when specifying both causes and steps, as there are causes and steps that cannot be manipulated by end users, but can be manipulated by experienced troubleshooters. In the following, it is assumed that there is an audience of end users that have only rudimentary understanding of the printer system, but can be guided to perform complicated steps.

In a step 901, causes of the issue are identified. In this step, the domain experts identify the causes of the problem under consideration. Causes are basically all the different components, properties or events that can cause the problem.

It is usually impossible and/or not necessary to identify and specify all causes, as there are causes that are too rare to be worth considering e.g., gravity out of specification causing printing problems or causes that cannot be affected by the user anyway e.g., advanced technical problems with printer components. These causes are then gathered in a single leak cause termed "other problems" which further has two subcauses representing respectively "temporary problems" that can be solved by power cycling the printer, and "permanent problems" that cannot be solved by the user.

One of the difficulties in identifying causes is the decision of whether to group sets of causes as a single cause or whether to keep the causes separate. As a rule of thumb it is easier to do the knowledge acquisition for actions, if causes for which there are different actions are kept separate.

For example, for the problem of "light print" the following causes and subcauses were identified as set out in Table 3 below:

TABLE-US-00003 TABLE 3 Cause/Subcause Explanation Media If the paper is of such a type that the toner doesn't stick correctly to it, this can cause light print. Paper path dirty If the paper path is dirty there is a chance that this causes lighter print. Environmental conditions - humidity, temperature, etc. can all cause lighter print if they are extreme. Toner cartridge Problems with the toner cartridge can problems cause ligher print, e.g., if the cartridge is low on toner. Transfer roller The transfer roller allows the toner problems image on the drum surface to be transferred to or placed on the media and can thus also cause light print. Incorrect application settings - obviously there are settings that can cause light print, if set incorrectly, both in the application, printer driver and on the control panel of the printer itself Incorrect printer driver settings Incorrect control panel settings Corrupt data flow There is a slight change that the print job can be corrupted somewhere in the flow from the application through the network to the printer, such that it prints out lighter than expected. Wrong driver used Using the incorrect driver for the printer can cause light print. Other problems As mentioned above there are causes of light print that it is not worth considering and they are gathered under this heading

Experience has shown that modeling the causes at this level, closely resembles the manner of thinking employed by experienced printing system call agents. When they troubleshoot printer problems over the phone, they maintain in their minds a list of the causes and subcauses similar to the above, and continually adjust the beliefs of the different causes based on the conversation with the customer.

In a step 902, subcauses, if any, are identified. Often, it is convenient to organize causes into categories. These categories are then seen as causes with a number of subcauses. It is not strictly necessary to use subcauses of causes, as it is entirely possible to have all subcauses on the same top level. However, this approach often leads to a high number of causes on the top level, making the acquisition of probabilities more difficult. Organizing the causes into a hierarchy allows the domain expert to consider fewer causes at a time when estimating probabilities, thus providing more accurate information.

While in FIG. 4 there are only represented two levels of the cause-structure, there can be arbitrarily many levels of causes and subcauses.

The finished hierarchy of causes for "light print" is as is set out in Table 4 below:

TABLE-US-00004 TABLE 4 1) Media 2) Paper path dirty 3) Environmental conditions 4) Toner cartridge problems a) Defective toner cartridge b) Improperly seated toner cartridge c) Toner distribution - this includes low on toner and other problems with the toner fluid. 5) Transfer roller problems a) Defective or dirty transfer roller b) Improperly seated transfer roller c) Worn out transfer roller 6) Incorrect application settings a) Economode/draft mode on - economode is set to save toner, and thus causes a lighter print than ordinarily. b) 300/600 dpi set to 300 dpi - 300 dpi may cause lighter print than 600 dpi prints. c) Other settings set wrong - other settings that may cause light print. 7) Incorrect printer driver settings a) Economode set on b) 300/600 dpi set to 300 dpi c) Other settings set wrong 8) Incorrect control panel settings a) Economode/draft mode set on b) 300/600 dpi set to 300 dpi c) Print density set too low 9) Corrupt data flow 10) Wrong driver used 11) Other problems a) Temporary problem b) Permanent problem

In a step 903, troubleshooting steps of the issue are identified. Actions that can solve any of the causes of the problem, and questions that can provide information regarding the causes are listed.

When listing the troubleshooting steps of a problem, the domain experts basically consider the steps they themselves would perform or suggest for the customer to perform, if they were faced with the problem. Experience shows that it is beneficial to start out listing the steps without considering the previously listed causes, i.e., with a "blank" mind, as this will occasionally bring otherwise forgotten steps into mind. Then, when these first steps have been listed, it is good to consider the list of causes and add all steps that potentially solve these causes.

When listing troubleshooting steps, only steps that can be performed by the assumed audience of the troubleshooter should be listed, e.g., if the audience is end users, it is irrelevant to suggest steps that require a high technical understanding of the printing system to be performed successfully. There are also steps that carry a high risk of breaking something else when performed by inexperienced users, that should not be included. Steps that require highly expensive requisites are also steps that should not usually be included.

Again, the domain expert faces the problem of size and coverage of steps. There are troubleshooting procedures that can be equivalently modeled as a single step or a series of steps. The rule of thumb here is that it depends on the user interface and the step itself how to represent a step. If the step can be conveniently represented as a deterministic flow-diagram if-then-else structure, and the user interface of the troubleshooter supports the implementation of such deterministic "programs", then the step should be modeled as a single step. If the flow-diagram of the step includes uncertain/probabilistic decisions, the step has to be represented as multiple steps.

There are two main categories of troubleshooting steps, actions and questions. The first category, actions, are steps that require the user to perform some kind of intervention in the system, and report back to the troubleshooter whether the action solved the problem or not. Thus, actions have the potential to solve the problem. The second category, questions, are steps that require the user to obtain some information related with the problem at hand possibly by intervening with the system, and report back the result to the troubleshooter. Questions are grouped into two subcategories, information-gathering actions and general questions.

Information-gathering actions are actions that do not have the potential to solve the problem. They merely provide information, that is relevant to solving the problem. Ordinary actions are also termed solution actions to distinguish them from the information-gathering actions. It is important to distinguish, as the two types of actions are handled differently in the troubleshooting algorithms, as further described below where information-gathering actions are treated as questions. To clarify, this means that algorithmically there is no difference between information-gathering actions and questions. However, the distinction is kept during knowledge acquisition as it is easier for domain experts to elicit probabilities for information-gathering actions if they are treated as actions.

The distinction between information-gathering and solution actions should also be clarified. Solution actions have the potential to solve the problem while information-gathering actions cannot possibly solve the problem. Information-gathering actions only have the potential to temporarily remove the problem while some change to the environment is tried out.

General questions are the remaining questions that are not information-gathering actions. Questions do not have the potential to solve the problem, and can have any number of answers as opposed to actions that only have two: yes (it helped) and no (it didn't). the problem, and can have any number of answers as opposed to actions that only have two: yes (it helped) and no (it didn't).

When listing the troubleshooting steps of a problem, they must be categorized as either solution actions (SA), information-gathering actions (IA) or questions (Q).

For all actions and questions, explanations should be written as early in the knowledge acquisition process as possible, as these explanations/definitions help to reduce future confusion and ensure that errors are caught as early as possible.

For the "light print" problem, the following steps were identified, as set out in Table 5 below:

TABLE-US-00005 TABLE 5 A) Ensure that media is within specifications (SA) B) Try another toner cartridge that is within specification (IA) C) Remove, shake and reinsert toner cartridge (SA) D) Reseat transfer roller (SA) E) Try different media (IA) F) Perform printer maintenance kit (SA) G) Power cycle the printer (SA) H) Ensure that environmental conditions are within specifications (SA) I) Clean the inside of the printer according to the user manual (SA) J) Try another in-spec transfer roller (IA) K) Ensure economode/draft more is not on in the application (SA) L) Ensure 300 dpi is not set in the application (SA) M) Examine and correct other application settings related to "light print" (SA) N) Ensure economode is not on in the printer driver (SA) O) Ensure 300 dpi is not set in the printer driver (SA) P) Examine and correct other printer driver settings related to "light print" (SA) Q) Ensure economode/draft more is not on on the control panel of the printer (SA) R) Ensure 300 dpi is not set on the control panel of the printer (SA) S) Ensure print density is not set too low on the control panel (SA) T) Troubleshoot the data flow (SA) U) Ensure that an in-spec up-to-date printer driver is used (SA) V) Is the printer maintenance kit due? (Q) W) Is the toner cartridge from a supported manufacturer? (Q) X) Does the control panel say "Toner low"? (Q) Y) Is the printer configuration page printed light? (Q)

A few of the above steps are classified as information-gathering actions, e.g., step B "Try another toner cartridge". If, after performing step B, the problem is removed, the problem is still not solved. The likely cause of the problem has been identified, but there are further investigations that could be done, and the other toner cartridge probably has to be returned to the place it came from, i.e., the problem is not solved. This is generally true for steps that replace a printer component with another--if they succeed, the scope of the troubleshooting has been significantly narrowed down, but there are still remaining steps that can be performed to solve the problem completely.

Step F in Table 5 suggests performing the printer maintenance (PM) kit which must be performed every time a specific amount of pages has been printed. If the PM kit must be performed, the control panel of the printer will usually give a notification, but not necessarily always. It is a good idea to ask whether it is suggested on the control panel, before suggesting the PM kit, as the PM kit should only be performed if absolutely necessary.

Step T in Table 5 is a large and complicated troubleshooting step consisting of a series of substeps attempting to determine whether the print job is corrupted somewhere in the dataflow, and identifying the source of the corruption. Basically, the entire dataflow model for corrupt output described below fits under step T and its associated cause.

In a step 904, causes and troubleshooting steps are matched. The troubleshooting steps are matched with the causes that they can solve. Additionally, the causes that are associated with questions are identified. In this step, the causes are matched with troubleshooting steps such that actions are matched with the causes that they can solve, and questions are matched with the causes that they are associated with (i.e., affect the probabilities of).

For each action, A.sub.i, it is considered for each cause, C.sub.j, whether there is a non-zero probability that performing A.sub.i will solve C.sub.j. If this is so, there is a match which is registered for later use in the knowledge acquisition process.

Information-gathering actions can be handled almost similarly to solution actions. Even though they are not able to solve the problem, they are still able to temporarily remove the problem while trying some change in the environment. For instance, in step B within Table 5 above, "Try another toner cartridge" will cause the problem to go away, if the cause is subcause 4a, 4b or 4c, as listed in Table 4 above. So, for information-gathering actions the causes for which the action will remove the problem when performed are still registered.

For each question, Q.sub.i, it is considered for each cause, C.sub.j, whether an answer to Q.sub.i will directly affect the belief in C.sub.j (i.e., cause the probability to decrease or increase).

Questions do not have to affect the beliefs of any causes at all as they are sometimes used to provide information about the troubleshooting scenario, user type, etc. to allow/disallow related actions. An example of this could be a question about the type or manufacturer of certain components, the answer to which controls whether the component supports certain actions. Thus, the probability of these actions succeeding is zero when the manufacturer of the component is not of the right type.

For the "light print" problem, the matching of steps and causes is as shown in Table 6 below. After each action or question, the associated causes (keyed to Table 4 above) are listed:

TABLE-US-00006 TABLE 6 Troubleshooting Steps Causes A) Ensure that media is within specifications (SA) 1 B) Try another toner cartridge that is within 4 specification (IA) C) Remove, shake and reinsert toner cartridge (SA) 4b, 4c D)