### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# INTROTOARTIFICLINTELLIGENCE CS1571

Pitt

GPA 3.77

### View Full Document

## 32

## 0

## Popular in Course

## Popular in ComputerScienence

This 342 page Class Notes was uploaded by Jonas Bartell on Monday October 26, 2015. The Class Notes belongs to CS1571 at University of Pittsburgh taught by MilosHauskrecht in Fall. Since its upload, it has received 32 views. For similar materials see /class/229381/cs1571-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.

## Reviews for INTROTOARTIFICLINTELLIGENCE

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

CS 1571 Introduction to AI Lecture 25 Decision making in the presence of uncertainty Milos Hauskrecht miloscspittedu 5329 Sennott Square 381571 Intro to Al M Hauskrecht Decisionmaking in the presence of uncertainty Many realworld problems require to choose future actions in the presence of uncertainty Examples patient management investments Main issues How to model the decision process in the computer How to make decisions about actions in the presence of uncertainty 381571 Intro to AI M Hauskrecht Decision making example We need to make a choice whether to invest in Stock 1 or 2 put money into bank or keep them at home But how Monetary outcomes for different scenarios CS 1571 Intro to AI M Hauskrecht Decision tree representation of the problem Investing 100 for 6 months u 06 110 down Stock 2 CS 1571 Intro to AI M Hauskrecht Decision making example Assume the simpli ed problem with the Bank and Home choices only The result is guaranteed the outcome is deterministic 10 Bank 101 10 Home I 100 What is the rational choice assuming our goal is to make money CS 1571 Intro to AI M Hauskrecht Decision making Deterministic outcome Assume the simpli ed problem with the Bank and Home choices only These choices are deterministic 10 10 Home l 100 Our goal is to make money What is the rational choice Answer Put money into the bank The choice is always strictly better in terms of the outcome But what to do if we have uncertain outcomes CS 1571 Intro to AI M Hauskrecht Decision making Stochastic outcome How to quantify the goodness of the stochastic outcome We want to compare it to deterministic and other stochastic outcomes Idea Use the expected value of the outcome CS 1571 Intro to AI M Hauskrecht Expected value Let X be a random variable representing the monetary outcome with a discrete set of values QX Expected value of X is EX Z xPX x XEQX Expected value summarizes all stochastic outcomes into a single quantity Example 100 Expected value for the outcome of the Stock 1 option 06 gtlt110 04 gtlt90 66 36 CS 1571 Intro to AI M Hauskrecht Expected values Investing 100 for 6 months u 102 0396 110 06gtlt11004gtlt90 down 66 36 102 90 140 Stock 2 9 down 39 80 101 10 39l 100 CS 1571 Intro 0 AI M Hauskrecht Expected values Investing 100 for 6 months ll 0396 110 06gtlt11004gtlt90 down 66 36 102 Stock 2 04gtlt140 06gtlt80 5648 104 CS 1571 Intro to AI M Hauskrecht Selection based on expected values The optimal action is the option that maximizes the expected outcome CS 1571 Intro to AI M Hauskrecht Sequential multistep problems The decision tree can be build to capture multi step decision problems Choose an action Observe the stochastic outcome And repeat How to make decisions for multi step problems Start from the leaves of the decision tree outcome nodes Compute expectations at chance nodes Maximize at the decision nodes Algorithm is sometimes called expectimax CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods 200 Two actlons stock and bank 100 125 Stock 130 Wu 10 90 140 80 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods Two actions stock and bank 200 100 125 130 90 140 80 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods Two actions stock and bank 90 140 8 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods Two actions stock and bank 200 100 125 130 90 140 8 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods Two actions stock and bank 90 140 8 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problem example Assume Two investment periods Two actions stock and bank 200 100 125 130 90 140 8 10 105 CS 1571 Intro to AI M Hauskrecht Multistep problems Conditioning Notice that the probability of stock going up and down in the 2quotd step is independent of the 1st step 05 CS 1571 Intro to AI M Hauskrecht Conditioning in the decision tree But this may not be the case In decision trees 7 Later outcomes can be conditioned on the earlier stochastic outcomes and actions Example stock movement probabilities Assume P1 up04 P2 up1 up04 P2 quotup1 down05 CS 1571 Intro to AI M Hauskrecht Multistep problems Conditioning Tree Structure every observed stochastic outcome 1 branch P1 up04 P2 up1 up04 P2 quotup1 down05 1n down 1 down CS 1571 Intro to AI M Hauskrecht Trajectory payoffs Outcome values at leaf nodes eg monetary values 7 Rewards and costs for the path trajectory Example stock fees and gains Assume Fee per period 5 paid at the beginning Gain for up 15 loss for down 10 15L down CS 1571 Intro to AI M Hauskrecht Constructing a decision tree The decision tree is rarely given to you directly 7 Part of the problem is to construct the tree Example stocks bonds bank for k periods Stock 7 Probability of stocks going up in the first period 03 7 Probability of stocks going up in subsequent periods Pkth stepUp k lth step Up04 Pkth Step Up k lth stepDown05 7 Return if stock goes up 15 if down 10 7 Fixed fee per investment period 5 Bonds 7 Probability ofvalue up 05 down 05 7 Return if bond value is going up 7 if down 3 7 Fee per investment period 2 Bank 7 Guaranteedreturn of 3 per period no fee CS 1571 Intro to AI M Hauskrecht Informationgathering actions Many actions and their outcomes irreversibly change the world Information gathering exploratory actions 7 make an inquiry about the world 7 Key bene t reduction in the uncertainty Example medicine 7 Assume a patient is admitted to the hospital with some set of initial complaints 7 We are uncertain about the underlying problem and consider a surgery or a medication to treat them 7 But there are often lab tests or observations that can help us to determine more closely the disease the patient suffers from 7 Goal of lab tests Reduce the uncertainty of outcomes of treatments so that better treatment option can be chosen CS 1571 Intro to AI M Hauskrecht Decisionmaking with exploratory actions In decision trees Exploratory actions can be represented and reasoned about the same way as other actions How do we capture the effect of exploratory actions in the decision tree model Information obtained through exploratory actions may affect the probabilities of later outcomes 7 Recall that the probabilities on later outcomes can be conditioned on past observed outcomes and past actions 7 Sequence of past actions and outcomes is remembered within the decision tree branch CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem An oil wildcatter has to make a decision of whether to drill or not to drill on a speci c site Chance of hitting an oil deposit 0 Oil 40 POz39l T 04 Nooil 60 POz39l F 06 Cost of drilling 70K Payoffs 0 Oil 220K Nooil 0 K 22070150 Drill 70 CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem An oil wildcatter has to make a decision of whether to drill or not to drill on a speci c site Chance of hitting an oil deposit Oil 40 POil T04 Nooil 60 POil F 06 Cost of drilling 70K Payoffs 0 Oil 220K Nooil 0 K 22o7o1so Drill Jo 0 CS 1571 Intro to Al M Hauskrecht Oil Wildcatter problem Assume that in addition to the drillnodrill choices we have an option to run the seismic resonance test Seismic resonance test results 7 Closed pattern more likely when the hole holds the oil 7 Diffuse pattern more likely when empty POil Seismic resonance test Seismic resonance test pattern closed di use True 08 02 False 03 07 Oil Test cost 10K CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem 22o70 10140 Declsmn tree 036 noon mlquot 0 70 1080 clo sed 010 10 2207010140 nooil 84 0 70 1080 010 10 CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem 18 2207010140 Alternative model Drill 036 mom dosed o7o1oso 01010 22o7o1o14o l 0 70 1080 010 10 CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem Decision tree probabilities 22o701014o Drill moi dosed o7o1oso 010 10 PTest closed Oil TPOil T PTevt closed POil T Test closed PTest closed Oil FPOil F PT closed PTest closed PTest closed Oil FPOil F PTest closed Oil TPOil T POil F Test closed CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem Decision tree probabilities 22o701014o 036 nooil dosed o7o1oso 010 10 PTest closed PTest closed Oil FPOil F PTest closed Oil TPOil T PTest di PTest di Oil FPOilFPTest di Oil TPOil T CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem 22e70 10140 Dec1s10n tree 036 noon 60 8 0 70 1080 clo sed Drill 010 10 2207010140 nooil 84 0 70 1080 010 10 CS 1571 Intro to AI M Hauskrecht Oil Wildcatter problem 2207010140 Dec1s10n tree 608 036 noon closed Dnn 0 70 1080 010 10 2207010140 nooil 84 0 70 1080 010 10 The presence of the test and its result affected our decision if test closed then M if testdiffuse then do not drill CS 1571 Intro to AI M Hauskrecht Value of information When the test makes sense Only when its result makes the decision maker to change his mind that is he decides not to drill Value of information 7 Measure of the goodness of the information from the test 7 Difference between the expected value with and without the test information Oil wildcatter example 7 Expected value without the test 18 7 Expected value with the test 254 7 Value of information for the seismic test 74 CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 18 Firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Tictactoe competition Results 1 Richard Matchett 2 Vinay Sarpeshkar 3 Brandon Blatnick 381571 Intro to AI M Hauskrecht Firstorder logic FOL More expressive than propositional logic Eliminates de ciencies of PL by 7 Representing objects their properties relations and statements about them 7 Introducing variables that refer to an arbitrary objects and can be substituted by a specific object 7 Introducing quanti ers allowing us to make statements over groups objects without the need to represent each of them separately CS 1571 Intro to AI M Hauskrecht Logic Logic is de ned by A set of sentences 7 A sentence is constructed from a set of primitives according to syntax rules A set of interpretations 7 An interpretation gives a semantic to primitives It associates primitives with objects values in the real world The valuation meaning function V 7 Assigns a truth value to a given sentence under some interpretation V sentence gtlt interpretation gt True False CS 1571 Intro to AI M Hauskrecht Firstorder logic Syntax Term syntactic entity for representing objects Terms in FOL Constant symbols represent speci c objects 7 Eg John France car89 Variables represent objects of a certain type type domain of discourse 7 Eg x yz Functions applied to one or more terms 7 Egfather ofJohn father of ather of ohn CS 1571 Intro to AI M Hauskrecht First order logic Syntax Sentences in FOL Atomic sentences 7 A predicate symbol applied to 0 or more terms Examples Red car 2 SisterAmy Jane ManagerO ather of ohn 7 t1 t2 equivalence of terms Example John father o Peter CS 1571 Intro to AI M Hauskrecht First order logic Syntax Sentences in FOL Complex sentences Assume 1 are sentences in FOL Then 7 WuI v1 3 w w 39l and Vx 3y are sentences Symbols El V stand for the existential and the universal quanti er CS 1571 Intro to AI M Hauskrecht Semantics Interpretation An interpretation I is de ned by a mapping to the domain of discourse D or relations on D domain of discourse a set of objects in the world we represent and refer to An interpretation I maps Constant symbols to objects in D IJohn Predicate symbols to relations properties on D 1brother gt Function symbols to functional relations on D 1fatherofltgt gt CS 1571 Intro to AI M Hauskrecht Semantics of sentences Meaning evaluation function V sentence gtlt interpretation gt True False A predicate predicateterm 1 term 2 term 3 term n is true for the interpretation I iff the objects referred to by term 1 term 2 term 3 term n are in the relation referred to by predicate 1John 1Paul a WW lt9X a brotherJohn Paul in Ibrother VbrotherJohn Paul I True CS 1571 Intro to AI M Hauskrecht Semantics of sentences Equality Vterm 1 term 2 I True Hf 1term 1 Iterm 2 Boolean expressions standard Eg Vsentence 1 v sentence 2 I True Hf Vsentence 1I True or Vsentence 2I True Quanti cations bstitution of x with d VVx ITrue su Hf for all d e D V IVd True VEx 1True Iff there is a d e D st V IVd True CS 1571 Intro to AI M Hauskrecht Representing knowledge in FOL Ex ample Kinship domain Objects people John Mary Jane Properties gender Male x Female x Relations parenthood brotherhood marriage Parent x y Brother x y Spouse x y Functions motherof one for each person X MotherOf x CS 1571 Intro to AI M Hauskrecht Kinship domain in FOL Relations between predicates and functions write down what we know about them how relate to each other Male and female are disjoint categories Vx Male x lt3 Female x Parent and child relations are inverse Vx y Parent x y Q Child y x A grandparent is a parent of parent Vg c Grandparentg c cgt Elp Parentg p A Parentp c A sibling is another child of one s parents Vx y Sibling x y cgt x at y A Elp Parent p x A Parent p y Andso on CS 1571 Intro to AI M Hauskrecht Inference in First order logic CS 1571 Intro to AI M Hauskrecht Logical inference in FOL Logical inference problem Given a knowledge base KB a set of sentences and a sentence a does the KB semantically entail a KB za In other words In all interpretations in which sentences in the KB are true is also 0 true Logical inference problem in the rst order logic is undecidable 11 No procedure that can decide the entailment for all possible input sentences in a nite number of steps CS 1571 Intro to AI M Hauskrecht Logical inference problem in the Propositional logic Computational procedures that answer KBla Three approaches Truth table approach Inference rules Conversion to the inverse SAT problem 7 Resolution refutation CS 1571 Intro to AI M Hauskrecht Inference in FOL Truth table Is the Truthtable approach a Viable approach for the FOL CS 1571 Intro to AI M Hauskrecht Inference in FOL Truth table approach Is the Truthtable approach a Viable approach for the FOL I N 0 Why It would require us to enumerate and list all possible interpretations I I assignments of symbols to objects predicates to relations and functions to relational mappings Simply there are too many interpretations CS 1571 Intro to AI M Hauskrecht Inference in FOL Inference rules Is the Inference rule approach a Viable approach for the FOL CS 1571 Intro to AI M Hauskrecht Inference in FOL Inference rules Is the Inference rule approach a viable approach for the FOL Yes The inference rules represent sound inference patterns one can apply to sentences in the KB What is derived follows from the KB Caveat we need to add rules for handling quantifiers CS 1571 Intro to AI M Hauskrecht Inference rules Inference rules from the propositional logic 7 Modus ponens A 3 B A B 7 Resolution A v B B v C A v C 7 and others Andintroduction Andelimination Or introduction Negation elimination Additional inference rules are needed for sentences with quantifiers and variables 7 Must involve variable substitutions CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er Vx P x 7 Free 7 if it is not bound 3x 130 Q06 y is free Examples Vx Ely Likes xy Bound or free CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er VJQPWZ 7 Free71f 1t 1s not ound 335 PO yis free Examples Vx Ely Likes xy Bound Vx Likes x y Ely Likes y Raymond Bound or free CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er VJQPWZ 7 Free71f1t1s not ound 3xPyQx yisfree Examples Vx Ely Likes x y Bound Vx Likes x y Ely Likes yRaym0nd Free CS 1571 Intro to AI M Hauskrecht Sentences With variables Firstorder logic sentences can include variables Sentence formula is 7 Closed 7 if it has no free variables Vy x P y 3 Q06 7 Open 7 if it is not closed 3x Py A Qx yis free 7 Ground 7 if it does not have any variables Likes J ohn Jane CS 1571 Intro to AI M Hauskrecht Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTxz y father0fJ0hnLikesxy CS 1571 Intro to AI M Hauskrecht Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTx zy father0fJ0hnLikesxy Likesz fatherof J0hn CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal elimination Vx x a 1s a constant symbol a 7 substitutes a variable with a constant symbol Vx Likesx IceC ream LikesBen IceC ream Existential elimination El x x a 7 Substitutes a variable with a constant symbol that does not appear elsewhere in the KB Elx Kill x Victim Kill Murderer Victim CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal instantiation introduction x 7 is not free in Vx 7 Introduces a universal variable which does not affect or its assumptions SisterAmy Jane Vx S isterAmy Jane Existential instantiation introduction a a7isagr0undtermin Elx x x7is notfree in 7 Substitutes a ground term in the sentence with a variable and an existential statement LikesBen I ceC ream Elx Likesx IceC ream CS 1571 Intro to AI M Hauskrecht Uni cation Problem in inference Universal elimination gives many opportunities for substituting variables with ground terms Vx x a Solution Try substitutions that may help 7 Use substitutions of similar sentences in KB a is a constant symbol Uni cation 7 takes two similar sentences and computes the substitution that makes them look the same if it exists UNIFY pq 039 st SUBST a39p SUBST 039q CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJ0hn x KnowsJ0hn Jane x Jane UNIF Y KnowsJ ohn x Knows y Ann CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yMotherOf y CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yMotherOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yMotherOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth fail CS 1571 Intro to AI M Hauskrecht Generalized inference rules Use substitutions that let us make inferences Example Modus Ponens If there exists a substitution 6 such that SUBST 6 A1 SUBST ox11 for all i12 11 A1 AA2 An 3 B Al39A239An39 S UBST a B Substitution that satis es the generalized inference rule can be build Via uni cation process Advantage of the generalized rules they are focused 7 only substitutions that allow the inferences to proceed CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka l1Vl2 V ln SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PXVQxa 39QJ0hnVSy PJ0hn v Sy CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1VW2VWn SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PxvQx QJ0hnvSy CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 19 Inference in firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference in FOL Logical inference problem Given a knowledge base KB a set of sentences and a sentence a does the KB semantically entail a KB za In other words In all interpretations in which sentences in the KB are true is also 0 true Logical inference problem in the rst order logic is undecidable 11 No procedure that can decide the entailment for all possible input sentences in a nite number of steps 381571 Intro to AI M Hauskrecht Logical inference problem in the Propositional logic Computational procedures that answer KBla Three approaches Truth table approach gtlt Inference rules Conversion to the inverse SAT problem 7 Resolution refutation CS 1571 Intro to AI M Hauskrecht Inference rules Inference rules from the propositional logic 7 Modus ponens A 3 B A B 7 Resolution A v B B v C A v C 7 and others Andintroduction Andelimination Or introduction Negation elimination Additional inference rules are needed for sentences with quanti ers and variables 7 Must involve variable substitutions CS 1571 Intro to AI M Hauskrecht Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTx zy father0fJ0hnLikesxy Likesz fatherof J0hn CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal elimination Vx x a 7 substitutes a variable with a constant symbol Vx Likesx IceC ream LikesBen IceC ream a is a constant symbol Existential elimination El x x a 7 Substitutes a variable with a constant symbol that does not appear elsewhere in the KB Elx Kill x Victim Kill Murderer Victim CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal instantiation introduction qu 7 Introduces a universal variable which does not affect or its assumptions x 7 is not free in SisterAmy Jane Vx S isterAmy Jane Existential instantiation introduction a a 7 is a ground term in Elx x x7is notfree in 7 Substitutes a ground term in the sentence with a variable and an existential statement LikesBen I ceC ream Elx Likesx IceC ream CS 1571 Intro to AI M Hauskrecht Uni cation Problem in inference Universal elimination gives many opportunities for substituting variables with ground terms Vx x a Solution Try substitutions that may help a is a constant symbol 7 Use substitutions of similar sentences in KB Uni cation 7 takes two similar sentences and computes the substitution that makes them look the same if it exists UNIFY pq 039 st SUBST a39p SUBST 039q CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yMotherOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth fail CS 1571 Intro to AI M Hauskrecht Generalized inference rules Use substitutions that let us make inferences Example Modus Ponens If there exists a substitution 6 such that SUBST 6 A1 SUBST ox11 for all i12 11 A1 AA2 An 3 B Al39A239An39 S UBST a B Substitution that satis es the generalized inference rule can be build Via uni cation process Advantage of the generalized rules they are focused 7 only substitutions that allow the inferences to proceed CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1VW2VWn SUBSTU IVV HV i1v kvylvv1j1v1j1ln Example PxvQx QJ0hnvSy CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1VW2VWn SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PXVQxa 39QJ0hnVSy PJ0hn v Sy CS 1571 Intro to AI M Hauskrecht Inference with resolution rule Proof by refutation 7 Prove that KB a is unsatis able 7 resolution is refutation complete Main procedure steps 1 Convert KB I a to CNF with ground terms and universal variables only 2 Apply repeatedly the resolution rule while keeping track and consistency of substitutions 3 Stop when empty set contradiction is derived or no more new resolvents conclusions follow CS 1571 Intro to AI M Hauskrecht Conversion to CNF 1 Eliminate implications equivalences 1v3 q gt pvq 2 Move negations inside DeMorgan s Laws double negation pAq gt pv q pr x p pvq gt p q axper p 3 Standardize variables rename duplicate variables Vx Px V 3x Qx gt Vx Px V 3y Q00 4 Move all quantifiers left no invalid capture possible Vx Px V 3y Qy gt Vx 3y Px V Qy CS 1571 Intro to AI M Hauskrecht Conversion to CNF 5 Skolemization removal of existential quanti ers through elimination If no universal quanti er occurs before the existential quanti er replace the variable with a new constant symbol 3yPAV Qy gt PAV QB If a universal quanti er precede the existential quanti er replace the variable with a function of the universal variable Vx Ely Px v Qy gt Vx Pxv QFx F x a special function called Skolem function CS 1571 Intro to AI M Hauskrecht Conversion to CNF 6 Drop universal quanti ers all variables are universally quanti ed Vx PxV QFx gt PxV QFx 7 Convert to CNF using the distributive laws pvqAr gt pvqpvr The result is a CNF with variables constants functions CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 39RZV SZ SA CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 RZV SZ SA yw Pw v Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 4WVQWamp QWMHWH vRWL M VsQLM yw 39PWV Sw xw Sw v Rw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il WVQWamp QUMHWH vRWL MDVsQLM yw 39PWV Sw xw Zw Sw v Rw Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV 30 PxV R06 39RZV 32 SA yw 39PWV SW xw zw Sw v Rw SW wA Contradiction Z CS 1571 Intro to AI M Hauskrecht Dealing with equality Resolution works for firstorder logic without equalities To incorporate equalities we need an additional inference rule Demodulation rule 6 UNIFY it1 fail 1V 2V ka l 121 2 SUBSTSUBSTUtlSUBSTUt2 1vv 1v i1v k Example Pow fx x 130 Paramodulation rule more powerful 0 39 illal quot giveal 39 I proof theory for FOL CS 1571 Intro to AI M Hauskrecht Sentences in Horn normal form Horn normal form HNF in the propositional logic 7 a special type of clause with at most one positive literal Av B Av CVD Typically written as B 3 A A C 3 D A clause with one literal eg A is also called a fact A clause representing an implication with a conjunction of positive literals in antecedent and one positive literal in consequent is also called a rule Generalized Modus ponens 7 is the complete inference rule for KBs in the Horn normal form Not all KBs are convertible to HNF ll CS 1571 Intro to AI M Hauskrecht Horn normal form in FOL First order logic FOL 7 adds variables and quanti ers works with terms Generalized modus ponens rule a a substitution st Vi SUBSTU SUBSTU i 1 2 1A 2Am n31 SUBSTUT v 5quot Generalized modus ponens is complete for the KBs with sentences in Horn form Not all rstorder logic sentences can be expressed in this orm CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Typical usage If we want to infer all sentences entailed by the existing KB Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Typical usage If we want to prove that the target goal sentence a is entailed by the existing KB Both procedures are complete for KBs in Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules KB R1 Steamboat x Sailboat y 3 Faster x y R R F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow N Sailboat y RowBoat z 3 Faster y 2 LA Faster x y AFaster y z 3 Faster x z Theorem Faster Titanic Poncb4rrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x A Sailboat y 3 Faster x y R21 Sailboat y A RowBoat z 3 Faster y 2 R3 FasterxyAFasteryz3 Faster xz F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x A Sailboat y 3 Faster x y R2 Sailboat y A RowBoat z 3 Faster y 2 R3 FasterxyAFasteryz3 Faster xz F1 Steamboat T itanie F2 Sailboat Mistral F3 RowBoatPonaL4rrow Rule R1 is satis ed F4 F asterT itanie Mistral CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x Sailboat y 3 Faster x y R21 Sailboat y ARowBoat z 3 Faster y 2 R3 FasterxyFasteryz3 Faster xz F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow CS 1571 Intro to AI M Hauskrecht KB Forward chaining example R11 Steamboat x Sailboat y 3 Faster x y 22 Sailboat y ARowBoat z 3 Faster y z 3 FasterxyFasteryz3 Faster xz F11 Steamboat T itanie F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow Rule R3 is satis ed F6 FasterTitaniePoncl4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the antecedents if part of the rule amp repeat recursively KB R11 Steamboat x Sailboat y 3 Faster x y R2 Sailboat y ARowBoat z 3 Faster y 2 R31 FasterxyFasteryz3 Faster xz F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow Theorem Faster Titanic Pond4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondA rrow F1 Steamboat Titanic R1 F22 Sailboat Mistral F3 RawBoaKPondlrrow SteamboaTitanic SailboatPondArrow X Steamboat x Sailboat y 3 Faster x y Faster Titanic Pon rrow xTitanic yPonal4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondArrow F12 Steamboat Titanic F2 Sailboat Mistral F3 RowBoaKPondArroM SteamboatTitanic SailboatTitanic SailboatPondArrow RWBoatPondArr0w X Sailboat y RowBoat z 3 Faster y 2 F aster Titanic Po rhllrrow y Titanic z Pond4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example F1 Steamboat Titanic F22 Sailboat Mistral F3 RowBoaKPondArroM Faster Titanic PondArrow SteamboatTitanic SailboatTitanic Faste yfondArmM x F astetTitanic y SailboatPondArrow RowBo ti PondArrow R2 R1 SteamboatTitanic Sailb0mMlstral RowBoatPondArrow SailboatMistral CS 1571 Intro to AI M Hauskrecht Backward chaining Faster Titanic PondArrow y must be bound to the same term SteamboatTitanic ailboatTitanic Fame Pond1WD x F asteKTitanic y SailboaKPondArrow RowBoatPondArraw X R1 SteamboatTitanic Sailb0mMlStral R0wBoatPondArraw SailboatMistral CS 1571 Intro to AI M Hauskrecht Backward chaining The search tree ANDOR tree Special search algorithms exits including heuristics A0 A0 F mfer Titanic Pondlrrow SfeLIMbow Titanic ailboatTifanic F aster yP0ndArroMb FasteKTitanig y SailboatP0ndArmw RowBo 7Pondlrmw R SteamboatTm1mc Sailboamm ml Stu110 M mj RowBoafPondArrow CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 19 Planning STRIPS Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Competition results Simulated annealing competition 1 Nathaniel Wetzel 2 David Bradley 3 Francesco DeSensi Extra credit 381571 Intro to AI M Hauskrecht Planning Planning problem nd a sequence of actions that achieves some goal an instance of a search problem the state description is very complex Methods for modeling and solving a planning problem State space search Situation calculus based on FOL 7 Typically Resolution refutation CS 1571 Intro to AI M Hauskrecht Planning problems Properties of real world planning problems The description of the state of the world is very complex Many possible actions to apply in any step Actions are typically local 7 they affect only a small portion of a state description Goals are defined as conditions and refer only to a small portion of state Plans consists of a long sequence of actions The state space search and situation calculus frameworks may be too cumbersome and inefficient to represent and solve planning problems CS 1571 Intro to AI M Hauskrecht Situation calculus problems Frame problem refers to The need to represent a large number of frame axioms Solution combine positive and negative effects in one rule Onu vDO MOVE x y 2 3 ltgt 7u x A v y A Onuvs v v u x A v 2 A Onx ys A Clear xs A Clear 23 Inferential frame problem 7 We still need to derive properties that remain unchanged Other problems Quali cation problem 7 enumeration of all possibilities under which an action holds Rami cation problem 7 enumeration of all inferences that follow from some facts CS 1571 Intro to AI M Hauskrecht Solutions Complex state description and local action effects 7 avoid the enumeration and inference of every state component focus on changes only Many possible actions 7 Apply only actions that make progress towards the goal 7 Understand what the effect of actions is and reason with the consequences Sequences of actions in the plan can be too long 7 Many goals consists of independent or nearly independent subgoals 7 Allow goal decomposition amp divide and conquer strategies CS 1571 Intro to AI M Hauskrecht STRIPS planner De nes a restricted FOL representation language as compared to the situation calculus Advantage leads to more efficient planning algorithms 7 Statespace search with structured representations of states actions and goals 7 Action representation avoids the frame problem STRIPS planning problem much like a standard search problem CS 1571 Intro to AI M Hauskrecht STRIPS planner States 7 conjunction of literals eg OnAB OMB Table ClearA 7 represent facts that are true at a specific point in time Actions operators 7 Action Move xyz 7 Preconditions conjunctions of literals with variables Onxy Clearx Clearz 7 Effects Two lists Add list Onxz Cleary Delete list Onxy Clearz Everything else remains untouched is preserved CS 1571 Intro to AI M Hauskrecht STRIPS planning Operator Move xyz Preconditions Onxy Clearx Clearz Add list Onxz Cleary Delete list Onxy Clearz I I I I I Move BTableC OnBTable add Clear C delete OnATable OnATable OnCTable OnCTable Clear A m Clear A Clear B Clear B Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht STRIPS planning Initial state Conjunction of literals that are true Goals in STRIPS A goal is a partially speci ed state Is defined by a conjunction of ground literals 7 N0 variables allowed in the description of the goal Example OnAB OnBC CS 1571 Intro to AI M Hauskrecht Search in STRIPS Objective Find a sequence of operators a plan from the initial state to the state satisfying the goal Two approaches to build a plan Forward state space search goal progression 7 Start from what is known in the initial state and apply operators in the order they are applied Backward state space search goal regression 7 Start from the description of the goal and identify actions that help to reach the goal CS 1571 Intro to AI M Hauskrecht Forward search goal progression Idea Given a state s 7 Unify the preconditions of some operator at with s 7 Add and delete sentences from the add and delete list of an operator at from s to get a new state mm 9 Move BTableC OnBTable add OnBC Clear C Q OnATable OnATable OnCTable OnCTable gear Egg m gear 831 ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M E goal Move A Table B Move B Table C llIove ATable C lt Initial state CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M H goal Move A Table B Move B Table C Move ATable C Olt Heuristics Initial state CS 1571 Intro to AI M Hauskrecht Backward search goal regression Idea Given a goal G Unify the add list of some operator at with a subset of G If the delete list of a does not remove elements of G then the goal regresses to a new goal G that is obtained from G by 7 deleting add list of a 7 adding preconditions of a E El M0veATableB New goal G Goal G On A Table Clear B precondition vhem1152 Clear A OnBC OquotB C OnCTable 0 CaTable Mapped from G CS 1571 Intro to AI M Hauskrecht Backward search goal regression Use operators to generate new goals Check whether the initial state satis es the goal Search tree 395 5 Initial state Move BTable C Move A Table B goal Move A B Table CS 1571 Intro to AI M Hauskrecht Statespace search Forward and backward state space planning approaches 7 Work with strictly linear sequences of actions m Disadvantages M 7 They cannot take advantage of the problem decompositions in which the goal we want to reach consists of a set of independent or nearly independent sub goals 7 Action sequences cannot be built from the middle 7 No mechanism to represent least commitment in terms of the action ordering CS 1571 Intro to AI M Hauskrecht Divide and conquer Divide and conquer strategy 7 divide the problem to a set of smaller subproblems 7 solve each subproblem independently 7 combine the results to form the solution In planning we would like to satisfy a set of goals Divide and conquer in planning 7 Divide the planning goals along individual goals 7 Solve nd a plan for each of them independently 7 Combine the plan solutions in the resulting plan Is it always safe to use divide and conquer 7 No There can be interacting goals CS 1571 Intro to AI M Hauskrecht Sussman s anomaly An example from the blocks world in which the divide and conquer fails due to interacting goals gt Initial state Goal OnAB OnBC CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst M H q 1339 Initial state But now we cannot satisfy On B C without undoing On A B CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst Initial state But now we cannot satisfy On B C without undoing On A B 2 Assume we want to satisfy 0quot B C rst H quot Initial state But now we cannot satisfy 0quot A B without undoing 0quot B C CS 1571 Intro to AI M Hauskrecht State space vs plan space search An alternative to planning algorithms that search states con gurations of world Plan De nes a sequence of operators to be performed Paltial plan 7 plan that is not complete Some plan steps are missing 7 some orderings of operators are not nalized Only relative order is given Bene ts of working with partial plans 7 We do not have to build the sequence from the initial state or the goal 7 We do not have to commit to a speci c action sequence 7 We can work on subgoals individually divide and conquer CS 1571 Intro to AI M Hauskrecht Statespace vs planspace search State space search STRIPS operator State set of formulas Plan space search Finish Plan transformation Start Incomplete partial plan CS 1571 Intro to AI M Hauskrecht Plan transformation operators Examples of Add an operator to a plan Mov eAxB start goal so that it satis es some open condition Add link instantiate t rt M0V9AHBf l s a goa oveCA amp Order reorder operators l CS 1571 Intro to AI M Hauskrecht Partialorder planners POP also called Non linear planners Use STRIPS operators Graphical representation of an operator Movexyz add list preconditions Delete list is not shown ll Illustration of a POP on the Sussman s anomaly case CS 1571 Intro to AI M Hauskrecht Partial order planning Start and finish Goal I Start M Hauskrecht CS 1571 Intro to AI Partial order planning Start and finish Goal Open conditions conditions yet to be satis ed m Start M H M Hauskrecht CS 1571 Intro to AI Partial order planning Add operator El Goal We want to satisfy an open Movemy condition OnAy Always select an operator that helps to satisfy one of the open conditions H Start 5 M Hauskrecht CS 1571 Intro to AI Partial order planning Add link El Goal I Start ME CS 1571 Intro to AI M Hauskrecht Partial order planning Add link El Goal Add link Satis es an open condition H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add link Goal Satis es an open condition instantiates y F1 Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links El Start 1 5 CS 1571 Intro to AI M Hauskrecht Deletes ClearB A was stacked on B t a sum I l CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators El MoveBFlC comes before MoveAFlB Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El MoveBF1C F t H w Stan 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links A I E MoveBFlC 0110351 CleaIC II I C m I I CS 1571 Intro to AI M Hauskrecht Partial order planning Threats El A Cl earC CleaIFl El a w Start I I CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators MoveBF1C OnBF1 CS 1571 Intro to AI M Hauskrecht 1 w CS 1571 Intro to AI M Hauskrecht MoveBF1C OnBFl CS 1571 Intro to AI M Hauskrecht Partial order planning Result plan Plan a topological son of a graph CS 1571 Intro to AI M Hauskrecht Partial order planning Remember we search the space of partial plans Start Incomplete partial plan POP is sound and complete CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 16 Propositional logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference problem Logical inference problem Given 7 a knowledge base KB a set of sentences and 7 a sentence 05 called a theorem Does a KB semantically entail a KB a In other words In all interpretations in which sentences in the KB are true is also at true Approaches Truth table approach Inference rules Conversion to SAT 7 Resolution refutation 381571 Intro to AI M Hauskrecht Truthtable approach Problem KB i 0 We need to check all possible interpretations for which the KB is true models of KB whether a is true for each of them Truth tables enumerate truth values of sentences for all possible interpretations assignments of True False to propositional symbols and check Example In H c P V Q Q True V CS 1571 Intro to AI M Hauskrecht Inference rules approach Motivation we do not want to blindly generate and check all interpretations 1 Inference rules Represent sound inference patterns repeated in inferences Application of many inference rules allows us to infer new sound conclusions and hence prove theorems An example of an inference rule Modus ponens A 3 B A 4 premise B conclusion CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 1 P Q 2 P 3 R 3 Q A R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 139 P A Q Nondeterministic ste s 2 P 3 R 3 Q R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens I Proved S I CS 1571 Intro to AI M Hauskrecht Logic inferences and search Inference rule method as a search problem State a set of sentences that are known to be true Initial state a set of sentences in the KB Operators applications of inference rules 7 Allow us to add new sound sentences to old ones Goal state atheorem a is derived from KB Logic inference Proof A sequence of sentences that are immediate consequences of applied inference rules Theorem proving process of nding a proof of theorem CS 1571 Intro to AI M Hauskrecht Satisfiability SAT problem Determine whether a sentence in the conjunctive normal form CNF is satis able Ie can evaluate to true PVQv R Pv RVS Pva T It is an instance of a constraint satisfaction problem Variables 7 Propositional symbols P R T S 7 Values True False Constraints 7 Every conjunct must evaluate to true at least one of the literals must evaluate to true All techniques developed for CSPs can be applied to solve the logical inference problem Why CS 1571 Intro to AI M Hauskrecht Inference problem and satisfiability Inference problem we want to show that the sentence 0 is entailed by KB Satisfiability The sentence is satisfiable if there is some assignment interpretation under which the sentence evaluates to true ConneCtiOIU KB i a if and only if KB a is unsatis able Consequences inference problem is NPcomplete programs for solving the SAT problem can be used to solve the inference problem Simulatedannealing WALKSAT CS 1571 Intro to AI M Hauskrecht Satisfiability SAT problem Determine whether a sentence in the conjunctive normal form CNF is satisfiable ie can evaluate to true PVQv R Pv RVS Pva T It is an instance of a constraint satisfaction problem Variables 7 Propositional symbols P R T S 7 Values True False Constraints 7 Every conjunct must evaluate to true at least one of the literals must evaluate to true Why is this important All techniques developed for CSPs can be applied to solve the logical inference problem CS 1571 Intro to AI M Hauskrecht Resolution algorithm Algorithm 1 Convert KB to the CNF form 2 Apply iteratively the resolution rule starting from KB a in the CNF form 3 Stop when 7 Contradiction empty clause is reached A I A Q proves the entailment 7 No more new sentences can be derived Rejects disproves the entailment CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S Step 1 convert KB to CNF PAQ gt PAQ o P3R gt PVR QARS gt Qv RVS KB P Q Pv R QV RvS Step 2 Negate the theorem to prove it Via refutation S gt IS Step 3 Run resolution on the set of clauses P Q PVR Qv RVS uS CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S P Q PvR QV RVs S A RVS R Contradiction gt CS 1571 Intro to AI M Hauskrecht KB in restricted forms If the sentences in the KB are restricted to some special forms other sound inference rules may become complete Example Horn form Horn normal form Av B Av C VD Canbe written also as B 3 AAC3 D Modus ponens 7 is the universal complete rule for the sentences in the Homform A33 A AIAAZAAkDBA1A2Ak B B CS 1571 Intro to AI M Hauskrecht KB in Horn form Horn form a clause with at most one positive literal Av B Av C VD Not all sentences in propositional logic can be converted into the Horn form KB in Horn normal form 7 Two types of propositional statements Implications called rules B 3 A Propositional symbols facts B Application of the modus ponens 7 Infers new facts from previous facts A 3 B A B CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satisfied Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Both procedures are complete for KBs in the Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules and facts KB Rl A B 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Theorem E MHauskrecht CS 1571 Intro to AI Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G F1 A F2 B F3 D Rule R1 is satis ed F4 C CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Rule R1 is satis ed F4 C Rule R2 is satis ed F5 E CS 1571 Intro to AI M Hauskrecht Backward chaining example E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G R2 D Fl A 3 F2 B F3 D Backward chaining is more focused 7 tries to prove the theorem only CS 1571 Intro to AI M Hauskrecht Backward chaining example E R1 D A B Backward chaining is more focused 7 tries to prove the theorem only KB R1 AABSC CAFSG CS 1571 Intro to AI M Hauskrecht KB agents based on propositional logic Propositional logic allows us to build knowledge based agents capable of answering queries about the world by infering new facts from the known ones Example an agent for diagnosis of a bacterial disease Facts The stain of the organism is grampositive The growth conformation of the organism is chains Rules If Then The stain of the organism is grampositive The morphology of the organism is coccus The growth conformation of the organism is chains 3 The identity of the organism is streptococcus CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 26 Decision making in the presence of uncertainty Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Selection based on expected values Until now The optimal action choice was the option that maximized the expected monetary value But is the expected monetary value always the quantity we want to optimize 381571 Intro to AI M Hauskrecht Selection based on expected values Is the expected monetary value always the quantity we want to optimize Answer Yes but only if we are riskneutral But what if we do not like the risk we are risk averse In that case we may want to get the premium for undertaking the risk of loosing the money Example 7 we may prefer to get 101 for sure against 102 in expectation but with the risk of loosing the money Problem How to model decisions and account for the risk Solution use utility function and utility theory CS 1571 Intro to AI M Hauskrecht Utility function Utility function denoted U 7 Quanti es how we value outcomes ie it re ects our preferences 7 Can be also applied to value outcomes other than money and gains eg utility of a patient being healthy or ill Decision making 7 uses expected utilities denoted EU EUX ZPX xUX x XEQX UX x the utility of outcome x Important 1 Under some conditions on preferences we can always design the utility function that ts our preferences CS 1571 Intro to AI M Hauskrecht Utility theory De nes axioms on preferences that involve uncertainty and ways to manipulate them Uncertainty is modeled through lotteries 7 Lottery P1A1PIC Outcome A with probability p Outcome C with probability lp The following six constraints are known as the axioms of utility theory The axioms are the most obvious semantic constraints on preferences with lotteries Notation gt preferable N indifferent equally preferable CS 1571 Intro to AI M Hauskrecht Axioms 0f the utility theory Orderability Given any two states the a rational agent prefers one of them else the two as equally preferable Agt BVBgt AVAB Transitivity Given any three states if an agent prefers A to B and prefers B to C agent must preferA to C AgtBBgtC3Agt C Continuity If some state B is betweenA and C in preference then there is a p for which the rational agent will be indifferent between state B and the lottery in which A comes with probability p C with probability lp Agt Bgt C3EIppAl pCB CS 1571 Intro to AI M Hauskrecht Axioms of the utility theory Substitutability If an agent is indifferent between two lotteries A and B then there is a more complex lottery in which A can be substituted with B AMB3P1A1PICNPIB1PIC Monotonicity If an agent prefers A to B then the agent must prefer the lottery in which A occurs with a higher probability AgtB3Pgtq 171A1PIBgtq1A1qIB Decomposability Compound lotteries can be reduced to simpler lotteries using the laws of probability 1vrA117qB161C3 prA1pqB1p1qrC CS 1571 Intro to AI M Hauskrecht Utility theory If the agent obeys the axioms of the utility theory then 1 there exists a real valued function U such that UAgtUB Agt B UAUBlt3AB 2 The utility of the lottery is the expected utility that is the sum of utilities of outcomes weighted by their probability Up A1 p B pUA1 pUB 3 Rational agent makes the decisions in the presence of uncertainty by maximizing its expected utility CS 1571 Intro to AI M Hauskrecht Utility functions We can design a utility function that ts our preferences if they satisfy the axioms of utility theory But how to design the utility function for monetary values so that they incorporate the risk What is the relation between utility function and monetary values Assume we loose or gain 1000 7 Typically this difference is more signi cant for lower values around 100 1000 than for higher values N 1000000 What is the relation between utilities and monetary value for a typical person CS 1571 Intro to AI M Hauskrecht Utility functions What is the relation between utilities and monetary value for a typical person Concave function that attens at higher monetary values utility 100000 Monetary value CS 1571 Intro to AI M Hauskrecht Utility functions Expected utility of a sure outcome of 750 is 750 EUsure 750 Ux utility 500 750 1000 Monetaryvalue CS 1571 Intro to AI M Hauskrecht Utility functions Assume a lottery L 05 500 051000 Expected value of the lottery 750 Expected utility of the lottery EUL is different 7 EUL 05U500 05U1000 Ux EU line for lotteries utility EUlotter L with outcomes 500 and 1000 Lottery L 05 500 051000 I 500 750 1000 Monetary value CS 1571 Intro to AI M Hauskrecht Utility functions Expected utility of the lottery EUlottery L lt EUsure 750 UX utility Lottery L 05 500 051000 500 750 1000 Monetary value Risk aversion 7 a bonus is required for undertaking the risk CS 1571 Intro to AI M Hauskrecht Decision making with utility function Original problem with monetary outcomes CS 1571 Intro to AI M Hauskrecht Decision making with the utility function Utility function log K 200653 0 20413 19542 21461 19030 20043 10 39 20000 381571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 26b Learning Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Machine Learning The eld of machine learning studies the design of computer programs agents capable of learning from past experience or adapting to changes in the environment The need for building agents capable of learning is everywhere 7 Predictions in medicine text classification speech recognition imagetext retrieval commercial software Machine learning is not only the deduction but induction of rules from examples that facilitate prediction and decision making CS 1571 Intro to AI M Hauskrecht Learning Learning process Learner a computer program takes data D representing past experiences and tries to either 7 to develop an appropriate response to future data or 7 describe in some meaningful way the data seen Example Learner sees a set of past patient cases patient records with corresponding diagnoses It can either try 7 to predict the presence of a disease for future patients 7 describe the dependencies between diseases symptoms e g builds a Bayesian network for them CS 1571 Intro to AI M Hauskrecht Types of learning Supervised learning 7 Learning mapping between inputs X and desired outputs y 7 Teacher gives me y s for the learning purposes Unsupervised learning 7 Learning relations between data components 7 No speci c outputs given by ateacher Reinforcement learning 7 Learning mapping between inputs X and desired outputs y 7 Critic does not give me y s but instead a signal reinforcement of how good my answer was Other types of learning 7 Concept learning explanation based learning etc CS 1571 Intro to AI M Hauskrecht Supervised learning Data D d1 d2 dn a set ofn examples dz lt xwyl gt X is input vector and y is desired output given by a teacher Objective learn the mapping f I X gt Y st yl m fxl for all i1 71 Two types of problems Regression X discrete or continuous Y is continuous Classi cation X discrete or continuous gt Y is discrete CS 1571 Intro to AI M Hauskrecht Supervised learning examples 0 Regression Yis continuous Debt equity Earnings 39 company stock price Future product orders 0 Classi cation Y is discrete r MNNI I t imam L 77 m Label 3 at an amth Handwritten digit array of 01s CS 1571 Intro to AI M Hauskrecht Unsupervised learning 0 Data D 11 d2dn 11 X vector of values No target value output y 0 Objective 7 learn relations between samples components of samples Types of problems 0 Clustering Group together similar examples e g patient cases 0 Density estimation 7 Model probabilistically the population of samples e g relations between the diseases symptoms lab tests etc CS 1571 Intro to AI M Hauskrecht Unsupervised learning example Density estimation We want to build the probability model of a population from which we draw samples d1 x1 t e T 25 w a Y 3 Mr 2 U J e U a ra r F g k 15 aw 3M a an w w i 3 Ik l r y r a 4 r k n Y 05 amp r r n a quot 439 w a r i 3 quot339 l3 2 3XW n t f t 5 E e KM u ig o wk 439 F 33 US gquot H Y W ii 2 45 1 HE n ma 1 15 2 CS 1571 Intro to AI M Hauskrecht Unsupervised learning Density estimation A probability density of a point in the two dimensional space Model used here Mixture of Gaussians CS 1571 Intro to AI M Hauskrecht Reinforcement learning We wantto learn fIX Y We see samples ofx but noty Instead of y we get a feedback reinforcement from a critic about how good our output was input sample A output reinforcement The goal is to select output that leads to the best reinforcement CS 1571 Intro to AI M Hauskrecht Typical learning Assume we have an access to the dataset D past data Three basic steps Select a model with parameters Select the error function to be optimized 7 Re ects the goodness of t of the model to the data Find the set of parameters optimizing the error function 7 The model and parameters with the smallest error represent the best t of the model to the data CS 1571 Intro to AI M Hauskrecht Learning Assume we see examples of pairs x y and we want to learn the mapping f I X Y to predict future ys for values of x CS 1571 Intro to AI M Hauskrecht Learning bias Problem many possible functions f I X gt Y exists for representing the mapping between x and y We choose a class offunctions Say we choose a linear function fx ax b CS 1571 Intro to AI M Hauskrecht Learning Choosing a parametric model or a set of models is not enough Still too many functions f x ax b 7 One for every pair of parameters a b CS 1571 Intro to AI M Hauskrecht Learning Optimize the model using some criteria that re ects the t of the model to data Example mean squared error yl fog 2 7 21 CS 1571 Intro to AI M Hauskrecht Typical learning Assume we have an access to the dataset D past data Three basic steps Select a model with parameters f x ax b Select the error function to be optimized 7 Re ects the goodness of t of the model to the data e fx2 Find the set of parameters optimizing the error function 7 The model and parameters with the smallest error represent the best t of the model to the data CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 18 Planning situation calculus Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Automated reasoning systems Examples and main differences Theorem provers 7 Prove sentences in the firstorder logic Use inference rules resolution rule and resolution refutation Deductive retrieval systems 7 Systems based on rules KBs in Horn form 7 Prove theorems or infer new assertions forward backward chaining Production systems 7 Systems based on rules with actions in antecedents 7 Forward chaining mode of operation Semantic networks 7 Graphical representation of the world objects are nodes in the graphs relations are various links 381571 Intro to AI M Hauskrecht Semantic network systems Knowledge about the world described in terms of graphs Nodes correspond to 7 Concepts or objects in the domain Links to relations Three kinds 7 subset links 0521 pan OfIinks Inheritance relation links 7 Member links instance links 7 Function links Can be transformed to the rstorder logic language Graphical representation is often easier to work with 7 better overall View on individual concepts and relations CS 1571 Intro to AI M Hauskrecht Semantic network Example Trans ortson EI isa isa Ocean liner Oil tanker Engine 9 9 1513M member member is39pan Swimming Queen Boiler pool Mary Inferred properties Queen Mary is a ship Queen Mary has a boiler Exxon Valdez CS 1571 Intro to AI M Hauskrecht Planning situation calculus CS 1571 Intro to AI M Hauskrecht Representation of actions situations events The world is dynamic What is true now may not be true tomorrow Changes in the world may be triggered by our activities Problems 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 nd a sequence of actions that achieves some goal in this complex world A very complex search problem CS 1571 Intro to AI M Hauskrecht Situation calculus Provides a framework for representing change actions and for reasoning about them Situation calculus 7 based on the rstorder logic 7 a situation variable models new states of the world 7 action objects model activities 7 uses inference methods developed for FOL to do the reasoning CS 1571 Intro to AI M Hauskrecht Situation calculus Logic for reasoning about changes in the state of the world The world is described by 7 Sequences of situations of the current state 7 Changes from one situation to another are caused by actions The situation calculus allows us to 7 Describe the initial state and a goal state 7 Build the KB that describes the effect of actions operators 7 Prove that the KB and the initial state lead to a goal state extracts a plan as sideeffect of the proof CS 1571 Intro to AI M Hauskrecht Situation calculus The language is based on the First order logic plus Special variables 361 7 objects of type situation and action Action functions return actions 7 Eg MoveA TABLE B represents a move action 7 M ovex yz represents an action schema Two special function symbols of type situation 7 s0 7 initial situation 7 DOas 7 denotes the situation obtained after performing an action a in situation s Situation dependent functions and relations also called uents 7 Relation Onxys 7 object X is on object y in situation s 7 Function AboveXs 7 object that is above X in situation s CS 1571 Intro to AI M Hauskrecht Situation calculus Blocks world example I I I Initial state OnA Table SD OMB Table so OnC Table so ClearA SD ClearB so ClearC so ClearTable SD Goal Find a state situation 5 such that OnAB s OMB C s OnC Table s CS 1571 Intro to AI M Hauskrecht Blocks world example I I I Initial state OnA Table so OMB Table SD OnC Table so ClearA so ClearB SD ClearC so ClearTable so Goal OnAB s OnBC s OnC Table s Note It is not necessary that the goal describes all relations ClearA s CS 1571 Intro to AI M Hauskrecht Blocks world example Assume a simpler goal OnAB s I I I Initial state OnA Table SD OMB Table so OnC Table so ClearA SD ClearB so ClearC so ClearTable SD 3 possible goal con gurations I I Goal OnAB s CS 1571 Intro to AI M Hauskrecht Knowledge base Axioms Knowledge base needed to support the reasoning Must represent changes in the world due to actions Two types of axioms Effect axioms 7 changes in situations that result from actions Frame axioms 7 things preserved from the previous situation CS 1571 Intro to AI M Hauskrecht Blocks world example Effect axioms Effect axioms Moving x from y to 2 MOVE x y 2 Effect of move changes on On relations Onx y 3 A Clear x 3 A Clear 2 3 Onx ZDO MOVE x y 2 3 Onx y 3 A Clear x 3 A Clear 2 3 On x y DO MOVE x y 2 3 Effect of move changes on Clear relations Onx y 3 A Clear x 3 A Clear 2 3 a Clear y DO MOVE x y 2 3 On x y 3 A Clear x 3 A Clear 2 3 A Z i Table Clear ZDO MOVE x y 2 3 CS 1571 Intro to AI M Hauskrecht Blocks world example Frame axioms Frame axioms 7 Represent things that remain unchanged after an action On relations OnuvsA u i xA v i y OnuvDOMOVE x yzs Clear relations Clear us A u i Z a Clear uDO MOVE x y 2 3 CS 1571 Intro to AI M Hauskrecht Planning in situation calculus Planning problem nd a sequence of actions that lead to a goal Planning in situation calculus is converted to the theorem proving problem Goal state HS OnABs A OnBCs A OnCTable 3 Possible inference approaches 7 Inference rule approach 7 Conversion to SAT Plan solution is a byproduct of theorem proving Example blocks world CS 1571 Intro to AI M Hauskrecht Planning in a blocks world I I I Initial state Goal OnA Table so OnAB s OMB Table SD OMB C s OnCTable so OnC Table s ClearA so ClearB SD ClearC so ClearTable so CS 1571 Intro to AI M Hauskrecht Planning in the blocks world M Initial state 90 so On ATable so Clear A so Clear Table so OnBTableso Clear 330 OnCTablesO Clear C so Action MOVEBTableC sl DOMOVE BTableCsO OnATablesl OnBC s1 C A 51 Clear Table sl OnBTablesl Cam951 OnCTable s1 nClear C 5 SI CS 1571 Intro to AI M Hauskrecht Planning in the blocks worl I I I Q Initial state s0 s1 s2 s1 DO MOVE BTableC so 3 S1 Clear A S1 Clear Table sl OnBTablesl Clear 331 OnCTable sl Clear Csl Action MOVE ATable B 52 DOMOVE ATableB s1 DO MOVE ATable BDOMOVE BTable C 50 OnABsZ OnATablesz Clear 332 0710390952 O BTabl 3552 ClearCsz O CTable 52 Clear 1452 Clear Table sz CS 1571 Intro to AI M Hauskrecht Planning in situation calculus Planning problem Find a sequence of actions that lead to a goal Is a special type ofa search problem Planning in situation calculus is converted to theorem proving Problems 7 Large search space 7 Large number of axioms to be de ned for one action 7 Proof may not lead to the best shortest plan CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 10 Finding optimal configurations combinatorial optimization Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Constraint satisfaction problem CSP Constraint satisfaction problem CSP is a configuration search problem where A state is de ned by a set of variables Goal condition is represented by a set constraints on possible variable values Special properties of the CSP allow more speci c procedures to be designed and applied for solving them 381571 Intro to AI M Hauskrecht Example of a CSP N queens Goal n queens placed in nonattacking positions on the board Variables Represent queens one for each column 7 Q15Q25Q35Q4 0 Values 7 Row placement of each queen on the board Q1 21Q2 4 1 2 3 4 C0DStFaintS Q 3 Q J Two queens not in the same row i Qi Q i i i i Two queens not on the same diagonal CS 1571 Intro to AI M Hauskrecht Solving a CSP problem Initial state No variable is assigned a value 0 Operators Assign a value to one of the unassigned variables Goal condition All variables are assigned no constraints are violated Unassigned Q Q2 Q3 7 Q Assigned UnassignedQ2 Q3 Q4 UnassignedQ2 Q3 Q4 Assigned Q1 1 AssignedQ 2 Unassigned ngQA Ega AssignedQi 2v Q2 4 n n CS 1571 Intro to AI M Hauskrecht Solving a CSP problem Search strateg Unassigied QthQsQ 11 Assi ed 7 Unassigied Q2 ngQ Assi ed Q11 o 0 cs 1571 Intrntn AI M quskrechl Solving a CSP problem Search strateg DFS Constraints may be violated earlier Unassxgied QthstyQt Assi ed Unassigied Q2 Q Q Assi ed Q1 2 Unassigied ngQ Assi ed Q1 2sz 7quot Unassigqed Q QOsts 1 Assi ed 1 u cs 1571 Intrntn AI M quskrechl Solving a CSP problem Search strateg DFS Constraints may be violated earlier 7 constraint propagation infers valid and invalid assignments Unassigied QthQhQL 11 Assi ed 7 Unassigied Q2 ngQ Assi ed Q11 o 0 cs 1571 Intrntn AI M quskrechl Constraint propagation Three known techniques for propagating the effects of past assignments and constraints Value propagation Arc consistency Forward checking Difference 7 Completeness of inferences 7 Time complexity of inferences cs 1571 Intrn In AI M quskrechl Solving a CSP problem Search strategy DFS Constraint propagation infers valid and invalid assignments What candidate to expand first in the DFS UnassignedQ2 3 Q3 3 Q4 Assi ned Q1 1 Unassigned Q33Q4 AssignedEQ1 2yQ2 4 cs 1571 Intro to AI Heuristics for CSP Examples map coloring Heu ristics Most constrained variable c RED 7 Country E is the most constrained one cannot use Red Green M Hauskrecht Least constraining value 7 Assume we have chosen variable C 7 Red is the least constraining valid color for the future cs 1571 Intro to AI M Hauskrecht Search for the optimal configuration Objective find the optimal con guration Optimality De ned by some quality measure Quality measure re ects our preference towards each con guration or state CS 1571 Intro to AI M Hauskrecht Example Traveling salesman problem Problem A graph with distances Goal find the shortest tour which Visits every city once and returns to the start An example of a valid tour ABCDEF CS 1571 Intro to AI M Hauskrecht Example N queens A CSP problem can be converted to the optimal con guration problem The quality of a con guration in a CSP the number of constraints violated Solving minimize the number of constraint violations of violations 3 of violations 1 of violations 0 CS 1571 Intro to AI M Hauskrecht Iterative optimization methods Searching systematically for the best configuration with the DFS may not be the best solution Worst case running time Exponential in the number of variables Solutions to large optimal con guration problems are often found using iterative optimization methods Methods Hill climbing Simulated Annealing Genetic algorithms CS 1571 Intro to AI M Hauskrecht Iterative optimization methods Properti s 7 Search the space of complete con gurations 7 Take advantage of local moves Operators make local changes to complete con gurations 7 Keep track of just one state the current state no memory of past states H No search tree is necessary cs 1571 lnlrn In All M quskrecht Example N queens Local operators for generating the next state 7 Select a variable a queen 7 Reallocate its position cs 1571 lnlrn In All M quskrecht Example Traveling salesman problem Local operator for generating the next state divide the existing tour into two parts reconnect the two parts in the opposite order Example ABCDEF B ABCD EF Part 2 I ABCDFE CS 1571 Intro to Al M Hauskrecht Example Traveling salesman problem Local operator 7 generates the next configuration state CS 1571 Intro to AIC M Hauskrecht Searching the configuration space Search algorithms keep only one con guration the current con guration Problem How to decide about which operator to apply CS 1571 Intro to AI M Hauskrecht Search algorithms Two strategies to choose the con guration state to be Visited next 7 Hill climbing 7 Simulated annealing Later Extensions to multiple current states 7 Genetic algorithms Note Maximization is inverse of the minimization min fXcgt max fX CS 1571 Intro to AI M Hauskrecht Hill climbing I one with the best Value m e mm to maximize the Betta Wmse as 1571 mm Al M HauskrscM Hill climbing Always choose the next best successor state stop when no improvement possible mum Momma WW a sumquot the no proIvum t none HnunH Mmmonzt leALVSYAIEImevom h Inn In mt a mghmmhnd ht em ormnw il stuzhmn s VALUELLHHCHH Ilmn v townHm nd tumer as 1571 mm Al M HauskrscM I Hill climbing Look around at states in the local neighborhood and choose the one with the best value value Better Worse states What can go wrong CS 1571 Intro to Al M Hauskrecht Hill climbing Hill climbing can get trapped in the local optimum No more value local improvement Better states What can go wrong CS 1571 Intro to AI M Hauskrecht Hill climbing Hill climbing can get clueless on plateaus value plateau states CS 1571 Intro to Al M Hauskrecht Hill climbing and nqueens The quality of a con guration is given by the number of constraints violated Then Hill climbing reduces the number of constraints Mincon ict strategy heuristic 7 Choose randomly a variable With con icts 7 Choose its value such that it violates the fewest constraints Success But not always The local optima problem CS 1571 Intro to Al M Hauskrecht Simulated annealing Permits bad moves to states with lower value thus escape the local optima Gradually decreases the frequency of such moves and their size parameter controlling it 7 temperature value Always up Sometimes down states CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm The probability of making a move The probability of moving into a state with a higher value is 1 The probability of moving into a state with a lower value is pAccept NEXT 6 where AE ENEXT ECURRENT 7 The probability is Proportional to the energy difference CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Current con guration Energy E 145 Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm AE ENEXT ECURREMquot 145 7167 22 AET ZZT e e A 1 Current con guration P 91 E E 145 nergy Sometimes accept Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Energy E 145 Current con guration AEEMXT ECURREM 1807167 gt 0 pAccept 1 Energy E 167 Energy E 180 Always accept Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm The probability of moving into a state with a lower value is pAccept 6 Where AE ENEXT ECURRENT The probability is 7 Modulated through a temperature parameter T for T gt 00 the probability of any move approaches 1 for T gt 0 the probability that a state with smaller value is selected goes down and approaches 0 Cooling schedule 7 Schedule of changes of a parameter T over iteration steps CS 1571 Intro to AI M Hauskrecht Simulated annealing LAIED7 pm nhlm i lunclinnSlMU aummalpmmm MumMIMI as soliilieosme wame LIL tl39UI 1mnplxlllghnwllmem lamlmmhllc mm to on um Me 139 n icomemlme mulling lhe malailnliuv a lmmimld slcus HNL NH lmexsoun lNlYlALSYAYEIpmHem ll tor m l lo m do 1 Lwrl39n do n elm iiecessei ul comm izluurtl 7 VALUEh39tllrur39ll ilAE v n llILn Cunarer elm limite nm oulyi minimum ES1571MmloAl M Halsme Simulated annealing algorithm Simulated annealing algorithm 7 developed originally for modeling physical processes Metropolis et a1 53 Prop erties 7 Ii T is decreased slowly enough the best conliguration state is always reached Applications 7 VLSI design 7 airline scheduling ES1571MmloAl M Halsme Simulated evolution and genetic algorithms Limitations of simulated annealing 7 Pursues one state con guration at the time 7 Changes to con gurations are typically local Can we do better Assume we have two con gurations with good values that are quite different We expect that the combination of the two individual con gurations may lead to a con guration with higher value Not guaranteed M This is the idea behind genetic algorithms in which we grow a population of individual combinations CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 16 Propositional logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference problem Logical inference problem Given 7 a knowledge base KB a set of sentences and 7 a sentence 05 called a theorem Does a KB semantically entail a KB a In other words In all interpretations in which sentences in the KB are true is also at true Approaches Truth table approach Inference rules Conversion to SAT 7 Resolution refutation 381571 Intro to AI M Hauskrecht Truthtable approach Problem KB i 0 We need to check all possible interpretations for which the KB is true models of KB whether a is true for each of them Truth tables enumerate truth values of sentences for all possible interpretations assignments of True False to propositional symbols and check Example In H c P V Q Q True V CS 1571 Intro to AI M Hauskrecht Inference rules approach Motivation we do not want to blindly generate and check all interpretations 1 Inference rules Represent sound inference patterns repeated in inferences Application of many inference rules allows us to infer new sound conclusions and hence prove theorems An example of an inference rule Modus ponens A 3 B A 4 premise B conclusion CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 1 P Q 2 P 3 R 3 Q A R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 139 P A Q Nondeterministic ste s 2 P 3 R 3 Q R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens I Proved S I CS 1571 Intro to AI M Hauskrecht Logic inferences and search Inference rule method as a search problem State a set of sentences that are known to be true Initial state a set of sentences in the KB Operators applications of inference rules 7 Allow us to add new sound sentences to old ones Goal state atheorem a is derived from KB Logic inference Proof A sequence of sentences that are immediate consequences of applied inference rules Theorem proving process of nding a proof of theorem CS 1571 Intro to AI M Hauskrecht Satisfiability SAT problem Determine whether a sentence in the conjunctive normal form CNF is satis able Ie can evaluate to true PVQv R Pv RVS Pva T It is an instance of a constraint satisfaction problem Variables 7 Propositional symbols P R T S 7 Values True False Constraints 7 Every conjunct must evaluate to true at least one of the literals must evaluate to true All techniques developed for CSPs can be applied to solve the logical inference problem Why CS 1571 Intro to AI M Hauskrecht Inference problem and satisfiability Inference problem we want to show that the sentence 0 is entailed by KB Satisfiability The sentence is satisfiable if there is some assignment interpretation under which the sentence evaluates to true ConneCtiOIU KB i a if and only if KB a is unsatis able Consequences inference problem is NPcomplete programs for solving the SAT problem can be used to solve the inference problem Simulatedannealing WALKSAT CS 1571 Intro to AI M Hauskrecht Satisfiability SAT problem Determine whether a sentence in the conjunctive normal form CNF is satisfiable ie can evaluate to true PVQv R Pv RVS Pva T It is an instance of a constraint satisfaction problem Variables 7 Propositional symbols P R T S 7 Values True False Constraints 7 Every conjunct must evaluate to true at least one of the literals must evaluate to true Why is this important All techniques developed for CSPs can be applied to solve the logical inference problem CS 1571 Intro to AI M Hauskrecht Resolution algorithm Algorithm 1 Convert KB to the CNF form 2 Apply iteratively the resolution rule starting from KB a in the CNF form 3 Stop when 7 Contradiction empty clause is reached A I A Q proves the entailment 7 No more new sentences can be derived Rejects disproves the entailment CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S Step 1 convert KB to CNF PAQ gt PAQ o P3R gt PVR QARS gt Qv RVS KB P Q Pv R QV RvS Step 2 Negate the theorem to prove it Via refutation S gt IS Step 3 Run resolution on the set of clauses P Q PVR Qv RVS uS CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S P Q PvR QV RVs S A RVS R Contradiction gt CS 1571 Intro to AI M Hauskrecht KB in restricted forms If the sentences in the KB are restricted to some special forms other sound inference rules may become complete Example Horn form Horn normal form Av B Av C VD Canbe written also as B 3 AAC3 D Modus ponens 7 is the universal complete rule for the sentences in the Homform A33 A AIAAZAAkDBA1A2Ak B B CS 1571 Intro to AI M Hauskrecht KB in Horn form Horn form a clause with at most one positive literal Av B Av C VD Not all sentences in propositional logic can be converted into the Horn form KB in Horn normal form 7 Two types of propositional statements Implications called rules B 3 A Propositional symbols facts B Application of the modus ponens 7 Infers new facts from previous facts A 3 B A B CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satisfied Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Both procedures are complete for KBs in the Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules and facts KB Rl A B 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Theorem E MHauskrecht CS 1571 Intro to AI Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G F1 A F2 B F3 D Rule R1 is satis ed F4 C CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Rule R1 is satis ed F4 C Rule R2 is satis ed F5 E CS 1571 Intro to AI M Hauskrecht Backward chaining example E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G R2 D Fl A 3 F2 B F3 D Backward chaining is more focused 7 tries to prove the theorem only CS 1571 Intro to AI M Hauskrecht Backward chaining example E R1 D A B Backward chaining is more focused 7 tries to prove the theorem only KB R1 AABSC CAFSG CS 1571 Intro to AI M Hauskrecht KB agents based on propositional logic Propositional logic allows us to build knowledge based agents capable of answering queries about the world by infering new facts from the known ones Example an agent for diagnosis of a bacterial disease Facts The stain of the organism is grampositive The growth conformation of the organism is chains Rules If Then The stain of the organism is grampositive The morphology of the organism is coccus The growth conformation of the organism is chains 3 The identity of the organism is streptococcus CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 14 Propositional logic Horn normal form Firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference problem Logical inference problem Given 7 a knowledge base KB a set of sentences and 7 a sentence 05 called a theorem Does a KB semantically entail a KB a In other words In all interpretations in which sentences in the KB are true is also at true Approaches Truth table approach Inference rules Conversion to SAT 7 Resolution refutation 381571 Intro to AI M Hauskrecht Truthtable approach Problem KB i 0 We need to check all possible interpretations for which the KB is true models of KB whether a is true for each of them Truth tables enumerate truth values of sentences for all possible interpretations assignments of True False to propositional symbols and check Example P r P v Q A Q True A 77 True False False CS 1571 Intro to AI M Hauskrecht Inference rules approach Motivation we do not want to blindly generate and check all interpretations 1 Inference rules Represent sound inference patterns repeated in inferences Application of many inference rules allows us to infer new sound conclusions and hence prove theorems An example of an inference rule Modus ponens A 3 B A lt premise B 4 conclusion CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 1 P Q 2 P 3 R 3 Q A R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens CS 1571 Intro to AI M Hauskrecht Example Inference rules approach KBPQ PER QAR3S TheoremS 139 P A Q Nondeterministic ste s 2 P 3 R 3 Q R 3 S 4 P From 1 and And elim 5 R From 24 and Modus ponens 6 Q From 1 and And elim 7 Q R From 56 and And introduction 8 S From 73 and Modus ponens I Proved S I CS 1571 Intro to AI M Hauskrecht Inference problem and satisfiability Inference problem we want to show that the sentence 0 is entailed by KB Satisfiability The sentence is satisfiable if there is some assignment interpretation under which the sentence evaluates to true ConneCtiOIU KB i a if and only if KB a is unsatis able Consequences inference problem is NPcomplete programs for solving the SAT problem can be used to solve the inference problem Simulatedannealing WALKSAT CS 1571 Intro to AI M Hauskrecht Satisfiability SAT problem Determine whether a sentence in the conjunctive normal form CNF is satisfiable ie can evaluate to true PVQv R Pv RVS Pva T It is an instance of a constraint satisfaction problem Variables 7 Propositional symbols P R T S 7 Values True False Constraints 7 Every conjunct must evaluate to true at least one of the literals must evaluate to true Why is this important All techniques developed for CSPs can be applied to solve the logical inference problem CS 1571 Intro to AI M Hauskrecht Resolution algorithm Algorithm 1 Convert KB to the CNF form 2 Apply iteratively the resolution rule starting from KB a in the CNF form 3 Stop when 7 Contradiction empty clause is reached A I A Q proves the entailment 7 No more new sentences can be derived Rejects disproves the entailment CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S Step 1 convert KB to CNF PAQ gt PAQ o P3R gt PVR QARS gt Qv RVS KB P Q Pv R QV RvS Step 2 Negate the theorem to prove it Via refutation S gt IS Step 3 Run resolution on the set of clauses P Q PVR Qv RVS uS CS 1571 Intro to AI M Hauskrecht Example Resolution KB P AQ P 3R AR 3 S Theorem S P Q PvR QV RVs S A RVS R Contradiction gt CS 1571 Intro to AI M Hauskrecht KB in restricted forms If the sentences in the KB are restricted to some special forms other sound inference rules may become complete Example Horn form Horn normal form Av B Av C VD Canbe written also as B 3 AAC3 D Modus ponens 7 is the universal complete rule for the sentences in the Homform A33 A AIAAZAAkDBA1A2Ak B B CS 1571 Intro to AI M Hauskrecht KB in Horn form Horn form a clause with at most one positive literal Av B Av C VD Not all sentences in propositional logic can be converted into the Horn form KB in Horn normal form 7 Two types of propositional statements Implications called rules B 3 A Propositional symbols facts B Application of the modus ponens 7 Infers new facts from previous facts A 3 B A B CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satisfied Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Both procedures are complete for KBs in the Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules and facts KB Rl A AB 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Theorem E MHauskrecht CS 1571 Intro to AI Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G F1 A F2 B F3 D Rule R1 is satis ed F4 C CS 1571 Intro to AI M Hauskrecht Forward chaining example Theorem E KB R1 A AB 3 C R2 C AD 3 E R3 C AF 3 G Fl A F2 B F3 D Rule R1 is satis ed F4 C Rule R2 is satis ed F5 E CS 1571 Intro to AI M Hauskrecht Backward chaining example E KB R1 A AB 2 C R2 C AD 3 E R3 C AF 3 G R2 D Fl A 3 F2 B F3 D Backward chaining is more focused 7 tries to prove the theorem only CS 1571 Intro to AI M Hauskrecht Backward chaining example E R1 D A B Backward chaining is more focused 7 tries to prove the theorem only KB R1 AABSC CAFSG CS 1571 Intro to AI M Hauskrecht KB agents based on propositional logic Propositional logic allows us to build knowledge based agents capable of answering queries about the world by infering new facts from the known ones Example an agent for diagnosis of a bacterial disease Facts The stain of the organism is grampositive The growth conformation of the organism is chains Rules If Then The stain of the organism is grampositive The morphology of the organism is coccus The growth conformation of the organism is chains 3 The identity of the organism is streptococcus CS 1571 Intro to AI M Hauskrecht First order logic CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic The world we want to represent and reason about consists of a number of objects with variety of properties and relations among them Propositional logic Represents statements about the world without re ecting this structure and without modeling these entities explicitly Consequence some knowledge is hard or impossible to encode in the propositional logic Two cases that are hard to represent 7 Statements about similar objects relations 7 Statements referring to groups of objects CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic Statements about similar objects and relations needs to be enumerated Example Seniority of people domain Assume we have John is older than Mary Mary is older than Paul To derive John is older than Paul we need John is older than Mary A Mary is older than Paul 3 John is older than Paul Assume we add another fact Jane is older than Mary To derive Jane is older than Paul we need Jane is older than Mary A Mary is older than Paul 3 Jane is older than Paul What is the problem CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic Statements about similar objects and relations needs to be enumerated Example Seniority of people domain Assume we have John is older than Mary Mary is older than Paul To derive John is older than Paul we need John is older than Mary A Mary is older than Paul 3 John is older than Paul Assume we add another fact Jane is older than Mary To derive Jane is older than Paul we need Jane is older than Mary A Mary is older than Paul 3 Jane is older than Paul Problem KB grows large CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic Statements about similar objects and relations needs to be enumerated Example Seniority of people domain For inferences we need John is older than Mary A Mary is older than Paul 3 John is older than Paul Jane is older than Mary A Mary is older than Paul 3 Jane is older than Paul Problem if we have many people and facts about their seniority we need represent many rules like this to allow inferences Possible solution 2 CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic Statements about similar objects and relations needs to be enumerated Example Seniority of people domain For inferences we need John is older than Mary A Mary is older than Paul 3 John is older than Paul Jane is older than Mary A Mary is older than Paul 3 Jane is older than Paul Problem if we have many people and facts about their seniority we need represent many rules like this to allow inferences Possible solution introduce variables PersA is older than PersB A PersB is older than PersC 3 PersA is older than PersC CS 1571 Intro to AI M Hauskrecht Limitations of propositional logic Statements referring to groups of objects require exhaustive enumeration of objects Example Assume we want to express Every student likes vacation Doing this in propositional logic would require to include statements about every student John likes vacation Mary likes vacation Arm likes vacation Solution Allow quanti cation in statements CS 1571 Intro to AI M Hauskrecht Firstorder logic FOL More expressive than propositional logic Eliminates de ciencies of PL by 7 Representing objects their properties relations and statements about them 7 Introducing variables that refer to an arbitrary objects and can be substituted by a specific object 7 Introducing quanti ers allowing us to make statements over groups objects without the need to represent each of them separately CS 1571 Intro to AI M Hauskrecht Logic Logic is de ned by A set of sentences 7 A sentence is constructed from a set of primitives according to syntax rules A set of interpretations 7 An interpretation gives a semantic to primitives It associates primitives with objects values in the real world The valuation meaning function V 7 Assigns a truth value to a given sentence under some interpretation V sentence gtlt interpretation gt True False CS 1571 Intro to AI M Hauskrecht Firstorder logic Syntax Term syntactic entity for representing objects Terms in FOL Constant symbols represent speci c objects 7 Eg John France car89 Variables represent objects of a certain type type domain of discourse 7 Eg xyz Functions applied to one or more terms 7 Egfather ofJohn father of ather of ohn CS 1571 Intro to AI M Hauskrecht First order logic Syntax Sentences in FOL Atomic sentences 7 A predicate symbol applied to 0 or more terms Examples Red car 2 SisterAmy Jane ManagerO ather of ohn 7 t1 t2 equivalence of terms Example John father o Peter CS 1571 Intro to AI M Hauskrecht First order logic Syntax Sentences in FOL Complex sentences Assume 1 are sentences in FOL Then 7 WuI v1 3 w w ll and Vx 3y are sentences Symbols El V stand for the existential and the universal quanti er CS 1571 Intro to AI M Hauskrecht Semantics Interpretation An interpretation I is de ned by a mapping to the domain of discourse D or relations on D domain of discourse a set of objects in the world we represent and refer to An interpretation I maps Constant symbols to objects in D 1John a Predicate symbols to relations properties on D ltgt 9 Function symbols to functional relations on D 1fatherofltgt gt CS 1571 Intro to AI M Hauskrecht Semantics of sentences Meaning evaluation function V sentence gtlt interpretation gt True False A predicate predicateterm 1 term 2 term 3 term n is true for the interpretation I iff the objects referred to by term 1 term 2 term 3 term n are in the relation referred to by predicate 1John 3 1Paul L 1brother gt brotherJohn Paul in Ibrother VbrotherJohn Paul I True CS 1571 Intro to AI M Hauskrecht Semantics of sentences Equality Vterm 1 term 2 I True Hf Iterm 1 Iterm 2 Boolean expressions standard Eg Vsentence 1 v sentence 2 I True Hf Vsentence 1I True or Vsentence 2I True Quantifications bstitution of x with d VVx ITrue su Hf for all d e D V IVd True VEx 1True Iff there is a d e D st V IVd True CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 9 Finding optimal configurations Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Search for the optimal configuration Objective find the optimal con guration Optimality De ned by some quality measure Quality measure re ects our preference towards each con guration or state 381571 Intro to AI M Hauskrecht Example Traveling salesman problem Problem 0 A graph with distances 0 Goal find the shortest tour which visits every city once and returns to the start An example of a valid tour ABCDEF CS 1571 Intro to AI M Hauskrecht Example N queens A CSP problem can be converted to the optimal con guration problem The quality of a con guration in a CSP the number of constraints violated Solving minimize the number of constraint violations of violations 3 of violations 1 of violations 0 CS 1571 Intro to AI M Hauskrecht Iterative optimization methods DF S may not be the best solution Worst case running time 7 Exponential in the number of variables found using iterative optimization methods Methods 7 Hill climbing 7 Simulated Annealing 7 Genetic algorithms Searching systematically for the best con guration with the Solutions to large optimal con guration problems are often CS 1571 Intro to AI M Hauskrecht Iterative optimization methods Properties 7 Search the space of complete con gurations 7 Take advantage of local moves Operators make local changes to complete con gurations 7 Keep track of just one state the current state no memory of past states 1 No search tree is necessary 1 CS 1571 Intro to AI M Hauskrecht Example N queens Local operators for generating the next state 7 Select a variable a queen 7 Reallocate its position cs 1571 lnlrn In Al M quskrecht Example Traveling salesman problem Local operator for generating the next state divide the existing tour into two parts reconnect the two parts in the opposite order Example ABCDEF B ABCD EF Part2 ABCDFE cs 1571 lnlrn In Al M quskrecht Example Traveling salesman problem Local operator 7 generates the next configuration state CS 1571 Intro to AIC M Hauskrecht Searching the configuration space Search algorithms keep only one con guration the current con guration Problem How to decide about which operator to apply CS 1571 Intro to AI M Hauskrecht Search algorithms Two strategies to choose the con guration state to be Visited next 7 Hill climbing 7 Simulated annealing Later Extensions to multiple current states 7 Genetic algorithms Note Maximization is inverse of the minimization min fXcgt max fX CS 1571 Intro to AI M Hauskrecht Hill climbing Look around at states in the local neighborhood and choose the one with the best value Assume we want to maximize the value Better Worse states CS 1571 Intro to AI M Hauskrecht Hill climbing Always choose the next best successor state stop when no improvement possible lunclinn Hth mmwmmmt mums a mth snte pm pvam 4 Wth no e tuner n me tin t mm DrumH MAKEAODEI tmnssswawomm h lnup Iln HerH a highrxh hm sneeessst m mmw in ALuElnnll s VALUElnHier then return Lurer ton one my 251571 hlrolu Al M HauskrscM I Hill climbing L L one with the best value v1 Betta Wm se suns What can go wrong M mom 5 1571 mm Al Hill climbing Hill climbing can get trapped in the local optimum No more value local improvement Better states What can go wrong CS 1571 Intro to AI M Hauskrecht Hill climbing Hill climbing can get clueless on plateaus value plateau states CS 1571 Intro to AI M Hauskrecht Hill climbing and nqueens The quality of a con guration is given by the number of constraints violated Then Hill climbing reduces the number of constraints Mincon ict strategy heuristic 7 Choose randomly a variable with con icts 7 Choose its value such that it violates the fewest constraints Success But not always The local optima problem CS 1571 Intro to Al M Hauskrecht Simulated annealing Permits bad moves to states with lower value thus escape the local optima Gradually decreases the frequency of such moves and their size parameter controlling it 7 temperature value Always up Sometimes down states CS 1571 Intro to Al M Hauskrecht Simulated annealing algorithm The probability of making a move The probability of moving into a state with a higher value is 1 The probability of moving into a state with a lower value is pAccept NEXT e where AE ENEXT ECURRENT 7 The probability is Proportional to the energy difference CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Energy E 145 Current con guration Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm AE ENEXT ECURREMquot 145716722 A t AET 722 T Current con guration p seep e e Energy E 145 Sometimes accept Energy E 167 Energy E 180 Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm Current con guration Energy E 145 AE ENEXT ECURREMquot 1807 167 gt 0 pAccept 1 Energy E 167 Energy E 180 Always accept Energy E 191 CS 1571 Intro to AI M Hauskrecht Simulated annealing algorithm The probability ofmoving into a state with alower value is where AEdmszm p Accept The probability is e Modulated through a wmperamre parameter T for T gt no the probability ofany move approaches 1 for T gt 0 the probability that astate with smaller Wlue is selected goes down and approaches 0 Cooling schedule 7 Schedule ofchanges ofapammeter T over iteratiori steps 51571lmroluAl M Halshscm S mulated annealing lunninn swuwzu wzmuai primum minihi rluuu a solution state iopulr PruNum a uiuhlem v is i nupwughmu umsm ieiuuouuua de Xlalic39 Lw mr sn uo um a node T a lcmlmalmequotrmmongllwpmmblhlyardmvmmldslnp HUMH hLAKErNoDEUNlTlALSYAYEImelem it turn Hue do Te dually7 il Tu tneo I39rlul39n unuer mer o mrlouih selrtlrd urnsml nH39llrrm Aft wins m Lushmm my D quotlemurerwa pure commie m1 Duly w H pralvalvlhlydquot i 51571lmroluAl M Halshscm Simulated annealing algorithm Simulated annealing algorithm 7 developed originally for modeling physical processes Metropolis et al 53 Propelties 7 If T is decreased slowly enough the best con guration state is always reached Applications 7 VLSI design 7 airline scheduling CS 1571 Intro to AI M Hauskrecht Simulated evolution and genetic algorithms Limitations of simulated annealing 7 Pursues one state con guration at the time 7 Changes to con gurations are typically local Can we do better Assume we have two con gurations with good values that are quite different We expect that the combination of the two individual con gurations may lead to a con guration with higher value Not guaranteed M This is the idea behind genetic algorithms in which we grow a population of individual combinations CS 1571 Intro to AI M Hauskrecht Genetic algorithms Algorithm idea Create a population of random configurations Create a new population through 7 Biased selection of pairs of configurations from the previous population 7 Crossover combination of pairs 7 Mutation of resulting individuals Evolve the population over multiple generation cycles Selection of configurations to be combined 7 Fitness function value function measures the quality of an individual a state in the population 05 1571 Intro to AI M Hauskrecht Reproduction process in GA Assume that a state configuration is defined by a set variables with two values represented as 0 or 1 000110010111 gtlt 111010010111l gtl 111010010111 111010101100 000 0010111 000110101100 000110101100 001110101001 6 24 1110101 100 gtlt 111010101001 111E10101001 111011011100 5 20 001110101001 001110101100 00111010110I ill b Cl M iv 01ml Populaiwn 11le Function Sclcclmn xiy7 or Mumnon cs 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 16 Inference in firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference in FOL Logical inference problem Given a knowledge base KB a set of sentences and a sentence a does the KB semantically entail a KB za In other words In all interpretations in which sentences in the KB are true is also 0 true Logical inference problem in the rst order logic is undecidable 11 No procedure that can decide the entailment for all possible input sentences in a nite number of steps 381571 Intro to AI M Hauskrecht Logical inference problem in the Propositional logic Computational procedures that answer KBla Three approaches Truth table approach Inference rules Conversion to the inverse SAT problem 7 Resolution refutation CS 1571 Intro to AI M Hauskrecht Inference in FOL Truth table Is the Truthtable approach a Viable approach for the FOL CS 1571 Intro to AI M Hauskrecht Inference in FOL Truth table approach Is the Truthtable approach a Viable approach for the FOL I N 0 Why It would require us to enumerate and list all possible interpretations I I assignments of symbols to objects predicates to relations and functions to relational mappings Simply there are too many interpretations CS 1571 Intro to AI M Hauskrecht Inference in FOL Inference rules Is the Inference rule approach a Viable approach for the FOL CS 1571 Intro to AI M Hauskrecht Inference in FOL Inference rules Is the Inference rule approach a viable approach for the FOL Yes The inference rules represent sound inference patterns one can apply to sentences in the KB What is derived follows from the KB Caveat we need to add rules for handling quantifiers CS 1571 Intro to AI M Hauskrecht Inference rules Inference rules from the propositional logic 7 Modus ponens A 3 B A B 7 Resolution A v B B v C A v C 7 and others Andintroduction Andelimination Or introduction Negation elimination Additional inference rules are needed for sentences with quantifiers and variables 7 Must involve variable substitutions CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er Vx P x 7 Free 7 if it is not bound 3x 130 Q06 y is free Examples Vx Ely Likes xy Bound or free CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er VJQPWZ 7 Free71f 1t 1s not ound 335 PO yis free Examples Vx Ely Likes xy Bound Vx Likes x y Ely Likes y Raymond Bound or free CS 1571 Intro to AI M Hauskrecht Sentences with variables Firstorder logic sentences can include variables Variable is 7 Bound 7 if it is in the scope of some quanti er V16 P XI 7 Free 7 1f 1t 1s not ound 335 PO yis free Examples Vx Ely Likes x y Bound Vx Likes x y Ely Likes yRaym0nd Free M Hauskrecht CS 1571 Intro to AI Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTx z y fatherof J0hn Likesx y Likesz fatherof J0hn CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal elimination Vx x a 1s a constant symbol a 7 substitutes a variable with a constant symbol Vx Likesx IceC ream LikesBen IceC ream Existential elimination El x x a 7 Substitutes a variable with a constant symbol that does not appear elsewhere in the KB Elx Kill x Victim Kill Murderer Victim CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal instantiation introduction x 7 is not free in Vx 7 Introduces a universal variable which does not affect or its assumptions SisterAmy Jane Vx S isterAmy Jane Existential instantiation introduction a a7isagr0undtermin Elx x x7is notfree in 7 Substitutes a ground term in the sentence with a variable and an existential statement LikesBen I ceC ream Elx Likesx I ceC ream CS 1571 Intro to AI M Hauskrecht Uni cation Problem in inference Universal elimination gives many opportunities for substituting variables with ground terms Vx x a Solution Try substitutions that may help 7 Use substitutions of similar sentences in KB a is a constant symbol Uni cation 7 takes two similar sentences and computes the substitution that makes them look the same if it exists UNIFY pq 039 st SUBST o p SUBST 039q CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yM0therOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth fail CS 1571 Intro to AI M Hauskrecht Generalized inference rules Use substitutions that let us make inferences Example Modus Ponens If there exists a substitution 6 such that SUBST 6 A1 SUBST on11 for all i12 11 A1 AA2 An 3 B Al39A239An39 S UBST a B Substitution that satis es the generalized inference rule can be build Via uni cation process Advantage of the generalized rules they are focused 7 only substitutions that allow the inferences to proceed CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1 VVz V ln SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PxvQx QJ0hnvSy CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1v 2v k wlvwzwlIn SUBSTU IVV HV i1v kvylvv1j1v1j1ln Example PXVQxa 39QJ0hnVSy PJ0hnvSy CS 1571 Intro to AI M Hauskrecht Inference with resolution rule Proof by refutation Prove that KB a resolution is refutation complete is unsatis able Main procedure steps Convert KB a to CNF with ground terms and universal variables only 2 Apply repeatedly the resolution rule while keeping track and consistency of substitutions 3 Stop when empty set contradiction is derived or no more new resolvents conclusions follow CS 1571 Intro to AI M Hauskrecht Conversion to CNF 1 Eliminate implications equivalences 1v3 q gt pvq 2 Move negations inside DeMorgan s Laws double negation 39I7 I gt 39PV 39q pr gtEx p 39PV I gt 39P quotI Exp gtVx p 3 Standardize variables rename duplicate variables Vx Px V 3x QXD gt Vx Px V 3y Qy 4 Move all quanti ers left no invalid capture possible Vx Px V 3y Qy gt Vx 3y Px V Qy CS 1571 Intro to AI M Hauskrecht Conversion to CNF 5 Skolemization removal of existential quanti ers through elimination If no universal quanti er occurs before the existential quanti er replace the variable with a new constant symbol 3yPAV Qy gt PAV QB If a universal quanti er precede the existential quanti er replace the variable with a function of the universal variable Vx EIyPxv Qy gt Vx Pxv QFx F x a Special function called Skolem function CS 1571 Intro to AI M Hauskrecht Conversion to CNF 6 Drop universal quantifiers all variables are universally quanti ed Vx PxV QFx gt PxV QFx 7 Convert to CNF using the distributive laws pvqAr gt pvqpvr The result is a CNF with variables constants functions CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV 01 PxV R06 RZV 32 SA CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 4WVQWamp QWMHWH vRWL M VsQLM yw Pw v Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il WVQWamp QUMHWH vRWL MDVsQLM yw 39PWV Sw xw Sw v Rw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 39RZV SZ SA yw 39PWV Sw xw Zw Sw v Rw Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 RZV SZ SA yw 39PWV Sw xw Zw Sw v Rw Sw Contradiction sz wA CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 19 Inference in firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference in FOL Logical inference problem Given a knowledge base KB a set of sentences and a sentence a does the KB semantically entail a KB za In other words In all interpretations in which sentences in the KB are true is also 0 true Logical inference problem in the rst order logic is undecidable 11 No procedure that can decide the entailment for all possible input sentences in a nite number of steps 381571 Intro to AI M Hauskrecht Logical inference problem in the Propositional logic Computational procedures that answer KBla Three approaches Truth table approach gtlt Inference rules Conversion to the inverse SAT problem 7 Resolution refutation CS 1571 Intro to AI M Hauskrecht Inference rules Inference rules from the propositional logic 7 Modus ponens A 3 B A B 7 Resolution A v B B v C A v C 7 and others Andintroduction Andelimination Or introduction Negation elimination Additional inference rules are needed for sentences with quanti ers and variables 7 Must involve variable substitutions CS 1571 Intro to AI M Hauskrecht Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTx zy father0fJ0hnLikesxy Likesz fatherof J0hn CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal elimination Vx x a 7 substitutes a variable with a constant symbol Vx Likesx IceC ream LikesBen IceC ream a is a constant symbol Existential elimination El x x a 7 Substitutes a variable with a constant symbol that does not appear elsewhere in the KB Elx Kill x Victim Kill Murderer Victim CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal instantiation introduction qu 7 Introduces a universal variable which does not affect or its assumptions x 7 is not free in SisterAmy Jane Vx S isterAmy Jane Existential instantiation introduction a a 7 is a ground term in Elx x x7is notfree in 7 Substitutes a ground term in the sentence with a variable and an existential statement LikesBen I ceC ream Elx Likesx IceC ream CS 1571 Intro to AI M Hauskrecht Uni cation Problem in inference Universal elimination gives many opportunities for substituting variables with ground terms Vx x a Solution Try substitutions that may help a is a constant symbol 7 Use substitutions of similar sentences in KB Uni cation 7 takes two similar sentences and computes the substitution that makes them look the same if it exists UNIFY pq 039 st SUBST a39p SUBST 039q CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yMotherOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth fail CS 1571 Intro to AI M Hauskrecht Generalized inference rules Use substitutions that let us make inferences Example Modus Ponens If there exists a substitution 6 such that SUBST 6 A1 SUBST ox11 for all i12 11 A1 AA2 An 3 B Al39A239An39 S UBST a B Substitution that satis es the generalized inference rule can be build Via uni cation process Advantage of the generalized rules they are focused 7 only substitutions that allow the inferences to proceed CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1VW2VWn SUBSTU IVV HV i1v kvylvv1j1v1j1ln Example PxvQx QJ0hnvSy CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1VW2VWn SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PXVQxa 39QJ0hnVSy PJ0hn v Sy CS 1571 Intro to AI M Hauskrecht Inference with resolution rule Proof by refutation 7 Prove that KB a is unsatis able 7 resolution is refutation complete Main procedure steps 1 Convert KB I a to CNF with ground terms and universal variables only 2 Apply repeatedly the resolution rule while keeping track and consistency of substitutions 3 Stop when empty set contradiction is derived or no more new resolvents conclusions follow CS 1571 Intro to AI M Hauskrecht Conversion to CNF 1 Eliminate implications equivalences 1v3 q gt pvq 2 Move negations inside DeMorgan s Laws double negation pAq gt pv q pr x p pvq gt p q axper p 3 Standardize variables rename duplicate variables Vx Px V 3x Qx gt Vx Px V 3y Q00 4 Move all quantifiers left no invalid capture possible Vx Px V 3y Qy gt Vx 3y Px V Qy CS 1571 Intro to AI M Hauskrecht Conversion to CNF 5 Skolemization removal of existential quanti ers through elimination If no universal quanti er occurs before the existential quanti er replace the variable with a new constant symbol 3yPAV Qy gt PAV QB If a universal quanti er precede the existential quanti er replace the variable with a function of the universal variable Vx Ely Px v Qy gt Vx Pxv QFx F x a special function called Skolem function CS 1571 Intro to AI M Hauskrecht Conversion to CNF 6 Drop universal quanti ers all variables are universally quanti ed Vx PxV QFx gt PxV QFx 7 Convert to CNF using the distributive laws pvqAr gt pvqpvr The result is a CNF with variables constants functions CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 39RZV SZ SA CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV Sy PxV R06 RZV SZ SA yw Pw v Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 4WVQWamp QWMHWH vRWL M VsQLM yw 39PWV Sw xw Sw v Rw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il WVQWamp QUMHWH vRWL MDVsQLM yw 39PWV Sw xw Zw Sw v Rw Sw CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 39PWV QWmQyV 30 PxV R06 39RZV 32 SA yw 39PWV SW xw zw Sw v Rw SW wA Contradiction Z CS 1571 Intro to AI M Hauskrecht Dealing with equality Resolution works for firstorder logic without equalities To incorporate equalities we need an additional inference rule Demodulation rule 6 UNIFY it1 fail 1V 2V ka l 121 2 SUBSTSUBSTUtlSUBSTUt2 1vv 1v i1v k Example Pow fx x 130 Paramodulation rule more powerful 0 39 illal quot giveal 39 I proof theory for FOL CS 1571 Intro to AI M Hauskrecht Sentences in Horn normal form Horn normal form HNF in the propositional logic 7 a special type of clause with at most one positive literal Av B Av CVD Typically written as B 3 A A C 3 D A clause with one literal eg A is also called a fact A clause representing an implication with a conjunction of positive literals in antecedent and one positive literal in consequent is also called a rule Generalized Modus ponens 7 is the complete inference rule for KBs in the Horn normal form Not all KBs are convertible to HNF ll CS 1571 Intro to AI M Hauskrecht Horn normal form in FOL First order logic FOL 7 adds variables and quanti ers works with terms Generalized modus ponens rule a a substitution st Vi SUBSTU SUBSTU i 1 2 1A 2Am n31 SUBSTUT v 5quot Generalized modus ponens is complete for the KBs with sentences in Horn form Not all rstorder logic sentences can be expressed in this orm CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Typical usage If we want to infer all sentences entailed by the existing KB Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Typical usage If we want to prove that the target goal sentence a is entailed by the existing KB Both procedures are complete for KBs in Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules KB R1 Steamboat x Sailboat y 3 Faster x y R R F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow N Sailboat y RowBoat z 3 Faster y 2 LA Faster x y AFaster y z 3 Faster x z Theorem Faster Titanic Poncb4rrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x A Sailboat y 3 Faster x y R21 Sailboat y A RowBoat z 3 Faster y 2 R3 FasterxyAFasteryz3 Faster xz F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x A Sailboat y 3 Faster x y R2 Sailboat y A RowBoat z 3 Faster y 2 R3 FasterxyAFasteryz3 Faster xz F1 Steamboat T itanie F2 Sailboat Mistral F3 RowBoatPonaL4rrow Rule R1 is satis ed F4 F asterT itanie Mistral CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x Sailboat y 3 Faster x y R21 Sailboat y ARowBoat z 3 Faster y 2 R3 FasterxyFasteryz3 Faster xz F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow CS 1571 Intro to AI M Hauskrecht KB Forward chaining example R11 Steamboat x Sailboat y 3 Faster x y 22 Sailboat y ARowBoat z 3 Faster y z 3 FasterxyFasteryz3 Faster xz F11 Steamboat T itanie F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow Rule R3 is satis ed F6 FasterTitaniePoncl4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the antecedents if part of the rule amp repeat recursively KB R11 Steamboat x Sailboat y 3 Faster x y R2 Sailboat y ARowBoat z 3 Faster y 2 R31 FasterxyFasteryz3 Faster xz F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow Theorem Faster Titanic Pond4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondA rrow F1 Steamboat Titanic R1 F22 Sailboat Mistral F3 RawBoaKPondlrrow SteamboaTitanic SailboatPondArrow X Steamboat x Sailboat y 3 Faster x y Faster Titanic Pon rrow xTitanic yPonal4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondArrow F12 Steamboat Titanic F2 Sailboat Mistral F3 RowBoaKPondArroM SteamboatTitanic SailboatTitanic SailboatPondArrow RWBoatPondArr0w X Sailboat y RowBoat z 3 Faster y 2 F aster Titanic Po rhllrrow y Titanic z Pond4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example F1 Steamboat Titanic F22 Sailboat Mistral F3 RowBoaKPondArroM Faster Titanic PondArrow SteamboatTitanic SailboatTitanic Faste yfondArmM x F astetTitanic y SailboatPondArrow RowBo ti PondArrow R2 R1 SteamboatTitanic Sailb0mMlstral RowBoatPondArrow SailboatMistral CS 1571 Intro to AI M Hauskrecht Backward chaining Faster Titanic PondArrow y must be bound to the same term SteamboatTitanic ailboatTitanic Fame Pond1WD x F asteKTitanic y SailboaKPondArrow RowBoatPondArraw X R1 SteamboatTitanic Sailb0mMlStral R0wBoatPondArraw SailboatMistral CS 1571 Intro to AI M Hauskrecht Backward chaining The search tree ANDOR tree Special search algorithms exits including heuristics A0 A0 F mfer Titanic Pondlrrow SfeLIMbow Titanic ailboatTifanic F aster yP0ndArroMb FasteKTitanig y SailboatP0ndArmw RowBo 7Pondlrmw R SteamboatTm1mc Sailboamm ml Stu110 M mj RowBoafPondArrow CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 3 Problem solving by searching N los Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Course administrivia Instructor N los Hauskrecht 5329 Sennott Square 1niloscspittedu TA Swapna Somasundaran 5422 Sennott Square swapnacspittedu Course web page httpwwwcspitteduNmiloscoursescs1571 381571 Intro to AI M Hauskrecht Solving problems by searching Some problems have a straightforward solution 7 Just apply the formula or follow a standardized procedure Example solution of the quadratic equation 7 Hardly a sign of intelligence More interesting problems require search 7 more than one possible alternative needs to be explored before the problem is solved 7 the number of alternatives to search among can be very large even infinite cs 1571 Introto AI M Hauskrecht Search example Traveler problem Find a route from one city Arad to the other Bucharest I Gradea Sihm Fagzras I I Hivsova I E1 39 I Giurgiu we cs 1571 Introto AI M Hauskrecht Example Puzzle 8 0 Find the sequence of the empty tile moves from the initial game position to the designated target position Initial position Goal position E 1 i i 2 i W E E 7 4 G 7 BE L F M Hauskrecht CS 1571 Intro to AI Example Nqueens problem Find a con guration of n queens not attacking each other A goal con guration A bad con guration CS 1571 Intro to Al M Hauskrecht A search problem is de ned by A search space 7 What is it A goal condition CS 1571 Intro to AI M Hauskrecht A search problem is de ned by A search space 7 What is it 7 A set of objects among which we search for the solution 7 What is the search space for the puzzle 8 problem A goal condition CS 1571 Intro to AI M Hauskrecht A search problem is de ned by A search space 7 What is it 7 A set of objects among which we search for the solution 7 What is the search space for the puzzle 8 problem 7 A sequence of moves A goal condition 7 Give an example of a goal condition for the map problem CS 1571 Intro to AI M Hauskrecht A search problem is de ned by A search space 7 What is it 7 A set of objects among which we search for the solution 7 What is the search space for the puzzle 8 problem 7 A sequence of moves A goal condition 7 Give an example of a goal condition for the map problem 7 A path from Ato B 7 The shortest path from A to B CS 1571 Intro to AI M Hauskrecht Search Search process 7 The process of exploration of the search space The ef ciency of the search depends on 7 The search space and its size 7 Method used to explore traverse the search space 7 Condition to test the satisfaction of the search objective what it takes to determine Ifound the desired goal object Important to remember ll 7 Conveniently chosen search space and the exploration policy can have a profound effect on the efficiency of the solution CS 1571 Intro to AI M Hauskrecht Graph search Many search problems can be naturally represented as graph search problems Typical example Route nding 7 Map corresponds to the graph nodes to cities links to available connections between cities 7 Goal find a route path in the graph from S to T CS 1571 Intro to AI M Hauskrecht Graph search Less obvious conversion Puzzle 8 Find a sequence of moves from the initial con guration to the goal con guration 7 nodes corresponds to states of the game 7 links to valid moves made by the player cs 1571 Inlrn In AI M quskrechl Search problem Search problems that can be represented or converted into a graph search problems can be de ned in terms 0 Initial state 7 State con guration we start to search from eg start city initial game position Operators 7 Transform one state to another eg valid connections between cities valid moves in Puzzle 8 Goal condition 7 De nes the target state destination winning position Search space the set of objects we search for the solution 7 is now de ned indirectly through the initial state operators cs 1571 Inlrn In AI M quskrechl Graph search problem States game positions or locations in the map that are represented by nodes in the graph 0 Operators connections between cities valid moves Initial state 7 start position start city Goal state 7 target position positions target city cities start T target CS 1571 Intro to AI M Hauskrecht N queens Some problems can be converted to the graph search problems 0 But some problems are harder and less intuitive 7 Take eg Nqueens problem Goal con guration 0 Problem 7 We look for a con guration not a sequence of moves 7 No distinguished initial state no operators moves CS 1571 Intro to AI M Hauskrecht Nqueens How to choose the search space for N queens Ideas cs 1571 Inlrn In AI M quskrechl Nqueens How to choose the search space for Nqueens Ideas Search space 7 all con gurations of N queens on the board Can we convert it to a graph search problem We need states operators initial state and goal condition initial goal 0 cs 1571 Inlrn In AI M quskrecht Nqueens Search space 7 all con gurations of N queens on the board Can we convert it to a graph search problem We need states operators initial state and goal state mum gm lt2 0 States are Nqueen con gurations Initial state Operators moves cs 1571 Intro In AI M quskrechl Nqueens Search space 7 all con gurations of N queens on the board Can we convert it to a graph search problem We need states operators initial state and goal condition initial gm llI V E 0 X Initial state an arbitrary Nqueen configuration Operators moves change a position of one queen CS 1571 Intro In Al M quskrechl Nqueens Is there an alternative way to formulate the N queens problem as a search problem Ideas cs 1571 Inlrn In AI M quskrechl Nqueens Is there an alternative way to formulate the N queens problem as a search problem Search space con gurations of01 2 N queens Graph search 7 States con gurations of012 N queens 7 Operators additions of a queen to the board 7 Initial state 0 queens on the board SEE cs 1571 Inlrn In AI M quskrechl Graph search A trick generate a con guration step by step one queen per step States nodes correspond to con gurations of 01234 queens Links operators correspond to the addition of a queen Initialtt 1 d thb d sae no queensp ace on e oar Targetl ug cs 1571 Intro In AI M quskrechl Graph search Nqueens problems This is a different graph search problem When compared to Puzzle 8 or Route planning We want to nd only the target con guration not a path cs 1571 Intro In AI M quskrecht Two types of graph search problems Path search 7 Find a path between states S and T 7 Example traveler problem Puzzle 8 7 Additional goal criterion minimum length cost path Con guration search constraint satisfaction search 7 Find a state con guration satisfying the goal condition 7 Example nqueens problem design of a device with a prede ned functionality 7 Additional goal criterion soft preferences for configurations eg minimum cost design CS 1571 Intro to AI M Hauskrecht Search problem Search problems that can be represented or converted into a graph search problems can be defined in terms of Initial state 7 State configuration we start to search from eg start city initial game position Operators 7 Transform one state to another eg valid connections between cities valid moves in Puzzle 8 Goal condition 7 Defines the target state destination winning position Search space the set of objects we search for the solution 7 is now defined indirectly through the initial state operators CS 1571 Intro to AI M Hauskrecht Traveler problem Traveler problem formulation States different cities Initial state city Arad Operators moves to cities in the neighborhood Goal condition city Bucharest Type of the problem path search Possible solution cost path length CS 1571 Intro to Al M Hauskrecht Puzzle 8 example WWW BEE Goal state E m Initial state Search problem formulation States tile configurations Initial state initial con guration Operators moves of the empty tile Goal reach the winning con guration Type of the problem path search Possible solution cost a number of moves CS 1571 Intro to Al M Hauskrecht Nqueens problem Initial con guration Problem formulation States con gurations of 0 to 4 queens on the board Initial state noqueen con guration Operators add a queen to the le Inost unoccupied column Goal a con guration with 4 nonattacking queens Type of the problem con guration search cs 1571 Inlrn In AI M quskrechl Nqueens problem Alternative formulation of N queens problem Bad goal con guration Valid goal con guration Problem formulation States different con gurations of 4 queens on the board Initial state an arbitrary con guration of 4 queens Operators move one queen to a different unoccupied position Goal a con guration with nonattacking queens Type of the problem con guration search cs 1571 Inlrn In AI M quskrecht Comparison of two problem formulations Solution 1 i Operators switch one of the queens 15 4 all con gurations Solution 2 Operators add a queen to the le most unoccupied column 1 4 42 43 44 lt 45 con gurations altogether cs 1571 Inlrn In 111 M quskrecht Even better solution to the Nqueens Solution 2 Operators add a queen to the le most unoccupied column lt 45 con gurations altogether Improved solution With a smaller search space Operators add a queen to the leftmost unoccupied column such that it does not attack already placed queens 1443432432165 con gurations altogether cs 1571 Inlrn In 111 M quskrecht Formulating a search problem Search process 7 The process of exploration of the search space The ef ciency of the search depends on 7 The search space and its size 7 Method used to explore traverse the search space 7 Condition to test the satisfaction of the search objective what it takes to determine Ifound the desired goal object Think twice before solving the problem by search 7 Choose the search space and the exploration policy CS 1571 Intro to AI M Hauskrecht Search process Exploration of the state space through successive application of operators from the initial state A search tree a kind of search exploration trace with nodes corresponding to explored states CS 1571 Intro to AI M Hauskrecht Search tree A search tree a search exploration trace It is different from the graph de ning the problem States can repeat in the search tree Search tree CS 1571 Intro to AI M Hauskrecht Search tree Nezmr last gtVasiui Hirsova Rimnicu Vilcez u Mehadiz Dobrek i Efuvie A branch in the search tree path in the graph 251571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem oop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem loop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem oop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem loop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem oop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to AI M Hauskrecht General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem loop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop CS 1571 Intro to Al M Hiuskrechf General search algorithm Generalsearch problem strategy initialize the search tree with the initial state of problem loop if there are no candidate states to explore return failure choose a leaf node of the tree to expand next according to strategy if the node satisfies the goal condition return the solution expand the node and add all of its successors to the tree end loop Search methods differ in how they explore the space that is how they choose the node to expand next ll CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 20 Planning situation calculus Milos Hauskrecht miloscspittedu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Knowledgebased system Knowledge base Inference engine Knowledge base 7 A set of sentences that describe the world in some formal representational language e g firstorder logic 7 Domain speci c knowledge Inference engine 7 A set of procedures that work upon the representational language and can infer new facts or answer KB queries eg resolution algorithm forward chaining 7 Domain independent 381571 Intro to AI M Hauskrecht Automated reasoning systems Examples and main differences Theorem provers 7 Prove sentences in the rstorder logic Use inference rules resolution rule and resolution refutation Deductive retrieval systems 7 Systems based on rules KBs in Horn form 7 Prove theorems or infer new assertions forward backward chaining Production systems 7 Systems based on rules with actions in antecedents 7 Forward chaining mode of operation Semantic networks 7 Graphical representation of the world objects are nodes in the graphs relations are various links CS 1571 Intro to AI M Hauskrecht Production systems Based on rules but different from KBs in the Horn form Knowledge base is divided into A Rule base includes rules A Working memory includes facts A special type of if then rule 171 A172 Ampquot 3 a1a2ak Antecedent a conjunction of literals 7 facts statements in predicate logic Consequent a conjunction of actions An action can 7 ADD the fact to the KB working memory 7 REMOVE the fact from the KB consistent with logic 7 QUERY the user etc CS 1571 Intro to AI M Hauskrecht Production systems Based on rules but different from KBs in the Horn form Knowledge base is divided into A Rule base includes rules A Working memory includes facts A special type of if then rule 171 A172 Ampquot 3 a1a2 Antecedent a conjunction of literals 7 facts statements in predicate logic Consequent a conjunction of actions An action can 7 ADD the fact to the KB working memory 7 REMOVE the fact from the KB lt Different from logic 7 QUERY the user etc ak CS 1571 Intro to AI M Hauskrecht Production systems Use forward chaining to do reasoning 7 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 R27 Conditions R27 gt Actions R27 R105 Conditions R105 1 Actions R105 Strategy for selecting the rule to be fired from among possible candidates is called con ict resolution CS 1571 Intro to AI M Hauskrecht Production systems Why is con ict resolution important Or Why do we care about the order Assume that we have two rules and the preconditions of both are satis ed R1 Ax ABx ACy 3 add Dx R2 AxBxEz 3 delete Ax What can happen if rules are triggered in different order CS 1571 Intro to AI M Hauskrecht Production systems Why is con ict resolution important Or Why do we care about the order Assume that we have two rules and the preconditions of both are satis ed R1 Ax ABx ACy 3 add Dx R2 Ax Bx Ez 3 delete Ax What can happen if rules are triggered in different order 7 If Rl goes rst R2 condition is still satis ed and we infer 1300 7 If R2 goes rst we may never infer DX CS 1571 Intro to AI M Hauskrecht Production systems Problems with production systems 7 Additions and Deletions can change a set of active rules 7 If a rule contains variables testing all instances in which the rule is active may require a large number of uni cations 7 Conditions of many rules may overlap thus requiring to repeat the same uni cations multiple times Solution Rete algorithm 7 gives more ef cient solution for managing a set of active rules and performing uni cations 7 Implemented in the system OPS 5 used to implement XCON 7 an expert system for con guration of DEC computers CS 1571 Intro to AI M Hauskrecht Rete algorithm Assume a set of rules Ax A Bx A Cy 3 add Dx AxAByADx 3 add Ex Ax A Bx A Ez 3 delete Ax Andfm A0A2B2B3B4C5 Rete 7 Compiles the rules to a network that merges conditions of multiple rules together avoid repeats 7 Propagates valid uni cations 7 Reevaluates only changed conditions CS 1571 Intro to AI M Hauskrecht Rete algorithm Network Rules AgtC 2mm Cy 2 add 132 AgtC 3002 132 2 add 52 AgtC BgtC 52 2 2121222 42 Fm A1A2 22 23 B4cs 251511 mm m MINI15km Con ict resolution strategies Problem Two or more rules are active at the same time Which one to execute next Solutions 2 No duplication do not execute the same rule twice 2 Recency Rules referring to facts newly added to the working memory take precedence 2 Speci city Rules that are more speci c are preferred 2 Priority levels Define priority ofrules actions based on expert opinion Have multiple priority levels such that the higher priority rules fire first 251511 mm m MINI15km Semantic network systems Knowledge about the world described in terms of graphs Nodes correspond to 7 Concepts or objects in the domain Links to relations Three kinds 7 subset links 0521 pan OfIinks Inheritance relation links 7 Member links instance links 7 Function links Can be transformed to the rstorder logic language Graphical representation is often easier to work with 7 better overall View on individual concepts and relations CS 1571 Intro to AI M Hauskrecht Semantic network Example Trans ortson EI isa isa Ocean liner Oil tanker Engine 9 9 1513M member member is39pan Swimming Queen Boiler pool Mary Inferred properties Queen Mary is a ship Queen Mary has a boiler Exxon Valdez CS 1571 Intro to AI M Hauskrecht Planning situation calculus CS 1571 Intro to AI M Hauskrecht Representation of actions situations events The world is dynamic What is true now may not be true tomorrow Changes in the world may be triggered by our activities Problems 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 nd a sequence of actions that achieves some goal in this complex world A very complex search problem CS 1571 Intro to AI M Hauskrecht Situation calculus Provides a framework for representing change actions and reasoning about them Situation calculus 7 based on firstorder logic 7 a situation variable models new states of the world 7 action objects model activities 7 uses inference methods developed for FOL to do the reasoning CS 1571 Intro to AI M Hauskrecht Situation calculus Logic for reasoning about changes in the state of the world The world is described by 7 Sequences of situations of the current state 7 Changes from one situation to another are caused by actions The situation calculus allows us to 7 Describe the initial state and a goal state 7 Build the KB that describes the effect of actions operators 7 Prove that the KB and the initial state lead to a goal state extracts a plan as sideeffect of the proof CS 1571 Intro to AI M Hauskrecht Situation calculus The language is based on the First order logic plus Special variables 361 7 objects of type situation and action Action functions return actions 7 Eg MoveA TABLE B represents a move action 7 M ovex yz represents an action schema Two special function symbols of type situation 7 s0 7 initial situation 7 DOas 7 denotes the situation obtained after performing an action a in situation s Situation dependent functions and relations also called uents 7 Relation Onxys 7 object X is on object y in situation s 7 Function AboveXs 7 object that is above X in situation s CS 1571 Intro to AI M Hauskrecht Situation calculus Blocks world example I I I Initial state OnA Table SD OMB Table so OnC Table so ClearA SD ClearB so ClearC so ClearTable SD Goal Find a state situation 5 such that OnAB s OMB C s OnC Table s CS 1571 Intro to AI M Hauskrecht Blocks world example I I I Initial state OnA Table so OMB Table SD OnC Table so ClearA so ClearB SD ClearC so ClearTable so Goal OnAB s OnBC s OnC Table s Note It is not necessary that the goal describes all relations ClearA s CS 1571 Intro to AI M Hauskrecht Blocks world example Assume a simpler goal OnAB s I I I Initial state OnA Table SD OMB Table so OnC Table so ClearA SD ClearB so ClearC so ClearTable SD 3 possible goal con gurations I I Goal OnAB s CS 1571 Intro to AI M Hauskrecht Knowledge base Axioms Knowledge base needed to support the reasoning Must represent changes in the world due to actions Two types of axioms Effect axioms 7 changes in situations that result from actions Frame axioms 7 things preserved from the previous situation CS 1571 Intro to AI M Hauskrecht Blocks world example Effect axioms Effect axioms Moving x from y to 2 MOVE x y 2 Effect of move changes on On relations Onx y 3 A Clear x 3 A Clear 2 3 Onx ZDO MOVE x y 2 3 Onx y 3 A Clear x 3 A Clear 2 3 On x y DO MOVE x y 2 3 Effect of move changes on Clear relations Onx y 3 A Clear x 3 A Clear 2 3 a Clear y DO MOVE x y 2 3 On x y 3 A Clear x 3 A Clear 2 3 A Z i Table Clear ZDO MOVE x y 2 3 CS 1571 Intro to AI M Hauskrecht Blocks world example Frame axioms Frame axioms 7 Represent things that remain unchanged after an action On relations OnuvsA u i xA v i y OnuvDOMOVE x yzs Clear relations Clear us A u i Z a Clear uDO MOVE x y 2 3 CS 1571 Intro to AI M Hauskrecht Planning in situation calculus Planning problem nd a sequence of actions that lead to a goal Planning in situation calculus is converted to the theorem proving problem Goal state HS OnABs A OnBCs A OnCTable 3 Possible inference approaches 7 Inference rule approach 7 Conversion to SAT Plan solution is a byproduct of theorem proving Example blocks world CS 1571 Intro to AI M Hauskrecht Planning in a blocks world I I I Initial state Goal OnA Table so OnAB s OMB Table SD OMB C s OnCTable so OnC Table s ClearA so ClearB SD ClearC so ClearTable so CS 1571 Intro to AI M Hauskrecht Planning in the blocks world M Initial state 90 so On ATable so Clear A so Clear Table so OnBTableso Clear 330 OnCTablesO Clear C so Action MOVEBTableC sl DOMOVE BTableCsO OnATablesl OnBC s1 C A 51 Clear Table sl OnBTablesl Cam951 OnCTable s1 nClear C 5 SI CS 1571 Intro to AI M Hauskrecht Planning in the blocks worl I I I Q Initial state s0 s1 s2 s1 DO MOVE BTableC so 3 S1 Clear A S1 Clear Table sl OnBTablesl Clear 331 OnCTable sl Clear Csl Action MOVE ATable B 52 DOMOVE ATableB s1 DO MOVE ATable BDOMOVE BTable C 50 OnABsZ OnATablesz Clear 332 0710390952 O BTabl 3552 ClearCsz O CTable 52 Clear 1452 Clear Table sz CS 1571 Intro to AI M Hauskrecht Planning in situation calculus Planning problem Find a sequence of actions that lead to a goal Is a special type ofa search problem Planning in situation calculus is converted to theorem proving Problems 7 Large search space 7 Large number of axioms to be de ned for one action 7 Proof may not lead to the best shortest plan CS 1571 Intro to AI M Hauskrecht Planning Planning problem nd a sequence of actions that achieves some goal An instance of a search problem Methods for modeling and solving a planning problem State space search Situation calculus based on FOL 7 Inference rules 7 Resolution refutation CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 17 Inference in firstorder logic Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Logical inference in FOL Logical inference problem Given a knowledge base KB a set of sentences and a sentence a does the KB semantically entail a KB za In other words In all interpretations in which sentences in the KB are true is also 0 true Logical inference problem in the rst order logic is undecidable 11 No procedure that can decide the entailment for all possible input sentences in a nite number of steps 381571 Intro to AI M Hauskrecht Variable substitutions Variables in the sentences can be substituted with terms terms constants variables functions Substitution 7 Is represented by a mapping from variables to terms x1 t1x2 t2 7 Application of the substitution to sentences S UBST x Sam y PamLikesx y LikesSam Pam SUBSTx zy father0fJ0hnLikesxy Likesz fatherof J0hn CS 1571 Intro to AI M Hauskrecht Inference rules for quantifiers Universal elimination Vx x a 7 substitutes a variable with a constant symbol Vx Likesx IceC ream LikesBen IceC ream a is a constant symbol Existential elimination El x x a 7 Substitutes a variable with a constant symbol that does not appear elsewhere in the KB Elx Kill x Victim Kill Murderer Victim CS 1571 Intro to AI M Hauskrecht Uni cation Problem in inference Universal elimination gives many opportunities for substituting variables with ground terms Vx x a Solution Try substitutions that may help 7 Use substitutions of similar sentences in KB a is a constant symbol Uni cation 7 takes two similar sentences and computes the substitution that makes them look the same if it exists UNIFY pq 039 st SUBST o p SUBST 039q CS 1571 Intro to AI M Hauskrecht Unification Examples Uni cation UNIFY pq 039 st SUBST039p SUBST 039q Examples UNIF Y KnowsJohn x KnowsJohn Jane x Jane UNIF Y KnowsJohn x Knows y Ann x Ann y John UNIFY Knows John x Knows yM0therOf y xMotherOf John yJohn UNIFY Knows John x Knows x Elizabeth fail CS 1571 Intro to AI M Hauskrecht Generalized inference rules Use substitutions that let us make inferences Example Modus Ponens If there exists a substitution 6 such that SUBST 6 A1 SUBST on11 for all i12 11 A1 AA2 An 3 B Al39A239An39 S UBST a B Substitution that satis es the generalized inference rule can be build Via uni cation process Advantage of the generalized rules they are focused 7 only substitutions that allow the inferences to proceed CS 1571 Intro to AI M Hauskrecht Resolution inference rule Recall Resolution inference rule is sound and complete refutationcomplete for the propositional logic and CNF A v B A v C B v C Generalized resolution rule is sound and refutation complete for the rstorder logic and CNF wo equalities if unsatis able the resolution will nd the contradiction a UNIFY i 111 2 fail 1V 2 V ka W1 VVz V ln SUBSTU 1 vv i1 v i1v k vylvv1j1v1j1ln Example PXVQxa 39QJ0hnVSy PJ0hn v Sy CS 1571 Intro to AI M Hauskrecht Inference with resolution rule Proof by refutation 7 Prove that KB a is unsatis able 7 resolution is refutation complete Main procedure steps 1 Convert KB I a to CNF with ground terms and universal variables only 2 Apply repeatedly the resolution rule while keeping track and consistency of substitutions 3 Stop when empty set contradiction is derived or no more new resolvents conclusions follow CS 1571 Intro to AI M Hauskrecht Conversion to CNF 1 Eliminate implications equivalences 1v3 q gt pvq 2 Move negations inside DeMorgan s Laws double negation pAq gt pv q pr x p pvq gt p q axper p 3 Standardize variables rename duplicate variables Vx Px V 3x Qx gt Vx Px V 3y Q00 4 Move all quantifiers left no invalid capture possible Vx Px V 3y Qy gt Vx 3y Px V Qy CS 1571 Intro to AI M Hauskrecht Conversion to CNF 5 Skolemization removal of existential quanti ers through elimination If no universal quanti er occurs before the existential quanti er replace the variable with a new constant symbol 3yPAV Qy gt PAV QB If a universal quanti er precede the existential quanti er replace the variable with a function of the universal variable Vx Ely Px v Qy gt Vx Pxv QFx F x a special function called Skolem function CS 1571 Intro to AI M Hauskrecht Conversion to CNF 6 Drop universal quanti ers all variables are universally quanti ed Vx PxV QFx gt PxV QFx 7 Convert to CNF using the distributive laws pvqAr gt pvqpvr The result is a CNF with variables constants functions CS 1571 Intro to AI M Hauskrecht Resolution example KB Il 4WVQWamp QWMHWH vRWL M VsQLM yw 39PWV SW xw Zw Sw v Rw SW w A Contradiction Z CS1571ntrotoAl MHauskrecht Sentences in Horn normal form Horn normal form HNF in the propositional logic 7 a special type of clause with at most one positive literal Av B Av C VD Typically written as B 3 A A C 3 D A clause with one literal egA is also called a fact A clause representing an implication with a conjunction of positive literals in antecedent and one positive literal in consequent is also called a rule Generalized Modus ponens 7 is the complete inference rule for KBs in the Horn normal form Not all KBs are convertible to HNF ll CS 1571 Intro to AI M Hauskrecht Horn normal form in FOL First order logic FOL 7 adds variables and quanti ers works with terms Generalized modus ponens rule a a substitution st Vi SUBSTU SUBSTU i 139 239 1A 2A n31 SUBSTUT Generalized modus ponens is complete for the KBs with sentences in Horn form Not all rstorder logic sentences can be expressed in this orm CS 1571 Intro to AI M Hauskrecht Forward and backward chaining Two inference procedures based on modus ponens for Horn KBs Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Typical usage infer all sentences entailed by the existing KB Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the premises of the rule Continue recursively Typical usage If we want to prove that the target goal sentence 0 is entailed by the existing KB Both procedures are complete for KBs in Horn form CS 1571 Intro to AI M Hauskrecht Forward chaining example Forward chaining Idea Whenever the premises of a rule are satis ed infer the conclusion Continue with rules that became satis ed Assume the KB with the following rules KB R1 Steamboat xASailboat y 3 Fasterxy R2 Sailboat y A RowBoat z 3 Faster y 2 R3 FasterxyAFaster yz3 Faster xz F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow Theorem Faster Titanic PoncMrrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x A Sailboat y 3 Faster xy Sailboat y ARowBoat z 3 Faster y z 3 Faster x y A Faster y z 3 Faster x 2 F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonaL4rrow CS 1571 Intro to AI M Hauskrecht KB R1 Forward chaining example Steamboat x Sailboat y 3 Faster x y 21 Sailboat y ARowBoat z 3 Faster y 2 R3 FasterxyFasteryz3 Faster xz pa F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral CS 1571 Intro to AI M Hauskrecht KB Forward chaining example R11 Steamboat x Sailboat y 3 Faster x y 22 Sailboat y ARowBoat z 3 Faster y z 3 FasterxyFasteryz3 Faster xz F11 Steamboat T itanie F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanie Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow CS 1571 Intro to AI M Hauskrecht Forward chaining example KB R11 Steamboat x Sailboat y 3 Faster x y 21 Sailboat y ARowBoat z 3 Faster y 2 R3 FasterxyFasteryz3 Faster xz pa F11 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonal4rrow Rule R1 is satis ed F4 F asterT itanic Mistral Rule R2 is satis ed F5 F asterMistral PoncMrrow Rule R3 is satis ed F6 F asterT itanic Ponal4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Backward chaining goal reduction Idea To prove the fact that appears in the conclusion of a rule prove the antecedents if part of the rule amp repeat recursively KB R11 Steamboat x Sailboat y 3 Faster x y R21 Sailboat y ARowBoat z 3 Faster y 2 R3 FasterxyFasteryz3 Faster xz F1 Steamboat Titanic F2 Sailboat Mistral F3 RowBoatPonal4rrow Theorem Faster Titanic PoncMrrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondA rrow F1 Steamboat Titanic R1 F2 Sailboat Mistral F3 RowBoaKPondArroM SteamboaTitanic SailboatPondArrow X Steamboat x Sailboat y 3 Faster x y 39 Faster Tit ic Po rhllrrow xTitanic yPoncl4rrow CS 1571 Intro to AI M Hauskrecht Backward chaining example Faster Titanic PondArrow F1 Steamboat Titanic F22 Sailboat Mistral F3 RowBoaKPondArroM SteamboatTitanic SailboatTitanic SailboatPondArrow RWBoatPondArr0w X Sailboat y RowBoat z 3 Faster y z Faster Titanic Po rbllrrow y Titanic z PoncMrrow CS 1571 Intro to AI M Hauskrecht Backward chaining example F12 Steamboat Titanic F2 Sailboat Mistral F3 RowBoaKPondArroM Faster Titanic PondArrow SteamboatTitanic SailboatTitanic Faste yfondArmM x F asteiTitanic y Sailboat PomMrrow RowBoatPondArrow X R2 R1 SteamboatTitanic Sailb0mMlstral SailboatMistral RWBUaIltP0nMrrW CS 1571 Intro to AI M Hauskrecht Backward chaining Faster Titanic PondArrow y must be bound to the same term SteamboatTitanic ailboatTitanic Fame Pond1WD x F asterTi tani c y SailboaKPondArrow RowBo Li PondArrow X R1 SteamboatTitanic Sailb0mMlStral RowBoatPondArrow Sailbo 7Mistral CS 1571 Intro to AI M Hauskrecht Backward chaining The search tree ANDOR tree Special search algorithms exits including heuristics A0 A0 F axter Titanic Pondirrow Steamboat Titanic R2 ailboatTitamc Faste yP0ndArrm FasterTitanig y SailboatPondArmw RowBo afPondlrmw R SteamboatTitamc nglboafMsfml Saj1b7Mfm1 RowBoatPondArrow CS 1571 Intro to AI M Hauskrecht Knowledgebased system Knowledge base Inference engine Knowledge base 7 A set of sentences that describe the world in some formal representational language e g firstorder logic 7 Domain speci c knowledge Inference engine 7 A set of procedures that work upon the representational language and can infer new facts or answer KB queries eg resolution algorithm forward chaining 7 Domain independent CS 1571 Intro to AI M Hauskrecht Automated reasoning systems Examples and main differences Theorem provers 7 Prove sentences in the rstorder logic Use inference rules resolution rule and resolution refutation Deductive retrieval systems 7 Systems based on rules KBs in Horn form 7 Prove theorems or infer new assertions forward backward chaining Production systems 7 Systems based on rules with actions in antecedents 7 Forward chaining mode of operation Semantic networks 7 Graphical representation of the world objects are nodes in the graphs relations are various links CS 1571 Intro to AI M Hauskrecht Production systems Based on rules but different from KBs in the Horn form Knowledge base is divided into A Rule base includes rules A Working memory includes facts A special type of if then rule 171 A172 Ampquot 3 a1a2ak Antecedent a conjunction of literals 7 facts statements in predicate logic Consequent a conjunction of actions An action can 7 ADD the fact to the KB working memory 7 REMOVE the fact from the KB consistent with logic 7 QUERY the user etc CS 1571 Intro to AI M Hauskrecht Production systems Based on rules but different from KBs in the Horn form Knowledge base is divided into A Rule base includes rules A Working memory includes facts A special type of if then rule 171 A172 Ampquot 3 a1a2 Antecedent a conjunction of literals 7 facts statements in predicate logic Consequent a conjunction of actions An action can 7 ADD the fact to the KB working memory 7 REMOVE the fact from the KB lt Different from logic 7 QUERY the user etc ak CS 1571 Intro to AI M Hauskrecht Production systems Use forward chaining to do reasoning 7 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 R27 Conditions R27 gt Actions R27 R105 Conditions R105 1 Actions R105 Strategy for selecting the rule to be fired from among possible candidates is called con ict resolution CS 1571 Intro to AI M Hauskrecht Production systems Why is con ict resolution important Or why do we care about the order Assume that we have two rules and the preconditions of both are satis ed R1 Ax ABx ACy 3 add Dx R2 AxBxEz 3 delete Ax What can happen if rules are triggered in different order CS 1571 Intro to AI M Hauskrecht Production systems Why is con ict resolution important Or Why do we care about the order Assume that we have two rules and the preconditions of both are satis ed R1 Ax ABx ACy 3 add Dx R2 Ax Bx Ez 3 delete Ax What can happen if rules are triggered in different order 7 If Rl goes rst R2 condition is still satis ed and we infer 1300 7 If R2 goes rst we may never infer DX CS 1571 Intro to AI M Hauskrecht Production systems Problems with production systems 7 Additions and Deletions can change a set of active rules 7 If a rule contains variables testing all instances in which the rule is active may require a large number of uni cations 7 Conditions of many rules may overlap thus requiring to repeat the same uni cations multiple times Solution Rete algorithm 7 gives more ef cient solution for managing a set of active rules and performing uni cations 7 Implemented in the system OPS 5 used to implement XCON 7 an expert system for con guration of DEC computers CS 1571 Intro to AI M Hauskrecht Rete algorithm Assume a set of rules Ax A Bx A Cy 3 add Dx AxAByADx 3 add Ex Ax A Bx A Ez 3 delete Ax Andfm A0A2B2B3B4C5 Rete 7 Compiles the rules to a network that merges conditions of multiple rules together avoid repeats 7 Propagates valid uni cations 7 Reevaluates only changed conditions CS 1571 Intro to AI M Hauskrecht Rete algorithm Network Rules AgtC 2mm Cy 2 add 132 AgtC 3002 132 2 add 52 AgtC BgtC 52 2 2121222 42 Fm A1A2 22 23 B4cs 251511 mm m MINI15km Con ict resolution strategies Problem Two or more rules are active at the same time Which one to execute next Solutions 2 No duplication do not execute the same rule twice 2 Recency Rules referring to facts newly added to the working memory take precedence 2 Speci city Rules that are more speci c are preferred 2 Priority levels Define priority ofrules actions based on expert opinion Have multiple priority levels such that the higher priority rules fire first 251511 mm m MINI15km Semantic network systems Knowledge about the world described in terms of graphs Nodes correspond to 7 Concepts or objects in the domain Links to relations Three kinds 7 subset links 0521 pan OfIinks Inheritance relation links 7 Member links instance links 7 Function links Can be transformed to the rstorder logic language Graphical representation is often easier to work with 7 better overall View on individual concepts and relations CS 1571 Intro to AI M Hauskrecht Semantic network Example Trans ortson EI isa isa Ocean liner Oil tanker Engine 9 9 1513M member member is39pan Swimming Queen Boiler pool Mary Inferred properties Queen Mary is a ship Queen Mary has a boiler Exxon Valdez CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 21 Planning STRIPS Milos Hauskrecht miloscspittedu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Planning Planning problem nd a sequence of actions that achieves some goal An instance of a search problem Methods for modeling and solving a planning problem State space search Situation calculus based on FOL 7 Inference rules 7 Resolution refutation 381571 Intro to AI M Hauskrecht Planning problems Properties of real world planning problems The description of the state of the world is very complex Many possible actions to apply in any step Actions are typically local 7 they affect only a small portion of a state description Goals are de ned as conditions and refer only to a small portion of state Plans consists of a long sequence of actions The state space search and situation calculus frameworks may be too cumbersome and inefficient to represent and solve the planning problems CS 1571 Intro to AI M Hauskrecht Situation calculus problems Frame problem refers to The need to represent a large number of frame axioms Solution combine positive and negative effects in one rule Onu vDO MOVE x y 2 3 ltgt 7u x A v y A Onuvs v v u x A v 2 A Onx ys A Clear xs A Clear 23 Inferential frame problem 7 We still need to derive properties that remain unchanged Other problems Quali cation problem 7 enumeration of all possibilities under which an action holds Rami cation problem 7 enumeration of all inferences that follow from some facts CS 1571 Intro to AI M Hauskrecht Solutions Complex state description and local action effects 7 avoid the enumeration and inference of every state component focus on changes only Many possible actions 7 Apply actions that make progress towards the goal 7 Understand what the effect of actions is and reason with the consequences Sequences of actions in the plan can be too long 7 Many goals consists of independent or nearly independent subgoals 7 Allow goal decomposition amp divide and conquer strategies CS 1571 Intro to AI M Hauskrecht STRIPS planner De nes a restricted representation language as compared to the situation calculus Advantage leads to more ef cient planning algorithms 7 Statespace search with structured representations of states actions and goals 7 Action representation avoids the frame problem STRIPS planning problem much like a standard search planning problem CS 1571 Intro to AI M Hauskrecht STRIPS planner States 7 conjunction of literals eg OnAB OMB Table ClearA 7 represent facts that are true at a speci c point in time Actions operators 7 Action Move xyz 7 Preconditions conjunctions of literals with variables Onxy Clearx Clearz 7 Effects Two lists Add list Onxz Cleary Delete list Onxy Clearz Everything else remains untouched is preserved CS 1571 Intro to AI M Hauskrecht STRIPS planning Operator Move xyz Preconditions Onxy Clearx Clearz Add list Onxz Cleary Delete list Onxy Clearz mm 9 Move BTableC OnBTable add OnBC Clear C Q OnATable OnATable OnCTable OnCTable gear Egg m gear Egg ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht STRIPS planning Initial state Conjunction of literals that are true Goals in STRIPS A goal is a partially speci ed state Is defined by a conjunction of ground literals 7 No variables allowed in the description of the goal Example OnAB OnBC CS 1571 Intro to AI M Hauskrecht Search in STRIPS Objective Find a sequence of operators a plan from the initial state to the state satisfying the goal Two approaches to build a plan Forward state space search goal progression 7 Start from what is known in the initial state and apply operators in the order they are applied Backward state space search goal regression 7 Start from the description of the goal and identify actions that help to reach the goal CS 1571 Intro to AI M Hauskrecht Forward search goal progression Idea Given a state s 7 Unify the preconditions of some operator at with s 7 Add and delete sentences from the add and delete list of an operator at from s to get a new state I I I Move BTableC OnBTable add Clear C delete OnATable OnATable OnCTable OnCTable gear Egg m gear Egg ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M H goal Move A Table B Initial state Move B Table C llIove ATable C Ov CS 1571 Intro to AI M Hauskrecht Backward search goal regression Idea Given a goal G Unify the add list of some operator at with a subset of G If the delete list of a does not remove elements of G then the goal regresses to a new goal G that is obtained from G by 7 deleting add list of a 7 adding preconditions of a E q E M0veATableB New goal G Goal G On A Table Clear B precondition vhem1152 Clear A OnBC OquotB C OnCTable 0 CaTable Mapped from G CS 1571 Intro to AI M Hauskrecht Backward search goal regression Use operators to generate new goals Check whether the initial state satis es the goal Search tree 395 5 Initial state Move BTable C Move A Table B goal Move A B Table CS 1571 Intro to AI M Hauskrecht Statespace search Forward and backward state space planning approaches 7 Work with strictly linear sequences of actions Disadvantages 7 They cannot take advantage of the problem decompositions in which the goal we want to reach consists of a set of independent or nearly independent sub goals 7 Action sequences cannot be built from the middle 7 No mechanism to represent least commitment in terms of the action ordering CS 1571 Intro to AI M Hauskrecht Divide and conquer Divide and conquer strategy 7 divide the problem to a set of smaller subproblems 7 solve each subproblem independently 7 combine the results to form the solution In planning we would like to satisfy a set of goals Divide and conquer in planning 7 Divide the planning goals along individual goals 7 Solve nd a plan for each of them independently 7 Combine the plan solutions in the resulting plan Is it always safe to use divide and conquer 7 No There can be interacting goals CS 1571 Intro to AI M Hauskrecht Sussman s anomaly An example from the blocks world in which the divide and conquer fails due to interacting goals n Initial state Goal OnAB OnBC CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst M H q 1339 Initial state But now we cannot satisfy On B C without undoing On A B CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst Initial state But now we cannot satisfy On B C without undoing On A B 2 Assume we want to satisfy 0quot B C rst H quot Initial state But now we cannot satisfy 0quot A B without undoing 0quot B C CS 1571 Intro to AI M Hauskrecht State space vs plan space search An alternative to planning algorithms that search states con gurations of world Plan De nes a sequence of operators to be performed Paltial plan 7 plan that is not complete Some plan steps are missing 7 some orderings of operators are not nalized Only relative order is given Bene ts of working with partial plans 7 We do not have to build the sequence from the initial state or the goal 7 We do not have to commit to a speci c action sequence 7 We can work on subgoals individually divide and conquer CS 1571 Intro to AI M Hauskrecht Statespace vs planspace search State space search STRIPS operator State set of formulas Plan space search Finish Plan transformation Start Incomplete partial plan CS 1571 Intro to AI M Hauskrecht Plan transformation operators Examples of Add an operator to a plan Mov eAxB start goal so that it satis es some open condition Add link instantiate t rt M0V9AHBf l s a goa oveCA amp Order reorder operators l CS 1571 Intro to AI M Hauskrecht Partialorder planners POP also called Non linear planners Use STRIPS operators Graphical representation of an operator Movexyz add list preconditions Delete list is not shown ll Illustration of a POP on the Sussman s anomaly case CS 1571 Intro to AI M Hauskrecht Partial order planning Start and finish Goal I Start M Hauskrecht CS 1571 Intro to AI Partial order planning Start and finish Goal Open conditions conditions yet to be satis ed m Start M H M Hauskrecht CS 1571 Intro to AI Partial order planning Add operator El Goal We want to satisfy an open Movemy condition OnAy Always select an operator that helps to satisfy one of the open conditions H Start 5 M Hauskrecht CS 1571 Intro to AI Partial order planning Add link El Goal I Start ME CS 1571 Intro to AI M Hauskrecht Partial order planning Add link El Goal Add link Satis es an open condition H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add link Goal Satis es an open condition instantiates y F1 Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links El Start 1 5 CS 1571 Intro to AI M Hauskrecht Deletes ClearB A was stacked on B t a sum I l CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators El MoveBFlC comes before MoveAFlB Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El MoveBF1C F t H w Stan 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links A I E MoveBFlC 0110351 CleaIC II I C m I I CS 1571 Intro to AI M Hauskrecht Partial order planning Threats El A Cl earC CleaIFl El a w Start I I CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators MoveBF1C OnBF1 CS 1571 Intro to AI M Hauskrecht r w CS 1571 Intro to AI M Hauskrecht MoveBF1C OnBFl CS 1571 Intro to AI M Hauskrecht Partial order planning Result plan Plan a topological son of a graph CS 1571 Intro to AI M Hauskrecht Partial order planning Remember we search the space of partial plans Start Incomplete partial plan POP is sound and complete CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 21 Planning STRIPS Milos Hauskrecht miloscspittedu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Planning Planning problem nd a sequence of actions that achieves some goal An instance of a search problem Methods for modeling and solving a planning problem State space search Situation calculus based on FOL 7 Inference rules 7 Resolution refutation 381571 Intro to AI M Hauskrecht Planning problems Properties of real world planning problems The description of the state of the world is very complex Many possible actions to apply in any step Actions are typically local 7 they affect only a small portion of a state description Goals are de ned as conditions and refer only to a small portion of state Plans consists of a long sequence of actions The state space search and situation calculus frameworks may be too cumbersome and inefficient to represent and solve the planning problems CS 1571 Intro to AI M Hauskrecht Situation calculus problems Frame problem refers to The need to represent a large number of frame axioms Solution combine positive and negative effects in one rule Onu vDO MOVE x y 2 3 ltgt 7u x A v y A Onuvs v v u x A v 2 A Onx ys A Clear xs A Clear 23 Inferential frame problem 7 We still need to derive properties that remain unchanged Other problems Quali cation problem 7 enumeration of all possibilities under which an action holds Rami cation problem 7 enumeration of all inferences that follow from some facts CS 1571 Intro to AI M Hauskrecht Solutions Complex state description and local action effects 7 avoid the enumeration and inference of every state component focus on changes only Many possible actions 7 Apply actions that make progress towards the goal 7 Understand what the effect of actions is and reason with the consequences Sequences of actions in the plan can be too long 7 Many goals consists of independent or nearly independent subgoals 7 Allow goal decomposition amp divide and conquer strategies CS 1571 Intro to AI M Hauskrecht STRIPS planner De nes a restricted representation language as compared to the situation calculus Advantage leads to more ef cient planning algorithms 7 Statespace search with structured representations of states actions and goals 7 Action representation avoids the frame problem STRIPS planning problem much like a standard search planning problem CS 1571 Intro to AI M Hauskrecht STRIPS planner States 7 conjunction of literals eg OnAB OMB Table ClearA 7 represent facts that are true at a speci c point in time Actions operators 7 Action Move xyz 7 Preconditions conjunctions of literals with variables Onxy Clearx Clearz 7 Effects Two lists Add list Onxz Cleary Delete list Onxy Clearz Everything else remains untouched is preserved CS 1571 Intro to AI M Hauskrecht STRIPS planning Operator Move xyz Preconditions Onxy Clearx Clearz Add list Onxz Cleary Delete list Onxy Clearz mm 9 Move BTableC OnBTable add OnBC Clear C Q OnATable OnATable OnCTable OnCTable gear Egg m gear Egg ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht STRIPS planning Initial state Conjunction of literals that are true Goals in STRIPS A goal is a partially speci ed state Is defined by a conjunction of ground literals 7 No variables allowed in the description of the goal Example OnAB OnBC CS 1571 Intro to AI M Hauskrecht Search in STRIPS Objective Find a sequence of operators a plan from the initial state to the state satisfying the goal Two approaches to build a plan Forward state space search goal progression 7 Start from what is known in the initial state and apply operators in the order they are applied Backward state space search goal regression 7 Start from the description of the goal and identify actions that help to reach the goal CS 1571 Intro to AI M Hauskrecht Forward search goal progression Idea Given a state s 7 Unify the preconditions of some operator at with s 7 Add and delete sentences from the add and delete list of an operator at from s to get a new state I I I Move BTableC OnBTable add Clear C delete OnATable OnATable OnCTable OnCTable gear Egg m gear Egg ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M H goal Move A Table B Initial state Move B Table C llIove ATable C Ov CS 1571 Intro to AI M Hauskrecht Backward search goal regression Idea Given a goal G Unify the add list of some operator at with a subset of G If the delete list of a does not remove elements of G then the goal regresses to a new goal G that is obtained from G by 7 deleting add list of a 7 adding preconditions of a E q E M0veATableB New goal G Goal G On A Table Clear B precondition vhem1152 Clear A OnBC OquotB C OnCTable 0 CaTable Mapped from G CS 1571 Intro to AI M Hauskrecht Backward search goal regression Use operators to generate new goals Check whether the initial state satis es the goal Search tree 395 5 Initial state Move BTable C Move A Table B goal Move A B Table CS 1571 Intro to AI M Hauskrecht Statespace search Forward and backward state space planning approaches 7 Work with strictly linear sequences of actions Disadvantages 7 They cannot take advantage of the problem decompositions in which the goal we want to reach consists of a set of independent or nearly independent sub goals 7 Action sequences cannot be built from the middle 7 No mechanism to represent least commitment in terms of the action ordering CS 1571 Intro to AI M Hauskrecht Divide and conquer Divide and conquer strategy 7 divide the problem to a set of smaller subproblems 7 solve each subproblem independently 7 combine the results to form the solution In planning we would like to satisfy a set of goals Divide and conquer in planning 7 Divide the planning goals along individual goals 7 Solve nd a plan for each of them independently 7 Combine the plan solutions in the resulting plan Is it always safe to use divide and conquer 7 No There can be interacting goals CS 1571 Intro to AI M Hauskrecht Sussman s anomaly An example from the blocks world in which the divide and conquer fails due to interacting goals n Initial state Goal OnAB OnBC CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst M H q 1339 Initial state But now we cannot satisfy On B C without undoing On A B CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst Initial state But now we cannot satisfy On B C without undoing On A B 2 Assume we want to satisfy 0quot B C rst H quot Initial state But now we cannot satisfy 0quot A B without undoing 0quot B C CS 1571 Intro to AI M Hauskrecht State space vs plan space search An alternative to planning algorithms that search states con gurations of world Plan De nes a sequence of operators to be performed Paltial plan 7 plan that is not complete Some plan steps are missing 7 some orderings of operators are not nalized Only relative order is given Bene ts of working with partial plans 7 We do not have to build the sequence from the initial state or the goal 7 We do not have to commit to a speci c action sequence 7 We can work on subgoals individually divide and conquer CS 1571 Intro to AI M Hauskrecht Statespace vs planspace search State space search STRIPS operator State set of formulas Plan space search Finish Plan transformation Start Incomplete partial plan CS 1571 Intro to AI M Hauskrecht Plan transformation operators Examples of Add an operator to a plan Mov eAxB start goal so that it satis es some open condition Add link instantiate t rt M0V9AHBf l s a goa oveCA amp Order reorder operators l CS 1571 Intro to AI M Hauskrecht Partialorder planners POP also called Non linear planners Use STRIPS operators Graphical representation of an operator Movexyz add list preconditions Delete list is not shown ll Illustration of a POP on the Sussman s anomaly case CS 1571 Intro to AI M Hauskrecht Partial order planning Start and finish Goal I Start M Hauskrecht CS 1571 Intro to AI Partial order planning Start and finish Goal Open conditions conditions yet to be satis ed m Start M H M Hauskrecht CS 1571 Intro to AI Partial order planning Add operator El Goal We want to satisfy an open Movemy condition OnAy Always select an operator that helps to satisfy one of the open conditions H Start 5 M Hauskrecht CS 1571 Intro to AI Partial order planning Add link El Goal I Start ME CS 1571 Intro to AI M Hauskrecht Partial order planning Add link El Goal Add link Satis es an open condition H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add link Goal Satis es an open condition instantiates y F1 Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links El Start 1 5 CS 1571 Intro to AI M Hauskrecht Deletes ClearB A was stacked on B t a sum I l CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators El MoveBFlC comes before MoveAFlB Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El MoveBF1C F t H w Stan 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links A I E MoveBFlC 0110351 CleaIC II I C m I I CS 1571 Intro to AI M Hauskrecht Partial order planning Threats El A Cl earC CleaIFl El a w Start I I CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators MoveBF1C OnBF1 CS 1571 Intro to AI M Hauskrecht r w CS 1571 Intro to AI M Hauskrecht MoveBF1C OnBFl CS 1571 Intro to AI M Hauskrecht Partial order planning Result plan Plan a topological son of a graph CS 1571 Intro to AI M Hauskrecht Partial order planning Remember we search the space of partial plans Start Incomplete partial plan POP is sound and complete CS 1571 Intro to AI M Hauskrecht CS 1571 Introduction to AI Lecture 10 Multi layer neural networks Milos Hauskrecht miloscspittedu 5329 Sennott Square CS 1571 Intro to AI Linear units Linear regression Logistic regression fxwa fxpy1xwgWTX 1 W f X 2 99 W fX f Py1x 9 I w xd xd Gradient update Gradient update w ew 0129 fx1xl The same w ew 0129 fX1X1 0 W PW i39aO fxx 0nlim w ew ay fxx CS 1571 Intro to AI Limitations of basic linear units Linear regression d fx w0 2 wjxj 11 1 x1 w 2 fx W X xd Function linear in inputs Logistic regression fx1vy1xwgw0 ijxj 2 f z Py1x O 39 Linear decision boundary CS 1571 Intro to AI Extensions of simple linear units use feature basis functions to model nonlinearities Linear regression m mm2wn X Logistic regression m m mzw an arbitrary function of x CS 1571 Intro to AI Regression with a quadratic model cs 1571 1mm m A1 Quadratic decision boundary cs 1571 1mm m A1 Multilayered neural networks Offer an alternative way to introduce nonlinearities to regressionclassi cation models Idea Cascade several simple logistic regression units Motivation from a neuron and synaptic connections mm mmvmmmv Axum 111111191111 11 mm 11 sum cs 1571 1mm m Al Model of a neuron Axunal mmrllauun am My Huollvorcvll Symypse swam Cell may or Scum Thr eshold func on cs 1571 1mm m Al Multilayer neural network Also called a multilayer perceptron MLP Cascades multiple logistic regression units Example a 2 layer classi er with nonlinear decision boundaries 1 212 f py1lx Hidden layer Output layer Input layer CS 1571 Intro to AI Multilayer neural network Models non linearities through logistic regression units Can be applied to both regression and biliary classi cation problems Input layer Hidden layer Output layer regression f X f KW gt classi cation ffxPy1lXgtW 0 option CS 1571 Intro to AI Multilayer neural network Non linearities are modeled using multiple hidden logistic regression units organized in layers Output layer determines whether it is a regression and binary classi cation problem InPut layer Hidden layers Output layer regreSSlon fXfXW x1 x2 classi cation xd ffxPy1iXgtW option CS 1571 Intro to AI Learning with MLP How to learn the parameters of the neural network Gradient descent algorithm On line version Weight updates are based on J mum DZ w B W e Waa J0nlineDzW w We need to compute gradients for weights in all units Can be computed in one backward sweep through the net ll 4 The process is called back propagation CS 1571 Intro to AI Backpropagation k1th leve1 kth level k lth level xjk l xlk 1 x UC output of the unit i on level k 2 06 input to the sigmoid function on level k Mir16 weight between unitsj and i on levels kl and k 2 06 W okZW jkxjk 1 W gzk j CS 15711ntro to AI Backpropagation Update weight w j k using a data point Du lt x y gt Mirk F Wljk 05WJWWDWW 5 k J D Let l BZ UC anlme WW D w3JanzmDwW 34k LJ 3w k W 32 k 3w k Then Slick14 St 20 is computed fromx k and the next layer 61k1 5 06 51k1wzlk1 x k1 xlk 1 Last unit is the same as for the regular linear units 5K yfXW It is the same for the classi cation with the loglikelihood measure of t and linear regression with leastsquares error CS 15711ntro to AI Learning with MLP Online gradient descent algorithm 7 Weight update wwke wwk a wa Ljonline 9le k DWW 2 MW wa 821k a wa k Jaw a k wa k 6 kw k 1 wwk e wwk a51kxjk 1 x k 1 jth output ofthe k 1 layer 5106 derivative computed via backpropagation a a learning rate CS 15711ntro to AI Online gradient descent algorithm for MLP Online gradient descent D number of iterations Initialize all weights WW k for 1391139 number ofiteratz39ons do select a data point Dultxygt from D set a 1 139 compute outputs x J k for each unit compute derivatives 51 kvia backpropagation update all weights in parallel wwk e wwk a lkxjk 1 end for return weights w CS 15711ntro to AI ix 3 95 2 m0 5 it sas v ar ix 55 may 33 55 a nku mm gg a A 5 4 25 fl 4IPEF 5 555 23 t f g 55 It tii i f f f g gg g Ep g f Av i a 5 2 53 63828 X 3 3 95 2 m0 bmwason39 E5803 Son OZ oEEnxm EX Xor example Neural network With 2 hidden units R N K a CS 15711ntro to AI Xor example Neural network With 10 hidden units CS 15711ntro to AI Problems with learning MLPs Decision about the number of units must be made in advance Converges to local optima Sensitive to initial set of weights CS 15711ntro to AI MLP in practice Optical character recognition 7 digits 20x20 7 Automatic sorting of mails 7 5 layer network with multiple output functions 10 outputs 019 layer Neurons Weights 5 10 3000 4 300 1200 3 1200 50000 2 784 3136 1 3136 78400 20x20 400 inputs CS 15711ntro to AI CS 1571 Introduction to AI Lecture 19 Planning STRIPS Milos Hauskrecht milos cspitt edu 5329 Sennott Square 381571 Intro to AI M Hauskrecht Competition results Simulated annealing competition 1 Nathaniel Wetzel 2 David Bradley 3 Francesco DeSensi Extra credit 381571 Intro to AI M Hauskrecht Planning Planning problem nd a sequence of actions that achieves some goal an instance of a search problem the state description is very complex Methods for modeling and solving a planning problem State space search Situation calculus based on FOL 7 Typically Resolution refutation CS 1571 Intro to AI M Hauskrecht Planning problems Properties of real world planning problems The description of the state of the world is very complex Many possible actions to apply in any step Actions are typically local 7 they affect only a small portion of a state description Goals are defined as conditions and refer only to a small portion of state Plans consists of a long sequence of actions The state space search and situation calculus frameworks may be too cumbersome and inefficient to represent and solve planning problems CS 1571 Intro to AI M Hauskrecht Situation calculus problems Frame problem refers to The need to represent a large number of frame axioms Solution combine positive and negative effects in one rule Onu vDO MOVE x y 2 3 ltgt 7u x A v y A Onuvs v v u x A v 2 A Onx ys A Clear xs A Clear 23 Inferential frame problem 7 We still need to derive properties that remain unchanged Other problems Quali cation problem 7 enumeration of all possibilities under which an action holds Rami cation problem 7 enumeration of all inferences that follow from some facts CS 1571 Intro to AI M Hauskrecht Solutions Complex state description and local action effects 7 avoid the enumeration and inference of every state component focus on changes only Many possible actions 7 Apply only actions that make progress towards the goal 7 Understand what the effect of actions is and reason with the consequences Sequences of actions in the plan can be too long 7 Many goals consists of independent or nearly independent subgoals 7 Allow goal decomposition amp divide and conquer strategies CS 1571 Intro to AI M Hauskrecht STRIPS planner De nes a restricted FOL representation language as compared to the situation calculus Advantage leads to more efficient planning algorithms 7 Statespace search with structured representations of states actions and goals 7 Action representation avoids the frame problem STRIPS planning problem much like a standard search problem CS 1571 Intro to AI M Hauskrecht STRIPS planner States 7 conjunction of literals eg OnAB OMB Table ClearA 7 represent facts that are true at a specific point in time Actions operators 7 Action Move xyz 7 Preconditions conjunctions of literals with variables Onxy Clearx Clearz 7 Effects Two lists Add list Onxz Cleary Delete list Onxy Clearz Everything else remains untouched is preserved CS 1571 Intro to AI M Hauskrecht STRIPS planning Operator Move xyz Preconditions Onxy Clearx Clearz Add list Onxz Cleary Delete list Onxy Clearz I I I I I Move BTableC OnBTable add Clear C delete OnATable OnATable OnCTable OnCTable Clear A m Clear A Clear B Clear B Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht STRIPS planning Initial state Conjunction of literals that are true Goals in STRIPS A goal is a partially speci ed state Is defined by a conjunction of ground literals 7 N0 variables allowed in the description of the goal Example OnAB OnBC CS 1571 Intro to AI M Hauskrecht Search in STRIPS Objective Find a sequence of operators a plan from the initial state to the state satisfying the goal Two approaches to build a plan Forward state space search goal progression 7 Start from what is known in the initial state and apply operators in the order they are applied Backward state space search goal regression 7 Start from the description of the goal and identify actions that help to reach the goal CS 1571 Intro to AI M Hauskrecht Forward search goal progression Idea Given a state s 7 Unify the preconditions of some operator at with s 7 Add and delete sentences from the add and delete list of an operator at from s to get a new state mm 9 Move BTableC OnBTable add OnBC Clear C Q OnATable OnATable OnCTable OnCTable gear Egg m gear 831 ear ear Clear Table Clear Table CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M E goal Move A Table B Move B Table C llIove ATable C lt Initial state CS 1571 Intro to AI M Hauskrecht Forward search goal progression Use operators to generate new states to search Check new states whether they satisfy the goal Search tree E E M H goal Move A Table B Move B Table C Move ATable C Olt Heuristics Initial state CS 1571 Intro to AI M Hauskrecht Backward search goal regression Idea Given a goal G Unify the add list of some operator at with a subset of G If the delete list of a does not remove elements of G then the goal regresses to a new goal G that is obtained from G by 7 deleting add list of a 7 adding preconditions of a E El M0veATableB New goal G Goal G On A Table Clear B precondition vhem1152 Clear A OnBC OquotB C OnCTable 0 CaTable Mapped from G CS 1571 Intro to AI M Hauskrecht Backward search goal regression Use operators to generate new goals Check whether the initial state satis es the goal Search tree 395 5 Initial state Move BTable C Move A Table B goal Move A B Table CS 1571 Intro to AI M Hauskrecht Statespace search Forward and backward state space planning approaches 7 Work with strictly linear sequences of actions m Disadvantages M 7 They cannot take advantage of the problem decompositions in which the goal we want to reach consists of a set of independent or nearly independent sub goals 7 Action sequences cannot be built from the middle 7 No mechanism to represent least commitment in terms of the action ordering CS 1571 Intro to AI M Hauskrecht Divide and conquer Divide and conquer strategy 7 divide the problem to a set of smaller subproblems 7 solve each subproblem independently 7 combine the results to form the solution In planning we would like to satisfy a set of goals Divide and conquer in planning 7 Divide the planning goals along individual goals 7 Solve nd a plan for each of them independently 7 Combine the plan solutions in the resulting plan Is it always safe to use divide and conquer 7 No There can be interacting goals CS 1571 Intro to AI M Hauskrecht Sussman s anomaly An example from the blocks world in which the divide and conquer fails due to interacting goals gt Initial state Goal OnAB OnBC CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst M H q 1339 Initial state But now we cannot satisfy On B C without undoing On A B CS 1571 Intro to AI M Hauskrecht Sussman s anomaly 1 Assume we want to satisfy On A B rst Initial state But now we cannot satisfy On B C without undoing On A B 2 Assume we want to satisfy 0quot B C rst H quot Initial state But now we cannot satisfy 0quot A B without undoing 0quot B C CS 1571 Intro to AI M Hauskrecht State space vs plan space search An alternative to planning algorithms that search states con gurations of world Plan De nes a sequence of operators to be performed Paltial plan 7 plan that is not complete Some plan steps are missing 7 some orderings of operators are not nalized Only relative order is given Bene ts of working with partial plans 7 We do not have to build the sequence from the initial state or the goal 7 We do not have to commit to a speci c action sequence 7 We can work on subgoals individually divide and conquer CS 1571 Intro to AI M Hauskrecht Statespace vs planspace search State space search STRIPS operator State set of formulas Plan space search Finish Plan transformation Start Incomplete partial plan CS 1571 Intro to AI M Hauskrecht Plan transformation operators Examples of Add an operator to a plan Mov eAxB start goal so that it satis es some open condition Add link instantiate t rt M0V9AHBf l s a goa oveCA amp Order reorder operators l CS 1571 Intro to AI M Hauskrecht Partialorder planners POP also called Non linear planners Use STRIPS operators Graphical representation of an operator Movexyz add list preconditions Delete list is not shown ll Illustration of a POP on the Sussman s anomaly case CS 1571 Intro to AI M Hauskrecht Partial order planning Start and finish Goal I Start M Hauskrecht CS 1571 Intro to AI Partial order planning Start and finish Goal Open conditions conditions yet to be satis ed m Start M H M Hauskrecht CS 1571 Intro to AI Partial order planning Add operator El Goal We want to satisfy an open Movemy condition OnAy Always select an operator that helps to satisfy one of the open conditions H Start 5 M Hauskrecht CS 1571 Intro to AI Partial order planning Add link El Goal I Start ME CS 1571 Intro to AI M Hauskrecht Partial order planning Add link El Goal Add link Satis es an open condition H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add link Goal Satis es an open condition instantiates y F1 Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El H Start 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links El Start 1 5 CS 1571 Intro to AI M Hauskrecht Deletes ClearB A was stacked on B t a sum I l CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators El MoveBFlC comes before MoveAFlB Start M 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add operator El MoveBF1C F t H w Stan 5 CS 1571 Intro to AI M Hauskrecht Partial order planning Add links A I E MoveBFlC 0110351 CleaIC II I C m I I CS 1571 Intro to AI M Hauskrecht Partial order planning Threats El A Cl earC CleaIFl El a w Start I I CS 1571 Intro to AI M Hauskrecht Partial order planning Order operators MoveBF1C OnBF1 CS 1571 Intro to AI M Hauskrecht 1 w CS 1571 Intro to AI M Hauskrecht MoveBF1C OnBFl CS 1571 Intro to AI M Hauskrecht Partial order planning Result plan Plan a topological son of a graph CS 1571 Intro to AI M Hauskrecht Partial order planning Remember we search the space of partial plans Start Incomplete partial plan POP is sound and complete CS 1571 Intro to AI M Hauskrecht

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.