Full Opportunistic Backward Chaining Rulebased Systems

Greetings:

In this blog I will try to dispel the myth you can do Full Opportunistic Backward Chaining (FOBC) with a Forward Chaining (FC) rulebased system without making significant changes to the FC system. Actually, you can do backward chaining with a forward chaining system - BUT it would take a drastic re-write of all of the FC logic to achieve this and even then probably it would not work properly. So, what do you call it when you want to do backward chaining (BC) with a FC engine? Most of those in this field call it Goal-Driven FC - a misnomer if ever there was one. Which is another good reason to drop the explanation of a Backward Chaining system as "goal-driven" and the Forward Chaining system as "data-driven." A BC engine is or can be just as data-driven as a FC engine.

Before discussing chaining, we have to discuss Conflict Resolution - CR. All forward-chaining rulebased systems have some kind of method that will determine which rule to fire if there are more than one rule wherein all of the condition elements are true. This CR varies from vendor to vendor but, for the most part, they all seem to have recency (whether MEA or LEX or something else) as the first or second element in the CR algorithm. Usually this means for any given set of rules, they are resolved in the following order:

1. Refraction
2. Priority
3. Recency
4. Specificity
5. Arbitrary

OPSJ, a Java version of other systems developed by PST (Dr. Forgy) uses a slightly different variation on this where recency takes a higher order than

1. Refraction
2. Rule Class
3. Recency
4. Priority
5. Specificity
6. Arbitrary

At one time, most vendors posted (documented) their CR Strategy but not many do any more. In Jess and CLIPS you can (or used to be able to) set whatever CRS you wanted - usually depth was sufficient for most applications.

First, for the uninitiated, let's discuss a Forward Chaining (FC) engine. In the normal FC engine all of the data are loaded into objects (either embedded or external to the engine itself) and the rules are instantiated, initialized, started, whatever you want to call it. The rules will interact with the data in a non-monotonic manner until there are no more rules left to "fire" - meaning, to execute the "then" part of the "IF - THEN" rule. This is normal FC and what has come to be called "data-driven" rulebase, which is a misnomer because all rulebased systems use data to drive the rules one way or the other.

Now, what if we use a Goal-Driven approach with a FC? In that case (what is normally done today) the first condition element (CE) of a rule would be something like "if the goal.name == (goalName) " and, due the the recency factor or the CR discussed above and elsewhere, then rules would be "clustered" into those that have the same goal name when a new goal is asserted by any rule. The "goalName" could be a String, Integer, whatever you like. This is NOT backward chaining - this is simply clumping rules together much in the same manner that you might run a sub-routine in C/C++ program. It is the same effect as using a "focus" command in CLIPS or Jess. If this were C++ or Java it would be leaving the main chain of thought to run a sub-routine that might or might not return some value but would operate on whatever objects it needed. Nothing fancy here; Goal-Driven is nothing more than regular old rulebase logic with a first CE that would follow the goal.

Now, on to true Full Opportunistic Backward Chaining: The first thing is that the objects themselves must support this by being able to report to a calling routine whether the value of the slots (attributes) are known, unknown, not known, true / false / value. If a slot is known, then the object returns the value of that slot. But now we have two more wrinkles in the system in that of "not-known" - meaning that we do not know the value and we have not tried to find the value - and "unknown" - meaning that we have tried to find the value and we could not find the value. (Sometimes these are reversed in meaning but, regardless, you should get the idea.) I have always used the rule, "unknown and unknowable" to mean that we cannot find the value. If it were the other kind of state system, then I would use "not-known and never-knowable."

Here is where the wicket gets a bit sticky: If the value is not-known, then there must be some mechanism that will allow the rulebase to try and find the value. This is normally done via question handlers that will either ask the user to enter a value or go back to the database for an answer. If the answer can not be found, then the status of the slot (and the object) is changed to unknown. If this is an AND, NAND, XOR, NXOR gate, it forces the whole object to become unknown. If the object is an OR or NOR gate then other slots have to be checked until all return unknown and then the entire object is unknown.

The bottom line here is that the engine itself must generate the goals to find the value (and state) of the slots, not the programmer. This CAN be done with a forward chaining engine IF and ONLY IF the engine is programmed to do this. Haley (at one time) said that the Haley Expert Rules engine did this for you and OPSJ at one time did this for you. I'm not sure that either does it any longer since it does tend so slow things down if you don't need this.

Why would you need FOBC? Mostly for problems involving diagnostics (medical, instrumentation, processing plants, etc.) or configuration (manufacturing, computers, etc.) where you need to find all of the possibilities for your system. As you can see, this gets to be quite complex with many objects but if answer can be found with just a few backward chains, then the result would be much faster than using a FC rulebase or a "Goal-Oriented" FC rulebase.

SDG
jco