HOMEWORK THREE
out 9/21, due 9/28

Uninformed State Space Search

Approaching problem solving as a search through a state space is a common and powerful technique. The basic algorithms for searching the state space graph are well known and easy to implement. The real work lies in deciding how to model the problem as a graph of possible states and how to implement a function to generate the graph. This assignment asks you to set up a simple problem for solution using any of the standard 'uninformed' search algorithms and to use the implementations associated with the text in Python or Java to solve the problem.

0 Background

Our text has code in Java and Python that implement various search algorithms. You are encouraged to try the Python version but are free to use the Java one or write your own. We'll give some examples for Python.

1 Missionaries and Cannibals

Solving the Missionaries and Cannibals problem is a classic example in AI. It was used in a seminal paper by Saul Amarel to demonstrate that changing a problem representation can have a big impact on the complexity of solving it. Here's one description of the problem.

Three missionaries and three cannibals are on the left bank of a river. A boat is available which will hold two people, and which can be navigated by any combination of missionaries and cannibals involving one or two people. If the missionaries on either bank of the river are outnumbered at any time by cannibals, the cannibals will indulge in their anthropophagic tendencies and do away with the missionaries who are outnumbered. Find a schedule of crossings that will permit all the missionaries and cannibals to cross the river from the left bank to the right bank safely.

Write a module, mc.py, for this standard problem using AIMA python code (search.py, utils.py and agents.py). if you copy these files to a directory, complete mc.py, and invoke 'python mc.py' you should get something like the output in mc.txt. As an example, wj.py implements the two water jugs problem, producing wj.txt as output.

2 Jealous husbands

Three traditional, but jealous, couples need to cross a river. Each couple consists of a husband and a wife. They find a small boat that can contain no more than two persons. Find the simplest schedule of crossings that will permit all six people to cross the river so that none of the women shall be left in company with any of the men, unless her husband is present. It is assumed that all passengers on the boat onboard before the next trip and at least one person has to be in the boat for each crossing.

Note that the number of men and women on each side of the river bank is not what is important in this problem, but which man is with which woman. While an unmarried man and woman can be in the boat without violating the constraint, when they reach the other side of the river, they must both disembark before the next action is taken. After disembarking on the shore, the people on that shore must satisfy the constraint.

Develop a module jh.py that sets up this problem for solution with the AIMA code.

What to hand in

Turn in your code for the two problems along with output showing them solving the standard problem for each.

Background reading

• Python tutorial
• Amarel, S. (1968). On representations of problems of reasoning about actions, Machine Intelligence.