Minimum cardinality candidate generation
AssigneePalo Alto Research Center Incorporated
InventorJohan de Kleer
Life of this patent
Estimating the term…
Abstract
This NGDE algorithm incorporates a minimum cardinality candidate diagnosis generator which exploits conflict set reduction rules to dramatically reduce the search space and thus reduce the computational resources required to find minimum cardinality diagnoses.
Claims17
A method for performing diagnoses in a modeled system, the method comprising:
- searching for output information from components of the modeled system;
- searching for conflicts among the output information of the modeled system being searched;
- discovering conflicts among the output information;
- forming a conflict set from the discovered conflicts;
- transforming the conflict set into a simplified conflict set;
- searching for a diagnosis of the modeled system using the simplified conflict set;
- and
- obtaining the diagnosis using the simplified conflict set, wherein the obtaining focuses on obtaining a minimum cardinality diagnosis.
The method according to claim wherein the searching for the minimum cardinality diagnosis includes (1) performing a connected component analysis to factor the conflicts and (2) reducing both the number of conflicts, their sizes and the involved variables, while preserving an ability to determine the minimum cardinality diagnoses.
Dependencies are inferred from the claim text.