Heuristics and Logic

Sections 1 to 6 (heuristics) and 8 to 15 (logic) are adapted from the lecture notes of CS50’s Introduction to Artificial Intelligence with Python by Brian Yu and David J. Malan (Harvard University), licensed under CC BY-NC-SA 4.0. Sections 7 and 16 were written for COMP5001. The notes are shared under the same licence.

1. Where Week 2 left off
2. A heuristic is a guess
3. Greedy best-first search
4. Where greedy goes wrong
5. A* search
6. A good guess never overestimates
7. What is logic?
8. Knowledge-based agents
9. Symbols, and joining sentences: not, and, or
10. If … then, and if and only if
11. Models and knowledge bases
12. Entailment
13. Model checking
14. Knights and knaves, by model checking
15. In the code: logic.py and harry.py
16. Heuristics and logic in the real world
17. Check yourself, key terms and reading

1Where Week 2 left off

Last week, breadth-first search explored 29 squares of the Week 1 maze to find the 17-step path, and depth-first search explored 25. When you solved the same maze yourself in Week 1, you did not look at every square. You could see where B was, so you headed towards it.

DFS and BFS cannot do that. They try squares in a fixed order (newest first, or oldest first), whatever the maze looks like. This week’s first half gives the search a sense of direction.

2A heuristic is a guess

To head towards B, the search needs a number for each square that says roughly how far it is from B. In a maze, the simplest such number is the Manhattan distance: count how many rows and how many columns the square is from B, and add them up. It ignores the walls. (The name comes from walking between blocks in Manhattan, where you cannot cut diagonally across.)

3Greedy best-first search

Greedy best-first search uses the loop from Week 2 and changes one line: which node comes out of the frontier. Instead of the newest (DFS) or the oldest (BFS), it takes the node with the smallest h, the one that looks closest to the goal.

If two nodes have the same h (a tie), we take the one that joined the frontier first. Your own code may break ties differently, so your numbers can differ slightly.

Worked example: greedy on the Week 1 maze

The small number in the corner of each square is h. Lilac squares have been taken out of the frontier, numbered in order; dashed squares are waiting; the ringed square was taken out last.

Here the guess was good, so greedy went almost straight to B. Is it always this good? No.

4Where greedy goes wrong

The maze below is maze4.txt in week02-search/maze. Look at it before reading on: which way would you go from A? Most people go down and along the long bottom corridor, because they can see it leads straight to the right-hand side.

The shortest path goes down and along the bottom: 16 steps. Greedy never found it, because at step 2 the bottom route looked worse (13 against 11), and after that the top route always looked better than the square below A.

• When the heuristic is good, greedy is often very fast.
• The path it finds may not be the shortest.
• A misleading heuristic can lead it away from a much shorter route.

5A* search

A* search (said “A star”) fixes greedy’s mistake by adding the cost already paid. For each node it adds two numbers:

• g(n): the cost from the start to n, here the number of steps already taken. This is known exactly, because we walked it.
• h(n): the heuristic, the guessed cost from n to the goal.

Worked example: two squares in the frontier

Greedy compares only h and takes X (7 is less than 11). A* sees that X is already 11 steps from A, so a path through X is about 18 steps long, while a path through Y is about 16. It takes Y.

Worked example: A* on the trap maze

In these pictures the big number in each explored square is its f, not the step number. Ties are broken by taking the square nearer B (smaller h).

Greedy often explores the fewest squares, but on the trap maze its path is 4 steps too long. BFS and A* found the shortest path in every maze, and A* always explored fewer squares than BFS, because the heuristic keeps it away from squares that lead the wrong way.

Worked example: A* with real costs

In Week 2, BFS on the road map returned the 55-minute route via Andover, because it counts roads, not minutes. A* uses the minutes. Here g is the driving time so far, and h is a straight-line estimate of the time still to go (it can never be more than the real time, because no road is shorter than a straight line).

A* returns the optimal 50-minute route, and it never even expanded Andover or Romsey. Note that the goal test happens when a node is taken out of the frontier, not when it is added: that is what lets A* compare every way of reaching the goal before it stops.

6A good guess never overestimates

A straight line between two towns can never be longer than the road between them, because the road can bend but the straight line cannot. So a straight-line heuristic never guesses too high. Manhattan distance in a maze is the same: walls can only make the real route longer, never shorter.

Other heuristics, and where they come from

Manhattan distance is the right guess for a maze, but every problem needs its own heuristic. Table 1 collects some common ones.

Two more rules of thumb. A guess that is closer to the truth makes A* explore fewer squares: on the 8-puzzle, the tiles-out-of-place guess and the Manhattan-distance guess are both admissible, but the second is nearer the real answer and solves the puzzle far faster. And if you have two admissible heuristics, take the larger of the two at each node: it is still admissible, and at least as good as either on its own. Next week, planning uses a guess of the same kind: the number of goal facts that are not yet true.

