Homework 1 -- due Thursday February 7

Written questions

1. [15 points] Answer the following questions briefly but precisely:
   • Can an agent that keeps no history of its percept sequence be rational? Please explain.
   • Why performance measures for an agent should be designed according to the effects in the environment instead of the behaviors of the agent?
   • Why it is important to know if an agent's environment is fully observable or if it is partially observable?
2. [25 points] You are given the following problem: Given a 7-gallon jug filled with water and an empty 3-gallon jug can you have precisely 5 gallons of water in the 7-gallon jug? Assume you can fill the jugs with water as many times as desired, but you cannot measure how much water is in each jug. When you move water out of a jug you can either fill up the other jug or dump the water.
   You are to formulate the problem using a state-space search representation. Describe (precisely):
   1. what is the initial state
   2. the goal test
   3. the actions. Write the actions as rules, specifying applicability conditions and resulting state. For instance, if a state is a pair (x,y) of the amount of water in the 7-gallon jug and the amount in the 3-gallon jug, here are a couple of actions:
      Fill the 7-gallon jug: if (0, y) then (7, y)
      Move 3 gallons from 7-gallon to 3-gallon jug: if (x, 0) and x>3 then (x-3, 3)
   4. is the state-space a tree or a graph?
   5. show graphically the state space explored and the solution you found (there might be more than one solution).
3. [20 points] You are given an instance of the traveling salesperson problem (TSP). A salesperson has to visit a group of cities, visiting each only once and getting back to the starting city. Assume each city is directly connected to each other city. The objective is to minimize the total distance traveled.
   • Describe a state-space representation for the problem, specifying the initial state, goal state(s), and actions.
   • For a problem with $n$ cities, how many states are there in the search space? Explain briefly your answer.
4. [20 points] This question is on properties of search algorithms. Consider the following algorithms:
   • depth-first,
   • breadth-first,
   • depth-limited depth first,
   • iterative deepening depth first,
   • bidirectional.
   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?

Programming Part

1. [10 points] Download and install the AIMA book code from https://github.com/aimacode. Once done, submit the file that shows all test were run successfully.
   To show the output of your program, 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.

   The AIMA 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.

   Details on using the python 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.

   Details on using the Lisp software

   • 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).
2. [5 points] Use the code to run the reflex vacuum agent.
3. [5 points] Use the code to run the random vacuum agent.
   Copyright: © 2019 by the Regents of the University of Minnesota
   Department of Computer Science and Engineering. All rights reserved.
   Comments to: Maria Gini
   Changes and corrections are in red.