You may not be very impressed by the search algorithms we’ve studied so far as being artificial intelligence. Our next topic, I hope, will seem much more like a genuine form of AI. We’ll be using logic to infer facts about our agents’ environments.

Learn about Wumpus World

Our toy example is called Wumpus World. Read sections 7.1 and 7.2 in our text so that you understand the context.

Also check out some online resources:

• this playable WumpusWorld by ganimtron10 Some minor differences, but you can still move and reason about the location of the pits, wumpus, and so on.
• another nice demo

The goal: understand our inference process

Where are the pits? Where is the wumpus?

As you (well: the agent, but I will conflate “you” with our AI agent here) explore wumpus world, you will use your percepts (like “perceptions”) to reason about the locations of the pits so you can avoid them.

You already know how to do this, using your own (natural) intelligence. Our goal here is to carefully work through that process to see how we can systematize it and turn it into an algorithm. That is, so we can convert your natural intelligence into artificial intelligence.

Here you’ll get a sense for how we can use model checking to perform inference; you’ll then learn how to use propositional logic inference.

Galaxy-brain view

About 350 years ago, Leibniz had the idea of turning human thought into calculations so as to mechanize them. His ideas were a first step towards symbolic logic and inference algorithms.

In the 19th century, George Boole (he of “boolean”) really got our modern notions of logic going. (Wikipedia.)

While not too directly related to what we’re doing here, in the first part of the 20th century, Whitehead and Russell published their Principia Mathematica which axiomatized a lot of mathematics. This was in part a response to things like Russell’s paradox (does the set of all sets that don’t contain themself contain itself?) and other unnerving things in logic and math.

(And then a bit later, Gödel came along and more or less showed how the entire enterprise was profoundly limited.)

For more on these ideas and a big-picture view, check out chapter 2 of:

Nilsson, Nils J. The Quest for Artificial Intelligence. 1st ed. Cambridge University Press, 2009. doi:10.1017/CBO9780511819346.

Get it online from the author’s website.

Here we’ll be learning the first steps towards a form of Leibniz’s calculus ratiocinator and Boole’s laws of thought.

Exploring and reasoning about the wumpus world

For our next class, work through the following. Come prepared to do more of this kind of inference and see how we use propositional logic to do it.

We’ll be interested in possible states of the world (to use our proper language: models consistent with our knowledge base) and how we update those as our knowledge base changes via the process of model checking.

Our universe here is all possible states of the 4x4 wumpus world grid: every possible placement of pits, the wumpus, gold, and so on.

You start in the wumpus world in position (1,1), as usual. We’ll only be interested in the 6 squares in the lower left corner, and only care about whether they contain a pit or not. I’ll use “S” for safe spaces with no pit, “P” for those with a pit, and □ for squares where we don’t know or want to refer to either state. So a priori (the Latin literally means “before experience, which is exactly what we have here), we can describe states – or models – of the wumpus world with:

□
□ □
□ □ □

So: 64 possible states. As an example, four states are described by

S
P S
□ P □

Warmup: naturally intelligent reasoning

Consider the following:

• in square (1, 1) you perceive nothing
• in square (2, 1) you perceive a breeze
• in (1, 2) you perceive nothing.

What does that tell you about square (2, 2)? Does it have a pit or not?

You should have no difficulty inferring from those three statements that there is no pit in (2, 2).

Our goal here is to very carefully examine that reasoning process to develop a systematic, algorithmic way to make that same inference.

Being artificially intelligent: inference by model checking

1. Let α be the sentence (used here in the formal sense for this topic) “you perceive nothing in square (1, 1)”. Use the above S/P/□ diagrams to describe all states consistent with this percept. (There are 8.)

   Each of those states corresponds to a sentence: something like “square (1,1) is safe and square (2,1) has a pit and…”. Sentence P entails Q (written P ⊨ Q) when Q follows logically from P: in every model in which P is true, Q is also true. (Set-theoretically, P is a subset of Q.)

   (I always find it easy to get confused about the corresponding ideas of set containment and phrases like “X is stronger than Y” in relation to entailment / logical implication. Be careful and make sure you’re clear.)

   So what you did above is find all models that entail α: you did some model checking.

   For good measure, think of a state or two that do not entail α.

2. You move to (2, 1) and perceive a breeze. Use β for that percept. Use our little diagrams to describe models that entail β. (There are 6.)

   Our knowledge base (“KB”) now consists of α and β (and the background rules and context). You’ve inferred those models of wumpus world that entail our KB.

3. You move to (1, 2) and now perceive nothing; call that sentence γ. Describe the four states consistent with that percept ignoring the others.

4. It will help to draw the diagrams and draw lines around them, like this from our text. The knowledge base there corresponds to models in which we perceive nothing in (1,1) and a breeze in (2,1). (Our α and β. There’s three and not six because they aren’t showing square (1,3).) On the left in that figure, α₁ corresponds to “no pit in (1,2)”. Convince yourself that the {α, β} KB ⊨ α₁. Carefully note the distinction between precepts like “you perceive nothing in (1,1)” and “no pit in (1,2)”.

   

5. Draw out all the diagrams for models that entail α and β. There are 9 total. Draw lines around the α models and the β models.

6. There is only one model that entails our current knowledge base, which is…!

You just used model checking to infer the state of square (2, 2). That’s exactly what you did initially, just using your ordinary thinking process. We introduce and use the fancy, probably-somewhat-confusing terms and concepts used above because we can use them to algorithmically perform inference.

Next: propositional logic

For our next topic, be sure you are familiar with the very basics of propositional logic (section 7.4; there’s also a ton of lecture notes and other articles out on the web):

• its syntax and if you are familiar with BNF or context-free grammars, the grammar for propositional logic.

• the not / and / or / implies / iff operators

• a bit about the semantics: we aren’t just pushing symbols around and playing a game; these sentences have some meaning.

Why are we doing this?

Above you did inference by model checking – roughly, a big exercise in set-theoretic operations. That’s not very efficient, and you can easily imagine a combinatorial explosion in which the number of sets is far too large to handle.

Using inference with propositional logic, instead of dealing with huge sets of models, we can operate on very small sets of sentences to infer facts about our world.

one more thing

Do let me know if you find this helpful or interesting, not overly difficult, not tedious busywork, and so on. Or, in propositional logic, something like…

( helpful ∨ interesting ) ∧ ¬ too difficult ∧ ¬ confusing ∧ ¬ tedious

Really, let me know. And give suggestions for future things that will help you learn.