Method and apparatus for generation of multi-branched diagnostic trees

Claim 2

In an automated diagnostic reasoning system comprising a fault candidate generator, a best measurement mechanism, a constraint propagator mechanism, a dependency tracking mechanism, and a model of a system to be diagnosed, said model including terminals indicating measurement points in the system to be diagnosed, a method for automated generation of a diagnostic tree comprising the steps of: a) determining an operating value for each of said terminals; b) selecting a granularity for each node of said diagnostic tree; c) establishing at least one terminal as a root node and establishing the root node as a selected node; d) generating a plurality of branches extending from said selected node, the number of branches extending from said selected node corresponding to said selected granularity, and selecting a branch value to correspond to each of said generated branches; e) selecting one of said branches of said selected node not terminating in a leaf node for analysis; f) propagating the branch value of said selected branch through said model thereby generating a propagated value for said terminals; g) identifying conflicts between propagated values at each terminal and generating conflict candidate sets; h) terminating the selected branch with a leaf node denoting no further fault isolation is possible if no conflict set exists; i) terminating the selected branch with a node denoting multiple faults if multiple, nonintersecting conflict sets exists; j) terminating the selected branch with a leaf node denoting a single fault if one conflict set having a single component exists; k) attempting to identify a next measurement to be made if at least one conflict set exists, terminating the selected branch with a leaf node denoting no further fault isolation is possible if no next measurement can be identified, terminating the selected branch with a measurement node corresponding to an identified next measurement and establishing said measurement node as the selected node and returning to step (d) if a next measurement can be identified; l) finding a branch not terminated with a node and establishing the found branch as the selected branch and returning to step (f); m) finding a measurement node without established branches, establishing said measurement node as the selected node, and returning to step (d) if a measurement node is established; and n) stopping tree generation if all branches are terminated with leaf nodes.

Claim 3

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein selecting the granularity of each node of said tree comprises the step of: setting the granularity of each node to equal at least two if at least one component of said system to be diagnosed has an analog input or output.

Claim 4

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein the granularity of each node is equal to the granularity of the root node.

Claim 5

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein the granulariry of each node may vary.

Claim 6

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein the granularity of each node is selected by a system user.

Claim 7

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein the granularity of each node is selected automatically.

Claim 8

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein establishing a terminal of said model as a root node comprises the steps of: identifying an output terminal of said model; and establishing said identified output terminal as said root node.

Claim 9

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein establishing a terminal of said circuit model as a root node comprises the steps of: identifying a component most likely to be faulty based on prior experience; identifying an output terminal of said identified component; and establishing said identified output terminal as said root node.

Claim 10

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein measurement at a plurality of terminals is established as a root node.

Claim 11

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein said selected value is a single numerical value.

Claim 12

A method for automated generation of a:diagnostic tree in accordance with claim 1 wherein said selected value is a range of numerical values.

Claim 13

A method for automated generation of a diagnostic tree in accordance with claim 1 further comprising the step of: finding a node denoting multiple faults, establishing said multiple fault node as a selected node and returning to step (d) before stopping tree generation.

Claim 14

A method for automated generation of a diagnostic tree in accordance with claim 1 wherein a node denoting multiple faults is established as a leaf node.

Claim 15

