8 A Multitasking Application

8.4 The backward chainer

The backward chainer can be characterized as a goal processor. The top-level goal is the query pattern entered by the user, and the subgoals are the fact patterns found in rule premises. A chain of reasoning is created in which each node is a process concerned with achieving instances of a different goal. Sequential nodes in this chain represent successive refinement of subgoals, while branches represent alternative choice points for deriving different instances of a goal. The resulting chain, with all of its branches, is the decision tree for the top-level goal.

Each process can achieve its goal through the following methods:

When using a rule to deduce instances of the goal pattern, the application replaces this goal pattern with the premises of the matching rule. These premises become new subgoal patterns. Thus, the backward chainer repeatedly breaks up a larger goal into smaller subgoals until each goal is primitive enough to be directly looked up in the database.

The application stores the goal patterns on a stack called the goal stack. Initially, the only item on the goal stack is the top-level goal. When a rule is selected whose conclusion matches the top goal in the goal stack, the goal is popped off of the goal stack, and the premises of the rule are pushed onto the goal stack. The backward chainer process repeatedly tries to achieve all of the goals in the goal stack. If it can do so, the original goal is achieved; that is, a fact is deduced that matches the original query pattern.

Each pattern can match more than one fact, rule, or both. To handle this situation, the reasoning chain splits into parallel branches for pursuing alternative derivations. All branches in the decision tree represent disjunctive, or alternative, reasoning paths. A new process is created when the stack is modified to avoid conflicts over the use of only one stack by alternative reasoning processes. This technique results in a one-to-one correspondence between the goals and the reasoning processes.

Each node has its own goal stack to represent the set of goals whose collective achievement would imply achievement of the top-level goal. When a process encounters a pointer to a rule as the top item on its goal stack, all of the premises of that rule have been satisfied, and the rule is applied. The conclusions of the rule are asserted into the database by using the variable bindings in effect at that node.

When a node is created with an empty goal stack, all necessary subgoals have been achieved; thus, some instance of the user's original query pattern has been inferred. The node sends a success message up the tree to its parent. This message allows the user to specify how many instances of the pattern to deduce. When that number of success messages are received, the tree is killed.

The root node in the tree is initialized with the top-level goal on its goal stack. Since the root is the only reasoning process at this point, the BC scheduler runs it. The BC scheduler allows each level in the tree to finish processing before the next level is activated.

Once a variable receives a binding in one premise or conclusion of a rule, the binding is propagated throughout the rule. Thus, each occurrence of the variable in the rule is effectively replaced with the symbol to which it is bound. For example, the following rules are not the same:

R1: (IF (THE BROTHER OF CLYDE IS ?BRO)
        (THE COLOR OF ?BRO IS ?COLOR)
     THEN
        (A SELECTED COLOR IS ?COLOR))


R2: (IF (THE BROTHER OF CLYDE IS ?BRO)
        (THE COLOR OF ?WHO IS ?COLOR)
     THEN
        (A SELECTED COLOR IS ?COLOR))
If the fact(THE BROTHER OF CLYDE IS JOE) is stored in the database, the ruleR1 selects only the color ofJOE;R2 does not select the color of anyone.

The Advanced User's Guide - 9 SEP 1996

Generated with Harlequin WebMaker