Homework 2 -- due Tuesday February 16

Written questions

1. [20 points]
   1. Can best first search ever find a better path than A*, where better means lower cost?
   2. If the definition of better includes the time to complete the search (finding a low cost is still the primary factor), can best first find a better path? A significantly better path?
   3. Draw an example for the previous question supporting either opinion.
   4. Using the definition of better from 1.b, what types of search spaces/properties of the search space that can cause A* to underperform best first? What is the property of A* that causes it to underperform?
2. [20 points]
   1. Is A* guaranteed to find the lowest cost path if you modify the way f is computed to be f = 3g + 3h? Why or why not? Draw an example to help explain your answer.
   2. Repeat the previous step using the formula f = g + 3h
   3. Repeat the previous step using the formula f = 3g + h
   4. The terms g and h each play a different role in A*. What are those roles? What happens when you emphasize or de-emphasize one of them?
3. [10 points] A* is optimal in that it finds the lowest cost solution. However, this is not the only property of an algorithm that is important. When might a different search algorithm be preferred to A*? Give a concrete example.
4. [15 points] Question 3.14 from the third edition of the book.
   If you do not have this edition, here it is:
   Which of the following are true and which are false. Explain your answers:
   1. Depth-first search always expand at least as many nodes as A* search with an admissible heuristics.
   2. h(n)= 0 is an admissible heuristic for the 8-puzzle.
   3. A* is of no use in robotics because percepts, states, and actions are continuous.
   4. Breadth-first search is complete even if zero step costs are allowed.
   5. Assume a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves.
5. [10 points] Question 3.21 from the third edition of the book. It is question 4.3 in the second edition.
6. [10 points] Question 3.30, parts a and b from the third edition of the book. It is question 4.8 in the second edition.

Lisp questions

1. [15 points] For this question we will use the AIMA softare for the TSP problem that you will find in search/domains/tsp.lisp. Do not change any of the functions in tsp.lisp. You should load the aima software as you did for the first homework and then load a file with any changes you want to make to the AIMA functions and with your new functions.
   1. generate randomly a TSP map with 8 cities using the function random-tsp-map (in aima/search/domains/tsp.lisp) and compare using the AIMA function compare-search-algorithms, the performance of A*-search, greedy-search, and another search algorithm of your choice on the TSP map you have created. Look in the file search/domains/tsp.lisp to find out how to specify the number of cities in a randomly generated map. Make sure you run the three algorithms on the same map, otherwise you'll get very different results. The time it takes to do the search and the cost of the optimal solution depends on the specific random network that has been generated. A* and greedy-search will run fast, but uniform cost search can take a large amount of time. Try to avoid it and choose a different algorithm.
   2. Repeat the previous step two more times generating two other different random maps and comparing the same search algorithms on them. Write Lisp code to compute the average cost and standard deviation of the cost of the paths found by the different algorithms for the three different maps.