1 Rule-based Systems 1 Brian C. Williams 16.410 – 16.413 September 10 th , 2003 Slides adapted from: 6.034 Tomas Lozano Perez Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Goal-directed Rule Systems 2 Reflex Rules NEAR Spacecraft Observations Action Rules on NEAR and Messenger: A Simple Reflex System Applying Rules to the NEAR Spacecraft Sample NEAR rule Symptom : – (Charger current > 0.8 A) for 10 sec Recovery : – Switch to the redundant charger and disengage the primary. Courtesy of NASA/JHUAPL. http://www.jhuapl.com Courtesy of NASA/JHUAPL. http://www.jhuapl.com 3 Rules on Cassini: A State Centered Approach Diagnostic Rules Repair Rules Failure Mode Cassini Spacecraft Observations Action Each rule should capture a single independent inference and should make sense by itself Deduction style Rules IF A1 A2 THEN B1 B2 Antecedent Consequent variables Variables of the same name must have the same value Example: IF (is-a-parent-of ?x ?y) (is-a-parent-of ?y ?z) THEN (is-a-grand-parent-of ?x ?z) Courtesy of NASA/JPL-Caltech. http://www.jpl.nasa.gov 4 Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Forward chaining Production rules Goal-directed Rule Systems Rule Based Architecture Assertions Rules Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions 5 Rule Based Architecture Assertions Rules Rule Interpreter Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter Rule Based Architecture Assertions Rules Rule Interpreter Pick rule Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter 6 Rule Based Architecture Assertions Rules Rule Interpreter Match antecedents Pick rule Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter Rule Based Architecture Assertions Rules Rule Interpreter Match antecedents Add consequent Pick rule Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter 7 Rule Based Architecture Assertions Rules Rule Interpreter Match antecedents Add consequent Pick rule Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter & conflict resolution strategy Conflict Resolution Strategy Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Forward chaining Production rules Goal-directed Rule Systems 8 Rule Interpreter (forward chaining) Identify triggered rules, creating rule instances triggered rule: – antecedents in assertions database – can change the database (e.g. add new assertion) rule instance: rule with variables filled in Choose one rule instance (called conflict resolution) Conflict resolution strategies, e.g. first instance, random instance, most specific instance, etc. Fire the chosen rule instance Firing a rule instance means performing the actions indicated by the rule (e.g. adding a new assertion) Terminate when no triggered rules or special stop assertion Rule Interpreter (forward chaining) Identify triggered rules, creating rule instances triggered rule: – antecedents in assertions database – can change the database (e.g. add new assertion) rule instance: rule with variables filled in Choose one rule instance (called conflict resolution) Conflict resolution strategies, e.g. first instance, random instance, most specific instance, etc. Fire the chosen rule instance Firing a rule instance means performing the actions indicated by the rule (e.g. adding a new assertion) Terminate when no triggered rules or special stop assertion 9 Rule Interpreter (forward chaining) Identify triggered rules, creating rule instances triggered rule: – antecedents in assertions database – can change the database (e.g. add new assertion) rule instance: rule with variables filled in Choose one rule instance (called conflict resolution) Conflict resolution strategies e.g. first instance, random instance, etc. Fire the chosen rule instance Firing a rule instance means performing the actions indicated by the rule (e.g. adding a new assertion) Terminate when no triggered rules or special stop assertion Rule Interpreter (forward chaining) Identify triggered rules, creating rule instances triggered rule: – antecedents in assertions database – can change the database (e.g. add new assertion) rule instance: rule with variables filled in Choose one rule instance (called conflict resolution) Conflict resolution strategies e.g. first instance, random instance, etc. Fire the chosen rule instance Firing a rule instance means performing the actions indicated by the rule – (e.g. adding a new assertion) Terminate when no triggered rules or special stop assertion 10 Rule Interpreter (forward chaining) Identify triggered rules, creating rule instances triggered rule: – antecedents in assertions database – can change the database (e.g. add new assertion) rule instance: rule with variables filled in Choose one rule instance (called conflict resolution) Conflict resolution strategies e.g. first instance, random instance, etc. Fire the chosen rule instance Firing a rule instance means performing the actions indicated by the rule – (e.g. adding a new assertion) Terminate when no triggered rules or special stop assertion Forward chaining - strep throat (using rule order for conflict resolution) R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) Assertions: (sore throat) (org stain gram-pos) (org morph coccus) (org growth chains) 11 Forward chaining - strep throat (using rule order for conflict resolution) R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) Assertions: (sore throat) (org stain gram-pos) (org morph coccus) (org growth chains) R3 fires: (signs (throat infec)) Forward chaining - strep throat (using rule order for conflict resolution) R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) Assertions: (sore throat) (org stain gram-pos) (org morph coccus) (org growth chains) R3 fires: (signs (throat infec)) R4 fires: (org streptococcus) 12 Forward chaining - strep throat (using rule order for conflict resolution) R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) Assertions: (sore throat) (org stain gram-pos) (org morph coccus) (org growth chains) R3 fires: (signs (throat infec)) R4 fires: (org streptococcus) R1 fires: (strep throat) Forward chaining - strep throat (using rule order for conflict resolution) R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) Assertions: (sore throat) (org stain gram-pos) (org morph coccus) (org growth chains) R3 fires: (signs (throat infec)) R4 fires: (org streptococcus) R1 fires: (strep throat) Done. 13 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 14 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 15 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 16 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 17 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (y:C z:E) (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (y:C z:E) conflict in y (x:A y:C) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 18 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (y:C z:E) conflict in y (x:A y:C) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) (x:A y:C z:E) (x:B y:D) (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (y:C z:E) conflict in y (x:A y:C) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) (x:A y:C z:E) (x:B y:D) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) conflict in y (x:C y:E) Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) 19 (parent ?x ?y) (parent ?y ?z) (grand-parent ?x ?z) (x:A y:B) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) (x:A y:B z:D) (y:C z:E) conflict in y (x:A y:C) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) (x:A y:C z:E) (x:B y:D) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) conflict in y (x:C y:E) (y:A z:B) conflict in y (y:A z:C) conflict in y (y:B z:D) conflict in y (y:C z:E) conflict in y Forward Chaining with variables IF (parent ?x ?y) (parent A B) (parent ?y ?z) (parent A C) THEN (grand-parent ?x ?z) (parent B D) (parent C E) Goal: Find all variable bindings that make each rule antecedent match an entry in the database: For every variable binding of the first antecedent, find all bindings of the second antecedent, check for consistency of shared variables. – For the third antecedent, – repeat for each combination of valid bindings of the first and second antecedents. ? And so forth… Implementing forward chaining 20 Implementing forward chaining efficiently grandparent example: 1 rule with 2 antecedents 4 assertions in knowledge base ?4x4 = 16 matching operations. ? In general: ? 1 rule with K antecedents ? N assertions, ?worst-case matching grows as N^K ?Practical systems use the RETE algorithm. Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Forward chaining Production rules Goal-directed Rule Systems 21 Production Rules Deduction rules only add new assertions to the database. Production rules can also delete assertions, have side-effects (printing, executing programs, etc). Example: IF (at ?x ?y) (move ?x to ?z) ADD (at ?x ?z) DELETE (move ?x to ?z) (at ?x ?y) Initial database: (at A room1) (move A room2) Rule Adds: (at A room2) Rule Deletes: (at A room1) (move A room2) Production rules are very sensitive to order of execution, so conflict resolution strategy is crucial. Some Conflict Resolution Strategies First- Choose an instance of the rule that occurs earliest in the list of rules. Random - Choose randomly among all the triggered instances. Gives every rule a chance to fire. Least recently fired - Choose instance of the rule that was least recently fired. Gives every rule a chance to fire. Most specific – For backward chaining …choose instance of the rule with the most antecedent conditions, since that suggests the rule is more specific to the current state of the database. Combinations of these are also possible, e.g. most specific and least-recently fired. Beware: Conflict resolution strategies can destroy modularity! 22 Conflict Resolution for Deduction Rules For deduction rule sets that only add assertions, conflict resolution is irrelevant all triggered rule instances will eventually fire, and all be added to the database. But, it is possible to write deduction rules that create “infinite loops”. ?IF ?x THEN (not (not ?x)) If this rule is triggered once, it will keep triggering… A conflict resolution strategy can – Give other triggered rules a chance to fire – Terminate rule firing. Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Goal-directed Rule Systems 23 Goal-directed, Backward Chaining Backward Chaining conclusions -> assertions Focuses derivation, working back from one desired conclusion. Can ask questions when a relevant fact cannot be derived. Forward Chaining assertions -> conclusions Derives all conclusions from the rules and assertions. Assertions must be known at the start of chaining. Start with a possible conclusion and check whether the assertions, together with the rules, justify that conclusion. Start with a query, and apply rules that derive the answer to that query. strep throat expert: What the doctor sees Questions: 1. Red throat? No. 2. Sore throat? Yes 3. Stain gram-pos? Yes 4. Morphology coccus? Yes 5. Growth chains? Yes 24 strep throat expert: What the “expert” decides Questions: 1. Red throat? No. 2. Sore throat? Yes 3. Stain gram-pos? Yes 4. Morphology coccus? Yes 5. Growth chains? Yes (strep throat) (signs (throat infec)) (org streptococcus) (sore throat) R3 (red throat) R2 R1 AND (org stain gram-pos) (org growth chains) (org morph coccus) R4 AND Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Goal-directed Rule Systems Backward Chaining Unification 25 Backward chaining - strep throat R1: if (signs (throat infec)) (org streptococcus) then (strep throat) R2: if (red throat) then (signs (throat infec)) R3: if (sore throat) then (signs (throat infec)) R4: if (org stain gram-pos) (org morph coccus) (org growth chains) then (org streptococcus) (sore throat) R3 (red throat) R2 (strep throat) (signs (throat infec)) (org streptococcus) R1 AND (org stain gram-pos) (org growth chains) (org morph coccus) R4 AND AND-OR Tree for (strep throat) goal Backward chaining - strep throat (strep throat) (signs (throat infec)) (org streptococcus) (sore throat) R3 (red throat) R2 R1 AND (org stain gram-pos) (org growth chains) (org morph coccus) R4 AND (1) initial goal (2) subgoal (3) subgoal Matching rule Matching rules No rules, ask! Questions: 1. Red throat? No. 26 Backward chaining - strep throat (strep throat) (signs (throat infec)) (org streptococcus) (sore throat) R3 (red throat) R2 R1 AND (org stain gram-pos) (org growth chains) (org morph coccus) R4 AND (1) initial goal (2) subgoal (3) subgoal Matching rule Matching rules No rules, ask! (4) subgoal No rules, ask! Questions: 1. Red throat? No. 2. Sore throat? Yes Backward chaining - strep throat (strep throat) (signs (throat infec)) (org streptococcus) (sore throat) R3 (red throat) R2 R1 AND (org stain gram-pos) (org growth chains) (org morph coccus) R4 AND (1) initial goal (2) subgoal (3) subgoal Matching rule Matching rule Matching rules No rules, ask! (4) subgoal No rules, ask! (5) subgoal (6) subgoal (7) subgoal (8) subgoal No rules, ask! No rules, ask! No rules, ask! Questions: 1. Red throat? No. 2. Sore throat? Yes 3. Stain gram-pos? Yes 4. Morphology coccus? Yes 5. Growth chains? Yes 27 Backchain(G) - Rule interpreter If G matched assertion in database, then return True Else If there are rules whose consequent matches G For each matching rule R For each antecedent C of R If Backchain(C) is true, proceed Else go to next rule. Return True /* when all antecedents are true */ Return False /* when no matching rule succeeds */ Else, ask user if G is true. If answer is “yes” return True, Else return False. Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Goal-directed Rule Systems Backward Chaining Unification 28 Unification Forward-chaining: Assertions (no variables) match rule antecedents (patterns with variables) Backward-chaining: (sub)Goals (patterns with variables) match Rule consequents (patterns with variables) (grandparent A ?g) (grandparent ?x ?z) (parent ?x ?y) (parent ?y ?z) R1 R3: if (sore ?x) then (signs (?x infec)) (sore throat) Unification Problem: Find bindings for the variables in two patterns so that the patterns become identical. Example: Unify (grandparent ?x ?z) & (grandparent A ?g) ?Binding: {?x = A, ?z = ?g} Binding ?z = ?g Indicates that both variables must ultimately be assigned the same value. Value not known at time of binding. 29 R1: if (parent ?x ?y) (parent ?y ?z) then (grandparent ?x ?z) R2: if (father ?v2 ?w2) then (parent ?v2 ?w2) R3: if (mother ?v3 ?w3) then (parent ?v3 ?w3) Assertions: (father A B) (mother B C) Backward chaining with variables (grandparent A ?g) (grandparent ?x ?z) (parent ?x ?y) (parent ?y ?z) R1 (parent ?v2 ?w2) (father ?v2 ?w2) R2 A A B B BA (?v2 = A) (?w2 = ?y) (father A B) BA (?y = ?w2 = B) (?x = A) (?z = ?g) A R1: if (parent ?x ?y) (parent ?y ?z) then (grandparent ?x ?z) R2: if (father ?v2 ?w2) then (parent ?v2 ?w2) R3: if (mother ?v3 ?w3) then (parent ?v3 ?w3) Assertions: (father A B) (mother B C) Backward chaining with variables (grandparent A ?g) (grandparent ?x ?z) (parent ?x ?y) (parent ?y ?z) R1 (parent ?v2 ?w2) (father ?v2 ?w2) R2 (parent ?v3 ?w3) (mother ?v3 ?w3) R3 (father A B) (mother B C) A A A A B B B C C B C B C (?x = A) (?z = ?g) (?v2 = A) (?w2 = ?y) (?y = ?w2 = B) B (?y = ?v3 = B) (?g = ?w3 = ?z) CB (?g = ?z = ?w3 = C) A 30 Issue 1: Avoiding variable name conflicts Consider subgoal and rule (foo ?x) IF (bar ?x ?y) THEN (foo ?y) Backward chaining unifies: (foo ?x) with (foo ?y) ? {?y = ?x} Creates new subgoal: (bar ?x ?x) Matches assertions like (bar A A) Doesn’t match assertions like (bar A B) Problem:Occurrence of ?x in subgoal and rule accidental Solution: Give variables unique names in rules Issue 1: Avoiding variable name conflicts Consider subgoal and rule (foo ?x) IF (bar ?x1 ?y1) THEN (foo ?y1) Backward chaining unifies: (foo ?x) with (foo ?y1) ? {?y1 = ?x} Creates new subgoal: (bar ?x1 ?x) Matches assertions like (bar A A) Does match assertions like (bar A B) Problem:Occurrence of ?x in subgoal and rule accidental Solution: Give variables unique names in rules 31 Issue 2: Occurs check Consider the unifier for: (likes ?z ?z) (likes ?y (house-of ?x)) ?{?z = ?y, ?z = (house-of ?x)}, hence ?y = (house-of ?x), which is consistent. Consider the unifier for: (likes ?z ?z) (likes ?x (house-of ?x)) ?{?z = ?x, ?z = (house-of ?x)} hence ?x = (house-of ?x), which is problematic. Solution: In unification, a variable cannot be assigned to an expression where that variable occurs. which is problematic Rule Based Architecture Assertions Rules Rule Interpreter Match antecedents Add consequent Pick rule Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules & assertions Control: rule interpreter & conflict resolution strategy Approaches: Forward Chaining: Deductive and Response Systems Backward Chaining: Goal-driven and Query Systems ? Core Computation: Unification Conflict Resolution Strategy 32 Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Forward Chaining Production Systems Goal-directed Rule Systems Backward Chaining Unification