System for solving diagnosis and hitting set problems

• US 20060195302A1
• Filed: 02/13/2006
• Published: 08/31/2006
• Est. Priority Date: 02/11/2005
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Fijany, Amir, Vatan, Farrokh
• Granted Patent: US 7,249,003 B2
• Time in Patent Office: Days
• US Class Current: 702/196
• CPC Class Codes: G05B 23/0248 Causal models, e.g. fault tree; digraphs; qualitative physics
• CPC Class Codes: G06F 11/0706 the processing taking place on a specific hardware platform or in a specific software environment
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36

Abstract

The diagnosis problem arises when a system'"'"'s actual behavior contradicts the expected behavior, thereby exhibiting symptoms (a collection of conflict sets). System diagnosis is then the task of identifying faulty components that are responsible for anomalous behavior. To solve the diagnosis problem, the present invention describes a method for finding the minimal set of faulty components (minimal diagnosis set) that explain the conflict sets. The method includes acts of creating a matrix of the collection of conflict sets, and then creating nodes from the matrix such that each node is a node in a search tree. A determination is made as to whether each node is a leaf node or has any children nodes. If any given node has children nodes, then the node is split until all nodes are leaf nodes. Information gathered from the leaf nodes is used to determine the minimal diagnosis set.

Claims

1. A method for calculating a minimal Hitting Set from a collection of sets, comprising using a computer system to analyze a system having a collection of sets to derive the minimal Hitting Set from the collection of sets, the computer system being configured to perform acts of:

receiving information regarding the collection of sets from the system;

creating an incidence matrix of the collection of sets;

creating nodes from the incidence matrix such that each node is a node in a search tree and has a label that includes a sub-matrix of the incidence matrix, and two disjoint subsets of the columns of the incidence matrix;

calculating an upper bound and calculating a lower bound for each label, where the upper bound and lower bound define a range of solutions for the minimal Hitting Set; and

determining whether each label has any child nodes or is a leaf node without any child nodes;

if the label does not have any child nodes, then stop and designate the label as a leaf node;

if the label does have a child node, splitting the label to create two new labels;

repeating acts of calculating and determining until all labels have been designated as leaf nodes, with information gathered from leaf nodes determining a solution of the Hitting Set, thereby allowing a user to identify the Hitting Set.

2. A method for calculating a minimal Hitting Set as set forth in claim 1, wherein in the act of calculating the minimal Hitting Set, the minimal Hitting Set is a minimal diagnosis set and the collection of sets is a collection of conflict sets, such that the method for calculating a minimal Hitting Set calculates a solution for a diagnosis problem.

3. A method for calculating a minimal Hitting Set as set forth in claim 2, wherein in the act of creating an incidence matrix, the incidence matrix is created as a binary matrix denoted as m×

n binary matrix A having columns and rows, where the columns of matrix A are labeled by numbers 1, 2, . . . , n, and where any subset of these columns are denoted as a subset of {1, 2, . . . , n}.

4. A method for calculating a minimal Hitting Set as set forth in claim 3, wherein in the act of creating nodes, each node has a label (λ

) in a form of λ

=(M, T_in, T_out), where M is a sub-matrix of matrix A, and where T_in and T_out are disjoint subsets of the columns of matrix A, where T_in denotes a set of columns of matrix A considered as part of the minimal diagnosis set, and where T_out denotes a set of columns of matrix A that are considered not as part of the minimal diagnosis set.

5. A method for calculating a minimal Hitting Set as set forth in claim 4, wherein the act of calculating an upper bound further comprises acts of calculating a value for the upper bound of λ

=(M, T_in, T_out) and a calculating an upper bound set, by performing the following acts;

initializing the value of the upper bound as U=size of T_in and initializing the upper bound set as the set T_in, where the size of T_in is the number of elements in T_in;

choosing a column a₁ of M with a maximum weight, where the column with the maximum weight is the column of M with the largest number of 1'"'"'s;

increasing the value of U by 1 and adding the column a₁ to the upper bound set;

constructing the matrix M₁ from M by deleting the column a₁ and all rows of M that correspond with non-zero components of the column a₁, where if the matrix M₁ is empty then the current value of U is the upper bound and a solution for the Hitting Set is the upper bound set;

