Graph matching system for comparing and merging fault models

• US 8,645,019 B2
• Filed: 12/09/2010
• Issued: 02/04/2014
• Est. Priority Date: 12/09/2010
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Singh, Satnam, Holland, Steven W., Bandyopadhyay, Pulak
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): PAIGE, TYLER D
• Application Number:
  US12/964,230
• Publication Number:
  US 20120151290A1
• Time in Patent Office: 1,153 Days
• Field of Search: 704/26, 701/29.9, 701/30.1, 701/30.2, 701/31.6, 701/31.7, 703/2, 703/16, 703/20, 703/27, 703/46
• US Class Current: 701/30.2
• CPC Class Codes: G05B 23/0278 Qualitative, e.g. if-then rules; Fuzzy logic; Lookup tables; Symptomatic search; FMEA

Abstract

A method and system for comparing and merging fault models which are derived from different data sources. Two or more fault models are first represented as bipartite weighted graphs, which define correlations between failure modes and symptoms. The nodes of the graphs are compared to find failure modes and symptoms which are the same even though the specific terminology may be different. A graph matching method is then used to compare the graphs and determine which failure mode and symptom correlations are common between them. Finally, smoothing techniques and domain expert knowledge are used to merge and update the fault models, producing an integrated fault model which can be used by onboard vehicle systems, service facilities, and others.

Claims

1. A method for comparing and merging fault models, said method comprising:

providing a first fault model and a second fault model, where the first and second fault models are derived from different data sources and describe failure modes and symptoms of a hardware or software system;

representing the first fault model as a first bipartite weighted graph, and the second fault model as a second bipartite weighted graph;

matching graph nodes between the bipartite weighted graphs, using a microprocessor, to identify common symptoms and failure modes;

employing a graph matching technique to compare the bipartite weighted graphs and the fault models, and produce a common sub-graph and an uncommon section;

applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section to merge and update the fault models into an integrated fault model; and

using the integrated fault model in connection with the hardware or software system.

2. The method of claim 1 wherein providing a first fault model and a second fault model includes providing fault models of types including an engineering data fault model, a service document fault model, a text verbatim fault model, and a warranty data fault model.

3. The method of claim 1 wherein representing the first fault model as a first bipartite weighted graph, and the second fault model as a second bipartite weighted graph includes creating a node for each of the failure modes and each of the symptoms, and connecting the nodes with arrows representing causality weights.

4. The method of claim 1 wherein matching graph nodes between the bipartite weighted graphs includes comparing each of the failure modes of the first fault model with each of the failure modes of the second fault model, and each of the symptoms of the first fault model with each of the symptoms of the second fault model to determine which of the failure modes and symptoms are the same.

5. The method of claim 1 wherein matching graph nodes between the bipartite weighted graphs includes removing superfluous words, resolving synonyms, acronyms, and abbreviations, applying text similarity measures to provide a text similarity score, and using the text similarity score to determine which of the failure modes and symptoms are the same.

6. The method of claim 1 wherein employing a graph matching technique to compare the bipartite weighted graphs and the fault models includes selecting for inclusion in the common sub-graph only correlations which have a non-zero value in both the first bipartite weighted graph and the second bipartite weighted graph, and placing in the uncommon section any correlations which have a non-zero value in only one of the first bipartite weighted graph or the second bipartite weighted graph.

7. The method of claim 1 wherein applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section includes using Laplacian or Bayesian smoothing techniques.

8. The method of claim 1 wherein applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section includes reviewing by a subject matter expert to determine how to incorporate content from the uncommon section into the integrated fault model.

9. The method of claim 1 wherein the hardware or software system is a vehicle or a vehicle sub-system.

10. The method of claim 9 wherein using the integrated fault model in connection with the hardware or software system includes using the integrated fault model in a processor onboard the vehicle, using the integrated fault model in a diagnostic tool at a service facility, or using the integrated fault model by vehicle development personnel to improve service procedures or design new products.

11. A method for comparing and merging fault models, said method comprising:

providing a first fault model and a second fault model, where the first and second fault models are derived from different data sources and describe failure modes and symptoms of a vehicle or a vehicle sub-system, and the fault models are of types including an engineering data fault model, a service document fault model, a text verbatim fault model, and a warranty data fault model;

representing the first fault model as a first bipartite weighted graph, and the second fault model as a second bipartite weighted graph;

matching graph nodes between the bipartite weighted graphs, using a microprocessor, to identify common symptoms and failure modes;

employing a graph matching technique to compare the bipartite weighted graphs and the fault models, and produce a common sub-graph and an uncommon section;

applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section to merge and update the fault models into an integrated fault model; and

using the integrated fault model in connection with the vehicle or the vehicle sub-system.

12. The method of claim 11 wherein representing the first fault model as a first bipartite weighted graph, and the second fault model as a second bipartite weighted graph includes creating a node for each of the failure modes and each of the symptoms, and connecting the nodes with arrows representing causality weights.

13. The method of claim 11 wherein matching graph nodes between the bipartite weighted graphs includes removing superfluous words, resolving synonyms, acronyms, and abbreviations, applying text similarity measures to provide a text similarity score, and using the text similarity score to determine which of the failure modes and symptoms are the same.

14. The method of claim 11 wherein applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section includes using Laplacian or Bayesian smoothing techniques, and reviewing by a subject matter expert to determine how to incorporate content from the uncommon section into the integrated fault model.

15. A system for comparing and merging fault models, said system comprising:

means for providing a first fault model and a second fault model, where the first and second fault models are derived from different data sources and describe failure modes and symptoms of a vehicle or a vehicle sub-system;

means for representing the first fault model as a first bipartite weighted graph, and the second fault model as a second bipartite weighted graph;

means for matching graph nodes between the bipartite weighted graphs to identify common symptoms and failure modes;

means for employing a graph matching technique to compare the bipartite weighted graphs and the fault models, and produce a common sub-graph and an uncommon section;

means for applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section, to merge and update the fault models into an integrated fault model; and

means for using the integrated fault model in connection with the vehicle or the vehicle sub-system.

16. The system of claim 15 wherein the means for matching graph nodes between the bipartite weighted graphs compares each of the failure modes of the first fault model with each of the failure modes of the second fault model, and each of the symptoms of the first fault model with each of the symptoms of the second fault model, to determine which of the failure modes and symptoms are the same.

17. The system of claim 16 wherein the means for matching graph nodes between the bipartite weighted graphs removes superfluous words, resolves synonyms, acronyms, and abbreviations, applies text similarity measures to provide a text similarity score, and uses the text similarity score to determine which of the failure modes and symptoms are the same.

18. The system of claim 15 wherein the means for employing a graph matching technique to compare the bipartite weighted graphs and the fault models selects for inclusion in the common sub-graph only correlations which have a non-zero value in both the first bipartite weighted graph and the second bipartite weighted graph, and places in the uncommon section any correlations which have a non-zero value in only one of the first bipartite weighted graph or the second bipartite weighted graph.

19. The system of claim 15 wherein the means for applying parameter smoothing techniques and domain knowledge to the common sub-graph and the uncommon section uses Laplacian or Bayesian smoothing techniques and review by a subject matter expert to determine how to incorporate content from the uncommon section into the integrated fault model.

20. The system of claim 15 wherein the means for using the integrated fault model in connection with the vehicle or the vehicle sub-system uses the integrated fault model in a processor onboard the vehicle, uses the integrated fault model in a diagnostic tool at a service facility, or uses the integrated fault model by vehicle development personnel to improve service procedures or design new products.