Technique for producing an expert system for system fault diagnosis

• US 5,107,497 A
• Filed: 07/28/1989
• Issued: 04/21/1992
• Est. Priority Date: 07/28/1989
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Yue, On C., Lirov, Yuval V.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Chung, Phung My
• Application Number:
  US07/386,325
• Time in Patent Office: 998 Days
• Field of Search: 371/15.1, 364/551.01, 364/550
• US Class Current: 714/26
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: Y10S 706/911 Nonmedical diagnostics

Abstract

The present invention relates to a technique for operation on a computer for developing the knowledge base for ultimately providing very fast and cost-efficient fault diagnosis systems. The present technique uses an effective hierarchy of rules where at a first level are rules which allow the arrangement of the system under test to be decomposed into a hierachy of sequential and parallel subsystems. At the second level are rules that generate the efficient testing rules for each pure subsystem. The second level rules can be compared to a node evaluation function in a typical problem of searching a graph to select the best node for expansion from a current list of candidate nodes, so that the best path to the correct system diagnosis is found in the shortest amount of time using a minimum of user input. Two heuristic rules are applied to speed-up the process of selecting the node as the best candidate for expansion. The resultant hierarchy of rules permit the cost-efficient knowledge base and resultant output test tree procedure to be generated for a fault diagnosis system to be applied for testing an associated device or system.

Claims

1. A method of forming a knowledge base in a computer for producing an expert system for diagnosing a predetermined arrangement of a system to determine if the system contains a fault, said system comprising a plurality of components having respective predetermined failure rates, the method comprising the steps of:

(a) decomposing the system into groups of sequential and parallel subsystems, each of said subsystems comprising at least one of said components;

(b) generating a tree structure of the groups of step (a) by attaching nodes to each parallel and sequential link between subsystems in the tree to provide a tree configuration of sets of components suspected of being faulty and possible choice measurement sets;

(c) computing a lower bound cost of a sequence of tests for each of the parallel and sequential subsystems using a first rule that (1) if a node is a parallel node, then the lower bound cost for that node is computed by

(i) sorting numerically and in a first predetermined order a first list P of the failure rates of the components of each subsystem,

(ii) sorting numerically and in a second predetermined order a second list L of test costs of the components of each subsystem, and

(iii) for corresponding elements in lists P and L, computing a product of each of the corresponding elements, and (2) a second rule that if the node is a sequential node, then the lower bound cost of the sequence of test cases for that node is computed by

(i) separately sorting numerically and in a predetermined order each of the failure rate and the test cost for each component of each subsystem in the first and second lists P and L, respectively,

(ii) initializing a variable h to zero,

(iii) selecting the lowest valued two numbers p₁ and p₂ from the list P,

(iv) computing a current value for a failure rate p by summing p₁ and p₂

(v) selecting a first member c from list L,

(vi) summing the current value of h with the product of the value of p₁ and p₂ from step (iv), and placing such sum for the current value for h,

(vii) inserting the current value of p in numerical order in list P, and

(viii) repeating steps (iii) to (vii) until p=1; and

(d) generating a diagnostic knowledge base for generating a diagnostic fault testing sequence at an output of the computer.

2. The method according to claim 1 wherein in computing step (iii) for the lower bound cost for a parallel node performing the steps of:

(c1) initializing a first and second variable h and q to 0 and 1, respectively;

(c2) selecting a first member c from list L;

(c3) computing the product of h+c·

q and substituting such value for the current value of h;

(c4) selecting a last member p from list P;

(c5) subtracting the selected member p in step (c4) from the current value of q and substitute such subtracted value as the current value of q; and

(c6) repeating steps (c2) to (c5) until the number of elements in list P=1.

3. The method according to claim 1 wherein in performing step (d) performing the step of:

(d1) the computer computing the lower bound cost for the test cases of a parallel node in accordance with an expression defined by ##EQU3## where i includes all possible partitions of the system, q_i is a subnode_i probability, and the choice measurement set is determined from

space="preserve" listing-type="equation">t.sub.i =arg min c(node).

4. The method according to claim 1 wherein in performing step (d) performing the step of:

(d1) the computer computing the lower bound cost for the test cases of a sequential node in accordance with an expression defined by ##EQU4## where i includes all possible partitions of the system, left subnode corresponds to the node obtained when test t_i passed, right subnode corresponds to the node obtained when test t_i failed, and the choice measurement set is determined from

space="preserve" listing-type="equation">t.sub.i =arg min c(node).

5. A method according to claim 1, wherein in performing steps (a) and (b), performing the steps of:

(e1) constructing a single parallel node if all of the components of the system are connected in parallel;

(e2) constructing a single sequential node if all of the components of the system are connected in sequence;

(e3) subdividing a parallel node into a sequence of a two nodes, with one of said two nodes comprising a common prefix component and the other one of said two nodes comprising all remaining components, if said common prefix component is common to all component sequences of said parallel node; and

(e4) if several parallel subnodes of a super component sequence node include common prefixes or suffices, then deleting such parallel subnodes and inserting parallel subnodes into the super component sequence node in a predetermined order.