University of Washington
Department of Computer Science and Engineering

CSE573–Artificial Intelligence I

Autumn 1997


Problem Set #1.

Assigned October 10, 1997

Due October 20, 1997


LISP Drill and Agent Implementation



LISP Drill


Here are some standard recursive functions and small applications to write in LISP. In some cases these functions, or ones like them, are defined as part of the Common Lisp language. Do not use the built-in function in writing your solution.


  1. Write a function (add-numbers list), which returns the sum of all the numbers in its list argument. Non-numbers should be ignored. Write two versions: one in which the list is simply a flat list of objects (no nesting), the other in which the list structure may be nested.

  3. Write the function (obj-position object list) which returns the index of the first occurrence of the object in the list. Assume that the list is not nested. (Extra credit: extend the function so it would return a reasonable answer if the list is nested. First discuss what the function should return, then write the function that does so.)

  5. Write the function (generate-indices num) that takes as input an integer 0 or greater, and generates the list (0 1 2 ... num). You should signal an error if the argument is less than 0. (Hint: two functions may be easier than one.)

  7. The next two functions will be a binary search and a sort. In each case it will be useful to have a function that splits a list into its first half and its second half. Write two functions, (first-half list) and (second-half list) that do exactly that. Be careful about lists with odd numbers of elements. You want to assure that the list always splits into two disjoint sublists.





  1. A simple password module. Consider a module that stores user-ids and passwords, and is responsible for adding a new user/password pair, verifying a password, changing a password, and removing a user. You will implement this functionality by defining the following functions. In all cases, user-id can be a symbol, and password can be a string of arbitrary length.


One final complication: your database will consist of user-id/password pairs (an association list will work fine for this), but you should store the passwords encrypted. That is, write a helper function
(encrypt password-string) => new-string
and only store the encrypted result in the database.


Extra credit: do any or all.




Garbage Agent Implementation


(Code for this assignment is in the "usual" places:

    • on the instructional NT network in
    • in the directory
    • on the course web)


The "garbage agent" is like the vacuum agent we have already studied, only somewhat more complex. In this world there is paper, there is garbage, and there are recycling bins and garbage cans to put them in. The agent has a finite capacity to carry objects (default is 5). The performance measure rewards putting paper in recycling bins and garbage in garbage cans, it penalizes loose paper and garbage in the world, putting objects in the wrong receptacle, and each step taken.


You will find an "examples" file in which there are two simple agents. The first just waits a certain number of steps, then halts (which ends the simulation). This is to show how an agent can "remember" things like the number of steps, or the location of certain objects it has seen.


The second agent just wanders around the world, picking up paper and garbage when it can, and putting them in proper receptacles when it can.


You will work to extend this second agent, but first you should run it a few times to make sure you understand how it works.


  1. The first thing you might notice is that the wandering agent will never terminate. Develop a simple stopping criterion (After a fixed number of steps? After going N steps without finding any paper or garbage?) Incorporate it into the wandering agent.
  2. One thing the agent does particularly badly is that its wandering can be very inefficient. For example, the agent can get to an edge and repeatedly try to move through a wall. This is because it just chooses randomly between turn and forward actions. Change the agent's wandering behavior so it does not run into obstacles: it can "know" the size of the grid, and when it comes to an edge it can randomly turn away from the wall then continue to wander. In worlds where the only obstacles are the walls at the edge, this agent should never bump into anything.
  3. The current collecting behavior just picks up the first loose item available, until it reaches capacity. Since paper is more valuable than garbage to recycle, change the agent's policy so if there is loose paper on the ground, and the agent is carrying some garbage, it will put down the garbage and pick up the paper.
  4. This completes the "required" part of the assignment. Continue on for extra credit, as your background, interest, and time permits.
  5. The agent's policy of just wandering until it happens upon a receptacle to dump its garbage can be very inefficient, especially in worlds where there are few receptacles stuck in corners. Suppose the agent knows ahead of time where the bins and cans are. Modify its policy so that when it reaches capacity it heads for a bin or can, dumps its cargo, then continues.
  6. Now suppose the agent does not know the location of receptacles ahead of time. Extend the agent so when it encounters one in the world, it remembers the location, then proceeds as above. Allow your agent to remember receptacle locations between simulation runs. That is, we will test your agent by repeatedly running it in environments where the location of receptacles remain the same, but the location of paper and garbage are varied. We would expect your agent's behavior to improve over time.
  7. Finally, improve the agent's stopping criterion. If it knew the size of the grid, it could adopt a (conceptually) simple stopping rule: terminate when all paper and garbage are gone from the grid. Implement this policy.
  8. Super extra credit!! It's not clear that the policies you have implemented above are actually good ones—that they will lead to good scores. Suppose the agent knew the location of all paper, garbage, and receptacles from the very beginning. Modify the agent so it "thinks about" where it should go, what it should pick up, and where it should deposit it, and acts so as to optimize its score. (Caution: this is really hard!)