Conflict Resolution in Rules

Probably the initial work done in Conflict Resolution (CR) for rulebased Systems (RBS) was done by Charles Forgy and John McDermott and published in the collection of papers "Pattern-Directed Inference Systems", edited by D.A. Waterman and Frederick Hayes-Roth way back in 1978. (This was my "bible" in grad school.) Anyway, since that time, several other books have come out, the best of which IHMO is "Rule-based Programming with OPS5" by Thomas Cooper and Nancy Wogrin, published in 1988. Both are long since out of print but can still be found on the internet. Even Giarratano and Riley spend very little time with CR since it's considered by most to be something that we thought about a long time ago and should not need

The first one is a rather high-level book that is far more general than most of us would want to read. The second, however, is very down-to-earth and easily understood by most rulebase guys. In particular I would recommend chapter three where the difference between the LEX and the MEA strategies are explained. But, back to the original point, what exactly do we mean by CR and why do we need it? The first book explains, in excruciating detail WHY we need it; sensitivity of control and stability of rules. But HOW to accomplish this? Some RBS allow you to set your own strategy. Some have it pre-programmed in to the system. Some don't have it at all. But, for now, let's take the Cooper and Wogrin approach, explain it, and later we'll expand on it.

When the system is first initialized, along with setting up the Rete network, the system sets up an Agenda Table wherein the rules that the Left Hand Side (LHS) all evaluate to TRUE are kept and adjusted between cycles. These rules are "ordered" in the following manner:

Refraction (any rule already fired is not eligible to fire again)
Recency (based on the time stamp)
Specificity
Arbitrary

What they did not consider was either priority or ruleset membership. So, just for arguments sake, let's add those.

Refraction (any rule already fired is not eligible to fire again)
Priority
Recency (based on the time stamp)
Specificity
Ruleset
Arbitrary

The hardest of all to understand is the one on Specificity. For each of the following, a count of +1 is given to the rule based on the LHS for

An element Class name
A Predicate Operator with a constant (such a x <= 3)
A Predicate Operator with a "bound" variable
A disjunction such as << a b c d >>
Each predicate of disjunction within a conjunction

An example is that

{ <=> symbol << yes no maybe . >> }

counts as two in the specificity count. Normally, the CR doesn't get much beyond recency. So, why do we need CR? (I think that this is where we started...) Stability and Control. What I have discovered is that systems without a CR strategy do poorly in benchmark tests while those that at least have a depth strategy do much better. In the older systems you could set the strategy to see which one got the better response. AND it helped to see if you got a different answer using a different strategy. If you did, then that helped GREATLY when trouble shooting - you shouldn't get a different answer if the rules are constructed properly but, as Cooper and Wogrin point out, you surely can get a different answer.

SDG
Yaakov