Matching technique for context sensitive rule application

• US 5,317,677 A
• Filed: 04/16/1992
• Issued: 05/31/1994
• Est. Priority Date: 04/16/1992
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Keirsey, David M., Dolan, Charles P., Reiser, Kurt
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Shapiro, Stuart
• Application Number:
  US07/869,402
• Time in Patent Office: 775 Days
• Field of Search: 395/50, 395/51, 395/52, 395/60, 395/64, 395/68, 395/11
• US Class Current: 706/10
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

A knowledge-based system (10) which combines case-based reasoning, heuristic search and deductive rule application. The resulting inference engine is sensitive to the context of problem solving. The system (10) includes a heuristic searcher (22), a case memory (14), a rule memory (18), a rule applier (26) and a case matcher (24). The rule applier (26) uses stored rules to elaborate on new cases by deriving new features so that it will be closer to selected old cases. The case matcher (24) detects how close selected cases are to the new case and generates a score for the match. The heuristic searcher (22) maintains a plurality of elaborated cases and determines the goodness of each elaborated case, the goodness being a measure of the match between the elaborated case and the selected old case.

Claims

1. A knowledge-based system for solving a problem in a given domain, said knowledge-based system comprising:

case memory means for storing a set of exemplary cases from said domain, said case memory means containing a plurality of fields, each field containing data describing features of said exemplary cases;

rule memory means for storing a set of rules, each rule associated with one or more stored exemplary cases;

heuristic search means for receiving a new case comprising a plurality of fields, each field containing data describing features of said problem to be solved, said heuristic search means including means for controlling a search of said case memory means and rule memory means for cases and rules which relate to said new case, said means for controlling a search choosing selected exemplary cases in said case memory means for comparison with said new case;

case matcher means, coupled to said heuristic search means and to said case memory means for determining how close the selected exemplary cases are to the new case, and for determining which fields of said new case do not match with said stored exemplary cases; and

rule applier means for using said set of rules to elaborate the new case by deriving new features and creating an elaborated new case, so that the elaborated new case will be closer to one of the selected exemplary cases;

wherein said heuristic search means is coupled to said rule applier means, said heuristic search means maintaining a plurality of elaborated new cases and determining a goodness metric for each elaborated new case, wherein the goodness metric is measured by the match between the elaborated new case and said selected exemplary cases, wherein said heuristic search means includes a means coupled to said means for controlling a search for determining when an elaborated new case represents an acceptable solution to said problem based on said goodness metric.

2. The system of claim 1 wherein said case matcher means determines a partial case match by comparing how close two features are, one feature being from a stored exemplary case and one feature being from the new case.

3. The system of claim 2 wherein said case matcher means determines a score for the partial case match of the two features and any new token correspondences engendered by matching the two features.

4. The system of claim 1 wherein said heuristic search means comprises a beam search means for performing a beam search.

5. The system of claim 1 wherein said heuristic search means, contains at least three operators including 1) means for matching individual predicates contained in both an exemplary case and a new case, 2) means for invoking rules in said rule memory means to derive a feature that is present on a stored exemplary case but missing on a new case, and 3) means for moving to a new stored exemplary case.

6. The system of claim 1 wherein said rule applier means receives as input from said heuristic search means said new case, the name of a predicate to be derived along with the number of arguments, and a description of which rule sets to apply.

7. The system of claim 6 wherein said rule applier means also receives as input from said heuristic search means information describing the amount of computational effort to be spent.

8. The system of claim 6 wherein said rule applier means includes a stack-based backward chaining inference engine.

9. A method for solving problems which present a set of known and a set of unknown parameters, said method comprising the steps of:

receiving a set of known parameters of said problem;

storing a set of previous cases representing solutions from a domain related to said problem;

storing a set of rules which apply to said previous cases;

determining which of said stored previous cases most resembles said known parameters in said problem;

determining which rules of said stored set of rules apply to said set of stored previous cases;

elaborating said problem of known parameters by inserting values for said unknown parameters which will make said problem more like one of said cases in said set of stored previous cases, to create a plurality of elaborated cases;

performing a heuristic search on said elaborated cases to determine a goodness measure of said elaborated cases;

choosing a best elaborated case based on said heuristic search; and

determining when an elaborated case represents an acceptable solution to said problem based on said goodness measure.

10. The method of claim 9 wherein said step of performing a heuristic search further comprises the step of determining a partial match based on two features, one feature from a previous case and one feature from said problem.

11. The method of claim 10 wherein said step of performing a heuristic search further comprises the step of determining a score for said partial match of said two features and determining new token correspondences engendered by said partial match.

12. The system of claim 9 wherein said step of performing a heuristic search performs a search which is a beam search.

13. A knowledge-based system for solving a problem in a given domain, said knowledge-based system comprising:

case memory means for storing a set of exemplary cases from said domain, said case memory means containing a plurality of fields, each filed containing data describing features of said exemplary cases;

rule memory means for storing a set of rules, each rule associated with one or more stored exemplary cases;

heuristic search means for receiving a new case comprising a plurality of fields, each field containing data describing features of said problem to be solved, said heuristic search means including means for controlling a search of said case memory means and rule memory means for cases and rules which relate to said new case, said means for controlling a search choosing selected exemplary cases in said case memory means for comparison with said new case, said heuristic search means containing at least three operators including (1) means for matching individual predicates contained in both an exemplary case and a new case, (2) means for invoking rules in said rule memory means to derive a feature that is present on a stored exemplary case but missing on a new case and (3) means for moving to a new stored exemplary case;

case matcher means, coupled to said heuristic search means and to said case memory means for determining how close the selected exemplary cases are to the new case, and for determining which fields of said new case do not match with said stored exemplary cases, said case matcher means determining a partial case match based on two features, one feature from a stored exemplary case and one feature from said new case; and

rule applier means for using said set of rules to elaborate the new case by deriving new features of the new case and creating an elaborated new case so that the elaborated new case will be closer to one of the selected exemplary cases;

wherein said heuristic search means maintains a plurality of elaborated new cases, and determines a goodness metric for each elaborated new case, wherein the goodness metric is measured by the match between the elaborated new case and said selected exemplary cases,

wherein said heuristic search means includes a means coupled to said means for controlling a search for determining when an elaborated new case represents an acceptable solution to said problem based on said goodness metric.