The chapter the Wumpus World was made for. A hybrid agent TELLs its knowledge base what it perceives and ASKs it what is safe. Below that, the inference lab answers the same question five ways (model checking, resolution, forward chaining, backward chaining, DPLL), plus WalkSAT, on the KB as it stands at any step.
A The hybrid Wumpus agent (Fig. 7.20)
True world
What the KB entails click a square to query it in the lab below
OK = KB ⊨ ¬P ∧ ¬W · P! / W! = KB ⊨ P / W · ¬P, ¬W = proved absent · ? = not entailed either way · B/S = percepts
Agent program
Knowledge base
Highlighted: sentences TELLed at this step. Every ASK is a satisfiability check (KB ∧ ¬α unsatisfiable ⇒ KB ⊨ α) done with DPLL. A “cached” answer was refuted by a model of KB found earlier, so no SAT call was needed.
B Inference lab works on the KB at the step selected above
Query α:square
C Why propositional logic doesn't scale
The KB above covers only the squares the agent visited. The book's full KB has physics sentences for every square. It also has a copy of every fluent (Ltx,y, FacingEastt, HaveArrowt, WumpusAlivet) and successor-state axioms for every time step t. Sizes of the atemporal part:
Chapter 8 writes all of this as a few first-order sentences: ∀s Breezy(s) ⇔ ∃r Adjacent(r, s) ∧ Pit(r).
Chapter notes & questions
Load the Book Fig. 7.2 world and step to the moment the agent is at [1,2]. Why is the wumpus at [1,3] entailed? Prove it with resolution and with backward chaining. hint¬S1,1 rules out W1,2 and W2,1; ¬S2,1 rules out W2,2; S1,2 says one of W1,1, W2,2, W1,3 holds.
In model checking, count the models of KB that make α false. Why does one such model suffice to answer “not entailed”?
Forward chaining only derives what a Horn KB allows. Find a situation where DPLL proves a square safe but forward chaining on our Horn rules cannot. hintReasoning by cases: “the pit is in [1,3] or [2,2], and either way…” is not Horn.
DPLL: how many decisions (branches) does a typical ASK need? Most of the work is unit propagation. Why is that for the Wumpus KB?
WalkSAT finds some model of the KB, a possible world consistent with everything perceived. Run it with several seeds. What changes between models, and what never changes? (What never changes is exactly what is entailed.)
Resolution on the wumpus sub-KB generates many more clauses than on the pit sub-KB. Which KB sentences cause that? Compare the three strategies.
Fig. 7.20 prefers a risky step into a square that is not provably unsafe over going home. Try ten random worlds: how often does that kill the agent? Chapter 12 replaces “not provably unsafe” with an actual probability.