Computer based inference engine device and method thereof for integrating backward chaining and forward chaining reasoning

• US 5,119,470 A
• Filed: 04/27/1990
• Issued: 06/02/1992
• Est. Priority Date: 04/27/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gallivan, Hugh W., Highland, Frederic D., Iwaskiw, Christine T., Tani, James D.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): DAVIS, GEORGE B
• Application Number:
  US07/515,720
• Time in Patent Office: 767 Days
• Field of Search: 395/64
• US Class Current: 706/48
• CPC Class Codes: G06N 5/042 Backward inferencing
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

An inference engine device adapted for use in a computer-controlled expert system, the computer-controlled expert system having a computer and a knowledge base of objects and rules, the objects having known values and unknown values, the rules having at least one test against an object or objects and configured in a Rete based network. The inference engine is comprised of a first module with a function of storing instructions for the computer; a second module, associated with the first module, that is comprised of a function for instructing the computer to perform forward reasoning with the objects having known values and another function for generating a conflict set; a third module, associated with the first module, that has a function of instructing the computer to perform backward reasoning about the objects having unknown values; and a fourth module, associated with the first module, that determines whether the first or second module is being executed by the computer.

Claims

1. An inference engine device adapted for use in a computer-controlled expert system, the computer-controlled expert system having a computer and a knowledge base of objects and rules, the objects having known values and unknown values, the rules having at least one test against an object or objects, which inference engine device comprising:

a) first means for storing instructions for the computer;

b) second means, associated with said first means, for instructing the computer to perform forward reasoning with the objects having known values using the rules configured in a Rete based network, said second means comprising means for generating a conflict set;

c) third means, associated with said first means, for instructing the computer to perform backward reasoning using the rules about the objects having unknown values; and

d) fourth means, associated with said first means, for controlling the execution of said second means and said third means.

2. The inference engine device of claim 1, wherein said fourth means further comprises means for initiating backward reasoning when no rules are present in the conflict set.

3. The inference engine device of claim 2, wherein said fourth means comprises means for initiating forward reasoning upon detection of a rule in the conflict set.

4. The inference engine device of claim 3, wherein said second means further comprises means for distributing the objects having known values to the Rete based network.

5. The inference engine device of claim 4, wherein said third means comprise a goal stack for storing a goal, said goal being at least one of the objects having unknown values.

6. The inference engine device of claim 5, wherein said objects having unknown values may be obtained by either an external source or by selecting a rule with an associated action that will provide a value for said goal and adding said selected rule to said goal stack.

7. The inference engine device of claim 6, wherein said third means further comprise means for selecting said selected rule from said goal stack and means for evaluating said selected rule.

8. The inference engine device of claim 7, wherein said evaluation means comprise means for examining each test of the rule and determining whether a referenced object in a premise is known.

9. The inference engine device of claim 8, wherein said evaluation means further comprises means for placing said referenced object on said goal stack if said premise is unknown.

10. The inference engine device of claim 9, wherein said third means further comprises means for selectively distributing said referenced object to the rule in the Rete based network.

11. The inference engine device of claim 9, wherein said third means further comprises means for distributing said referenced object to the Rete based network.

12. The inference engine device of claim 5 further comprising fifth means for retracting said goal and one of the rules associated with said goal from said goal stack.

13. The inference engine device of claim 12, wherein said fifth means comprises:

(1) means for detecting when a known object does not satisfy a rule; and

(2) means for deleting said known object and its associated rule from said goal stack and a goal pool.

14. A computer-controlled method for reasoning about a knowledge base of an expert system, the knowledge base having objects and rules therein, which method comprises the steps of:

(a) performing forward reasoning on the objects to generate a conflict set of rule instances using the rules configured in a Rete based network;

(b) continuing forward reasoning using the rules until no said rule instances exist in the conflict set; and

(c) performing backward chaining using the rules on the objects when no said rule instances exist in the conflict set.

15. The computer-controlled method of claim 14, wherein step (c) comprises the steps of:

(1) generating a set of desired object values (goals) and rules that have actions that provide the desired object values;

(2) selecting one of said rules and one of said desired object values from said set;

(3) updating said set in order to obtain a value for said selected desired object value; and

(4) selectively distributing a known object value to said rules for matching.

16. The computer-controlled method of claim 15, wherein step (a) comprises the steps of:

(1) detecting when said selectively distributed known object does not match its associated rule; and

(2) deleting the goal corresponding to said selectively distributed known object and its associated rule from said set.

17. A computer-controlled inference engine adapted for reasoning about a knowledge base of an expert system, the knowledge base having objects and rules therein, the rules having first condition tests and second condition tests, which computer-controlled inference engine comprises:

(a) first means for reasoning in a forward or backward chaining manner using the rules, wherein the rules are configured in a Rete based network;

(b) second means for reasoning in a forward chaining manner with one or more of the first condition tests of one of the rules; and

(c) third means for reasoning in a backward manner with one or more of the second condition tests of the same rule.

18. A computer-controlled inference engine adapted for reasoning about a knowledge base of an expert system, the knowledge base having objects and rules therein, the rules having at least one condition test, which computer-controlled inference engine comprises:

(a) first means for acquiring object values so that the expert system can reason in a forward chaining manner with all the rules, wherein the rules are configured in a Rete based network;

(b) second means for reasoning in a backward chaining manner with one or more of the rules to acquire object values; and

(c) third means for forward chaining reasoning with all the rules using said object values.