CS 416 Artificial Intelligence Lecture Lecture 10 10 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 Chess Article Garry Garry Kasparov Kasparov reflects reflects on on computerized computerized chess chess IBM IBM should should have have released released the the contents contents of of Deep Deep Blue Blue to to chess chess community community to to advance advance research research of of computation computation as as itit relates relates to to chess chess Kudos Kudos to to Deep Deep Junior Junior for for putting putting information information in in public public domain domain so so state state of of the the art art can can advance advance Deep Deep Blue Blue made made one one good good move move the the surprised surprised Kasparov Kasparov though though he he thinks thinks aa person person was was in in the the loop loop Deep Deep Junior Junior made made aa fantastic fantastic sacrifice sacrifice that that reflects reflects aa new new accomplishment accomplishment for for computerized computerized chess chess http www opinionjournal com extra id 110003081 http www opinionjournal com extra id 110003081 Logical Agents What What are are we we talking talking about about logical logical Aren t Aren t search based search based chess chess programs programs logical logical Yes Yes but but knowledge knowledge is is used used in in aa very very specific specific way way Win Win the the game game Not Not useful useful for for extracting extracting strategies strategies or or understanding understanding other other aspects aspects of of chess chess We We want want to to develop develop more more general purpose general purpose knowledge knowledge systems systems that that support support aa variety variety of of logical logical analyses analyses Why study knowledge based agents Partially Partially observable observable environments environments combine combine available available information information percepts percepts with with general general knowledge knowledge to to select select actions actions Natural Natural Language Language Language Language is is too too complex complex and and ambiguous ambiguous Problem solving Problem solving agents agents are are impeded impeded by by high high branching branching factor factor Flexibility Flexibility Knowledge Knowledge can can be be reused reused for for novel novel tasks tasks New New knowledge knowledge can can be be added added to to improve improve future future performance performance Components of knowledge based agent Knowledge Knowledge Base Base Store Store information information knowledge knowledge representation representation language language Add Add information information Tell Tell Retrieve Retrieve information information Ask Ask Perform Perform inference inference derive derive new new sentences sentences knowledge knowledge from from existing existing sentences sentences The wumpus world A A scary scary world world indeed indeed A A maze maze in in aa cave cave A A wumpus wumpus who who will will eat eat you you One One arrow arrow that that can can kill kill the the wumpus wumpus Pits Pits that that can can entrap entrap you you but but not not the the wumpus wumpus for for itit is is too too large large to to fall fall in in A A heap heap of of gold gold somewhere somewhere But you have sensing and action Sensing Sensing each each is is either either on on or or off off aa single single bit bit wumpus wumpus emits emits aa stench stench in in adjacent adjacent squares squares pits pits cause cause aa breeze breeze in in adjacent adjacent squares squares gold gold causes causes glitter glitter you you see see when when in in the the square square walking walking into into wall wall causes causes aa bump bump death death of of wumpus wumpus can can be be heard heard everywhere everywhere in in world world But you have sensing and action Action Action You You can can turn turn left left or or right right 90 90 degrees degrees You You can can move move forward forward You You can can shoot shoot an an arrow arrow in in your your facing facing direction direction An example An example Our agent played well Used Used inference inference to to relate relate two two different different percepts percepts observed observed from from different different locations locations Agent Agent is is guaranteed guaranteed to to draw draw correct correct conclusions conclusions ifif percepts percepts are are correct correct Knowledge Representation Must Must be be syntactically syntactically and and semantically semantically correct correct Syntax Syntax the the formal formal specification specification of of how how information information is is stored stored aa 22 cc typical typical mathematical mathematical syntax syntax a2y a2y not not legal legal syntax syntax Semantics Semantics the the meaning meaning of of the the information information aa 22 cc c c must must be be 22 more more than than a a Logical Reasoning Entailment Entailment one one sentence sentence follows follows logically logically from from another another a b a b the the sentence sentence aa entails entails the the sentence sentence bb a b a b ifif and and only only ifif every every model model in in which which aa is is true true bb is is also also true true An example After After one one step step in in wumpus wumpus world world Knowledge Knowledge base base is is rules rules of of game game percepts percepts a a breeze breeze in in 2 2 1 1 Ask Ask the the KB KB ifif there there is is aa pit pit in in adjacent adjacent squares squares 1 1 22 pit pit 2 2 22 pit pit 3 3 11 pit pit Model Checking The The agent agent wishes wishes to to check check all all models models of of the the game game in in which which aa pit pit is is in in the the three three candidate candidate spots spots Enumerate Enumerate all all models models where where three three candidate candidate spots spots may may have have pits pits 33 pits pits two two conditions conditions each each 2233 Eight Eight models models Checking entailment Can Can There There is is no no pit pit in in 1 1 2 2 be be true true is is 11 true true For For all all models models where where KB KB is is true true 11 is is true true also also KB KB 11 Checking entailment Can Can There There is is no no pit pit in in 2 2 2 2 be be true true is is 22