The_Wumpus_World

Report
The Wumpus World!
2012级ACM班
金汶功
Hunt the wumpus!
Description
•
•
•
•
Performance measure
Environment
Actuators
Sensors: Stench & Breeze & Glitter & Bump &
Scream
An Example
An Example
Reasoning via logic
Semantics
• Semantics: Relationship between logic and the
real world
• Model: (α)
• Entailment:  ⊨ β iff M() ⊆ ()
Models
• KB: valid sentences
• 1 : “There is no pit in [1,2]”
• 2 : “There is no pit in [2,2]”
Sensors
Tell
Axioms
Current
States
Knowledge base
Ask
Answer
Tell
Model
checking
Actuators
Agent
Efficient Model Checking
•
•
•
•
•
•
DPLL
Early termination
Pure symbol heuristic
Unit clause heuristic
Component analysis
…
Drawbacks
• Model checking is NP-complete
• Knowledge base may tell nothing.
Probabilistic Reasoning
Full joint probability distribution
• P(X, Y) = P(X|Y)P(Y)
• X: {1,2,3,4} -> {0.1,0.2,0.3,0.4}
• Y: {a,b} -> {0.4, 0.6}
• P(X = 2, Y = a) = P(X = 2|Y = a)P(Y = a)
• The probability of all combination of values
Normalization
•   ℎℎ) =
(∧ℎℎ)
(ℎℎ)
• (ℎℎ) is a constant
•   ℎℎ) = α ( ∧
ℎℎ)
•   ℎℎ) =  < 0.12,0.08 >
• =< 0.6,0.4 >
The Wumpus World
• Aim: calculate the probability that each of the
three squares contains a pit.
Full joint distribution
• P(1,1 , ⋯ 4,4 , 1,1 , 1,2 , 2,1 ) = P(1,1 , 1,2 ,
2,1 |1,1 , ⋯ 4,4 ) P(1,1 , ⋯ 4,4 )
• P(1,1 , ⋯ 4,4 ) =
, P(, )
• Every room contains a pit of probability 0.2
•  1,1 , ⋯ 4,4 = 0.2 × 0.816−
How likely is it that [1,3] has a pit?
• Given observation:
•  = ¬1,1 ∧ 1,2 ∧ 2,1
•  = ¬1,1 ∧ ¬1,2 ∧ ¬2,1
•  1,3 ,  = 
• 212 = 4096 terms
 (1,3 , , , )
Using independence
Simplification
•  1,3 ,  = 
• =
• =
 (1,3 , , , )
 (|1,3 , , )(1,3 , , )

(|1,3 , , , ℎ)
ℎ ( , , , ℎ)
1,3
• =⋯
• =   (1,3 )
 (|1,3 , , )()
• Now there are only 4 terms, cheers!
Finally
•  1,3 ,  =< 0.31, 0.69 >
• [2,2] contains a pit with 86% probability!
• Data structures---independence
Bayesian Network
Simple Example
P(B)
Burglary
P(E)
Earthquake
.001
Alarm(Bark)
John Calls
Bark
P(J)
true
.90
false
.05
.002
B
E
P(A)
True
true
.95
true
false
.94
false
true
.29
false
false
.001
Mary Calls
Bark
P(M)
true
.70
false
.01
Specification
• Each node corresponds to a random variable
• Acyclic – DAG
• Each node has a conditional probability
distribution   ( )
Conditional Independence
Exact Inference
•   ,  = α , , 
• = α   (, , , , )
• = α         ,     (|)
• (|, ) =< 0.284,0.716 >
P(P2,2)
0.2
P1,3
P2,2
P(P3,1)
P3,1
0.2
P(known)
P(1,3)
known
0.2
b
P1,3
P2,2
P3,1
b
True
True
True
1
True
True
False
1
True
False
True
1
True
False
False
0
False
True
True
1
False
True
False
1
False
False
True
0
False
False
False
0
Approximate Inference
• Markov Chain Monte Carlo
• Gibbs Sampling
• Idea: The long-run fraction of time spent in
each state is exactly proportional to its
posterior probability.
( ′ |  ) = αP(′ |  ) ×
( |( ))
 ∈ℎ 
Reference
• http://zh.wikipedia.org/wiki/Hunt_the_Wumpus
• http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%8F%B6%E6%9
6%AF%E7%BD%91%E7%BB%9C
• Stuart Russell, Peter Norvig Artificial Intelligence—A Modern
Approach 3rd edition, 2010

similar documents