Forward and Backward Chaining: Part 1

By Charles Forgy, PhD

 

Since this is the first of these columns, I decided to start with the most fundamental issue in rules: The difference between forward and backward chaining. In the rules literature, there are many articles that discuss the difference between forward and backward chaining. Some of these articles tell only a part of the story, and as a result, while they may be technically correct, they can be misleading. I hope to give a more complete explanation. This is a two-part column. This months part gives a detailed description of forward and backward chaining. Next months part will explore why forward and backward chaining are more alike than it may appear at first.

An Example

Before describing the two kinds of chaining, lets define a few simple rules that we can use to show what the two systems would do. The following rules might be found in an order processing system. The rules operate on the following variables:

  • last-years-orders: The total amount spent by the customer in the last twelve months.
  • current-order: The dollar amount of the current order.
  • discount-level: An indication of how good a customer this one is; the possible values are Platinum, Gold, Silver, and Default.
  • eligible-for-discount: A logical variable; it is true if the current-order is large enough to be discounted.
  • discount-amount: How much to discount the current order.
The rules are:
    R1: If last-years-orders are >= $10,000
    Then discount-level is Platinum.

    R2: If last-years-orders are < $10,000
    And last-years-orders are >= $5,000
    Then discount-level is Gold.

    R3: If last-years-orders are < $5,000
    And last-years-orders are >= $2,000
    Then discount-level is Silver.

    R4: If last-years-orders are < $2,000
    Then discount-level is Default.

    R5: If current-order is >= $100
    Then eligible-for-discount is true.

    R6: If current-order is < $100
    Then eligible-for-discount is false.

    R7: If discount-level is Platinum
    And eligible-for-discount is true
    Then discount-amount is 10%.

    R8: If discount-level is Gold
    And eligible-for-discount is true
    Then discount-amount is 7%.

    R9: If discount-level is Silver
    And eligible-for-discount is true
    Then discount-amount is 5%.

    R10: If discount-level is Default
    Then discount-amount is 0%.

    R11: If eligible-for-discount is false
    Then discount-amount is 0%.

Forward Chaining
A forward-chaining rule based system contains two basic components:
    1. A collection of rules.
    2. A collection of facts or assumptions that the rules operate on. (This is sometimes called the rules Working Memory.)
The standard definition of a forward-chaining system is that the system operates by repeating the following sequence of operations:
    1. Examine the rules to find one whose If part is satisfied by the current contents of Working memory.
    2. Fire the rule by adding to Working Memory the facts that are specified in the rules Then part. (The Then part may perform other actions as well, but we can ignore that for now.)
This control cycle continues until no rules have satisfied If parts.

For an example of how this works, suppose we were executing the rules above, and suppose the system starts with the two following facts in Working Memory:
    last-years-orders = $6300
    current-order = $260
With those facts, two rules, R2 and R5 can fire. If R2 fires first, it will add the fact
    discount-level = Gold
Then rule R5 will fire and add the fact
    eligible-for-discount = true
After these two new facts have been added, rule R8 will be satisfied. It will fire and add the fact
    discount-level = 7%
At this point, no other rules will have satisfied If parts, so execution will terminate.


Backward Chaining
A backward-chaining rule based system contains three basic components:
  • A collection of rules.
  • A collection of facts or assumptions for the rules to operate on. (The Working Memory.)
  • A stack of goals, where a goal is simply a statement of something that the rules need to determine.
The control flow of a backward-chaining system is more complex than that of a forward-chaining system. Backward-chaining systems try to satisfy the goals in the goal stack. They do this by finding rules that can conclude the information needed by the goal, and trying to make the If parts of those rules satisfied. In more detail, the standard backward-chaining control cycle is:
    1. Check the conclusions of the rules to find all rules that can satisfy the top goal on the stack.

    2. Process these rules one at a time:

      a. Evaluate the conditions in the rules If part one at a time:

        i. If the condition is currently unknown (that is, if there is not enough information currently known to determine whether the condition is satisfied) push a goal to make that condition known, and recursively invoke the system.

        ii. If the condition is known to be unsatisfied, continue with the loop at Step 2.

        iii. If it was not possible to determine whether the condition was satisfied, continue with the loop at Step 2.

      b.
      If all the conditions in the selected rule are satisfied, add to Working Memory the facts specified in the Then part of the rule, pop the goal off the stack, and return from this invocation of the system.
The system terminates with success when the goal stack is empty. It terminates with failure if the system runs out of rules to try in Step 2.

Using our same example, we will again suppose the system starts with the two following facts:
    last-years-orders = $6300

    current-order = $260
In a backward-chaining system, we also need an initial goal. Let us assume the stack contains one goal:
    G1: Determine the value of discount-amount
When the system begins evaluating goal G1, it will find that R7, R8, R9, R10, and R11 might satisfy this goal. If it starts with R7, it will determine that to satisfy R7s If part, it need the value of discount-level, so it will assert the goal
    G2: Determine the value of discount-level
It will determine that rules R1, R2, R3, and R4 could satisfy this goal. If it tries R1 first, it will determine that it has all the information that it needs (since it already has the value of last-years-orders), but that R1s If part is not satisfied. If it tries R2 next, it will determine that R2s If part is satisfied, and conclude
    discount-level = Gold
When it adds this fact to Working Memory, it will pop goal G2 from the stack, and return to G1 and R7 (where it was when it pushed G2). It will determine that R7s If part cannot be satisfied. If it selects R8 next, it will determine that the first condition in R8 is satisfied, but that it does not have the necessary information for the second condition. It will push the goal
    G3: Determine the value of eligible-for-discount
It will find that rules R5 and R6 can determine this value. If it tries R5 first, it will find that R5s single condition is satisfied (because last-years-orders are $6300). It will conclude
    eligible-for-discount = true
It will pop G3, and return to G1 and R8. It will determine that both of R8s conditions are satisfied. It will conclude
    discount-amount = 7%
It will pop goal G1, and terminate with success.

The backward-chaining system, then, concludes the same value for discount-amount as the forward-chaining system, though it follows a completely different path to the conclusion.

Conclusion
The standard brief explanation of the difference between forward and backward chaining usually focuses on two points:
  • Forward-chaining systems simply 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.
  • 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.

This is correct as far as it goes, but it does not give an accurate picture of how rules are used in practice. Next months column will attempt to show how rules are actually used. It will also discuss the RulesPower systems use of forward and backward chaining for business process automation.

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.