INFERENCE ENGINE GREEDINESS - SUBSUMPTION AND SUBOPTIMALITY

Greedy inference engines find solutions without a complete enumeration of all solutions. Instead, greedy algorithms search only a portion of the rule set in order to generate a solution. As a result, using gree dy algorithms results in some unique system verification and quality c oncerns. This paper focuses on mitigating the impact of those concerns . In particular, rule orderings are established so that better solutio ns can be found first and those rules that would never be examined by greedy inference engines can be identified. The primary results are dr iven by rule specificity. A rule is more specific than some other rule when the conditions in one rule are a subset of the conditions in ano ther rule. If the least specific rule is ordered first and it is true, then greedy algorithms will never get to the more specific rule, even if they are true. Since the more specific rules generally also have t he greatest return this results in the 'wrong' ordering-the rule with the least return will be found. As a result, this paper focuses on gen erating orderings that will likely lead to higher returns. (C) 1997 El sevier Science B.V.