Homework 2 -- due Wednesday February 11

Written questions

1. [10 points] Answer Question 3.6 (page 90) of the textbook
2. [15 points] Answer Question 3.8 (page 90) of the textbook
3. [15 points] Answer Question 4.3 (page 134) of the textbook
4. [10 points] Answer parts a and b of Question 4.8 (page 135) of the textbook.
5. [10 points] This is only for Graduate Students (an old WPE question). Undergraduate students do not need to answer this question, they will get credit for it without having to do any work. Undergraduates are welcome to answer this question for extra credit.
   You are to provide a state-space representation for a simple scheduling problem, which is defined as follows: you are given a collection of tasks (task1, task2,...) and their respective execution times (d1, d2,...). The tasks are to be executed using 3 identical processors. Any task can be executed on any processor, each processor can execute one task at a time. The scheduling problem is to assign tasks to processors so that the time when the last task is completed is minimized.
   Specify the problem (not its solution!) by answering the following questions. Justify your answers briefly.
   1. Describe the problem as a search space problem. Provide a representation for the states and characterize the initial state, goal test, actions, and path cost.
   2. Is the search state a tree or a graph?
   3. Propose a non trivial heuristics (h=0 is not allowed) and analyze it with respect to admissibility and monotonicity.

Lisp questions

The Lisp material you need for this part is covered in Chapter 3 from Lamkins ("Structures let you store related data" i.e. (defstruct) and Chapter 6 (use of keywords and default values in structures). You also need to understand the notation #'.

For documentation on the functions defined in the aima search system, look at http://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html For the agents functions look at http://aima.cs.berkeley.edu/lisp/doc/overview-AGENTS.html

You can look at how the functions are called by looking at the file search/test-search.lisp and at agents/test-agents.lisp. You do not need to use deftest for your programs. If you decide to use deftest you can find its documentation in http://aima.cs.berkeley.edu/lisp/doc/overview-UTILITIES.html under Testing Tool: deftest and test. deftest is a macro, so it follows different evaluation rules.

1. [10 points] Download and install the Lisp code from the AIMA book. We will use only the search and agents part.
   • 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 type 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
     (test 'agents)         ; 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. I also got a warning about redefining agent-body, but the program compiled fine.
   • Test the search and agents subsystem by typing:

     (test 'search)         ; tests the functions in the search subsystem
     (test 'agents)         ; tests the functions in the agents subsystem
     

     Check that there are no errors (look at the last line printed).
2. [10 points] You will use the 8-puzzle problem as defined in the aima software.
   1. Create an instance of the 8-puzzle problem and print the instance.
   2. Solve the instance using the A*-search algorithm. If it takes too long to solve it, generate a different instance and try again. Why does the solution time vary?
   3. Compare the performance of no-duplicates-breadth-first-search and A*-search using the function compare-search-algorithms (look for how to use it in the documentation or in search/test-search.lisp).
3. [10 points] Run the reactive vacuum agent defined in the agents system in a 4x4 room. Change the distribution of dirt and observe how it affects performance.