METHOD AND SYSTEM USING LINEAR PROGRAMMING FOR ESTIMATING TEST COSTS FOR BAYESIAN DIAGNOSTIC MODELS

• US 20090094076A1
• Filed: 10/05/2007
• Published: 04/09/2009
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Reddy, Sudhakar Y.
• Granted Patent: US 8,463,641 B2
• Time in Patent Office: Days
• US Class Current: 705/7.41
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06395 Quality analysis or management

Abstract

In accordance with an embodiment, a method for troubleshooting a fault to determine a root cause of the fault. A Bayesian network model is created based on information obtained from a Fault Isolation Manual (FIM), where the FIM provides tests to be performed in troubleshooting the fault to determine a root cause of the fault. Heuristics are used to determine a structure and conditional probabilities for the Bayesian network. A plurality of test costs inherent in the FIM are imputed by first generating a plurality of constraints between the cost of each test and fault probabilities that hold for all fault scenarios. A linear programming algorithm is used to solve the plurality of constraints, and to construct a tuned Bayesian network model. The tuned Bayesian network model is used to iteratively rank likely faults according to their probabilities given accumulating test evidence, and to rank pending tests according to their value.

Claims

1. A method for troubleshooting a fault to determine a root cause of the fault, comprising:

creating a Bayesian network model based on information obtained from a Fault Isolation Manual (FIM), where said FIM provides tests to be performed in troubleshooting said fault to determine a root cause of said fault;

using heuristics to determine a structure and conditional probabilities for the Bayesian network;

imputing a plurality of test costs inherent in the FIM by first generating a plurality of constraints between the cost of each test and fault probabilities that hold for all fault scenarios;

using a linear programming algorithm to solve these for said plurality of constraints, and to construct a tuned Bayesian network model; and

using the tuned Bayesian network model to iteratively rank likely faults according to their probabilities given accumulating test evidence, and to rank pending tests according to their value.

2. The method of claim 1, further comprising displaying said test values in an ordered list on a display, wherein each said test value further comprises a sum of information entropy, if a specific test outcome is known, and a test cost of the specific test.

3. The method of claim 2, further comprising displaying said test values from lowest to highest on said display.

4. The method of claim 1, further comprising using said Bayesian network model and imputed costs for each said available test called for in said Bayesian network model, to generate an ordered list of faults based on a probability of failure of each part of a system being troubleshot.

5. The method of claim 1, further comprising displaying said ordered list of faults in a list from highest probability of fault to lowest probability of fault.

6. The method of claim 1, wherein creating a Bayesian network model based on information obtained from the Fault Isolation Manual comprises initially creating a graph, based on said FIM, of a troubleshooting procedure for isolating a root cause of said fault.

7. The method of claim 6, wherein creating a graph comprises creating a directed acyclic graph (DAG) in accordance with troubleshooting procedures set forth in said FIM.

8. The method of claim 1, wherein using linear programming algorithm comprises iteratively generating said costs for each said available test that may be performed in troubleshooting said fault.

9. A method for troubleshooting a fault to determine a root cause of the fault in a time and cost efficient manner, comprising:

using information from a Fault Isolation Manual (FIM) to form a graph of a test procedure to be carried out in troubleshooting the fault;

using the graph to construct a Bayesian network model based on a causality implied by the graph;

using heuristics to determine a structure and conditional probabilities for the Bayesian network;

imputing a plurality of test costs inherent in the FIM by first generating a plurality of constraints between the cost of each test and fault probabilities that hold for all fault scenarios;

using an algorithm to solve these for said plurality of constraints, and to construct a tuned Bayesian network model;

using the tuned Bayesian network model to iteratively rank likely faults according to their probabilities given accumulating test evidence, and to rank pending tests; and

displaying the ranked tests on a display system.

10. The method of claim 9, wherein the ranked tests are ranked according to their value.

11. The method of claim 10, further comprising generating a ranked list of faults based at least in part on probabilities associated with particular items of information imputed from the FIM.

12. The method of claim 10, wherein ranking said tests according to their value comprises calculating a total cost of each said available test using a linear programming algorithm, and constraints imposed by the available tests and order of said available tests, to solve for a total cost of each said available test.

13. The method of claim 10, further comprising using a total cost of each said available test to generate an ordered list of test values for all of said tests set forth in said Bayesian network model.

14. The method of claim 13, further comprising displaying said ranked order of test values from lowest test value to highest test value.

15. The method of claim 10, wherein forming a graph comprises forming a directed acyclic graph (DAG).

16. A method for troubleshooting a fault to determine a root cause of the fault in a time and cost efficient manner, comprising:

using information from a Fault Isolation Manual (FAM) to form a directed acyclic graph (DAG) of a test procedure comprising a plurality of texts to be carried out in troubleshooting the fault;

using the DAG to construct a Bayesian network model based on the causality implied by the DAG;

using heuristics to determine a structure and conditional probabilities for the Bayesian network;

imputing a plurality of test costs inherent in the FIM by first generating a plurality of constraints between the cost of each test and fault probabilities that need to hold for all possible fault scenarios;

using an algorithm to solve these for said plurality of constraints, and to construct a tuned Bayesian network model;

using the tuned Bayesian network model to iteratively rank likely faults according to their probabilities; and

displaying said results.

17. The method of claim 16, wherein said faults are ranked in accordance with accumulating test evidence according to their value.

18. The method of claim 16, wherein said algorithm comprises a linear programming algorithm.

19. The method of claim 16, further comprising displaying test costs in a list on a display, from lowest test cost to highest test cost.

20. The method of claim 16, further comprising displaying a ranked order of possible component faults on a display, from most probable to least probable.

21. The method of claim 16, wherein the value of each test is estimated using an information entropy metric H described by the expression