CS 232 Assignment 2 Due: Tuesday, Sept. 26

This assignment explores the implementation of basic search methods and the application of these methods to solving the 9-Squares Puzzle and the Water Jug Problem. To begin, copy the following subdirectory of code files onto your own directory by connecting to your cs232 subdirectory and executing the following copy command in Unix:

     cp -R ~cs232/download/search/ .

(Note the period at the end of the command.) Connect to this subdirectory to see the following four code files: search.lisp, cities.lisp, 9squares.lisp, waterjug.lisp. The last three files, which are specific to the applications of the search methods, each contain a definition of the functions goalp, same-state, get-next-states, path-length, and distance, so if more than one of these files is loaded into your clisp environment, the most recent version overrides a previous version.

Submission details for the entire assignment appear at the end of this document.

Problem 1: Completing the Basic Search Methods

The search.lisp file contains completed code for most of the search methods discussed in class. There are two search methods, however, whose implementation is not yet complete: best-first search and branch-and-bound-estimate search. To complete the best-first search method, fill in the body of the queue-best-first function whose skeleton appears in the code file. The branch-and-bound-estimate search method evaluates each path using the sum of the length (or cost) of the path so far and an estimate of the distance remaining to the goal. To complete the implementation of this method, fill in the body of the functions queue-branch-and-bound-estimate and total-path-length, whose skeletons appear in the file. Hint: queue-branch-and-bound-estimate is very similar to queue-branch-and-bound. Note that the two functions path-length and distance are defined in separate files that are application-specific (cities.lisp, 9squares.lisp, and waterjug.lisp). The A* search method also uses the total-path-length function that you will complete.

You can test your completed code on the problem of searching for a path through the network of cities. Load the initial code files into your clisp environment as follows:

     (load "cities.lisp")
     (load "search.lisp")

