### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Artificial Intelligence 22C 145

UI

GPA 3.87

### View Full Document

## 31

## 0

## Popular in Course

## Popular in ComputerScienence

This 23 page Class Notes was uploaded by Tamia Bernhard on Friday October 23, 2015. The Class Notes belongs to 22C 145 at University of Iowa taught by Hantao Zhang in Fall. Since its upload, it has received 31 views. For similar materials see /class/228040/22c-145-university-of-iowa in ComputerScienence at University of Iowa.

## Popular in ComputerScienence

## Reviews for Artificial Intelligence

### 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

b b Einstein s Puzzle in Logic We used propositinal variables to specify everything x1 house 1 is red 12 house 2 is red mm Brit lives in house 1 Can we use one symbol with parameters for the color of house 1 is ie lsCoorx y Or simply colorx y Yes we can do this in FirstOrder Logic 22c 145 Arti cial Intelligence FirstOrder Logic Readings Chapter 8 of Russell amp Norvig N 9 Ontological Commitments The world is made of objects things with individual identities and properties that distinguish them Various relations hold among objects Some ofthese relations are functional Every fact involving objects and their relations is either true or false 7 r FirstOrder Logic 0 Rather powerful representation and reasoning system Very well understood and extensively studied a couple ofthousand yearsl Many fancy knowledge representation formalisms semantic nets frames scripts are basically sugarcoated variants of part of it 7 D Variables constant symbols and function symbols are Language of FOL Symbols used to build terms I Bill6 Fathe39rOfz HeightFatheTOfBill Log3 y7 Relational symbols are applied to terms to build predicates Evenz MarriedBill HillaryL0vesz Mothe39rOfz Predicates and logical constants are used to build sentences Even3 Hz Lovesz Mothe39rOfzVz Evenz 5 OddI 1 The Language of FirstOrder Logic V Symbols Variables Constant symbols Functional symbols with arities Relational symbols with an39ties bbbbb Logical constants As in Propositional Logic plus V forall 3 thereexists equal bb b b 5 Language of FOL Sentences True False is a sentence lft1t2 are terms t1 t2 is a sentence lfp is an nary relation symbol and t1 tn are n terms p051 tn is a sentence Ifgo is a sentence ago Hi 90 Vac 90 are sentences W17 02 are sentences 01 A 02 901 v 902 01 a 02 901 lt2 902 are sentences Nothing else is a sentence Language of FOL Terms A variable is a term b b A constant symbol is a term If f is an nary function symbol and t1 tn are n terms ft1 tn is a term 5 b Nothing else is a term A Note on the Syntax of FOL As defined the syntax of FOL is ambiguous Vx Px 131 gt SQ It can be disambiguated by using parentheses or fixing a precedence ordering on the logical connectives We will use the following ordering m A V 7 en V739 V th this ordering 1 actually is W PWD V 206 A R06 51 When in doubt use parentheses 1 Language of FOL Grammar Sentence AtomicS CompIeXS Term Connective Quantifier Variable ConstantSymb FunctionSymb RelationSymb AtomicS l CompIeXS True l False l RelationSymbTerm7 l Term Term Sentence l Sentence Connective Sentence l Sentence Quantifier Sentence FunctionSymbTerm7 l ConstantSymb l Variable A l v l gt l gt V Variable l 3 Variable albl lzlyl Aij lJohnl0l1l l7rl FlGj lCosmelHeightlFathe39rOfl l 13ij lRedlB mthe rlApplel gt l J Constant Symbols and Variables b Denote stand for objectsindividuals Example 1 D0914 is a constant symbol denoting a particular dog J peach is a variable ranging over peaches 1 The symbolgtobject association is arbitrary b Under another interpretation D0914 could denote another dog or maybe something else altogether Similarly peach might as well range over apples 7 Semantics of FirstOrder Logic r Interprets constant symbols and variables as objects relational symbols as relations over objects 3 functional symbols as functions from objects to objects 1 as equality ie the identity relation 7 Semantics of FOL Examples Semantics of FirstOrder Logic Sentence Intuitive meaning i Interprets 1 AboveA B object A ls above object B 2 Bn39tz39shElz39sabeth an object called Elisabeth is British 9 the universal quantifier essentially as an in nite 3 VI Applez 5 Redz CONJUNCtW 4 VI Applez A Rear I VI Redz E RedObj1 A RedObj2 A RedObj3 A RedObj4 A 5 31 AW V Rear J the existential quantifier essentially as an in nite disjunction 6 VI 3y y gt 1 Hz Red 1 E Red Obj VRed Obj VRed Obj VRed Obj 6b WNumbWHHyy lt gt lt 1 lt 2 lt 3 lt 4 7 VI Applez V 3y Pea39ry 7b VI Applez V 31 Pea39rz 8 VI 3y Lavesz7 y 8b 3y VI Lavesz7 y L 9 Hz Vy L0veszy 7 L J True False A V max as in propositional logic Free and Bound Variables Semantics of FOL Examples if Sentence Intuitive meaning j 10 VI Bi39mlz A Ost39richz 5 Fliesz An occurrence of variable in a sentence is free if it is not in the scope of any quantifier with the same variable A nonfree variable occurrence is bound 11 VI Fish A OsmchWD Flies 12 VI Fliesz ltgt Birdz V Planez 13 VI Perszmz 5 Vac Pz A Qz both occurrences of z bound by Vac WW V MW A ltWltzgt A MW Vac Pz A Qz first occurrence of z bound by Vac second free 14 VI 14961 lt Agewath o r Vac Rz z A By 81 y both occurrences of z bound by Vac occurrence of y bound by By occurrence of 2 free Note The scope of a quantifier is the sentence it applies to A sentence is open if it contains free variables it is closed W 131 A Q05 W RW Z A 33 SW 1 otherwise scope of Vac scope of y scope of Vac L Li L J b b Relations Let U be the universe ofdiscourse A relation ofarity n is a subset of the Cartesian product U x x U ntimes Example Some relations in the Blocks World On ltabgtltbcgtltctgtltdegtltetgt Clear ltagtltdgt Example Less Than over the naturals Ill lt 311 xyEN32OENStx2y 0102H1213gt Formalizing Knowledge in FOL First Step Fix a Universe of Discourse that is the set of objects of interest 0 Example The Blocks World t Here the universe is the table block a block b blocke 0 Note The universe may be infinite even uncountable the integers the reals b b Examples of Functions Most mathematical functions x 6 sme W Some relations in the Blocks World E h Color lta blue ltb 78dgt lt0 blue it 3 Support ltabgtltbcgtltctgtltdegtltetgt We may define function colorx such that colora blue colorb red Note Functions in FOL are always total ie defined over the entire universe of discourse Functions 0 A function in one variable is simply a functional binary relation 1 A relation f over U x U is functional if for all x e U there is one and only one y e U such that Ly e f b If f is a function mo 6fMltltx72gt 6f Hence instead of writing xy e f we write y ag Functions in n gt 1 variables are defined similarly implies y 2 Functions and Names D The functional notation can be used to create several names for the same object 0 Examples 3 V5 12 ageBaby GeorgeBush PresldentO US SonOfHusbandOfBarbam L Relations and Predicates The notation MotherJane Bill is intended to mean that Jane Bill 6 Mother A relation implicitly defines or provides the meaning of a predicate Le a function ranging over True False Predicate is a syntactic way of representing a relation in the style of a function An Interpretation A in the Blocks World 7 Constant Symbols ABCDET W Function Symbols Support On Above Clear Relation Symbols AAaBAbcAcDAdEAeFAfTAt Swarmquot lt7 1 b126ctltdeltetlttt 0M ltab ac ltde Abovequot ltab 16 ac ltde Clemquot 11 d L l Semantics of FirstOrder Logic L A little more formally An interpretation is a pair 7 a where n D is a set of objects the universe or domain 3 a is mapping from variables to objects in D L 1 CD is an object in D for every constant symbol 0 FD is a function from D to D for every function symbol F of arity n 0 R is a relation over 7 for every relation symbol R of arity n J b Semantics of FirstOrder Logic Let D a be an interpretation and E an expression of FOL We write El to denote the meaning ofE in the domain 7 under the variable assignment a The meaning 21 ofa term t is an object of D It is inductively defined as follows llavlli7 llCllZ7 Ft1 mllE 01 017 F1739t1 397 A 7 lltnllg for all variables I for all constant symbols 0 for all function symbols F of arity n Constant Symbols Relation Symbols A different interpretation 8 A B C D ET OnAb0ue Clear Function Symbols Support Joe s hat s Joe bike ground AB JoesHatBB 10505 blkeDB JlllEB wseTB ground SupportB Unas hat Joe Joe bike Inlet2 ground Jill case case ground lt9r0uml gmundgt O39ILB Unas hat Joe Joe bike Jill wsegt LAbO lBB Unas hat Joe Joes hat bike J ClearB ltJlll no hat Joes hat b Semantics of FirstOrder Logic The meaning 90 ofa formula 90 is either True or False It is inductively defined as follows til till 13t1tn37 llwll 801 V 802 31 sol True True TrueFalse True Tru e ff iff iff iff iff 7 ml isthe same as M lt tl gvu v tn ggt 6 RD gn FalseTrue gn True or gn True go f7 True for some a coincic with 0 except maybe for z b 5 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 gt Chelsea Clinton y gt Hillary Clinton What is the meaning of Mother0fz according to Du MntherO z 7 MotherOf g z MotherOfDaz Hillary Clinto What is the meaning of SchoolO Fchz ldO yBill SchoolO Fchz39ldO y Bum SchoolOfDFchildOfDay Bill er Models Validity etc for Sentences 70 An interpretation 7 0 satisfies a sentence 0 or is a model for go if True 0 A sentence is satisfiable if it has at least one model Examples Vac as 2 y Px 0 A sentence is unsatisfiable if it has no models Examples Pac P x yo 0 A sentence 0 is valid if every interpretation is a model for 0 Examples Pac gt 131 ac as 0 is validunsatisfiable iff ago is unsatisfiablevalid b 0 Valid sentences do not tell us anything about the world They are always true Semantics of FirstOrder Logic 0 The meaning of formulas built with the other logical symbols can be defined by reduction to the previous symbols 901 A 902 i Hem V WWW 901 j 902 3 Hm V 902 901 902 3 WA 5 02 A 02 5 01M WM 3 396 wll 0 If a sentence is closed no free variables its meaning does not depend on the the variable assignment although it may depend on the domain W 31 RW ml M 31 RW ml for any 07 0 L J Possible Interpretations Semantics r 0 Sentences can be seen as constraints on the set S of all possible interpretations 0 A sentence denotes all the possible interpretations that satisfy it the models of go If 01 denotes a set of interpretations S1 and 02 denotes a set 52 then 01 v 02 denotes 51 u S2 01 02 denotes 51 S2 ago denotes SS1 901 02 iff S1 Q S2 0 A sentence denotes either no interpretations or an infinite number of them bib 5 7 Models Validity etc for Sets of Sentences T 0 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 0 A set F of sentences is satisfiable if it has at least one model EX Vxe 07 Vxx1 gt1 0 F is unsatisfiable or inconsistent if it has no models EX 131 4306 0 As in Propositional Logic F entails a sentence 0 F k 50 if every model of F is also a model of go EX39 W 173965 007 PA10 E Q0410 0 Note Again F k 0 iff F ago is unsatisfiable 22c145 Artificial Intelligence Fall 2005 Informed Search and Exploration I Cesare Tinelli The University of Iowa Copyright 200105 Cesare Tinelli and Hantao Zhang 8 8 These notes are copyrighted material and may not be used in other course settings outside of the University of Iowa in their current or modified form without the express written permission of the copyright holders 22c145 Artificial Intelligence Fall 05 p12 Readings l Chap 4 of Russell and Norvig 2003 22c145 Artificial Intelligence Fall 05 p22 Review Tree Search function TREESEARCHprobIem fringe returns a solution or failure fringe lt INSERTMAKENODEINITIALSTATEprobem fringe loop do if fringe is empty then return failure node lt REMOVEFRONTfringe if GOALTESTprobem applied to STATEnode succeeds return nod fringe lt INSERTALLEXPANDnOde probem fringe A strategy is defined by a particular node expansion order 22c145 Artificial Intelligence Fall 05 p32 Uninformed Search Strategies Strategies Time Space Complete Breadthfirst Search 0bd 0bd Yes Depthfirst Search 0bm 0bm No Depthlimited Search 0bl 0bl No Iterative Deepening Search 0bd 0bd Yes Uniform Cost Search 0bd 0bd Yes where b is the branching factor d is the depth of the shallowest solution m is the length of the longest path and l is the limit set by the user 22c145 Artificial Intelligence Fall 05 p42 Informed Search Strategies l Uninformed search strategies look for solutions by systematically generating new states and checking each of them against the goal I This approach is very inefficient in most cases I Most successor states are obviously a bad choice l Such strategies do not know that because they have minimal problemspecific knowledge I Informed search strategies exploit problemspecific knowledge as much as possible to drive the search I They are almost always more efficient than uninformed searches and often also optimal 22c145 Artificial Intelligence Fall 05 p52 Informed Search Strategies Main Idea I Use the knowledge of the problem domain to build an evaluation function f I For every node n in the search space fn quantifies the desirability of expanding n in order to reach the goal I Then use the desirability value of the nodes in the fringe to decide which node to expand next 22c145 Artificial Intelligence Fall 05 p62 Informed Search Strategies l The evaluation function f is typically an imperfect measure of the goodness of the node The right choice of nodes is not always the one suggested by f I It is possible to build a perfect evaluation function which will always suggest the right choice I How I Why don t we use perfect evaluation functions then 22c145 Artificial Intelligence Fall 05 p72 Standard Assumptions on Search Spaces l The cost of a node increases with the node s depth l Transitions costs are nonnegative and bounded below ie there is a e gt 0 such that the cost of each transition is 2 e l Each node has only finitelymany successors Note There are problems that do not satisfy one or more of these assumptions 22c145 Artificial Intelligence Fall 05 p82 BestFirst Search l Idea use an evaluation function estimating the desirability of each node I Strategy Always expand the most desirable unexpanded node I Implementation the fringe is a priority queue sorted in decreasing order of desirability l Special cases I greedy search I A search Note Since f is only an approximation quotBestFirstquot is a misnomer Each time we choose the node at that point appears to be the best 22c145 Artificial Intelligence Fall 05 p92 Implementing Bestfirst Search function BESTFIRST SEARCH problem EVAL FN returns a solution sequence inputs problem a problem Eval Fn an evaluation function QueueingFm e a function that orders nodes by EVALFN return GENERALSEARCH problem QueueingFm function GENERALSEARCH problem QUEUINGFN returns a solution or failure nodes e MAKEQUEUEMAKENODEINITIALSTATE problem loop do if nodes is empty then return failure node 9 REMOVEFRONTn0des if GOALTESTpr0blem applied to STATEn0de succeeds then return node nodes e QUEUINGFNnodes EXPANDnode OPERATORsproblem end 22c145 Artificial Intelligence Fall 05 p102 Bestfirst Search Strategies I There is a whole family of bestfirst search strategies each with a different evaluation function I Typically strategies use estimates of the cost of reaching the goal and try to minimize it I Uniform Search also tries to minimize a cost measure I Is it a bestfirst search strategy 22c145 Artificial Intelligence Fall 05 p112 Bestfirst Search Strategies I There is a whole family of bestfirst search strategies each with a different evaluation function I Typically strategies use estimates of the cost of reaching the goal and try to minimize it l Uniform Search also tries to minimize a cost measure I Is it a bestfirst search strategy I Not in spirit because the evaluation function should incorporate a cost estimate of going from the current state to the closest goal state 22c145 Artificial Intelligence Fall 05 p112 Romania with Step Costs in Km Dobreta l l Giurgiu to Bucharest Arad Bucharest Craiova Dobreta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj Mehadia Neamt Oradea Pitesti Rimnicu Vilcea 86 Sibiu Timisoara Urz iceni Vaslui Zerind Eforie 22c145 Artificial Intelligence Fall 05 Straightiline distance 366 0 160 242 161 178 77 151 226 244 241 234 380 193 253 329 80 199 374 p 1 22 Greedy BestFirst Search l Evaluation function hn heuristics estimates the cost of the cheapest path from node n to the closest goal Eg hSLDm straightline distance from n to Bucharest l Greedy search expands the node that appears to be closest to goal 22c145 Artificial Intelligence Fall 05 p132

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.