Transcript Let`s Play Wumpus!

Review: What is a logic?
• A formal language
– Syntax – what expressions are legal
– Semantics – what legal expressions mean
– Proof system – a way of manipulating syntactic
expressions to get other syntactic expressions (which
will tell us something new)
• Why proofs? Two kinds of inferences an agent
might want to make:
– Multiple percepts  conclusions about the world
– Current state & operator  properties of next state
Review: Types of logic
Review:
Propositional logic: syntax
Review:
Propositional logic: semantics
Entailment
Propositional inference:
enumeration method
Enumeration: Solution
Validity and satisfiability
Theorem
Proof methods
A Typical Wumpus World
Wumpus World Description
Wumpus World Sentences
Wumpus World Sentences
Wumpus World Sentences
Wumpus world: example
• Rules: A square has stench if and only if the square or
adjacent squares contain the wumpus
– R1: S1,1 ↔ W1,1 v W1,2 v W2,1
– R2: S2,1 ↔ W1,1 v W2,2 v W3,1
– …
• Facts: Percepts inject (TELL) facts into the KB
– [There is no stench at 1,1]   S1,1
• Inference:
– KB contains  S1,1 then using Modus Ponens we infer
 (W1,1 v W1,2 v W2,1)
– Using De Morgan’s Law we get:
 W1,1   W1,2   W2,1
– Using And-Elimination we get:
W1,1
W1,2
W2,1
Limitations of Propositional Logic
1. It is too weak, i.e., has very limited
expressiveness:
• Each rule has to be represented for each situation:
e.g., “don’t go forward if the wumpus is in front of you”
takes 64 rules
2. It cannot keep track of changes:
• If one needs to track changes, e.g., where the agent has
been before then we need a timed-version of each rule. To
track 100 steps we’ll then need 6400 rules for the previous
example.
Its hard to write and maintain such a huge rulebase
Inference becomes intractable
Predicate logic
Predicate Logic is more expressive, because it
allows us to represent :
• Objects
• Predicates (facts)
• Variables
Assume we have the following
assertions (facts)
•
•
•
•
•
•
•
•
•
Comet is a horse
Prancer is a horse
Comet is parent of Dasher
Comet is a parent of Prancer
Prancer is fast
Dasher is a parent of Thunder
Thunder is fast
Thunder is a horse
Dasher is a horse
Write predicate logic sentences
for these facts :
To do so, we need to understand the concepts of:
• Objects
– Comet, Prancer, Dasher, etc
• Predicates (facts)
– horse
– parent-of
• Variables
– horse(x)
horse(Comet)
parent-of(Comet,Dasher)
Thus, we can write
•
•
•
•
•
•
•
•
•
Comet is a horse
Prancer is a horse
Comet is parent of Dasher
Comet is a parent of Prancer
Prancer is fast
Dasher is a parent of Thunder
Thunder is fast
Thunder is a horse
Dasher is a horse
•
•
•
•
•
•
•
•
•
horse(Comet)
horse(Prancer)
parent-of(Comet,Dasher)
parent-of(Comet,Prancer)
fast(Prancer)
parent-of(Dasher,Thunder)
fast(Thunder)
horse(Thunder)
horse(Dasher)
We also can write compound
statements such as:
• not( horse(Schafer) )
• horse(Comet) and parent-of(Comet,Dasher)
• winner(Prancer) implies fast(Prancer)
Suppose we have the following rule
(relation)
R1: if x is-a horse
x is-parent-of y
y is-fast
then x is valuable
Bindings
In general, there will be variables in the rules
which stand for arbitrary objects. We need
to find bindings for them so that the rule is
applicable.
Bindings
Bindings
From these we can deduce that there are two possible bindings
applicable to the rule:
x = Comet and y = Prancer
x = Dasher and y = Thunder
Since x is valuable, Comet is valuable and Dasher is valuable
Forward Chaining
• Forward Chaining or data-driven inference works
by repeatedly: starting from the current state,
matching the premises of the rules (the IF parts),
and performing the corresponding actions (the
then parts) that usually update the knowledge base
or working memory.
• The process continues until no more rules can be
applied, or some cycle limit is met.
Forward Chaining
Forward Chaining
• In this example there are no more rules, so
we can draw the inference chain:
• This seems simple enough, but this had few
initial facts and few rules.
Disadvantages of Forward Chaining
• Many rules may be applicable at each stage
– so how should we choose which one to
apply next at each stage?
• The whole process is not directed towards a
goal, so how do we know when to stop
applying the rules?
Backward Chaining
• Backward chaining or goal-driven inference
works towards a final state by looking at the
working memory to see if the sub-goal
states already exist there. If not, the actions
(the THEN parts) of the rules that will
establish the sub-goals are identified and
new sub-goals are set up for achieving the
premises of those rules (the IF parts).
Backward Chaining
• The previous example now becomes:
Backward Chaining
• The first part of the chain works back from
the goal until only the initial facts are
required, at which point we know how to
traverse the chain to achieve the goal state.
Backward Chaining
• Advantage
– The search is goal directed, so we only apply
the rules that are necessary to achieve the goal.
• Disadvantage
– The goal has to be known.
– Fortunately, many AI systems can be
formulated in a goal based fashion.