Production rule filter mechanism and inference engine for expert systems

• US 5,642,471 A
• Filed: 05/06/1994
• Issued: 06/24/1997
• Est. Priority Date: 05/14/1993
• Status: Expired due to Fees

• Current Assignee: Alcatel NV (Nokia Corporation)
• Original Assignee: Alcatel NV (Nokia Corporation)
• Inventors: Paillet, Olivier
• Primary Examiner(s): Downs, Robert
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/239,386
• Time in Patent Office: 1,145 Days
• Field of Search: 395/51, 395/64, 395/60, 395/75, 364/513
• US Class Current: 706/47
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks

Abstract

A mechanism for filtering production rules which express conditions to be satisfied, identifies during successive inference cycles rules whose conditions are satisfied for deduced facts. The mechanism includes a sorting system for ordering the conditions of the rules according to a sorting criterion in order to verify the conditions of the rules on the basis of an order in which the conditions are to be applied. The sorting mechanism activates the system for sorting the conditions of the rules only if the number of facts satisfying a rule condition is multiplied or divided by a variable factor between the current inference cycle and the last preceding inference cycle during which the sorting system was activated for that rule.

Claims

1. An apparatus for filtering production rules, which express conditions to be satisfied, said apparatus being adapted to identify, during successive inference cycles, rule(s) whose conditions are satisfied for deduced facts, said apparatus comprising a sorting system for ordering the conditions of the rules in accordance with a sorting criterion, wherein said sorting system is activated to sort the conditions of the rules only if the number of facts which satisfy a rule condition is multiplied or divided by a variable factor between the current inference cycle and the last preceding inference cycle during which the sorting system was activated for this rule.

2. The apparatus according to claim 1 wherein said sorting system is adapted to memorize an ordered list of the other conditions of said rule.

3. The apparatus according to claim 1, wherein the criteria for sorting the conditions of a rule comprises:

a) a first condition of the rule is one which must be verified for a new deduced fact;

b) a next condition of the rule is selected from the remaining conditions of the rule, said next condition being the one which satisfies one of the following criteria in the following order of preference;

i) a condition that does not include any variable;

ii) a condition including at least one variable present in a condition already selected;

iii) a condition including at least one variable and for which the number of constrained facts is the smallest.

4. Expert system inference engine comprising a filtering apparatus for filtering production rules which express conditions to be satisfied, said filtering apparatus being adapted to identify, during successive inference cycles, rule(s) whose conditions are satisfied for deduced facts, and said filtering apparatus comprising a sorting system for ordering the conditions of the rules in accordance with a sorting criterion, wherein said sorting system is activated to sort the conditions of the rules only if the number of facts which satisfy a rule condition is multiplied or divided by a variable factor between the current inference cycle and the last preceding inference cycle during which the sorting system was activated for this rule.

5. An expert system inference engine according to claim 4, wherein said sorting system is adapted to memorize an ordered list of the other conditions of said rule.

6. An expert system inference engine according to claim 4, wherein the criteria for sorting the conditions of a rule comprises:

a) a first condition of the rule is one which must be verified for anew deduced fact;

b) a next condition of the rule is selected from the remaining conditions of the rule, said next condition being the one which satisfies one of the following criteria in the following order of preference;

i) a condition that does not include any variable;

ii) a condition including at least one variable present in a condition already selected;

iii) a condition including at least one variable and for which the number of constrained facts is the smallest.