Page 202 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes determine which rules have their LHS conditions satisfied with consistent
bindings to working memory terms.

Rules which are found to be applicable are put in a conflict set.
Select:
From the conflict set, one of the rules is selected to execute. The selection
strategy may depend on recency of usage, specificity of the rule or other
criteria.

Execute:
The rule selected from the conflict set is executed by carrying the action or
conclusion part of the rule, the RHS of the rule. This may involve an I/O
operation, adding, removing or changing clauses in working memory or
simply causing a halt.

The above cycle is repeated until no rules are put in the conflict set or until a
stopping condition is reached.

The main time saving features of Rete are as follows:
1. In most expert systems, the contents of working memory change very little from cycle to
cycle. There is persistence in the data known as temporal redundancy. This makes exhaustive
matching on every cycle unnecessary. Instead, by saving match information, it is only
necessary to compare working memory changes on each cycle. In RETE, addition to,
removal from, and changes to working memory are translated directly into changes to the
conflict set in Figure 10.2 shown below. Then when a rule from the conflict set has been
selected to fire, it is removed from the set and the remaining entries are saved for the next
cycle. Consequently, repetitive matching of all rules against working memory is avoided.
Furthermore, by indexing rules with the condition terms appearing in their LHS, only
those rules which could match. Working memory changes need to be examined. This
greatly reduces the number of comparisons required on each cycle.

Figure 10.2: Changes to Working Memory are Mapped to the Conflict Set

2. Many rules in a knowledge base will have the same conditions occurring in their LHS.
This is just another way in which unnecessary matching can arise. Repeating testing of the
same conditions in those rules could be avoided by grouping rules which share the same
conditions and linking them to their common terms. It would then be possible to perform
a single set of tests for all the applicable rules shown in Figure 10.3 shown below:

196 LOVELY PROFESSIONAL UNIVERSITY