The expertise of any agent (domain-specific or pedagogical) is expressed by a set of rules. These rules are executed by the inference engine. We have implemented an inference engine in order to achieve a high level of integration between the rules and the other components of the system. We first describe the generic engine. i.e. an application-independent engine that could be applied to any AI problem. Then, we explain how we added some facilities or modified some aspects of the engine to adapt this generic engine to the architecture of ETOILE.
The implemented production system has the following features:
In first-generation rule based systems, the inference engine was assigned a special working memory, neatly separated from other data structures such as those manipulated by conventional code. This working memory was represented as a list of assertions which were matched with rule conditions to determine applicable rules. The advent of object-oriented languages led to an intermediate version where a global memory of object structures coexisted with a working memory of logical assertions: only the latter was accessible to the inference engine. The OOPS-engine strives towards full integration of object-oriented and rule-based representation. On the one hand, rules should refer to and work directly on the hierarchy of classes and objects present in the global memory. On the other hand, rules themselves, their antecedents and their conclusions, as well as the other task-implementation structures needed to operate the inference engine (ex. the current conflict set) are all represented as objects.
- a powerful rule representation language
To give an idea of the expressive power of the representation language used, the basic rule condition template is the following:
(<object> is <class> with
<slot1> <operator1> <value1> &
.. &
<slotn> <operatorn> <valuen>)
where <operator> can be =, <>, <, >, <=, or >=.
This rule condition is the object-oriented equivalent of a set of two-place logical assertions where <slot> is the predicate, <object> the first argument and <value> the second argument. Note that here, the rule interpreter allows variables not only for the arguments but also for the predicate, thus approximating the power of second-order predicate logic. In addition, a rule condition may include any function call:
(CALL <function> <argument>* <operator> <result>)
Universally and existentially quantified rule conditions are also allowed:
(FORALL (<variable>*) (<var-domain-condition>*)
<subcondition>*)
(FORSOME (<variable>*) (<var-domain-condition>*)
<subcondition>*)
Finally, any of the above rule conditions (or any conjunction of these) may be negated.
The most important rule actions consist in creating or destroying objects, or modifying slot values of objects. In the general case, these actions are applied to objects of the application domain; they are then base-level actions. But since rules themselves are represented as full-fledged objects, these same actions become meta-actions when applied to rules; that is, the same set of commands allows us to change rule conditions and actions, rule priorities, etc. Furthermore, metalevel-specific actions, like activating a particular rule or rule set, allow the user to modify the inference engine's control strategy. Finally, to enhance the system's flexibility, any user-defined function can be called from a rule's right-hand side.
Up to this point, we have referred to `the' inference engine as though only one were possible in a given system. Actually this system has been designed with a view to implement multi-expert systems. Any number of inference engines can be created, each associated with its own knowledge base (KB) (tutors, experts, coach). We originally envisaged a non hierarchical set of agents. Coordination would then have required a central control process such as a blackboard. However, the society of agents in ETOILE is now highly structured: the coach controls the tutors and the tutors control the experts. We hence abandoned our preliminary attempts to apply a blackboard approach.
Since rules are represented in exactly the same formalism and within the same global memory as domain objects, rules can reason about rules and can examine their own (and other rules') components, evaluation contexts, history of past successes and failures, etc. Rules can also modify (even destroy) themselves and other rules as well as create new rules. Full metareasoning power is not available in classical production system languages: an OPS5 rule, for example, cannot directly examine its own instantiations because these are represented differently and separately from domain knowledge. To implement metalevel reasoning in such systems, programmers usually have to code special-purpose functions to retrieve metaknowledge inaccessible to rules.However, these facilities are currently not exploited by ETOILE.
Like all production system interpreters, the OOPS inference engine follows a deliberation-action cycle.
During the deliberation cycle, the interpreter evaluates and selects the rule to be fired. Two contending philosophies underlay rule evaluation procedures as implemented in existing inference engines. The first is what we might call maximal fact propagation. Whenever a modification is made in the knowledge base, this change is propagated in all existing rules so that at each instant, the interpreter knows exactly which rules will fire, and with which instantiations. This approach is illustrated by the RETE network which is at the heart of many production system interpreters such as OPS5.
However, several criticisms of the Rete algorithm have been aired since. First, critics of the maximal propagation approach contend that it is at its best when working memory does not change very much. TREAT claims to remedy precisely this drawback of the OPS5 interpreter. Second, the OPS5 interpreter does not allow partitioning of the rulebase into rule sets, precisely because the RETE network is a monolithic network which has to be updated integrally each time a working memory element is added, removed or modified. Third, both the representation of rules and the operation of the RETE network are such as to make metareasoning nearly impossible. In OPS5, for example, there is no way to write a metarule that examines, for instance, the conditions, actions, current instantiations or past history of a given rule in order to take a strategic decision on rulebase management.
The solution adopted for the OOPS engine aims at overcoming these three shortcomings. For a highly volatile working memory, a partial propagation approach coupled with complete rule evaluation after conflict resolution may be the optimal solution. Furthermore, changes in working memory entail reconsideration, not of all the rules in the current rulebase, but only of those in the active rule set(s). This saves a lot of computational time in the case of very large rule bases. Finally, since rules are represented as objects in OOPS, rules can examine and modify other rules in the same way that they examine and modify any base-level object.
- Conflict set maintenance
When a rulebase is run, the conflict set (CS) is initialized to all the rules of the currently active rule set. Conflict set updates take place whenever changes are made to working memory, whether during rule firing (execution of a rule's right-hand side) or in response to top-level user commands which modifies working memory. When a value is added to an object slot, all rules containing a positive condition which partially match this object-slot-value triple are added to the conflict set. When a value is deleted from an object slot, all rules containing a negative condition which partially matches this object-slot-value triple are added to the conflict set.
The update technique used above, based on partial matches, is the heart of the minimal propagation approach. In the maximal propagation approach, each working memory modification leads to a complete revision of the status of all rule conditions, thus the updated conflict set contains only firable rules, i.e., rules that will surely fire. In OOPS' minimal propagation approach, the conflict set contains candidate rules, only a subset of which will surely fire. The underlying principle in the latter case is that it is safer to leave in the CS rules that will not actually fire (the price to pay would be a loss in efficiency) rather than to eliminate from the CS rules that could have fired (in which case the - unjustifiable - price to pay would be incorrectness).
- Rule choice
As we have seen above, the conflict set contains rules that will certainly fire as well as a few rules that may not fire. If the conflict set contains only one candidate rule, then that rule is evaluated. Otherwise, conflict resolution is based on two criteria:
- Choose the rule with the highest priority. The user can attribute priorities to rules using the keyword priority followed by an integer. The value 0 represents the highest priority. By default, rules are assigned priority 99.
- Among rules of equal priority, choose the most constrained rule, i.e., the rule with the greatest number of rule condition tests.
- If more than one rule remains in the conflict set after the above elimination process, select the first rule in the set.
- Rule evaluation
Rule evaluation consists in verifying the satisfaction of all conditions of the rule's left hand side by matching each one against working memory. At any moment during rule evaluation, the interpreter maintains two stacks of rule conditions---matched conditions and pending conditions---as well as the list of current variable bindings, which will constrain the possible instantiations of pending conditions.
The order in which conditions are matched is determined dynamically, on the basis of the current state of working memory. The principle of condition choice is the following: give priority to the condition that is least likely to match. The rationale of this principle is that if the rule will not fire, we might as well find out as soon as possible. That would save us computer time spent on evaluating conditions that match before having to give up on encountering one that doesn't. Below are criteria followed for dynamic condition choice:
- If there is a single remaining condition, evaluate it; else:
- Take any ground---i.e., fully instantiated---condition if one exists.
- Identify conditions that relate to the same object as that instantiated in a previously evaluated condition.
If no such condition exists, take any condition which is completely instantiated except for the variable represented the object.
If only one such condition is pending, then evaluate it, else select one using the following criteria:
- Select the most constrained condition, i.e., that which has the fewest unbound variables. If several conditions have the minimal number of unbound variables:
- Select the condition that is least likely to be instantiated, i.e., the condition which has the shortest list of candidate instantiations (determined on the basis of the current facts).
- If none of the above criteria yields a single candidate condition, take the first pending condition.
All actions in the current rule's right hand side are simply executed in sequence. The OOPS-engine follows the principle of rule exhaustion---i.e., once a rule has been selected, it is fired for all possible instantiations. Concretely, this means that when a rule is selected for evaluation, each of its conditions is attributed a list of possible instantiations on the basis of existing facts in the object hierarchy. The rule is fired for all possible combinations of these different instantiations. Once a rule has been fired for a given instantiation, the interpreter backtracks over the successfully evaluated rule conditions: each condition in the matched-conditions stack is unstacked and reevaluated for remaining elements in its list of candidate instantiations.
The task of finding all possible instantiations of a condition set at a given time becomes more complicated in the case of self-referencing rules. A self-referencing rule is one which tests a slot of object in the left-hand side, then modifies or deletes the slot or the object in its right-hand side. When the rule is fired for a given instantiation, modifications made to a subset of this instantiation can make all pending instantiations invalid. Thus the need to unstack all evaluated conditions down to that condition whose terms have been modified during rule firing. All this is ensured by the inference engine in a manner transparent to the user. At rule compilation time, the parser identifies conditions concerning slots and objects that are affected (added, deleted or modified) by one or several rule actions. It does this by examining the correspondences between slots and objects tested by object-slot-value conditions in the LHS and the arguments of object-centered actions in the RHS. Thus the interpreter knows, at rule evaluation time, which conditions have had their instantiation candidates invalidated during firing. In order that this process can work with no major problems, the golden rule the user should follow is: a function called from the RHS of a rule should NEVER execute a hidden object-slot-value modification that will affect an object slot that is being tested in the condition part of that same rule. All such modifications should be made explicit in the RHS using typical object-centered actions such ADD-VALUE, DELETE-VALUE, SET-VALUE, MAKE-OBJECT and KILL-OBJECT.
There are many differences between a genuine expert system and the role of an expert in the architecture of ETOILE. These differences led us to adapt the inference engine in various ways. Most of these differences have been defined outside the core inference engine (in a function called do-etoile-kludge).
A genuine expert system has to produce ONE solution, ideally the optimal solution. In ETOILE, the expert must cover several solutions since he must maintain the interaction with the learner even if this learner follows a sub-optimal approach. The expert must accept a learner step which is not optimal, but still correct. Hence the expert needs both optimal rules for proposing the best actions and suboptimal rules for accepting suboptimal learner actions. This trade-off between accuracy and flexibility is obtained by attaching a priority integer to rules (see section III.2.1. on page 29). Hence, optimal rules will be considered before suboptimal ones.
The actions of the learner may be worse than suboptimal, they may be wrong. In principle, an autonomous expert system never generates an incorrect problem state since all its rules define only legal moves. However, in ETOILE, the expert might face an incorrect situation created by the learner. He therefore has a set of rules called `repair' rules (see section 4.4. "The learner-expert-tutor triangle" on page 11). The repair rules are not triggered in isolation from the other rules. The `repair rule' class is a sub-class of the `rule' class. Its syntax is similar except that repair rules have an additional slot that includes a pointer towards a hypertext node that is relevant for the type of mistake that made a repair necessary.
A genuine expert system does not perform any learner modelling. This function implies changes in the normal sequence of operations of a production system. Here are some examples of modifications that are specific to the diagnosis mode:
- When the expert activates his rules to evaluate the learner's actions, he must find the activatable rules without activating them really. Hence, the inference engine must support a `preview' mode that does not activate the rule conclusions.
- The learner's actions change the problem from state N to state N+1. If the expert rule preview is performed after the learner's action, he obtains the rules activatable for the state N+1. It would of course be nonsense to compare the learner's action at state N with the expert's action at state N+1. Hence, the expert previews its rulebase before the learner does anything, and stores the activatable rules for later comparison with the learner action.
- Let us assume that on one hand the learner creates a list of 20 words with no particular properties. On the other hand, one of the expert's activatable rules leads to a list of 22 words without particular properties. The learner's and expert's actions are not identical, but from a pedagogical viewpoint, they should be considered as equivalent. Hence, for each feature of an object, the author must specify a predicate (equivalent-? feature value-1 value-2) that determines when the difference between two values of this feature is significant.
In ETOILE, the expert does not work alone but in interaction with a learner. He does not work in an abstract world defined by facts but he has to accomplish actions affecting the rest of the system. In other words, if one wants to integrate an inference engine into an interactive system, we must tolerate function calls in the rule actions or conditions.
Rule actions modify the objects base via OOPS-specific terminology (e.g., ADD-VALUE, DELETE-VALUE, KILL-OBJECT) which, in addition to changing some slot value, propagate these changes to determine how to update the conflict set. If a rule action includes a procedure that changes some objects with the usual Lisp accessors, these changes will remain invisible to the inference engine as it updates the conflict set. As a result, the conflict set will no longer correctly reflect the actual state of object memory. The technical solution consists in using a table where the customized functions used by the expert are explicitly declared to produce side effects on specific slots of specific classes.
In the condition part, two types of function calls are performed. The first case concerns predicates that do not exist in OOPS or summarize in one expression a condition that would need many expressions in the OOPS syntax. The second case returns particular predicates representing learner responses to questions asked by a tutor or expert (e.g. "Do you agree that I undo your previous move?"). In both cases, the function calls do not change the objects, they only affect the dynamic evaluation of conditions.
Control flows from one agent to another. Regarding the tutors and the coach, the deliberation-action cycle is repeated until it activates a rule that explicitly activates another agent. The expert cycle is determined by the two factors previously described in section 4.2. "How to implement the interaction between the learner and a computational agent?" (page 9): the local and the global interaction modes. If the local interaction mode is `observe', the expert performs a rule preview, waits for the learner's action, compares it to the actions he would have done, determines the diagnosis value (positive, negative or unknown) and returns control to the active tutor. If the local interaction mode is `propose', the expert will perform a certain number of consecutive steps. The number of steps is determined by the value of the global interaction mode. In other words, the inference engine includes a simple step counter and stops when the required number of steps has been performed. A `step' does not correspond to a single iteration of the deliberation-action cycle, it involves a sequence of cycles which terminates once a fired rule executes a microworld command. The expert may first fire a sequence of rules for updating private objects (e.g. task goals), and only later on activate one rule that affects the microworld. When N steps are performed successively, the expert conducts a brief dialogue with the learner between two steps. He instantiates and presents the comments associated with the fired rule, then asks the learner whether he allows the expert to carry on. If the learner agrees, the expert performs the next step. If the learner asks to stop or to continue by himself, the expert returns control to the tutor.