Rule-based Systems Brian C. Williams 16.410-16413 September 10th, 2003 from: 6.034 Tomas Lozano perez Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Goal-directed Rule Systems
1 Rule-based Systems 1 Brian C. Williams 16.410 – 16.413 September 10th, 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
Rules on NEAr and messenger A Simple Reflex System Reflex Rules NEAR CourtesyofNasa/JhuaPl.http://www.jhuapl.com Applying Rules to the NeAr Spacecraft Sample NEAR rule ymptom (Charger current>0.8 A) Switch to the redundant charger and disengage the CourtesyofNasa/JhuaPl.http://www.jhuapl.con
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
Rules on Cassini: A State Centered Approach Rules Observations CourtesyofNasa/jPl-cAlteCh.http://www.jpl.nasa.gov Rules Deduction style IF Antecedent THEN B2 Consequent Each rule should capture a single independent inference and should make sense by itself Examyf (is-a-parent-of ?x 2y/variables is-a- parent-o￡?y? ThEN (is-a-grand-parent-of ?x ?z) Variables of the same name must have the same value
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
Rule Based systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems rward chaining Production rules Goal-directed Rule Systems Rule based architecture Programs: Knowledge is lost within the control structures .Rule-based Architectures: Separate knowledge and control Knowledge: rules assertions
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
Rule based architecture Rule sse Interpreter Programs: Knowledge is lost within the control structures ule- based Architectures: Separate knowledge and control Knowledge assertions Control: rule interpreter Rule based architecture Rule interpreter Programs: Knowledge is lost within the control structures .Rule- based Architectures: Separate knowledge and control Knowledge: rules& assertions Control: rule interpreter
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
Rule based architecture Rule sse Interpreter rule Match antecedents Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules assertions Control: rule interpreter Rule based architecture Rule Pick consequent Interpreter rule Match antecedents 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
Rule based architecture Conflict resolution strategy Assertions consequent Interpreter rule Match antecedents Programs: Knowledge is lost within the control structures Rule-based Architectures: Separate knowledge and control Knowledge: rules assertions Control: rule interpreter conflict resolution strategy Rule Based Systems Big idea: Separation of Knowledge and Control Rules Forward Rule Systems Forward chair Production rules Goal-directed Rule Systems
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
Rule Interpreter(forward chaining) Identify triggered rules, creating rule instances Choose one rule instance(called conflict resolution) Fire the chosen rule instance 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 rule instance: rule with variables filled in
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
Rule Interpreter(forward chaining Identify triggered rules, creating rule instances antecedents in assertions database rule instance: rule with variables filled in Choose one rule instance(called conflict resolution) Conflict resolution strategies e.g. first instance, random instance, etc Rule Interpreter(forward chaining) Identify triggered rules, creating rule instances triggered rule antecedents in assertions database 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 ndicated by the rule (e.g. adding a new 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
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 Fire the chosen rule instance Firing a rule instance means performing the actions ndicated 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) 1:主f hroat infec)) ococcus) then (sages tthat at infec) R4: if R2: if stain gram-pos) red throat then (signs (throat infec)) morph chain Asserti。ns: (sore throat (。 rg stain gram-pos) org morph coccus)
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)