otherwise

repeating the acts of choosing through repeating on the matrix M₁.

6. A method for calculating a minimal Hitting Set as set forth in claim 5, wherein in the act of calculating a lower bound, a value for the lower bound of λ

=(M, T_in, T_out) is equal to the size of T_in plus k/L, where k is the number of rows of the matrix M and L is the maximum weight of the columns of M.

7. A method for calculating a minimal Hitting Set as set forth in claim 6, wherein in the act of determining whether each label has any child nodes or is a leaf node without any child nodes, a label is determined to be a leaf node if any of the following are true:

if T_in∪

T_out={1, 2, . . . , n}, where ∪

denotes the union of two sets;

if the value for the lower bound of λ

≧

the current value for the upper bound;

if the columns of T_in form a solution such that if the columns in T_in are added together to form a resulting vector, then the resulting vector has no zero component;

or

if M contains an all-zero row.

8. A method for calculating a minimal Hitting Set as set forth in claim 7, wherein the act of splitting the label to create two new labels further comprises an act of splitting label λ

=(M, T_in, T_out) into label λ

₀ and label λ

₁;

where label λ

₀ is defined as;

λ

₀=(Remove_—

0[M,j],T_in,T_out∪

{{umlaut over (j)}}),

where j denotes a column of M with a maximum weight and {umlaut over (j)} is the corresponding column in the original matrix, and where Remove_—

