CSC 550: Introduction to Artificial Intelligence
CSC 650: Advanced Artificial Intelligence
Spring 2003

HW3: State Spaces & Informed Search

  1. Consider the Water Jugs problem described in class (see reed/csc550/Code/jugs.scm). In Assignment 2, you used various uninformed search strategies to solve this problem and compared their behavior using the built-in time predicate. For this problem, you will compare informed approaches using the following heuristic: take the sum of the differences in jug contents in the current state versus the goals state, then negate it and divide by 2. For example, suppose the contents of the large and small jugs in a given state are 4 and 1, respectively. Assuming the goal state specifies 2 and 0, the differences in volumes in the large and small jugs are |4-2| = 2 and |1-0| = 1, respectively. Adding these two values, negating, and dividing by two yields the heuristic value -1.5.

    1. Since a heuristic value is intended to quantify how "close" a given state is to the goal, it follows that the goal state should have the highest possible heuristic value. Is this true here? Justify your answer.
    2. Using this heuristic, would hill-climbing be able to solve the Water Jug problem? That is, starting with both jugs empty, would hill-climbing be able to find a sequence of moves that lead to 2 gallons in the large jug and 0 gallons in the small jug? Justify your answer.
    3. Make a copy of the jugs.scm file and implement the described HEURISTIC function in that file. Be sure to test your function on numerous states to ensure that it works as decribed. For example,

      > (HEURISTIC '(0 0) '(2 0)) > (HEURISTIC '(4 1) '(2 0)) -1 -1.5
    4. Using your implementation of the heuristic function, determine whether a best first search leads to improved performance relative to an uninformed breadth first search. Do both searches produce the same answer? Is best first search faster? You will most likely need to make use of the time-reps function from Assignment 2 to execute and time multiple evaluations.
    5. Is the performance advantage/disadvantage of best first search with your heuristic consistent across all goals? That is, if best first search required less time to solve the Water Jug problem (Part D), can you find a different goal state for which breadth first search is actually faster? Or, likewise, if best first search required more time, is there a different goal state for which it is faster than breadth first search?

  2. Consider the following sliding-blocks puzle, consisting of three black tiles, three white tiles, and an empty space. The initial configuration for the puzzle consists of all the black tiles to the left, all of the white tiles to the right, and the empty space in the middle. For example, the following shows the initial configuration:


    The goal is to reverse the locations of the tiles, i.e., have all white tiles to the left and all black tiles to the right, with the space in the middle. There are two types of moves allowed. A tile can move into an adjacent empty space, or it can jump over two adjacent tiles into the empty space.

    1. Define a state space for this problem by specifying the representation of a state and listing all possible moves from one state to another.
    2. Attempt to solve this problem using the uninformed search control strategies: DFS-nocycles, BFS-nocycles, and DFS-deepening. Describe and compare your results.
    3. Now devise a heuristic that you think would help lead to a solution. Implement your heuristic as a Scheme function and solve the problem using best first search. Compare the performance of best first search using your heuristic with that of the uninformed strategies.


  1. The Scheme implementations of the search control strategies that we have studied in class all stop as soon as an answer is found. There are times, however, when it might be useful to look at alternative answers. Modify the best function to prompt the user when an answer is found. If the user finds that answer acceptable, then the function should return the answer (as before). If not, then the function should continue to find the next answer. For example: