conflict resolution

from Pete Carapetyan:

Conflict Resolution:
Each of the engines he compared uses an algorthim for rules conflict
resolution. All but JRules use MEA, and JRules uses LEX, which is
similar but not quite as efficient
MEA and LEX are very similar, and each does about 5 things to establish
which should fire first. Since MEA is both published and a long term
accepted standard, is there a reason for not going with the flow on
this, long term?

from Tom McGuire:

I was browsing through the archives and saw a post about Rule Priorities.
Bob had asked for a design or some rough ideas. This will be my quick stab
at it.

BACKGROUND
This topic is generally termed Conflict Resolution. Multiple Rules may be
able to fire based on the set facts entered into the Rule Engine. The Rule
Engine must apply some strategy to determine which rule to fire first. Bob
had indicated in his response to the original posting that drools uses
"rule-load-order" to determine which rules to fire. I take that mean the
rules can be thought of as numbered based on where they appear in the .drl
file. If multiple rules can be fired drools will fire from the lowest number
first and then move up the chain through each of the higher numbered rules.
This ordinal numbering of Rules is defined as SALIENCE and is used by JESS
and CLIPS as the basis for various strategies.
Jackson describes 3 conflict resolution mechanisms in his book (See
references): Refactoriness, Recency, and Specificity.

Refactoriness - is that a rule shouldn't fire more than once on the same set
of data.

Recency - Working memory objects are time tagged and rules that can fire are
prioritized based on whether they are triggered by more recent data.

Specificity - the rules with more conditions (therefore more specific) fire
first.

CONFLICT RESOLUTION STRATEGIES
Given the above background here are my suggestions on improving drools
conflict resolution:

SALIENCE
The easiest suggestion would be to add a salience parameter to the
definition of the Rule. This would allow Rules to be added in any order and
still let the developer to have some control over how those rules will be
processed when their are conflicts. There would still be a need for the
rule-load-order because a developer could end up with Rules with the same
SALIENCE. Rules added dynamically could then be inserted into the Rule base
with higher or lower prioirity based on data collected during runtime. It's
also a first step at providing information into a rule to allow more complex
strategies.

DEPTH
This is an add on to SALIENCE. Rules triggered by new data are placed above
rules of the same SALIENCE triggered by old data. This provides a depth
first search over the data.

BREADTH
Rules triggered by new data are placed below rules of the same SALIENCE.
This allows all the rules triggered first to be completed before the next
cycle of rules come into play.

SIMPLICITY
If the Rules provide a number for the amount of conditions they have. Now
when multiple Rules with the same SALIENCE conflict we can use the simpler
rules first ie. the ones with lower specificity. This is a good startegy if
we always want to do something or trigger something on a related set of
rules.

COMPLEXITY
This is the reverse of SIMPLICITY choose the higher specificity first.

CONCLUSION
Once the information is available within the Rule we can then make the
strategy user selectable and allow the developer to provide their own
Conflict resolution strategy.

REFERENCES
Nambiar, Ullas B. "Study of JAVA based Expert System Shell - JESS" Dept of
Comp. Sci. Arizona State University

Jackson Peter "Introduction to Expert Systems" Addison-Wesley 1999