1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 20Milos [email protected] Sennott SquarePlanning: situation calculus CS 1571 Intro to AIM. HauskrechtKnowledge-based system• Knowledge base:– A set of sentences that describe the world in some formal (representational) language (e.g. first-order logic)– Domain specific knowledge• Inference engine:– A set of procedures that work upon the representational language and can infer new facts or answer KB queries (e.g. resolution algorithm, forward chaining)– Domain independentKnowledge baseInference engine2CS 1571 Intro to AIM. HauskrechtAutomated reasoning systemsExamples and main differences:• Theorem provers– Prove sentences in the first-order logic. Use inference rules, resolution rule and resolution refutation. • Deductive retrieval systems– Systems based on rules (KBs in Horn form)– Prove theorems or infer new assertions (forward, backward chaining) • Production systems– Systems based on rules with actions in antecedents– Forward chaining mode of operation• Semantic networks – Graphical representation of the world, objects are nodes in the graphs, relations are various linksCS 1571 Intro to AIM. HauskrechtProduction systemsBased on rules, but different from KBs in the Horn formKnowledge base is divided into:• A Rule base (includes rules)• A Working memory (includes facts)A special type of if – then rule• Antecedent: a conjunction of literals – facts, statements in predicate logic• Consequent: a conjunction of actions. An action can:– ADD the fact to the KB (working memory)– REMOVE the fact from the KB (consistent with logic ?)– QUERY the user, etc …knaaappp ,,,2121KK ⇒∧∧3CS 1571 Intro to AIM. HauskrechtProduction systemsBased on rules, but different from KBs in the Horn formKnowledge base is divided into:• A Rule base (includes rules)• A Working memory (includes facts)A special type of if – then rule• Antecedent: a conjunction of literals – facts, statements in predicate logic• Consequent: a conjunction of actions. An action can:– ADD the fact to the KB (working memory)– REMOVE the fact from the KB !!! Different from logic– QUERY the user, etc …knaaappp ,,,2121KK ⇒∧∧CS 1571 Intro to AIM. HauskrechtProduction systems•Use forward chaining to do reasoning:– If the antecedent of the rule is satisfied (rule is said to be “active”) then its consequent can be executed (it is “fired”)• Problem: Two or more rules are active at the same time. Which one to execute next?• Strategy for selecting the rule to be fired from among possible candidates is called conflict resolutionR27R105Conditions R27Conditions R105Actions R27Actions R105?4CS 1571 Intro to AIM. HauskrechtProduction systems• Why is conflict resolution important? Or, Why do we care about the order? • Assume that we have two rules and the preconditions of both are satisfied:• What can happen if rules are triggered in different order?)()()()( xDaddyCxBxA ⇒∧∧)()()()( xAdeletezExBxA ⇒∧∧R1:R2:CS 1571 Intro to AIM. HauskrechtProduction systems• Why is conflict resolution important? Or, Why do we care about the order? • Assume that we have two rules and the preconditions of both are satisfied:• What can happen if rules are triggered in different order?– If R1 goes first, R2 condition is still satisfied and we infer D(x)– If R2 goes first we may never infer D(x))()()()( xDaddyCxBxA ⇒∧∧)()()()( xAdeletezExBxA ⇒∧∧R1:R2:5CS 1571 Intro to AIM. HauskrechtProduction systems• Problems with production systems:– Additions and Deletions can change a set of active rules;– If a rule contains variables testing all instances in which the rule is active may require a large number of unifications.– Conditions of many rules may overlap, thus requiring to repeat the same unifications multiple times. • Solution: Rete algorithm– gives more efficient solution for managing a set of active rules and performing unifications– Implemented in the system OPS-5 (used to implement XCON – an expert system for configuration of DEC computers)CS 1571 Intro to AIM. HauskrechtRete algorithm• Assume a set of rules:• And facts:• Rete:– Compiles the rules to a network that merges conditions of multiple rules together (avoid repeats)– Propagates valid unifications– Reevaluates only changed conditions)()()()( xDaddyCxBxA ⇒∧∧)()()()( xEaddxDyBxA ⇒∧∧)()()()( xAdeletezExBxA ⇒∧∧)5(),4(),3(),2(),2(),1( CBBBAA6CS 1571 Intro to AIM. HauskrechtRete algorithm. Network.)()()()( xDaddyCxBxA ⇒∧∧)()()()( xEaddxDyBxA ⇒∧∧)()()()( xAdeletezExBxA ⇒∧∧)5(),4(),3(),2(),2(),1( CBBBAARules:Facts:CS 1571 Intro to AIM. HauskrechtConflict resolution strategies • Problem: Two or more rules are active at the same time. Which one to execute next?• Solutions:– No duplication (do not execute the same rule twice)– Recency. Rules referring to facts newly added to the working memory take precedence– Specificity. Rules that are more specific are preferred.– Priority levels. Define priority of rules, actions based on expert opinion. Have multiple priority levels such that the higher priority rules fire first.7CS 1571 Intro to AIM. HauskrechtSemantic network systems• Knowledge about the world described in terms of graphs. Nodes correspond to:– Concepts or objects in the domain.Links to relations. Three kinds:– Subset links (isa, part-of links)– Member links (instance links)– Function links.• Can be transformed to the first-order logic language• Graphical representation is often easier to work with – better overall view on individual concepts and relationsInheritance relation linksCS 1571 Intro to AIM. HauskrechtSemantic network. Example.ShipOcean liner Oil tanker Engine HullSwimmingpoolQueenMaryExxonValdezBoilerisa isamember memberis-partis-partis-partis-partQueen Mary is a shipQueen Mary has a boilerWaterTransports onInferred properties:8CS 1571 Intro to AIM. HauskrechtPlanning: situation calculus CS 1571 Intro to AIM. HauskrechtRepresentation of actions, situations, eventsThe world is dynamic:• What is true now may not be true tomorrow• Changes in the world may be triggered by our activitiesProblems:• Logic (FOL) as we had it referred to a static world. How to represent the change in the FOL ?• How to represent actions we can use to change the world?Planning problem:• find a