0[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M; and

where label λ

₁ is defined as;

λ

₁=(Remove_—

1[M,j],T_in∪

{{umlaut over (j)}},T_out),

where j denotes a column of M with a maximum weight and j is the corresponding column in the original matrix, and Remove_—

1[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M and deleting all rows of M that correspond with non-zero components of that column.

9. A method for calculating a minimal Hitting Set as set forth in claim 8, wherein the act of splitting a label further comprises acts of:

on label λ

=(M, T_in, T_out), if the j^th column of the matrix M is an all-one column, then changing the label X to the label ({ }, T_in∪

{{umlaut over (j)}}, T_out), where ∪

denotes the union of two sets, { } is an empty matrix and j is a corresponding column in the original matrix;

on label λ

=(M, T_in, T_out), if the matrix M has a row of weight one, with 1 as its j^th component, then changing the label λ

to the label (Removed_—

1[M,j], T_in∪

{{umlaut over (j)}}, T_out) where ∪

denotes the union of two sets, {umlaut over (j)} is the corresponding column in the original matrix, and Remove_—

1[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M and deleting all rows of M that correspond with non-zero components of that column;

on label λ

=(M, T_in, T_out), if the matrix M has an all-one row, then deleting that row;

on label λ

=(M, T_in, T_out), if j^th column of the matrix M is an all-zero column, then changing the label λ

to the label (Remove_—

0[M,j], T_in, T_out∪

{{umlaut over (j)}}), where ∪

denotes the union of two sets, {umlaut over (j)} is the corresponding column in the original matrix, and Remove_—

0[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M;

on label λ

=(M, T_in, T_out), if the matrix M has two equal rows, then deleting one of them; and

repeating the acts of claim 9 until all of the acts of claim 9 are exhausted.

10. A method for calculating a minimal Hitting Set as set forth in claim 9, further comprising an act of applying a Branch-and-Bound technique to the incidence matrix A to find an optimal solution for the problem, comprising acts of:

initializing a label λ

₀ as λ

₀=Rules*[{A, { }, { }}], where Rules* denotes applying and repeating the acts of claim 9 until all of the acts of claim 9 are exhausted;

initializing a set of labels as {λ

₀};

initializing a value of the upper bound U as the upper bound of λ

₀;

initializing a solution set as the upper bound set of λ

₀;

choosing a label λ

from the set of labels;

deleting λ

from the set of labels;

computing U₁ as the upper bound of λ and

its corresponding upper bound set;

if U₁<

U, then changing the value of U to U₁ and the value of the solution set to the upper bound set;

if the label λ

is not a leaf, then splitting λ

to labels λ

₀ and λ

₁ and adding the new labels λ

₀ and λ

₁ to the set of labels;

if the set of labels is not empty, repeating the acts of choosing a label λ

through the act of repeating the acts;

if the set of labels is empty, then the outputting is the solution set and stopping.

11. A computer program product for calculating a minimal Hitting Set from a collection of sets, the computer program product comprising computer-readable instruction means stored on a computer-readable medium for causing a computer to:

receive information regarding the collection of sets from the system;

create an incidence matrix of the collection of sets;

create nodes from the incidence matrix such that each node is a node in a search tree and has a label that includes a sub-matrix of the incidence matrix, and two disjoint subsets of the columns of the incidence matrix;

calculate an upper bound and calculating a lower bound for each label, where the upper bound and lower bound define a range of solutions for the minimal Hitting Set; and

determine whether each label has any child nodes or is a leaf node without any child nodes;

if the label does not have any child nodes, then stop and designate the label as a leaf node;

if the label does have a child node, splitting the label to create two new labels;

repeat operations of calculating and determining until all labels have been designated as leaf nodes, with information gathered from leaf nodes determining a solution of the Hitting Set, thereby allowing a user to identify the Hitting Set.

12. A computer program product for calculating a minimal Hitting Set as set forth in claim 11, wherein when calculating the minimal Hitting Set, the minimal Hitting Set is a minimal diagnosis set and the collection of sets is a collection of conflict sets, such that the computer program product is configured to calculate a solution for a diagnosis problem.

13. A computer program product for calculating a minimal Hitting Set as set forth in claim 12, wherein when creating an incidence matrix, the incidence matrix is created as a binary matrix denoted as m×

n binary matrix A having columns and rows, where the columns of matrix A are labeled by numbers 1, 2, . . . , n, and where any subset of these columns are denoted as a subset of {1, 2, . . . , n}, and

wherein when creating nodes, each node has a label (λ

) in a form of λ

=(M, T_in, T_out), where M is a sub-matrix of matrix A, and where T_in and T_out are disjoint subsets of the columns of matrix A, where T_in denotes a set of columns of matrix A considered as part of the minimal diagnosis set, and where T_out denotes a set of columns of matrix A that are considered not as part of the minimal diagnosis set.

14. A computer program product for calculating a minimal Hitting Set as set forth in claim 14, wherein when calculating an upper bound, the computer program product is further configured to cause a computer to perform operations of calculating a value for the upper bound of λ

=(M, T_in, T_out) and a calculating an upper bound set, by performing the following operations;

initializing the value of the upper bound as U=size of T_in and initializing the upper bound set as the set T_in, where the size of T_in is the number of elements in T_in;

choosing a column a₁ of M with a maximum weight, where the column with the maximum weight is the column of M with the largest number of 1'"'"'s;

increasing the value of U by 1 and adding the column a₁ to the upper bound set;

constructing the matrix M₁ from M by deleting the column a₁ and all rows of M that correspond with non-zero components of the column a₁, where if the matrix M₁ is empty then the current value of U is the upper bound and a solution for the Hitting Set is the upper bound set;

otherwise

repeating the operations of choosing through repeating on the matrix M₁.

15. A computer program product for calculating a minimal Hitting Set as set forth in claim 15, wherein when calculating a lower bound, a value for the lower bound of λ

=(M, T_in, T_out) is equal to the size of T_in plus k/L, where k is the number of rows of the matrix M and L is the maximum weight of the columns of M.

16. A computer program product for calculating a minimal Hitting Set as set forth in claim 16, wherein when determining whether each label has any child nodes or is a leaf node without any child nodes, the computer program product is configured to cause a computer to determine a label to be a leaf node if any of the following are true:

if T_in∪

T_out={1, 2, . . . , n}, where ∪

denotes the union of two sets;

if the value for the lower bound of λ

≧

the current value for the upper bound;

if the columns of T_in form a solution such that if the columns in T_in are added together to form a resulting vector, then the resulting vector has no zero component;

or

if M contains an all-zero row.

17. A computer program product for calculating a minimal Hitting Set as set forth in claim 17, wherein when splitting the label to create two new labels, the computer program product is further configured to cause a computer to perform an operation of splitting label λ

=(M, T_in, T_out) into label λ

₀ and label λ

₁;

where label λ

₀ is defined as;

λ

₀=(Remove_—

0[M,j],T_in,T_out∪

{{umlaut over (j)}}),

where j denotes a column of M with a maximum weight and {umlaut over (j)} is the corresponding column in the original matrix, and where Remove_—

0[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M; and

where label λ

₁ is defined as;

λ

₁=(Remove_—

1[M,j],T_in∪

{{umlaut over (j)}},T_out),

where j denotes a column of M with a maximum weight and {umlaut over (j)} is the corresponding column in the original matrix, and Remove_—

1[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M and deleting all rows of M that correspond with non-zero components of that column.

19. A computer program product for calculating a minimal Hitting Set as set forth in claim 19, further comprising instruction means for causing a computer to perform an operation of applying a Branch-and-Bound technique to the incidence matrix A to find an optimal solution for the problem, comprising operations of:

initializing a label λ

₀ as λ

₀=Rules[{A, { }, { }}], where Rules* denotes applying and repeating the operations of claim 19 until all of the operations of claim 19 are exhausted;

initializing a set of labels as {λ

₀};

initializing a value of the upper bound U as the upper bound of λ

₀;

initializing a solution set as the upper bound set of λ

₀;

choosing a label λ

from the set of labels;

deleting λ

from the set of labels;

computing U₁ as the upper bound of λ and

its corresponding upper bound set;

if U₁<

U, then changing the value of U to U₁ and the value of the solution set to the upper bound set;

if the label λ

is not a leaf, then splitting λ

to labels λ

₀ and λ

₁ and adding the new labels λ

and λ

₁ to the set of labels;

if the set of labels is not empty, repeating the operations of choosing a label λ

through the operation of repeating the operations;

if the set of labels is empty, then the outputting is the solution set and stopping.

18. A computer program product for calculating a minimal Hitting Set as set forth in claim 18, wherein when splitting a label, the computer program product further comprises instruction means for causing a computer to perform operations of:

on label λ

=(M, T_in, T_out), if the j^th column of the matrix M is an all-one column, then changing the label λ

to the label ({ }, T_in∪

{{umlaut over (j)}}, T_out), where ∪

denotes the union of two sets, { } is an empty matrix and {umlaut over (j)} is a corresponding column in the original matrix;

on label λ

=(M, T_in, T_out), if the matrix M has a row of weight one, with 1 as its j^th component, then changing the label λ

to the label (Remove_—

1[M,j], T_in∪

{{umlaut over (j)}}, T_out) where ∪

denotes the union of two sets, {umlaut over (j)} is the corresponding column in the original matrix, and Remove_—

1[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M and deleting all rows of M that correspond with non-zero components of that column;

on label λ

=(M, T_in, T_out), if the matrix M has an all-one row, then deleting that row;

on label λ

=(M, T_in, T_out), if j^th column of the matrix M is an all-zero column, then changing the label λ

to the label (Remove_—

0[M,j], T_in, T_out∪

{{umlaut over (j)}}), where ∪

denotes the union of two sets, {umlaut over (j)} is the corresponding column in the original matrix, and Remove_—

0[M,j] denotes a sub-matrix of M obtained by deleting the j^th column of M;

on label λ

=(M, T_in, T_out), if the matrix M has two equal rows, then deleting one of them; and

repeating operations of claim 19 until all of the operations of claim 19 are exhausted.

20. A computer program system for calculating a minimal diagnosis set from a collection of conflict sets, the computer system being configured to perform operations of:

creating an incidence matrix of the collection of sets;

creating nodes from the incidence matrix such that each node is a node in a search tree and has a label that includes a sub-matrix of the incidence matrix, and two disjoint subsets of the columns of the incidence matrix;

calculating an upper bound and calculating a lower bound for each label, where the upper bound and lower bound define a range of solutions for the minimal Hitting Set; and

determining whether each label has any child nodes or is a leaf node without any child nodes;

if the label does not have any child nodes, then stop and designate the label as a leaf node;

if the label does have a child node, splitting the label to create two new labels;

repeating acts of calculating and determining until all labels have been designated as leaf nodes, with information gathered from leaf nodes determining a solution of the Hitting Set, thereby allowing a user to identify the Hitting Set.