An automated diagnostic apparatus, comprising: means for making predictions about terminal values using a model of a system to be diagnosed and assigning predicted values to terminals of said model; means for generating conflicts between said assigned values and actual measured values and between different sets of assigned values; means for identifying a next measurement to be made for isolating a fault; said automated diagnostic apparatus being programmed to perform the steps of: a) determining an operating value for each of said terminals; b) selecting a granularity for each node of said diagnostic tree; c) establishing a first terminal as a root node and establishing the root node as a selected node; d) generating a plurality of branches extending from said selected node, the number of branches extending from said selected node corresponding to said selected granulariry, and selecting a branch value to correspond to each of said generated branches; e) selecting one of said branches of said selected node not terminating in a leaf node for analysis; f) propagating the branch value of said selected branch through said model thereby generating a propagated value for said terminals; g) identifying conflicts between propagated values at each terminal and generating conflict candidate sets; h) terminating the selected branch with a leaf node denoting no further fault isolation is possible if no conflict set exists: i) terminating the selected branch with a node denoting multiple faults if multiple, nonintersecting conflict sets exists: j) terminating the selected branch with a leaf node denoting a single fault if one conflict set having a single component exists; k) attempting to identify a next measurement to be made if at least one intersecting conflict set exists, terminating the selected branch with a leaf node denoting no further fault isolation is possible if no next measurement can be identified, terminating the selected branch with a measurement node corresponding to an identified next measurement and establishing said measurement node as the selected node and returning to step (d) if a next measurement can be identified: l) finding a branch not terminated with a node and establishing the found branch as the selected branch and returning to step (f); and m) finding a measurement node without established branches, establishing said measurement node as the selected node, and returning to step (d) if a measurement node is established; n) stopping tree generation if all branches are terminated with leaf nodes.

Claim 16

An automated diagnostic apparatus, comprising: means for making predictions about terminal values using a model of a system to be diagnosed and assigning predicted values to terminals of said model; means for generating conflicts between said assigned values and actual measured values and between different sets of assigned values; means for identifying a next measurement to be made for isolating a fault; said automated diagnostic apparatus being programmed to perform the steps of: a) determining an operating value for each of said terminals; b) selecting a granularity for each node of said diagnostic tree; c) establishing a first terminal as a root node and establishing the root node as a selected node; d) generating a plurality of branches extending from said selected node, the number of branches extending from said selected node corresponding to said selected granulariry, and selecting a branch value to correspond to each of said generated branches; e) selecting one of said branches of said selected node not terminating in a leaf node for analysis; f) propagating the branch value of said selected branch through said model thereby generating a propagated value for said terminals; g) identifying conflicts between propagated values at each terminal and generating conflict candidate sets; h) terminating the selected branch with a leaf node denoting no further fault isolation is possible if no conflict set exists: i) terminating the selected branch with a node denoting multiple faults if multiple, nonintersecting conflict sets exists: j) terminating the selected branch with a leaf node denoting a single fault if one conflict set having a single component exists; k) attempting to identify a next measurement to be made if at least one intersecting conflict set exists, terminating the selected branch with a leaf node denoting no further fault isolation is possible if no next measurement can be identified, terminating the selected branch with a measurement node corresponding to an identified next measurement and establishing said measurement node as the selected node and returning to step (d) if a next measurement can be identified: l) finding a branch not terminated with a node and establishing the found branch as the selected branch and returning to step (f); and m) finding a measurement node without established branches, establishing said measurement node as the selected node, and returning to step (d) if a measurement node is established; n) stopping tree generation if all branches are terminated with leaf nodes.

Claim 17

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein selecting the granularity of each node of said tree comprises the step of: setting the granularity of each node to equal at least two if at least one component of said system to be diagnosed has an analog input or output.

Claim 18

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein said means for identifying a next measurement identify a measurement which results in a minimum number of measurements required to isolate a fault.

Claim 19

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein said means for identifying a next measurement identify a measurement which results in a minimum cost to isolate a fault.

Claim 20

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein the granularity of each node is equal to the granularity of the root node.

Claim 21

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein the granularity of each node may vary.

Claim 22

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein the granulariry of each node is selected by a system user.

Claim 23

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein the granularity of each node is selected automatically.

Claim 24

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein establishing a terminal of said model as a root node comprises the steps of: identifying an output terminal of said model; and establishing said identified output terminal as said root node.

Claim 25

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein establishing a terminal of said model as a root node comprises the steps of: identifying a component most likely to be faulty based on prior experience; identifying an output terminal of said identified component; and establishing said identified output terminal as said root node.

Claim 26

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein measurement at a plurality of terminals is established as a root node.

Claim 27

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein said selected value is a single numerical value.

Claim 28

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein said selected value is a range of numerical values.

