Artificial Intelligence 22C 145
Popular in Course
Popular in ComputerScienence
This 9 page Class Notes was uploaded by Dr. Humberto Beier on Friday October 23, 2015. The Class Notes belongs to 22C 145 at University of Iowa taught by Staff in Fall. Since its upload, it has received 43 views. For similar materials see /class/228051/22c-145-university-of-iowa in ComputerScienence at University of Iowa.
Reviews for Artificial Intelligence
Report this Material
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/23/15
Sentence CompleXS Language of FOL Grammar l Quantifier Sentence FunctionSymbTerm7 r l ConstantSymb l Variable Connective 2 l V l 5 l ltgt Quantifier 2 VVariable l 3 Variable Variable 2 ConstantSymb 2 AlBllJ0hnl0llll7rli FunctionSymb 2 F l Gl l Cosine l Height l Fathe39rOf l l RelationSymb 2 P l Q l l Red l Brother l Applel gt l H AtomicS l CompleXS AtomicS 2 True l False l RelationSymbTerm7 r l Term Term Sentence l Sentence Connective Sentence l Sentence 22c 145 Arti cial Intelligence T FirstOrder Logic Readings Chapter 8 of Russell amp Norvig r A common mistake to avoid Typically gt is the main connective with V Common mistake using as the main connective with V V1 Atx7 Ulowa Smartx means Everyone is at Ulowa and everyone is smart 7 Universal quanti cation Vltvartablesgt sentence Everyone at Ulowa is smart V1 AtxUIawa gt Smartx Vac 131 istrue in an interpretation m iffPx is true with as being each possible object in the domain Roughly speaking equivalent to the conjunction of instantiations of P AtKz39ngJ0hnUIowa gt SmartKtngJOhn AtRZehardUImua gt SmartRZehard AtUIawaUIawa gt SmartUIawa L Another common mistake to avoid Typically is the main connective with 3 Common mistake using gt as the main connective with 3 3x Atx7 Stanford gt Smartx is true if there is anyone who is not at Stanford Existential quanti cation 7 variable sentence Someone at Stanford is smart 3 x Atm7 Stanford Smartx 395 P is true in an interpretation I iff P is true with as being some possible object in the domain Roughly speaking equivalent to the disjunction of instantiations of P AtKingJohn7 Stanford SmartKingJohn AtRichard7 Stanford SmartRichard AtStanford7 Stanford SmartStanford ltlt J Fun with sentences Brothers are siblings Vxy Brotherxy gt Siblingxy Sibling is symmetric Properties of quanti ers Vac Vy is the same asVy Vac why 395 y is the same as By 395 why Ex Vy is not the same as Vy 395 Hi Vy Lovesxy There is a person who loves everyone in the world Vy 3x Lovesx7 y Everyone in the world is loved by at least one person Quantifier duality each can be expressed using the other V1 Likesxce0ream L31 Lillt2esx7 Broccoli 1 LikesQ IceCream Vx LikesQ Broccoli J Fun with sentences Brothers are siblings Vxy Brothedmy gt Siblingmy Sibling is symmetric Vxy Siblingxy Siblingyx One s mother is one s female parent V1 y Mothedx y Femaldx Paren x7 A first cousin is a child of a parent s sibling L Fun with sentences Brothers are siblings Vxy Brothedmy gt Sibling y Sibling is symmetric Vxy Siblingxy Siblingyx One s mother is one s female parent Equality terml termg is true under a given interpretation if and only ifterrmL and termg refer to the same object Eg 1 2 and Vac xSqrtx Sqrtx x are satisfiable 2 2 is valid Eg definition of full Sibling in terms of Parent V0671 Siblingwyy Ha z A 3m f omf A Parentm7 x ParentU x Parentm7 y ParentU L Fun with sentences Brothers are siblings Vxy Brothedmy gt Sibling y Sibling is symmetric Vxy Siblingxy Siblingyx One s mother is one s female parent Vxy Motherxy Femaldx Parentxy A first cousin is a child ofa parent s sibling VIE y FirstCousz39Mx y 319195 Parentp7 x Siblin ps p Parentps7 y L An Interpretation A in the Blocks World l Constant Sym bols A B C D E T Support On Above Clear Function Symbols Relation Symbols AAaBAbcAcDAdEAeFAfTAt SuppoTtA 1112126ctgtdegtetgtttgt OnA 1112 ltbCgt degt AboveA 1112acgtbcgtdegt Clea rA 11 d L l Semantics of FirstOrder Logic A little more formally An interpretation is a pair 7 a where 0 D is a set of objects the universe or domain a is mapping from variables to objects in D O is an object in D for every constant symbol 0 bbb FD is a function from Dquot to D for every function symbol F of arity n 1 R is a relation over 7quot for every relation symbol R of arity n J Models for FOL Lots 7We can enumerate the models for a given FOL sentence W For each number of universe elements n from 1 to 00 For each kary predicate Pk in the sentence For each possible kary relation on n objects For each constant symbol 0 in the sentence For each one of n objects mapped to O Enumerating models is not going to be easy L l Constant Symbols A B C D ET OnB LAbmeB A different interpretation 8 Function Symbols Support Relation Symbols On Above Clear Joe s hat 4 bike ground A8 JoesHatBB 10505 blkeDB JillEB caseTB gm39Lmd SupportB Joes hat Joe Joe bike blkegr01mdgt Jill case case ground gnmml gmundgt Joes hat Joe Joe bike Jill wsegt Joes hat Joe Joes hat bike lt ClearB 1m no hat Joes hat 7 b b b Example Consider the symbols MotherOf SchoolOf Bill and the interpretation D a where MotherOfD is a unary fn mapping people to their mother SchoolOfD is a unary fn mapping people to their school Fchz39ldOfD is a binary fn mapping a couple to their first child Bill is Bill Clinton a z z l gt Chelsea Clinton y l gt Hillary Clinton What isthe meaning of Mother0fz according to Du MatherO z 7 MotherOf g iziig MotherOfDaz Hillary Clinto What isthe meaning of SehoolO Fchz ldO yBill SchoolO Fchz ldO y Bill SchoolOfDFchz39ldOfDay Bill s tz Semantics of FirstOrder Logic 9 Let D a be an interpretation and E an expression of FOL We write E aD to denote the meaning ofE in the domain 7 under the variable assignment a 0 The meaning 21 ofa term t is an object of D It is inductively defined as follows aci 7 01 for all variables I 0Z7 CD for all constant symbols 0 Ft1 mm FDt1E tn g for all function symbols F of arity n J L Semantics of FirstOrder Logic The meaning of formulas built with the other logical symbols can be defined by reduction to the previous symbols iiwl A Mi 3 How V reozliiop iiwl Wii 3 idem VsoziioD 901 Wit 3 in 02 A 902 01iioD iiniioD i 306 Vii Ifa sentence is closed no free variables its meaning does not depend on the the variable assignment although it may depend on the domain Wm 3y Rx7 3y Rx7 for any a 0 Semantics of FirstOrder Logic 1 The meaning 90 of a formula 90 is either True or False 0 It is inductively defined as follows in t2 True iff m7 is the same as M 13t1tn377 True iff tli i7 ELLE E RD moi I TrueFalse iff Roi FalseTrue gol V uni 2 True iff Rani True or gozi True 31 sari True iff 97 True for some a coincic with 0 except maybe for z 7 J Models Validity etc for Sets of Sentences D An interpretation 7 0 satisfies a set F of sentences or is a model for P if it is a model for every sentence in F A set F of sentences is satisfiable if it has at least one model EX Vxe 07 me1gtx F is unsatisfiable or inconsistent if it has no models Ex Pm Wm As in Propositional Logic F entails a sentence 90 F l 50 if every model ofF is also a model of go EX39 W 173955 007 PA10 l 1410 Note Again F l 90 iff F ago is unsatisfiable Models Validity etc for Sentences L 0 An interpretation 7 0 satisfies a sentence 0 or is a D model for go if 500 True A sentence is satisfiable if it has at least one model Examples Vac at 2 y 3a A sentence is unsatisfiable if it has no models Examples Px Px x ac b b A sentence 90 is valid if every interpretation is a model for 0 Examples Px gt Px ac at b 90 is validunsatisfiable iff go is unsatisfiablevalid b Valid sentences do not tell us anything about the world They are always true J r The Wumpus World in FOL L Possible Interpretations Semantics 0 Sentences can be seen as constraints on the set S of all possible interpretations 1 A sentence denotes all the possible interpretations that satisfy it the models of 50 If 901 denotes a set of interpretations S1 and 902 denotes a set 52 then 901 v 902 denotes 51 u S2 901 902 denotes 51 S2 am denotes SS1 901 l 902 iff S1 Q S2 0 A sentence denotes either no interpretations or an infinite number oftheml bbb b 7 J Knowledge base for the wumpus world Perception Vbgt PerceptSmellbgt gt Smeltt Vsbt PerceptsbGthtert gt AtGaldt Reflex Vt AtGaldt gt Acti0nGrabt Reflex with internal state do we have the gold already Vt AtGaldt HaldmgGaldt gt Act20nGrabt H0ldz39ngGald 25 cannot be observed keeping track of change is essential L i Interacting with FOL KBs Suppose a wumpusworld agent is using an FOL KB and perceives a smell and a breeze but no glitter at t 5 TellKB PerceptSmell Breeze None 5 AskKB 3 a Act20na 5 Le does the KB entail any particular actions at t 5 Answer Yes aShoot lt substitution binding list Given a sentence S and a substitution 0 Sa denotes the result of plugging a into S eg S Smarterx y 039 xHz39llaryyBz ll SO39 SmarteMHz39llary Bill LASkltKB S returns someall a such that KB i 50 J Keeping Track of Change Facts hold in situations rather than eternally Eg H01dz39ngGald Naw rather than just H01d239ngG0ld Deducing Hidden Properties 70 Properties oflocations j Vxt AtAgent x t Smeltt gt Smellyx 1 V145 AtAgent x t Bree2et gt Bree2yx 9 Squares are breezy near a pit 1 Diagnostic rule infer cause from effect Vy Bree2yy gt Hi 32151 Adjacen x y 0 Causal rule infer effect from cause VIE y Pitr Adjacen x y gt Bree2yy Neither ofthese is complete eg the causal rule doesn t say whether squares far away from pits can be breezy 0 Definition for the Breezy predicate Vy Bree2yy 31 Pitx Adjacen x L J Describing Actions D Effect axiom describe changes due to action V5 AtGald5 gt HoldingGold7 I365ultGrab7 5 I Frame axiom describe nonchanges due to action V5 HaveArraw5 gt HaveArrmuRe5ultGrab 5 Situation Calculus Situation calculus is one way to represent change in FOL Adds a situation argument to each noneternal predicate Eg Now in H0ldz39ngG0ld Now denotes a situation or a time stamp Situations are connected by the Result function Resulta 5 is the situation that results from doing a in 5 L J r Describing Actions Successorstate axioms solve the representational frame problem Each axiom is about a predicate not an action per se P true aftenNards lt2 an action made P true 7 P true already and no action made 1 Exmaple For holding the gold Va 5 HoldingGold7 Re5ulta7 5 a Grab AtGald5 Ht7ldz39ngG0ld7 5 a Relea5e Frame Qualifcation and Rami cation 0 5 Frame problem find an elegant way to handle nonchange representation avoid frame axioms 7 1 inference avoid repeated copyovers to keep track of state Qualification problem true descriptions ofrea actions require endless caveats what if gold is slippery or nailed down or Ramification problem real actions have many secondary consequences what about the dust on the gold wear and tear on gloves J b b b Making plans A better way Represent plans as action sequences 11 a2 an PlanResultp s is the result of executing p in 5 Then the query AskKB 3p HoldingG0ld PlanResultp SO has the solution pForward Grab Definition of PlanResult in terms of Result Vs PlanResult s s Vap s PlanResult alp s PlanResultp Resulta 5 Planning systems are specialpurpose reasoners designed to do this type of inference more efficiently than a generalpurpose reasoner b Making Plans Initial condition in KB magma 17 1 So AtGold 1 2 S0 Query AskKB 3 s HoldingGold 5 Le in what situation will I be holding the gold Answer sResultGrab ResultF0rward S0 ie go forward and then grab the gold This assumes that the agent is interested in plans starting at S0 and that So is the only situation described in the KB J Summary Firstorder logic objects and relations are semantic primitives syntax constants functions predicates equality quantifiers Increased expressive power sufficient to define wumpus world Situation calculus conventions for describing actions and change in FOL can formulate planning as inference on a situation calculus KB J
Are you sure you want to buy this material for
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'