CS63 HW1: State Space Search

Due by noon Friday, September 21

State space search is a general approach that can be applied to any problem domain that is deterministic, discrete, and static. In the reading from Russell and Norvig, they discussed a number of applications for this approach including route finding, VLSI layout, and automatic assembly sequencing. In class we examined how this approach could be applied to the water pitcher puzzle. In this homework, you will formulate a new problem so that state space search can be used. In addition, you will improve the efficiency of the state space search by recording all of the unique states that have been visited in a dictionary, and only adding unvisited states to the search queue.

Before you begin do an update63 to get a copy of the files you'll need to complete this homework. They should appear in the directory cs63/homework/01.


Missionaries and Cannibals

This problem is famous in AI because it was the subject of the first paper that approached problem formation in a formal way.

Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side of the river, without ever leaving a group of cannibals on one side of the river that are outnumbered by the missionaries (lest they become converted).

In your homework directory should be three files: search.py, pitcher.py and missionary.py.

The first file contains a general solution to state space search. It is based on four classes: Queue, Node, Search, and ProblemState. Notice that the last class is completely abstract. This is intended to be an interface for how to formulate any appropropriate problem for state space search. The pitcher.py file contains a concrete implementation of this abstract class.

  1. Execute the state space search on water pitcher problem: 
    % python pitcher.py
    After testing this, go through the code and make sure you understand how it functions.

  2. Formulate the missionaries and cannibals problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space showing the operators on the arcs. Given that the state space is so simple, why do you think people have a hard time solving this puzzle? Write your answer on the back of your diagram. Hand in your diagram outside my office.

  3. Implement your formulation in the file missionary.py, using the pitcher.py implementation as a model.


Improving State Space Search

The search has a verbose mode which by default is turned off. Turn on the verbose mode for an example of the water pitcher problem and observe how many states are being stored on the queue. Update the search algorithm so that it uses a dictionary to store a representation of all of the unique states that have been visited. The search should only add a node to the queue, if it is NOT already in this dictionary.


Submit
Once you are satisfied with your programs, hand them in by typing handin63 at the unix prompt.