Going further: CS50 and Russell & Norvig also describe consistent heuristics, which never drop by more than the cost of one step. Manhattan distance and straight-line distance are both consistent. You do not need this for COMP5001.

7What is logic?

The second half of the week is about logic. In Week 1 you solved the knights and knaves puzzles by reasoning: “if A is a knight, then …”. This half shows how to write that kind of knowledge down precisely, and how a computer can then work out what follows from it.

Compare the last two rows. “Is it raining?” and “It is raining” use almost the same words, but only the second is a statement. Whether it is true depends on which world we are in: on a wet day it is true, on a dry day it is false. That idea, that the same sentence can be true in one world and false in another, is at the heart of this half of the week.

8Knowledge-based agents

People reason from what they already know to reach new conclusions. CS50 starts with an example from Harry Potter. Suppose we know three things:

1. If it didn’t rain, Harry visited Hagrid today.
2. Harry visited Hagrid or Dumbledore today, but not both.
3. Harry visited Dumbledore today.

Did it rain today? None of the three sentences says so, but we can work it out. Sentence 3 says Harry visited Dumbledore, and sentence 2 says he did not visit both, so:

4. Harry did not visit Hagrid today.

Now sentence 1 says that if it had not rained, Harry would have visited Hagrid. Sentence 4 says he did not. So:

5. It rained today.

We reached sentence 5 by being clever: we picked the right sentences in the right order. A computer needs a method that works without cleverness. The rest of the week builds one: first a precise way to write the sentences (Sections 9 and 10), then a way to check what follows (Sections 11 to 13).

9Symbols, and joining sentences: not, and, or

Symbols

Writing out “Harry visited Hagrid today” every time is slow, so we give each statement a short name:

• It rained today. → rain
• Harry visited Hagrid today. → hagrid
• Harry visited Dumbledore today. → dumbledore

A symbol does not say whether its statement is true. It only names the statement. Whether rain is true depends on the world we are in.

Most sentences are built from smaller ones. Sentence 1, “If it didn’t rain, Harry visited Hagrid today”, contains two statements, “it rained” (with a “not”) and “Harry visited Hagrid”, joined by “if … then”. Propositional logic is logic built from symbols joined by five small words, called connectives: not, and, or, if … then, and if and only if. This section covers the first three, and Section 10 the other two.

Not, and, or

• not: “It did not rain.” → ¬rain
• and: “Harry visited Hagrid and Dumbledore.” → hagrid ∧ dumbledore
• or: “Harry visited Hagrid or Dumbledore.” → hagrid ∨ dumbledore

Read ¬ as “not”, ∧ as “and” and ∨ as “or”. Each connective has a simple rule for when the whole sentence is true:

• ¬P is true when P is false, and false when P is true: “not” flips the value.
• P ∧ Q is true only when both P and Q are true.
• P ∨ Q is true when at least one of P and Q is true.

Here P and Q stand for any two sentences. A table that lists every combination of true and false, and the value of a sentence in each, is called a truth table.

10If … then, and if and only if

• if … then: “If it is raining, then I am indoors.” → rain → indoors
• if and only if: “I am indoors if, and only if, it is raining.” → rain ↔ indoors

Read rain → indoors as “rain implies indoors”, and rain ↔ indoors as “rain if and only if indoors”. CS50 calls these two connectives implication and biconditional.

If … then

Think of rain → indoors as a promise: “If it is raining, I am indoors.” When is the promise broken?

• It is raining and I am indoors: the promise is kept, so the sentence is true.
• It is raining and I am outside: the promise is broken, so the sentence is false. This is the only way to break it.
• It is not raining: the promise says nothing about where I am, so it cannot be broken, whether I am indoors or not. The sentence counts as true.

The last case surprises most people. If the “if” part is false, the whole “if … then” sentence is true, whatever the “then” part says. Logically, we learn nothing from rain → indoors on a dry day.

If and only if

P ↔ Q is an “if … then” in both directions: P → Q and Q → P. “I am indoors if and only if it is raining” says that rain means indoors, and also that indoors means rain. So on a dry day I am outside. P ↔ Q is true exactly when P and Q have the same value.

Table 4 collects all five connectives.

11Models and knowledge bases

Whether a sentence is true depends on the world. With two symbols, rain and hagrid, there are four possible worlds: both true, only rain true, only hagrid true, or both false.

Each symbol can be true or false, so every new symbol doubles the number of possible worlds. With n symbols there are 2 × 2 × … × 2 = 2ⁿ models.

