Backward chaining with extended knowledge base network

• US 7,433,854 B2
• Filed: 07/21/2005
• Issued: 10/07/2008
• Est. Priority Date: 07/21/2005
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Zhang, Rui, Joseph, Sindhu
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US11/186,324
• Publication Number:
  US 20070094193A1
• Time in Patent Office: 1,174 Days
• Field of Search: 706/46, 706/45, 706/14, 705/9
• US Class Current: 706/46
• CPC Class Codes: G06N 5/042 Backward inferencing

Abstract

Mixed mode inferencing is provided by creating an extension to a RETE network to handle both forward and backward chaining efficiently. The extended RETE network is traversed from a root node through intermediate nodes to the rules of the network. The intermediate nodes contain objects that have values assigned by rules, and the intermediate nodes are linked to those rules appropriately. When using the network in a backward chaining context, rules linked to the intermediate node of interest are checked to see if they are active and the rule is solvable. If not, the related rules are checked. Because the system takes advantage of the previously formed RETE network, these checks can be done at the rule nodes without the need to retest each condition.

Claims

1. A computer system comprising:

a central processor for performing forward chaining and backward chaining;

a memory coupled to the central processor;

a knowledge base forward chaining network in the memory solves a goal by applying a set of known facts to a set of rules until the goal is solved;

an extension of the knowledge based network in the memory created from the knowledge base network; and

the extended network solves the goal by testing the rules that would solve the goal against the set of known facts in a backward chaining manner, wherein the memory comprises an agenda containing rules to be fired for the forward chaining network, and a temporary agenda which may be altered during backward chaining without modification of the agenda.

2. The system of claim 1 wherein the knowledge base network is a RETE network including at least one alpha node and at least one terminal node.

3. The system of claim 2 wherein the extended network includes at least one intermediate node connected to the at least one terminal node of the RETE network and a root node connected to each of the at least one intermediate nodes.

4. The system of claim 3 wherein testing the rules includes checking at least one direct rule to determine if the at least one direct rule is active.

5. The system of claim 3 wherein testing the rules includes checking at least one related rule to determine if the at least one related rule is active.

6. A computer implemented method for extending a knowledge base network comprising:

creating a forward chaining knowledge base network by linking a set of conditions to a set of rules in computer memory;

creating at least one intermediate node such that each intermediate node corresponds to an object having a value set by one of the rules in computer memory;

connecting each intermediate node to each rule that sets the intermediate node'"'"'s object value in computer memory;

creating a root node in computer memory; and

connecting each intermediate node to the root node such that the root node and intermediate node function as a backward chaining network.

7. The method of claim 6 further comprising:

receiving a goal; and

applying forward chaining inferencing with the knowledge base network.

8. The method of claim 7 wherein the knowledge base network is a RETE network including at least one alpha node and at least one terminal node.

9. The method of claim 8 wherein the knowledge base network includes a knowledge base containing at least one fact.

10. The method of claim 9 further comprising:

activating the at least one alpha node and the at least one terminal node based on the at least one fact before creating the at least one intermediate node.

11. The method of claim 10 further comprising:

receiving a goal;

breaking the goal into at least one simple goals;

traversing the extended network from the root node to one of the at least one intermediate nodes based on the at least one simple goals;

determining if the rules connected to the at least one intermediate nodes are active; and

firing the active rules.

12. The method of claim 11 further comprising:

determining if any rule is active that affects the rules connected to the at least one intermediate nodes;

firing the active rules.

13. A computer implemented method comprising:

creating an extension of a forward chaining knowledge base network in computer memory solves a goal in a backward chaining manner by applying a set of known facts to a set of rules until the goal is solved, such that the extended network is solves the goal by testing the rules that would solve the goal against the set of known facts such that a working memory for the forward chaining knowledge base network is not disturbed during backward chaining.

14. The method of claim 13 wherein the knowledge base network is a RETE network.

15. A computer readable medium having a data structure stored thereon for use by a computer for implementing a knowledge base network, the data structure comprising:

a forward chaining RETE knowledge base network having multiple nodes, terminal nodes; and

an extension of the knowledge base network having multiple intermediate nodes coupled to terminal nodes of the knowledge base network, and having a dummy root node connected to each of the intermediate nodes, wherein the intermediate nodes have object values defined by rules in corresponding terminal nodes, and wherein the dummy root node accepts a goal, and initiates backward chaining utilizing the intermediate nodes.

16. A system comprising:

processing unit;

I/O devices coupled to the processing unit; and

a memory comprising;

a first knowledge base network for forward chaining inferencing; and

an extension of the first knowledge base network for backward chaining inferencing.

17. The system of claim 16 wherein the extended knowledge base network is a clone of the knowledge base network, and further comprising intermediate nodes containing values defined by rules in terminal nodes of the knowledge base network and a root node.

18. The system of claim 16 wherein the memory further comprises a working memory for the knowledge base network, and a temporary working memory for the knowledge base network.

19. The system of claim 16 wherein the memory further comprises an agenda for the knowledge base network and a temporary agenda for the extended knowledge base network.

20. The system of claim 16 wherein the first and second knowledge base network comprises a RETE network.

21. The system of claim 20 wherein the RETE network is stored in a tree.

22. The system of claim 21 wherein the tree comprises alpha nodes, each storing a condition, beta nodes, each storing multiple conditions, and terminal nodes specifying rules and actions.

23. The system of claim 22 wherein the extended RETE network tree further comprises a dummy root node, and intermediate nodes coupled to the terminal nodes and to the dummy root node.

24. The system of claim 16 wherein the first and second knowledge bases share memory.

25. A computer-controlled system for reasoning a discrimination-oriented knowledge base having objects and rules, the system comprising:

means for extending the knowledge base network to provide an augmented knowledge base network;

means for storing at least one fact to a working memory (WM) to indicate a current status of the fact in the working memory (WM);

means for distributing the current status of the WM across plurality of intermediate nodes of the extended knowledge base network; and

means for querying the extended knowledge base network wherein said querying is adapted for backward inferencing about the object with respect to a predetermined goal.

26. The system of claim 25, wherein said querying is further adapted for forward inferencing based on working memory changes consequent to predetermined priorities of rule firing.

27. The system of claim 25, wherein extending the knowledge base network further comprises providing at least one root memory node of the knowledge base network wherein each of the root memory node comprises the rule having an original condition and an action being executed on satisfaction of the condition isolating the action from the original condition in each of the root node to provide a plurality of simple condition corresponding to each rule storing each of the simple condition in a plurality of intermediate memory nodes to establish hierarchy of the extended knowledge base network.

28. The system of claim 25 wherein a fact comprises a true statement.

29. The system of claim 25 wherein a status of the fact comprises an object value.

30. The system of claim 25 wherein working memory is protected during backward inferencing.