Claim 29

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 further comprising the step of: finding a node denoting multiple faults, establishing said multiple fault node as a selected node and returning to step (d) before stopping tree generation.

Claim 30

An apparatus for automated generation of a diagnostic tree in accordance with claim 14 wherein a node denoting multiple faults is established as a leaf node.

Claim 31

An apparatus in accordance with claim 14 wherein said leaf node identifies multiple faulty components.

Claim 32

In a model-based diagnostic reasoning system for generating a diagnostic tree including a root nodes, internal nodes and branches, a method for automatically assigning a granularity to each internal node, said method comprising the steps of: a) establishing at least one terminal as a root node and establishing the root node as a selected node; b) determining value for said one terminal; c) selecting a granularity for said root node; d) generating a plurality of branches extending from said root node, the number of branches extending from said root node corresponding to the selected granularity and selecting a branch value to correspond to each said generated branches; e) selecting one of said branches of said selected node not terminating in a node for analysis; f) propagating the branch value of said selected branch; g) attempting to identify a next measurement to be made at a terminal, if no next measurement can be found then terminating said selected branch in a leaf node; h) terminating the selected branch with a node identifying the terminal to be measured if a next measurement is identified; i) determining a number (N) of numeric ranges using the intervals propagated to the terminal to be measured; j) generating N branches from said node identifying the terminal to be measured; k) assigning each said branch one of said interval ranges; l) establishing a node having at least one branch not terminating in a node as the selected node and returning to step (e); and m) stopping tree generation when all paths of the tree terminate in leaf nodes.

Claim 33

In a model-based diagnostic reasoning system for generating a diagnostic tree including a root nodes, internal nodes and branches, a method for automatically assigning a granularity to each internal node, said method comprising the steps of: a) establishing at least one terminal as a root node and establishing the root node as a selected node; b) determining value for said one terminal; c) selecting a granularity for said root node; d) generating a plurality of branches extending from said root node, the number of branches extending from said root node corresponding to the selected granularity and selecting a branch value to correspond to each said generated branches; e) selecting one of said branches of said selected node not terminating in a node for analysis; f) propagating the branch value of said selected branch; g) attempting to identify a next measurement to be made at a terminal, if no next measurement can be found then terminating said selected branch in a leaf node; h) terminating the selected branch with a node identifying the terminal to be measured if a next measurement is identified; i) determining a number (N) of numeric ranges using the intervals propagated to the terminal to be measured; j) generating N branches from said node identifying the terminal to be measured; k) assigning each said branch one of said interval ranges; l) establishing a node having at least one branch not terminating in a node as the selected node and returning to step (e); and m) stopping tree generation when all paths of the tree terminate in leaf nodes.

Claim 34

A method for automatically assigning a granularity to each internal node in accordance with claim 30 wherein determining a number (N) of interval ranges resulting from propagating the range of values comprises the steps of: determining if any ranges intersect; and assigning each non-intersected portion of each said range to a respective branch and assigning each intersected portion to a respective branch.

Claim 35

A method for automatically assigning a granularity to each internal node in accordance with claim 31 further comprising the steps of: determining a mid-point for each of said non-intersected and intersected portions where possible; defining ranges in accordance with each of said non-intersected portions and their respective midpoints and each of said intersected portions and their respective midpoints; and generating branches and assigning each branch one of said defined ranges.

Claim 36

A method for automatically assigning a granularity to each internal node in accordance with claim 31 further comprising the steps of: combining intervals in a consecutive pair-wise manner; defining ranges in accordance with said combined intervals; and generating branches and assigning each branch one of said defined ranges.

Claim 37

A method for automatically assigning a granularity to each internal node in accordance with claim 30 wherein the granularity of said root node is user selected.

Claim 38

A method for automatically assigning a granularity to each internal node in accordance with claim 30 wherein the granularity of said root node is automatically selected.

Claim 39

A method for automatically assigning a granularity to each internal node in accordance with claim 30 wherein a maximum limit as to the number (N) of branches generated from a node is predetermined.