University of Washington

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.

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.

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.)

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.)

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.

A binary search looks for an element in a sorted list as follows: split the list into the first and second half. If the element in question is less than the first element in the second half of the list, search for it in the first half. Otherwise search for it in the second half. The search terminates when the size of the list is 1 or less. Write the function
(binary-search integer sorted-list-of-integers).
The function should return NIL if the input integer is not in the list.

A merge sort is a simple way of sorting a list. The idea is that you split the list into two lists of equal length, recursively sort each shorter list, then merge the result. (The base case for the recursion is that a list of length 0 or 1 is already sorted.) Write the recursive function merge-sort, which takes a single list of integers as input and returns it sorted. In implementing the sort you should also write a recursive function my-merge that takes two sorted lists as input and merges them to produce a single sorted list. (MERGE is already a function in Common Lisp and the interpreter complains if you re-define that function. You are to write your own version of merge; don't use the built-in version.) Extra credit: make merge-sort work on arbitrarily nested lists of integers.

Now put them together: write a function
(hideously-inefficient-search number list-of-numbers)
that searches for the number in the list by first sorting the list, then using binary search.

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.

(add-user user-id password)
Add the user-id/password pair to the database. Return T if the add succeeds, NIL if it fails because the user-id already exists.

(remove-user user-id password)
Remove this user from the database. Return T if the remove succeeds, NIL if it fails because the user does not exist or the password is invalid.

(verify-password user-id password)
Return one of the following symbols :VERIFIED, :NO-SUCH-USER, :INVALID-PASSWORD

(change-password user-id old-password new-password)
Return T if the change succeeds, NIL if it fails because the user does not exist, or the old-password is invalid.

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.

Presumably your first solution to the problem will be to store the database in a global variable. Of course that means that anybody can change its value. Hide the database so only the access functions you define can search or modify the database directly.
Package up the module into a single package, with the four functions above exported as the public interface.
Write a driver loop outside that package that tests the package by prompting for operations, user-ids, and passwords, and printing the results.

Garbage Agent Implementation

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

on the instructional NT network in
courses\\cse573\\garbage-world

in the directory
/projects/ai/573/garbage-world

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.

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

This completes the "required" part of the assignment. Continue on for extra credit, as your background, interest, and time permits.

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

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!)