First-Order Logic: Better

choice for Wumpus World

 Propositional logic represents facts
 First-order logic gives us
 Objects
 Relations: how objects relate to each other
 Properties: features of an object
 Functions: output an object, given others
 Syntax and Semantics
 Propositional logic has the following:
 Constant symbols: book, A, cs327
 Predicate symbols: specify that a given
relation holds
 Example:
 Teacher(CS327sec1, Dave)
 Teacher(CS327sec2, Dave)
 “Teacher” is a predicate symbol
 For a given set of constant symbols,
relation may or may not hold
Syntax and Semantics
 Function Symbols
 FatherOf(Luke) = DarthVader
 Variables
 Refer to other symbols
 x, y, a, b, etc.
 In Prolog, capitalization is reverse:
 Variables are uppercase
 Symbols are lower case
 Prolog example ([user], ;)
Syntax and Semantics
 Atomic Sentences
 Father(Luke,DarthVader)
 Siblings(SonOf(DarthVader),
DaughterOf(DarthVader))
 Complex Sentences
 and, or, not, implies, equivalence
Father( Luke, DarthVader )  Father( Leia , DarthVader )

 Equality
( DaveAppleyard  DaveMusicant )
 Universal Quantification
 “For all, for every”: 
 Examples:

x Cat ( x)  Mammal( x)
x WeighsSameAs( x, Duck )  Witch( x)
 Usually use  with 
 Common mistake to use 
x At ( x, Carleton)  Smart ( x)
 Existential Quantification
 “There exists”: 
x HopeForUniverse( x)  ( x  Luke)
 Typically use  with 
 Common mistake to use 

x At ( x, Carleton)  Smart ( x)
 True if there is no one at Carleton!
 Properties of quantifiers
x y same as y x
x y same as y x
x y not the same as y x :
y x FavoriteFood ( y, x)
x y FavoriteFood ( y, x)
 Can express each quantifier with the
other
x Likes( x, IceCream) x Likes( x, IceCream)
x Likes( x, Broccoli ) x Likes( x, Broccoli )
 Some examples
x MadeOfWood ( x)  Burns ( x)
x MadeOfWood ( x)  FloatsInWater( x)

 Definition of sibling in terms of parent:

x, y Sibling ( x, y )  [( x  y )  m, f (m  f ) 
Parent (m, x)  Parent ( f , x)  Parent (m, y )  Parent ( f , y )]
 First-Order Logic in Wumpus
World
 Suppose an agent perceives a stench,
breeze, no glitter at time t = 5:
 Percept([Stench,Breeze,None],5)
 [Stench,Breeze,None] is a list
 Then want to query for an appropriate
action. Find an a (ask the KB):

a Action(a,5) ?
 Simplifying the percept and
deciding actions
b, g , t Percept ([ Stench, b, g ], t )  Stench(t )
s, g , t Percept ([ s, Breeze , g ], t )  Breeze (t )
s, b, t Percept ([ s, b, Glitter ], t )  AtGold (t )
 Simple Reflex Agent

t AtGold (t )  Action(Grab, t )

 Agent Keeping Track of the World

t AtGold (t )  Holding (Gold , t )  Action(Grab, t )
 Using logic to deduce
properties
 Define properties of locations:
l , t AtAgent(l , t )  Stench(t )  Smelly (l )
l , t AtAgent(l , t )  Breeze (t )  Breezy (l )
 Diagnostic rule: infer cause from effect
y Breezy ( y )  x Pit ( x)  Adjacent( x, y )
 Causal rule: infer effect from cause
x, y Pit ( x)  Adjacent( x, y )  Breezy ( y )
 Neither is sufficient: causal rule doesn’t say if squares
far from pits can be breezy. Leads to definition:
y Breezy ( y )  x Pit ( x)  Adjacent( x, y )
 Keeping track of the world is
important
 Without keeping track of state...
 Cannot head back home
 Repeat same actions when end up back in
same place
 Unable to avoid infinite loops
 Do you leave, or keep searching for gold?
 Want to manage time as well
 Holding(Gold,Now) as opposed to just
Holding(Gold)
 Situation Calculus
 Adds time aspects to first-order logic
AtAgent([1,1], S0 )  AtAgent([1,2], S1 )
Result function connects actions to results
Result(For ward, S0 )  S1
Result(Tur n( Right ) , S1 )  S 2
 Describing actions
 Pick up the gold!
Stated with an effect axiom


s AtGold ( s)  Holding (Gold , Result (Grab, s))

 When you pick up the gold, still have
the arrow!
 Nonchanges: Stated with a frame axiom
s HaveArrow( s)  HaveArrow( Result (Grab, s))
 Cleaner representation:
successor-state axiom
 For each predicate (not action):
 P is true afterwards means
 An action made P true, OR
 P true already and no action made P false
 Holding the gold:
a, s Holding (Gold , Result(a, s )) 
(( a  Grab)  AtGold ( s )) 
( Holding (Gold , s )  (a  Release ))
(if there was such a thing as a release action – ignore that for our example)
 Difficulties with first-order
logic
 Frame problem
 Need for an elegant way to handle non-change
 Solved by successor-state axioms
 Qualification problem
 Under what circumstances is a given action
guaranteed to work? e.g. slippery gold
 Ramification problem
 What are secondary consequences of your
actions? e.g. also pick up dust on gold, wear and
tear on gloves, etc.
 Would be better to infer these consequences, this
is hard
 Keeping track of location
 Direction (0, 90, 180, 270)
Orientation(S0 )  0
 Define function for how orientation affects x,y
location
x, y LocationToward ([ x, y ],0)  [ x  1, y ]
x, y LocationToward ([ x, y ],90)  [ x, y  1]
x, y LocationToward ([ x, y ],180)  [ x  1, y ]
x, y LocationToward ([ x, y ],270)  [ x, y  1]
 Location cont...
 Define location ahead:
l , s AtAgent(l , s) 
LocationAhead ( s )  LocationToward (l , Orientatio n( s ))
 Define what actions do (assuming you know
where wall is):
l , d , p, s AtAgent(l , Result(a, s )) 
[ (a  Forward  l  LocationAhead ( s)  Wall (l ))
 ( AgentAt(l , s )  a  Forward )
 Primitive goal based ideas
 Once you have the gold, your goal is to get
back home
s Holding (Gold , s)  GoalLocation([1,1], s)

 How to work out actions to achieve the goal?

 Inference: Lots more axioms. Explodes.
 Search: Best-first (or other) search. Need to
convert KB to operators
 Planning: Special purpose reasoning systems
(chapter 11)