Is a sentence true in a model?

To find out, put the model’s values into the sentence and work from the inside out, using the rules in Table 4.

Knowledge rules worlds out. Suppose the KB is a single sentence, rain ∨ hagrid. It is false only in the world where both symbols are false, so that world is ruled out, and three are left. Every sentence we add can only rule out more worlds, never bring one back.

12Entailment

If “It is a Tuesday in January” is true, must “It is January” be true? Yes: every world in which it is a Tuesday in January is a world in which it is January. The other way round fails: on a Wednesday in January, “It is January” is true but “It is a Tuesday in January” is not. One world like that is enough to show that the second sentence does not follow from the first.

For a knowledge-based agent the question is always the same: does the knowledge base entail the sentence we want to know about, the query? In symbols, KB ⊨ query? For the Harry example: does our knowledge base entail rain?

13Model checking

Entailment says “B is true in every world where the KB is true”. The most direct way to check that is to look at every world. That is model checking.

Models where the KB is false are skipped: they are worlds that contradict what we know, so they do not matter. If the query is true in every model that is left, the KB entails it.

The same table answers other queries too. Does the KB entail ¬hagrid? In the one model left, hagrid is false, so yes: Harry did not visit Hagrid. Does the KB entail hagrid? No: the one model left is a counter-example.

14Knights and knaves, by model checking

In Week 1 you solved this puzzle in words. Most people reason like this: “Suppose A is a knight. Then what A said is true, so A is a knave. But A cannot be both, so A is not a knight. So A is a knave, which means A was lying: they are not both knaves. A is a knave, so B must be the one who is not. B is a knight.” That is good reasoning, but it needs a clever idea (“suppose A is a knight”) and a different clever idea for every new puzzle. A computer needs a method with no cleverness in it. This section builds one in four steps, and the steps work for any knights-and-knaves puzzle.

Step 1: name the statements

A statement is anything that is true or false. Here there are four, one for each thing a person might be. Give each a short name, a propositional symbol:

• AKnight: A is a knight.
• AKnave: A is a knave.
• BKnight: B is a knight.
• BKnave: B is a knave.

A symbol does not say whether its statement is true. It just names it. In one world AKnight is true; in another it is false. Our job is to find the world that fits everything we know.

Step 2: write down the rules of the island

The puzzle says every person is a knight or a knave. We also know nobody is both. In plain words, for A: “A is a knight or a knave, and not both.” In symbols:

(AKnight ∨ AKnave) ∧ ¬(AKnight ∧ AKnave)

Read it as: (A is a knight or A is a knave) and it is not the case that (A is a knight and A is a knave). The first bracket rules out “neither”; the second rules out “both”. Write the same sentence for B. Together these are sentence 1 of the knowledge base.

Step 3: write down what A said

A said: “We are both knaves.” As a sentence of logic that is simply AKnave ∧ BKnave. But we cannot add it to the knowledge base as it stands, because we do not know whether A was telling the truth. What we do know is the rule about who tells the truth:

• If A is a knight, then what A said is true. In symbols, sentence 2: AKnight → (AKnave ∧ BKnave)
• If A is a knave, then what A said is false. Sentence 3: AKnave → ¬(AKnave ∧ BKnave)

This is the one trick in the whole method: never write down a person’s statement on its own. Write “if knight, then it is true” and “if knave, then it is false”. The second sentence uses a “not” in front of the statement: ¬(both knaves) means “at least one of them is not a knave”. B said nothing, so there is nothing to write for B.

Those three sentences are the whole knowledge base. Nothing in it says what A or B is; the answer has to follow from it.

Step 4: check every world

Four symbols give 2⁴ = 16 worlds, but sentence 1 throws out every world where someone is both or neither. Only four worlds survive it: each of A and B is a knight or a knave. Now test sentences 2 and 3 in each of the four. The question to ask in each world is: is what A said true here, and is that what A’s kind allows?

Two things in the table deserve a second look. First, an “if … then” sentence holds whenever its “if” part is false: in the third row A is not a knight, so sentence 2 is not tested and cannot be broken. That is the “promise not tested” rule from Section 10, and it is what lets one sentence sit quietly while the other does the work. Second, the last row is the one people find surprising: two knaves looks consistent with “we are both knaves”, until you remember that a knave cannot say something true.

Reading off the answer

Only one world fits: A is a knave and B is a knight. Every sentence we care about is true in every surviving world (there is only one), so the knowledge base entails AKnave and it entails BKnight: KB ⊨ AKnave ∧ BKnight. This is the same answer as Week 1, found with no cleverness: name the statements, write the rules, check every world. If two worlds had survived, the puzzle would have two answers; if none had, the puzzle would contradict itself.

