Forward and Backward Chaining: Part 2

By Charles Forgy, PhD

 

In the last column we looked at the basic difference between forward and backward chaining rule systems. In this column we will continue to look at chaining. First we will look at forward chaining in more detail, and we will see that forward and backward chaining rules are not as different as they may first appear. Then we will look at how forward and backward chaining are integrated in modern systems.

As we discussed, the difference between forward and backward chaining boils down to just two points:

  1. Forward-chaining systems fire rules whenever the rules If parts are satisfied. Backward-chaining systems attempt to fire rules only when those rules can potentially satisfy a goal.
  2. Backward-chaining systems automatically create new subgoals when more information is needed to determine whether a given rule is satisfied. Forward-chaining systems do not automatically create subgoals.
Some discussions of forward chaining systems go beyond these two points to give a very misleading characterization of forward chaining systems. The usual statement is something like, Forward chaining systems start with the facts about the situation and proceed to compute every conclusion that can be made based on those facts. I have to say I have never seen a system of any size that operates that way. Just as backward chaining systems do, forward chaining systems use goals to control which rules may fire at a given time. The only difference is that the goals are created explicitly by the rules in a forward chaining system.

Working with goals in a forward chaining system is actually quite simple. As was explained in the last column, forward chaining rules operate on an in-core data base of objects usually called the systems working memory. This working memory can contain not only facts about the problem situation, but goals as well. For instance, the data base can contain not only facts such as
Chest C1 is locked.
But also goals such as
Goal: Unlock Chest C1.
The If parts of the rules in a forward chaining system generally specify both a goal that they can satisfy (or help to satisfy) and the facts about the problem that the rule needs. For instance, there might be a rule in a system that says

In this article we are going to use a very abstract representation for working memory objects as well as the rules that operate on them. In later articles we can get objects and rules in actual systems look like.
    IF
      The current goal is Open Chest x, and Chest x is locked
    THEN
      Create Goal: Unlock Chest x.

In general, most of the rules in a system that is organized this way will take one of two formats. The first is rules to create subgoals, like the one we just saw:

    IF
      The current goal is Goal1, and
      Fact1, and
      Fact2, and
      . . .
      FactN
    THEN
      Create the goal Goal2.
The second format is for the rules that really do something (i.e., rules that dont just create goals for other rules):

    IF
      The current goal is Goal3, and
      Fact1, and
      Fact2, and
      . . .
      FactN
    THEN
      Change fact Factw, and
      Change fact Factx, and
      . . .
      Delete goal Goal3.

We might call the second form of rules, action rules and the first form of rules subgoaling rules. In short, action rules make the changes to the state of the world that are required to solve the problem, while subgoaling rules insure that all the facts required by the action rules are available.

You might ask why you would want to use a forward chaining system if you have to write rules to manage subgoals. After all, backward chaining systems automatically manage the subgoals. There answer is very simple: Backward chaining systems are more limited than forward chaining systems. There are many kinds of tasks that can be handled easily with a forward chaining system that are either difficult or impossible with a backward chaining system. Backward chaining systems are good for diagnostic and classification tasks, but they are not good for planning, design, process monitoring, and quite a few other tasks. Forward chaining systems can handle all these tasks.

But the fact remains that when backward chaining is applicable, it is certainly easier to use. The ideal would be to use backward chaining where it could be used, and forward chaining elsewhere. For instance, a medical system might use backward chaining to diagnose an illness, and then use forward chaining to design a course of treatment. Modern rule based systems provide both forward and backward chaining capabilities in a single system. The RulesPower system, for instance, is primarily a forward chaining system, but it can invoke automatic backward chaining to create the preconditions needed by the forward chaining rules. That is, you can avoid writing manyperhaps allof the subgoaling rules needed by a strictly forward chaining system.

The way automatic backward chaining works is quite simple. Consider again the action rule from above:

    IF
      The current goal is Goal3, and
      Fact1, and
      Fact2, and
      . . .
      FactN
    THEN
      Change fact Factw, and
      Change fact Factx, and
      . . .
      Delete goal Goal3.

All the developer needs to do is to indicate which conditions in the rule should be handled by automatic back chaining. For example, in this rule, if all the facts are to be handled by back chaining, the developer might write something like

    IF
      The current goal is Goal3, and
      Can establish Fact1, and
      Can establish Fact2, and
      . . .
      Can establish FactN
    THEN
      Change fact Factw, and
      Change fact Factx, and
      . . .
      Delete goal Goal3.

When the rule interpRETEr processes this If part, if it finds that a certain fact is not available, it automatically creates a goal object and puts it into working memory. For instance, if Fact1 was available and Fact2 was not, the system would behave as if the following rule was in the system:

    IF
      The current goal is Goal3, and
      Fact1, and
      NOT Fact2, and
    THEN
      Create Goal: Achieve Fact2.

In short, the system behaves as if there were subgoaling rules for each of the facts. (Though the rules are not actually present in the system, which makes the system smaller and more efficient.)

In conclusion, forward and backward chaining systems both use subgoals to control the operation of a rule base. Pure forward chaining systems are more powerful than pure backward chaining systems, but pure forward chaining systems require the developer to write all the subgoaling rules. Modern forward chaining systems such as the RulesPower system integrate automatic backward chaining with forward chaining. These systems combine the best features of both forward and backward chaining.


I welcome your questions, comments and suggestions for future topics. Please email me at info@rulespower.com

 



Copyright © 2002-2005 by RulesPower, Inc. All rights reserved.