Homework 1 -- due Thursday February 1

Written questions

1. [15 points] A robot has to deliver three identical packages to locations A, B, and C in an office environment. The robot starts in location S holding the packages. The environment is a grid of squares, some of which are free (so the robot can move into them) and some of which are occupied (by walls, doors, etc.). The robot can move in the horizontal or vertical direction into neighboring squares, one square at a time, and can pick up and drop packages if they are in the same square as the robot.
   1. Specify the state space representation of the problem by specifying the states, the initial state, the goal test, the actions, and the cost of the actions. Be precise and consistent.
2. [25 points] This question is on using the proper search algorithm for each problem. The algorithms to compare are:
   1. depth-first,
   2. breadth-first,
   3. depth-limited depth first,
   4. iterative deepening depth first,
   5. bidirectional.
   For each of those algorithms describe briefly an example of a problem for which the algorithm is well suited and one for which it is not. Be specific and precise. For example, uniform cost is appropriate to find a path in a graph, where each node represents a location and the cost of each arc is the distance between the two locations connected by the arc. Uniform cost is not useful for problems where all the actions have the same cost, and for problems that have a complete state formulation (see Section 3.2.1 for the definition).
3. [15 points] This question is on properties of search algorithms. You need to explain the reasons for your answers, not simply write the name of one algorithm.
   1. if you want to limit the memory requirements, which algorithm(s) would you choose? why?
   2. if you want to limit the time required the find a solution, which algorithm(s) would you choose? why?
   3. if you want to find the minimum cost solution, which algorithm(s) would you choose? why?
   4. if you want to solution with the minimum number of steps, but you do not want to use a lot of memory, which algorithm(s) would you choose? why?
   5. if you want to parallelize your algorithm, which algorithm(s) would you prefer? why? [this is not in the textbook]
4. [10 points]
   1. If you are given a problem described using a state space representation and add 10 to the cost of each action, will the optimal solution be the same as the one with the original costs? Explain.
   2. If in the previous problem instead of adding 10 to the costs of each actions you double its cost, will the optimal solution be the same as the one with the original costs? Explain.
5. [10 points] Does a finite state space always lead to a finite search tree? What if the finite state space is a tree? Can you be more precise about what types of state spaces always lead to finite search trees? [Be short but precise. Explain your answers. You can support your answer with example or counterexamples, or use more formal arguments.]
6. [10 points] If you do not use CLOSED (this is what the textbook calls explored set in Fig 3.7) in an algorithm that uses it, what happens? be specific on what happens in each of the algorithms that we have studied.

Programming Part

1. Download and install the AIMA book code from https://github.com/aimacode. The code is written for different programming languages. The ones we will use are lisp https://github.com/aimacode/aima-lisp or python https://github.com/aimacode/aima-python.
2. Use the code to run the vacuum cleaning agent.
3. To show that you have the software installed and working, and you know how to use it, show the output of the program.
   For the output, if you start the program from the command line in linux you can save the output into a file (let's call it output.txt) using the command

    % script > output.txt 

   
   If you use windows or do not use the command line, submit a screen dump that shows the output of the vacuum cleaning agent.
   If you use Lisp there are other ways of capturing the output. See http://www-users.cs.umn.edu/~gini/lisp/output.html for details.
   You can upload multiple files.

Details on using the software

• If you use python, look at the detailed instructions at https://github.com/aimacode/aima-python/blob/master/README.md.
  To test the code in the aima-python directory, execute the command
  

      python3 -m doctest -v *.py
  

  The "-v" is optional; it means "verbose". Various output is printed, but if all goes well there should be no instances of the word "Failure", nor of a long line of "". If you do use the "-v" option, the last line printed should be "Test passed."
  To pass all the tests, you'll need to separately download the files in https://github.com/aimacode/aima-data and put those files in your copied repository under the data folder.
• If you use Lisp, here are the steps:
  • make sure you have a Lisp system working. Look at Lisp Info for information on the implementations available in the cselabs and for free implementations you can download. I like clisp, it is fast to load and works well.
  • Go to https://github.com/aimacode/aima-lisp and download the code.
  • Edit the file "aima.lisp" to change the value of the parameter *aima-root* on line 9 to reflect the location of the files. Make sure to use the proper syntax for a directory, not a regular file. For example, on a Unix file system, you want something like "/usr/local/aima/", or "/home/yourname/aima/", where the final "/" indicates that /usr/local/aima is a directory. For a Windows file system, you'd have something like "c:\\aima\\". Note that you have to use double backslashes, because backslashes are treated specially in Common Lisp strings. In most versions of Windows you can also use forward slashes: "c:/aima/", but check to see if this works on your system before you try it. For most installations, this will be the only edit you need to make.
  • Start up your Common Lisp, and enter 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 agents subsystem
    

    When I did this part, using CLISP, I got a couple of error messages in the file agents/environments/wumpus.lisp, since kill is a system defined macro and should not be redefined. CLISP allows you to continue. If you have trouble with it, you can change all the occurrences of kill to something else. I also got a warning about redefining agent-body, but the program compiled fine.
  • 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).