15In the code: logic.py and harry.py

The practical uses CS50’s logic.py (folder week04-knowledge/logic in the module code). It gives a Python class for each part of propositional logic: Symbol, Not, And, Or, Implication and Biconditional, plus the function model_check. Here is harry.py, the Harry example:

from logic import *

rain = Symbol("rain")
hagrid = Symbol("hagrid")
dumbledore = Symbol("dumbledore")

knowledge = And(
    Implication(Not(rain), hagrid),
    Or(hagrid, dumbledore),
    Not(And(hagrid, dumbledore)),
    dumbledore
)

print(model_check(knowledge, rain))

The four lines inside And(…) are the four sentences from Section 10, in the same order. And joins them into one knowledge base, true only when all four are. The last line asks whether the knowledge base entails rain, and prints True.

How model_check works

model_check does exactly what Section 13 describes, but it builds the models one symbol at a time. Its helper, check_all, takes the list of symbols that have no value yet:

• If every symbol has a value, the model is complete. If the knowledge base is true in it, return whether the query is true; if not, the model does not matter, so return true.
• Otherwise, take one symbol without a value, make two copies of the model (one where the symbol is true, one where it is false), and check both. The answer is true only if both checks say true.

A function that calls itself like this is called recursive. Each call fixes one more symbol, so with three symbols it reaches all 8 complete models, the rows of Table 6. Each sentence class has an evaluate(model) method that works out whether the sentence is true in a model, using the rules in Table 4.

16Heuristics and logic in the real world

• Sat-navs and video games: route finders use A* (with many refinements) and a heuristic such as straight-line distance.
• Computer chips and software: model checking is used to show that a design can never reach a bad state, by checking every state it could be in. Edmund Clarke, Allen Emerson and Joseph Sifakis shared the 2007 Turing Award for it. Industrial model checkers use far cleverer methods than a truth table, but the idea is the same: try every possibility.
• Railways: logic is used to check that signalling systems can never send two trains onto the same stretch of track.
• Product options: when you build a car or a computer online, logic works out which options can go together.

A question to think about: a railway signalling system has been checked by model checking, and in every world that fits its knowledge base no two trains share a track. Can we trust it completely? The check is only as good as the knowledge base. A missing or wrong sentence, or something the symbols do not cover (a broken sensor, a driver who ignores a signal), is outside the proof. People who understand the railway must check the sentences, and the system still needs testing in the real world.

Check yourself

Try these without looking back. The answers are at the end.

1. In Figure 1, what is h for the square directly below D? Is the real number of steps from that square to B more or less than h?
2. The frontier holds three squares with h = 9, 4 and 6, and g = 2, 10 and 6. Which one does greedy best-first search take next? Which one does A* take?
3. In maze4.txt, why does greedy best-first search find a 20-step path when a 16-step path exists?
4. Suppose h = 0 for every square. Does it ever overestimate? What would A* do then?
5. A robot in a grid can also move diagonally, one square at a time. Is Manhattan distance still admissible? Suggest a heuristic that is.
6. Which of these are statements? “Winchester is in Scotland.” “Shut the window!” “Is the robot holding a block?”
7. Let P be “It is sunny” and Q be “We go to the beach”. Write in symbols: (a) “It is not sunny.” (b) “If it is sunny, we go to the beach.” (c) “We go to the beach if and only if it is sunny.”
8. P is false and Q is true. Which of these are true? P ∧ Q, P ∨ Q, P → Q, Q → P, P ↔ Q.
9. How many models are there with 4 symbols? With 10?
10. Does rain ∨ hagrid entail rain? Give a model that shows why or why not.
11. CS50’s example. P: “It is a Tuesday.” Q: “It is raining.” R: “Harry will go for a run.” The KB is (P ∧ ¬Q) → R, P and ¬Q. Use model checking to decide whether KB ⊨ R.
12. The first Week 1 knights and knaves puzzle: A says “I am both a knight and a knave.” Using the symbols AKnight and AKnave, write the knowledge base and check the four models. What is A?

Key terms

Reading and next week

• Russell & Norvig, Artificial Intelligence: A Modern Approach (4th ed.): sections 3.5 and 3.6 (informed search and heuristics), and sections 7.1 to 7.4 (logical agents and propositional logic; 7.2, the wumpus world, is a longer example you can skim).
• Poole & Mackworth, Artificial Intelligence: Foundations of Computational Agents (3rd ed., free at artint.info): section 3.6 and section 5.1.

Next week: Knowledge and Planning. Model checking doubles its work with every symbol. Next week starts with ways to reason that do not check every world (inference rules, and a first look at first-order logic), then uses facts and actions to plan, and solves the Week 1 river crossing.