FORWARD CHAINING PRODUCTION SYSTEMS =================================== Introduction ------------ A forward chaining production system consists of (1) a working memory (WM) or short-term memory (STM) containing facts, (2) a production memory (PM) containing if-then rules, and (3) an inference engine. The design of the original forward chaining production systems was heavily influenced by theories of cognitive psychology. WM was designed to model human short-term memory, and typically would contain very few items (seven plus or minus two). These were operated upon by the rules in PM, which could read from and write to WM. Rules in PM were designed to model neurons, or clusters of neurons, inside the brain. ---------- Working Memory -------------- Facts held in working memory can be considered to be variable-free atomic formulae from first-order predicate calculus, i.e. they are either constants, or have the following form: predicate(atomic-formula-1, ... , atomic-formula-N) Examples: (1) blattering (2) rain-type(17) (3) moving-on(cranes, skyline) (4) s(np(det(the), noun(cranes)), vp(verb(to-be(are), vn(moving)), pp(prep(on), np(det(the), noun(skyline))))) The last example illustrates how facts complex in structure can be built up and included in WM. WM is constantly changing during the execution of the production system, as a result of rules in PM adding or deleting facts. ---------- Production Memory ----------------- PM consists of rules of the form IF condition THEN action1 ... actionN The condition of a rule can be considered to be any well-formed formula in first-order predicate calculus in which the connectives (logical relations) are restricted to AND and NOT. OR is sometimes also allowed but is not strictly necessary, as any rule of the form IF cond1 OR cond2 THEN action can be replaced by two rules of the form IF cond1 THEN action IF cond2 THEN action Thus, conditions can be restricted to the form cond1 AND cond2 AND ... AND condN, where CONDI takes one of the following forms: atomic-formula NOT(atomic-formula) The conditions of a rule are matched against WM contents, thus causing the variables in the rules to be assigned values by unification, as in predicate calculus. Those values are then substituted for the same variables in the rule's actions; the rule is then said to be instantiated. Actions can take any of the following forms (1) ADD(atomic-formula) (2) DEL(atomic-formula) (3) READ() (4) PRINT(atomic-formula) or PRINT(string) The atomic formulae in this case can contain varables, unlike those in working memory, provided those variables are contained in a non- negated condition in the same rule. This is because, when a rule is about to be fired (which will generally cause it to modify WM), the variables in its conditions will already have been assigned values when they were matched with the contents of WM. ADD adds a fact to WM. If it is already present, one of two things can happen, depending on the specification of the production system: either the fact is added again (causing more than one copy of the same fact to coexist in WM), or nothing happens (meaning that multiple copies are not permitted). DEL deletes a fact from WM. If the fact is not present in WM, either nothing happens or an error message is generated. If multiple copies of the same fact are present, only one of the copies is deleted -- the other copies remain. READ causes the system to wait for input, which is added to WM. Input must obey the syntax of the WM elements. PRINT causes either an atomic formula or a character string to be printed. ---------- The Inference Engine -------------------- The inference engine controls the selection and firing of rules, and determines when the system is to halt. Generally a forward chaining production system is given a goal, i.e. it is invoked by means of a command such as the following: run(g) where g is a variable-free atomic formula. The production system adds goal(g) to WM, and then executes the following algorithm: while goal is not true, loop (1) Build up a conflict set, i.e. a list of all the rules whose conditions have matched successfully against the contents of WM. The conflict set may contain the same rule twice, matched against different conditions in WM to produce different substitution list. If the conflict set is empty, then exit loop and halt the production system. (2) Use conflict resolution (explained below) to select a single rule from the conflict set. (3) Fire the rule selected during stage (2), i.e. execute all of the rule's actions. end loop; ---------- Conflict Resolution ------------------- Conflict resolution is necessary in the case where the conflict set contains more than one rule. There are several different strategies used to handle this situation. These include (1) If a rule has already been fired recently, do not fire it again. This prevents the production system from looping (2) Prefer those rules which mention goals which are currently being pursued to those rules which do not mention any goals, and prefer those rules which do not mention any goals to those which mention goals which are not being currently being pursued. In order to do this, it is convenient to have the goals explicitly flagged as such. (3) Prefer the least general rule, i.e. the rule with the most non-negated conditions; thus, where WM contains a, b, c, and d, IF a AND b AND c THEN action would be fired in preference to IF a AND b THEN action. (4) Prefer the rule whose conditions are matched by the most recent WM elements; thus, where WM contains a, b, and c, with c the most recent, IF a AND c THEN action would be fired in preference to IF a AND b THEN action. (5) Fire the first rule in the conflict set. In this case, it was not actually necessary to build it in the first place. Which rule is fired in this strategy depends critically on the order of the rules in PM. There is a sixth conflict resolution strategy -- using metaknowledge explicitly encoded in forward-chaining rules. In this case, after the conflict set has been built, control is temporarily handed to a production system containing metaknowledge, whose goal is to resolve the conflict.