CS 416 Artificial Intelligence Lecture Lecture 12 12 Logical Logical Agents Agents Chapter Chapter 77 Midterm Exam Midterm Midterm will will be be on on Thursday Thursday March March 13 13thth ItIt will will cover cover material material up up until until Feb Feb 27 27thth Propositional Logic We re We re still still emphasizing emphasizing Propositional Propositional Logic Logic Very Very important important question question with with this this method method Does Does knowledge knowledge base base of of propositional propositional logic logic satisfy satisfy aa particular particular proposition proposition Can Can we we generate generate some some sequence sequence of of resolutions resolutions that that prove prove aa proposition proposition is is possible possible Backtracking Another Another way way representation representation for for searching searching Problem Problem to to solve solve is is in in CNF CNF Is Is Marvin Marvin aa Martian Martian given given M M 11 true true Marvin Marvin is is green green G 1 G 1 Marvin Marvin is is little little L 1 L 1 little little and and green green implies implies Martian Martian L L G G M M L G L G V VM M L L V V G G V VM M 11 Make sure you understand this logic Proof Proof by by contradiction contradiction are are there there true false true false values values for for G G L L and and M M that that are are consistent consistent with with knowledge knowledge base base and and Marvin Marvin not not being being aa Martian Martian G G LL L L V V G G V V M M M M 0 0 Searching for variable values Want Want to to find find values values such such that that G L L V G V M M 0 Randomly Randomly consider consider all all true false true false assignments assignments to to variables variables until until we we exhaust exhaust them them all all or or find find match match G G L L M M 1 1 0 0 0 0 no no 0 0 1 1 0 0 no no 0 0 0 0 0 0 no no 1 1 1 1 0 0 no no Alternatively Alternatively Searching for variable values Davis Putnam Davis Putnam Algorithm Algorithm DPLL DPLL Search Search through through possible possible assignments assignments to to G G L L M M via via depth depth first first search search 0 0 0 0 0 0 to to 0 0 0 0 1 1 to to 0 0 1 1 0 0 G Each Each clause clause of of CNF CNF must must be be true true L M Terminate Terminate consideration consideration when when clause clause evaluates evaluates to to false false Use Use heuristics heuristics to to reduce reduce repeated repeated computation computation of of propositions propositions Early Early termination termination Pure Pure symbol symbol heuristic heuristic Unit Unit clause clause heuristic heuristic Searching for variable values Other ways to find G L M assignments for G L L V G V M M 0 Simulated Annealing WalkSAT Start with initial guess 0 1 1 Evaluation metric is the number of clauses that evaluate to true Move in direction of guesses that cause more clauses to be true Many local mins use lots of randomness WalkSAT termination How How do do you you know know when when simulated simulated annealing annealing is is done done No No way way to to know know with with certainty certainty that that an an answer answer is is not not possible possible Could Could have have been been bad bad luck luck Could Could be be there there really really is is no no answer answer Establish Establish aa max max number number of of iterations iterations and and go go with with best best answer answer to to that that point point So how well do these work Think Think about about itit this this way way 16 16 of of 32 32 possible possible assignments assignments are are models models are are satisfiable satisfiable for for this this sentence sentence Therefore Therefore 22 random random guesses guesses should should find find aa solution solution WalkSAT WalkSAT and and DPLL DPLL should should work work quickly quickly What about more clauses IfIf symbols symbols variables variables stays stays the the same same but but number number of of clauses clauses increases increases More More ways ways for for an an assignment assignment to to fail fail on on any any one one clause clause More More searching searching through through possible possible assignments assignments is is needed needed Let s Let s create create aa ratio ratio m n m n to to measure measure clauses clauses symbols symbols We We expect expect large large m n m n causes causes slower slower solution solution What about more clauses Higher Higher m n m n means means fewer fewer assignments assignments will will work work IfIf fewer fewer assignments assignments work work itit is is harder harder for for DPLL DPLL and and WalkSAT WalkSAT Combining it all 4x4 4x4 Wumpus Wumpus World World The The physics physics of of the the game game At At least least one one wumpus wumpus on on board board A A most most one one wumpus wumpus on on board board for for any any two two squares squares one one is is free free n n 1 2 n n 1 2 rules rules like like W W1 1 V W W1 2 1 1 V 1 2 Total Total of of 155 155 sentences sentences containing containing 64 64 distinct distinct symbols symbols Wumpus World Inefficiencies Inefficiencies as as world world becomes becomes large large Knowledge Knowledge base base must must expand expand ifif size size of of world world expands expands Preferred Preferred to to have have sentences sentences that that apply apply to to all all squares squares We We brought brought this this subject subject up up last last week week Next Next chapter chapter addresses addresses this this issue issue