Artificial Intelligence Problem Set 1 Solution

Description

Problem 1. (20 pts) Rush Hour

Consider the following “Rush Hour” puzzle. Recall that the rules for solving the puzzle are that vehicles can move only back or forward (no turning). The goal is to get the red car out of the parking lot through the exit at right.

2.1 (1 pt) Solve the problem and present your solution.

2.2 (7 pts) Give as accurate an estimate as you can for the size of the problem space for this puzzle. (The estimate should be for this instance of the puzzle, not a “general” estimate for an arbitrary Rush Hour puzzle.) Explain the rationale behind your estimate.

2.3 (7 pts) Suggest a plausible “h” function that would be appropriate for A* search for a general instance of the Rush Hour puzzle. (The function should be a non- trivial but easily computable underestimate of the number of moves required to solve the puzzle from a given position.)

2.4 (5 pts) Did your solution in 2.1 have features in common with (e.g.) depth-first search? Breadth-first search? Means-ends analysis? Would bidirectional search be a good idea for this puzzle? Why or why not?

Problem 2. (15 pts) Bidirectional Search

Answer problem 3.15 (p. 116) in the Russell-Norvig text.

Problem 3. (15 pts) Turing and Searle

Choose your favorite of the “objections” from either the Turing or Searle papers and write a short paragraph or two explaining why you find that particular objection particularly provocative (regardless of whether you actually agree or disagree with it).

Problem 4. (50 pts) Implementing Depth-First Search

Consider the “milk-can transfer” problem shown in class. (Briefly: there are two 40-quart cans, both full; one empty five-quart can; and one empty four-quart can. Your job is to transfer milk between the cans without spilling until there are two quarts in each of the smaller cans.)

5.1 (5 pts) With as much accuracy as you can, calculate the size of the problem space for this problem. (Or, to put it another way: how many distinct achievable states are there?)

5.2 (45 pts) Write, in whatever language you prefer, a depth- first search algorithm that solves the milk-transfer puzzle and show a well-documented printout of your program and solution. Try to experiment with variations on the basic DFS algorithm shown in class: for instance, you might want to experiment with a version that maintains both an “open” and “closed” (i.e., “already-tested”) list of nodes.