If you were not connected to your search subdirectory when starting clisp, you will need to specify the complete path, e.g. "~username/cs232/search/cities.lisp". Once the full code files have been loaded in, you can re-load a single, modified function as you did earlier. To use the best-first and branch-and-bound-estimate strategies, you can call the search-cities function as follows:

     (search-cities #'best-first)
     (search-cities #'branch-and-bound-estimate)

Remember that the final search path is printed in reverse, from start to goal.

Problem 2: Using Search to Solve the 9-Squares Puzzle

The 9-squares puzzle consists of a 3x3 grid of 8 tiles and a blank space, initially placed in a random configuration. For example, if the tiles contain integers, an initial configuration might be given as follows:

The object of the puzzle is to move the tiles into a goal configuration. On each move, one of the tiles that is adjacent to the space can be moved into the position of the space. The following is the goal configuration for the above puzzle:

The file 9squares.lisp contains partial code to use with the search functions in search.lisp to solve the 9-squares puzzle. The state of the puzzle is represented by a 9-element list, where the first three elements contain the tiles for the top row of the puzzle, the second three elements store the middle row of tiles, and the last three elements store the bottom row of tiles. The space is represented by S. For example, the top two puzzles would be represented by the lists (4 7 3 8 2 6 1 S 5) and (1 2 3 4 5 6 7 8 S).

Part a: The functions move-up and move-left take an input state and return a new state in which the space tile has been shifted upwards or to the left, respectively. In both cases, if the requested move cannot be made, because the space is at the top or left edge of the board, these functions return NIL. Using these two functions as guides, complete the definitions of move-down and move-right. The position function is a built-in Common LISP function that returns the index of a particular element contained in a list. The exchange function is defined earlier in this code file. First test your functions on their own with different input states before testing them with the general search code. When the functions are working, you can then test them with methods such as A* search:

     (search-9squares #'A* start3)

If you do not want to see so much printout, comment out the format statement in the extend function. Warning: Certain search methods, like depth-first search, can take a very long time to solve the 9-squares puzzle, so you may want to avoid them.

Part b: The quality of the estimate of the distance to the goal state can affect the efficiency of the search process. Currently, this distance estimate uses a measure called the Manhattan distance. The Manhattan distance between two locations on a grid is the sum of the differences in their row and column numbers. For example, the Manhatten distance between the upper left and lower right corners of the 9-squares puzzle is 4 (the two locations differ by two rows and two columns). A simpler estimate to use for the 9-squares problem is the total number of tiles (including the space) that are still in the wrong place. For example, the distance between the first configuration shown above and the goal state is 7, because only the 3 and 6 are in their final position. Temporarily comment out the current distance function and write a new version of this function that returns the number of tiles that are in different places in the two input states. You can think of this function as computing the number of locations in the input lists state1 and state2 that have different contents. Test your new function on specific examples, such as:

     (distance '(5 2 6 4 8 1 7 3 S) '(1 2 3 4 5 6 7 8 S))

which should return 5. Using A* search, compare the number of paths extended for solving the 9-squares puzzle with the initial states start1, start2 and start3 (defined at the beginning of 9squares.lisp), and with the two different distance functions. How does the number of paths extended differ for the two methods for estimating the distance to the goal? Does this method always make a difference?

Part c: For the same three initial configurations used in Part b, compare the number of paths extended during the search for a solution, using the following three methods of search: breadth-first, branch-and-bound and A* (using Manhattan distance). How do the methods compare, in terms of the amount of work required to find a solution?

Problem 3: The Water Jug Problem

Another classic problem that is often used to illustrate AI problem solving strategies and search is the Water Jug Problem described as follows:

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither jug has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?

If you consider a simple set of possible operations that can be applied at each moment and formulate the problem as a search problem, a solution can be found quite easily. Assume that you can only perform one of the following eight operations:

(1) Fill the 4-gallon jug
(2) Fill the 3-gallon jug
(3) Empty the 4-gallon jug on the ground
(4) Empty the 3-gallon jug on the ground
(5) Pour water from the 3-gallon jug into the 4-gallon jug until the 4-gallon jug is full
(6) Pour water from the 4-gallon jug into the 3-gallon jug until the 3-gallon jug is full
(7) Pour all the water from the 3-gallon jug into the 4-gallon jug
(8) Pour all the water from the 4-gallon jug into the 3-gallon jug

There are natural preconditions for the application of these operators. For example, in order to apply operator (3), there must be some water in the 4-gallon jug, and in order to apply operator (8), the amount of water currently in the 4-gallon jug cannot exceed the space that is available in the 3-gallon jug.

Part a: In this part of the problem, you will complete an implementation of the application of search methods to the solution of the Water Jug problem. In particular, you will complete the code that determines the possible operators that can be applied to the current state of the problem to reach a new state. The state of this problem is represented by a list that contains two numbers, where the first number is the amount of water in the 4-gallon jug and the second number is the amount of water in the 3-gallon jug. In order to keep track of the operators that are applied at each step, the state list also contains a third element that is the operator that was applied to reach the current state from the previous state (the operators are represented by the names OP1 to OP8). If both jugs are full, for example, and the current state was reached from the previous state by applying operator (2), then the current state of the problem is (4 3 OP2). The initial state is (0 0). The goal state that you are trying to reach must have a 2 as the amount of water in the 4-gallon jug, but the amount of water in the 3-gallon jug does not matter. During the search for a solution to this problem, a partial path in the search tree is represented as a list of nested three-element lists (with the two-element initial state at the end), such as the following:

((1 0 OP4) (1 3 OP6) (4 0 OP1) (0 0))

In a valid path, each state in this list can be reached from its neighbor on the right by the application of the specified operator. In the above path, for example, the state of the jugs (4 0) can be reached from the initial state (0 0) using operator (1). As in previous search applications, a queue of partial paths is maintained as the search progresses.

In the waterjug.lisp file, the definitions of the functions op1, op3, op6 and op8 are complete, and implement the operators (1), (3), (6) and (8), respectively. Each of these functions has a current state as input. If the associated operator is applicable, given the current state, a new state is computed and returned. The op1 function, for example, captures the fact that the operator "(1) Fill the 4-gallon jug" can be applied only if the 4-gallon jug is not yet full, and the function returns a list with 4 as the first element, reflecting the fact that the 4-gallon jug is full after applying this operator. The op6 function captures the fact that the operator "(6) Pour water from the 4-gallon jug into the 3-gallon jug until the 3-gallon jug is full" can be applied only if the 3-gallon jug is not yet full, and there is enough water in the 4-gallon jug to fill the 3-gallon jug. The op6 function returns a list that incorporates the reduction of water in the 4-gallon jug, and the fact that the 3-gallon jug is now full. The functions op1...op8 are expected to return NIL if a particular operator cannot be applied to the current state. The get-next-states function, which is also complete, first creates a list of the results returned by the functions op1, ... op8. Some of the returned values will be nil. The remove-if function is then used to remove any nil values from this list. The function new-remove-duplicates is then used to remove any duplicate elements from the list of new states.

Your task in this part of the problem is to fill in the definitions of the four functions op2, op4, op5 and op7. To test your new definitions, each function can be called directly, and the get-next-states function can then be called directly to test the combined use of all of these functions.

Once your four new functions are working correctly, you can run the search code to solve the Water Jug problem by calling the function search-waterjug with a particular input search strategy, for example:

    (search-waterjug #'breadth-first)

You can see the English instructions for the final solution path as follows:

    (setf path (search-waterjug #'breadth-first))
    (print-solution path)

Part b: Call the search-waterjug function with the following search functions: breadth-first, depth-first, and branch-and-bound. In the results, examine things such as the length of the solution found and the number of paths extended during the search. Observe both the similarities and differences in these two properties across the three search methods and briefly explain why they are similar or different.

Part c (optional): The current search code stops after finding a single search path. In some cases, you may want to continue the search process until all possible paths are found. Create a new version of the search code that finds all solutions to the Water Jug problem. Maintain a global variable that keeps track of the total number of solutions found. Your code should print each solution as it is found (in addition to the number of paths extended), and then print the total number of solutions at the end. Observe the order in which solutions are found using breadth-first, depth-first and branch-and-bound search. Briefly explain any similarities and differences that you observe.

Submission details: Hand in a hardcopy of all of the functions that you completed and your answers to the questions. Drop off an electronic copy of all of your code files by connecting to your search subdirectory and executing the submit command as follows:

     submit cs232 search *.lisp

All of the code files in your search subdirectory will be dropped off at once.