Intelligent Systems
CS 520

Test 1, 4 October 2011

1. Explain what happens to A* search when the heuristic it uses isn't an underestimate of actual costs.

   ---

   A* search is best-first search augmented with a heuristic function that estimates the cost of reaching a goal state from a vertex. The cost function for A* search is the sum of the actual cost of reaching a vertex v from an initial state plus the estimated cost of reaching a goal state from v.

   If the A*-search heuristic function consistently underestimates the cost of reaching a goal state, then the first goal state the search finds will be optimal (least cost). However, if the heuristic function overestimates the cost of reaching a goal state, the A* search may produce a sub-optimal solution. For example, if a sub-optimal solution has a smaller overestimate than the optimal solution, the A* search will favor the sub-optimal solution given its better (cheaper) over-all cost.

2. Dogs love cheese and Wrigley is a dog. Represent these facts in a knowledge base, and show how your knowledge base entails Wrigley loves cheese.

   ---

   The knowledge base is

   KB: { Wrigleyisadog, Wrigleylovescheese \(\leftarrow\) Wrigleyisa dog }

   Assuming a model for KB (which exists because KB is a propositional knowledge base), the two clauses in KB and modus ponens lets us conclude KB \(\models\) Wrigleylovescheese.

3. Search B is breadth-first search; search ID is some other search augmented with iterative deepening. Is there ever a case in which ID is better than B? If so, give an example showing when ID is better than B; if not, explain why B is uniformly better than ID.

   ---

   The trick is figuring out what “better” means. Iterative deepening has no inherent advantage over breadth-first search in terms of the solutions produced, so adding iterative deepening to the search underlying ID isn't going to change anything in that respect.

4. Given the two procedures top-down proof (TDP) and bottom-up proof (BUP), does there exist a propositional knowledge base which causes one of the two procedures to produce a result but the other procedure to churn forever, never producing a result? If so, produce such a knowledge base and show how it effects each of the procedures; if not, explain why no such knowledge base exists.

   ---

   The top-down proof could get stuck in an infinite loop if the knowledge base contains a rule in which the head appears in the body, as in a \(\leftarrow\) a \(\wedge\) b.

5. Poole and Mackworth claim that breadth-first search can't use bit-per-node cycle detection. Is this always true, or are there circumstances under which breadth-first search can use bit-per-node cycle detection? Justify your answer.

   ---

   Breadth-first search may use bit-per-vertex cycle detection when the existence of a solution is more important than the path used to reach the solution.

6. The propositional knowledge base KB contains

   a \(\leftarrow\) b \(\wedge\) c
   b \(\leftarrow\) d
   b \(\leftarrow\) e
   c
   d \(\leftarrow\) h
   e
   f \(\leftarrow\) g \(\wedge\) b
   g \(\leftarrow\) c \(\wedge\) k
   j \(\leftarrow\) a \(\wedge\) b

   a) Find the smallest model M for KB. Explain why M contains the atoms it does.

   b) Modify KB to create a non-empty model M' that is smaller than M. Explain the modification and the contents of M'.

   ---

   a) The atoms c and e must be in the model, otherwise KB would contain false clauses (either under a closed-world assumption or by their absence from the model). If e is true and b \(\leftarrow\) e is to be true, then b must be true too. If b and c are true and a \(\leftarrow\) b \(\wedge\) c is to be true, then a must be true; similarly with a and b true and j \(\leftarrow\) a \(\wedge\) b to be true, then j must be true. The remainder of the atoms (d, f, g, and k) can be false, leaving the remaining clauses true. The model is

   M = { a, b, c, e, j }

   b) There are lots of modifications to KB that would produce a non-empty smaller than the one found in a). Perhaps the easiest change is to drop e from KB. Now the model is just { c }. model .quiz answers A* search could return paths which aren't optimal. It would be possible for the heuristic function to return an f value for a node X on the optimal path that when added to the cost value of X results in a larger estimated cost then some non-optimal node y. Node y would be selected instead, and the resulting path wouldn't be optimal.