Homework 2 -- due Tuesday March 4

1. [60 points] Answer the following questions from Russell and Norvig:
   1. [15 points] Question 4.3
   2. [15 points] Question 4.11
   3. [15 points] Question 5.3
   4. [15 points] Question 5.4

2. [30 points] Do the following in Lisp.
   Do not forget to test your Lisp functions and submit both the functions and results on test cases using the IT Labs Submit Tool. The Lisp material you need for this part is covered in Chapter 3 from Lamkins (use of structures, i.e. (defstruct) and Chapter 6 (use of keywords and default values). You also need to understand the notation #'.
   1. [10 points] Download and install the Lisp code from the AIMA book. We will use only the search part, so you can download and compile only the search part, as explained down here.
      
      1. Go to http://aima.cs.berkeley.edu/lisp/doc/install.html and follow the instructions. If you want to save time, when you get to step 4 do the following:

          
         (load "aima.lisp")
         (aima-load 'agents)    ; loads the agents subsystem
         (aima-load 'search)    ; loads the search subsystem
         (aima-compile 'agents) ; compiles the agents subsystem
         (aima-compile 'search) ; compiles the search subsystem
         (test 'search)         ; tests the functions in the search subsystem
         

         When I did this part, using CLISP, I got an error message in the file agents/environments/wumpus.lisp, since kill is a system defined macro and should not be redefined. I fixed the problem by changing all occurrences of kill to something else. Alternatively you can remove wumpus.lisp from the agents susbsystem definition in aima.lisp. I also got a warning about redefining agent-body, but the progarm compiled fine.
      2. Test the search subsystem by typing: (test 'search) ; tests the functions in the search subsystem Check that there are no errors (look at the last line printed).
      You are now ready to use the search subsystem. For documentation on the functions defined in it, look at http://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html You can look at the code used to test it by looking at the file test-search.lisp
   2. [10 points] Run on the cannibals and missionary problem with 3 cannibals and 3 missionaries the following search algorithms: breadth-first-search, no-duplicates-breadth-first-search, no-returns-breadth-first-search, A*-search. Compare the algorithms using the function compare-search-algorithms (look for how to use it in the documentation or in search/test-search.lisp).
   3. [10 points] Compare, using the compare-search-algorithms function, the performance of the following search algorithms A*-search, greedy-search, uniform-cost-search to solve a TSP problem on the same randomly generated network of 15 cities. Look in the file search/domains/tsp.lisp to find out how to specify the number of cities. Make sure you run the three algorithms on the same set of cities. Do not change any of the functions in tsp.lisp. The time it takes to do the search depends on the specific of the random network. A* and greedy-search run fast, but uniform cost search can take a huge amount of time (hours and hours). So, instead of using uniform-cost-search in your comparison you are free to select a different algorithm from the algorithm collection available.
3. [10 points] [Graduate Students only] Graduate students have to answer this question (part of an old WPE question). Undergraduate students do not need to answer this question. They will get credit (10 points) for it without having to do any work. However, undergraduates are welcome to answer this question, which will count as some extra credit (precise amount to be decided).

   The question I listed originally was used in an old midterm. It has been replaced with a new one. Sorry for the inconvenience. Discuss the possible advantages of the following state-space search strategy: obtain by some method a path to a goal node and its associated cost C. This cost is not necessarily minimal but it gives an upper bound on the minimal cost. Now use A* with an admissible h function and discard immediately any open nodes reached whose f values are greater than C.

   1. Is the modified A* algorithm with this strategy guaranteed to find an optimal solution if one exists?
   2. Does the fact that the algorithm discards some of the OPEN nodes mean that fewer nodes are expanded?
   3. Does this strategy reduce the total storage requirements?