CS 4804 Homework #1

1. (10 points) Exercise 3.15 from your textbook. You do not have to do any programming, just read the robot navigation problem described there and cast the problem formally as search. First, classify the environment of this problem using the distinctions given in Section 2.3. What is the start state? What are the allowed moves/operators? How is cost measured? What is the goal test?
   
   
2. (10 points) Exercise 4.4 from your textbook.
   
   
3. (10 points) Exercise 4.6 from your textbook.
   
   
4. (30 points) Consider an infinite chessboard, where we are given a board position as the start state and another board position as the goal state. The objective is to go from the start to the goal using only knightly moves (i.e., following the rules of a knight). First determine if this problem is solvable for all cases. Then formulate the problem systematically as search, defining states, operators, goal test, and cost of a solution path. Finally, devise an admissible heuristic for solving it. Tighter heuristics will get higher points. A heuristic such as "h(n)=0" will fetch h(n) points.
   
   
5. (40 points; programming) For this question, you are going to write a program for solving the 8-puzzle. But you should structure your code in such a way that it can play the 15-puzzle as well. Your program must implement A* with pattern database heuristics as described in Chapter 4.
   
   Before you begin, notice that some 8- and 15-puzzle problems are not solvable (why?). So even if you run your perfect heuristic on a problem that is unsolvable, you will end up exhaustively searching the space before giving up. Therefore, create a collection of solvable test problems to pit against your program. This can be easily done by starting with some random tile layout, making a sequence of moves (randomly), and choosing the resulting layout as the goal state.
   
   First define the goal state unambiguously. Keep this fixed for the entire assignment. Create lots of "patterns" that vary in the amount of tiles that are being moved to their right positions. For instance, the example in Fig 4.9 of your book uses 4 tiles. You can create patterns with 3 tiles, 1 tile, 6 tiles, etc. For each pattern, do a BFS, compute the actual costs from various start positions, and record them in your "pattern database".
   
   Compare various runs of A* search (with different heuristics that vary in the amount of tiles used in the pattern) and also breadth first search (BFS; with h(n) = 0). Present results of the following form (graphs or tables):
   
   
   • Number of nodes expanded by A*, for each heuristic, versus BFS, for both problem sizes, i.e., 8-puzzle and 15-puzzle
   • Effective branching factor (see textbook; Section 4.2) for A*, with each heuristic, versus BFS, for both problem sizes
     
     
   To have confidence in your results, it is recommended that you average each measurement over multiple problems (of a given size).
   
   Make observations about the effectiveness of the heuristic (i.e., how much it prunes) versus the amount of space/memory required to store the pattern database. Is the time taken to compute the heuristic a consideration?